DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME Twenty One
TITLE: Workshop on Interconnection Networks and Mapping and Scheduling Parallel Computations
EDITORS: D. Frank Hsu, Arnold L. Rosenberg, Dominique Sotteau
Published by the American Mathematical Society

Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

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.

PREFACE

The interconnection network is one of the most basic components of a massively parallel computer system. Each system consists of hundreds or thousands of processors, interconnected to work cooperatively on computations. One of the central problems in parallel computing is the task of mapping a collection of processes onto the processors and routing network of a parallel machine. Once processors are mapped onto the physical processors, it is critical to schedule computation within and communication among processors so that the necessary inputs for a process would be available where and when the process is scheduled to be computed.

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.
hsu@murray.fordham.edu

Arnold L. Rosenberg, Amherst, MA,
U.S.A. rsnbrg@cs.umass.edu

Dominique Sotteau, Orsay, France
sotteau@lri.lri.fr

TABLE OF CONTENTS


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
Index Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on October 28, 1998.