SPAA'96 Preliminary Schedule



******************************************************
Monday, June 24
9-10:15 AM 

Towards Efficiency and Portability: Programming with the BSP Model
Mark Goudreau, Kevin Lang, Satish Rao, Torsten Suel, Thanasis Tsantilas

A Quantitative Comparison of Parallel Computation Models
Harry A.G. Wijshoff, B.H.H. Juurlink

BSP vs LogP
G. Bilardi, K.T. Herley, A. Pietracaprina, G. Pucci and P. Spirakis

******************************************************
Monday, June 24
10:45-12:25

A Steady State Analysis of Diffracting Trees
Nir Shavit, Eli Upfal, Asaph Zemach

Asynchronous Shared Memory Search Structures
Micah Adler

Improved Methods for Hiding Latency in Networks of Workstations
Matthew Andrews, Tom Leighton, P. Takis Metaxas, Lisa Zhang

Optimal Latency-Throughput Tradeoffs for Data Parallel Pipelines
Jaspal Subhlok, Gary Vondran

******************************************************
Monday, June 24
2:30-3:45

First and second order diffusive algorithms for rapid, coarse, distributed load balancing
Bhaskar Ghosh, S. Muthukrishnan, Martin H. Schultz

On Multiprocessor System Scheduling
Xiaotie Deng, Patrick Dymond

An Analysis of Gang Scheduling for Multiprogrammed Parallel Computing Environments
Mark Squillante, Fang Wang, Marios Papaefthymiou

******************************************************
Monday, June 24
4:15-5:30

Flexible Usage of Parity Storage Space in Disk Arrays
Eric J. Schwabe, Ian M. Sutherland

Simple Randomized Mergesort on Parallel Disks
Rakesh D. Barve, Edward F. Grove, Jeffrey Scott Vitter

Anticipatory Instruction Scheduling
Vivek Sarkar, Barbars Simons


******************************************************
Tuesday, June 25
9-10:15 AM 

Invited Talk

******************************************************
Tuesday, June 25
10:45-12:25 AM 

On the Benefit of Supporting Virtual Channels in Wormhole Routers
Richard J. Cole, Bruce M. Maggs, Ramesh K. Sitaraman

Universal Continuous Routing Strategies
Berthold Vocking, Christian Scheideler

On the Communication Throughput of Buffered Multistage Interconnection Networks
Ralf Rehrmann, Burkhard Monien, Reinhard Luling, Ralf Diekmann

Constant Time per Edge is Optimal on Rooted Tree Networks
Michael Mitzenmacher

******************************************************
Tuesday, June 25
2:30-3:45 AM 

A Tight Layout of the Butterfly Network
Aythan Avior, Tiziana Calamoneri, Shimon Even, Ami Litman, Arnold L. Rosenberg

The Slowdown of Efficient Simulations of Multibutterflies on Butterflies and Butterfly-Derived Networks
Kevin J. Rappoport

Local Memory Requirement of Universal Routing Schemes
P. Fraigniaud, C. Gavoille

******************************************************
Tuesday, June 25
4:15-5:45 AM 

(Research Summaries)

A Dynamic Load Balancing Framework for Unstructured Adaptive Computations on Distributed-Memory Multiprocessors
Andrew Sohn, Rupak Biswas, Horst D.Simon

A Library of basic PRAM algorithms and its implementation in FORK
Christoph W. Kebler, Jesper Larsson Traff

uDatabase: Parallelism in a Memory-Mapped Environment
Peter Buhr, Anil Goel, Naomi Nishimura, Prabhakar Ragde

 From AAPC Algorithms to High Performance Permutation Routing and Sorting
Thomas M. Stricker, Jonathan C. Hardwick

Parallel Neighborhood Modeling: Research Summary
D. Hutchinson, L. K\"{u}ttner, M. Lanthier, A. Maheshwari, D. Nussbaum, D. Roytenberg, J. R. Sack

Components of Congestion Control
Ludmila Cherkasova, Al Davis, Robin Hodgson, Vadim Kotov, Ian Robinson, Tomas Rokicki

******************************************************
Wednesday, June 26
9:00-10:15

Parallel Algorithms for Personalized Communication and Sorting with an Experimental Study
David R. Helman, David A. Bader, Joseph J\`{a}J\`{a}

Deterministic and Randomized BSP Algorithms
Alexandros V. Gerbessiotis, Constantinos J. Siniolakis

Fully Dynamic Search Trees for an extension of the BSP model
Wolfgang Dittrich, Armin B\"{a}umker


******************************************************
Wednesday, June 26
10:45-12:25

Sampling with partial solution: on O(log n)-time optimal-work randomized parallel MST algorithm
Richard Cole, Philip N. Klein, Robert E. Tarjan

Parallel multidimensional search using approximation algorithms: with applications to linear-programming and related problems
Sandeep Sen

Parallel Balanced Allocations
Volker Stemann

Efficient Execution of Non-deterministic Parallel Programs on Asynchronous Systems
Yonatan Aumann, Michael A. Bender, Y.Lisa Zhang

******************************************************
Wednesday, June 26
2:30-3:45

Scope Consistency: a bridge between Release Consistency and Entry Consistency
Liviu Iftode, Jaswinder Pal Singh, Kai Li

Verification of FLASH Cache Coherence Protocol by Aggregation of Distributed Actions
Seungjoon Park, David L. Dill

An Analysis of Dag-Consistent Distributed Shared-Memory Algorithms
Robert D. Blumofe, Matteo Frigo, Christopher F. Joerg, Charles E. Leiserson, Keith H. Randall

******************************************************
Wednesday, June 26
4:15-5:30
On Trading Task Reallocation for Thread Management in Multiprocessors
Lixin Gao, Arnold L.Rosenberg, Ramesh K. Sitaraman

Load Sharing via Weighted Factoring
Susan Flynn Hummel, Jeanette Schmidt, R.N. Uma, Joel Wein

Job scheduling for practical parallel database and scientific applications
Soumen Chakrabarti, S. Muthukrishnan