Data Transfer Optimization for Pipelined Architecture with Hierarchical Memory

Koichi Nakamura, Department of Information Science, The University of Tokyo

Data transfer optimizations are important for architectures which have hierarchical memory structure, and approaches which aim to minimize summation of costs of transfer operations have been principal. However, since these approaches do not consider influences of pipeline execution of transfer operations and computations, optimized codes may have pipeline hazards. To achieve overall optimization, it is necessary to minimize not transfer cost but total execution time under pipeline execution.

This paper presents Modulo Scheduling with Copy-candidate Selection (MSCS), which integrates data transfer optimization based on copy-candidate selection and software pipelining, a scheduling method to minimize initiation interval of innermost loops. For the integration, we re-formalized copy-candidate selection problem as a sub-graph selection problem on Data Dependence Graph, and formulated our optimization problem using mixed integer linear programming model (MIP model). We can obtain an optimal data transfer procedure and a schedule by solving the MIP problem. In addition, MSCS can perform additional optimization (e.g., of power consumption, of amount of memory usage) by selecting objective function appropriately.

We show our experimental results for a massively parallel machine GRAPE-DR, and show that MSCS achieves optimization that is more efficient than previous transfer cost minimization methods.

Long Abstract

Back to Program