SPAA'97

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

Sponsored by
ACM SIGACT and ACM SIGARCH
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
http://www.cs.jhu.edu/Conferences/SPAA/
http://www.uni-paderborn/cs/SPAA/
http://www.cs.dartmouth.edu/FPCC/



                      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  
               Programs
            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
             Partitioner
         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
             Machines
         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
            Restrictions
         Micah Adler, Heinz Nixdorf Inst., Paderborn,
            Germany
; Phillip B. Gibbons, Yossi Matias, Bell
            Labs
; 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
            Networks
         Alan Mainwaring, Brent Chun, Daniel
         Wilkerson, Saul Schleimer, UC Berkeley


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


4:30   Bounds to the Throughput of an Interconnection
            Network
         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
             networks
         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,
            France
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
              Multiprocessor
          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
Washington

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

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,
            Germany


9:10   Using Tadpoles to Reduce Memory and
            Communication Requirements for Exhaustive,
            Breadth-First Search Using Distributed
            Computers
         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
            Prefix-Sum

         Uzi Vishkin, U. of Maryland


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

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

12:10  Lunch

                                        Session 9

1:30   On the Analysis of Randomized Load Balancing
            Schemes
         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
            Mining
         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

Webmaster

Reinhard Lueling, U. of Paderborn

Curricular Forum Chair

David Kotz, Dartmouth

Corporate Affiliates

Cambridge University Press
Elsevier Science Publishers
Morgan Kaufmann Publishers
Plenum Publishers
SIAM