Automatic operator configuration in the synthesis of pipelined architectures

ABSTRACT

We present an algorithm for automating the choice of operator configurations while synthesizing a pipelined design. The chosen configuration set must meet the design constraints of the pipeline (number of stages and stage time) while minimizing the total cost(s) (e.g. area, power) of the design. The configuration algorithm is first used with heuristics to make initial operator choices for insertion of stage latches; then optimally to choose configurations within each stage. Some advantages to this new algorithm are that it will allow the designer to specify both the number of stages as well as the latency of each stage, and that it will take arbitrary timing functions.

REFERENCES

• 1: A. E. Casavant , M. A. d'Abreu , M. Dragomirecky , D. A. Duff , J. R. Jasica , M. J. Hartman , K. S. Hwang , W. D. Smit, A Synthesis Environment for Designing DSP Systems, IEEE Design & Test, v.6 n.2, p.35-44, March 1989 [doi>10.1109/54.19133]
• 2: G.B. Chapman and J. Del Hoyo. Progressive basic decision CPM. Operations Research Quarterly, 23(3):345-359, September 1972.
• 3: Dennis C. Fogg. Operator selection: Two approaches. In Fourth Internalional Worksho~ on High-Level Synthesis. ACM/IEEE, October 1989.
• 4: 3.H. Harvey, R.T.; Patterson. An implicit enumeration algorithm for the time/cost tradeoff problem in project network analysis. Con~rolEngineering (Poland), 4(3):107-117, 1979.
• 5: Thomas J. Hindelang. A d!Iuamle programming algorithm ,for decision CPM networks. PhD thesis, Indiana University, September 1973.
• 6: Thomas J. Hindelang and John F. Muth. A dynamic programming algorithm for decision CPM networks. Operations Research, 27(2):225-241, Mar-Apr 1979.
• 7: Kai Hwang, H.C. Wang, axld Z. Xu. Evaluating elementary functions with chebyshev polynomials on pipeline nets. In 8~h Symposium on Computer Arithme$ic, pages 121-128. IEEE, May 1987.
• 8: Kristen N. McNall. Automatic operator configuration in the synthesis of pipelined architectures. RPI Computer Science Project Report, December 1989.
• 9: Thomas L. Morin and Roy E. Marsten. An algorithm for nonlinear knapsack problems. Management Science, 22(10):1147-1158, June 1976.
• 10: D. Panagiotakopoulos. A CPM time-cost computational algorithm for arbitrary activity cost functions. {nfor, 15(2):183-195, June 1977.
• 11: Nohbyung Park. Synthesis of High-Speed Digital Systems. PhD thesis, University of Southern California, October 1985.
• 12: Don R. Robinson. A dynamic programming solution to costtime tradcoff for CPM. Management Science, 22(2):158- 166, October 1975.
• 13: W. D. Smith , D. Duff , M. Dragomirecky , J. Caldwell , M. Hartman , J. Jasica , M. A. d'Abreu, FACE core environment: the model and its application in CAE/CAD tool development, Proceedings of the 26th ACM/IEEE conference on Design automation, p.466-471, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74460]
• 14: Stephen H. Unger. Tree realizations of iter&tive circuits. IEEE Transactions on Computers, C-26(4):365-383, April 1977.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.1 Design Styles
          Subjects: Pipeline

Additional Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES

General Terms:
Algorithms, Design