2D data locality: definition, abstraction, and application

Data locality has been a central theme in the compiler optimization world for a long time. Most of the prior compiler techniques try to optimize data locality in a one-dimensional linear address space. However, there are many problems out there where the domain for data locality can be two or higher dimensional. For example, in a 2D mesh network environment, each node has connections with its four neighbors, and therefore, the data locality can potentially be exploited in two dimensions from a given processor´s viewpoint. Because of this, maximizing the number of communications with any of four neighbors (instead of other nodes) helps improve performance. Similar examples can be given from the areas of embedded sensor processing and 3D systems as well. In this application domain, we make two specific contributions. First, we show how array data of a loop-intensive application can be mapped onto a 2D mesh so that the communication distances between the nodes are reduced. Second, we discuss how code restructuring through loop transformation can help us achieve better data locality in the 2D space.