The problem of load balancing parallel applications is particularly challenging on computational grids, since the characteristics of both the application and the platform must be taken into account. This chapter reviews the wide range of solutions that have been proposed. It considers tightly coupled parallel applications that can be described by an undirected graph representing concurrent execution of tasks and communication of tasks, executing on computational grids with static and dynamic network and processor performance. While a rich set of solution techniques have been proposed, there has not been of yet any performance comparisons between them. Such comparisons will require parallel benchmarks and computational grid emulators and simulators.
Since heterogeneous computing is a broad research area and there are many definitions of computational grids, we define the characteristics of the applications and platforms that we are considering.
Key Terms in this Chapter
Resource-Aware Load Balancing: Assignment of tasks to a computational platform, taking into account its heterogeneous characteristics, with the objective of balancing the work assigned to processors. The tasks may be independent, or may have interdependencies described in a graph or digraph. In the latter case an additional objective is to minimize communication between processors. The assignment may be static, that is decided before tasks execute, or dynamic, that is tasks are assigned as conditions change.
Dynamic Load Balancing: Assignment of tasks to a computational platform, with the objective of balancing the work assigned to processors. When the tasks are interdependent an additional objective is to minimize communication between processors. The load balance is monitored during execution of the application, and the assignment is modified if required, while trying to minimize the communication cost of migrating tasks.
High Capacity Computational Grid: A grid platform dedicated to high performance computing (HPC) applications and generally consisting of an aggregation of multiple HPC clusters. These grids are space-shared, that is processors only execute a single user’s process(es) at a time. The clusters may be located in one organization, or they may be more spread out geographically, which can pose additional problems of high latencies.
Static Load Balancing: Assignment of tasks to a computational platform, before execution takes place, with the objective of balancing the work assigned to processors. When the tasks are interdependent an additional objective is to minimize communication between processors. This assignment is then fixed for the duration of the computation.
Graph Partitioning: In the context of parallel computing, the partitioning of a graph (representing concurrent execution of tasks and communication between tasks) into disjoint subgraphs, where the communication between subgraphs is minimized and the load is roughly balanced.
High Throughput Computational Grid: A grid platform that aims to take advantage of spare compute cycles on processing nodes. These nodes may be dedicated to multiple users at the same time and hence are time-shared. These grids can consist of local or global networks of computers, and can be either within one organization or be simply a collection of individual computers on the Internet.
Heterogeneous Computing: Design and implementation of algorithms for computing platforms with heterogeneous characteristics, such as processor and network performance.
Complete Chapter List
Emmanuel Udoh, Frank Zhigang Wang
Emmanuel Udoh, Frank Zhigang Wang, Vineet R. Khare
Enis Afgan, Purushotham Bangalore
Kuo-Chan Huang, Po-Chi Shih, Yeh-Ching Chung
Gianni Pucciani, Flavia Donno, Andrea Domenici, Heinz Stockinger
Ming Wu, Xian-He Sun
Zhihui Du, Zhili Cheng, Xiaoying Wang, Chuang Lin
Kris Bubendorfer, Ben Palmer, Ian Welch
Sandro Fiore, Alessandro Negro, Salvatore Vadacca, Massimo Cafaro, Giovanni Aloisio, Roberto Barbera
Man Wang, Zhihui Du, Zhili Cheng
Vineet R. Khare, Frank Zhigang Wang
Yuhui Deng, Frank Zhigang Wang, Na Helian
Dominic Cherry, Maozhen Li, Man Qi
Maozhen Li, Man Qi, Bin Yu
Irfan Habib, Ashiq Anjum, Richard McClatchey
Kurt Vanmechelen, Jan Broeckhove, Wim Depoorter, Khalid Abdelkader
Rosario M. Piro
Frans Arickx, Jan Broeckhove, Peter Hellinckx, David Dewolfs, Kurt Vanmechelen
Gabriel Aparicio, Fernando Blanco, Ignacio Blanquer, César Bonavides, Juan Luis Chaves, Miguel Embid, Álvaro Hernández
Gerald Schaefer, Roger Tait
Daniele Andreotti, Armando Fella, Eleonora Luppi
Roberto Barbera, Valeria Ardizzone, Leandro Ciuffo
Dirk Gorissen, Tom Dhaene, Piet Demeester, Jan Broeckhove
Gokop Goteng, Ashutosh Tiwari, Rajkumar Roy
Hai Jin, Li Qi, Jie Dai, Yaqin Luo