Eleventh ACM Symposium on Parallel Algorithms and Architectures

Program

5:00-8:00 PM: Opening Reception

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

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