Load balancing problem for parallel computers with distributed memory

Article type: Research Article

Authors: Čiegis, Raimondas | Šablinskas, Ramūnas | Šimkevičius, Juozas | Waśniewski, Jerzy

Affiliations: Institute of Mathematics and Informatics, Akademijos 4, 2600 Vilnius, Lithuania. Email: [email protected] | Vytautas Magnus University, Vileikos 8, 3000 Kaunas, Lithuania | The Danish Computer Center for Research and Education, UNI-C, DTH, Bldg. 305, DK-2800 Lyngby, Denmark

Abstract: This paper deals with load balancing of parallel algorithms for distributed-memory computers. The parallel versions of BLAS subroutines for matrix-vector product and LU factorization are considered. Two task partitioning algorithms are investigated and speed-ups are calculated. The cases of homogeneous and heterogeneous collections of computers/processors are studied, and special partitioning algorithms for heterogeneous workstation clusters are presented.

Keywords: parallel algorithms, load balancing, parallel virtual machine, distributed-memory computers

DOI: 10.3233/INF-1996-7301

Journal: Informatica, vol. 7, no. 3, pp. 281-294, 1996