ON THE EXPECTED EXECUTION TIME FOR A CLASS OF NON UNIFORM RECURRENCE EQUATIONS MAPPED ONTO 1D REGULAR ARRAYS

Abstract

A special class non uniform recurrent equations produced data dependency graphs which involve non-constant data dependencies on the input data f(i) is considered. The mathematical expectation of the execution time for the problems described by such recurrences under the assumption that f(i) are uniformly distributed is found. In case when f(i) are exponentially distributed it is proved that the mathematical expectation of time tends to the optimal one.

KEY WORDS:

• Systolic arrays
• non-uniform recurrence equations
• average execution time