Title page for ETD etd-1104102-000906


Type of Document Dissertation
Author He, Min
Author's Email Address mhe@bit.csc.lsu.edu
URN etd-1104102-000906
Title Efficient Parallel Computation on Multiprocessors with Optical Interconnection Networks
Degree Doctor of Philosophy (Ph.D.)
Department Computer Science
Advisory Committee
Advisor Name Title
Donald Kraft Committee Chair
Si Qing Zheng Committee Co-Chair
Jianhua Chen Committee Member
Ramachandran Vaidyanathan Committee Member
S. Sitharama Iyengar Committee Member
Mike Cherry Dean's Representative
Keywords
  • optical networks
  • selection
  • parallel algorithms
  • boolean matrix multiplication
  • sorting
Date of Defense 2002-10-14
Availability unrestricted
Abstract
This dissertation studies optical interconnection networks, their architecture, address schemes, and computation and communication capabilities. We focus on a simple but powerful optical interconnection network model - the Linear Array with Reconfigurable pipelined Bus System (LARPBS). We extend the LARPBS model to a simplified higher dimensional LAPRBS and provide a set of basic computation operations. We then study the following two groups of parallel computation problems on both one dimensional LARPBS's as well as multi-dimensional LARPBS's: parallel comparison problems, including sorting, merging, and selection; Boolean matrix multiplication, transitive closure and their applications to connected component problems.

We implement an optimal sorting algorithm on an n-processor LARPBS. With this optimal sorting algorithm at disposal, we study the sorting problem for higher dimensional LARPBS's and obtain the following results:

An optimal basic Columnsort algorithm on a 2D LARPBS.

Two optimal two-way merge sort algorithms on a 2D LARPBS.

An optimal multi-way merge sorting algorithm on a 2D LARPBS.

An optimal generalized column sort algorithm on a 2D LARPBS.

An optimal generalized column sort algorithm on a 3D LARPBS.

An optimal 5-phase sorting algorithm on a 3D LARPBS.

Results for selection problems are as follows:

A constant time maximum-finding algorithm on an LARPBS.

An optimal maximum-finding algorithm on an LARPBS.

An O((log log n)2) time parallel selection algorithm on an LARPBS.

An O(k(log log n)2) time parallel multi-selection algorithm on an LARPBS.

While studying the computation and communication properties of the LARPBS model, we find Boolean matrix multiplication and its applications to the graph are another set of problem that can be solved efficiently on the LARPBS. Following is a list of results we have obtained in this area.

A constant time Boolean matrix multiplication algorithm.

An O(log n)-time transitive closure algorithm.

An O(log n)-time connected components algorithm.

An O(log n)-time strongly connected components algorithm.

The results provided in this dissertation show the strong computation and communication power of optical interconnection networks.

Files
  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  He_dis.pdf 1.27 Mb 00:05:52 00:03:01 00:02:38 00:01:19 00:00:06

Browse All Available ETDs by ( Author | Department )

If you have questions or technical problems, please Contact LSU-ETD Support.