LEA
Fakultät für Informatik der Technischen Universität München
Lehrstuhl für Effiziente Algorithmen
Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München

4th PASA Workshop
Parallel Systems and Algorithms

Forschungszentrum Jülich
Zentralinstitut für Angewandte Mathematik
April 10-12, 1996

in cooperation with:
GI-Fachgruppe 0.1.3 - Parallele und verteilte Algorithmen
GI-Fachgruppe 3.1.2 - Parallel-Algorithmen, -Rechnerstrukturen und -Systemsoftware

About the Workshop

Scope

The PASA workshop series has the goal to build a bridge between theory and practice in the area of parallel systems and algorithms. In this context practical problems which require theoretical investigations as well as the applicability of theoretical approaches and results to practice will be discussed.
An important aspect is communication and exchange of experience between various groups which work in the area of parallel computing, e.g. in computer science, electrical engineering, physics or mathematics.

Topics of interest include:

* parallel architectures
* interconnection networks
* fault-tolerant parallel computers
* models for parallel computing
* performance evaluation of parallel systems
* tools for parallel programming
* parallel real-time systems
* programming environments for parallel computers
* parallel and distributed algorithms
* parallel programming languages.

Programme Committee

* M. Dal Cin (Erlangen-Nürnberg)
* W. Händler (Erlangen-Nürnberg)*
* F. Hoßfeld (Jülich)*
* W. Juling (Rostock)
* W. Karl (München)
* E. Maehle (Lübeck)*
* E. Mayr (München)*
* F. Meyer auf der Heide (Paderborn)*
* W. Paul (Saarbrücken)
* U. Schwiegelshohn (Dortmund)
* PASA Steering Committee

Programme

Wednesday, 10 April 1996

08:15 Bus from the Hotel Ibis
09:00 Registration
09:40 Welcome Address and Opening
Invited Lecture (Chair: E. Maehle)
10:00 A. Bode; University of Munich, Germany
Runtime-Oriented Design Tools: A Contribution to the Standardization of Development Environments for Parallel and Distributed Programs
11:00 Coffee
Session 1: Scheduling (Chair: E. Mayr)
11:30 T. Erlebach; K. Jansen; University of Munich, Germany
T1: Scheduling of Virtual Connections in Fast Networks
12:05 F. Seredynski; University of Warsaw, Poland
T2: Parallel and Distributed Algorithms of Dynamic Mapping and Scheduling
12:40 Lunch
Session 2: Routing (Chair: A. Bode)
14:15 T. Seifert, E. Speckenmeyer; University of Cologne, Germany
T3: Optimal Oblivious Permutation Routing in Small Hypercubes
14:50 A. C. Döring, G. Lustig, W. Obelöer; Medical University of Lübeck, Germany
T4: The Impact of Routing Decision Time on Network Latency
15:25 H. Song; KAIST, Korea; S.B. Eun; Han Nam University, Korea; H.Yoon; KAIST, Korea;
T5: A Static Wormhole Routing in Mesh-Connected Multicomputers, Exploiting Communication Characteristics of Applications
16:00 Coffee
Session 3: Distributed Systems (Chair: W. Händler)
16:30 R. Baldoni, Y. Manabe, M. Raynal, S. Aoyagi; University of Rome, Italy
T6: Quorum-based Solutions to the h-out of-k Mutual Exclusion Problem in Distributed Systems
17:05 M. Makhaniok, R. Männer; University of Mannheim, Germany
T7: Duration of Asynchronous Operations in Distributed Systems
18:00 Reception and Dinner
20:30 Bus to the Hotel Ibis

Thursday, 11 April 1996

8:45 Bus from the Hotel Ibis
Invited Lecture (Chair: U. Schwiegelshohn)
9:30 S. Müller; University of Saarland, Germany
Complexity and Correctness of Computer Architectures
Session 4: Architecture (Chair: U. Schwiegelshohn)
10:30 U. Sigmund, T. Ungerer; University of Karlsruhe, Germany
T8: Evaluating a Multithreaded Superscalar Microprocessor versus a Multiprocessor Chip
11:05 Coffee
Session 5: Scheduling and Load Balancing (Chair: W. Nagel)
11:30 M. Leberecht; University of Munich, Germany
T9: A Concept for a Multithreaded Scheduling Environment
12:05 M. Böhm, E. Speckenmeyer; University of Cologne, Germany
T10: Precomputing based Load Balancing
12:40 Lunch
Session 6: Interconnection Networks (Chair: F. Hoßfeld)
14:15 V. Heun, E. W. Mayr; University of Munich, Germany
T11: Optimal Dynamic Edge-Disjoint Embeddings of Complete Binary Trees into Hypercubes
14:50 V. Auletta, A. Negro, V. Scarano; University of Salerno, Italy
T12: Efficient Token Clustering on Hypercubes
15:25 W. Zimmermann, W. Löwe; University of Karlsruhe, Germany
T13: Summation and Prefix Summation on LogP-Meshes
16:00 Coffee
Session 7: Dependence Graphs (Chair: F. Meyer auf der Heide)
16:30 W. Achtziger, K.-H. Zimmermann; University of Karlsruhe, Germany
T14: A Branching Linear Programming Approach for the Mapping of Systems of n-Dimensional Affine Recurrences onto k-Dimensional Systolic Arrays
17:05 W. Amme, E. Zehendner; University of Jena, Germany T15: A/D Graphs - A Data Structure for Data Dependence Analysis in Programs with Pointers
17:50 Bus to Aachen

Friday, 12 April 1996

08:45 Bus from the Hotel Ibis
Invited Lecture (Chair: W. Karl)
9:30 W. Oed, Cray Research GmbH
Are MPP Systems Mature for Production Environments?
10:30 Coffee
Session 8: Traffic Systems (Chair: E. Mayr)
11:00 E. Duschnig, R. Weiss; University of Graz, Austria
T16: Design of a Distributed Fault-Tolerant Computer Architecture Applied to the Traffic Control System IVMS
11:35 M. Rickert, P. Wagner, C. Gawron; University of Cologne, Germany
T17: Real-Time Traffic Simulation of the German Autobahn Network
12:10 Conclusion
12:30 Lunch
13:55 Transfer to
* the Düren Railway Station
* the Düsseldorf Airport
* and the Hotel Ibis

General Information

Venue

The 4th PASA Workshop Parallel Systems and Algorithms will be held in the Forschungszentrum Jülich, Germany, from 10 to 12 April 1996.

Oral Presentations

The oral presentations will be given in the lecture room of the Central Institute for Applied Mathematics. Facilities will include overhead projectors; speakers are reminded of the importance of using only clear and high quality transparencies. Video display device can be provided if requested.

Language

The official language of the workshop is English.

Proceedings

All accepted and presented papers will be published. Authors are kindly requested to submit camera-ready manuscripts until 1 May 1996. The maximum length of papers will be limited to 10 pages.

Social Programme

On Wednesday evening a reception and a dinner will be held by invitation of the Board of Directors of the Forschungszentrum Jülich at the Waldcasino.

Registration and Conference Fee

The registration fees are given below and include participation in the scientific programme, one copy of the proceedings, coffee and refreshments, all luncheons, and the social programme.
Participants DM 230
Students* DM 100
* Only for full-time students. Please attach a confirmation by the Head ot the Department. Proceedings are not included.

Payment should be made in Deutsche Mark by one of the following alternatives:
* Cheque made payable to
Forschungszentrum Jülich,
Conference Service,
D-52425 Jülich, Germany
Reference: PASA Workshop
* Bank transfer to
Kreissparkasse Düren,
D-52428 Jülich,
account No. 6569
* national: banking code 395 501 10
* international: swift code SDUEDE 33

* or via Westdeutsche Landesbank, Düsseldorf,
swift code WELADE DD
in favour of Forschungszentrum Jülich GmbH,
Conference Service,
D-52425 Jülich, Germany
Reference: PASA Workshop
It is absolutely necessary to indicate the participant's name on the remittance or cheque.

Accommodation

Participants of the workshop are recommended to stay in Hotel Ibis am Marschiertor in Aachen.

Hotel Ibis am Marschiertor

Comfortable hotel. All rooms with shower, WC, TV and phone. Situated in the centre of Aachen, close to the Central Railway Station. 10 minutes walk to the city centre.
104 rooms, single: DM 103; double: DM 118. Free car park.
The given rates include breakfast.

Double occupancy

Sharing a double room in Hotel Ibis at a rate of DM 59 per person and night is the recommended accommodation at a moderate price in downtown Aachen. If not specified, room mates will be assigned by the conference secretariat.

The local organization has appointed the Aachen Tourist Office to handle the hotel reservations.

Participants will be individually notified (by letter). If for any reason you have to cancel your reservation please notify the hotel directly. <[> In order to take advantage of the given group rates you must register until 4 April 1996.

How to Get to Aachen

The city of Aachen is located near the Dutch and Belgian borders, about 70km west of Cologne. Aachen can be reached
* by air
* via Düsseldorf airport. The suggested and most convenient route is the Airport Express to Aachen leaving every 90 minutes from the central bus terminal (platform 3). (Appr. 1 hour).
* via Cologne airport. There is an airport bus to Cologne Central Railway Station and frequent trains leave from there to Aachen. (Approx. 2hours).
* by train
* via frequent direct express train services from Cologne to the Aachen Central Railway Station.
* by car
* via Autobahn A4, A44, and A61

Limousine Service to the Forschungszentrum

On meeting days a limousine can be booked from Düsseldorf Airport The driver will pick you up at the official meeting point. (DM 30 per person).

Düren Railway Station

The driver will pick you up outside the main entrance. (DM 15 per person). For cancellation give direct notice to workshop secretary.

Transportation at the End of the Workshop

At the end of the workshop on Friday, transportation will be arranged to Düren Railway Station, Düsseldorf airport and Aachen. You will be able to reach IC-trains leaving Cologne Central Railway Station after 15:15h and planes leaving Düsseldorf Airport after 16:00h. Individual transportation will be arranged by the workshop secretary upon request to the Düren Railway Station and the Düsseldorf airport at any time and at cost prices.

Local Organization

F. Hoßfeld and H. Burg
Forschungszentrum Jülich (KFA)
Zentralinstitut für Angewandte Mathematik
D-52425 Jülich, Germany

Phone: ++49 2461 61-3175
Fax: ++49 2461 61-6656
E-mail: h.burg@kfa-juelich.de

Workshop Secretariat

Ms Andrea Deußen and Ms Elke Bielitza
Forschungszentrum Jülich GmbH
Conference Service
D-52425 Jülich, Germany

Phone: ++49 2461 61-3833
Fax: ++49 2461 61-4666

Important Dates

Please note, new registration deadline
4 April 1996 Deadline for registration and hotel reservation
10 - 12 April 1996 PASA Workshop
Volker Heun, 1996-03-06, 1996-03-26
Tobias Knopff, 1997-04-14