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.