Matrix computations on mesh arrays
Jaime H. Moreno · 1990
This dissertation addresses the systematic derivation of mesh arrays for matrix computations, in particular realizing the algorithm-specific arrays and mapping algorithms onto class-specific arrays. A data-dependency graph-based transformational method is proposed in a design frame work consisting of two stages, namely algorithm regularization and derivation of arrays. The first stage derives the fully-parallel data-dependency graph (FPG) of an algorithm and transforms this graph into a three-dimensional one with unidirectional nearest-neighbor dependencies (a multi-mesh graph MMG). The second stage transforms the MMG into a two-dimensional G-graph, which is realized as an algorithm-specific array or mapped onto a class-specific array. This stage allows the incorporation of implementation restrictions and the evaluation of tradeoffs in properties of cells, as well as the derivation of arrays for fixed-size data and partitioned problems, while performing optimization of specific performance/cost measures. The proposed method is formalized by presenting a sufficient set of transformations and demonstrating the equivalence of graphs obtained from those transformations. Moreover, it is demonstrated that the MMG representation is always possible, due to the characteristics of the operators. The method used systolic, pseudo-systolic (an extension to systolic) and local-access cells. Pseudo-systolic cells include two small FIFO buffers, require bandwidth that is a fraction of the computation rate, allow performing tradeoffs between memory size and cell bandwidth, and use pipelined functional units efficiently. In contrast, systolic cells have no local storage, while local-access cells have large local memory and low bandwidth. The method has been applied to a collection of matrix algorithms, including matrix multiplication, convolution, matrix decompositions (LU, QR, Cholesky), transitive closure, the Faddeev algorithm, and $BA\sp{-1}$. The examples show that, in addition to the features listed earlier, this method is easy to apply. Moreover, the method is compared with other techniques, concluding that it is advantageous because it meets evaluation criteria and produces more efficient arrays. A linear class-specific array for partitioned problems is proposed for which the method produces high cell utilization, low I/O bandwidth and low cell bandwidth. The method has also proved useful for mapping algorithms onto local-access arrays, using coalescing combined with a heuristic approach to achieve load balancing.