V.N. Aleksandrov
S. Fidanova
University of Newcastle upon Tyne. 1994
A special class of non uniform recurrent equations producing data dependency graphs which involve non-constant data dependencies on the input data f (i) is considered in this paper. This class includes for example Dynamic Programming recurrence equations for Knapsack Type Problems. 2D regular arrays for such equations are derived. It is shown that the execution time is m + c on 2D arrays of size m x [fmax /µ], where µ is the size of the cell memory. In addition it is proved that the mathematical expectation of the execution time on the fixed sized (p x q) regular arrays is ET = O (m (c + 1) / pq + m + q), i.e. optimal, for the case when f (i) £ t < < c and it is measured by ET = O (m (c + 1)2/p 2q + m (c + 1)/pq + m + q) in the case when t = c under the assumption that f (i) are independently drawn from the uniform distribution over {1, 2, ..., t} and p 3q £ (t + 1)/2.