Optimizing computations for effective block-processing

Block-processing can decrease the time and power required to perform any given computation by simultaneously processing multiple samples of input data. The effectiveness of block-processing can be severely limited, however, if the delays in the dataflow graph of the computation are placed suboptimally. In this paper we investigate the application of retiming for improving the effectiveness of block-processing in computations. In particular, we consider the k-delay problem: Given a computation dataflow graph and a positive integer k, we wish to compute a retimed computation graph in which the original delays have been relocated so that k data samples can be processed simultaneously and fully regularly. We give an exact integer linear programming formulation for the k-delay problem. We also describe an algorithm that solves the k-delay problem fast in practice by relying on a set of necessary conditions to prune the search space. Experimental results with synthetic and random benchmarks demonstrate the performance improvements achievable by block-processing and the efficiency of our algorithm.