Title :
The impact of task-length parameters on the performance of the random load-balancing algorithm
Author :
Ben-Asher, Yosi ; Cohen, Avid ; Schuster, Assaf ; Sibeyn, Jop F.
Author_Institution :
Dept. of Math. & Comput. Sci., Haifa Univ., Israel
Abstract :
Considers the problem of dynamic load balancing in an n processors parallel system. The authors focus on the algorithm which randomly assigns newly generated tasks to processors for execution. This process is modeled by randomly throwing weighted balls into n holes. For a given program A, the ball weights (task lengths) are chosen according to an unknown probability distribution D( A) with expectation μ, maximum M and minimum m . For any A, D(A) and a constant 0<∈⩽0.5, they derive an upper bound on the number of processes which A needs to generate in order for the algorithm to achieve optimal load balancing with very high probability, so that the run-time is optimal up to a factor of (1+∈)2. Using the relation derived, the programmer may control the load-balancing of his program by modifying the global parameters of the generated processes
Keywords :
parallel processing; performance evaluation; dynamic load balancing; n processors parallel system; random load-balancing; task-length parameters; Algorithm design and analysis; Computer science; Control systems; Load management; Optimal control; Probability distribution; Processor scheduling; Programming profession; Runtime; Upper bound;
Conference_Titel :
Parallel Processing Symposium, 1992. Proceedings., Sixth International
Conference_Location :
Beverly Hills, CA
Print_ISBN :
0-8186-2672-0
DOI :
10.1109/IPPS.1992.223067