kale%kale.cs.uiuc.edu@a.cs.uiuc.edu (L. V. Kale') (04/05/89)
In response to a recent posting regarding dynamic load balancing: We have been refining a dynamic load balancing strategy for small grained (currently about 1-10-100 msec) "tasks" for past few years (in conjunction with our development of the machine independent parallel programming syste: the Chare Kernel) and parallel Prolog. The scheme runs on hypercube (iPSC/2 64 nodes, currently) and our simulator. It is called "Adaptive Contracting Within Neighborhood" (ACWN). Its predecessor scheme (CWN) was published in icpp 88. The new scheme is written up in an upcoming tech. report, and I can send a draft/final TR for anyone interested. ACWN routinely outperforms gradient model and randomized allocation, two of the schemes which have similar assumptions as us. (small grain-size, no migration of running tasks). The icpp reference is: %A L. V. Kale %T Comparing the Performance of Two Dynamic Load Distribution Methods %D August 1988 %J Proceedings of the International Conference on Parallel Processing %C St. Charles Incidentally, the words "dynamic load balancing" mean different things to different people.(We really need to invent different names for these.) The "relatively fine-grained, large-number-of-processors" problem is much different than the much explored "relatively large-grain, few-processors (on a LAN?), migration ok" problem. In the latter, one is typically talking about performance (throughput, response time) in a multiprogramming system, whereas the former is oriented more towards (particular forms of) parallel processing. The fuzziness above is intentional. They do overlap. Real time scheduling (dynamic) is yet another ballgame, again with overlaps. L.V. Kale (kale@cs.uiuc.edu) Dept. of Computer Science University of Illinois at Urbana-Champaign 1304 W. Springfield Ave. Urbana, IL-61801 (217) 244-0094