TY - CONF AB - Load balancing is an important requirement for the efficient execu-tion of parallel numerical simulations. In particular when the simulation domainchanges over time, the mapping of computational tasks to processors needs tobe modified accordingly. State-of-the-art libraries for this problem are basedon graph repartitioning. They have a number of drawbacks, including the opti-mized metric and the difficulty of parallelizing the popular repartitioning heuris-tic Kernighan-Lin (KL).Here we further explore the very promising diffusion-based graph partitioningalgorithm DIBAP (Meyerhenke et al., JPDC 69(9):750–761, 2009) by adaptingDIBAP to the related problem of load balancing. Experiments with graph se-quences that imitate adaptive numerical simulations demonstrate the applicabilityand high quality of DIBAP for load balancing by repartitioning. Compared to thefaster state-of-the-art repartitioners PARMETIS and parallel JOSTLE, DIBAP’ssolutions have partitions with significantly fewer external edges and boundarynodes and the resulting average migration volume in the important maximumnorm is also the best in most cases.We also prove that one of DIBAP’s key components optimizes a relaxed versionof the minimum edge cut problem. Moreover, we hint at a distributed algorithmbased on ideas used in DIBAP for clustering a virtual P2P supercomputer. AU - Gehweiler, Joachim AU - Meyerhenke, Henning ID - 19016 T2 - Dagstuhl Seminar Proceedings 10261: Algorithm Engineering TI - On Dynamic Graph Partitioning and Graph Clustering using Diffusion ER - TY - GEN AU - Thies, Michael AU - Gehweiler, Joachim ID - 19018 TI - Thread Migration and Checkpointing in Java ER - TY - CONF AU - Kernbach, Serge AU - Schmickl, Thomas AU - Hamann, Heiko AU - Stradner, Jürgen AU - Schlachter, Florian AU - Schwarzer, Christopher s. F. AU - Winfield, Alan F. T. AU - Matthias, Rene ID - 19023 T2 - Artificial Life XII (ALife XII) TI - Adaptive Action Selection Mechanisms for Evolutionary Multimodular Robotics ER - TY - CONF AU - Briest, Patrick AU - Chalermsook, Parinya AU - Khanna, Sanjeev AU - Laekhanukit, Bundit AU - Nanongkai, Danupon ID - 19029 SN - 0302-9743 T2 - Workshop on Internet and Network Economics (WINE) TI - Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing ER - TY - JOUR AU - Meyer auf der Heide, Friedhelm AU - Scheideler, Christian ID - 1903 IS - 5 JF - Informatik Spektrum TI - Algorithmische Grundlagen verteilter Speichersysteme ER - TY - CONF AU - Briest, Patrick AU - Chawla, Shuchi AU - Kleinberg, Robert AU - Weinberg, S. Matthew ID - 19033 SN - 9780898717013 T2 - Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms TI - Pricing Randomized Allocations ER - TY - THES AU - Mahlmann, Peter ID - 19041 SN - 978-3-942647-02-1 TI - Peer-to-peer networks based on random graphs VL - 283 ER - TY - THES AU - Degener, Bastian ID - 19042 SN - 978-3-939350-97-2 TI - Local, distributed approximation algorithms for geometric assignment problems VL - 278 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 - Fischer, Matthias AU - Jähn, Claudius AU - Suess, Tim ID - 18136 T2 - Eurographics Symposium on Parallel Graphics and Visualization (EGPGV) TI - Asynchronous Parallel Reliefboard Computation for Scene Object Approximation ER - TY - CONF AB - Many professional cluster systems consist of nodes with different hardware configurations. Such heterogeneous environments require different load-balancing techniques than homogenous environments. The c-load-collision-protocol is able to achieve good results for data-management purposes. Using this protocol, we propose a way for load-balancing in interactive rendering environments. For this work, we implemented a parallel rendering system and took different picking strategies into account to compare the results. The advantage of our approach compared to other approaches is that we group the available nodes of a cluster into two different categories, based on the hardware abilities. Some nodes are used solely for rendering, while others serve as secondary storage and to assist the former ones by performing auxiliary calculations. AU - Suess, Tim AU - Wiesemann, Timo AU - Fischer, Matthias ID - 18289 SN - 9781424481330 T2 - 2010 IEEE Fifth International Conference on Networking, Architecture, and Storage TI - Evaluation of a c-Load-Collision-Protocol for Load-Balancing in Interactive Environments ER - TY - CHAP AB - Typischerweise sind die Knoten eines PC-Clusters nicht mit leistungsfähigen Grafikkarten ausgestattet. Dennoch bieten Cluster-Betreiber einige wenige Rechenknoten an, die mit Highend-Grafikkarten ausgestattet sind, um beispielsweise eine PowerWall zu betreiben. Wenn zwischen diesen unterschiedlichen Knotentypen ein schnelles Netzwerk existiert, kann die Bilderzeugung durch die Knoten mit schwacher Grafikkarte beschleunigt werden. Dabei können die unterschiedlichen Knotentypen unterschiedliche Aufgabe bearbeiten. In einem solchen heterogenen System, müssen die unterschiedlichen entstehenden Lasten auf andere Weise verteilt werden, als in einem System, bei dem alle Knoten gleich ausgestattet sind. Wir präsentieren in dieser Arbeit Lastbalancierungsmechanismen, die in einem parallelen Out-of-Core-Renderingsystem für heterogene PC-Cluster eingesetzt werden. AU - Suess, Tim AU - Wiesemann, Timo AU - Fischer, Matthias ID - 18290 T2 - Augmented & Virtual Reality in der Produktentstehung TI - Gewichtetes c-Collision-Protokoll zur Balancierung eines parallelen Out-of-Core-Renderingsystems ER - TY - CONF AU - Meyer auf der Heide, Friedhelm AU - Phillips, Cynthia A. ID - 16414 SN - 9781450300797 TI - Proceedings of the 22nd ACM symposium on Parallelism in algorithms and architectures - SPAA '10 ER - TY - CHAP AB - We present an approach for real-time rendering of complex 3D scenes consisting of millions of polygons on limited graphics hardware. In a preprocessing step, powerful hardware is used to gain fine granular global visibility information of a scene using an adaptive sampling algorithm. Additively the visual influence of each object on the eventual rendered image is estimated. This influence is used to select the most important objects to display in our approximative culling algorithm. After the visibility data is compressed to meet the storage capabilities of small devices, we achieve an interactive walkthrough of the Power Plant scene on a standard netbook with an integrated graphics chipset. AU - Eikel, Benjamin AU - Jähn, Claudius AU - Fischer, Matthias ID - 16505 SN - 0302-9743 T2 - Advances in Visual Computing TI - Preprocessed Global Visibility for Real-Time Rendering on Low-End Hardware ER - TY - CHAP AU - Degener, Bastian AU - Kempkes, Barbara AU - Kling, Peter AU - Meyer auf der Heide, Friedhelm ID - 16365 SN - 0302-9743 T2 - Structural Information and Communication Complexity TI - A Continuous, Local Strategy for Constructing a Short Chain of Mobile Robots ER - TY - CONF AU - Degener, Bastian AU - Kempkes, Barbara AU - Meyer auf der Heide, Friedhelm ID - 16401 SN - 9781450300797 T2 - Proceedings of the 22nd ACM symposium on Parallelism in algorithms and architectures - SPAA '10 TI - A local O(n2) gathering algorithm ER - TY - BOOK ED - Abramsky, Samson ED - Gavoille, Cyril ED - Kirchner, Claude ED - Meyer auf der Heide, Friedhelm ED - Spirakis, Paul G. ID - 16403 SN - 0302-9743 TI - Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part II. ER - TY - BOOK ED - Abramsky, Samson ED - Gavoille, Cyril ED - Kirchner, Claude ED - Meyer auf der Heide, Friedhelm ED - Spirakis, Paul G. ID - 16404 SN - 0302-9743 TI - Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I. ER - TY - THES AU - Lürwer-Brüggemeier, Katharina ID - 19605 TI - Mächtigkeit und Komplexität von Berechnungen mit der ganzzahligen Division VL - 261 ER - TY - THES AU - Mense, Mario ID - 19614 SN - 978-3-939350-79-8 TI - On Fault-Tolerant Data Placement in Storage Networks VL - 260 ER - TY - THES AU - Kortenjan, Michael ID - 19617 SN - 978-3-939350-77-4 TI - Size Equivalent Cluster Trees - Rendering CAD Models in Industrial Scenes VL - 258 ER -