Optimizing systems for effective block-processing: the k-delay problem
K.N. Lalgudi, M.C. Papaefthymiou, M. Potkonjak · 2005
Block-processing is a powerful and popular technique for increasing computation speed by simultaneously processing several samples of data. 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 retime any given computation so that given an integer k the resulting computation can process k data samples simultaneously in a fully regular manner. Our main contribution is an O(V/sup 3/E+V/sup 4/ log V)-time algorithm for the L-delay problem, where V is the number of computation blocks and E is the number of interconnections in the computation.