Optimization of Data Distribution and Processor Allocation Problem Using Simulated Annealing

In this study, a global optimization meta-heuristic is developed for the problem of determining the optimum data distribution and degree of parallelism in parallelizing a sequential program for distributed memory machines. The parallel program is considered as the union of consecutive stages and the method deals with all the stages in the entire program rather than proposing solutions for each stage. The meta-heuristic developed here for this specific problem combines simulated annealing and hill climbing (SA-HC) in the search for the optimum configuration. Performance is tested in terms of the total execution time of the program including communication and computation times. Two exemplary codes from the literature, the first being computation intensive and the second being communication intensive, are utilized in the experiments. The performance of the SA-HC algorithm provides satisfactory results for these illustrative examples.