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 AbstractThis 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.pdf1.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.