Optimizing systems for effective block-processing
Kumar N. Lalgudi, Marios C. Papaefthymiou, Miodrag Potkonjak · 1996
Abstract|Block-processing is a powerful and popular technique for increasing computation speed by simultaneously processing several samples of data.The eectiveness of block-processing is often reduced, however, due to suboptimal placement of delays in the data ow graph of a computation.In this paper we i n v estigate an application of the retiming transformation for improving the effectiveness of block-processing in computation structures.Speci cally, w e consider the k-delay problem in which w e 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 3 E+V 4 log V )-time algorithm for the k-delay problem, where V is the number of computation blocks and E is the number of interconnections in the computation.