Scalability limits of Bag-of-Tasks applications running on hierarchical platforms

Bag-of-Tasks applications are parallel applications composed of independent (i.e., embarrassingly parallel) tasks, which do not communicate with each other, may depend upon one or more input files, and can be executed in any order. Each file may be input for more than one task. Examples of Bag-of-Tasks (BoT) applications include Monte Carlo simulations, massive searches (such as key breaking), image manipulation applications and data mining algorithms. A common framework to execute BoT applications is the master–slave topology, in which the user machine is used to control the execution of tasks. In this scenario, a large number of concurrent tasks competing for resources (e.g., CPU and communication links) severely limits application execution scalability. This paper is devoted to study the scalability of BoT applications running on multi-node systems (such as clusters and multi-clusters) organized as hierarchical platforms, considering several communication paradigms. Our study employs a set of experiments that involves the simulation of various large-scale platforms. The results presented provide important guidelines for improving the scalability of practical applications.

► Scalability analysis of BoT applications on hierarchically organized platforms.
► Determination of lower bounds on the isoefficiency function for several topologies.
► Determination of absolute lower bounds for several communication models.
► Evaluation of the impact of output file transfer contention on scalability.
► Extension of results to heterogeneous platforms.