@inproceedings{19016, abstract = {{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.}}, author = {{Gehweiler, Joachim and Meyerhenke, Henning}}, booktitle = {{Dagstuhl Seminar Proceedings 10261: Algorithm Engineering}}, title = {{{On Dynamic Graph Partitioning and Graph Clustering using Diffusion}}}, year = {{2010}}, } @techreport{19018, author = {{Thies, Michael and Gehweiler, Joachim}}, title = {{{Thread Migration and Checkpointing in Java}}}, year = {{2010}}, } @inproceedings{19023, author = {{Kernbach, Serge and Schmickl, Thomas and Hamann, Heiko and Stradner, Jürgen and Schlachter, Florian and Schwarzer, Christopher s. F. and Winfield, Alan F. T. and Matthias, Rene}}, booktitle = {{Artificial Life XII (ALife XII)}}, pages = {{781--788}}, publisher = {{MIT Press}}, title = {{{Adaptive Action Selection Mechanisms for Evolutionary Multimodular Robotics}}}, year = {{2010}}, } @inproceedings{19029, author = {{Briest, Patrick and Chalermsook, Parinya and Khanna, Sanjeev and Laekhanukit, Bundit and Nanongkai, Danupon}}, booktitle = {{Workshop on Internet and Network Economics (WINE)}}, isbn = {{9783642175718}}, issn = {{0302-9743}}, title = {{{Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing}}}, doi = {{10.1007/978-3-642-17572-5_37}}, year = {{2010}}, } @article{1903, author = {{Meyer auf der Heide, Friedhelm and Scheideler, Christian}}, journal = {{Informatik Spektrum}}, number = {{5}}, pages = {{468----474}}, title = {{{Algorithmische Grundlagen verteilter Speichersysteme}}}, doi = {{10.1007/s00287-010-0470-2}}, year = {{2010}}, } @inproceedings{19033, author = {{Briest, Patrick and Chawla, Shuchi and Kleinberg, Robert and Weinberg, S. Matthew}}, booktitle = {{Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms}}, isbn = {{9780898717013}}, title = {{{Pricing Randomized Allocations}}}, doi = {{10.1137/1.9781611973075.49}}, year = {{2010}}, } @phdthesis{19041, author = {{Mahlmann, Peter}}, isbn = {{978-3-942647-02-1}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}}, title = {{{Peer-to-peer networks based on random graphs}}}, volume = {{283}}, year = {{2010}}, } @phdthesis{19042, author = {{Degener, Bastian}}, isbn = {{978-3-939350-97-2 }}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}}, title = {{{Local, distributed approximation algorithms for geometric assignment problems}}}, volume = {{278}}, year = {{2010}}, } @inproceedings{18136, abstract = {{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.}}, author = {{Fischer, Matthias and Jähn, Claudius and Suess, Tim}}, booktitle = {{Eurographics Symposium on Parallel Graphics and Visualization (EGPGV)}}, pages = {{43--51}}, publisher = {{The Eurographics Association}}, title = {{{Asynchronous Parallel Reliefboard Computation for Scene Object Approximation}}}, doi = {{10.2312/EGPGV/EGPGV10/043-051}}, year = {{2010}}, } @inproceedings{18289, abstract = {{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.}}, author = {{Suess, Tim and Wiesemann, Timo and Fischer, Matthias}}, booktitle = {{2010 IEEE Fifth International Conference on Networking, Architecture, and Storage}}, isbn = {{9781424481330}}, pages = {{448 -- 456}}, title = {{{Evaluation of a c-Load-Collision-Protocol for Load-Balancing in Interactive Environments}}}, doi = {{10.1109/nas.2010.52}}, year = {{2010}}, }