IPPS '97 Advance Program



Workshops Index






Workshops 1-8
Tutorials 1, 2, & 3


Technical Sessions 1-9


Technical Sessions 10-21 Industrial Track




Workshops 9-14



Our goal over the years has been to build a truly international event and to conduct our program in pleasant surroundings which promote congenial discussion. The week of April 1-5, 1997 will help us to meet our objectives.

In addition, several features of IPPS '97 will make this our 11th year particularly memorable.

* Workshops return in full force with several which are by now leading events in their field of inquiry.

* Our schedule will be slightly modified. Keynote speeches and the panel discussion will be presented by PARCON on a single day following two days of technical sessions and the industrial track of invited presentations. As usual, workshops will start on the first day, and all of the tutorials will be presented on the same day. The remaining workshops will be held on the last day which is Saturday.

* This year our host is the University of Geneva (and with students away for the week, we will have the place to ourselves!). Lunch will be served daily on campus and there will be morning and afternoon refreshment breaks. Note that the specially priced hotel accommodations reserved for IPPS '97 participants are located only a 10-15 minute walk to the campus.

* As the announcement here explains, at IPPS '97 we will begin our activities for an expanded 1998 event. Details are given below in the merger announcement.

This Advance Program describes the topics which will be discussed and the papers which will be presented. We invite you to join us and participate in our program.

We also take this opportunity to express our appreciation for the international effort and support of the organizations and individuals listed in this program.

George Westrom
Steering Chair

Viktor Prasanna & Jose Rolim
General Co-Chairs

Allan Gottlieb
Program Chair

A special note from the organizing committee:

If you will be traveling from outside Europe, we suggest you check guide books and travel agents for information to help make your trip problem free. And for travel arrangements and accommodations, be sure to make reservations at the earliest possible date.


Also on our agenda in 1997 is the announcement of the merger of IPPS and the Symposium on Parallel and Distributed Processing (SPDP). We will begin holding a combined event in 1998. The first merged symposium - planned for April 1998 in Florida - will be co-chaired by Viktor Prasanna from IPPS and Behrooz Shirazi from SPDP. Sartaj Sahni - chair of the IEEE-CS Technical Committee on Parallel Processing and a member of the steering committees for both events - will serve as program chair for IPPS/SPDP 1998. Under direction of current IPPS steering chair George Westrom and along with the 1998 general co-chairs and program chair, the IPPS/SPDP 1998 steering group will include K. Mani Chandy, Ali R. Hurson, F. Tom Leighton, H.J. Siegel, and Hal Sudborough. The united symposium will offer better value to attendees and build a forum as a primary annual international event in parallel processing.


Viktor K. Prasanna, University of Southern California
Jose D.P. Rolim, University of Geneva

Allan Gottlieb, New York University
& NEC Research Institute

Algorithms: Sartaj Sahni, University of Florida
Applications: Malvin Kalos, Cornell University
Architecture: Kai Li, Princeton University
Software: Hans Zima, University of Vienna

John K. Antonio, Texas Tech University (Americas)
Helmar Burkhart, University of Basel (Europe/Asia)

Tao Yang, University of California, Santa Barbara

Bill Pitts, Toshiba America Information Systems, Inc.

Susamma Barua, California State University, Fullerton

Sally Jelinek, Electronic Design Associates, Inc.

C.P. Ravikumar, Indian Institute of Technology, New Delhi

Eastern Europe
Ondrej Sykora, Slovak Academy of Sciences

Middle East
Assir Jihad, Societe Saudi Oger SA

North America
D.N. Jayasimha, Intel Corp., Santa Clara

Pacific Rim
Cho-Li Wang, The University of Hong Kong

South America
Nelson Maculan, Universidade Federal do Rio de Janeiro, Brazil

Western Europe/Africa
Stephane Ubeda, LIP ENS-Lyon, France


Otto Anshus, University of Tromso
Mikhail Atallah, Purdue University
Prith Banerjee, Northwestern University
Gianfranco Bilardi, Universita di Padova and University of Illinois at Chicago
Maurizio A. Bonuccelli, University of Pisa
Helmar Burkhart, University of Basel, Switzerland
Larry Carter, UC San Diego and San Diego Supercomputer Center
Barbara Chapman, University of Vienna
Andrew Chien, University of Illinois at Urbana-Champaign
Bogdan S. Chlebus, Uniwersytet Warszawski, Warsaw
Alok Choudhary, Northwestern University
Sajal Das, University of North Texas
Josep Diaz, Universitat Politecnica de Catalunya
Michel Dubois, University of Southern California
Edward Felten, Princeton University
Afonso Ferreira, CNRS, LIP - ENS Lyon
Ian Foster, Argonne National Laboratory
Oscar Ibarra, UC Santa Barbara
Joseph Ja'Ja', University of Maryland
D.N. Jayasimha, Intel Corporation
Carl Kesselman, California Institute of Technology
Guojie Li, National Research Center for Intelligent Computing Systems
Yossi Matias, Bell Laboratories
Burkhard Monien, University of Paderborn
David Nassimi, New Jersey Institute of Technology
Kunle Olukotun, Stanford University
James Philbin, NEC Research Institute
James Plank, University of Tennessee
Sanguthevar Rajasekeran, University of Florida
Sanjay Ranka, University of Florida
John Rice, Purdue University
Arnold Rosenberg, University of Massachusetts
Ahmed Sameh, University of Minnesota
Assaf Schuster, Technion
Paul Spirakis, CTI, Crete
Chandramohan A. Thekkath, Systems Research Center, Digital Equipment Corp.
Mateo Valero, Universitat Politecnica de Catalunya
Uzi Vishkin, University of Maryland and Tel Aviv University
Imrich Vrto, Institute for Informatics, Bratislava
Pearl Wang, George Mason University
Harry Wijshoff, Leiden University
Tao Yang, University of California at Santa Barbara
Emilio Zapata, University of Malaga (Spain)

George Westrom, Odetics, Inc. & FSEA

K. Mani Chandy, California Institute of Technology
Joseph Ja'Ja', University of Maryland
F. Tom Leighton, MIT
Viktor K. Prasanna, University of Southern California
Sartaj Sahni, University of Florida
H.J. Siegel, Purdue University

Michel Cosnard, Ecole Normale Superieure de Lyon (France)
Michael J. Flynn, Stanford University (USA)
Friedhelm Meyer auf der Heide, University of Paderborn (Germany)
Louis O. Hertzberger, University of Amsterdam (The Netherlands)
Richard Karp, University of Washington (USA)
Jan van Leeuwen, University of Utrecht (The Netherlands)
Kurt Mehlhorn, Max Planck Institute (Germany)
Gary Miller, Carnegie Mellon University (USA)
Juerg Nievergelt, ETH Zurich (Switzerland)
Charles L. Seitz, Myricom, Inc. (USA)
Leslie Valiant, Harvard University (USA)
Paolo Zanella, E.B.I., Cambridge (UK)


The 11th International Parallel Processing Symposium is sponsored by the IEEE Computer Society Technical Committee on Parallel Processing (TCPP) and is held in cooperation with the ACM Special Interest Group on Computer Architecture (SIGARCH) and also the University of Geneva, the European Association for Theoretical Computer Science (EATCS), the Swiss Special Interest Group on Parallelism (SIPAR), and the SPEEDUP Society. Companies and organizations listed on the inside cover are providing commercial support.

IPPS '97 Program


All events will be conducted at the University of Geneva which is walking distance from the two hotels reserved for IPPS attendees. See the last two pages of the program and the accompanying map to learn more about the area. As usual, book early to assure your choice of accommodations. See contact information for Swissair and the Noga Hilton Geneve and Hotel Ambassador on the middle tear-out sheet.


There will be 113 contributed technical papers to be presented in 21 technical sessions. Topics cover all areas of parallel processing and present previously unpublished research in the design, development, use and analysis of parallel processing systems.


On Friday, PARCON will present a one-day program of invited speakers and a panel discussion. Known as the Symposium on New Directions in Parallel and Concurrent Computing, PARCON will co-locate with IPPS in 1997 to provide a forum for leading scientists to speak about the issues and challenges at the frontier of parallel processing. For details, see next page.


The Industrial Track and Commercial Exhibits portion of the symposium is designed to give manufacturers of commercial products the opportunity to both explain and demonstrate their wares. The Industrial Track consists of original technical papers authored and presented by representatives from the participating organizations, and the papers will be printed in the symposium proceedings. The Commercial Exhibits portion of the symposium complements the presentations of the Industrial Track by providing vendors with the opportunity to display and/or demonstrate their products in an informal "walk-up and talk" setting.


To be held on the first and last days of the symposium - Tuesday and Saturday. Open to all registrants, workshops are an opportunity to explore special topics. See descriptions in pages which follow for each workshop.

1. Heterogeneous Computing Workshop

2. Joint Workshop on Parallel and Distributed Real-Time Systems

3. Reconfigurable Architectures Workshop

4. Optics and Computer Science

5. Formal Methods for Parallel Programming: Theory and Applications

6. High-Level Programming Models and Supportive Environments

7. Parallel Processing and Multimedia

8. Randomized Parallel Computing

9. Runtime Systems for Parallel Programming

10. Job Scheduling Strategies for Parallel Processing

11. Embedded HPC Systems and Applications

12. Fault-Tolerant Parallel and Distributed Systems

13. Solving Combinatorial Optimization Problems in Parallel

14. Nomadic Computing


There will be three tutorials, all to be held on Tuesday. The first one will be held in the morning and the other two will be in the afternoon.

1. High Performance Computing for Scientists and Engineers: An Introduction

2. Advanced Introduction to MPI-1 and MPI-2

3. Stuctured Concurrent Programming with Java, Windows NT, & Pthreads


Refreshments and lunch will be served all five days of the symposium. On Friday following PARCON, there will be a dinner cruise on Lake Geneva. All other evenings will leave participants free to explore Geneva.


See the tear-out form in the middle of the Advance Program. Note that you need to register by March 4, 1997 to obtain the "Early Bird" discount. Also, this year you may register electronically from the IPPS home page (www.ippsxx.org). Registrations after March 17, 1997 will be accepted on-site only.


The proceedings will be published by the IEEE Computer Society Press in both book and CD-ROM form and will be available to all registrants including students at the symposium. Extra copies and proceedings from previous symposia (including the CD-ROM for 1996) may be obtained by contacting the IEEE Computer Society.


Proceedings from the workshops will vary in format and availability and cannot be guaranteed to each IPPS registrant. Most workshop organizers will put proceedings on the Web as well as having hard copies available at the symposium. To help fairly distribute a limited supply at the symposium, a ticket for proceedings from two workshops (one for Tuesday and one for Saturday) will be issued to each registrant, and printed copies will be distributed at the beginning of each workshop with preference given to those participating in the workshop. Requests for additional printed copies should be made to the individual workshop chair(s).


Additional information regarding IPPS '97 may be obtained on the Web (using URL http://www.ippsxx.org) or contact one of the IPPS '97 General Co-Chairs: Viktor K. Prasanna (ipps97@ganges.usc.edu), Jose D.P. Rolim (ipps97@cui.unige.ch)

Symposium on New Directions in Parallel and Concurrent Computing
Friday April 4, 1997
9 AM - 4 PM


Parallelism and Concurrency in the Emerging Virtual Enterprise
Frances E. Allen, T.J. Watson
Research Center, IBM

DNA Based Parallel Computers
Richard J. Lipton, Department of
Computer Science, Princeton University

Irregular Applications on the SB-PRAM
Wolfgang Paul, Department of Computer
Science, University of Saarlandes


Building Parallel Systems: Experiences and Lessons Learned
Panel discussion led by Anant Agarwal,
Massachusetts Institute of Technology

Dennis Gannon (Indiana University)
Allan Gottlieb (NYU and NEC)
Kai Li (Princeton University)
David Wood (University of Wisconsin)

PROGRAM CHAIR: Krishna V. Palem
Courant Institute of Mathematical Sciences
Courant Institute of Mathematical Sciences

ADVISORY PANEL: Frances E. Allen, Arvind, K. Mani Chandy,
Richard M. Karp, F. Thomson Leighton, Michael O. Rabin (Chair)


1 - 8

1.HCW *

See below for full name of workshops. Descriptions of these 8 workshops start on page 8 and include contact information.

Workshop schedules will vary. Most will begin at 8AM and run to 6PM with a morning and afternoon break and lunch served from 12 to 2PM.

Schedules for each workshop will be available at registration check-in.

* Schedule listed in Advance Program (see pages 8 & 9).

** Continues on Wednesday & Thursday.

Tutorial 1
8:30 AM - 12:30 PM

Tutorial 2
1:30 PM - 5:30 PM

Tutorial 3
1:30 PM - 5:30 PM

9:00 AM - 9:15 AM

9:15 AM - 10:00 AM

10:00 AM - 12 NOON

Networks I


12 NOON - 1:30 PM

1:30 PM - 3:30 PM


Performance Evaluation
3:30 PM - 4:00 PM

4:00 PM - 6:00 PM

Synchronization & Threads

Algorithms I


8:00 AM - 10:00 AM

I/O and Message Passing

Algorithms II


10:00 AM - 10:30 AM

10:30 AM - 12:30 PM


Shared Memory

Algorithms III

Compilers I

12:30 PM - 2:00 PM

2:00 PM - 4:00 PM

Networks II

Algorithms IV

Compilers II

4:00 PM - 4:30 PM

4:30 PM - 6:30 PM

Architecture Theory

Data Structures

Networks III


9:00 AM - 10:00 AM
Frances E. Allen

10:00 AM - 10:30 AM

10:30 AM - 11:30 AM
Richard J. Lipton

11:30 AM - 12 NOON

12 NOON - 1:00 PM
Wolfgang Paul

1:00 PM - 2:30 PM

2:30 PM - 4:00 PM
Building Parallel Systems: Experiences and Lessons Learned

Dinner Cruise on Lake Geneva
Boat sails at 6PM sharp - Swiss time!

Registration will be open in the evenings Monday, Tuesday and Wednesday and will open early on Tuesday and Wednesday.

9 - 14


See below for full name of workshops. Descriptions of these 6 workshops start on page 26 and include contact information.

Workshop schedules will vary. Most will begin at 8AM and run to 6PM with a morning and afternoon break and lunch served from 12 to 2PM.

Schedules for each workshop will be available at registration check-in.

HCW Heterogeneous Computing Workshop
WPDRTS Workshop on Parallel and Distributed Real-Time Systems
RAW Reconfigurable Architectures Workshop
WOCS Workshop on Optics and Computer Science
FMPPTA Formal Methods for Parallel Programming: Theory and Applications
HIPS High-Level Programming Models and Supportive Environments
WPPM Workshop on Parallel Processing and Multimedia
WRPC Workshop on Randomized Parallel Computing
RTSPP Runtime Systems for Parallel Programming
JSSPP Job Scheduling Strategies for Parallel Processing
EHPC Embedded HPC Systems and Applications
FTPDS Fault-Tolerant Parallel and Distributed Systems
SCOOP Solving Combinatorial Optimization Problems in Parallel
WNC Workshop on Nomadic Computing


Workshop 1: All Day Tuesday
HCW '97

Co-sponsored by

IEEE Computer Society & Office of Naval Research

Proceedings published by
IEEE Computer Society Press


HCW '97 Contents

In addition to the fourteen contributed, refereed papers, HCW '97 will feature four invited case studies. These case studies are derived from industrial and academic projects that have succeeded in harnessing the power of heterogeneous computing for various applications ranging from aircraft design to simulated forces.

HCW '97 Focus

Heterogeneous computing systems range from diverse elements within a single computer to coordinated, geographically distributed machines with different architectures. A heterogeneous computing system provides a variety of capabilities that can be orchestrated to execute multiple tasks with varied computational requirements. Applications in these environments achieve performance by exploiting the affinity of different tasks to different computational platforms or paradigms, while considering the overhead of inter-task communication and the coordination of distinct data sources and/or administrative domains.

Organizing Committee:

General Chair: H.J. Siegel, Purdue University
Vice-General Chair: Dan Watson, Utah State University

Program Committee:
Ishfaq Ahmad, Hong Kong University of Science & Tech.
Giovanni Aloisio, Universita degli Studi di Lecce
Cosimo Anglano, Universita di Torino
John K. Antonio, Texas Tech University, Case Studies Co-Chair
Francine Berman, University of California, San Diego
Steve Chapin, Kent State University
Partha Dasgupta, Arizona State University
Hank Dietz, Purdue University
Mary Eshaghian, New Jersey Institute of Technology
Andrew Grimshaw, University of Virginia
Debra Hensgen, Naval Postgraduate School (CHAIR)
Nayeem Islam, IBM T.J. Watson Research Center
Gary Johnson, George Mason University
Taylor Kidd, Naval Postgraduate School (Case Studies Co-Chair)
Domenico Laforenza, CNUCE - Institute of the Italian NRC
David Lilja, University of Minnesota
Miron Livny, University of Wisconsin - Madison
Bob Lucas, ARPA
Richard C. Metzger, Rome Lab
Lantz Moore, University of Cincinnati
Jim Patterson, Boeing Info. and Support Services
Ranga S. Ramanujan, Architecture Technology Corporation
Rick Stevens, Argonne National Labs
Vaidy Sunderam, Emory University
Maria Uspenski, EcoSoftware, Inc.
Dan Watson, Utah State University
Chip Weems, University of Massachusetts, Amherst
Elizabeth Williams, Center for Computing Sciences
Albert Y. Zomaya, University of Western Australia

Steering Committee:

Francine Berman, UCSD
Jack Dongarra, University of Tennessee
Richard F. Freund, NRaD (CHAIR)
Debra Hensgen, Naval Postgraduate School
Paul Messina, Caltech
Jerry Potter, Kent State University
Viktor Prasanna, USC
H.J. Siegel, Purdue University
Vaidy Sunderam, Emory University

Opening Remarks
8:30 - 8:40

Session 1
8:40 - 10:20
System Support for Heterogeneous Computing
Chair: Richard F. Freund
NRaD,San Diego, CA, USA

Dynamic Load Balancing of Distributed SPMD Computations with Explicit Message-Passing
M. Cermele, M. Colajanni, G. Necci, Universita di Roma, Rome, Italy

The MOL Project: An Open, Extensible Metacomputer
R. Baraglia, D. Laforenza, CNUCE - Institute of the Italian National Research Council, Italy T. Decker, J. Gehring, F. Ramme, A. Reinefeld, T. Romke, J. Simon, PC2- Paderborn Center for Parallel Computing, Germany

A Programming Environment for Heterogeneous Distributed Memory Machines
Dmitry Arapov, Alexey Kalinov, Alexey Lastovetsky, Ilya Ledovskih, Russian Academy of Sciences, Moscow, Russia Ted Lewis, Naval Postgraduate School, Monterey, CA, USA

UbiWorld: An Environment Integrating Virtual Reality, Supercomputing, and Design
Terrence Disz, Michael E. Papka, Rick Stevens, Argonne National Laboratory, Argonne, IL, USA

Modular Heterogeneous Multicomputing
Thomas H. Einstein, Mercury Computer Systems, Chelmsford, MA, USA

Session 2: 10:40 - 12:00
Mapping and Scheduling Systems
Chair: John Antonio
Texas Tech University
Lubbock, TX, USA

A Scheduling Expert Advisor for Heterogeneous Environments
Mihai G. Sirbu, Dan C. Marinescu, Purdue University, West Lafayette, IN, USA

Exploiting Multiple Heterogeneous Networks to Reduce Communication Costs in Parallel Programs
JunSeong Kim, David J. Lilja, University of Minnesota, Minneapolis, MN, USA

On-Line Use of Off-Line Derived Mappings for Iterative Automatic Target Recognition Tasks and a Particular Class of Hardware Platforms
John R. Budenske, Ranga S. Ramanujan, Architecture Technology Corporation, Minneapolis, MN, USA H.J. Siegel, Purdue University, West Lafayette, IN, USA

Distributed Interactive Simulation for Synthetic Forces
Paul Messina, Sharon Brunett, Tom Gottschalk, Caltech University, Pasadena, CA, USA David Curkendall, Herb Siegel, Jet Propulsion Laboratory, Los Angeles, CA, USA

12:00 - 1:20

Session 3: 1:20 - 2:40
Mapping and Scheduling Algorithms
Chair: Ranga S. Ramanujan
Architecture Technology Corporation
Minneapolis, MN, USA

A Stochastic Model of a Dedicated Heterogeneous Computing System for Establishing a Greedy Approach to Developing Data Relocation Heuristics
Min Tan and H.J. Siegel, Purdue University, West Lafayette, IN, USA

Optimal Task Assignment in Heterogeneous Computing Systems
Muhammad Kafil, Ishfaq Ahmad, Hong Kong University of Science and Technology, Clear Water Bay, Hong Kong

Mapping Heterogeneous Task Graphs onto Heterogeneous System Graphs
Song Chen, Mary M. Eshaghian, Ying-Chieh Wu, New Jersey Institute of Technology, Newark, NJ, USA

Practical Issues in Heterogeneous Computing for Military Applications
Glenn O. Ladd, Jr., Hughes Aircraft Company, El Segundo, CA, USA

Session 4: 3:00 - 4:40
Performance Evaluation and Reliability and Security
Chair: Domenico Laforenza
CNUCE - Institute of the Italian National Research Council, Italy

Estimating the Execution Time Distribution for a Task Graph in a Heterogeneous Computing System
Yan Alexander Li, Purdue University, West Lafayette, IN, USA John K. Antonio, Texas Tech University, Lubbock, TX, USA

Stochastic Petri Nets Applied to the Performance Evaluation of Static Task Allocations in Heterogeneous Computing Environments
Albert R. McSpadden, Noe Lopez-Benitez, Texas Tech University, Lubbock, TX, USA

Supporting Fault-Tolerance in Heterogeneous Distributed Applications
Piyush Maheshwari, Jinsong Ouyang, The University of New South Wales, Sydney, NSW, Australia

The Hopping Ruse
Marina Chen, James Cowie, Cooperating Systems Corporation, Deering, NH, USA

A Performance and Portability Study of Parallel Applications
Viorel Morariu, Matt Cunningham, Mark Letterman, Concurrent Technologies Corporation, Johnstown, PA, USA

Open Discussion: 4:40 - 5:10
Topic: How Do We Know How Well We Are Doing?
Chair: Andrew Grimshaw
University of Virginia

An open discussion of how we can best evaluate and compare heterogeneous computing techniques and tools, covering topics such as benchmark applications, benchmark systems, performance metrics, and quality of service issues. The community needs to establish guidelines for analyzing the goodness of our own work - what should these guidelines be?

Workshop 2:
All Day Tuesday, Wednesday, & Thursday

Fifth International Workshop on Parallel and Distributed Real-Time Systems & Third Workshop on Object-Oriented Real-Time Systems

General Chairs:
Dieter K. Hammer, Eindhoven University of Technology, The Netherlands
Lonnie R. Welch, The University of Texas at Arlington, USA

The workshop will feature manuscripts that demonstrate original unpublished research pertaining to real-time systems that have parallel and/or distributed architectures. Of interest are experimental and commercial systems, their scientific and commercial applications, and theoretical foundations. Topics of interest (as they relate to parallel and distributed real-time systems) include:

- Architecture
- Benchmarking
- Command and control systems
- Communications and networking
- Databases (real-time)
- Embedded systems
- Fault tolerance
- Formal methods
- Instrumentation
- Languages (real-time)
- Multimedia
- New paradigms
- Object orientation (real-time)
- Signal and image processing
- Reengineering
- Resource allocation and scheduling
- Software architectures
- Systems engineering
- Tools and environments
- Validation and simulation
- Visualization

This year's WPDRTS program will also include a problem session focused on a distributed real-time problem that was distributed with the call for papers.

Program Chairs:

Guenter Hommel
(Chair for Europe and Africa)
Computer Science Department
Berlin University of Technology
Franklinstr. 28/29
D-10587 Berlin,Germany
Vox: +49(303)147-3110
Fax: +49(303)142-1116

Tadashi Ae
(Chair for Asia and Oceania)
Electrical Engineering
Faculty of Engineering
Hiroshima University
1-4-1 Kagamiyama
Higashi-Hiroshima, 739 Japan

Norman R. Howes
(Chair for the Americas)
Institute for Defense Analyses
1801 N. Beauregard Street
Alexandria, VA 22311, USA
Vox: +1(703)845-6660
Fax: +1(703)845-6788

Advisory Committee:

Harry Crisp, NSWCDD, USA
Li Guan, Australia
Robert D. Harrison, NSWCDD, USA
Yoshiaki Kakuda, Osaka University, Japan
Wook Hyun Kwon, Seoul National University, Korea
Harold Lawson, Lawson AB, Sweden
Al Mok, University of Texas at Austin, USA
Jose L. Munoz, ARPA, USA
Viktor K. Prasanna, University of Southern California, USA
Heonshik Shin, Seoul National University, Korea
Kang G. Shin, University of Michigan, USA
Behrooz Shirazi, University of Texas at Arlington, USA
John A. Stankovic, University of Massachusetts, USA
Mario Tokoro, Keio University, Japan
Hideyuki Tokuda, Japan
Stephanie White, Northrop/Grumman, USA

Program Committee:
Bruno Achauer, University of Linz, Austria
Gul Agha, University of Illinois, USA
Mehmet Aksit, Twente University of Technology, The Netherlands
Jorge Amador-Monteverdi, Euro. Space Tech. Eng. Center, The Netherlands
David Andrews, University of Arkansas, USA
Mary A. Austin, United Technologies, USA
Maarten Boasson, Hollands Signaalapparaten B.V., The Netherlands
Flaviu Cristian, University of California, USA
John Drummond, NRaD, USA
Klaus Ecker, University of Clausthal, Germany
Richard Games, MITRE, USA
D.F. Garcia Nocetti, University Nacional Autonoma, Mexico
Martin Gergeleit, GMD, Germany
Andy Goforth, NASA Ames Research Center, USA
Jan Gustafsson, University of Malardalen, Sweden
Wolfgang Halang, University of Hagen, Germany
Constance Heitmeyer, Naval Research Laboratory, USA
Farnam Jahanian, University of Michigan, USA
Mathai Joseph, University of Warwick, UK
Joerg Kaiser, University of Ulm, Germany
Yoshiaki Kakuda, Osaka University, Japan
Christian Kelling (Publicity Chair), Berlin University of Tech., Germany
Gerard Le Lann, INRIA, France
Bruce Lewis, Army MICOM, USA

Miroslaw Malek, Humboldt University, Berlin, Germany David Marlow, NSWCDD, USA
Richard Metzger, Rome Laboratory, USA
Tatsuo Nakajima, JAIST, Japan
Hidenori Nakazato, Oki Electric, Japan
Edgar Nett, GMD, Germany
Binoy Ravindran (Publications Chair), University of Texas at Arlington, USA
Onno van Roosmalen, Eindhoven University of Technology, The Netherlands
Diane Rover, Michigan State University, USA
Helmut Rzehak, University of the Federal Armed Forces, Germany
Antonio L. Samuel(Publicity Chair), NSWCDD, USA
Bo Sanden, Colorado Technical University, USA
Karsten Schwan, Georgia Institute of Technology, USA
Bran Selic, ObjecTime, Inc., USA
Sang Son, University of Virginia, USA
Seiichi Takegaki, Mitsubishi Electric, Japan
Kenji Toda, ETL, Japan
C.M. Woodside, Carleton University, Canada
Tomohiro Yoneda, TIT, Japan

WPDRTS is held in cooperation with the IEEE Technical Committees on Parallel Processing, Real-Time, and Engineering of Computer-Based Systems and is sponsored by the Naval Surface Warfare Center Dahlgren Division (NSWCDD), U.S. Army MICOM, and Hollands Signaalapparaten B.V.

Workshop 3: All Day Tuesday


Workshop Co-Chairs:
Reiner W. Hartenstein, Universitaet Kaiserslautern (Germany)
Viktor K. Prasanna, University of Southern California (USA)

Program Committee:

Peter Athanas, Virginia Tech
Klaus Buchenrieder, Siemens Research
Steven Casselman, Virtual Computer Corp.
Bernard Courtois, University of Grenoble
AndrŽ DeHon, University of California, Berkeley
Hossam ElGindy, University of Newcastle
Rolf Ernst, University of Braunschweig
Manfred Glesner, TH Darmstadt
John Gray, Xilinx Corp.
Reiner Hartenstein, Universitaet Kaiserslautern
Brad Hutchings, Brigham Young University
Rong Lin, State University of New York, Geneseo
Viktor Prasanna, University of Southern California
Michal Servil, Techn. University of Prague
John Villasenor, University of California, Los Angeles

The recent decade has witnessed enormous technological advances, a deeper appreciation of the power of the use of reconfigurable technology platforms, and a better understanding of computing in time and in space. On account of increasing interest in reconfigurable systems, the scope of this workshop has been substantially widened in comparison with previous years. It now deals with reconfigurability at all levels: reconfigurable processor networks structures, reconfigurable processors, as well as reconfigurable components.

The topics of interest of the workshop include reconfigurable systems, models, and implementations, as well as scalable programmable logic platforms (architectures, technology, CAD tools, applications), and also reconfigurable custom computing machines, reconfigurable accelerators and their applications. It also covers innovative development tools and methods and compilation techniques.

The primary goal of the workshop is to bridge the gap between hardware on one side, and HPC, parallel processing, or supercomputing on the other side. The building of reconfigurable systems can only be achieved by building on the experience in these different areas. Close interaction between them is necessary to identify and solve important research problems. The workshop aims to provide an opportunity to intensify creative interaction between researchers actively involved in the fabrication, design, applications and enabling technologies of reconfigurable architectures.

Submitting Papers:

Please send five (5) copies of complete paper (up to 10 single spaced, single sided pages) to:

Reiner W. Hartenstein
Universitaet Kaiserslautern (Germany)
Fax: +49 (631) 205-2640

Electronic submissions (in postscript format) are encouraged and should be sent to both hartenst@rhrk.uni-kl.de & abakus@informatik. uni-kl.de. All papers will be reviewed by the program committee. The workshop proceedings will be published by a professional publisher, taking care of ISBN number and Library of Congress catalog number.

Important Dates:

Manuscripts Due - January 3, 1997
Notification of Review Decisions - January 31, 1997
Final Version Due - February 28, 1997

For further information, please send email to hartenst@rhrk.uni-kl.de. To keep yourself up-to-date, also frequently check the RAW'97 Web page: http://xputers.informatik.uni-kl.de/RAW/RAW97.html. For ASCII version see http://xputers.informatik.unikl.de/RAW/RAW97/call_RAW97_txt.html.

Workshop 4: All Day Tuesday


Workshop Co-Chairs:
P. Berthome, LRI, Orsay, France
P.J. Marchand, UCSD, USA

Workshop 5: All Day Tuesday

Workshop Chair:
Dominique Mery, University Henri Poincare-Nancy 1 and IUF, France

Workshop 6: All Day Tuesday


Workshop Chair:
Hermann Hellwagner, Technische Universitaet Muenchen, Germany

Program Committee:

Arndt Bode, TU Muenchen
Helmar Burkhart, Universitaet Basel
John Carter, University of Utah
Michel Cosnard, ENS Lyon
Karsten Decker, SCSC
Ian Foster, Argonne Nat'l Labs
Michael Gerndt, Research Centre Juelich
Hermann Hellwagner, TU Muenchen
Tony Hey, University of Southampton
Francois Irigoin, Ecole des Mines de Paris
Pete Keleher, University of Maryland
Carl Kesselman, Caltech
Ulrich Kremer, Rutgers University
Thierry Priol, INRIA
Howard A. Sholl, University of Connecticut
Klaus E. Schauser, UC Santa Barbara
Bernard Tourancheau, ENS Lyon

One of the keys for a (commercial) breakthrough of parallel processing are high-level programming models that allow to produce truly efficient code. Along this way, languages and packages have been established which are more convenient than explicit message passing and allow higher productivity in software development. Examples are High Performance Fortran (HPF), thread packages for shared-memory based programming, and Shared Virtual Memory (SVM) environments.

Yet, current implementations of high-level programming models often suffer from low performance of the generated code, from the lack of corresponding high-level development tools, e.g. for performance analysis, and from restricted applicability, e.g., to the data parallel programming style. This situation requires strong research efforts in the design of parallel programming models and languages that are both at a high conceptual level and implemented efficiently, in the development of supportive tools, and in the integration of languages and tools into convenient programming environments. Hardware and operating system support for high-level programming, e.g., distributed shared memory and monitoring interfaces, are further areas of interest.

This workshop provides a forum for researchers and commercial developers to meet and discuss the various hardware and software issues involved in the design and use of high-level parallel programming models and supportive environments. Topics to be discussed include, but are not limited to:

- Concepts and languages for high-level parallel programming
- Concurrent object-oriented programming
- Automatic parallelization and optimization
- High-level programming environments
- Performance analysis techniques and tools
- Implementation techniques for high-level programming models
- Distributed shared memory
- Architectural support for high-level programming models

The workshop will consist of the presentations of submitted research articles, short presentations and discussions of ongoing projects, and an invited talk by Helmar Burkhart, University of Basel, Switzerland.

For further information, please contact:

Hermann Hellwagner
Institut fuer Informatik
Technische Universitaet Muenchen
D - 80290 Muenchen, Germany
Vox: +49-89-289-22386
Fax: +49-89-289-28232

or check the Web at


Workshop 7: All Day Tuesday


Workshop Chair:
Argy Krikelis, Aspex Microsystems Ltd., UK

Program Committee:

V. Michael Bove Jr., MIT Media Lab, USA
Shih-Fu Chang, Columbia University, USA
Edward J. Delp, Purdue University, USA
Ophir Frieder, George Mason University, USA
Martin Goebel, GMD, Germany
Argy Krikelis, Aspex Microsystems Ltd., UK
Tosiyasu L. Kunii, The University of Aizu, Japan
Yoshiyasu Takefuji, Keio University, Japan & Case Western Reserve University, USA

In the recent years multimedia technology has emerged as a key technology, mainly because of its ability to represent information in disparate forms as a bit-stream. This enables, everything from text to video and sound to be stored, processed and delivered in digital form. A great part of the current research community effort has emphasized the delivery of the data as an important issue of multimedia technology. However, the creation, processing, and management of multimedia forms are the issues most likely to dominate the scientific interest in the long run. The focus of the activity will be how multimedia technology deals with information, which is in general task-dependent and is extracted from data in a particular context by exercising knowledge. The desire to deal with information from forms such as video, text, and sound will result in a data explosion. This requirement to store, process, and manage large data sets naturally leads to the consideration of programmable parallel processing systems as strong candidates in supporting and enabling multimedia technology.

The workshop aims to act as a platform for topics related, but not limited, to:

- Parallel architectures for multimedia
- Mapping multimedia applications to parallel architectures
- System interfaces and programming tools to support multimedia
applications on parallel processing systems
- Multimedia content creation, processing and management using
parallel architectures
- Parallel processing architectures of multimedia set-top boxes
- Multimedia agent technology and parallel processing
- `Proof of concept' implementations and case studies

The workshop will include a keynote address, submitted papers, and a panel discussion. A proceedings of the accepted papers will be available at the workshop. In addition, the accepted papers will be appearing in a special issue of Parallel Computing.

The Keynote Speaker is Rick Stevens, Division Director of the Mathematics & Comp. Sci. Division, Director of High Performance Computing & Communications Program, Leader of the Computing & Communications Infrastructure Futures Laboratory, Argonne National Laboratory.

For more information contact:

Argy Krikelis
Aspex Microsystems Ltd.
Brunel University
Uxbridge, UB8 3PH
United Kingdom
Vox: + 44 1895 274000, ext: 2763
Fax: + 44 1895 258728

Workshop 8: All Day Tuesday


Workshop Chair:

Sanguthevar Rajasekaran, University of Florida, Gainesville

Program Committee:

Susanne E. Hambrusch, Purdue University
Frank Hsu, Fordham University
Oscar Ibarra, University of California, Santa Barbara
Joseph Ja'Ja', University of Maryland
Danny Krizanc, Carleton University
Tom Leighton, MIT
Rajeev Motwani, Stanford University
Michael Palis, Rutgers University
Greg Plaxton, University of Texas, Austin
Sanguthevar Rajasekaran, University of Florida (Chair)
Satish Rao, NEC
John Reif, Duke University
Sartaj Sahni, University of Florida
Paul Spirakis, University of Patras
Jeff Vitter, Duke University

Randomization has played a vital role in the domains of both sequential and parallel computing in the past two decades. This workshop is a forum for bringing together both theoreticians and practitioners who employ randomized techniques in parallel computing. Topics include but are not limited to:

- Network algorithms
- PRAM algorithms
- Architectures
- I/O systems
- Scheduling
- Network fault tolerance
- Reconfigurable networks
- Optical networks
- Various applications
- Programming models and languages
- Implementation experience

Papers of an experimental nature (describing implementation results) are especially sought. Authors are invited to submit previously unpublished original papers (that will not be submitted elsewhere) reflecting their current research results. All submitted papers will be refereed for quality and originality. Accepted papers will be published in the workshop proceedings.

Authors are requested to submit six copies of the manuscripts to S. Rajasekaran, Dept. of CISE, 301 CSE Building, University of Florida, Ganesville, FL 32611, USA by January 10, 1997. Late submissions run the risk of rejection without consideration of merits. Manuscript length should be no more than 12 double-spaced, single-sided pages using 12-point type. Contact email address: raj@cise.ufl.edu.

For more information:


Important dates:

Submissions Due - January 10, 1997
Notification - February 1, 1997
Camera Ready Manuscripts Due - March 5, 1997

Tutorial 1
8:30 AM - 12:30 PM


Horst D. Simon
NERSC Division, Lawrence Berkeley National Laboratory

Who Should Attend:

This tutorial is aimed at engineers and scientists with large scale applications programs, who are interested in the potential use of high performance computing technology for their applications. It will also be of interest to theoreticians in computer science or a general audience, who want to get up-to-date information on the current status of using parallel supercomputers for grand challenge applications.

Course Description:

This tutorial proposes to be a practical guide for beginners to the main topics and themes of high performance computing (HPC) for engineering and scientific applications. The intent is to provide some guidance and directions in the rapidly growing field of scientific computing using massively parallel supercomputers, clusters of symmetric multiprocessors, and high-end shared-memory systems. In the last few years highly parallel systems have become the tool of choice for solving the grand challenge problems of science and engineering. Even though many research issues concerning their effective use and their integration into a large scale production facility are still unresolved, parallel supercomputers are now widely used for production computing. In this talk I will share the experience gained at the National Energy Research Scientific Computing (NERSC) Center in using these different architectures for solving grand challenge problems in science and engineering.


Since February 1996, Dr. Horst D. Simon is Director of the NERSC (National Energy Research Scientific Computing) Division located at Lawrence Berkeley National Laboratory in Berkeley, CA. NERSC is the principal supplier of production high performance computing services to the nationwide energy research community. From 1994-1996 Simon was with the Advanced System Division of Silicon Graphics where he managed SGI's university and research laboratory programs. Previously he held positions related to supercomputing with Boeing, and with CSC at NASA Ames Research Center. Dr. Simon's algorithm research efforts were honored with the 1988 Gordon Bell Prize for parallel processing research. He participated significantly in the development of the NAS Parallel Benchmarks. Simon previously taught at SUNY Stony Brook. He holds a Diploma in Mathematik from the TU Berlin, Germany (1978) and a PhD in Mathematics from the University of California, Berkeley (1982).

Tutorial 2
1:30 PM - 5:30 PM

Anthony Skjellum, Mississippi State University
Andrew Lumsdaine, University of Notre Dame

Who Should Attend:

Training in the uses and capabilities of MPI is currently of interest to high performance programmers and analysts, researchers who want to parallelize demanding applications, and technically oriented managers who want to understand how this technology can be introduced into their company.

Course Description:

MPI, the Message Passing Interface, is an important emerging standard for message passing in parallel and distributed application programming. MPI, defined by the stand-alone MPI Forum, includes a formal standards document, and is widely implemented, both in free implementations and by several commercial companies. MPI usage is growing rapidly, and has had a tremendously positive impact on High Performance Computing. This tutorial will cover key features of MPI-1 and MPI-2 including point-to-point and collective communication operations, communicators, data types, topologies, intercommunicators, and dynamic process management.


Anthony Skjellum is a graduate of the California Institute of Technology (BS, MS, PhD). He is currently an Associate Professor of Computer Science at Mississippi State University, with joint appointment to the NSF Engineering Research Center for Computational Field Simulation. He was a Computer Scientist at the Lawrence Livermore National Laboratory (DOE), prior to coming to MSU in 1993. He has been involved with message passing software research for eight years, with leading involvement in MPI-1 and MPI-2 Forums, including chairing the MPI Real-time subcommittee of MPI-2.

Andrew Lumsdaine (PhD, MIT, 1992) has been working in the area of high performance parallel computing for over eight years. He is currently on the faculty in the Department of Computer Science and Engineering at the University of Notre Dame and is an active participant in the MPI Forum. His research interests include parallel processing, scientific computing, numerical methods and software, and VLSI circuit and semiconductor device simulation.

Tutorial 3
1:30 PM - 5:30 PM


Mani Chandy and John Thornley
California Institute of Tecnnology Pasadena, California

Who Should Attend:

Computer scientists interested in: constructs for concurrency in Java, Windows NT, and Pthreads, structured design and development of concurrent applications, distributed applications on the internet, and parallel applications on shared-memory multiprocessors.

Course Description:

This tutorial introduces distributed computing using Java, and parallel computing using thread libraries, such as the Windows NT thread library and the POSIX thread standard (Pthreads). The motivation for the tutorial is three-fold: (1) the dramatic increase in the power and prevalence of network-centric languages and tools, (2) the emergence of shared-memory multiprocessor computers as commodity products, and (3) the demand for active object networks and parallel applications from computer users. The emphasis of the tutorial is on systematic design and development methods. This is important because concurrent applications are complex, reasoning and debugging are difficult, and the constructs provided by current languages and libraries are unstructured.

The lecture outline is as follows:

- Introduction to the object-oriented features of Java
- Constructs provided by Java for multithreaded programming
- Java libraries for message passing
- A worldwide active object network layered on top of Java
- Practical examples of distributed applications
- Introduction to the multithreaded programming constructs provided by Windows NT and Pthreads
- Performance issues in multithreaded programming of shared-memory multiprocessors
- Design, development, and reasoning issues in multithreaded programming for performance
- A high-level, structured parallel programming layer defined on top of Windows NT and Pthreads
- Practical examples with performance measurements


Mani Chandy received a BTech from IIT Madras, an MS from the Polytechnic University of New York, and a PhD from MIT. He has been a Professor of Computer Science at the California Institute of Technology since 1989. He was a Professor and Chair in the Computer Science Department at the University of Texas at Austin from 1970 to 1989. He was awarded the A.A. Michelson award for his contributions to computer performance modeling, and the IEEE Koji Kobayashi award for computers and communication. He was a Sherman Fairchild Fellow in 1987. He is an IEEE Fellow and a member of the US National Academy of Engineers. He has written several books and numerous papers on computer performance modeling, distributed discrete-event simulation, distributed algorithms, and formal methods for reasoning about concurrent programs.

John Thornley received a BSc and MSc from the University of Auckland in New Zealand. He was a Lecturer in Computer Science at the University of Auckland from 1984 to 1990. He received an MS and PhD from the California Institute of Technology, where he is presently a Postdoctoral Scholar in Computer Science. He is currently writing a book with Mani Chandy on structured parallel programming for shared-memory multiprocessors. His research interests include parallel and distributed computing, systematic programming methods, and programming language design and implementation.


10:00 AM - 12:00 PM
Chair: Mateo Valero
Universitat Politecnica de Catalunya, Spain

A Study of the Efficiency of Shared Attraction Memories in Cluster-Based COMA Multiprocessors
Anders Landin and Mattias Karlgren, SICS, Sweden

An Evaluation of a Commerical CC-NUMA Architecture - the CONVEX Exemplar SPP1200
Radhika Thekkath and Amit Pal Singh, Stanford University, Jaswinder Pal Singh, Princeton University, Susan John, National Center for Supercomputing Applications, John Hennessy, Stanford University

Coherent Block Data Transfer in the FLASH Multiprocessor
John Heinlein, Stanford University, Kourosh Gharachorloo, DEC Western Research Laboratory, Robert P. Bosch, Jr., Mendel Rosenblum, and Anoop Gupta, Stanford University

A Memory Efficient Array Architecture for Real-Time Motion Estimation
Vasily G. Moshnyaga and Keikichi Tamaru, Kyoto University, Japan

An Efficient Technique of Instruction Scheduling on a Superscalar-Based Multiprocessor
Rong-Yuh Hwang, National Taipei Institute of Technology, R.O.C.

Accuracy and Speed-Up of Parallel Trace-Driven Architectural Simulation
A-T. Nguyen, M. Michael, A. Nanda, K. Ekanadham, and P. Bose, IBM Thomas J. Watson Research Center

10:00 AM - 12:00 PM
Networks I
Chair: Sartaj Sahni
University of Florida

Wide-Sense Nonblocking Clos Networks under Packing Strategy
Yuanyuan Yang, University of Vermont, Jianchao Wang, GTE Laboratories

Gracefully Degradable Pipeline Networks
Robert Cypher and Ambrose K. Laing, Johns Hopkins University

Distributed Submesh Determination in Faulty Tori and Meshes
Hsing-Lung Chen, National Taiwan Institute of Technology, R.O.C., Shu-Hua Hu, Jin-Wen College of Business and Technology, R.O.C.

Modeling Communication Costs in Multiplexed Optical Switching Networks
C. Salisbury and R. Melhem, University of Pittsburgh

Characterization of Deadlocks in Interconnection Networks
Sugath Warnakulasuriya and Timothy Mark Pinkston, University of Southern California

k-ary n-trees: High Performance Networks for Massively Parallel Architectures
Fabrizio Petrini, Universita di Pisa, Italy

10:00 AM - 12:00 PM
Chair: Alok Choudhary
Northwestern University

An Architecture Workbench for Multicomputers
A.D. Pimentel and L.O. Hertzberger, University of Amsterdam, The Netherlands

SuperWeb: Towards a Global Web-Based Parallel Computing Infrastructure
Alberto D. Alexandrov, Maximilian Ibel, Klaus E. Schauser, and Chris J. Scheiman, University of California, Santa Barbara

S-Check: A Tool for Tuning Parallel Programs
Robert Snelick, National Institute of Standards and Technology

Causality Filters: A Tool for the Online Visualization and Steering of Parallel and Distributed Programs
Eileen Kraemer, Washington University in St. Louis

Interactive Visual Exploration of Distributed Computations
Delbert Hart, Eileen Kraemer, and Gruia-Catalin Roman, Washington University in St. Louis

High Performance Computational Steering of Physical Simulations
Jeffrey Vetter and Karsten Schwan, Georgia Institute of Technology

1:30 PM - 3:30 PM
Chair: Allan Gottlieb
New York University & NEC Research Institute

Fault-Tolerant Deadline-Monotonic Algorithm for Scheduling Hard-Real-Time Tasks
Alan A. Bertossi, Andrea Fusiello, and Luigi Mancini, Universita di Trento, Italy

Performance Comparison of Processor Scheduling Strategies in a Distributed-Memory Multicomputer System
Yuet-Ning Chan, Sivarama P. Dandamudi, and Shikharesh Majumdar, Carleton University, Canada

Optimal Scheduling for UET-UCT Generalized n-Dimensional Grid Task Graphs
Theodore Andronikos, Nectarios Koziris, George Papakonstantinou, and Panayotis Tsanakas, National Technical University of Athens, Greece

A Comparison of General Approaches to Multiprocessor Scheduling
Jing-Chiou Liou, AT&T Laboratories, Middletown, Michael A. Palis, Rutgers University

DFRN: A New Approach on Duplication Based Scheduling for Distributed Memory Multiprocessor Systems
Gyung-Leen Park, Behrooz Shirazi, The University of Texas at Arlington, Jeff Marquis, Parallel Solutions, Inc.

Dynamic Processor Scheduling with Client Resources for Fast Multi-resolution WWW Image Browsing
Daniel Andresen, Tao Yang, and David Watson, University of California, Santa Barbara

1:30 PM - 3:30 PM
Chair: Josep Diaz
Universitat Politecnica de Catalunya, Spain

Performance Analysis and Optimization on a Parallel Atmospheric General Circulation Model Code
John Z. Lou, Jet Propulsion Laboratory, John D. Farrara, University of California, Los Angeles

A Tool for On-Line Visualization and Interactive Steering of Parallel HPC Applications
Sabine Rathmayer and Michael Lenke, Technische Universitat Munchen, Germany

Performance Prediction for Complex Parallel Applications
Jurgen Brehm, University of Hannover, Germany, Patrick Worley, Oak Ridge National Laboratory

Implementation and Results of Hypothesis Testing from the C3I Parallel Benchmark Suite
Brian VanVoorst, Luiz Pires, Rakesh Jha, and Mustafa Muhhamad, Honeywell Technology Center

Real-Time Parallel MPEG-2 Decoding in Software
Angelos Bilas, Jason Fritts, and Jaswinder Pal Singh, Princeton University

Parallel Inference on a Linguistic Knowledge Base
Sanda M. Harabagiu, University of Southern California, Dan I. Moldovan, Southern Methodist University

1:30 PM - 3:30 PM
Performance Evaluation
Chair: Jose D.P. Rolim
University of Geneva

Predicting Queue Times on Space-sharing Parallel Computers
Allen B. Downey, University of California, Berkeley and San Diego Supercomputer Center

A Data Parallel Fortran Benchmark Suite
Yu Hu, Harvard University, Lennart Johnsson, Harvard University and University of Houston, Dimitris Kehagias and Nadia Shalaby, Harvard University

Latency Tolerance: A Metric for Performance Analysis of Multithreaded Architectures
Shashank S. Nemawarkar and Guang R. Gao, McGill University, Canada

Architecture and Performance of the Hitachi SR2201 Massively Parallel Processor System
Hiroaki Fujii, Yoshiko Yasuda, Hideya Akashi, Yasuhiro Inagami, Makoto Koga, Osamu Ishihara, Masamori Kashiyama, Hideo Wada, and Tsutomu Sumimoto, Hitachi, Ltd., Japan

Experience with Fine-Grain Communication in EM-X Multiprocessor for Parallel Sparse Matrix Computation
Mitsuhisa Sato, Real World Computing Partnership, Japan, Yuetsu Kodama, Hirofumi Sakane, Hayato Yamana, Shuichi Sakai, and Yoshinori Yamaguchi, Electrotechnical Laboratory, Japan

A Customizable Simulator for Workstation Networks
Mustafa Uysal, Anurag Acharya, Robert Bennett, and Joel Saltz, University of Maryland

4:00 PM - 6:00 PM
Synchronization and Threads
Chair: Kai Li
Princeton University

Empirical Evaluation of Distributed Mutual Exclusion Algorithms
Shiwa S. Fu, Nian-Feng Tzeng, and Zhiyuan Li, University of Southwestern Louisiana

External Adjustment of Runtime Parameters in Time Warp Synchronized Parallel Simulators
Radharamanan Radhakrishnan, Lantz Moore, and Philip A. Wilsey, University of Cincinnati

Relative Performance of Preemption-Safe Locking and Non-Blocking Synchronization on Multiprogrammed Shared Memory Multiprocessors
Maged M. Michael and Michael L. Scott, University of Rochester

Reliable Hardware Barrier Synchronization Schemes
Rajeev Sivaram, Ohio State University, Craig B. Stunkel, IBM T.J. Watson Research Center, Dhabaleswar K. Panda, Ohio State University

Analysis of Several Scheduling Algorithms under the Nano-Threads Programming Model
Xavier Martorell, Jesus Labarta, Nacho Navarro, and Eduard Ayguade, Universitat Politecnica de Catalunya (UPC), Spain

Comparing Gang Scheduling with Dynamic Space Sharing on Symmetric Multiprocessors Using Automatic Self-Allocating Threads (ASAT)
Charles Severance and Richard Enbody, Michigan State University

4:00 PM - 6:00 PM
Algorithms I
Chair: Sanguthevar Rajasekaran
University of Florida

A Randomized Sorting Algorithm on the BSP model
Alexandros V. Gerbessiotis and Constantinos J. Siniolakis, Oxford University, United Kingdom

Work-Time Optimal k-merge Algorithms on the PRAM
Tatsuya Hayashi and Koji Nakano, Nagoya Institute of Technology, Japan, Stephan Olariu, Old Dominion University

Optimizing Parallel Bitonic Sort
Mihai F. Ionescu and Klaus E. Schauser, University of California, Santa Barbara

A Fast Scalable Universal Matrix Multiplication Algorithm on Distributed-Memory Concurrent Computers
Jaeyoung Choi, Soongsil University, Korea

Matrix Transpose on Meshes: Theory and Practice
Michael Kaufmann, Universitat Tubingen, Germany, Ulrich Meyer and Jop F. Sibeyn, Max-Planck-Institut fur Informatik, Germany

Coarse Grained Parallel Geometric Search
Albert Chan and Frank Dehne, Carleton University, Canada, Andrew Rau-Chaplin, Technical University of Nova Scotia, Canada

4:00 PM - 6:00 PM
Chair: Gianfranco Bilardi
Universita di Padova and University of Illinois at Chicago

Optimal Wormhole Routing in the (n,d)-Torus
Stefan Bock, Friedhelm Meyer auf der Heide, and Christian Scheideler, University of Paderborn, Germany

Adaptive Fault-Tolerant Wormhole Routing Algorithms for Hypercube and Mesh Interconnection Networks
Jau-Der Shih, National Pingtung Teachers College, R.O.C.

A Hybrid Interconnection Network for Integrated Communication Services
Yi-long Chen, Nortel, Jyh-Charn Liu, Texas A&M University

Deadlock-free Fault-tolerant Routing in the Multi-dimensional Crossbar Network and its Implementation for the Hitachi SR2201
Yoshiko Yasuda, Hiroaki Fujii, Hideya Akashi, Yasuhiro Inagami, Teruo Tanaka, Junji Nakagoshi, Hideo Wada, and Tsutomu Sumimoto, Hitachi, Ltd., Japan

An Accurate Model for the Performance Analysis of Deterministic Wormhole Routing
B. Ciciani, Universita di Roma "La Sapienza", Italy, M. Colajanni, Universita di Roma "Tor Vergata", Italy, C. Paolucci, Universita di Roma "La Sapienza", Italy


8:00 AM - 10:00 AM
I/O and Message Passing
Chair: Anthony Skjellum
Mississippi State University

Design and Evaluation of Data Storage and Retrieval Strategies in a Distributed Memory Continuous Media Server
Chutimet Srinilta and Divyesh Jadav, Syracuse University, Alok Choudhary, Northwestern University

MTIO A Multi-Threaded Parallel I/O System
Sachin More and Alok Choudhary, Northwestern University, Ian Foster and Ming Q. Xu, Argonne National Laboratory

Low Latency MPI for Meiko CS/2 and ATM Clusters
Chris R. Jones, Ambuj K. Singh, and Divyakant Agrawal, University of California, Santa Barbara

Reducing Waiting Costs in User-Level Communication
Stefanos N. Damianakis, Yuqun Chen, and Edward W. Felten, Princeton University

Design and Implementation of Virtual Memory-Mapped Communication on Myrinet
Cezary Dubnicki, Angelos Bilas, and Kai Li, Princeton University, James Philbin, NEC Research Institute

8:00 AM - 10:00 AM
Algorithms II
Chair: Tao Yang
University of California at Santa Barbara

Designing Efficient Distributed Algorithms Using Sampling Techniques
Sanguthevar Rajasekaran, University of Florida, David S.L. Wei, The University of Aizu, Japan

Fast Parallel Computation of the Polynomial Shift
Eugene V. Zima, Moscow State University, Russia

A Parallel Algorithm for Weighted Distance Transforms
Akihiro Fujiwara, Michiko Inoue, Toshimitsu Masuzawa, and Hideo Fujiwara, Nara Institute of Science and Technology (NAIST), Japan

Parallel Solutions of Indexed Recurrence Equations
Yosi Ben-Asher, Haifa University, Israel, Gady Haber, IBM Science and Technology, Haifa, Israel

Joining Forces in Solving Large-Scale Quadratic Assignment Problems in Parallel
Adrian Brungger and Ambros Marzetta, Swiss Federal Institute of Technology, Switzerland, Jens Clausen and Michael Perregaard, University of Copenhagen, Denmark

8:00 AM - 10:00 AM
Chair: Hans Zima
University of Vienna

Optimization Schemas for Parallel Implementation of Nondeterministic Languages and Systems
Gopal Gupta and Enrico Pontelli, New Mexico State University

Logic Channels: A Coordination Approach to Distributed Programming
M. Diaz, B. Rubio, and J.M. Troya, Universidad de Malaga, Spain

Efficient Algorithms for Parallelization of Loops at Run-Time
Chengzhong Xu and Vipin Chaudhary, Wayne State University

Interoperability of Data Parallel Runtime Libraries
Guy Edjlali, Alan Sussman, and Joel Saltz, University of Maryland

Platform-Independent Runtime Optimizations Using OpenThreads
Matthew Haines, University of Wyoming, Koen Langendoen, Vrije Universiteit, The Netherlands

10:30 AM - 12:30 PM
Shared Memory
Chair: James Philbin
NEC Research Institute

Aurora: Scoped Behavior for Per-Context Optimized Distributed Data Sharing
Paul Lu, University of Toronto, Canada

Evaluating the Performance of Software Distributed Shared Memory as a Target for Parallelizing Compilers
Alan L. Cox, Sandhya Dwarkadas, Honghui Lu, and Willy Zwaenepoel, Rice University

View Caching: Efficient Software Shared Memory for Dynamic Computations
Vijay Karamcheti and Andrew A. Chien, University of Illinois at Urbana-Champaign

Enhancing Software DSM for Compiler-Parallelized Applications
Pete Keleher and Chau-Wen Tseng, University of Maryland

Relative Performance of Hardware and Software-Only Directory Protocols Under Latency Tolerating and Reducing Techniques
Hakan Grahn, University of Karlskrona/ Ronneby, Sweden, Per Stenstrom, Chalmers University of Technology, Sweden

10:30 AM - 12:30 PM
Algorithms III
Chair: Uzi Vishkin
University of Maryland and Tel Aviv University

O(log log N) Time Algorithms for Hamiltonian-Suffix and Min-Max-Pair Heap Operations on the Hypercube
Sajal K. Das, University of North Texas, M. Cristina Pinotti, CNR, Italy, Falguni Sarkar, University of North Texas

A Parallel Tabu Search Algorithm for the 0-1 Multidimensional Knapsack Problem
Smail Niar and Arnaud Freville, Universite de Valenciennes, France

Lower Bounds on Systolic Gossip
Michele Flammini, University of LAquila, Italy, Stephane Perennes, Universite de Nice-Sophia Antipolis, France

Parallel Simulated Annealing: An Adaptive Approach
Jonas Knopman, Federal University of Rio de Janeiro - NCE, Brazil, Julio S. Aude, Federal University of Rio de Janeiro - NCE and IM, Brazil

Parallel Global Routing Algorithms for Standard Cells
Zhaoyun Xing, University of Illinois at Urbana-Champaign, John Chandy, Cadence Design Systems, Prithviraj Banerjee, Northwestern University

10:30 AM - 12:30 PM
Compilers I
Chair: Emilio Zapata
University of Malaga, Spain

On Privatization of Variarles for Data-Parallel Execution
Manish Gupta, IBM T.J. Watson Research Center

Semantics and Implementation of a Generalized forall Statement for Parallel Languages
P.F.G. Dechering, L.C. Breebaart, F. Kuijlman, C. van Reeuwijk, and H.J. Sips, Delft University of Technology, The Netherlands

A BSP Approach to the Scheduling of Tightly-Nested Loops
Radu Calinescu, Oxford University Computing Laboratory, England

A Formal Model of Software Pipelining Loops with Conditions
Dragan Miliaeev and Zoran Jovanoviae, University of Belgrade, Yugoslavia

Data Access Reorganizations in Compiling Out-of-Core Data Parallel Programs on Distributed Memory Machines
M. Kandemir, Syracuse University, R. Bordawekar, Caltech, A. Choudhary, Northwestern University

2:00 PM - 4:00 PM
Networks II
Chair: Timothy Pinkston
University of Southern California

A Hybrid Time Synchronization Implemented Through Special Ring Array for Mesh or Torus
Yuzhong Sun, Zhiwei Xu, and Mingfa Zhu, National Research Center for Intelligent Computers, P.R.C.

Deadlock- and Livelock-Free Routing Protocols for Wave Switching
Jose Duato and Pedro Lopez, Universidad Politecnica de Valencia, Spain, Sudhakar Yalamanchili, Georgia Institute of Technology

Architecture-Dependent Tuning of the Parameterized Communication Model for Optimal Multicasting
Natawut Nupairoj and Lionel M. Ni, Michigan State University, Ju-Young L. Park, Duksung Womens University, Korea, Hyeong-Ah Choi, George Washington University

Crossbar Analysis for Optimal Deadlock Recovery Router Architecture
Yungho Choi and Timothy Mark Pinkston, University of Southern California

Performance Analysis of Minimal Adaptive Wormhole Routing with Time-Dependent Deadlock Recovery
Fabrizio Petrini and Marco Vanneschi, Universita di Pisa, Italy

2:00 PM - 4:00 PM
Algorithms IV
Chair: Sajal Das
University of North Texas

A Parallel Convex Hull Algorithm with Optimal Communication Phases
Jieliang Zhou, Xiaotie Deng, and Patrick Dymond, York University, Canada

An Efficient Parallel Strategy for Computing K-terminal Reliability and Finding Most Vital Edge in 2-trees and Partial 2-trees
Chin-Wen Ho, National Central University, Taiwan, Sun-Yuan Hsieh and Gen-Huey Chen, National Taiwan University, Taiwan

An Efficient Parallel Algorithm for Solving the Knapsack Problem on the Hypercube
A. Goldman and D. Trystram, LMC-IMAG, France

d-Dimensional Range Search on Multicomputers
Afonso Ferreira and Claire Kenyon, LIP ENS-Lyon, France, Andrew Rau-Chaplin, Technical University of Nova Scotia, Canada, Stephane Ubeda, LIP ENS-Lyon, France

Control Schemes in a Generalized Utility for Parallel Branch-and-Bound Algorithms
Yuji Shinano, Kenichi Harada, and Ryuichi Hirabayashi, Science University of Tokyo, Japan

2:00 PM - 4:00 PM
Compilers II
Chair: Prith Banerjee
Northwestern University

Alias Analysis for Fortran90 Array Slices
K. Gopinath and R. Seshadri, Indian Institute of Science, India

A Compile-Time Partitioning Strategy for Non-Rectangular Loop Nests
Rizos Sakellariou, University of Manchester, United Kingdom

The Sparse Cyclic Distribution against its Dense Counterparts
Gerardo Bandera, University of Malaga, Spain, Manuel Ujaldon, University of Malaga, Spain and University of Maryland, Maria A. Trenas and Emilio L. Zapata, University of Malaga, Spain

A Compiler-Directed Cache Coherence Scheme Using Data Prefetching
Hock-Beng Lim, University of Illinois at Urbana-Champaign, Pen-Chung Yew, University of Minnesota

Extensible Message Passing Application Development and Debugging with Python
David M. Beazley, University of Utah, Peter S. Lomdahl, Los Alamos National Laboratory

4:30 PM - 6:30 PM
Architecture Theory
Chair: Ali Hurson
Pennsylvania State University

Parallel `Go with the Winners' Algorithms in the LogP Model
Marcus Peinado and Thomas Lengauer, German National Research Center for Information Technology (GMD), Germany

A Comparison of Parallel Approaches for Algebraic Factorization in Logic Synthesis
Sumit Roy, University of Illinois at Urbana-Champaign, Prithviraj Banerjee, Northwestern University

Conflict-Free Access to Multiple Single-Ported Register Files
Silvia M. Mueller, University of Saarland, Germany, Uzi Vishkin, University of Maryland and Tel Aviv University

On the Dynamic Initialization of Parallel Computers
Stephan Olariu, Old Dominion University, Ivan Stojmenovic, University of Ottawa, Canada, Albert Y. Zomaya, University of Western Australia, Perth, Australia and Waterloo University, Canada

Searching Trees On-Line on the Reconfigurable Mesh
Michael A. Palis, Rutgers University, David S.L. Wei, Kshirasagar Naik, and Osamu Koitabashi, The University of Aizu, Japan

4:30 PM - 6:30 PM
Data Structures
Chair: Afonso Ferreira
CNRS, LIP - ENS Lyon, France

The Impact of Timing on Linearizability in Counting Networks
Marios Mavronicolas, University of Cyprus, Nicosia, Cyprus, Marina Paptriantafilou and Philippas Tsigas, Max-Planck-Institut fur Informatik, Germany

A Parallel Priority Data Structure with Applications
Gerth Stolting Brodal, University of Aarhus, Denmark, Jesper Larsson Traff and Christos D. Zaroliagis, Max-Planck-Institut fur Informatik, Germany

Multiple Templates Access of Trees in Parallel Memory Systems
Vincenzo Auletta, Amelia De Vivo, and Vittorio Scarano, Universita di Salerno, Italy

Maintaining Spatial Data Sets in Distributed-Memory Machines
Susanne E. Hambrusch, Purdue University, Ashfaq A. Khokhar, University of Delaware

Geometric Data Structures on a Reconfigurable Mesh, with Applications
Amitava Datta, University of New England, Australia

4:30 PM - 6:30 PM
Networks III
Chair: Helmar Burkhart
University of Basel, Switzerland

Efficient Sorting and Routing on Reconfigurable Meshes Using Restricted Bus Length
Manfred Kunde and Kay Gurtzig, Technical University of Ilmenau, Germany

Oblivious Routing Algorithms on the Mesh of Buses
Kazuo Iwama and Eiji Miyano, Kyushu University, Japan

Nearly Optimal One-to-Many Parallel Routing in Star Networks
Chi-Chang Chen, Tatung Institute of Technology, R.O.C., Jianer Chen, Texas A&M University

Broadcasting and Multicasting in Cut-through Routed Networks
Johanne Cohen and Pierre Fraigniaud, Ecole Normale Superieure de Lyon, France, Jean-Claude Konig, Universite d'Evry, France, Andre Raspaud, Universite de Bordeaux 1, France

Cyclic Networks: A Family of Versatile Fixed-Degree Interconnection Architectures
Chi-Hsiang Yeh and Behrooz Parhami, University of California, Santa Barbara

10:30 AM - 12:30 PM
Industrial Track Co-Chairs:
John K. Antonio, Texas Tech University, USA
Helmar Burkhart, University of Basel, SWITZERLAND

Electronics and Telecommunications Research Institute (ETRI)
Topic: SPAX: A New Parallel Processing System for Commercial Application
Authors: Woo-Jong Hahn, Principal Member of Engineering Staff, Sang-Seok Shin, Principal Member of Engineering Staff, Ki-Wook Rim, Director of Computer Systems Department, and Soo-Won Kim, Professor of Electronics Engineering (Korea University)

Sun Microsystems, Inc.
Topic: Scalability of SCI Workstation Clusters: A Preliminary Study
Authors: Knut Omang, Research Fellow (University of Oslo, Norway) and Bodo Parady, Staff Engineer, SMCC Performance

Tandem Computers, Inc.
Topic: Maximum Delivery Time and Hot Spots in ServerNet-TM Topologies
Authors: Dimiter R. Avresky, Associate Professor of ECE (Boston University, USA), Vladimir Shurbanov, Graduate Research Assistant (Boston University, USA), Robert Horst, Technical Director of Tandem Labs, William Watson, Member of Arch/Perf & Design Validation, Luke Young, Member of Systems Verification, and Doug Jewett, Member of Tandem Labs

2:00 PM - 4:00 PM

To Be Announced


9 AM - 4 PM

General Coordinator:
Zvi M. Kedem, Courant Institute of Mathematical Sciences

Program Chair:
Krishna V. Palem, Courant Institute of Mathematical Sciences

9:00 AM - 10:00 AM

Parallelism and Concurrency in the Emerging Virtual Enterprise Frances E. Allen
T.J. Watson Research Center, IBM

10:30 AM - 11:30 AM

DNA Based Parallel Computers
Richard J. Lipton
Department of Computer Science, Princeton University

12:00 PM - 1:00 PM

Irregular Applications on the SB-PRAM
Wolfgang Paul
Department of Computer Science, University of Saarlandes

2:30 PM - 4:00 PM

Building Parallel Systems: Experiences and Lessons Learned

Anant Agarwal, Massachusetts Institute of Technology

Panel Members:
Dennis Gannon, Indiana University
Allan Gottlieb, NYU and NEC
Kai Li, Princeton University
David Wood, University of Wisconsin

- IPPS'97 Dinner Cruise -

6:00 PM Departure
9:30 PM Return (approx.)

Details for boarding the boat will be available at registration check-in. See the IPPS'97 Registration Form to reserve additional places for family and guests.


Workshop 9: All Day Saturday
Workshop Co-Chairs:
Matthew Haines, University of Wyoming
Greg Benson, University of California

Program Chair:

Koen Langendoen, Faculty of Mathematics and Computer Science, Vrije Universiteit de Boelelaan

Program Committee:

Greg Andrews, University of Arizona, USA
Henrk Bal, Vrije Universiteit, The Netherlands
Greg Benson, University of California, Davis, USA
Wim Bohm, Colorado State University, USA
Denis Caromel, University of Nice - INRIA Sophia Antipolis, France
Ian Foster, Argonne National Laboratory, USA
Dennis Gannon, Indiana University, USA
Dirk Grunwald, University of Colorado, USA
Matthew Haines, University of Wyoming, USA
Koen Langendoen, Vrije Universiteit, The Netherlands
Frank Mueller, Humboldt-Universitaet zu Berlin, Germany
Ron Olsson, University of California, Davis, USA

Runtime systems are critical to the implementation of parallel programming languages and libraries. They provide the core functionality of a particular programming model and the glue between the model and the underlying hardware and operating system. As such, runtime systems have a large impact on the performance and portability of parallel programming systems.

Despite the importance of runtime systems, few papers describing their design and implementation appear in the literature. RTSPP will provide a forum where researchers can present their results and ideas on runtime systems for parallel programming. The one-day workshop will include both paper presentations and invited talks.

The focus of the workshop is on the design and implementation of runtime systems for parallel programming languages and libraries. The topics for the workshop include, but are not limited to, the following:

- Techniques to reduce the tension between portability and efficiency in runtime systems
- Relationship between runtime systems and programming models
- Interfaces between compiler-generated code and runtime systems
- Operating system support for runtime systems
- Performance evaluation of runtime systems
- The design and implementation of runtime systems for high-speed networks
- The design and implementation of thread systems
- Runtime systems for distributed shared memory
- Extensibility and adaptability in runtime systems

The contributed papers for the RTSPP workshop will be selected by the program committee through a thorough reviewing process. These papers will be published in a proceedings along with the IPPS proceedings, which will be available at the workshop.

For further information about RTSPP, please look at the Web page at: http://www.cs.vu.nl/~rtspp/, or contact one of the organizers.

Matthew Haines - General Chair
University of Wyoming
Laramie, WY 82071-3682, USA
Vox: (307) 766-2440
Fax: (307) 766-4036

Koen Langendoen - Program Chair
Faculty of Mathematics and Computer Science
Vrije Universiteit
de Boelelaan 1081a
1081 HV Amsterdam
The Netherlands
Vox: +31 20 44 47754
Fax: +31 20 44 47653

Greg Benson - Co-Chair
Department of Computer Science
University of California
Davis, CA 95616, USA
Vox: (916) 752-6476
Fax: (916) 752-4767

Workshop 10: All Day Saturday
Workshop Co-Chairs:
Dror Feitelson, Hebrew University
Larry Rudolph, Hebrew University & MIT

Workshop 11: All Day Saturday
Workshop Co-Chairs:
Devesh Bhatt, Honeywell Technology Center, USA
Viktor Prasanna, University of Southern California, USA

Program Committee:

Ashok Agrawala, University of Maryland, USA
Milissa Benincasa, Integrated Sensors, Inc., USA
Clive Benjamin, Wright Laboratory, USA
Bob Bernecky, NUWC, USA
Terry Fountain, University College, London, UK
Richard Games, MITRE, USA
Farnam Jahanian, University of Michigan, USA
Craig Lund, Mercury Computer Systems, Inc., USA
David Martinez, MIT Lincoln Laboratory, USA
Rick Metzger, Rome Laboratory, USA
Stephen Rhodes, Advanced Systems Architectures Ltd., UK
Philip Sementilli, Hughes Missile Systems Co., USA
Anthony Skjellum, Mississippi State University, USA
Lothar Thiele, Swiss Federal Institute of Technology, Zuerich, Switzerland
Chip Weems, University of Massachusetts, USA
Sudhakar Yalamanchili, Georgia Tech., USA

Advisory Committee:

Keith Bromley, NRaD, USA
Dieter Hammer, Eindhoven University of Technology, The Netherlands
Jose Munoz, DARPA/ Information Technology Office, USA
Clayton Stewart, SAIC, USA
Lonnie Welch, University of Texas at Arlington, USA

The International Workshop on Embedded HPC Systems and Applications (EHPC) is a forum for the presentation and discussion of approaches, research findings, and experiences in the applications of High Performance Computing (HPC) technology for embedded systems. Of interest are both the development of relevant technology (e.g., hardware, middleware, tools) as well as the embedded HPC applications built using such technology.

We hope to bring together industry, academia, and government researchers/users to explore the special needs and issues in applying HPC technologies to defense and commercial applications.

Topics of interest include:

- Algorithms and applications
- Programming models and environments
- Methodologies and tools
- Performance modeling/simulation
- Partitioning/mapping and architecture trade-offs
- System integration, debugging, and testing tools
- Operating systems and middleware services
- Static/dynamic resource management
- Architectures, including special-purpose processors

The workshop will feature technical papers, presentations, a keynote speech, and an open discussion session. Workshop advance program will be made available on the Web by March 1997.

Workshop proceedings will be published on the World Wide Web. Abstracts will be distributed in hard-copy to the workshop attendees. For further information, please contact:

Devesh Bhatt
Honeywell Technology Center
3660 Technology Drive
Minneapolis, MN 55418 USA
Vox: +1 (612) 951-7316

Workshop 12: All Day Saturday
Workshop Co-Chairs:
Dimiter Avresky, Boston University
David R. Kaeli, Northeastern University

Program Committee:

J. Bruck, Caltech, USA
B. Ciciani, University of Roma, Italy
F. Cristian, U.C. San Diego
A. Goyal, IBM Watson Research Center, USA
J. Hayes, University of Michigan
D. Jewett, Tandem Computers Inc., USA
M. Karpovsky, Boston University, USA
H. Levendel, Lucent Technology, USA
Q. Li, Santa Clara University, USA
D. Pradhan, Texas A&M University, USA
M. Raynal, IRISA, France
B. Smith, IBM Watson Research Center, USA
K. Trivedi, Duke University, USA

Increasingly large parallel computing systems provide unique challenges to the researchers in dependable computing, especially because of the high failure rates intrinsic to these systems. While commercial and scientific companies share the need for massive throughput and low latency, dependability of service is also a concern. In addition to providing uninterrupted service, commercial systems must be free from data corruption. Achieving dependability in highly scalable parallel and distributed systems poses a considerable challenge. As the number of components increases, so does the probability of a component failure. Therefore, improved fault-tolerant technology is required for high scalable parallel and distributed systems.

The goal of this workshop is to provide a forum for researchers and practitioners to discuss issues related to these issues of fault-tolerant parallel and distributed systems. All aspects of design, theory, and realization of parallel and distributed systems are of interest.

Topics of interest include, but are not limited to:

- Fault-tolerant systems
- Fault-tolerant interconnection networks - Reconfigurable fault-tolerant parallel and distributed systems
- Fault-tolerant parallel and distributed real-time systems
- Fault-tolerant parallel programming
- Scalable fault-tolerant architectures and algorithms
- Fault injection in parallel and distributed systems
- Dependability evaluation of fault-tolerant parallel and distributed systems

The workshop is sponsored by the IEEE Computer Society Technical Committee on Parallel Processing. For more information, contact:

D.R. Avresky
Boston University
ECE Dept.
44 Cummington Street
Boston, MA 02215
Vox: (617)-353-9850
Fax: (617)-353-6440

or send email to

or kaeli@ece.neu.edu.

Workshop 13: All Day Saturday
Workshop Chair:
Afonso Ferreira, CNRS
LIP - ENS Lyon

Program Committee:

A. de Bruin, Erasmus University
J. Clausen, DIKU
P. Crescenzi, University La Sapienza
J. Eckstein, Rutgers University
M. Gengler, LIP ENS Lyon
V. Kumar, University of Minnesota
G. Megson, University of Reading
S. Migdalas, University of Linkoping
B. Monien, University of Paderborn
P. Panagiotopoulos, University of Thessaloniki
P. Pardalos, University of Florida
J. Rolim, University of Geneva
C. Roucairol, University of Versailles

Organizing Committee:

G. Kindervater (Chair), Erasmus University
P. Rebreyend, LIP ENS Lyon
S. Ubeda, LIP ENS Lyon

The solution of optimization problems in real world applications usually involves an enormous amount of work in which the use of parallel computers may be of great value. Through parallel computing, not only problems may be solved faster, but also large-sized problems may become tractable.

The SCOOP workshop is aimed to bring together experts in the field of parallel combinatorial computing. It will address both exact and approximate methods for scientific and practical hard optimization problems. The workshop will be the final meeting of the Human Capital and Mobility project SCOOP of the European Union.

The program will consist of a key-note lecture, and a number of short (25 minute) contributed presentations. It will address research in parallel combinatorial optimization, including the following topics:

- Approximation algorithms
- Branch and bound
- Continuous optimization
- Dynamic programming
- Financial applications
- Graph partitioning
- Industrial problems
- Libraries
- Load balancing
- Metaheuristics
- Network design
- Quadratic assignment problems
- Randomized algorithms
- Scheduling
- Tools
- Vehicle routing problems

The final version of the papers presented at the workshop will be considered for publication in a special issue of the electronic journal Parallel Algorithms and Architectures, published by International Thompson Publishers, to appear in December 1997. (http://www.thomson.com:8866/compscinet/compsci.html)

The workshop program and book of abstracts wi|l be available electronically after March 1, 1997.

For further information please browse our Web site (http://www.ens-lyon.fr/LIP/SCOOP) or contact:

Gerard Kindervater
Department of Computer Science
Erasmus University
P.O. BOX 1738
3000 DR Rotterdam
The Netherlands
Fax: + 31 10 4526177
Vox: + 31 10 4081316

Workshop 14: All Day Saturday
Workshop Co-Chairs:
Maurizio A. Bonuccelli, Universita di Pisa (Italy)
Imrich Chlamtac, Boston University

Program Committee:

O. Bukhres, Purdue University at Indianapolis
L. Cardelli, DEC
A. Dahbura, DEC
S. Das, University of North Texas
R. De Nicola, University of Florence, Italy
D. Ferrari, Universita Cattolica, Piacenza, Italy
B. Gavish, Vanderbilt University
M. Gerla, UCLA
Z.J. Haas, Cornell University
S. Hailes, University College, London, UK
P. Humblet, EURECOM, France
R. Jain, Bellcore
P. Kermani, IBM
B. Khasnabish, GTE
A. Krishna, IBM
S. Kutten, Technion, Israel
T. Leighton, MIT
J. Lin, N.C.T. University,Taiwan
D.P. Sieworek, Carnegie Mellon University
K. Sohraby, Bell Labs

Recent technological advances brought about the birth of a new field, called nomadic computing. Nomadic computing is concerned with the connection of portable (mobile) computers, and with the migration of software, from a home platform to a remote one. Due to its special features (uncertainty of location, repeated lack of connections, migration into different physical and logical environments while operating, among others) this new field brings a set of original problems. In spite of its very recent appearance, nomadic computing is emerging as one of the hottest topics both in research and industry.

This workshop is intended for people from academia and industry. Its main goal is to provide an informal forum for discussions on all aspects, tleoretical or practical, related to nomadic computing, with a special emphasis on the mobility and wireless aspects of networking. Topics of interest include:

- Routing in mobile networks
- Admission control
- Security and privacy
- Resource discovery
- Data management issues
- Mobile internetworking
- Energy saving resource management
- Languages for mobility
- Semantics of mobile processes
- Location management
- Medium access protocols
- Databases for nomadic computing
- Mobile-fixed networks interconnection
- Fault tolerance
- Operating systems support for nomadicity
- Service access
- Performance evaluation for nomadic computing

Authors are invited to submit extended abstracts (no more than 12 double spaced single sided pages using 12 point fonts) describing original unpublished material. Electronic submission is encouraged. In this case, send a cover email message indicating author(s), title, and email address of the corresponding author, followed by a separate message containing the paper in PS format (only this format will be accepted for electronic submission) to: bonucce@di.unipi.it.

For ordinary submission, please send 6 copies of the paper to:

Maurizio A. Bonuccelli
Dipartimento di Informatica
Universit‡ di Pisa
Corso Italia, 40
56125 PISA - ITALY

Selected papers will appear in the ACM/Baltzer Wireless Networks Journal. Important Dates:

Submission Deadline - January 15, 1997
Notification of Acceptance - February 15, 1997
Final Copy Due - March 7, 1997

All the information about the workshop can be found at the Web location: http://www.di.unipi.it/~bonucce/WoNoCo.html



Swissair has been appointed official carrier for IPPS '97. To book the special conference fare, please contact your nearest Swissair office or, in the US and UK, the appointed travel agent listed below. To obtain a discount fare, give the ticket agent the code SR IDS G CGRF and refer to the event as the IEEE International Parallel Processing Symposium.

North American Participants:

The official Swissair designated airline ticketing agency is
Conferences International, Inc.
25 Huntington Avenue, Suite 607
Boston, MA 02116-5713
Tel 617-266-5800 Fax 266-5886
Toll Free in US & Canada

United Kingdom Participants:

For full details of special inclusive travel arrangements, contact
Karen Hammond
Karin Rommel Travel Plc.
17 St. George Street
Hanover Square
London W1R 9DE
Tel 171-499-7611 Fax 493-0326

Participants from other countries should contact their nearest Swissair office. If other arrangements including ground and rail are required, contact your travel agent for assistance.


In 1997, IPPS will be held on the campus of the University of Geneva. Two hotels (listed below and on the tear out registration form at middle of program) have reserved a block of rooms at special IPPS rates. The discounted rates offered by the Noga Hilton Geneve, a 5 star establishment, are an especially good value.

Prices for both hotels are guaranteed until the specified dates but to assure your choice, register early. Both hotels are within 10-15 minutes walking distance from the University of Geneva campus.

To reserve accommodations, contact the selected hotel below by the deadline listed. For both hotels, furnish the following information:

* Name - Affiliation - Address
* Phone & Fax
* Accommodations requested (Single/Double) * Number in party (Ages of children)
* Arrival & Departure Date/Time
* Credit Card Guarantee (Most are accepted)

CONTACT Mme Marianne Mouret
TEL +41 22 908-9131
FAX +41 22 908-9090
SINGLE 230 Sfrs
DOUBLE 280 Sfrs
CONTACT Monsieur J.Cl. Bemet
TEL +41 22 731-7200
FAX +41 22 738-9080
SINGLE 165 Sfrs
DOUBLE 205 Sfrs

For information on other accommodations and tour packages, you or your travel agent may contact the GENEVA TOURIST OFFICE for information. Call +41 22 310-5031 or fax +41 22 311-8965 or write PO Box 5230, CH-1211 Geneva 11, Switzerland.


From the airport:
A taxi from the airport to either hotel will cost about 30Sfr. Alternatively you may take the train from the airport to the main train station - a 5 minute walk from the hotels. The ride will cost around 5Sfr and will take 10 minutes. Purchase a ticket before boarding the train.

From hotels to the University:
It is a 10 minute walk. You may cross the river via either the Pont des Bergues or Pont de la Machine and then take Rue de la Corraterie to Place Neuve. The University is located at the park called Promenade des Bastions.

By public transportation, take tramway number 13 from the main train station to the fourth stop (called Plainpalais). From there walk by rue du Grand Conseil until you reach the Promenade des Bastions.

Note: When using any local transportation, you need to purchase a ticket in advance at the machine located at the bus stop; the cost is 2.20Sfr. This ticket is valid for one hour and you may take as many connections as you want. Also note that the machine does not give change, and if you enter a bus without a valid transportation ticket you risk being required to pay a fine of about 100Sfr and a visit to the police station.


Geneva is situated along the banks of Lac L'man and Le Rhine. The lake showcases the plumed fountain Jet d'Eau, and various districts of Geneva are connected by bridges across the waterways. The University of Geneva where IPPS '97 will convene is located on the `Left Bank' off Place Neuve and along the Promenade des Bastions near the Old Town section of Geneva.

The two IPPS '97 designated hotels are located lakeside - on the `Right Bank' - and are within walking distance of the University campus. It is a 10-15 minute walk which crosses through `Old Town'. Also, there is regular bus service running to the University, so IPPS participants may come and go throughout the day.

Geneva is a city of water parks and gardens and welcoming walkways which encourage exploration of the historical sites, museums, and international business and shopping districts. The University of Geneva is located near `Old Town' an area dotted with sidewalk cafes, student life, and building antiquities dating back to the 5th century.

Geneva is a crossroads situated in the heart of Europe and linked to the world by a vast network of motorways, airlines and railways. For those planning to attend IPPS '97 in Geneva, it is an excellent opportunity to organize short trips into the countryside of charming villages and vineyards. Tours to please all ages and interests are available including afternoon train excursions, shopping cruises on Lake Geneva and The Rhone, and bus and cablecar trips in the Alps.

For some, the most inviting attraction will be skiing. In early April, the snow fields less than an hour away are still open, so serious skiers should plan accordingly!


The climate in early April should be very pleasant with brisk evenings and breezes off the Lake. There may be showers but we can also expect sunny days. Comfortable `layers'(e.g., sweaters and raincoats) and footwear are recommended.


A valid passport is required for entry into Switzerland. Some nationals may also require a visa for Switzerland, and if you plan to visit France one may be required there. Please check with your travel agent or consulate to determine whether a visa will be required.


At IPPS '97, luncheon will be served on the University campus to all registrants on all five days and refreshments will be available during breaks. On Friday evening, there will be a dinner cruise on Lake Geneva; tickets for spouse, guests, and children may be purchased at the time you register. (Please be sure to indicate on your registration form whether you prefer vegetarian meals.)

At other times, participants will have a broad choice of dining options offering international and gourmet fare all within walking distance of accommodations and many along the shores of Lake Geneva. The traditional and most popular dishes among the local population are cheese fondue and raclette, delicious local wines, and lake perch.


The unit of currency is the Swiss franc. Notes are issued in denominations of 10, 20, 50, 100, 500, and 1,000. Coins are issued in denominations of 5, 10, and 20 centimes, and .5, 1, 2, and 5 Swiss francs. Most hotels, large stores, restaurants, and petrol stations accept all major credit cards (American Express, MasterCard, Visa, Diners Club, Eurocard).


The national languages of Switzerland are German (65%), French (18%), and Italian (10%). Many Swiss, especially those connected with travel and service industries, also speak English. In Geneva, French is the predominant language spoken.