Efficient Program Partitioning Based on Compiler COntrolled COmmunication

摘要

In this paper, we present an efficient framework for intraprocedural performance based program patitioning for sequential loop nests. Due to the limitations of static dependence analysis especiaally in the inter-procedural sense, many loop nests are identified as sequential but available task parallelism amongst them could be potentially exploited. SInce this available parallelism is quite limited, performance based program analysis and partitioning which carefully analyzes the interaction between the loop nests and the underlying architectural characteristics must the undertaken to effectively use this parallelism. We propose a ocmpiler driven approach that configures underlying architecture to support a given communication mechanism. We then devise an iterative program partitioning algorithm that generates efficient program partitioning by analyzing interaction between effective cost of communication andthe corresponding partitions. We model this problem as one of partitioning a directed acyclic task graph in which each node is identified with a sequential loop nest an the edges denote the precedences and communication betwee nthe nodes corresponding to data transfer between loop nests. We introduce the concept of behavioral edges between edges and nodes in the task graph for capturing the interactions between ocmputation and ocmmunication through parametric functions. We present an efficient interative partitioining algorithm using the behavioral edge augmented PDG to increementally compute and improve the schedule. A significant performance improvement is demosnstrated by using our framework on soem applciation which exhibit this type of parallelism.