SPAA '99  

Eleventh ACM Symposium on Parallel Algorithms and Architectures


June 27-30, 1999
Saint-Malo, France

SUNDAY, 27 June

5:00-8:00 PM: Opening Reception

MONDAY, 28 June

8:45 AM: Welcome

9:00-10:45 AM: Session 1. Chair: Ramesh Sitaraman

Time-Constrained Scheduling of Weighted Packets on Trees and Meshes
Micah Adler, University of Toronto
Sanjeev Khanna, Bell Laboratories
Rajmohan Rajaraman, Northeastern University
Adi Rosén, University of Toronto

Scheduling Optimization for Resource-Intensive Web Requests on Server Clusters
Huican Zhu, University of California, Santa Barbara
Ben Smith, University of California, Santa Barbara
Tao Yang, University of California, Santa Barbara

Efficient Approximation Algorithms for Scheduling Malleable Tasks
Gregory Mounie, Université de Grenoble
Christophe Rapine, Université de Grenoble
Denis Trystram, Université de Grenoble

Simple Competitive Request Scheduling Strategies
Petra Berenbrink, Paderborn University
Marco Riedel, Paderborn University
Christian Scheideler, Paderborn University

10:40-11:15 AM: Coffee Break

11:15 AM-12:30 PM: Invited Talk. Chair: Lennart Johnsson

Making Sparse Matrix Computations Scalable
Jim Demmel, University of California, Berkeley

12:30-2:00 PM: Lunch

2:00-3:40 PM: Session 2. Chair: Vijaya Ramachandran

Post-Mortem Black-Box Correctness Tests for Basic Parallel Data Structures
Phillip B. Gibbons, Bell Laboratories, Lucent Technologies
John L. Bruno, University of California, Santa Barbara
Steven Phillips, AT&T Labs - Research

Some Compact Layouts of the Butterfly
Yefim Dinitz, Ben-Gurion University
Shimon Even, Technion - Israel Institute of Technology
Roni Kupershtok, Technion - Israel Institute of Technology
Maria Zapolotsky, Technion - Israel Institute of Technology

Sorting and Counting Networks of Small Depth and Arbitrary Width
Costas Busch, Brown University
Maurice Herlihy, Brown University

Communication-Processor Tradeoffs in Limited Resources PRAM
Adnan Agbaria, Technion
Yosi Ben-Asher, Haifa University
Ilan Newman, Haifa University

3:40-4:15 PM: Coffee Break

4:15-5:55 PM: Session 3. Chair: Robert Blumofe

Scheduling Threads for Low Space Requirement and Good Locality
Girija Narlikar, Carnegie Mellon University

A Closer Look At Coscheduling Approaches for a Network of Workstations
Shailabh Nagar, The Pennsylvania State University
Ajit Banerjee, The Pennsylvania State University
Anand Sivasubramaniam, The Pennsylvania State University
Chita R. Das, The Pennsylvania State University

Experience with an Adaptive Globally-Synchronizing Clock Algorithm
Cheng Liao, Princeton University
Margaret Martonosi, Princeton University
Douglas W. Clark, Princeton University

BOS is Boss: A Case for Bulk-Synchronous Object Systems
Mark W. Goudreau, NEC USA
Kevin Lang, NEC Research Institute
Girija Narlikar, Carnegie Mellon University
Satish B. Rao, NEC Research Institute

9:00 PM: Business Meeting

TUESDAY, 29 June

9:00-10:40 AM: Session 4. Chair: Ernst Mayr

A Comparison of Scalable Superscalar Processors
Bradley C. Kuszmaul, Yale University
Dana S. Henry, Yale University
Gabriel H. Loh, Yale University

A System-Level Specification Framework for I/O Architectures
Mark D. Hill, University of Wisconsin, Madison
Anne E. Condon, University of Wisconsin, Madison
Manoj Plakal, University of Wisconsin, Madison
Daniel J. Sorin, University of Wisconsin, Madison

On the Scheduling of Variable Latency Functional Units
Silvia M. Mueller, University of Saarland

Optimal Replacements in Caches with Two Miss Costs
Jaeheon Jeong, University of Southern California
Michel Dubois, University of Southern California

10:40-11:15 AM: Coffee Break

11:15 AM-12:30 PM: Session 5. Chair: Dominique Sotteau

Data Management in Networks: Experimental Evaluation of a Provably Good Strategy
Christof Krick, University of Paderborn
Friedhelm Meyer auf der Heide, University of Paderborn
Harald Räcke, University of Paderborn
Berthold Vöcking, International Computer Science Institute, Berkeley
Matthias Westermann, University of Paderborn

Randomized and Adversarial Load Balancing
Petra Berenbrink, Universität Paderborn
Tom Friedetzky, Technische Universität München
Angelika Steger, Technische Universität München

All-To-All Routing and Coloring in Weighted Trees of Rings
Bruno Beauquier, Université de Nice-Sophia Antipolis
Stéphane Pérennes, Université de Nice-Sophia Antipolis
David Tóth, Technical University of Budapest

12:30-2:00 PM: Lunch

2:00-5:00 PM: SPAA REVUE. Chair: Micah Adler

5:30 PM: Excursion to Saint-Malo

8:00 PM: SPAA Banquet


9:00-10:40 AM: Session 6. Chair: Shanghua Teng

Tradeoffs Between Parallelism and Fill in Nested Dissection
Claudson F. Bornstein, Universidade Federal do Rio de Janeiro
Bruce M. Maggs, Carnegie Mellon University
Gary L. Miller, Carnegie Mellon University

Selecting Tile Shape for Minimal Execution Time
Karin Högstedt, University of California, San Diego
Larry Carter, University of California, San Diego
Jeanne Ferrante, University of California, San Diego

Efficient Parallel Solutions of Linear Algebraic Circuits
Yosi Ben-Asher, Haifa University
Gady Haber, IBM Science and Technology, Haifa

Recursive Array Layouts and Fast Parallel Matrix Multiplication
Siddhartha Chatterjee, University of North Carolina, Chapel Hill
Alvin R. Lebeck, Duke University
Praveen K. Patnala, University of North Carolina, Chapel Hill
Mithuna Thottethodi, Duke University

10:45-11:15 AM: Coffee Break

11:15 AM-12:30 PM: Session 7. Chair: Yossi Matias

A Simple and Efficient Parallel Disk Mergesort
Rakesh D. Barve, Duke University
Jeffrey Scott Vitter, Duke University

Multidimensional, Multiprocessor, Out-of-Core FFTs with Distributed Memory and Parallel Disks
Lauren M. Baptist, Dartmouth College
Thomas H. Cormen, Dartmouth College

Fundamental Control Algorithms in Mobile Networks
Kostas P. Hatzis, Computer Technology Institute and Patras University
George P. Pentaris, Computer Technology Institute and Patras University
Paul G. Spirakis, Computer Technology Institute and Patras University
Vasilis T. Tampakas, Computer Technology Institute and TEI of Patras
Richard B. Tan, Universiteit Utrecht

12:30 PM: Lunch

End of Conference

Back to SPAA home page
Thomas H. Cormen <>
Last modified: Thu May 20 11:14:05 1999