Improving scalability of Bag-of-Tasks applications running on master–slave platforms

Bag-of-Tasks applications are parallel applications composed of independent tasks. Examples of Bag-of-Tasks (BoT) applications include Monte Carlo simulations, massive searches (such as key breaking), image manipulation applications and data mining algorithms. This paper analyzes the scalability of Bag-of-Tasks applications running on master–slave platforms and proposes a scalability-related measure dubbed input file affinity. In this work, we also illustrate how the input file affinity, which is a characteristic of an application, can be used to improve the scalability of Bag-of-Tasks applications running on master–slave platforms. The input file affinity was considered in a new scheduling algorithm dubbed Dynamic Clustering, which is oblivious to task execution times. We compare the scalability of the Dynamic Clustering algorithm to several other algorithms, oblivious and non-oblivious to task execution times, proposed in the literature. We show in this paper that, in several situations, the oblivious algorithm Dynamic Clustering has scalability performance comparable to non-oblivious algorithms, which is remarkable considering that our oblivious algorithm uses much less information to schedule tasks.