Mapping signal processing algorithms to fixed architectures

A technique is described for partitioning 2-D signal flow graph (SFG)/systolic arrays to a 2-D triangular array (triarray) of N(N+1)/2 processors. The folding technique can be used to partition 2-D SFGs onto smaller subarrays of the SFG. The stages of development are all highly suited to CAD from algorithm specification to array implementation, and can be performed in an integrated mapping methodology using the Occam algebra. Because of the Occam algebra-based partitioning, the data flow of the SFG has been preserved and the SFG implementation on the triarray is guaranteed to be functionally correct. The control overheads introduced by this scheme are minimal and very straightforward, i.e. a very simple mux and demux processes at the link interfaces of each transputer to code and decode the data flow tags. It is concluded that a triarray of transputers (or transputer link wavefront devices) is a highly versatile and flexible array processor when the folding scheme is used