Design methodology of mapping iterative algorithms on piecewise regular processor arrays

摘要

A systematic framework for mapping a class of iterative algorithms onto processor array architectures is presented. The iterative algorithm is directly mapped on the array without the requirement of transforming it into any intermediate form, such a uniform recurrent equation (URE). The principles of Lamport's coordinate method are used. The important subclass of algorithms known as weak single assignment codes (WSACs) is treated in an optimal way. Due to the structure of the algorithm and/or the multidimensional mapping, the resulting architectures can be either regular arrays (RAs) or piecewise regular arrays (PRAs).