Register estimation in unscheduled dataflow graphs

ABSTRACT

A method for register number estimation in unscheduled or partially scheduled dataflow graphs is presented. The strategy consists of studying the probability that an edge between two nodes crosses the boundary between two control steps, and its is based on a model that associates probabilities with the different scheduling alternatives of each node. These probabilities are computed by means of an analytic method that takes into account the distribution of operations in the dataflow graph and the hardware modules available in the library. The results highlight that the estimation method is very accurate becaused the error between the estimated value and the real value is always within a narrow margin.

REFERENCES

• 1: Richard J. Cloutier , Donald E. Thomas, The combination of scheduling, allocation, and mapping in a single algorithm, Proceedings of the 27th ACM/IEEE conference on Design automation, p.71-76, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123230]
• 2: LANGEVIN, M. AND CERNY, E. 1993 A recursive technique for computing lower-bound performance of schedules. In Proceedings of ICCD '93 (Cambridge, MA, Oct. 3-6), 16-20.
• 3: MORENO, R., HERMIDA, R., FERNANDEZ, M., MEND~AS, J. M., AND SEPTIt~N, J. 1994. Global analysis for integrated scheduling and module allocation. In Proceedings of the Second Asia Pacific Conference on Hardware Description Languages, APCHDL'94 (Toyohashi, Japan, Oct. 24-25), 103-109.
• 4: PAULIN, P. G. AND KNIGNT, J.P. 1989. Force-directed scheduling for the behavioral synthesis of ASICs. IEEE Trans. CAD 8, 6 (June), 661-679.
• 5: RAMACHANDRAN, L. AND GAJSKI, D. 1991. An algorithm for component selection in performance optimized scheduling. In Proceedings of ICCAD'91 (Santa Clara, CA, Nov. 11-14), 92-95.
• 6: RIM, M. AND JAIN, R. 1994. Lower-bound performance estimation for the high-level synthesis scheduling problem. IEEE Trans. CAD 13, 4 (April), 451-458.
• 7: Josef Scheichenzuber , Werner Grass , Ulrich Lauther , Sabine März, Global hardware synthesis from behavioral dataflow descriptions, Proceedings of the 27th ACM/IEEE conference on Design automation, p.456-461, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123337]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design
          Subjects: Data-path design

General Terms:
Design

Keywords:
area estimation, high-level synthesis, probabilities, register estimation, scheduling