9th Annual ACM Symposium
on Parallel Algorithms
and Architectures
Newport, Rhode Island
June 22 - 25, 1997

Sponsored by
In Cooperation with EATCS

New this year:
Collocation with FPCC'97
The 2nd Forum on
Parallel Computing Curricula
June 22, 1997

For more information see

                      SUNDAY, JUNE 22, 1997

10:00 am - 5:00 pm    FPCC'97
6:00 pm - 8:00 pm      SPAA registration
7:00 pm - 9:00 pm      SPAA and FPCC reception

                      MONDAY, JUNE 23, 1997

                                     Session 1

8:45     Efficient Detection of Determinacy Races in Cilk  
            Mingdong Feng, National U. of Singapore;
            Charles E. Leiserson, MIT

9:10     Space-Efficient Scheduling of Parallelism with
               Synchronization Variables
           Guy E. Blelloch, CMU; Phillip B. Gibbons, Yossi
            Matias, Bell Labs; Girija J. Narlikar, CMU

9:35    Reactive Diffracting Trees
           Giovanni Della-Libera, Microsoft and MIT; Nir
           Shavit, Tel-Aviv U. and MIT

10:00  Break
                            Session 2
10:30  Efficient Load Balancing and Data Remapping
              for Adaptive Grid Calculations
          Leonid Oliker, RIACS; Rupak Biswas, MRJ
             Technology Solutions, NASA Ames

10:55  HARP: A New Dynamic Inertial Spectral
         Horst Simon, NERSC; Andrew Sohn, New
             Jersey Inst. of Tech.
; Rupak Biswas, MRJ
            Technology Solutions, NASA Ames

11:20 Three-Dimensional Pattern Matching
         Kunsoo Park, Seoul Nat. U., Korea; Zvi
         Galil, Columbia U.; Jong Geun Park, Chonbuk Nat.
            U., Korea

11:45 On the Parallel Complexity of Matrix
            Factorization Algorithms
         Giovanni Manzini, U. di Pisa, Italy; Mauro
         Leoncini, U. di Torino, Italy; Luciano Margara,
            U. di Bologna, Italy

12:10 Lunch

                                 Session 3

1:30   Can a Shared-Memory Model Serve as a
             Bridging Model for Parallel Computation?
          Phillip B. Gibbons, Yossi Matias, Bell Labs;
          Vijaya Ramachandran, U. of Texas, Austin

1:55   Efficient Computations on Fault-Prone BSP
         Spyros Kontogiannis, Patras U., Greece;
         Grammati Pantziou, Computer Tech. Inst.,
            Patras, Greece; Paul Spirakis, Patras U., Greece

2:20   Modeling Parallel Bandwidth: Local vs. Global
         Micah Adler, Heinz Nixdorf Inst., Paderborn,
; Phillip B. Gibbons, Yossi Matias, Bell
; Vijaya Ramachandran, U. of Texas, Austin

2:45   Efficient External Memory Algorithms by
            Simulating Coarse-Grained Parallel Algorithms
         Frank Dehne, Carleton U., Canada; Wolfgang
         Dittrich, U. of Paderborn, Germany; David
         Hutchinson, Carleton U., Canada

3:10   Break
                                 Session 4
3:40   Automatic Network Mapping for LANai Virtual
         Alan Mainwaring, Brent Chun, Daniel
         Wilkerson, Saul Schleimer, UC Berkeley

4:05   Triplex: A Multiprotocol Routing Algorithm
          Melanie Fulgham, Lawrence Snyder, U. of

4:30   Bounds to the Throughput of an Interconnection
         Ludek Kucera, Charles U., Prague and Ecole
            Normale Sup., Lyon

4:55   Deadlock-Free Deterministic Wormhole Routing
             with Cyclic Dependencies
          Loren Schwiebert, Wayne State U.

8:30   Business Meeting

                 TUESDAY, JUNE 24, 1997

                                Session 5

8:45   The Performance of Simple Routing Algorithms
             that Drop Packets
          Ramesh Sitaraman, Suprakash Datta, U. of
             Massachusetts, Amherst

9:10   Simple, efficient routing schemes for all-optical
         Christian Scheideler, U. of Paderborn, Germany;
         Michele Flammini, U. of L'Aquila, Italy

9:35   Approximation Algorithms for Structured
            Communication Problems
         Dominique Barth, U. de Paris Sud, France;
         Pierre Fraigniaud, Ecole Normale Sup. de Lyon,
10:00  Break
                         Invited Presentation
10:30  Scalable Shared-Memory Multiprocessing and
             SGI's Origin Servers
          Dan Lenoski, Silicon Graphics

                                     Session 6
11:15  Fine-Grain Multithreading with the EM-X
          Andrew Sohn, New Jersey Inst. of Tech.; Y.
          Kodama, Electrotechnical Lab. Japan; J. Ku,
             New Jersey Inst. of Tech.; M. Sato, Real World
             Comp. Center, Tsukuba, Japan; H. Sakane, H.
          Yamana, S. Sakai, Y. Yamaguchi,
             Electrotechnical Lab. Japan

11:40  Using Speculative Graduation to Improve the
             Performance of Sequential Consistency
          Parthasarathy Ranganathan, Vijay S. Pai, Sarita
          V. Adve, Rice U.

12:05  Temporal Notions of Synchronization
              and Consistency in Beehive
          Aman Singla, Umakishore Ramachandran,
          Jessica Hodgins, Georgia Inst. of Tech.

12:30  Afternoon Excursion

                              SPAA Revue

4:30   Poster presentations

An Analytical Model for the Performance of
Multicast Banyan Networks, Yuanyuan Yang,
U. of Vermont

A Metric for Parallel Poly-Algorithm Design,
Edward A. Luke, Ioana Banicescu, Jin Li,
Mississippi State U.

Optimal Throughput-Latency Tradeoff for a
Parallelizable Multimedia Pipeline - How
Relaxation Complicates Life,
G. N. Srinivasa Prasanna, Lucent;
A. Gerasoulis, Rutgers U.

Sparse Hypercubes: A Class of Minimal k-Line
Broadcast Graphs, Satoshi Fujita, Hiroshima U.

The UNH DyLoc Project: Dynamic Locality of
Communication, Pilar de la Torre, Matthew D.
Plumlee, U. of New Hampshire

5:00   Queueing Protocols for Minimizing Latency in
             Message-Routing Networks
          F. Thomson Leighton, MIT

5:30   Beyond CC-NUMA, Whither Shared Memory?
         David A. Wood, U. of Wisconsin

6:00   Research announcements

Cooperative Prefetching and Caching in a
Network of Workstations
, Anna Karlin, U. of

Multiprocessor Out-of-Core FFTs with
Distributed Memory and Parallel Disks, Thomas
H. Cormen, Jake Wegmann, David M. Nicol,

Competitive Parallel Disk Prefetching and Buffer
Management, Rakesh Barve, Duke U.; Mahesh
Kallahalla, Peter J. Varman, Rice U.; Jeffrey S.
Vitter, Duke U.

Evaluation of Superscalar Processor
Architectures in MCMR Queues' View, Yongxin
Zhu, Weng Fai Wong, National U. of Singapore

cBSP: Zero-Cost Synchronization in a Modified
BSP Model, Richard D. Alpert, James Philbin,
NEC Research

Conflict-Free Parallel Access to Templates of
Trees and Hypercubes, Sajal K. Das, U. of North
Texas; M. Cristina Pinotti, Consiglio Nazionale
d. Ricerche

7:15   Banquet

               WEDNESDAY, JUNE 25, 1997

                                    Session 7

8:45   Better Trade-offs for Parallel List Ranking
          Jop Sibeyn, Max Planck Inst. fur Informatik,

9:10   Using Tadpoles to Reduce Memory and
            Communication Requirements for Exhaustive,
            Breadth-First Search Using Distributed
         Gene Cooperman, Michael Tselman,
            Northeastern U.

9:35   A Theoretically and Empirically Efficient
            Parallel Delaunay Triangulation Algorithm
         Jonathan Hardwick, CMU

10:00  Break

                                     Session 8

10:30  Pipelining with Futures
          Guy Blelloch, Margaret Reid-Miller, CMU

10:55  From Algorithm Parallelism to Instruction-Level
             Parallelism: An Encode-Decode Chain Using

         Uzi Vishkin, U. of Maryland

11:20  Thread Partition and Schedule Based On Cost
          Xinan Tang, J. Wang, Kevin Theobald, Guang
          R. Gao, McGill U., Canada

11:45  Optimal Weighted Loop Fusion for Parallel
          Nimrod Megiddo, IBM; Vivek Sarkar, MIT and IBM

12:10  Lunch

                                        Session 9

1:30   On the Analysis of Randomized Load Balancing
         Michael Mitzenmacher, Digital Systems Res. Center

1:55   Allocating Weighted Balls in Parallel
         Klaus Schroeder, Petra Berenbrink, Friedhelm
         Meyer auf der Heide, Heinz Nixdorf Inst. and U.
            of Paderborn, Germany

2:20   Accessing Nearby Copies of Replicated Objects in
            a Distributed Environment
         Andrea Richa, CMU; C. Greg Plaxton,
         Rajmohan Rajaraman, U. of Texas, Austin

2:45   A Localized Algorithm for Parallel Association
         Mohammed Zaki, Srinivasan Parthasarathy, Wei
         Li, Rochester U.

'97 Organization

Conference Chair

Charles E. Leiserson, MIT

Program Chair

David E. Culler, UC Berkeley

Program Committee

Amotz Bar-Noy, Tel Aviv U.
Susanne E. Hambrusch, Purdue U.
Anna Karlin, U. of Washington
F. Thomson Leighton, MIT
Bruce Maggs, CMU
Bill McColl, Oxford U.
Burkhard Monien, U. of Paderborn
Greg Papadopoulos, Sun Microsystems
Satish Rao, NEC
Klaus E. Schauser, UC Santa Barbara
J.P. Singh, Princeton U.
Burton Smith, Tera Computer
Robert van de Geijn, U. of Texas
David A. Wood, U. of Wisconsin

Local Arrangements

Takis Metaxas, Wellesley

Revue Chair

Phillip B. Gibbons, Bell Labs

Conference Treasurer

Eric Schwabe, Northwestern

Conference Secretary

Robert Cypher, Sun Microsystems


Reinhard Lueling, U. of Paderborn

Curricular Forum Chair

David Kotz, Dartmouth

Corporate Affiliates

Cambridge University Press
Elsevier Science Publishers
Morgan Kaufmann Publishers
Plenum Publishers