HEINZ
NIXDORF
INSTITUT
University of Paderborn
Theoretical Computer Science
AG Meyer auf der Heide
Dr. Dieter Kratsch
(Friedrich-Schiller-Universität Jena)
-
Mariano Herrero Zahinos
-
Dr. Nabanita Das
(Indian Statistical Institute, India)
- Stay:
August - October, 1997
- Guest of AG Monien
- Email:
ndas@uni-paderborn.de
- Seminar:
August 12, 1997, (Tuesday), 14:15, F2.419
Oberseminar AG Monien
Title:
A Generalized Multistage Interconnection Network
-
Anna Gambin
(Warsaw University, Poland)
-
Thomas Plachetka
(Comenius University, Bratislava, Slovakia)
-
Dr. Ben Juurlink
-
Dr. Micah Adler
-
Gemma Durana de la Hoz
(Spain)
-
Dr. Paul Fischer
(Universität Dortmund)
-
Prof. Bruce M. Maggs
(School of Computer Science, Carnegie Mellon University, USA)
-
Prof. Bogdan S. Chlebus
(Warsaw University, Poland)
-
Alicia San Millan Perez
(Bilbao, Spain)
-
Marcin Kik
(Institute of Compuer Science, University of Wroclaw, Poland)
-
Prof. Robert Cypher
(Johns Hopkins University, USA)
- Stay: May 20 - July 9, 1995
- Guest of AG Meyer auf der Heide
-
Przemyslawa Kanarek
(University of Wroclaw, Poland)
-
Prof. Endre Szemerédi
(Rutgers University, USA)
- Stay: July 1, 1994 - July 20, 1995
- Guest of AG Meyer auf der Heide
-
Dr. Krzysztof Lorys
(University of Wroclaw, Poland)
- Stay: June 15 - July 31, 1995
- Guest of AG Meyer auf der Heide
-
Prof. C. Greg Plaxton
(University of Texas, USA)
- Stay: June 1 - July 31, 1995
- Guest of AG Meyer auf der Heide
-
Johannes Gehrke
(University of Texas, USA)
- Stay: June 12 - July 31, 1995
- Guest of AG Meyer auf der Heide
-
Rajmohan Rajaraman
(University of Texas, USA)
- Stay: June 6 - July 31, 1995
- Guest of AG Meyer auf der Heide
-
Prof. Dr. George E. Collins
(University of Delaware)
- Stay: August 1 - August 29, 1999
- Visiting AG Monien
- Contact during his visit in Paderborn:
- Room F2.126, Tel 6626, Email: collins@cis.udel.edu
- via Dr. Werner Krandick
(F2.201, Tel: 6650,
Email: krandick@upb.de)
-
Dr. Micah Adler
(University of Toronto, Canada)
- Stay: June 20 - June 27, 1999
- Visiting AG Meyer auf der Heide
- Contact during his visit in Paderborn:
- Seminar: June 23, 1999 (Wednesday), 11:15, F1.110
(Oberseminar des SFB (ICAMP))
Title:
Protocols for Asymmetric Communication Channels
-
Prof. Faith Fich
(University of Toronto, Canada)
- Stay: June 20 - June 27, 1999
- Contact during his visit in Paderborn
- Seminar: June 23, 1999 (Wednesday) 14:30, F1.110
(Oberseminar AG Meyer auf der Heide)
Title:
The Complexity of End-to-End Communication
-
Ladislav Stacho
(Slovak Academy of Sciences, Bratislava, Slovakia)
- Stay: April 26 - 30, 1999
- Contact during his visit in Paderborn
- Seminar: April 28, 1999 (Wednesday) 14:30, F1.110
Title:
Results and Problems on Wavelength Allocations in All-optical Networks
Abstract
-
Dr. Nikita D. Vvededenskaya
(Institute of Information Transmission Problems of Russian Academy of Science, Moscow, Russia)
- Stay: April 25 - May 1, 1999
- Contact during her visit in Paderborn
- Seminar: TBA
-
Prof. Angelika Steger
(Fakultät für Informatik der Technischen Universität München)
- Stay: April 11-17, 1999
- Contact during her visit in Paderborn
- Seminar: April 13, 1999 (Tuesday), 17:45, D 2
(Kolloquium für Mathematik und Informatik)
Title:
Asymptotic Enumeration, Global Structure, and Constrained Evolution
Abstract
-
Prof. Bruce M. Maggs
(School of Computer Science, Carnegie Mellon University, USA)
- Stay: December 13 - 21, 1998
(tentatively)
- Contact during his visit in Paderborn
-
Johanne Cohen
(Universite Paris Sud, France)
- Stay: November 9 - 11, 1998
- Contact during her visit in Paderborn
- Raum: F1.203
- Telefon: 6451 (local)
- Seminar: November 11, 1998 (Wednesday), 14:30, F1.110
(Oberseminar AG Meyer auf der Heide)
Title:
Multicasting and Broadcasting in the Tree
Abstract
-
Prof. Martin Dyer
(School of Computer Studies, Univeristy of Leeds, U.K.)
- Stay: November 3 - 6, 1998
- Email:
dyer@scs.leeds.ac.uk
- Contact during his visit in Paderborn
- Seminar: November 3, 1998 (Tuesday), 17:45, D 2
(Kolloquium für Mathematik und Informatik)
Title:
Counting Independent Sets in Graphs
Abstract
-
Prof. Andrzej Lingas
(Lund University, Sweden)
- Stay: October 24 - 27, 1998
- Email:
andrzej@dna.lth.se
- Contact during his visit in Paderborn
-
Prof. Jean-Pierre Tillich
(Universite Paris-Sud- Centre d'Orsay-
Laboratoire de Recherche en informatique,
Batiment 490, 91405 ORSAY Cedex)
- Stay:
November 30 - December 6, 1997
- Guest of AG Monien
-
Prof. Hanno Lefman
(Lehrstuhl Informatik II, Universität Dortmund)
- Stay:
November 21, 1997
- Guest of AG Meyer auf der Heide
- Email:
lefmann@ls2.informatik.uni-dortmund.de
- Seminar:
November 21, 1997, (Friday), 11:00, F1.110
Theorie-Seminar der Informatik
Title:
Approximation großer unabhängiger Mengen
-
Prof. Bogdan S. Chlebus
(University of Warsaw, Poland)
- Stay:
September 15 - 23, 1997
- Guest of AG Meyer auf der Heide
- Email:
chlebus@mimuw.edu.pl
- Seminar:
September 23, 1997, (Tuesday), 11:00, F1.110
Oberseminar AG Meyer auf der Heide
Title:
Performing Tasks on Restartable
Message-Passing Processors
Abstract
-
Luca Becchetti
(Dipartimento di Informatica e Sistemistica, Rom)
- Guest of AG Monien
- Stay: September 1997
- Seminar :
September 17, 1997, (Wednesday), 11:00,
F2 419
Title:
On the complexity of the Virtual Path Layout problem in ATM networks
Abstract of the talk
-
Hubertus Franke
(IBM T.J.Watson Research Center)
- Guest of C-LAB
- Stay: September 1997
- Seminar :
September 5, 1997, (Friday), 14:00,
Raum Beethoven (FU 116), C-LAB
Hubertus Franke will talk about work
he and some colleagues have done in
the area of Evolutionary Design of Complex
Systems at Vanderbilt University
Abstract of the talk
-
Prof. L. H. Harper
(University of California at Riverside)
- Guest of AG Monien
- Stay: September 1997
- Seminar :
September 3, 1997, (Wednesday), 14:00,
F2 419
Title:
On an Isoperimetric Problem for
Hamming Graphs
Abstract of the talk
-
Prof. Sajal K. Das
(Center for Research in Parallel and Distributed Computing,
Department of Computer Sciences,
University of North Texas, Denton, TX 76203)
- Guest of AG Monien
- Stay: August 1997
- Seminar :
August 25, 1997, (Monday), 16:15
F2.419
Title:
Conflict-Free Access to Data Structures
in Parallel Memory Systems
Abstract of the talk
-
Doc. Lenka Motyckova
(Masaryk University, Czech Republic)
- Guest of C-LAB
- Stay: August 1997
- Seminar (jointly with D. Carr):
August 25, 1997, (Monday), 14:00,
Raum Beethoven (FU 116), C-LAB
Title:
An Overview of Reliable Multicasting
-
Dr. David Carr
(Lulea University of Technology, Sweden)
- Guest of C-LAB
- Stay: August 1997
- Seminar (jointly with L. Motyckova):
August 25, 1997, (Monday), 14:00,
Raum Beethoven (FU 116), C-LAB
Title:
An Overview of Reliable Multicasting
-
Dr. Marek Piotrow
(Institute of Computer Science, University of Wroclaw, Poland)
-
Prof. Arnold L. Rosenberg
(University of Massachusetts, Amherst MA, USA)
-
Prof.
Ramesh K. Sitaraman
(University of Massachusetts, Amherst MA, USA)
-
Prof. Bruce M. Maggs
(School of Computer Science, Carnegie Mellon University, USA)
-
Prof. Michal Karonski
(Adam Mickiewicz University, Poznan, Poland)
- Stay:
June 2 - June 6, 1997
- Guest of AG Meyer auf der Heide
- Email:
karonski@math.amu.edu.pl
- Seminar:
June 11, 1997, (Wednesday), 14:00, F1.110
Oberseminar AG Meyer auf der Heide
Title:
Matchings in Random Graphs
-
Prof. Andrzej Pelc
(University of Quebec, Hull, Canada)
- Stay:
March 2 - March 4, 1997
- Guest of AG Meyer auf der Heide
- Office: F1.125
- Tel: 6433
- Seminar:
March 3, 1997, (Monday), 11:15, F1.110
Oberseminar AG Meyer auf der Heide
Title:
Broadcasting in Unlabeled Networks
Abstract
-
Prof. Dr. R. Biehler
(Universität Bielefeld)
- Stay: December 1996
- Seminar: December 17, 17:45,
Hörsaal D2
(Kolloquium des FB Mathematik/Informatik)
Vernetzung von funktionalem und stochastischem
Denken im Mathematikunterricht
-
Volker Schnecke
(Universität Osnabrueck)
- Stay: December 1996
- Seminar: December 5, 14:15, F0.530
(Kolloquium der Parallelverarbeitung)
Genetische Algorithmen für
Plazierungsprobleme mit Randbedingungen
-
Prof. Dr. A. Valette
(Universite de Neu Chatel)
- Stay: December 1996
- Seminar: December 4, 17:45,
Hörsaal D2
(Kolloquium des FB Mathematik/Informatik)
Ramanujan Graphs and Applications
-
Prof. G. Seregin
(V.A.Steklov Mathematical Institute, St. Petersburg, Russia)
- Stay: November 1996
- Seminar: November 29, 13:00, D1.303
(Sonderforschungsbereiches
"Massive Parallelitaet")
On two dimensional flows of generalized
newtonian fluids
-
Dr. Geir Horn
(SINTEF Electronics and Cybernetics in Norway)
- Stay: November 1996
- Seminar: November 28, 14:00, F0.530
(Kolloquium der Parallelverarbeitung)
When the Bus departed commenced the battle of
the Interconnects - what to be seen when
the fog lifts?
-
Dr. M. Schönert
(RWTH Aachen)
- Stay: November 1996
- Seminar: November 27, 16:00, N3.206
(MuPAD-Seminar)
Typisierung in der Computeralgebra
-
Panagiota Fatourou
(Computer Technology Institute, Patras, Greece)
- Stay: November 1996
- Seminar: November 27, 11:15, F1.110
(I!CAMP - Oberseminar)
Scheduling k-strict Multithreaded Computations
-
Alexander Sapozhenko
(Moscow State University, Russia)
- Stay: November 12- November 14, 1996
- Guest of AG Monien
- Seminar: November 13, 14:00, F2.211
On a Problem of Dedekind: the number of monotone Boolean functions
-
Jean-Pierre Tillich
(Universität Caen, France)
- Stay: November 7 - November 13, 1996
- Guest of AG Monien
- Seminar: November 8, 14:00, F1.110
On Spectral Graph Partioning Methods
-
Michele Flammini
(Universitaet L'Aquila)
- Stay: November 4 - November 9, 1996
- Guest of AG Meyer auf der Heide
- Seminar: November 6, 14:00, F2.211
Acyclic Orientations for Deadlock Prevention in Usual Networks
-
Dr. Jop Sibeyn
(Max-Planck-Institut für Informatik, Saarbrücken)
-
Przemyslawa Kanarek
(Institute of Compuer Science, University of Wroclaw, Poland)
-
Micah Adler
(University of California at Berkeley, USA)
- Stay:
June 27 - June 28, 1996
- Seminar:
June 28, 1996 (Friday), 11:00, F0.231
(Theorie-Seminar der Informatik)
Title:
New Coding Techniques for Improved Bandwidth Utilization
Abstract
-
Dr.
Salvatore Orlando
(Università Ca' Foscari di Venezia, Dipart. di Matematica Appl. e Informatica, Corso di Laurea in Informatica)
- Stay:
June 12 - July 2, 1996
- Seminar:
TBA
Title:
A Template for Non-uniform Parallel Loops Based on Dynamic Scheduling and Prefetching Techniques
Abstract
-
Dr.
Shiva Chaudhuri
(Max-Planck-Institut für Informatik, Saarbrücken)
- Stay:
May 5 - May 12, 1996
- Seminar:
May 10, 1996 (Friday), 11:00, F1.110
(Theorie-Seminar der Informatik)
Title:
Deterministic Restrictions in Circuit Complexity
Abstract
-
Prof. Martin Dyer
(School of Computer Studies, Univeristy of Leeds, U.K.)
- Stay: April 21 - April 26, 1996
- Seminar: April 24, 1996 (Wednesday), 14:00, F1.110
(Oberseminar, AG Meyer auf der Heide)
Title:
A New Approach to Generating a Random Point in a Convex Body
Abstract
-
Prof.
Frank Dehne
(School of Computer Science, Carleton University, Ottawa)
- Stay: February 22-23, 1996
- Seminar:
February 23, 1996, (Friday), 11:00, F1.110
(Theorie-Seminar der Informatik)
Title:
From Parallel Time Complexity To Parallel Time
Abstract
-
Dr. Leszek Gasieniec
(Max-Planck-Institut für Informatik, Saarbrücken)
- Stay:
February 5 - February 16, 1996
- Seminar:
February 9, 1996 (Friday), 11:00, F1.110
(Theorie-Seminar der Informatik)
Title:
Broadcasting with linearly bounded transmission faults
Abstract
-
Guests comming on the
Theory Day at the University of Paderborn, Thursday, February 1, 1996
Prof. Rainer Kemp
- Prof. Jiri Matousek
- Prof. Alberto Marchetti-Spaccamela
- Prof. Paul Spirakis
- Prof. Rusins Freivalds
- Prof. Paul Vitanyi
-
Anna Gambin
(Universität Dortmund und Universität Warschau)
- Stay: January 31 - February 1, 1996
- Seminar:
January 31, 1996, (Wednesday), 14:15, F1.110
(Oberseminar, AG Meyer auf der Heide)
Title:
Shared-Memory Simulations on a Faulty-Memory DMM
Abstract
-
Dr Andrea Pietracaprina
(Universit` di Padova, Dipartimento di Matematica Pura e Applicata)
- Stay: December 4 - December 16, 1995
- Seminar:
December 13, 1995, 14:15, F1.110
(Oberseminar, AG Meyer auf der Heide)
Title:
Fast Deterministic Backtrack Search
Abstract
- Research interest
-
Bernd Gaertner
(Freie Universität Berlin)
- Stay: November 22, 1995
- Seminar:
November 22, 1995, 14:15, F1.110
(Oberseminar, AG Meyer auf der Heide)
Title:
Randomisierte Optimierung. Die Simplex-Methode in neuem Gewand
Abstract
-
Jürgen Bierbrauer
(Department of Mathematical Sciences, Michigan
Technological University, Houghton)
- Stay: November 8 - November 9, 1995
- Seminar:
November 8, 1995, 14:15, F1.110
(Oberseminar, AG Meyer auf der Heide)
Title:
Universal hashing und fehlerkorrigierende Codes
-
Prof. Dr. Martin Dietzfelbinger
(Universität Dortmund)
- Stay: October 27, 1995
- Seminar:
October 27, 1995, 14:15, F2.419
(Theorie-Seminar der Informatik)
Title:
Universal hashing via integer
arithmetic without primes
Abstract of the talk
-
Dr. Christine Rüb
(Max-Planck-Institut für Informatik, Saarbrücken)
- Stay:
October 23 - October 27, 1995
- Seminar:
October 25, 1995, 14:15, F1.110
(Oberseminar, AG Meyer auf der Heide)
Title:
Über die mittlere Laufzeit
paralleler Sortierverfahren
-
Suleyman Cenk Sahinalp
(UMIACS, University of Maryland)
- Stay: April 24, 1995
- Seminar:
April 24, 1995
(Seminar of Graduiertenkolleg)
Title:
Locally Consistent Parsing for
High Performance Data Compression
Abstract of the talk
-
Alf-Christian Achilles
(Universität Karlsruhe)
- Stay: April 3 - April 5, 1995
- Seminar:
April 4, 1995
(Oberseminar, AG Meyer auf der Heide)
Title:
Effiziente Emulationen von Verbindungsnetzwerken
Abstract of the talk
- Research interest
-
Informatik '99,
Informatik überwindet Grenzen,
29. Jahrestagung der
Gesellschaft
für Informatik.
October 5 - 9, 1999, Paderborn, Germany.
The 29th Annual National Conference of
the German
Computer Science Association (GI)
-
International Workshop on Communication and Data Management
in Large Networks, October 5, 1999, Paderborn, Germany.
(Organized as part of
Informatik '99)
-
International Conference on the History of Computing,
August 14 - 16, 1998, Paderborn, Germany.
(Organized by the Heinz Nixdorf Museums Forum, Paderborn)
-
First MuPAD User Workshop,
September, 22-23, 1997, Paderborn, Germany.
-
4th International Symposium on Solving Irregularly Structured
Problems in Parallel (IRREGULAR '97),
June 11 - 13, 1997, Paderborn, Germany.
-
23rd International Colloquium on Automata, Languages,
and Programming (ICALP '96),
July 8 - 12, 1996, Paderborn, Germany
-
Theory Day: Parallel Algorithms and Complexity,
June 22, 1995, Paderborn, Germany
-
Paderborn Spring School 1995 on Efficient Use
of Parallel Systems,
April 25 - 28, 1995, Paderborn, Germany
Research interests of
Alf-Christian Achilles
Sein Arbeitsgebiet sind Netzwerk-Emulationen, d.h., er untersucht
Fragestellunge, wie z.B.: ``Wie schnell kann das Netzwerk A das
Netzwerk B simulieren?''. Er betrachtet dabei den Ansatz, bei dem
einzelne Gastprozessoren auch mehrfach simuliert werden koennen.
Eines seiner schoenen Resultate besteht darin, dass das Mesh of Trees
der Groesse N das quadratische 2D-Gitter aus N Prozessoren mit
konstantem Zeitverlust simulieren kann. Mit normalen Einbettungen ist
das nicht moeglich.
Abstract of the talk:
Alf-Christian Achilles
Effiziente Emulationen von Verbindungsnetzwerken
Die Leistungsfähigkeit eines Parallelrechners hängt im
Wesentlichen von dem gewählten Verbindungsnetzwerk ab, das die
einzelnen Prozessoren verbindet. Bei der Betrachtung von Klassen
von Verbindungsnetzwerken stellt sich die Frage, wie effizient
das Verhalten eines Netzwerks auf einem anderen Netzwerk
nachgebildet (emuliert) werden kann. Diese Frage ist eng mit dem
Problem der Abbildung von Algorithmen auf Parallelrechner
verbunden, und solche Emulationen ermöglichen einen allgemeinen,
problemunabhängigen Vergleich zwischen Netzwerken.
In diesem Vortrag wird die optimale Emulation von 2D-Gittern auf
Mesh-of-Trees-Netzwerken mit einer konstanten Verzögerung vor-
gestellt, obwohl jede Einbettung eine Dilation von Omega(log N)
hat. Aus dieser Emulation ergibt sich auch erstmals ein
optimaler Sortieralgorithmus für das Mesh-of-Trees-Netzwerk, der
nur O(sqrt(N)) Schritte benötigt.
Weiterhin werden Emulationen von planaren Graphen mit konstantem
Verzweigungsgrad auf 2D-Gittern mit unterschiedlicher Last
beschrieben, deren Effizienz teils optimal ist, teils sehr nahe
am Optimum liegt.
Abstract of the talk:
Suleyman Cenk Sahinalp
Locally Consistent Parsing for High Performance Data Compression
The size of the data involved in a wide range of
applications is growing rapidly.
To name a few, multimedia and genealogic applications
depend on massive data processing. In this respect, the need for
efficient data compression has become more critical than ever.
We introduce a practical serial universal compression algorithm that modifies
the Lempel-Ziv adaptive dictionary method, which is efficiently
parallelizable as well. It is based on a new parsing
technique that we call ``locally consistent parsing'', which considerably
reduces the size of the dictionary used for compression. The initial
implementation results show some
significant improvement over the Lempel-Ziv-Welch (LZW) implementations and
the Unix kernel ``compress''.
Abstract of the talk:
Prof. Dr. Martin Dietzfelbinger
Universal hashing via integer arithmetic without primes
Hash functions map ``keys'' from some finite ``universe'' to a
``range'' (usually the indices of a hash table). Universal hash-
ing is a method of generating hash functions that behave well on
the average or with high probability by choosing them at random
from a suitable set of functions. A multitude of such construc-
tions (``universal hash classes'') are known. Invariably, the
stronger ones among them involve arithmetic in some finite field
(given as arithmetic modulo a suitable prime number or polynomial
arithmetic modulo an irreducible polynomial), which complicates
implementations on computers with standard instruction sets, in
particular in the case of very long keys.
The talk describes universal hash functions of various levels of
strength that use only integer arithmetic without the need of
prime numbers of any size. A special class requires only the
operations addition, multiplication, and shifts of binary words.
Such classes are easily implemented; the functions have small
evaluation times.
Some applications (minimizing the number of random bits in hash-
ing schemes; generating k-wise independent random variables;
complexity issues) will also be discussed.
Abstract of the talk:
Bernd Gaertner
Randomisierte Optimierung.
Die Simplex-Methode in neuem Gewand.
Dantzigs Simplex-Algorithmus zum Loesen linearer Programme galt
in der Theoretischen Informatik - insbesondere der Algorithmischen
Geometrie - lange Zeit als `unanalysierbare Heuristik'
(mit exponentieller Laufzeit im schlechtesten Fall) und wurde
dementsprechend kaum untersucht. Erst vor einigen Jahren gab es
unabhaengig voneinander zwei wichtige Fortschritte. Kalai
entwickelte eine subexponentielle Zeitschranke fuer eine randomisierte
Simplex-Variante und Sharir, Welzl zeigten, dass auch
Probleme, die viel allgemeiner sind als lineares Programmieren,
eine effiziente randomisierte Loesung erlauben. Im Vortrag
moechte ich diese Resultate vorstellen und ueber erweiterte
Anwendungen sowie neue (obere und untere) Zeitschranken berichten,
die ich waehrend meiner Dissertation entwickelt habe. Als
Motivation und erste `praktische' Anwendung werde ich zeigen, wie
man effizient eine Party organisieren kann, oder wie man - falls
diese dann doch nicht zustandekommt - die freie Zeit sehr gut mit
einem Solitaerspiel auf Binaerzahlen fuellen kann.
Abstract of the talk:
Andrea Pietracaprina
Fast Deterministic Backtrack Search
The backtrack search problem involves visiting all the nodes of
an arbitrary binary tree given a pointer to its root, subject to the
constraint that the children of a node are revealed only after their
parent is visited. We describe a fast, deterministic backtrack
search algorithm for a p-processor COMMON CRCW-PRAM that visits any
n-node tree of height h in time O((n/p +h) (\log \log \log p)^2).
This upperbound compares favourably with a natural
Omega(n/p +h) lower bound for this problem. Our approach embodies
novel, efficient techniques for dynamically assigning tree-nodes to
processors to ensure that the work is shared equitably among them.
Joint work with: K.Herley and G.Pucci
Research interest of
Andrea Pietracaprina
(Universit` di Padova, Dipartimento di Matematica Pura e Applicata)
My research interests are primarily within the field of parallel
computation. The following is a list of topics that have been
considered in my past and/or current research:
- Parallel computational models;
- PRAM simulation, with particular emphasis on its worst-case
complexity;
- Explicit construction of (bipartite) expander graphs;
- Parallel data structures
- Packet routing: store-and-forward, deflection routing and
routing in arbitrary networks
- Dynamic load balancing and parallel backtrack search.
Abstract of the talk:
Prof.
Frank Dehne
From Parallel Time Complexity To Parallel Time
It is well known that theoretical time complexity results for the PRAM
as well as other fine grained parallel machine models do not always
reflected in the running times ofserved in actual implementations.
We study the design of efficient scalable parallel programs coarse grained
mulitprocessors. We present techniques which result in parallel algorithms
that are good on paper as well as in real implementation. Many of our
methods also have the adventage of being portable across a variety of
different platforms without loss in speedup observed.
Abstract of the talk:
Leszek Gasieniec
Broadcasting with linearly bounded transmission faults
(joint work with Andrzej Pelc)
We consider broadcasting with a linearly bounded number of transmission
failures. For a constant parameter $0<\alpha <1$ we assume that at most
$\alpha i$ faulty transmissions can occur during the first $i$ time units
of the communication process, for every natural number $i$.
Every informed node can transmit information to at most
one neighbor in a unit of time. Faulty transmissions have no effect.
We investigate worst-case optimal broadcasting time under this fault model,
for several communication networks.
We show, for example, that for the $n$-node line network
this time is linear in $n$, if $\alpha <\frac{1}{2}$,
and exponential otherwise.
For the hypercube and the complete graph, broadcasting
in the linearly bounded fault model can be performed in time
logarithmic in the number of nodes.
Abstract of the talk:
Anna Gambin
Shared-Memory Simulations on a Faulty-Memory DMM
In this talk we consider the Distributed Memory Machine (DMM)
with faults in memory. The DMM consists of a set of synchronized
processors together with memory units (MUs). A MU can be accessed
by at most one processor at a time. The number of word memory
faults is at most a fixed fraction of the total number of words.
Except for this condition, the distribution of faults is
arbitrary, in particular some MUs may be totally faulty.
We develop two fast randomized simulations of the PRAM on such a
faulty DMM. A simulation consists of two phases:
the preprocessing is followed by the simulation proper done in
a step-by-step fashion. The DMM has n processors and n MUs,
where each MU has the capacity of m words, m=n^gamma, for
a constant gamma>0. One simulation is of an n log n-processor
PRAM and it operates with
the optimal expected slowdown O(log n), the other is of a PRAM
with n/log n processors and has the slowdown O(loglog n).
The simulated PRAM can use the storage of size up to O(nm). One
would expect that to achieve this we need a preprocessing that
scans at least a fraction of the whole memory, and, since there
are m words per processor, requires time Omega(m). It is an in-
teresting feature of the presented simulations that the prepro-
cessing is performed in time sublinear in m, actually in time
O(sqrt(m) log n).
Abstract of the talk:
Prof. Martin Dyer
A New Approach to Generating a Random Point in a Convex Body
The first polynomial time algorithm for uniformly
generating a random point from a convex body in high dimension was given
by Dyer, Frieze and Kannan (1989). Their technique relied on an approach
called "conductance", and an isoperimetric inequality for convex
bodies. There have been many subsequent imrovements, but all have used
essentially the same approach. We will show how, in the light of some
of these improvements, a rather simpler method, called "coupling" can be
used to prove the existence of a polynomial time generation algorithm.
A short review of the background, and an outline of the new
approach, will be given.
(Joint work with Mark Jerrum and Russ Bubley.)
Abstract of the talk:
Dr. Shiva Chaudhuri
Deterministic Restrictions in Circuit Complexity
We study the complexity of computing Boolean functions using AND, OR
and NOT gates. We show that a circuit of depth $d$ with $S$ gates can
be made to output a constant by setting $O(S^{1-\epsilon(d)})$ (where
$\epsilon(d) = 4^{-d}$) of its input values. This implies a
superlinear size lower bound for a large class of functions. Using
this, we obtain a function computable by a uniform family of
constant depth polynomial size circuits that cannot be computed by
constant depth circuits of linear size. We give circuit constructions
that show that the bound $O(S^{1-\epsilon(d)})$ is near optimal.
We also study the complexity of computing threshold
functions. The function $T^n_r$ has the value 1 iff at least $r$ of
its inputs have the value 1. We show that a circuit computing $T^n_r$
has at least $\Omega(r^2 (\log n)/ \log r)$ gates, for $r \leq
n^{1/3}$, improving previous bounds. We also show a trade-off between
the number of gates and the number of wires in a threshold circuit,
namely, a circuit with $G$ $(< n/2)$ gates and $W$ wires computing
$T^n_r$ satisfies $W \geq \Omega(n r (\log n)/(\log (G/\log n)))$,
showing that it is not possible to simultaneously optimize the number
of gates and wires in a threshold circuit. Our bounds for threshold
functions are based on a combinatorial lemma of independent interest.
Abstract of the talk:
Dr. Salvatore Orlando
A Template for Non-uniform Parallel Loops Based on Dynamic Scheduling and Prefetching Techniques
In this talk we present an efficient template for the
implementation on distributed-memory multiprocessors of {\em
non--uniform parallel loops}, i.e. loops whose independent iterations are
characterized by highly varying execution times.
The technique relies upon a static {\em blocking}
distribution of the data sets and a hybrid scheduling policy. The template
initially adopts a static technique to distribute the loop iterations
among the processing nodes. As soon as a workload imbalance is
detected, it exploits a dynamic {\em receiver initiate}
technique to move work towards unloaded processors.
Two version of the template are presented. The first version is
optimized for iterated parallel loops, i.e. parallel loops nested in a
sequential one, for which it is necessary to maintain the coherence of the
data
among successive iterations of the outer sequential loop.
The second version is specifically designed for parallel loops which
are not nested or which do not modify the accessed data.
In both the cases prefetching is used to reduce overheads due to the
communications needed to monitor the load, move iterations, and restore
the consistency of migrated data.
Accurate performance costs of the technique can be derived, thus
allowing the template to be used by a compiler to generate
well-balanced code for non--uniform parallel loops.
The possibility of exploiting data locality deriving from the adoption of a
{\em blocking} data distribution
is one of the main goals of the proposed technique. A {\em cyclic} distribution
which causes the loss of data locality should be instead used
with an HPF-like language to achieve acceptable performances.
Experiments have been conducted on a 64-node Cray
T3D, and the performance of the proposed template has been compared with
the one obtained by using the CRAFT-Fortran language (an HPF-like language).
Abstract of the talk:
Micah Adler
New Coding Techniques for Improved Bandwidth Utilization
The introduction of parallel models that account for communication
between processors has shown that interprocessor bandwidth is often
the limiting factor in parallel computing. In this talk, we
introduce a novel coding technique for transmitting the XOR of
carefully selected patterns of bits to be communicated which greatly
reduces bandwidth requirements in some settings. This technique may
have broader applications. For example, we demonstrate that the
coding technique has a surprising application to a simple I/O (Input /
Output) complexity problem related to finding the transpose of a
matrix.
Our main results are developed in the PRAM(M) model, a limited
bandwidth PRAM model where P processors communicate through a small
globally shared memory of M bits. We provide new algorithms for
the problems of sorting and permutation routing. For the concurrent
read PRAM(M), as P grows with M held constant, our sorting
algorithm outperforms any previous algorithm by \Omega(\log^c P) for
any constant c. The combination of a known lower bound for sorting
in the exclusive read PRAM(M) model and this algorithm implies that
the concurrent read PRAM(M) is strictly more powerful than the
exclusive read PRAM(M).
Abstract of the talk:
Andrzej Pelc
Broadcasting in Unlabeled Networks
We consider broadcasting a message from one node to all other nodes
of an asynchronous totally unlabeled network: neither nodes nor links
of the network have a priori assigned labels but they know
the topology of the network. Nodes can send messages of arbitrary
size and we are interested in minimizing the total number of messages.
Broadcasting in an n-node unlabeled network is perfect if it uses n-1
messages (the minimum even in the labeled network). We show that
the problem of deciding whether an arbitrary network admits perfect
broadcasting from a given source, is NP-hard. We characterize regular
networks in which perfect broadcasting from every node is possible
and give such broadcasting algorithms. We also show a broadcasting
algorithm in an n-node unlabeled hypercube, which uses only O(n)
messages.
This is joint work with K. Diks and E. Kranakis.
Abstract of the talk:
Prof. Sajal K. Das
Conflict-Free Access to Data Structures in Parallel Memory Systems
Mapping the nodes of a data structure (represented as a graph) to as few
memory modules as possible of a multiprocessor architecture, such that
different subsets of nodes (called templates) can be accessed in parallel
and without memory conflicts, is an important problem. This can be
formulated as a hypergraph coloring problem and hence is NP-hard. So we will
seek for load-balanced mappings of various templates in special host data
structures like k-ary trees, binomial trees, and hypercubes. For trees, the
templates of interest are subtrees of a given height, paths from the root
to the leaves, or the nodes in any level; whereas for hypercubes the
potential templates are subcubes of any size or the set of nodes at a given
distance from a source. Our novel solutions are based on coding theory,
number theory or graph theory with suitable node labelings.
As applications, we will show how path templates play crucial roles in
work-optimal implementation of distributed priority queues, subtree templates
in parallel image processing or range queries in search trees, while subcube
templates in concurrent file accesses with designated signatures.
The intricacy of the mapping with an optimal number of memory modules
(the lower bound of which is the template size) is due to overlappings of
template instances, which motivate us to define a concept called oriented
templates. We will conclude the talk with a few open problems.
Abstract of the talk:
Hubertus Franke
One main Question is how to construct Problem Domain Specific
Programming Environments
with various things in mind:
- Fast Prototyping
- Evolutionary Changes (Domain Knowledge changes)
- Legacy System integration.
The approach taken is based on the model-integrated programming
paradigm.
Using a tightly defined model-paradigm, tools such as graphical model
editors,
database interfaces etc. are generated or customized automatically.
Using the editor, sophisticated multi-faceted models of the information
system,
the environment and their interactions are build.
Using program synthesis the final system is automatically generated from
the model.
The systems we have build based on this technology are driving real life
applications:
(1) Online Parallel Data Analysis Tool Set for world's largest
turbine engine test environment at the Airforce Engineering Center
(2) Chemical Process Control System for a Dupont Plastic Manufacturing
Plant
(3) General Motor's Saturn Site Production Flow system.
Since, in these systems, the model have become the essential investment
(not the code)
the approach has been used by BOEING for various sensor analysis on the
Space Station.
Abstract of the talk:
L. H. Harper
On an Isoperimetric Problem for Hamming Graphs
We consider an isoperimetric problem for the graph G = (K_q)^n, the
cartesian product of n complete graphs. The problem is to find a set A
of vertices with a given cardinality so that the number of vertices of
G-A at distance 1 of A is minimum. The problem does not have nested
solutions, so the known combinatorial methods are ineffectual. However,
passing to a continuous limit gives a variational problem which is
solved exactly and from its solutions we draw conclusions about
solutions of the original combinatorial problem.
Abstract of the talk:
Luca Becchetti
On the complexity of the Virtual Path Layout problem in ATM networks
Asynchronous Transfer Mode (ATM) is the leading transmission and
multiplexing technique for Broadband ISDN, providing fast
switching, high transfer rate and greater flexibility for
multimedia applications. Due to this fact it has been studied
intensively in the recent past.
Differently from other transmission modes, ATM is based on small
fixed-size cells which are routed independently by means of a
simple routing algorithm which makes it possible to obtain very
short switching times. The algorithm routes each cell in
dependance of the values assumed by two fields in the cell
header, the Virtual Channel (VC) Identifier and the Virtual Path
(VP) Identifier. The routing scheme is hierarchical, in the
sense that it is performed with reference to the VP Identifier
value, except when such a value is 0: in this case, the VC
Identifier is used.
This approach results in the definition of two different types of
routes in the network: Virtual Paths and Virtual Channels, with
Virtual Channels composed by a sequence of Virtual Paths. For any
connection requests between two end-users, a VC is obtained,
resulting in the assignment to the connection of a sequence of
VPs between the nodes which have to communicate.
A major problem in this framework is that of building the system
of virtual paths (in the following called Virtual Path Problem or
VPL for short), so that certain good properties are achieved. The
most important of them are the following:
--The number of VPs using the same physical link should be as low
as possible: this number is proportional to the dimensions of the
routing tables at the vertices. This is an important aspect in
order not to exceed the capacity of the routing tables and to
allow a possibly fast recovery from link disconnections due to
faults.
--Both the transmission rate and the time needed to establish a
VC are, with good approximation, proportional to the number of
VPs in the considered VC (Hop-count in the following).
Thus, also this value should be made as small as possible.
In this talk a simplified model is introduced, which captures the
intrinsic complexity of the problem. A general lower bound is
presented, which depends on the topological characteristics of
the physical network under consideration. The general lower bound
is then applied to derive lower bounds for particular classes of
graphs. Finally, an asymptotically optimal heuristic for square
mesh networks is proposed.
Abstract of the talk:
Bogdan S. Chlebus
Performing Tasks on Restartable Message-Passing Processors
This work considers the problem of performing t tasks reliably
in a message-passing synchronous system of p fault-prone processors.
This problem, called ``Do-All" herein, was introduced by Dwork, Halpern
and Waarts (1992). They developed several algorithms and analyzed them
in terms of the number of times each task is performed
(including multiplicities) and the number of messages.
De Prisco, Mayer and Yung (1994) developed an algorithm for the Do-All
problem and analyzed it in terms of the available processor steps S
(this measure charges processors for each step they perform,
not only for those steps in which tasks are executed),
and in terms of the number of messages.
The models of failures considered by prior solutions allow for up to
f < p stop-failures and do not accommodate processor restarts.
We present two new algorithms for the Do-All problem.
The first algorithm is tolerant of f < p stop-failures and it does not
allow restarts. It has the available processor steps complexity
S = O((t + p log p/ log log p) log f) and the message complexity
M = O(t + p log p/ log log p + f p). Unlike prior solutions,
our algorithm uses redundant broadcasts when encountering failures and,
for large f, it has better S complexity. This algorithm is used
as the basis for another algorithm which tolerates any pattern of
stop-failures and restarts. This new algorithm is the first solution
for the Do-All problem that efficiently deals with processor restarts.
Its available processor steps complexity is
S = O((t + p log p + f) min {log p, log f}), and its message
complexity is M = O(t + p log p + f p), where f is the number of
failures.
This is a joint work with Roberto De Prisco, MIT,
and Alex A. Shvartsman, University of Connecticut.
Abstract of the talk:
Martin Dyer (School of Computer Science, University of Leeds, England)
Counting Independent Sets in Graphs
The problem of counting and generating independent sets in graphs has
received recent attention. Its relation to the hard-core gas model in
statistical physics has been a particular stimulus. The counting problem
is known to be #P-complete, even for graphs of maximum degree 3.
On the other hand, it has been shown that, for graphs of maximum degree 4,
fully polynomial randomized approximate counting is possible.
This success has been achieved by using the Monte Carlo Markov chain
method to generate random uniformly selected independent sets in the
graph.
We will examine a paticular Markov chain for this problem and outline
its analysis by the method of "path coupling".
The degree 4 result suggests a natural question as to how far this
success might extend. Unfortunately, the evidence now seems to be:
not very far. We will outline two negative results.
The first indicates that the Monte Carlo Markov chain method is
likely to fail for graphs of degree not much greater than 4. The
second gives a larger (but still relatively small) value
of the maximum degree above which approximate counting by any means
is impossible, unless P=NP under randomized reductions.
Abstract of the talk:
Johanne Cohen (Universite Paris Sud, France)
Multicasting and Broadcasting in the Tree
This talk will briefly survey results on broadcasting in trees under
different constraints. The motivation of this study is that most of
the broadcasting protocols make use of a spanning tree of the network
to disseminate the information to members of groups (multicast)
or to the whole network (broadcast). Using a spanning tree
allows to decrease the number of copies of the same message in
the network (as opposed to flooding). On the other hand, some
communication constraints impose to schedule the communications in a
sophisticated manner. This is the purpose of this talk to present
some algorithms solving the broadcast problem in trees.
Abstract of the talk:
Prof. Dr. Angelika Steger (Institut für Informatik, TU München)
Asymptotic Enumeration, Global Structure, and Constrained Evolution
Determining the cardinality of a class of discrete objects
and the structure of a typical element within this class
is relatively easy whenever the objects can be generated by
a sequence of independent events. If this is not the case
the problem usually becomes much harder. Here one way
to circumvent the lack of independence is the following:
within the set in question, find a subset which can be
enumerated by independent decisions, and show that this
subset contains almost all of the objects of the larger set.
This strategy is very attractive since it not only estimates
the cardinality of the larger set, but at the same time
proves a result about the global structure of the
larger set: draw an object uniformly at random from the set,
then with high probability it satisfies the conditions
that define the subset.
In this talk we survey some results that are based on this approach.
In particular we will study triangle-free and d-regular graphs.
Abstract of the talk:
Ladislav Stacho (Slovak Academy of Sciences, Bratislava, Slovakia)
Results and Problems on Wavelength Allocations in All-optical Networks
TBA
Artur Czumaj
(artur@uni-paderborn.de)
Last modified August 16, 1999