Abstract
This paper studies load balancing issues for classes of problems with certain bisection properties. A class of problems has α-bisectors if every problem in the class can be subdivided into two subproblems whose weight (i.e. workload) is not smaller than an α-fraction of the original problem. It is shown that the maximum weight of a subproblem produced by Algorithm HF, which partitions a given problem into N subproblems by always subdividing the problem with maximum weight, is at most a factor of ⌈1/α⌋ · (1−α)⌈1/α⌋−2 greater than the theoretical optimum (uniform partition). This bound is proved to be asymptotically tight. Two strategies to use Algorithm HF for load balancing distributed hierarchical finite element simulations are presented. For this purpose, a certain class of weighted binary trees representing the load of such applications is shown to have 1/4-bisectors. The maximum resulting load is at most a factor of 9/4 larger than in a perfectly uniform distribution in this case.
Chapter PDF
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Stefan Bischof, Ralf Ebner, and Thomas Erlebach. Load Balancing for Problems with Good Bisectors, and Applications in Finite Element Simulations: Worst-case Analysis and Practical Results. SFB-Bericht 342/05/98 A, SFB 342, Institut für Informatik, Technische Universität München, 1998. http://wwwmayr.in.tum.de/berichte/1998/TUM-I9811.ps.gz.
Dietrich Braess. Finite Elemente. Springer, Berlin, 1997. 2. überarbeitete Auflage.
Greg N. Frederickson. Optimal Algorithms for Tree Partitioning. In Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms SODA ’91, pages 168–177, New York, 1991. ACM Press.
Reiner Hüttl. Ein iteratives Lösungsverfahren bei der Finite-Element-Methode unter Verwendung von rekursiver Substrukturierung und hierarchischen Basen. PhD thesis, Institut für Informatik, Technische Universität München, 1996.
Behrooz A. Shirazi, Ali R. Hurson, and Krishna M. Kavi. Scheduling and Load Balancing in Parallel and Distributed Systems. IEEE Computer Society Press, Los Alamitos, CA, 1995.
Thomas Schnekenburger and Georg Stellner, editors. Dynamic Load Distribution for Parallel Applications. TEUBNER-TEXTE zur Informatik. Teubner Verlag, Stuttgart, 1997.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bischof, S., Ebner, R., Erlebach, T. (1998). Load balancing for problems with good bisectors, and applications in finite element simulations. In: Pritchard, D., Reeve, J. (eds) Euro-Par’98 Parallel Processing. Euro-Par 1998. Lecture Notes in Computer Science, vol 1470. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0057878
Download citation
DOI: https://doi.org/10.1007/BFb0057878
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64952-6
Online ISBN: 978-3-540-49920-6
eBook Packages: Springer Book Archive