Caching in Networks: Non-Uniform Algorithms and Memory Capacity Constraints - Westermann, Matthias

PUB-Library, Release 7.0, User Guide and Function Reference - Bonorden, Olaf; Rieping, Ingo; von Otte, Ingo; Juurlink, Bernhardus

Probabilistic Methods for Coordination Problems - Scheideler, Christian

Tradeoff analysis and architecture design of a hybrid hardware/software sorter - Bednara, M.; Beyer, O.; Teich, J.; Wanka, Rolf (Proc. Int. Conf. on Application Specific Systems, Architectures, and Processors (ASAP))

Efficient Communication Strategies for Ad Hoc Wireless Networks - Adler, Micah; Scheideler, Christian (Theory Comput. Syst.)

From Static to Dynamic Routing: Efficient Transformations of Store-and-Forward Protocols - Scheideler, Christian; Vöcking, Berthold (SIAM J. Comput.)

Distributed Path Selection for Storage Networks - Berenbrink, Petra; Brinkmann, André; Scheideler, Christian (PDPTA)

Coloring non-uniform hypergraphs: a new algorithmic approach to the general Lovász local lemma - Czumaj, Artur; Scheideler, Christian (SODA)

Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lovász local lemma - Czumaj, Artur; Scheideler, Christian (Random Struct. Algorithms)

Efficient, distributed data placement strategies for storage area networks (extended abstract) - Brinkmann, André; Salzwedel, Kay; Scheideler, Christian (SPAA)

A new algorithm approach to the general Lovász local lemma with applications to scheduling and satisfiability problems (extended abstract) - Czumaj, Artur; Scheideler, Christian (STOC)

Randomized Point Sampling for Output-Sensitive Rendering of Complex Dynamic Scenes - Wand, Michael; Fischer, Matthias; Meyer auf der Heide, Friedhelm
We present a new output-sensitive rendering algorithm, the randomized z-buffer algorithm. It renders an image of a three dimensional scene of triangular primitives by reconstruction from a random sample of surface points which are chosen with a probability proportional to the projected area of the objects. The approach is independent of mesh connectivity and topology. It leads to a rendering time that grows only logarithmically with the numbers of triangles in the scene and to linear memory consumption, thus allowing walkthroughs of scenes of extreme complexity. We consider different methods for image reconstruction which aim at correctness, rendering speed and image quality and we develop an efficient data structure for sample extraction in output-sensitive time which allows for efficient dynamic updates of the scene. Experiments confirm that scenes consisting of some hundred billion triangles can be rendered within seconds with an image quality comparable to a conventional z-buffer rendering; in special cases, realtime performance can be achieved.

I/O-Efficient Well-Separated Pair Decomposition and Applications - Govindarajan, Sathish; Lukovszki, Tamas; Maheshwari, Anil; Zeh, Norbert (Proceedings of the 8th Annual European Symposium on Algorithms (ESA 2000), LNCS)

Property Testing in Computational Geometry - Czumaj, Artur; Sohler, Christian; Ziegler, Martin (Proceedings of the 8th Annual European Symposium on Algorithms (ESA'00))
We consider the notion of Property Testing as applied to computational geometry. We aim at developing efficient algorithms which determine whether a given (geometrical) object has a predetermined property Q or is 'far' from any object having the property. We show that many basic geometric properties have very efficient testing algorithms, whose running time is significantly smaller than the object description size.

Computing the Dimension of Linear Subspaces - Ziegler, Martin; Brattka, Vasco (SOFSEM 2000: Theory and Practice of Informatics)
Since its very beginning, linear algebra is a highly algorithmic subject. Let us just mention the famous Gauss Algorithm which was invented before the theory of algorithms has been developed. The purpose of this paper is to link linear algebra explicitly to computable analysis, that is the theory of computable real number functions. Especially, we will investigate in which sense the dimension of a given linear subspace can be computed. The answer highly depends on how the linear subspace is given: if it is given by a finite number of vectors whose linear span represents the space, then the dimension does not depend continuously on these vectors and consequently it cannot be computed. If the linear subspace is represented via its distance function, which is a standard way to represent closed subspaces in computable analysis, then the dimension does computably depend on the distance function.

Computing Cut Numbers - Ziegler, Martin; Sohler, Christian (Proceedings of the 12th Canadian Conference on Computational Geometry (CCCG'00))
What is the minimum number of hyperplanes that slice all edges of the d-dimensional hypercube? The answers have been known for d<=4. This work settles the problem for d=5 and d=6. More precisely, a computer search implies that 4 hyperplanes do not suffice for this purpose (but 5 do). We also develop computational approaches for attacking this extremal problem from combinatorial geometry in higher dimensions. They allow us to determine for example all maximal sliceable subsets of hypercube edges up to dimension 7.

Periodification Scheme: Constructing Sorting Networks with Constant Period - Lorys, Krzysztof; Wanka, Rolf; Oesterdiekhoff, Brigitte; Kutylowski, Miroslaw (Journal of the ACM)
We consider comparator networks M that are used repeatedly: while the output produced by M is not sorted, it is fed again into M. Sorting algorithms working in this way are called periodic. The number of parallel steps performed during a single run of M is called its period, the sorting time of M is the total number of parallel steps that are necessary to sort in the worst case. Periodic sorting networks have the advantage that they need little hardware (control logic, wiring, area) and that they are adaptive. We are interested in comparator networks of a constant period, due to their potential applications in hardware design. Previously, very little was known on such networks. The fastest solutions required time O(nε) where the depth was roughly 1/ε. We introduce a general method called periodification scheme that converts automatically an arbitrary sorting network that sorts n items in time T(n) and that has layout area A(n) into a sorting network that has period 5, sorts ***(n • T(n) items in time O(T(<n)• log n), and has layout area O(A(n)) • T(n)). In particular, applying this scheme to Batcher's algorithms, we get practical period 5 comparator networks that sort in time O(log3n). For theoretical interest, one may use the AKS netork resulting in a period 5 comparator network with runtime O(log2n).

A New Algorithmic Approach to the General Lovász Local Lemma with Applications to Scheduling and Satisfiability Problems - Czumaj, Artur; Scheideler, Christian (32nd ACM Symposium on Theory of Computing)

Data management in hierarchical bus networks - Meyer auf der Heide, Friedhelm; Räcke, Harald; Westermann, Matthias (Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures - SPAA '00)

Caching in networks - Meyer auf der Heide, Friedhelm; Vöcking, Berthold; Westermann, Matthias (SODA '00: Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms)
We present a general framework for the development of on-line algorithms for data management in networks with limited memory capacities. These algorithms dynamically create and delete copies of shared data objects that can be read and written by the nodes in the network. Our algorithms aim to minimize the congestion, i.e., the maximum communication load over all network resources, so that that none of these resources become a communication bottleneck. We give several examples of networks for which our framework yields efficient algorithms, including meshes, fat-trees, hypercubic networks, and complete networks. For example, our framework yields an $O(d cdot log n)$-competitive caching algorithm for $d$-dimensional meshes of size $n$ with respect to the congestion on the communication links, and an $O(1)$-competitive algorithms for complete networks with respect to the congestion at the memory modules due to remote accesses. Previous work on data management in networks either neglects memory capacity constraints or minimizes only the total communication load, i.e., the sum of the communication load over all resources, which may produce congestion as some of the links become bottlenecks.

Complexity Theory and Algorithms - Meyer auf der Heide, Friedhelm; Kutyłowski, Mirosław; Ragde, Prabhakar (Euro-Par 2000 Parallel Processing)

Contention Resolution in Hashing Based Shared Memory Simulations - Czumaj, Artur; Meyer auf der Heide, Friedhelm; Stemann, Volker (SIAM Journal on Computing)

Von der Hollerith-Maschine zum Parallelrechner - Die alltägliche Aufgabe des Sortierens als Fortschrittsmotor für die Informatik - Meyer auf der Heide, Friedhelm; Wanka, Rolf (ForschungsForum Paderborn)

The Paderborn university BSP (PUB) library-design, implementation and performance - Bonorden, Olaf; Juurlink, Bernhardus; Von Otte, I.; Rieping, Ingo (Proceedings 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing)
The Paderborn University BSP (PUB) library is a parallel C library based on the BSP model. The basic library supports buffered and unbuffered asynchronous communication between any pair of processors, and a mechanism for synchronizing the processors in a barrier style. In ad-dition, it provides routines for collective communication on arbitrary subsets of processors, partition operations, and a zero-cost synchronization mechanism. Furthermore, some techniques used in its implementation deviate significantly from the techniques used in other BSP libraries.

Simple, Efficient Routing Schemes for All-Optical Networks - Flammini, Michele; Scheideler, Christian (Theory Comput. Syst.)

Locally Efficient On-Line Strategies for Routing Packets Along Fixed Paths - Berenbrink, Petra; Scheideler, Christian (SODA)

Simple Competitive Request Scheduling Strategies - Berenbrink, Petra; Riedel, Marco; Scheideler, Christian (SPAA)

Partitioned neighborhood spanners of minimal outdegree - Fischer, Matthias; Lukovszki, Tamas; Ziegler, Martin (Proceedings of the 11th Canadian Conference on Computational Geometry)
A geometric spanner with vertex set P in Rd is a sparse approximation of the complete Euclidean graph determined by P. We introduce the notion of partitioned neighborhood graphs (PNGs), unifying and generalizing most constructions of spanners treated in literature. Two important parameters characterizing their properties are the outdegree k in N and the stretch factor f>1 describing the quality of approximation. PNGs have been throughly investigated with respect to small values of f. We present in this work results about small values of k. The aim of minimizing k rather than f arises from two observations: * k determines the amount of space required for storing PNGs. * Many algorithms employing a (previously constructed) spanner have running times depending on its outdegree. Our results include, for fixed dimensions d as well as asymptotically, upper and lower bounds on this optimal value of k. The upper bounds are shown constructively and yield efficient algorithms for actually computing the corresponding PNGs even in degenerate cases.

Fast Reconstruction of Delaunay Triangulations - Sohler, Christian (Proceedings of the 11th Canadian Conference on Computational Geometry ( CCCG'99))
We present a new ( O(n) ) algorithm to compute good orders for the point set of a Delaunay triangulation of ( n ) points in the plane. Such a good order makes reconstruction in ( O(n) ) time with a simple algorithm possible. In contrast to the algorithm of Snoeyink and van Kreveld cite1, which is based on independent sets, our algorithm uses a breadth first search (BFS) to obtain these orders. Both approaches construct such orders by repeatedly removing a constant fraction of vertices from the current triangulation. The advantage of the BFS approach is that we can give significantly better bounds on the fraction of removed points in a phase of the algorithm. We can prove that a single phase of our algorithm removes at least ( frac13 ) of the points, even if we restrict the degree of the points (at the time they are removed) to 6. We implemented and compared both algorithms. Our algorithms is slightly faster and achieves about 15% better vertex data compression when using a simple variable length code to encode the differences between two consecutive vertices of the given order.

New Results on Geometric Spanners and Their Applications - Lukovszki, Tamás

New Results on Fault Tolerant Geometric Spanners - Lukovszki, Tamás (Proceedings of the 6th Workshop on Algorithms an Data Structures (WADS'99), LNCS)
We investigate the problem of constructing spanners for a given set of points that are tolerant for edge/vertex faults. Let S be a set of $n$ points in the d-dimensional space and let k be an integer number. A k-edge/vertex fault tolerant spanner for S has the property that after the deletion of k arbitrary edges/vertices each pair of points in the remaining graph is still connected by a short path. Recently it was shown that for each set S of n points there exists a k-edge/vertex fault tolerant spanner with O(k^2 n) edges which can be constructed in O(n log n + k^2 n) time. Furthermore, it was shown that for each set S of n points there exists a k-edge/vertex fault tolerant spanner whose degree is bouned by O(c^k+1) for some constant c. Our first contribution is a construction of a k-vertex fault tolerant spanner with O(kn) edges which is a tight bound. The computation takes O(n log^d-1 n + k n log log n) time. Then we show that the same k-vertex fault tolerant spanner is also k-edge fault tolerant. Thereafter, we construct a k-vertex fault tolerant spanner with O(k^2 n) edges whose degree is bounded by O(k^2). Finally, we give a more natural but stronger definition of k-edge fault tolerance which not necessarily can be satisfied if one allows only simple edges between the points of S. We investigate the question whether Steiner points help. We answer this question affirmatively and prove Theta(kn) bounds on the number of Steiner points and on the number of edges in such spanners.

Data management in networks: experimental evaluation of a provably good strategy - Krick, Christof; Meyer auf der Heide, Friedhelm; Räcke, Harald; Vöcking, Berthold; Westermann, Matthias (Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures - SPAA '99)

Generating Random Star-Shaped Polygons - Sohler, Christian (Proceedings of the 11th Canadian Conference on Computational Geometry ('CCCG'99))
In this paper we deal with two problems on star-shaped polygons. First, we present a Las-Vegas algorithm that uniformly at random creates a star-shaped polygon whose vertices are given by a point set ( S ) of ( n ) points in the plane that does not admit degenerate star-shaped polygons. The expected running time of the algorithm is ( O(n^2log n) ) and it uses ( O(n) ) memory. We call a star-shaped polygon degenerate if its kernel has 0 area. Secondly, we show how to count all star-shaped polygons whose vertices are a subset of ( S ) in ( O(n^5log n) ) time and ( O(n) ) space. The algorithm can also be used for random uniform generation. We also present lower and upper bounds on the number of star-shaped polygons.

Design of the PRESTO Multimedia Storage Network (Extended Abstract) - Berenbrink, Petra; Riedel, Marco; Scheideler, Christian (International Workshop on Communication and Data Management in Large Networks (CDMLarge))

From Static to Dynamic Routing: Efficient Transformations of Store-and-Forward Protocols - Scheideler, Christian; Vöcking, Berthold (STOC)

Shortest-Path Routing in Arbitrary Networks - Meyer auf der Heide, Friedhelm; Vöcking, Berthold (Journal of Algorithms)

Allocating Weighted Jobs in Parallel - Berenbrink, P.; Meyer auf der Heide, Friedhelm; Schröder, K. (Theory of Computing Systems)

International Workshop on Communication and Data Management in Large Networks - Mayr, E. W.; Meyer auf der Heide, Friedhelm; Wanka, Rolf (Informatik aktuell)

Provably Good and Practical Strategies for Non-uniform Data Management in Networks - Meyer auf der Heide, Friedhelm; Vöcking, Berthold; Westermann, Matthias (Algorithms - ESA’ 99)

Static and Dynamic Data Management in Networks - Vöcking, Berthold

The Paderborn University BSP (PUB) Library - Design, Implementation and Performance - Bonorden, Olaf; Rieping, Ingo; von Otte, Ingo; Juurlink, Bernhardus
The Paderborn University BSP (PUB) library is a parallel C library based on the BSP model. The basic library supports buffered and unbuffered asynchronous communication between any pair of processors, and a mechanism for synchronizing the processors in a barrier style. In addition, it provides routines for collective communication on arbitrary subsets of processors, partition operations, and a zero-cost synchronization mechanism. Furthermore, some techniques used in the implementation of the PUB library deviate significantly from the techniques used in other BSP libraries.

Geometric Searching in Walkthrough Animations with Weak Spanners in Real Time - Fischer, Matthias; Lukovszki, Tamás; Ziegler, Martin (Algorithms — ESA’ 98)
We study algorithmic aspects in the management of geometric scenes in interactive walkthrough animations. We consider arbitrarily large scenes consisting of unit size balls. For a smooth navigation in the scene we have to fulfill hard real time requirements. Therefore, we need algorithms whose running time is independent of the total number of objects in the scene and that use as small space as possible. In this work we focus on one of the basic operations in our walkthrough system: reporting the objects around the visitor within a certain distance. Previously a randomized data structure was presented that supports reporting the balls around the visitor in an output sensitive time and allows insertion and deletion of objects nearly as fast as searching. These results were achieved by exploiting the fact that the visitor moves ''slowly'' through the scene. A serious disadvantage of the aforementioned data structure is a big space overhead and the use of randomization. Our first result is a construction of weak spanners that leads to an improvement of the space requirement of the previously known data structures. Then we develop a deterministic data structure for the searching problem in which insertion of objects are allowed. Our incremental data structure supports O(1+k) reporting time, where k is a certain quantity close to the number of reported objects. The insertion time is similar to the reporting time and the space is linear to the total number of objects.

A Network Based Approach for Realtime Walkthrough of Massive Models - Fischer, Matthias; Lukovszki, Tamas; Ziegler, Martin (Algorithm Engineering, 2nd International Workshop, WAE '98)
New dynamic search data structures developed recently guarantee constant execution time per search and update, i.e., they fulfil the real-time requirements necessary for interactive walkthrough in large geometric scenes. Yet, superiority or even applicability of these new methods in practice was still an open question. Their prototypical implementation presented in this work uses common libraries on standard stations and thus represents a first strut to bridge this gap. Indeed our experimental results give an indication on the actual performance of these theoretical ideas on real machines and possible bottlenecks in future developments. By special algorithmic enhancements, we can even avoid the otherwise essential preprocessing step.

Multimediale Entdeckungsreisen unserer Welt mit dem Internet - Ziegler, Martin; Fischer, Matthias; Lukovszki, Tamás
Preis für den Beitrag "Multimediale Entdeckungsreisen unserer Welt mit dem Internet"

On Periodic Comparator Networks - Oesterdiekhoff, Brigitte

Universal Continuous Routing Strategies - Scheideler, Christian; Vöcking, Berthold (Theory Comput. Syst.)

Efficient Communication Strategies for Ad-Hoc Wireless Networks (Extended Abstract) - Adler, Micah; Scheideler, Christian (SPAA)

Improved Bounds for Acyclic Job Shop Scheduling (Extended Abstract) - Feige, Uriel; Scheideler, Christian (STOC)

Universal Routing Strategies for Interconnection Networks - Scheideler, Christian

Routing on networks of optical crossbars - Meyer auf der Heide, Friedhelm; Schröder, Klaus; Schwarze, Frank (Theoretical Computer Science)

Truly efficient parallel algorithms: 1-optimal multisearch for an extension of the BSP model - Bäumker, Armin; Dittrich, Wolfgang; Meyer auf der Heide, Friedhelm (Theoretical Computer Science)

Communication-efficient parallel multiway and approximate minimum cut computation - Meyer auf der Heide, Friedhelm; Martinez, Gabriel Terán (LATIN'98: Theoretical Informatics)

Randomized protocols for low-congestion circuit routing in multistage interconnection networks - Cole, Richard; Maggs, Bruce M.; Meyer auf der Heide, Friedhelm; Mitzenmacher, Michael; Richa, Andréa W.; Schröder, Klaus; Sitaraman, Ramesh K.; Vöcking, Berthold (Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98)

Communication Efficient Parallel Searching - Bäumker, Armin

Communication and I/O Efficient Parallel Data Structures - Dittrich, Wolfgang

Bounded Degree Spanning Trees - Strothmann, Willy-Bernhard

Bounded degree spanning trees - Czumaj, Artur; Strothmann, Willy-Bernhard (Proceedings of the Fifth Annual European Symposium on Algorithms (ESA'97))
Given a connected graph $G$, let a $dT$-spanning tree of $G$ be a spanning tree of $G$ of maximum degree bounded by $dT$. It is well known that for each $dT ge 2$ the problem of deciding whether a connected graph has a $dT$-spanning tree is NP-complete. In this paper we investigate this problem when additionally connectivity and maximum degree of the graph are given. A complete characterization of this problem for 2- and 3-connected graphs, for planar graphs, and for $dT=2$ is provided. Our first result is that given a biconnected graph of maximum degree $2dT-2$, we can find its $dT$-spanning tree in time $O(m+n^3/2)$. For graphs of higher connectivity we design a polynomial-time algorithm that finds a $dT$-spanning tree in any $k$-connected graph of maximum degree $k(dT-2)+2$. On the other hand, we prove that deciding whether a $k$-connected graph of maximum degree $k(dT-2)+3$ has a $dT$-spanning tree is NP-complete, provided $k le 3$. For arbitrary $k ge 3$ we show that verifying whether a $k$-connected graph of maximum degree $k(dT-1)$ has a $dT$-spanning tree is NP-complete. In particular, we prove that the Hamiltonian path (cycle) problem is NP-complete for $k$-connected $k$-regular graphs, if $k>2$. This extends the well known result for $k=3$ and fully characterizes the case $dT=2$. For planar graphs it is NP-complete to decide whether a $k$-connected planar graph of maximum degree $dG$ has a $dT$-spanning tree for $k=1$ and $dG > dT ge 2$, for $k=2$ and $dG > 2(dT-1) ge 2$, and for $k=3$ and $dG > dT = 2$. On the other hand, we show how to find in polynomial (linear or almost linear) time a $dT$-spanning tree for all other parameters of $k$, $dG$, and $dT$.

Decremental Biconnectivity on Planar Graphs - Strothmann, Willy-Bernhard; Lukovszki, Tamás
In this paper we present a (randomized) algorithm for maintaining the biconnected components of a dynamic planar graph of $n$ vertices under deletions of edges. The biconnected components can be maintained under any sequence of edge deletions in a total of $O(n log n)$ time, with high probability. This gives $O(log n)$ amortized time per edge deletion, which improves previous (deterministic) results due to Giammarresi and Italiano, where $O(n log^2 n)$ amortized time is needed. Our work describes a simplification of the data structures from [GiIt96] and uses dynamic perfect hashing to reduce the running time. As in the paper by Giammarresi and Italiano, we only need $O(n)$ space. Finally we describe some simply additional operations on the decremental data structure. By aid of them this the data structure is applicable for finding efficiently a $Delta$-spanning tree in a biconnected planar graph with a maximum degree $2Delta-2$ do to Czumaj and Strothmann.

Encoding a Triangulation as a Permutation of its Point Set - Sohler, Christian; Denny, Markus (Proceedings of the 9th Canadian Conference on Computational Geometry)

Optimal Wormhole Routing in the (n, d)-Torus - Bock, Stefan; Meyer auf der Heide, Friedhelm; Scheideler, Christian (IPPS)

Simple, Efficient Routing Schemes for All-Optical Networks - Flammini, Michele; Scheideler, Christian (SPAA)

A lower bound for randomized algebraic decision trees - Grigoriev, Dima; Karpinski, Marek; Meyer auf der Heide, Friedhelm; Smolensky, Roman (computational complexity)

Simulating Shared Memory in Real Time: On the Computation Power of Reconfigurable Architectures - Czumaj, Artur; Meyer auf der Heide, Friedhelm; Stemann, Volker (Information and Computation)

Optimal Tradeoffs Between Size and Slowdown for Universal Parallel Networks - Meyer auf der Heide, Friedhelm; Storch, M.; Wanka, Rolf (Theory of Computing Systems)

Dynamic data structures for realtime management of large geometric scenes - Fischer, Matthias; Meyer auf der Heide, Friedhelm; Strothmann, Willy-Bernhard (5th Annual European Symposium on Algorithms (ESA '97))
We present a data structure problem which describes the requirements of a simple variant of fully dynamic walk-through animation: We assume the scene to consist of unit size balls in R2 or higher dimensions. The scene may be arbitrarily large and has to be stored in secondary memory (discs) with relatively slow access. We allow a visitor to walk in the scene, and a modeler to update the scene by insertions and deletions of balls. We focus on the realtime requirement of animation systems: For some t (specified by the computation power of (the rendering hardware of) the graphic workstation) the data structure has to guarantee that the balls within distance t of the current visitor's position are presented to the rendering hardware, 20 times per second. Insertions and deletions should also be available to the visitor with small delay, independent of the size of the scene. We present a data structure that fulfills the above task in realtime. Its runtime is output-sensitive, i.e. linear in a quantity close to the output size of the query. We further present (preliminary) experimental results indicating that our structure is efficient in practice.

Static and dynamic data management in networks - Meyer auf der Heide, Friedhelm; Vöcking, Berthold (Euro-Par'97 Parallel Processing)

Allocating weighted jobs in parallel - Berenbrink, Petra; Meyer auf der Heide, Friedhelm; Schröder, Klaus (Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures - SPAA '97)

Communication efficient parallel searching - Bäumker, Armin; Meyer auf der Heide, Friedhelm (Solving Irregularly Structured Problems in Parallel)

Routing on asyncronous processor networks - Karaivazoglou, Efstratios; Meyer auf der Heide, Friedhelm (Euro-Par'97 Parallel Processing)

Exploiting locality for data management in systems of limited bandwidth - Maggs, B.M.; Meyer auf der Heide, Friedhelm; Vöcking, Berthold; Westermann, Matthias (Proceedings 38th Annual Symposium on Foundations of Computer Science)

Parallel Computing in Paderborn: The SFB 376 “Massive Parallelism — Algorithms, Design Methods, Applications” - Meyer auf der Heide, Friedhelm; Decker, Thomas (Informatik ’97 Informatik als Innovationsmotor)

Routing on Networks of Optical Crossbars (Extended Abstract). - Schwarze, Frank; Meyer auf der Heide, Friedhelm; Schröder, Klaus (Euro-Par 1996)

Contention Resolution in Hashing Based Shared Memory Simulations - Czumaj, Artur; Meyer auf der Heide, Friedhelm; Stemann, Volker

A lower bound for randomized algebraic decision trees - Grigoriev, Dima; Karpinski, Marek; Meyer auf der Heide, Friedhelm; Smolensky, Roman (Proc. of 28th ACM-STOC)
We present a parallel algorithm for the rendering of complex three-dimensional scenes. The algorithm runs across heterogeneous architectures of PC-clusters consisting of a visualization-node, equipped with a powerful graphics adapter, and cluster nodes requiring weaker graphics capabilities only. The visualization-node renders a mixture of scene objects and simplified meshes (Reliefboards). The cluster nodes assist the visualization-node by asynchronous computing of Reliefboards, which are used to replace and render distant parts of the scene. Our algorithm is capable of gaining significant speedups if the cluster's nodes provide weak graphics adapters only. We trade the number of cluster nodes off the scene objects' image quality.

A Realistic Cost Model for the Communication Time in Parallel Programs - Fischer, Matthias; Rethmann, Jochen; Wachsmann, Alf (3rd Workshop on Abstract Machine Models for Parallel and Distributed Computing (AMW '96))
In this paper we develop a model for communication time on parallel computers consisting of processors and a service network, i.e., a network performing services like broadcast, synchronization, and global variables. The implementation of the service network is done on a free configurable Transputer network. Our cost model describes the communication time of accesses to global variables and consists of a multi-linear function. The cost model includes the parameters packet size, send hot spot, and the number of processors accessing global variables. These parameters influence the communication time in a high degree and capture important parameters like contention. We implement a Bitonic Sort and a Connected Components algorithm (among others) and we show that our model is able to predict the communication time within a 10% error if indirect service networks are used. The applications show that it is easy for a programmer to determine the parameter values for our model and that our new cost model precisely predicts the communication time of parallel algorithms. Furthermore, we minimize the communication time of accesses to global variables by finding a balance between the number of messages in the network and their size. Our model predicts the optimal values for these parameters which we validate by experiments. A modified implementation of our routing which determines on-line the optimal parameter values for an access to a global variable achieves good speed ups.

Realistic parallel algorithms: Priority queue operations and selection for the BSP* Model - Bäumker, Armin; Dittrich, Wolfgang; Meyer auf der Heide, Friedhelm; Rieping, Ingo (Lecture Notes in Computer Science)

A Realistic Cost Model for the Communication Time in Parallel Programs on Parallel Computers Using a Service Hardware - Fischer, Matthias; Rethmann, Jochen; Wachsmann, Alf
In this report, we develop a cost model for the communication time on parallel computers consisting of processors and a service network, i.e., a network performing services like broadcast, synchronization, and global variables. Because we do not have a parallel computer at our disposal that is equipped with a service network, we emulate the service network on a reconfigurable Transputer network. Our cost model describes the communication time of accesses to global variables and consists of a multilinear function. The cost model includes the parameters packet size, send hot spot (the number of messages sent out by one processor), and number of processors accessing global variables. We show that these parameters influence the communication time in a high degree and capture important parameters like network contention. We implement a Bitonic Sort, Sample Sort, Matrix Multiplication, and Connected Components algorithm, and we show that our model is able to predict the communication time within a 10% error if indirect service networks are used. The applications show that it is easy for a programer to determine the parameter values for our model and that our new cost model precisely predicts the communication time of parallel algorithms. We explore the interaction of hot spots and asynchrony and show that the influence of hot spots to the communication time is not as high as one would expect from theoretical considerations in a synchronous model. Therefore, we do not apprehend the hot spot in our cost model. Furthermore, we minimize the communication time of accesses to global variables by finding a balance between the number of messages in the network and their size. Our model predicts the optimal values for these parameters which we validate by experiments. A modified implementation of our routing which determines online the optimal parameter values for an access to a global variable achieves good speed ups.

Universal routing strategies - Scheideler, Christian

Exploiting Storage Redundancy to Speed up Randomized Shared Memory Simulations - Meyer auf der Heide, Friedhelm; Scheideler, Christian; Stemann, Volker (Theor. Comput. Sci.)

Deterministic Routing with Bounded Buffers: Turning Offline into Online Protocols - Meyer auf der Heide, Friedhelm; Scheideler, Christian (FOCS)

Communication in Parallel Systems - Meyer auf der Heide, Friedhelm; Scheideler, Christian (SOFSEM)

Universal Algorithms for Store-and-Forward and Wormhole Routing - Cypher, Robert; Meyer auf der Heide, Friedhelm; Scheideler, Christian; Vöcking, Berthold (STOC)

Trial and error. A new approach to space-bounded learning - Ameur, Foued; Fischer, Paul; Höffgen, Klaus -U.; Meyer auf der Heide, Friedhelm (Acta Informatica)

Strongly adaptive token distribution - Meyer auf der Heide, Friedhelm; Oesterdiekhoff, Brigitte; Wanka, Rolf (Algorithmica)

Efficient PRAM simulation on a distributed memory machine - Karp, R. M.; Luby, M.; Meyer auf der Heide, Friedhelm (Algorithmica)

The Tree Model for Hashing: Lower and Upper Bounds - Gil, Joseph; Meyer auf der Heide, Friedhelm; Wigderson, Avi (SIAM Journal on Computing)

Automata, Languages and Programming, 23rd International Colloquium, ICALP96

Fault-tolerant shared memory simulations - Berenbrink, Petra; Meyer auf der Heide, Friedhelm; Stemann, Volker (STACS 96)

Contention Resolution in Hashing Based Shared Memory Simulations - Stemann, Volker

Parallel Algorithmic Techniques: PRAM Algorithms and PRAM Simulations - Czumaj, Artur

Eine Bibliothek von Basisdiensten für Parallelrechner: Routing, Synchronisation, gemeinsamer Speicher - Wachsmann, Alf

Space-Bounded Learning Algorithms - Ameur, Foued

Simulating shared memory in real time: On the computation power of reconfigurable meshes - Czumaj, Artur; Meyer auf der Heide, Friedhelm; Stemann, Volker (Proceedings of the 2nd IEEE Workshop on Reconfigurable Architectures)

Routing with Bounded Buffers and Hot-Potato Routing in Vertex-Symmetric Networks - Meyer auf der Heide, Friedhelm; Scheideler, Christian (ESA)

Space-Efficient Routing in Vertex-Symmetric Networks (Extended Abstract) - Meyer auf der Heide, Friedhelm; Scheideler, Christian (SPAA)

Exploiting Storage Redundancy to Speed Up Randomized Shared Memory Simulations - Meyer auf der Heide, Friedhelm; Scheideler, Christian; Stemann, Volker (STACS)

Transforming comparison model lower bounds to the parallel-random-access-machine - Breslauer, Dany; Czumaj, Artur; Dubhashi, Devdatt P.; Meyer auf der Heide, Friedhelm (Information Processing Letters)

A packet routing protocol for arbitrary networks - Meyer auf der Heide, Friedhelm; Vöcking, Berthold (STACS 95)

Shared memory simulations with triple-logarithmic delay - Czumaj, Artur; Meyer auf der Heide, Friedhelm; Stemann, Volker (Lecture Notes in Computer Science)

Optimal trade-offs between size and slowdown for universal parallel networks - Meyer auf der Heide, Friedhelm; Storch, Martin; Wanka, Rolf (Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures - SPAA '95)