P. Kulasinghe et A. Elamawy, ON ACHIEVING MAXIMUM PERFORMANCE IN TIME-VARYING ARRAYS, Journal of parallel and distributed computing, 31(2), 1995, pp. 101-111
Citations number
19
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
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.