ابتکارات برای توزیع کار از یک طرح همگن برنامه ریزی پویا موازی در سیستم های ناهمگن

In this paper the possibility of including automatic optimization techniques in the design of parallel dynamic programming algorithms in heterogeneous systems is analyzed. The main idea is to automatically approach the optimum values of a number of algorithmic parameters (number of processes, number of processors, processes per processor), and thus obtain low execution times. Hence, users could be provided with routines which execute efficiently, and independently of the experience of the user in heterogeneous computing and dynamic programming, and which can adapt automatically to a new network of processors or a new network configuration.

Automatic tuning techniques have been used in the design of parallel routines in recent years. Techniques have been developed in different fields [1] and [2], and especially in linear algebra routines [3], [4] and [5]. The selection of appropriate values of some parameters which influence the execution time of the algorithm in parallel homogeneous systems has been analyzed in previous works. Linear algebra routines [4] and a Dynamic Programming Scheme [6] have been studied. In this paper the possibility of applying the automatic optimization techniques studied for homogeneous systems to heterogeneous networks is analyzed. In this new scenario the decisions to be taken to reduce the execution time are: the processors to use, the number of processes and their distribution in the processors system. In that way, the ideas previously presented for homogeneous systems are used in combination with a problem of assignation of tasks to processors. Section 2 analyzes the necessary modifications to the methodology used for homogeneous systems to adapt it to heterogeneous networks. In Section 3 the use of these ideas in a Dynamic Programming Scheme is considered. Experimental results and the results of some simulations are shown in Sections 4 and 5. Finally, Section 6 presents some conclusions.

The application of auto-optimization techniques to Parallel Dynamic Programming Schemes in heterogeneous systems has been considered. The scheme of the “coins problem” has been used to study the proposed methodology, and the method has been tested in two networks of processors. The experiments confirm that with the use of auto-optimization techniques, reduced execution times can be obtained with no user intervention, but more sophisticated selection methods are necessary to improve the selections in very complex heterogeneous systems. The optimization problem could be improved by better theoretical models and more experiments. The lower and upper bound execution formulas used to eliminate nodes in the tree must also be improved in order to reduce the time needed to solve the optimization problem. The optimization problem has not been included in the parallel routine yet, but from the experiments it seems possible to combine these and to make parameter selections both at installation and running time. The application of the methodology to other Parallel Dynamic Programming Schemes and to Linear Algebra algorithms is being considered. The suitable modifications to make the method applicable in variable load systems are being analyzed also.