Cyril Banino
Norwegian University
of Science and Technology (NTNU)
Dept. of Computer and Info. Science (IDI)
Trondheim, Norway
email: Cyril.Banino@idi.ntnu.no
In this paper, we consider the problem of allocating a large number of independent, equal-sized tasks to a large-scale heterogeneous ``Grid'' computing platform. We use a non-oriented graph to model a grid, where resources can have different speeds of computation and communication, as well as different overlap capabilities. Because spanning trees are easier to deal with in practice, we will also consider tree-shape platforms.
While most previous studies using the master-worker paradigm rely on both trees and graphs for modeling the heterogeneous platform, they usually make the assumption that the master initially resides at one given place. A natural question then arises: where should we place the master in order to maximize the steady-state throughput of the platform? We show that this problem is NP-hard, but still introduce and compare several low-cost heuristics to determine a sub-optimal master placement.
Although the master-worker paradigm provides a practical and flexible framework for processing independent equal-sized tasks onto heterogeneous platforms, this approach has however, a significant drawback in a large-scale environment: since all tasks are farmed out by one master, it does not let the system scale well in large systems. Indeed, we show that for any communication-to-computation ratio, there exist heterogeneous networks for which the optimal steady-state throughput obtained using a master-worker approach is arbitrarily bad compared to the total theoretical computing power that the platform could deliver. We consequently claim that the use of several masters is necessary to achieve good performance on large-scale platforms.
Key Words: Grid computing, master-worker paradigm, steady-state,
scalability, complexity.