Enhancing locality in two-dimensional space through integrated computation and data mappings

As the number of processors used in chip multiprocessors keeps increasing, NoC (Network-on-Chip) based multiprocessor architectures are becoming increasingly important. While the last couple of years have witnessed numerous proposals regarding how to architect NoC based parallel computing platforms, code and data mapping issues in these architectures have largely been ignored. In particular, there are very few papers so far focusing on providing compiler support for NoC based chip multiprocessor systems. Our goal in this paper is to demonstrate how an optimizing compiler can map data and computation to NoC nodes in a locality-aware manner such that the energy spent in data communications is minimized. The proposed approach formulates this locality problem within a linear algebraic framework and discusses two alternate solution strategies that determine appropriate computation/data mappings in NoC. Our experimental evaluation compares this proposed scheme against two alternate optimization strategies, one that optimizes data mapping alone and the other one that optimizes computation mapping alone. The collected results indicate that our approach improves energy consumption by about 25% with respect to a scheme that does not consider locality of communication during NoC mapping. More importantly, our results reveal that neither optimized data mapping alone nor optimized computation mapping alone is sufficient for achieving the best locality and the compiler needs to consider both in a coordinated fashion. In fact, our results show that the proposed approach improves energy consumption over the pure data mapping and pure computation mapping oriented schemes by around 22% and 20%, respectively, when considering all eight application codes we tested.