A semi distributed task allocation strategy for large hypercube supercomputers

The authors present a semi-distributed approach for task scheduling in large parallel and distributed systems which is different from the conventional centralized and fully distributed approaches. The proposed strategy partitions the system into independent 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. The authors consider hypercube systems for evaluation and, using their algebraic characteristics, show that identification of spheres and their scheduling points is an NP-complete problem. The performance of the proposed strategy was evaluated and compared with an efficient fully distributed strategy. In addition to yielding high performance in terms of response time, better resource utilization, and throughput, the proposed strategy is shown to incur small overhead in terms of network traffic