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

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