Design of algorithm transformations for VLSI array processing

The rapid advances in the very large scale integrated (VLSI) technology has created a flurry of research in designing future computer architectures. Many methods have been developed for parallel processing of algorithms by directly mapping them onto parallel architectures.

A procedure, based on the mathematical transformation of the index set and dependence vectors of an algorithm, is developed to find algorithm transformations for VLSI array processing. The algorithm is modeled as a program graph which is a directed graph. Techniques are suggested to regularize the data-flou in an algorithm, thereby minimizing the communication requirements of the architecture.

We derive a set of sufficient conditions on the structure of data-flou of a class of algorithms, for the existence of valid transformations. The VLSI array is modeled as a directed graph, and the program graph is mapped onto this using the algorithm transformation.