Task Percolation: Adaptive Load Distribution in a Distributed Environment

Julian R. Dermoudy
Department of Computer Science, University of Tasmania, GPO Box 252C Hobart, Tasmania, 7001, Australia.
J.R.Dermoudy@cs.utas.edu.au

Abstract

Multicomputers consist of disjoint memory and processor pairs connected by some network. Given a program suitable for concurrent execution, the concurrent tasks could be distributed to all available processors in order to reduce overall execution time. Further, if the number of available processors exceeds the number of tasks requiring execution it is advantageous to employ these otherwise idle processors on other work.

Load distribution is the (usually) decentralised process of allocating tasks to the available processors. To be effective, the load distribution algorithm must not hinder the program evaluation in any way Q either by slowing the processors or by TcloggingU the communications network. Additionally, to maximise effectiveness the load distribution algorithm should retain for local execution tasks which will be Tshort-livedU as well as those with high data dependence.

We present a general, efficient, non-intrusive, adaptive Tinformed-receiverU-initiated load distribution algorithm that allocates tasks to the available processors of a multicomputer network. The algorithm assumes prioritised tasks and its implementation on a network of Transputers includes a speculative evaluation scheme. The algorithm is presented in context together with several load distribution scenarios, and an argued justification of its suitability.

Conference Home Page