Optimizing computations for effective block-processing

ABSTRACT

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.

REFERENCES

• 1: Richard E. Blahut, Fast Algorithms for Digital Signal Processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985
• 2: CHERKASSKY, B., GOLDBERG, A., AND RADZIK, T. 1993. Shortest paths algorithms:: theory and experimental evaluation. Tech. Rep. STAN-CS-93-1480. Stanford University, Stanford, CA.
• 3: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 4: DE MICHELI, G. 1991. Synchronous logic synthesis: Algorithms for cycle-time optimization. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 10, 1 (Jan. 1991), 63-73.
• 5: GIBBS, W. W. 1994. Software's chronic crisis. Sci. Am. (Sept. 1994), 86-95.
• 6: GUERRA, L., POTKONJAK, M., AND RABAEY, J. 1994. System-level design guidance using algorithm properties. In Proceedings of the IEEE Workshop on VLSI Signal Processing VII, IEEE Press, Piscataway, NJ, 73-82.
• 7: ISHII, A. T., LEISERSON, C. E., AND PAPAEFTHYMIOU, M. C. 1992. Optimizing two-phase, level-clocked circuitry. In Proceedings of the 1992 Brown/MIT Conference on Advanced Research in VLSI and Parallel Systems, T. Knight and J. Savage, Eds. MIT Press, Cambridge, MA, 245-264.
• 8: Ku, D. C. AND DE MICHELI, G. 1992. Relative scheduling under timing constraints: Algorithms for high-level synthesis of digital circuits. IEEE Trans. CAD/ICAS 11, 6 (June), 696-718.
• 9: S. Y. Kung, VLSI array processors, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 10: Kumar N. Lalgudi , Marios C. Papaefthymiou, DELAY: an efficient tool for retiming with realistic delay modeling, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.304-309, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217546]
• 11: Kumar N. Lalgudi , Marios C. Papaefthymiou, Computing strictly-second shortest paths, Information Processing Letters, v.63 n.4, p.177-181, Aug. 28, 1997 [doi>10.1016/S0020-0190(97)00122-1]
• 12: LEISERSON, C. E. AND SAXE, J. B. 1991. Retiming synchronous circuitry. Algorithmica 6, 1, 5-35.
• 13: Stan Liao , Srinivas Devadas , Kurt Keutzer , Steve Tjiang , Albert Wang, Storage assignment to decrease code size, ACM SIGPLAN Notices, v.30 n.6, p.186-195, June 1995
• 14: Brian Lockyear , Carl Ebeling, The practical application of retiming to the design of high-performance systems, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.288-295, November 07-11, 1993, Santa Clara, California, United States
• 15: MALIK, S., SENTOVICH, E., BRAYTON, R. K., AND SANGIOVANNI-VINCENTELLI, A. 1990. Retiming and resynthesis: Optimizing sequential networks with combinational techniques. In Proceedings of the 23rd Annual Hawaii International Conference on System Sciences, 397-406.
• 16: RITZ, S., PANKERT, M., ZIVOJNOVIC, V., AND MEYR, H. 1993. Optimum vectorization of scalable synchronous dataflow graphs. In Proceedings of the International Conference on Application-Specific Array Processors (Oct. 1993), 285-296.
• 17: WALKER, R. A. AND THOMAS, D. E. 1989. Behavioral transformations for algorithmic level IC design. IEEE Trans. CAD/ICAS 8, 10 (Oct.), 1115-1127.
• 18: ZIVOJNOVIC, V., RITZ, S., AND MEYR, H. 1994. Retiming of DSP programs for optimum vectorization. In Proceedings of the International Conference on Acoustics, Speech, and Signal Processing 2, 19-22.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Signal processing systems

Additional Classification:
  F. Theory of Computation

General Terms:
Algorithms, Design, Performance

Keywords:
combinatorial optimization, computation dataflow graphs, embedded systems, high-level synthesis, integer linear programming, retiming, scheduling, vectorization