Using an evolutionary approach based on shortest common supersequence problem for loop fusion

In the literature, loop fusion is an effective optimization technique which tries to enhance parallelizing compilers’ performance via memory hierarchy management, and all its competing criteria create an NP-hard problem. This paper proposes an evolutionary algorithm that aims to achieve a profitable loop order which maximizes fusion taking into account register size, parallelism and data reuse advancement. Besides, this method preserves prerequisite relations between the loops by encoding each distinct loop sequence as the shortest common supersequence (SCS) of the related dependence graph. Regarding the related optimization methods that only focus on fusion, this set of metrics, an evolutionary algorithm and also the shortest common supersequence problem have not been considered before in this area. Despite all the envisaged complexities, experimental results confirm the accuracy and advantage of the proposed approach. But due to evolutionary methods effect on raising the compilation time, the proposed algorithm is only applicable when this issue is not prominent, in comparison with the quality of the outcome.