From: pan@udcps.cps.udayton.edu (Dr. Yi Pan)
Newsgroups: comp.parallel
Subject: no subject (file transmission)
Date: 17 Oct 1998 06:21:20 GMT
Organization: <NONE>
Approved: bigrigg@cs.cmu.edu
Message-Id: <709d10$7iv$1@encore.ece.cmu.edu>
Originator: bigrigg@ece.cmu.edu


  ------------------------------------------------------------------------

              Parallel Computing Using Optical Interconnections

                                  Edited by

             Keqin Li, State University of New York at New Paltz

                        Yi Pan, University of Dayton

                Si Qing Zheng, University of Texas at Dallas

                         Kluwer Academic Publishers

                       Published on September 25, 1998

                             ISBN 0-7923-8296-X

  ------------------------------------------------------------------------

Preface

Motivation

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.

Book Organization and Chapter Overview

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:

   * Various optical interconnects and their implementations, high-level
     system design, scalability, reconfigurability, partitionability, and
     performance evaluation;
   * Data communication schemes, resource scheduling, embedding, and mapping
     methods;
   * Models for parallel computing using optical interconnections, algorithm
     design and development, and applications.

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.

Audience and Use of the Book

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.

Acknowledgments

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

  ------------------------------------------------------------------------

Contributing Authors

(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.

  ------------------------------------------------------------------------

Table of Contents

Preface ............ ix

Contributing Authors ............ xiii

Part 1: Optical Interconnection Networks and System Architectures
............ 1

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

Part 2: Models and Algorithms for Optical Interconnections ............ 137

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

  ------------------------------------------------------------------------

What the Reviewers Said

``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."

  ------------------------------------------------------------------------

Ordering Information

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

Electronic Services

  ------------------------------------------------------------------------

--
Articles to bigrigg+parallel@cs.cmu.edu (Admin: bigrigg@cs.cmu.edu)
Archive: http://www.hensa.ac.uk/parallel/internet/usenet/comp.parallel