پارادایم برده اصلی در سیستم های ناهمگن: یک روش برنامه ریزی پویا برای نقشه برداری بهینه

We study the master–slave paradigm over heterogeneous systems. According to an analytical model, we develop a dynamic programming algorithm that allows to solve the optimal mapping for such paradigm. Our proposal considers heterogeneity due both to computation and also to communication. The optimization strategy used allows to obtain the set of processors for an optimal computation. The computational results show that considering heterogeneity also on the communication increases the performance of the parallel algorithm.

Cluster Systems are playing an important role in High Performance Computing due to the low cost and availability of commodity PCs networks. A typical resource pool comprises heterogeneous commodity PCs and complex servers. The parallel standard libraries allow an easy portability of the parallel programs to the cluster contributing also to the increasingly consideration of these architectural solutions. However, a disappointing handicap appears with the behavior of the real running time of the applications. Most of the programs have been developed under the assumption of an homogeneous target architecture and this assumption has been also followed by most of the analytical and performance models [1] and [2]. This models cannot be directly applied to the heterogeneous environments. We revisit in this paper the mapping problem for master–slave algorithms under this new heterogeneous context. Some authors [3] broach the same problem but consider heterogeneity due only to the difference in processing speeds of workstations. However, it is a stated fact that the heterogeneity in the speed of workstations can have a significant impact on the communication send/recv overhead [4], even when the communication capabilities of the processors are the same. Our proposals consider heterogeneity due both to computation and communication, what provides a very general overview of the system and a very wide range of applicability. The master–slave paradigm has been extensively studied and modeled in homogeneous architectures [5], [6], [7] and [8]. However the modelization of this paradigm on heterogeneous platforms is still an open question. A very good work that studies the scheduling of parallel loops at compile time in heterogeneous systems was presented in [9]. They cover both homogeneous and heterogeneous systems and regular and irregular computations, giving optimal or near optimal solutions. An analytical model and a strategy for an optimal distribution of the tasks on a master–slave paradigm has been presented in [10]. However the accuracy of the predictions with their model is still to be proved. In [3] the authors provide effective models in the framework of heterogeneous computing resources for the master–slave paradigm. They formulate the problem and approach different variants but they consider heterogeneity only due to differences in the processing speed of the workstations. In [11] a very elegant structural model has been presented to predict the performance of master–slave algorithms on heterogeneous systems. The model is quite general and covers most of the situations appearing in practical problems. The structural model can be viewed as an skeleton where the models for master–slave applications with different implementations or environments must be instantiated. The main drawback of the approach is that the instantiation of the model for the particular cases is not a trivial task. It does not find optimal distribution of works among the processors. In [12] we presented an analytical model that predicts the execution time of master–slave algorithms on heterogeneous systems. The model includes heterogeneity due both to computation and to communication. Our proposal covers some of the variants studied in [3] and [11]. The computational results prove the efficiency of our scheme and the accuracy of the predictions. The scheduling problem for master–slave computations has been extensively studied in many of the aforementioned works, however, most of these works consider the problem of the distribution of work over a set of fixed processors. We claim that to solve the optimal scheduling, the set of processors must be considered also as a parameter in the minimization problem. The predictive ability of the model that we propose in [12] constitutes the basis for further studies for the master–slave paradigm. The main contribution of this work is the development of an optimal mapping strategy for master–slave computations based in the analytical model introduced in [12]. In particular, this analytical model allows to formulate the problem as a resource optimization problem that has been studied in depth [13]. According to this formulation we derive strategies for the optimal assignment of tasks to processors. Our proposal improves the classical approach of assigning tasks of size proportional to the processing power of each processor and includes the elements to obtain the set of processors for an optimal computation. The paper is organized as follows. Section 2 introduces the heterogeneous network model and some notation used along the paper. Section 3 specifies the problem and describes an inductive analytical model that predicts the running time of a master–slave program in an heterogeneous cluster of PCs for a given distribution of work. This analytical model has been validated in Section 4. The problem of finding the optimal distribution of work among the processors (the mapping problem) is studied in Section 5. Based on the analytical model presented in Section 3 we propose a general approach that formulates the mapping problem as a particular instance of the Resource Allocation Problem (RAP). We solve this optimization problem using a dynamic programming algorithm. The dynamic programming approach allows also to solve the problem of finding the optimal number of processors. The computational results presented in Section 6 prove that considering heterogeneity on the communication capabilities increases the quality of the predictions. The paper is finished in Section 7 with some concluding remarks and future lines of work.

We have proposed an algorithmic approach to solve the optimal mapping problem of master–slave algorithms on heterogeneous systems. The algorithmic approach considers an exact dynamic programming algorithm based on an inductive analytical model. The dynamic programming algorithm solves the general resource allocation optimization problem involved into a master–slave computation. Through the sensitive analysis, the optimal set of processors can also be determined. There are several challenges and open questions to broach in the incoming future. Although the class of master–slave problems considered represents a wide range of problems, the master–slave programs where the results are accepted from the slave as soon as they are available, are not well modeled with this model. We plan to develop the same methodology with the aim of covering this class of problems also. This methodology can be introduced into a tool to provide the optimal mapping of master–slave algorithms over heterogeneous platforms following the algorithmic strategies proposed.