Statistical schedule length analysis in asynchronous datapath synthesis

The paper proposes statistical schedule length analysis for evaluating schedule and datapath during asynchronous datapath synthesis. In order to handle the randomness of delay variation mathematically, the execution time of each operation is modeled by a stochastic variable, and an algorithm to calculate the distribution of total computation time of an application is presented. The proposed statistical schedule length analysis is then incorporated with resource binding and scheduling to form an asynchronous datapath synthesis system. Our system tends to generate better solutions than the conventional one in the mean total computation time, when the size of a target algorithm becomes larger, the number of functional units becomes larger, and the variance of execution delay of each module becomes larger. Experimental results have been obtained for a differential equation solver, a wave digital filter and elliptic wave filters.