ON ACHIEVING MAXIMUM PERFORMANCE IN TIME-VARYING ARRAYS

Several important computationally intensive algorithms can be implemen ted on special purpose VLSI arrays. A number of such algorithms natura lly map onto either heterogenous arrays or arrays employing PEs with s witchable functions, or both. In many cases, such designs are the only known ones for VLSI implementation. Synchronization is generally achi eved by assuming that the time required to perform basic PE computatio ns is uniform, although the PEs perform different functions and may ch ange their functions at different algorithmic steps. This simplistic a pproach may result in significant performance degradation. This paper addresses the properties, performance, and theory of time-varying hete rogeneous arrays for the objective of achieving maximum performance. A systematic method for collision avoidance is formally introduced and analyzed. Our approach is based on dynamically balancing a two-level p ipelined array through the use of a set of buffers. Another set of buf fers is used to guarantee data synchronization. We show that if the in itial delays (PE execution times) and the time variances are determini stic, an equivalent time-invariant array can be constructed (in polyno mial time) which is optimal in speed. We describe a method for estimat ing the upper bound on computational time when array time variance is nondeterministic. Our method requires only knowledge of the bounds on initial delays. (C) 1995 Academic Press, Inc.