Speculation techniques for high level synthesis of control intensive designs

ABSTRACT

The quality of synthesis results for most high level synthesis approaches is strongly affected by the choice of control flow (through conditions and loops) in the input description. In this paper, we explore the effectiveness of various types of code motions, such as moving operations across conditionals, out of conditionals (speculation) and into conditionals (reverse speculation), and how they can be effectively directed by heuristics so as to lead to improved synthesis results in terms of fewer execution cycles and fewer number of states in the finite state machine controller. We also study the effects of the code motions on the area and latency of the final synthesized netlist. Based on speculative code motions, we present a novel way to perform early condition execution that leads to significant improvements in highly control-intensive designs. Overall, reductions of up to 38 \% in execution cycles are obtained with all the code motions enabled.

REFERENCES

• 1: Daniel D. Gajski , Nikil D. Dutt , Allen C.-H. Wu , Steve Y.-L. Lin, High-level synthesis: introduction to chip and system design, Kluwer Academic Publishers, Norwell, MA, 1992
• 2: K. Wakabayashi , H. Tanaka, Global scheduling independent of control dependencies based on condition vectors, Proceedings of the 29th ACM/IEEE conference on Design automation, p.112-115, June 08-12, 1992, Anaheim, California, United States
• 3: I. Radivojevic and F. Brewer. A new symbolic technique for control-dependent scheduling. IEEE Transactions on CAD, January 1996.
• 4: Luiz C. V. dos Santos , Jochen A. G. Jess, A reordering technique for efficient code motion, Proceedings of the 36th ACM/IEEE conference on Design automation, p.296-299, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309935]
• 5: Ganesh Lakshminarayana , Anand Raghunathan , Niraj K. Jha, Incorporating speculative execution into scheduling of control-flow intensive behavioral descriptions, Proceedings of the 35th annual conference on Design automation, p.108-113, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277067]
• 6: A. Nicolau and S. Novack. Trailblazing: A hierarchical approach to percolation scheduling. In International Conference on Parallel Processing, 1993.
• 7: Steven Novack , Alexandru Nicolau, An Efficient Global Resource-Directed Approach to Exploiting Instruction-Level Parallelism, Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques, p.87, October 20-23, 1996

INDEX TERMS

Primary Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.2 Input/Output Devices
          Subjects: Channels and controllers

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Electronics

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory