Newsgroups: comp.parallel From: dhenrich@ira.uka.de (Dominik Henrich -4265) Subject: Re: load balancing for SIMD Organization: University of Karlsruhe, FRG Date: Wed, 25 Aug 1993 16:57:46 +0200 ------------From: Dominik Henrich Please, can anyone point me out references, articles, etc. about load balancing for *SIMD* architectures. I will summarize the responses if appropriate. Thanks very much to everybody who answered! Here are the responces: -------------From: Chris Kuszmaul The earliest reference with which I am familier is an ICASE report by Sherry Tomboulian. It talks about doing it for Mandelbrot set computation (it would apply to PDE solvers as well). The key words Mandelbrot, SIMD, load balancing, and indirect addressing should get you there. -------------From: Craig Farrell We published a short paper about SIMD load balancing in the 1993 Parle conf proceedings. Munich Germany. The paper was called "Load balanced Optimisation of Virtualised Algorithms for Implementation on Massively Parallel SIMD Architectures" by Farrell and Kieronska. -------------From: Claus Bendtsen I'll suggest you'll take a look at: Report#.... TR-197 Author..... Frye, R. Title...... Load Balancing Algorithms on the Connection Machine and Their Use in Monte-Carlo Methods Date....... 5/91 Available from, Thinking Machines Corporation Technical Reports and Published Papers email: t-rex@think.com January 1993 It is presently not available in postscript or tex format at anonymous ftp to think.com but if you ask politely they might just put it there. -------------From: David Nicol @inproceedings{nicol-shpcc-1992, author = "D. Nicol", title = "Communication Efficient Global Load Balancing", booktitle = "Proceedings of the 1992 Scalable High Performance Computing Conference", publisher = "IEEE Press", month = "April", year = "1992", page = "292-299" } This describes a solution of perfectly redistributing a set of independent non-communicating equi-weight work units so as to minimize communication costs. It uses parallel prefix-sums and -maxs like there's no tomorrow. Many obvious extensions left to do. I've just recently worked out SIMD remapping in the context of chain-like computations, but have yet to write it up. -------------From: Jan Prins Here is a reference to a class of load-balancing algorithms that is suited to fine-grain multi-dimensional mesh machines, specifically including SIMD machines (the experimental results described were obtained from a MasPar MP-1). Eduardo S. Biagioni, "Scan-Directed Load Balancing", Ph.D. Thesis, University of North Carolina at Chapel Hill, Computer Science Dept. TR91-045 to obtain postscript of this thesis send mail to "netlib@cs.unc.edu" with subject "send 91-045.ps from techreports" an earlier version of this work also appears in E. Biagioni and J. Prins, "Scan-Directed Load Balancing for Mesh-Connected Highly Parallel Computers", in _Unstructured Scientific Computation on Scalable Multiprocessors_, MIT Press, 1992. -----------From: reusch@mpread.co.uk Tomboulian S., Pappas M., 1990, "Indirect Addressing and Load Balancing for Faster Solutions to Mandelbrot Set on SIMD Architectures" The third Symposium on the Frontiers of Massively Parallel Computation, College Park, MD, Oct 8.-10. and Biagioni E. S., Prins J. F., "Scan Direct Load-Balance for Highly-Parallel Mesh-Connected Computer" In: Unstructures Scientific Computation on Scalable Multiprocessores, MIT Pres, 1991 - Dominik Henrich ************************************************************** Dominik Henrich, Dipl.-Inform. Institute for Real-Time Computer Systems and Robotics (IPR) Department of Computer Science, University of Karlsruhe P 69 80, Kaiserstrasse 12 phone: +49 721 608-4265 D-76128 Karlsruhe facsimile: +49 721 60 67 40 F. R. of Germany e-mail: dhenrich@ira.uka.de **************************************************************