The circuit density offered by VLSI technology provides the means for implementing systems with a large number of processors. According to today's standards, a massively parallel processing (MPP) system consists of hundreds or thousands of processors. To achieve teraflops performance, it is expected that more and more processors are incorporated into a single system. An extremely important aspect of parallel computing is data communication among processors in parallel computing systems. Due to two-dimensionality, I/O constraints, and electrical properties such as resistance, capacitance, and inductance of VLSI circuits, the VLSI technology is not suitable for interconnecting communication intensive systems.
The advances in optical technologies have made it possible to implement optical interconnections in future MPP systems. Photons are non-charged particles, and do not naturally interact. Consequently, there are many desirable characteristics of optical interconnects, e.g., high speed (speed of light), increased fanout, high bandwidth, high reliability, supporting longer interconnection lengths, exhibiting low power requirements, and immunity to EMI with reduced crosstalk. Optics can utilize free-space interconnects as well as guided wave technology, neither of which has the problems mentioned for the VLSI technology. Optical interconnections can be built at various levels, providing chip-to-chip, module-to-module, board-to-board, and node-to-node communications.
Massively parallel processing using optical interconnections poses new challenges. In general, it does not worth the effort to improve performance by simply replacing the metal interconnections of a parallel system with optical interconnections in a one-to-one fashion. This is due to the fact that in doing so the inherent large bandwidth and high parallelism of optical interconnects are underutilized. The characteristics of optical interconnects have significant implications. New system configurations need to be designed due to the changes in architectural freedom and constraints when optical interconnects are incorporated. To fully utilize the bandwidth offered by the optical interconnections, scheduling and data communication schemes based on new resource metrics need to be investigated. Algorithms for a wide variety of applications need to be developed under novel computation models that are based on optical interconnections. Computations under these new models, which can be drastically different from existing theoretical PRAMs and parallel systems with electrical interconnections, may require new algorithm design techniques and performance measures.
The book is motivated by the fact that the area of massively parallel processing using optical interconnections has received increased attention in last few years, and noticeable progress has been made. A number of research groups and authors have been actively making contributions to this relatively new field. Though research in this area is still in its early stage, promising results have been demonstrated by experimental systems built in laboratories. There is need for better understanding of what optical technologies can offer for interconnections, how optical interconnections can be constructed, and what the impacts of optical interconnections are on MPP. A significant number of research articles have been published in various journals and conference proceedings, but there has not been a book that provides current and comprehensive coverage of the field, reflects the state-of-the-art from high-level architecture design and algorithmic points of view, and points out directions for further research and development. This book will serve to fill in this gap. The book is a collection of survey articles written by leading and active scientists in the area of parallel computing using optical interconnections. The primary purpose of the book is to provide an authoritative overview of the state-of-the-art of the field.
This book focuses on the potential of using optical interconnections in massively parallel processing systems, and their effects on system design and parallel computation. It is intended to provide readers the new perspectives of large-scale computing using optical interconnections. The emphases include the following aspects of MPP systems with optical interconnections:
The book consists of twelve chapters, which are grouped into two parts, with six chapters in each part. Part one covers optical interconnection networks and system architectures. Chapter 1, written by D.C. Hoffmeister, J. Chu, J.A. Perreault, and P. Dowd, provides a reconfigurable, hierarchical, wavelength division multiplexing (WDM) network called {\sc Lightning} for large-scale parallel computing in a distributed shared memory environment. Chapter 2, contributed by T.H. Szymanski, examines the class of ``Intelligent Optical Networks". In Chapter 3, A. Louri and B. Weech describe a scalable interconnection topology called Spanning Multichannel Linked Hypercube (SMLH) as well as its optical implementation, and compare SMLH with many popular networks. Chapter 4, by R. Melhem, G. Gravenstreter, D. Chiarulli, and S. Levitan, is devoted to the communication capabilities of the Partitioned Optical Passive Stars (POSP) network, together with message routing and scheduling on POSP, and analytical performance evaluation and simulations results. Chapter 5, authored by C.-f. Wang and S. Sahni, deals with the characteristics of parallel computers with optical transpose interconnection systems (OTIS), and summarizes the complexities of basic operations and fundamental algorithms on these systems. In Chapter 6, H.-A. Choi and E.J. Harder address the problems of routing and wavelength assignment in efficient use of WDM optical networks.
Part two of the book focuses on models and algorithms for optical interconnections. Several models are presented that make algorithm design, specification, and performance comparison relatively easier without worrying about optical engineering details. Algorithms and applications in this part include selection and sorting, numerical computations, matrix operations, image processing, and others. In Chapter 7, S.Q. Zheng proposes the hypernetwork model for optical interconnection networks, and shows how to design hypernetworks by using theory of hypergraphs and combinatorial block design. Chapter 8, written by C. Qiao, presents the Reconfigurable Array with Spanning Optical Buses (RASOB) model, together with example algorithms and embeddings. Chapter 9, contributed by S. Rajasekaran and S. Sahni, discusses and analyzes basic and important algorithms, deterministic and randomized, on the Array with Reconfigurable Optical Buses (AROB) model. In Chapter 10, S.D. Pavel and S.G. Akl develop optimal constant time algorithms for applications in image processing on the AROB model. Chapter 11, authored by Y. Pan, gives a comprehensive presentation of a model called Linear Array with Reconfigurable Pipelined Bus System (LARPBS), and implementation details of a number of primitive and fundamental operations. Finally, in Chapter 12, K. Li demonstrates novel implementations of fast and processor efficient parallel algorithms for matrix multiplication and related matrix manipulations on the LARPBS model by using the building blocks in Chapter 11.
The reader should keep in mind that the above division of the book into two parts is based on the emphasis of the chapters. It is virtually impossible to designate some chapters into certain category, since a chapter in Part one may contain algorithms, and a chapter in Part two may include optical implementation details, due to intimate interplay of various aspects of parallel computing. Each chapter is about 20-25 pages long and focuses on a particular topic. The material are survey/tutorial type and are based on published papers; some original results are also included. The extensive bibliography at the end of the chapters provide references for further information.
The book is primarily written for scientists, researchers, engineers, developers, educators, and administrators from universities, industries, research institutes and laboratories, and government agencies in the area of parallel and distributed computing. The interdisciplinary feature of the book is likely to be appealing to a wide range of audience. They will find this book a unique source of information on recent advances and future directions of parallel computation using optical interconnections. Since this is the first book addressing parallel architectures, algorithms, and applications using optical interconnection networks, we expect that the book will be an informative and useful reference in this new and fast growing research area.
The organization of this book makes it particularly useful for graduate courses. It can be used as a text for a research oriented and seminar based advanced graduate course. Graduate students will find the material covered by this book to be stimulating and inspiring. Using this book, they can identify interesting and important research topics for their Master's theses and Ph.D. dissertations. It can also serve as a supplementary book for regular courses on Parallel Architectures, Parallel Algorithms, and High-Performance Computing taught in Computer Science, Computer Engineering, and Electrical Engineering Departments.
The book is a successful result of collaboration, cooperation, and commitment among many researchers. We are very grateful to all the 22 contributing authors from the community of parallel computing with optical interconnections. Their expertise, energy, and enthusiasm have made it possible for us to edit and publish such a book in a short period of time. We also acknowledge ten anonymous reviewers of our book proposal for their encouragement and critical comments that helped greatly in shaping the scope and coverage of the book. The publication of the book originated from a lengthly discussion between the first editor and Mr. Scott E. Delman, a senior publishing editor of Computer and Information Science of Kluwer Academic Publishers, in the summer of 1997. We appreciate Scott's suggestions, guidance, and advice during the course of this endeavor. The book would not have been published without his initial push and encouragement. Our thanks extend to other staff of Kluwer Academic Publishers, in particular, Ms. Sharon Fletcher and Ms. Suzanne St. Clair, for their strong support in many aspects during various stages of the production of this book. Last but not least, we wish to express our most sincere gratitude to our wives and children, Ling, Andrew, and Charlotte of the Li's family, Hong and Marissa of the Pan's family, Lin Li, Ting An, and Lee Ming of the Zheng's family, and the families of all the contributing authors, for their support and sacrifice when all of us were working under very tight schedule.
Keqin Li, Yi Pan, Si Qing Zheng, July 1998
(The authors are listed in alphabetical order. An author marked with [x] is the contact person of Chapter x, 1 <= x <= 12.)
Selim G. Akl [10] is a professor of computing and information science at Queen's University, Kingston, Ontario, Canada. His current research interests are in the area of parallel algorithms, with a particular emphasis on alternative models of computation and inherently parallel paradigms. He is the author of Parallel Sorting Algorithms (Academic Press, 1985), The Design and Analysis of Parallel Algorithms (Prentice Hall, 1989), and Parallel Computation: Models and Methods (Prentice Hall, 1997), and co-author of Parallel Computational Geometry (Prentice Hall, 1992). He is an editor of Information Processing Letters (North-Holland), Computational Geometry (Elsevier), Parallel Processing Letters (World Scientific Publishing), and Parallel Algorithms and Applications (Gordon & Breach).
Donald Chiarulli received his B.S. degree (physics, 1976) from Louisiana State University, M.S. (computer science, 1979) from Virginia Polytechnic Institute, and Ph.D. (computer science, 1986) from Louisiana State University. He was an instructor/research associate at LSU from 1979 to 1986, and has been at the University of Pittsburgh since 1986. His current research includes several projects concerned with the architecture, implementation, and application of scalable parallel processing systems.
Hyeong-Ah Choi [6] is currently a professor of computer science at the George Washington University, Washington, DC. She has published over 60 technical papers in parallel processing, optical interconnects, and algorithms. She is a coauthor of the paper received an Outstanding Paper Award at the 1996 IEEE International Conference on Parallel Processing.
John Chu received the B.S. degree in electrical engineering from the State University of New York at Buffalo in 1992. He was a Presidential Fellow at SUNY at Buffalo, and received the M.S. degree in electrical engineering in 1996. He is currently pursuing the Ph.D. degree.
Patrick Dowd [1] received the B.S. in electrical engineering and computer science (Summa Cum Laude) from the State University of New York at Buffalo in 1983, M.S. (1985) and Ph.D. (1988) degrees in electrical engineering from Syracuse University. Currently he is an associate professor in the Department of Electrical Engineering and UMIACS at the University of Maryland at College Park, and also holds the position of senior research scientist at the Advanced Networking Research Department, U.S. Department of Defense. He has served in various important positions for numerous international conferences, and is currently on the executive committee of ACM SIGCOMM, and an area technical program committee chair of INFOCOM98. He also serves on the editorial board of the International Journal in Computer Simulation, and is an associate editor of the SCS Transactions on Simulation, and the editor of the electronic journal Computer Simulation: Modeling and Analysis. He is a member of IEEE and ACM with research interests in high speed networks, cluster-based computing, mobile and optical communication.
Greg Gravenstreter is currently involved in networking and security at the Software Engineering Institute within Carnegie Mellon University. From 1971 to 1985, he was with the Westinghouse Electric Corporation's Research and Development Center. He worked as Director of Systems and Operations for Guidance Technologies in Pittsburgh from 1988 to 1992. His interests include a wide range of network and security issues, architectural and systems issues for parallel and distributed systems.
Eric J. Harder received his D.Sc. in computer science in 1998 from the George Washington University. He is currently a senior computer scientist with the U.~S. Department of Defense. His research interests include approximation and online algorithms for routing and wavelength assignment, applied graph theory, and combinatorics.
David C. Hoffmeister received the B.S. (summa cum laude) and M.S. degrees in electrical and computer engineering from the State University of New York at Buffalo in 1994 and 1996, respectively. He is currently pursuing the Ph.D. degree in that department. His research interests include WDM networks, reconfigurable networks, distributed network control, and all-optical networks.
Steven P. Levitan is the Wellington C. Carl associate professor of electrical engineering at the University of Pittsburgh. He received the B.S. degree from Case Western Reserve University in 1972. From 1972 to 1977 he worked for Xylogic Systems. He received his M.S. (1979) and Ph.D. (1984) degrees, both in computer science, from the University of Massachusetts, Amherst. During that time he also worked for Digital Equipment Corporation, and Viewlogic Systems, as a consultant in HDL simulation and synthesis. He was an assistant professor from 1984 to 1986 in the Electrical and Computer Engineering Department at the University of Massachusetts. In 1987 he joined the electrical engineering faculty at the University of Pittsburgh where he holds a joint appointment in the Department of Computer Science. He is the editor of the SIGDA Newsletter and Manager of the SIGDA Internet Server.
Keqin Li [12] received B.S. degree in computer science from Tsinghua University, China, in 1985, and Ph.D. degree in computer science from the University of Houston in 1990. He is currently an associate professor of computer science in State University of New York at New Paltz. He has published over 100 technical papers and received best paper awards in 1996 International Conference on Parallel and Distributed Processing Techniques and Applications, and 1997 IEEE National Aerospace and Electronics Conference. He is the Associate Editor-in-Chief of International Journal of Parallel and Distributed Systems and Networks. He is the program chair of the 9th International Conference on Parallel and Distributed Computing and Systems (October 1997), a general co-chair of the 10th International Conference on Parallel and Distributed Computing and Systems (October 1998), a conference co-chair of the 4th International Conference on Computer Science and Informatics (October 1998), and the vice program chair of the IPPS Workshop on Optics and Computer Science (April 1999). He is a senior member of IEEE, and a member of IEEE Computer Society, ACM, SIGACT, SIGARCH, SIAM, ISMM, IASTED, and SCS.
Ahmed Louri [3] is currently an associate professor of electrical and computer engineering at the University of Arizona and Director of the Optical Networking and Parallel Processing Laboratory. His research interests include computer architecture, parallel processing, optical computing, and optical interconnects. He has published numerous journal and conference articles on the above topics. He has served as a member of the technical program committee of several conferences including OSA Topical Meeting on Optics in Computing, OSA/IEEE Conference on Massively Parallel Processors using Optical Interconnects, among others. In 1996 he was the general chair of the Workshop on Optics in High-Performance Computing, at Euro-Par'96 Lyon France. He is a senior member of the IEEE and a member of the ACM, OSA, and SPIE.
Rami Melhem [4] is a professor of computer science at the University of Pittsburgh. He served on program committees of numerous conferences and workshops and as the general chair for the third International Conference on Massively Parallel Processing Using Optical Interconnections. He was on the editorial board of the IEEE Transactions on Computers and is currently on editorial board of the IEEE Transactions on Parallel and Distributed Systems. His research interests include fault-tolerant and real-time systems, optical interconnection networks, high performance computing, and parallel computer architectures.
Yi Pan [11] received his B.Eng. degree in computer engineering from Tsinghua University, China, in 1982, and his Ph.D. degree in computer science from the University of Pittsburgh, USA, in 1991. Currently he is an associate professor at the University of Dayton. He is an author of more than 60 research papers, and has received several awards including NSF Research Opportunity Award, AFOSR Summer Faculty Fellowship, Andrew Mellon Fellowship from Mellon Foundation, the best paper award from PDPTA '96, and Summer Research Fellowship from the Research Council of the University of Dayton. He is currently on the editorial boards of the Journal of Supercomputing and the Journal of Parallel and Distributed Computing Practices, and is an associate editor of the International Journal of Parallel and Distributed Systems and Networks. He is the program chair of the 10th International Conference on Parallel and Distributed Computing and Systems in 1998, the conference co-chair of the 4th International Conference on Computer Science and Informatics in 1998, and the program chair of the 1999 IPPS Workshop on Optics and Computer Science. He is a senior member of IEEE and a member of the IEEE Computer Society. He is listed in Men of Achievement and Marquis Who's Who in Midwest.
Sandy D. Pavel is currently a member of the scientific staff at Nortel (Northern Telecom) in Ottawa, Canada. He received the Ph.D. degree in computer science from Queen's University at Kingston, Ontario, Canada. His research interests include algorithms, high-speed network protocols, IP over optical networks, and all-optical networking.
James A. Perreault received the B.S., M.S., and Ph.D. degrees in electrical and computer engineering from the State University of New York at Buffalo in 1991, 1994, and 1998, respectively. Since 1997, he has been working for the Department of Defense in advanced network research. His research interests include all-optical networking, switch design, and IP quality of service.
Chunming Qiao [8] got his BS degree in 1985 from University of Science and Technology of China (USTC) in China. He received the Andrew-Mellon Distinguished doctoral fellowship award from University of Pittsburgh and obtained his Ph.D. degree in 1993. Since then, he has been with SUNY at Buffalo. He received an NSF Research Initiation Award (RIA) in 1994 for his research on fiber-optic interconnection networks, and recently, another NSF grant for research on fiber-optic wavelength division multiplexed (WDM) networks and internetworking (e.g., optical internet). His research interests cover the two converging areas of computers and communications, including parallel and distributed computing and systems, interconnection networks, and photonic switching. He has published many papers in these areas in IEEE Trans. on Computers, IEEE Trans. on Parallel and Distributed Systems, IEEE Trans. on Communications, and IEEE/ACM Trans. on Networking. He has served as a co-chair for both the 1997 and 1998 All-optical Networking Conferences sponsored by SPIE (International Society for Optical Engineering), a program vice co-chair for the 1998 International Conf. on Computer Communications and Networks (IC3N), a session organizer/chair at the IEEE MILCOM'96 (the Conference on Military Communications), and program committee members and session chairs in several other conferences and workshops. He is also an editor of the Journal on High-Speed Networks (JHSN) and a member of IEEE Computer Society and IEEE Communications Society.
Sanguthevar Rajasekaran [9] is an associate professor in the Department of Computer and Information Science and Engineering at the University of Florida. He received his Ph.D. from Harvard University in 1988. His research interests include parallel algorithms, randomized computing, combinatorial optimization, parsing, and image processing. He has published more than 80 papers in journals, conferences, and books. He is a co-author of the texts Computer Algorithms and Computer Algorithms/C++ published by W.H. Freeman Press. He serves on the editorial boards of IEEE Transactions on Computers and the Journal of Parallel and Distributed Computing.
Sartaj Sahni [5] is a University of Florida Research Foundation Professor of computer and information sciences and engineering and a Fellow of IEEE, ACM, AAAS, and Minnesota Supercomputer Institute. He received his B.Tech. (electrical engineering) degree from the Indian Institute of Technology, Kanpur, and the M.S. and Ph.D. degrees in computer science from Cornell University. He has published over 150 research papers and written several texts. His research publications are on the design and analysis of efficient algorithms, parallel computing, interconnection networks, and design automation. In 1997, he was awarded the IEEE Taylor L. Booth Education Award ``for contributions to Computer Science and Engineering education in the areas of data structures, algorithms, and parallel algorithms''. He is a co-editor of the Journal of Parallel and Distributed Computing and is on the editorial boards of IEEE Parallel and Distributed Technology, and Computer Systems: Science and Engineering. He has served as program committee chair, general chair, and been a keynote speaker at many conferences.
Ted H. Szymanski [2] is an associate professor at McGill University. He has served as the Director of the Microelectronics and Computer Systems Laboratory at McGill, and as a project leader in the Canadian Institute for Telecommunications Research. His research interests include optical networks, telecommunication and computing architectures, and performance analysis. He has been on the program committees of the 1998 and 1997 Workshops on Optics in Computer Science, the 1998 and 1997 International Conferences on Massively Parallel Processing using Optical Interconnects, the 1998 International Conference on Optical Computing, the 1997 Innovative Systems on Silicon Conference, the 1995 Workshop on High-Speed Network Computing, and the 1998, 1995 and 1994 Canadian Conferences on Programmable Logic Devices. He is a member of the IEEE Computer and Communications Societies.
Chih-fang Wang is currently a Ph.D. candidate at the Department of Computer and Information Science and Engineering, University of Florida. He got his M.S. degree in mathematics and computer science from University of Miami in 1993. His research interests include distributed and parallel algorithms, reconfigurable networks, optical interconnection computers, and all-optical networks.
Brent Weech is an M.S. candidate at the University of Arizona. He received the B.S. degree in electrical engineering from Arizona State University in 1994. His research interests include parallel and distributed processing, communication networks, and optical interconnects. He is a student member of the IEEE.
Si Qing Zheng [7]
received the Ph.D. degree in computer science
from the University of California, Santa Barbara, in 1987,
and joined the faculty of Louisiana State University in the same year.
He was an associate professor of computer science and
an adjunct associate professor of electrical and computer engineering
at LSU before moving to the University of Texas at Dallas in 1998,
where he is currently a professor of computer science.
He has published 130 refereed papers in
VLSI design, computer architectures, parallel and distributed computing,
optical interconnections, computer networks,
and design and analysis of algorithms.
He was the program committee chairman of the
8th International Conference on Computing and Information (1996),
the program committee co-chairman of the
10th ISCA International Conference on
Parallel and Distributed Computing Systems (1997),
and the program committee vice chairman of the
2nd International Conference on
Parallel and Distributed Computing and Networks (1998).
He is an associate editor of several computing journals.
Preface ............ ix
Contributing Authors ............ xiii
Chapter 1. Lightning Network and Systems Architecture ............ 3
David C. Hoffmeister, John Chu, James A. Perreault, and Patrick Dowd
1.1 Introduction ............ 4
1.2 Lightning Architecture ............ 5
1.3 Dynamic Bandwidth Reallocation ............ 10
1.4 Performance Analysis ............ 17
1.5 Conclusions ............ 21
References ............ 21
Chapter 2. Parallel Computing with ``Intelligent Optical Networks'' ............ 25
Ted H. Szymanski
2.1 Introduction ............ 26
2.2 Intelligent Optical Networks ............ 30
2.3 Parallel Computing with Intelligent Optical Networks ............ 33
2.4 Analysis of Butterfly Algorithms (Parallel Sorting) ............ 34
2.5 Performance and Bandwidth Relationship ............ 36
2.6 Scalability to U.S. Accelerated Computing Initiative Targets ............ 41
2.7 Conclusions ............ 43
References ............ 44
Chapter 3. Scalable Optical Interconnection Networks for Large-scale Parallel Computers ............ 47
Ahmed Louri and Brent Weech
3.1 Introduction ............ 48
3.2 Structure of the Spanning Multichannel Linked Hypercube Network ............ 49
3.3 Comparisons of SMLH with Popular Networks ............ 57
3.4 Optical Implementation of the SMLH Network ............ 64
3.5 Power and Delay Analysis of the Optical Implementation ............ 70
3.6 Conclusions ............ 73
References ............ 74
Chapter 4. The Communication Capabilities of Partitioned Optical Passive Stars Networks ............ 77
Rami Melhem, Greg Gravenstreter, Donald Chiarulli, and Steven Levitan
4.1 Introduction ............ 77
4.2 Description of The POPS Topology ............ 79
4.3 Communication Using POPS Networks ............ 82
4.4 Permutation Capabilities of The POPS Topology ............ 83
4.5 Realization of Specific Communication Patterns ............ 93
4.6 Conclusion ............ 96
References ............ 97
Chapter 5. OTIS Optoelectronic Computers ............ 99
Chih-fang Wang and Sartaj Sahni
5.1 Introduction ............ 99
5.2 Optical Transpose Interconnection System (OTIS) ............ 100
5.3 OTIS Parallel Computers ............ 102
5.4 OTIS-Mesh ............ 103
5.5 OTIS-Hypercube ............ 108
5.6 Permutation Routing on OTIS Computers ............ 110
5.7 Summary of Other Results ............ 112
5.8 Summary ............ 114
References ............ 115
Chapter 6. On Wavelength Assignment in WDM Optical Networks ............ 117
Hyeong-Ah Choi and Eric J. Harder
6.1 Introduction ............ 117
6.2 Complexity ............ 119
6.3 All-to-All Gossiping on Square Meshes ............ 123
6.4 File Transfer in Optical Networks ............ 128
6.5 Summary ............ 134
References ............ 134
Chapter 7. An Abstract Model for Optical Interconnection Networks ............ 139
Si Qing Zheng
7.1 Introduction ............ 139
7.2 Optical Multiconnect Hardware ............ 140
7.3 Hypernetworks ............ 142
7.4 Hypernetwork Design Based on Duals of Hypergraphs ............ 145
7.5 Using Combinatorial Block Design Theory to Design Hypernetworks ............ 152
7.6 Summary ............ 160
References ............ 161
Chapter 8. A Unique Design of Fiber-optic Interconnection Networks and Algorithms ............ 163
Chunming Qiao
8.1 Introduction ............ 163
8.2 The RASOB Model ............ 165
8.3 Algorithm Development ............ 171
8.4 Summary ............ 182
References ............ 183
Chapter 9. Fundamental Algorithms for the Array with Reconfigurable Optical Buses ............ 185
Sanguthevar Rajasekaran and Sartaj Sahni
9.1 Introduction ............ 185
9.2 Preliminaries ............ 188
9.3 Packet Routing ............ 190
9.4 Sorting on the AROB ............ 197
9.5 Selection ............ 199
9.6 Conclusions ............ 201
References ............ 202
Chapter 10. Computing the Hough Transform on Arrays with Reconfigurable Optical Buses ............ 205
Sandy D. Pavel and Selim G. Akl
10.1 Introduction ............ 205
10.2 The AROB Model ............ 208
10.3 The HT for line detection on AROB ............ 214
10.4 An HT algorithm for circle detection on AROB ............ 217
10.5 Conclusions ............ 223
References ............ 224
Chapter 11. Basic Data Movement Operations on the LARPBS Model ............ 227
Yi Pan
11.1 Introduction ............ 227
11.2 The LARPBS Model ............ 229
11.3 Basic Data Movement Operations ............ 233
11.4 Scalability Issues ............ 241
11.5 Conclusions ............ 242
References ............ 243
Chapter 12. Fast Matrix Multiplication and Related Operations Using Reconfigurable Optical Buses ............ 249
Keqin Li
12.1 Introduction ............ 250
12.2 The LARPBS Computational Model ............ 253
12.3 An O(N) Algorithm Using N$^2$ Processors ............ 257
12.4 An O(1) Algorithm Using N$^3$ Processors ............ 258
12.5 An O(logN) Algorithm Using O(N$^2.8074$) Processors ............ 261
12.6 Compound Algorithms ............ 264
12.7 Applications to Other Matrix Operations ............ 267
12.8 Concluding Remarks ............ 269
References ............ 271
Index ............ 275
``This is the first book in the area of optical interconnection networks. The interdisciplinary feature of this book will be very appealing to a wide range of audience."
``It will be a valuable reference book for academic and/or industry professionals working in the areas covered by the book."
``The breadth and depth, and the very unique feature of this book make it stand out. This book may have far-reaching impact on future directions of parallel and distributed computing."
``The editors are all famous international leading researchers on parallel computing and have very high international reputation in the field."
``Due to the increasing importance of parallel computing and optical networks, this book will be extremely significant for promotion of research in this new trend."
``So technically you will have no problem in selling the book."
``This would be a great book for the parallel and distributed computing communities. It is time for someone to put such a book together. This book would be a great reference book for both people in academic and industry, everybody can find an interesting subject."
``This would be the first book covering a very important new area of computer science."
``This book will be of interest to numerous researcher in this area."
``This is likely to be a "must have" for all university libraries, for workers in the field, for graduate students in computer science and engineering, in a word, a large audience."
``Looks like a winner. I am convinced this book fills a real need in the community and that it will be a very welcome addition to any library."
``I believe that any serious computer science/engineering publisher
will be pleased with such a book."
Distributors for North, Central and South America:
Kluwer Academic Publishers
101 Philip Drive
Assinippi Park
Norwell, Massachusetts 02061
U.S.A.
Tel: (781) 871-6600
Fax: (781) 871-6528
Email: kluwer@wkap.com
Distributors for all other countries:
Kluwer Academic Publishers Group
Distribution Center
Post Office Box 322
3300 AH Dordrecht
The Netherlands
Tel: 31-78-6392-392
Fax: 31-78-6546-474
Email: orderdept@wkap.nl