Accelerated Program Partitioning Algorithm ― An Improvement of Girkar's Algorithm ―

摘要

In this paper, we propose several heuristics that improve the branch and bound based program partitioning algorithm proposed by Girkar et. al, and indicate the effectiveness by experiments. The heuristic depends on the element order of edges of given task graphs deeply. Therefor, it is needed to sort edges pertinently for the effective use of the heuristic. The ways of sorting are investigated with experiments. As the results of the experiments, it turned out that approximate solutions, which provide enough practical partitionings, by accelerated heuristic is obtained, and execution times and errors to optimal solutions decrease considerably by sorting edges.