Parallelizing by Smart Tiling

Abstract

The paper is devoted to the methods of automatic parallelization and software optimization. The authors focus on parallelizing of computational loops. The problem of quickly choosing a partitioning method and determining its parameters is an urgent task. Its solution provides a reduction in software’s execution time for computing systems with multiprocessor architecture. To build an automated system for parallelizing programs, the authors propose to use Discrete Particle Swarm Optimization Method as an optimization method which allows to find a local or global minimum of program execution time regarding complicated relationship between tile sizes and execution time. The paper proposes an approach to optimizing the process of partitioning the iterative space of loop operators using the methods of Swarm Intellect. It uses partitioning by rectangular parts but has no fundamental restrictions on its use for other types of partitioning (triangles, parallelograms, rhombuses, etc.). Proposed method is called Smart Tiling Method.