Document Type
Report
Date
8-1991
Keywords
Interconnection Networks, Load Balancing, Multicomputer Systems, Network Partitioning, Parallel Processors, Performance Evaluation, Task Scheduling
Language
English
Disciplines
Computer Sciences
Description/Abstract
This paper presents a semi-distributed approach, for load balancing in large parallel and distributed systems, which is different from the conventional centralized and fully distributed approaches. The proposed strategy uses a two-level hierarchical control by partitioning the interconnection structure of a distributed or multiprocessor system into independent symmetric regions (spheres) centered at some control points. The central points, called schedulers, optimally schedule tasks within their spheres and maintain state information with low overhead. We consider interconnection structures belonging to a number of families of distance transitive graphs for evaluation, and using their algebraic characteristics, show that identification of spheres and their scheduling points is, in general, an NP-complete problem. An efficient solution for this problem is presented by making an exclusive use of a combinatorial structure known as the Hadamard Matrix. Performance of the proposed strategy has been evaluated and compared with an efficient fully distributed strategy, through an extensive simulation study. In addition to yielding high performance in terms of response time and better resource utilization, the proposed strategy incurs less overhead in terms of control messages. It is also shown to be less sensitive to the communication delay of the underlying network.
Recommended Citation
Ahmad, Ishfaq and Ghafoor, Arif, "Semi-Distributed Load Balancing for Massively Parallel Multicomputer Systems" (1991). Electrical Engineering and Computer Science - Technical Reports. 103.
https://surface.syr.edu/eecs_techreports/103
Source
local
Additional Information
School of Computer and Information Science, Syracuse University, SU-CIS-91-30