Optimizing Computations for Effective Block-Processing

Block-processing is a powerful and popular technique for increasing computation speed by simultaneously processing several samples of data. In comparison with conventional computations, block-processed computations have reduced hardware and power dissipation requirements and result in less expensive implementations on uniprocessor and parallel programmable platforms. The effectiveness of block-processing is often reduced, however, due to suboptimal placement of delays in the dataflow graph of a computation. In this paper we investigate an application of the retiming transformation for improving the effectiveness of block-processing in computation structures. Specifically, we consider the k-delay problem in which we wish to restructure any given computation by relocating its delays so that for any given k, the resulting computation can process k data samples simultaneously in a fully regular manner. Our first contribution is the formulation of the k-delay problem as an integer linear pr..