Implementation of Retiming Algorithms in MATLAB

Abstract

Data driven property and real time requirements are the two significant features of digital signal processing systems. Dataflow models of computation are widely used to represent digital signal processing applications. DSP algorithms are often repetitive. Execution of all the computations for the required number of times is called iteration. The iteration period of synchronous dataflow graph is the least time required for executing one iteration. Retiming is a graph transformation technique that only changes the delay distribution of the graph, while it has no effect on its functionality. Retiming is used to optimize the synchronous dataflow graphs by reducing the iteration period. Here, the three algorithms to find the retiming vectors of synchronous dataflow graphs have been implemented and their execution times found. These algorithms are – byHSDF, ZHU10, and sdfFEAS. ByHSDF is the oldest method in which the synchronous dataflow graph is first converted to a homogeneous dataflow graph and then the retiming vector is found. ZHU10 doesn’t require the conversion to a homogenous dataflow graph to find the retiming vector. sdfFEAS is the latest method. This method doesn’t use backtracking as is employed in the previous method. Instead it employs the concept of critical walks. These algorithms are implemented in MATLAB and their execution times are compared and it is seen which algorithm gives the best results.