To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.
You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.
In the context of the 1993-94 DIMACS Special Year on Massively Parallel Computation, funded jointly by the National Science Foundation and the New Jersey Commission for Science and Technology, a three-day workshop on Interconnection Networks and Mapping and Scheduling Parallel Computations was held on February 7-9, 1994. The Workshop focused on the interconnection networks of parallel architectures of today and of the near future, examining the task of mapping and scheduling parallel computations on these parallel machines. Subject areas covered included network topologies, network properties, message routing, network embeddings, network emulation, mappings, and efficient scheduling.
The Workshop was held at DIMACS at Rutgers University, Piscataway, New Jersey. DIMACS is the National Science Foundation science and technology center for discrete mathematics and computer science. It is a consortium of Rutgers and Princeton Universities, AT&T Bell Laboratories, and Bellcore.
There were 49 presentations in the 12 scheduled sessions of the Workshop. Over 115 scientists, mathematicians, and engineers from inside and outside DIMACS, and from 14 countries attended the Workshop. Participants included researchers from universities and research laboratories, as well as practitioners who are involved with the design, implementation, and application of massively parallel computer systems.
All speakers were invited to submit their complete papers following talks given at the Workshop. All manuscripts have been refereed according to the standard of a high-quality journal. This volume contains 21 accepted papers. All of the papers are in final form. A DIMACS technical report, which contains titles and abstracts for the talks and the program and schedule of the Workshop, is available upon request.
We would like to thank the DIMACS Executive Committee and the Special Year Organizing Committee for sponsoring the Workshop. Diane Souvaine, Pat Toci, and Maryann Holtsclaw all provided great help. Tom Leighton and Bruce Maggs were of enormous help in the process of organizing the Workshop. We also want to thank Christine Thivierge, Donna Harmon, Shirley Hill, and Jennifer Sharp at the AMS for helping to prepare this volume.
D. Frank Hsu, New York, U.S.A.
Arnold L. Rosenberg, Amherst, MA,
Dominique Sotteau, Orsay, France
Foreword vii Preface ix Ranking algorithms for Hamiltonian paths in hypercubic networks 1 FRED S. ANNEXSTEIN Dense bus networks of diameter 2 J.-C. BERMOND. J. BOND, AND S. DJELLOTOUL 9 On broadcasting schemes in restricted optical passive star systems P. BERTHOME AND A. FERREIRA 19 Restricted routing and wide diameter of the cycle prefix network W. Y. C. CHEN, V. FABER. AND E. KNILL 31 Permutation routing via Cayley graphs with an example for bus interconnection networks GENE COOPERMAN AND LARRY FINKELSTEIN 47 Using helpful sets to improve graph bisections RALF DIEKMANN, BURKHARD MONIEN, AND ROBERT PREIS 57 Modification of consecutive-d digraphs DING-ZHU DU, D. FRANK HSU, AND DANIEL J. KLEITMAN 75 Highly adaptive wormhole routing algorithms for N-dimensional torus JOSE DUATO AND PEDRO LOPEZ 87 Conflict-free access to constant-perimeter, rectangular, subarrays DOREEN L. GALLI ERICKSON AND CHARLES J. COLBOURN 105 Makespan Minimization of task graphs with random task running times LUCIAN FINTA AND ZHEN LIU 125 Scheduling Of Structured and Unstructured computation APOSTOLOS GERASOULIS, JIA JIAO, AND TAO YANG 139 Routing in Optical networks: The problem of contention LESLIE ANN GOLDBERG 173 Communications in optically interconnected parallel computer systems MOUNIR HAMDI 181 Fault-tolerant Kautz networks RABAH HARBANE 201 Asynchronous packet routers CHRIS JESSHOPE AND IVAILO NEDELCHEV 211 Cayley digraphs of finite cyclic groups with minimal average distance XINGDE JIA 229 Shuffled tree based fault-tolerant hierarchical interconnection networks OMAR H. KARAM AND DHARMA P. AGRAWAL 251 Restricted connectivity and restricted fault diameter of some interconnection networks Li QIAO AND ZHANG YI 267 Sorting and selection on interconnection networks SANGUTHEVAR RAJASEKARAN 275 Towards a simple construction method for Hamiltonian decomposition of the hypercube S. W. SONG 297 Generalized reduced hypercube interconnection networks for massively parallel computers SOTIRIOS G. ZIAVRAS 307 List of Participants 327