DEPENDENCE GRAPH BASED DESIGN OF SYSTOLIC ARRAYS FOR THE ALGEBRAIC PATH PROBLEM.

A systolic design for the algebraic path problem (APP) is introduced. The APP is a generalization of a cross-disciplinary set of problems that includes transitive closure, shortest path, and matrix inversion. Special cases of the array can be used to solve any instance of the APP. The array uses N**2 processing elements, and requires 2N I/O connections. A design methodology that is based on dependence-graph analysis is introduced to derive this array. The design methodology is an extension of methods based on uniform recurrence equations. The algorithm for the APP is described in a localized, indexed, single-assignment form. A systolic implementation of the algorithm is generated by mapping its dependence graph onto an array configuration. Different mappings of the same dependence graph produce both the array used here and those previously proposed for the APP. A comparison is made of all arrays proposed for the APP.