DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME Thirty
TITLE: Parallel Algorithms
EDITORS: Sandeep N. Bhatt
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 past decade witnessed the development of parallel computers which were successfully used to solve large-scale numerical problems, typically arising from scientific and engineering applications. The use of massive parallelism in nonnumerical applications received considerably less attention. However, this period also witnessed a flurry of research in the design of algorithms for discrete combinatorial applications. Despite the large body of theoretical work on parallel algorithms for combinatorial problems, it was unclear what kinds of parallel algorithms would be effective in practice, and how well these would compete with standard sequential algorithms.

The Third Annual DIMACS Implementation Challenge was formulated with the view to provide a forum for a concerted effort to study effective algorithms for combinatorial problems, and to investigate opportunities for massive speedups on parallel computers. The challenge included two problem areas for research study: (a) tree searching algorithms, used in game search and combinatorial optimization for example; and (b) algorithms for sparse graphs.

Participants at sites in the U.S. and Europe undertook projects during the period from November 1993 to October 1994. The Challenge workshop was held at DIMACS on October 17 and 18, 1994. Following the workshop, participants were encouraged to share test instances where possible, to rework their implementations in light of the feedback at the workshop, and to submit a final report for the proceedings. Nine papers were selected for this volume.

Approximately 50 researchers attended the workshop; there were 17 project presentations, 7 invited talks, and a panel discussion. The specific application problems presented at the workshop included connected components and shortest paths in graphs, geometric clustering and dominance, graph partitioning, N-body algorithms for astrophyiscs, branch-and-bound techniques, and massively parallel chess. The invited presentations focused on topics ranging from good experimental methodology (Guy Blelloch, David Johnson); the interplay between modeling, algorithm design, and implementation (David Culler); and specific applications such as factoring (Arjen Lenstra), traveling salesman (David Applegate), and mesh partitioning (Shanghua Teng, Zdenek Johann).

The expert assistance of the DIMACS staff in hosting and arranging the workshop is gratefully acknowledged. The NSF STC grant supported Pangfeng Liu as a DIMACS post-doctoral fellow to help coordinate the Challenge. Thanks to Pangfeng for his efforts, and also to the rest of the Challenge Steering Committee, which included David Culler (UC Berkeley), David Johnson (AT&T Labs), Lennart Johnsson (Univ. of Houston) and Charles Leiserson (MIT).

Sandeep Bhatt
November 1996

TABLE OF CONTENTS

Foreword                                                                ix
Preface                                                                 xi

Connected components on distributed memory machines 
ARVIND KRISHNAMURTHY, STEVEN S. LUMETTA, DAVID E. CULLER, 
AND KATHERINE YELICK                                                     1 

Parallel implementation of algorithms for finding connected components 
  in graphs 
  TSAN-SHENG HSU, VIJAYA RAMACHANDRAN, AND NATHANIEL DEAN               23

Connected components algorithms for mesh-connected parallel computers
  STEVE GODDARD, SUBODH KUMAR, AND JAN F. PRINS                         43

Implementing parallel shortest-paths algorithms 
  MARIOS PAPAEFTHYMIOU AND JOSEPH RODRIGUE                              59 

Finding friends-of-friends clusters quickly 
  BRENDAN MUMEY                                                         69 

A practical comparison of N-body algorithms 
  GUY BLELLOCH AND GIRIJA NARLIKAR                                      81

Parallel algorithms for geometric dominance problems 
  JAN PETERSSON                                                         97

The *Socrates massively parallel chess program 
  CHRISTOPHER F. JOERG AND BRADLEY C. KUSZMAUL                         117 

Concurrent data structures and load balancing strategies for parallel 
  branch-and-bound/A* algorithms 
  V.-D. CUNG, S. DOWAJi, B. LE CUN, T. MAUTOR, AND C. ROUCAIROL        141
Index Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on October 28, 1998.