On Characterizing the Data Movement Complexity of Computational DAGs for Parallel Execution

Technology trends are making the cost of data movement increasingly dominant, both in terms of energy and time, over the cost of performing arithmetic operations in computer systems. The fundamental ratio of aggregate data movement bandwidth to the total computational power (also referred to the machine balance parameter ) in parallel computer systems is decreasing. It is there- fore of considerable importance to characterize the inherent data movement requirements of parallel algorithms, so that the minimal architectural balance parameters required to support it on future systems can be well understood. In this paper, we develop an extension of the well-known red-blue pebble game to develop lower bounds on the data movement complexity for the parallel execution of computational directed acyclic graphs (CDAGs) on parallel systems. We model multi-node multi-core parallel systems, with the total physical memory distributed across the nodes (that are connected through some interconnection network) and in a multi-level shared cache hierarchy for processors within a node. We also develop new techniques for lower bound characterization of non-homogeneous CDAGs. We demonstrate the use of the methodology by analyzing the CDAGs of several numerical algorithms, to develop lower bounds on data movement for their parallel execution.Avec les technologies actuelles, le coût d'une communication (autant en terme de temps que d'énergie) devient de plus en plus dominant face au coût de calcul. Le ratio entre bande passante et puissance de calcul ("machine balance parameter" en anglais) dans les systèmes parallèles ne fait que décroître. Il est donc fondamental de savoir caractériser la complexité d'une application en terme de nombre de mouvements de données minimal. Cet article développe une extension du jeu des pions rouges et noirs ("red-blue pebble game") afin de dériver des bornes inférieures sur la complexité de communication d'un graphe de tâches acyclique (CDAG) dans un environnement de calcul distribué. Les systèmes modélisés à cet effet sont des multi-coeurs à mémoire distribuées, ainsi que des multi-coeurs à mémoire partagée. Les techniques développées s'appliquent à des CDAG non homogènes. Nous illustrons la méthodologie à travers l'analyse de CDAGs de plusieurs algorithmes, dérivant ainsi des bornes inférieures sur leur complexité de communication sur machines distribuées