Hyperplane partitioning of arrays based on eigenvector analysis

摘要

This paper addresses the problem of partitioning arrays accessed by loops onto Array Processors. We analyze the influence of the array subscript expressions on the array data decomposition. The array data domains are decomposed into the union of a finite number of parallel hyperplanes. Arrays that admit the same hyperplane data decomposition are grouped in the same class. Based on an eigenvector analysis, it is provided a characterisation of conditions in which two arrays belong to the same class. It turns out that data movements between two arrays belonging to the same class, can be decomposed in two orthogonal and independent communication subfunctions in order to simplify the matching with a composition of communication routines implemented on the abstract machine. Afterwards, we focus on the problem of data partitioning in Image Processing applications.