TY - CHAP AU - Meyer auf der Heide, Friedhelm AU - Decker, Thomas ID - 16693 SN - 1431-472X T2 - Informatik ’97 Informatik als Innovationsmotor TI - Parallel Computing in Paderborn: The SFB 376 “Massive Parallelism — Algorithms, Design Methods, Applications” ER - TY - JOUR AU - Schwarze, Frank AU - Meyer auf der Heide, Friedhelm AU - Schröder, Klaus ID - 19958 JF - Euro-Par 1996 TI - Routing on Networks of Optical Crossbars (Extended Abstract). VL - I ER - TY - GEN AU - Czumaj, Artur AU - Meyer auf der Heide, Friedhelm AU - Stemann, Volker ID - 17418 TI - Contention Resolution in Hashing Based Shared Memory Simulations ER - TY - CONF AB - 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. AU - Grigoriev, Dima AU - Karpinski, Marek AU - Meyer auf der Heide, Friedhelm AU - Smolensky, Roman ID - 17419 T2 - Proc. of 28th ACM-STOC TI - A lower bound for randomized algebraic decision trees VL - 65453 ER - TY - CONF AB - 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. AU - Fischer, Matthias AU - Rethmann, Jochen AU - Wachsmann, Alf ID - 17483 SN - 905199267X T2 - 3rd Workshop on Abstract Machine Models for Parallel and Distributed Computing (AMW '96) TI - A Realistic Cost Model for the Communication Time in Parallel Programs ER - TY - CHAP AU - Bäumker, Armin AU - Dittrich, Wolfgang AU - Meyer auf der Heide, Friedhelm AU - Rieping, Ingo ID - 17564 SN - 0302-9743 T2 - Lecture Notes in Computer Science TI - Realistic parallel algorithms: Priority queue operations and selection for the BSP* Model ER - TY - GEN AB - 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 multi­linear 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 on­line the optimal parameter values for an access to a global variable achieves good speed ups. AU - Fischer, Matthias AU - Rethmann, Jochen AU - Wachsmann, Alf ID - 18352 TI - A Realistic Cost Model for the Communication Time in Parallel Programs on Parallel Computers Using a Service Hardware ER - TY - THES AU - Scheideler, Christian ID - 2181 TI - Universal routing strategies ER - TY - JOUR AU - Meyer auf der Heide, Friedhelm AU - Scheideler, Christian AU - Stemann, Volker ID - 2182 IS - 2 JF - Theor. Comput. Sci. TI - Exploiting Storage Redundancy to Speed up Randomized Shared Memory Simulations ER - TY - CONF AU - Meyer auf der Heide, Friedhelm AU - Scheideler, Christian ID - 2183 T2 - FOCS TI - Deterministic Routing with Bounded Buffers: Turning Offline into Online Protocols ER - TY - CONF AU - Meyer auf der Heide, Friedhelm AU - Scheideler, Christian ID - 2184 T2 - SOFSEM TI - Communication in Parallel Systems VL - 1175 ER - TY - CONF AU - Cypher, Robert AU - Meyer auf der Heide, Friedhelm AU - Scheideler, Christian AU - Vöcking, Berthold ID - 2186 T2 - STOC TI - Universal Algorithms for Store-and-Forward and Wormhole Routing ER - TY - JOUR AU - Ameur, Foued AU - Fischer, Paul AU - Höffgen, Klaus -U. AU - Meyer auf der Heide, Friedhelm ID - 16698 JF - Acta Informatica SN - 0001-5903 TI - Trial and error. A new approach to space-bounded learning ER - TY - JOUR AU - Meyer auf der Heide, Friedhelm AU - Oesterdiekhoff, Brigitte AU - Wanka, Rolf ID - 16699 JF - Algorithmica SN - 0178-4617 TI - Strongly adaptive token distribution ER - TY - JOUR AU - Karp, R. M. AU - Luby, M. AU - Meyer auf der Heide, Friedhelm ID - 16700 JF - Algorithmica SN - 0178-4617 TI - Efficient PRAM simulation on a distributed memory machine ER - TY - JOUR AU - Gil, Joseph AU - Meyer auf der Heide, Friedhelm AU - Wigderson, Avi ID - 16701 JF - SIAM Journal on Computing SN - 0097-5397 TI - The Tree Model for Hashing: Lower and Upper Bounds ER - TY - BOOK ED - Meyer auf der Heide, Friedhelm ED - Monien, Burkhard ID - 16702 SN - 0302-9743 TI - Automata, Languages and Programming, 23rd International Colloquium, ICALP96 ER - TY - CHAP AU - Berenbrink, Petra AU - Meyer auf der Heide, Friedhelm AU - Stemann, Volker ID - 16703 SN - 0302-9743 T2 - STACS 96 TI - Fault-tolerant shared memory simulations ER - TY - THES AU - Stemann, Volker ID - 19623 SN - 3-931466-02-7 TI - Contention Resolution in Hashing Based Shared Memory Simulations VL - 3 ER - TY - THES AU - Czumaj, Artur ID - 19627 SN - 3-931466-07-8 TI - Parallel Algorithmic Techniques: PRAM Algorithms and PRAM Simulations VL - 8 ER -