Conditional speculation and its effects on performance and area for high-level snthesis

ABSTRACT

We introduce a code transformation technique, "conditional speculation", that speculates operations by duplicating them into preceding conditional blocks. This form of speculation belongs to a class of aggressive code motion techniques that enable movement of operations through and beyond conditionals and loops. We show that, when used during scheduling in a high-level synthesis system, this particular code motion has positive effect on latency and controller complexity, e.g., up to 35% reduction in longest path cycles and the number of states in the finite state machine (FSM) of the controller. However, it is not enough to determine complexity by the number of states in the control FSM. Indeed, the greater resource sharing opportunities afforded by speculation actually increase the total control cost (in terms of multiplexing and steering logic). This also adversely affects the clock period. We examine the effect of the various code motions on the total synthesis cost and propose techniques to reduce costs to make the transformations useful in real-life behavioral design descriptions. Using the MPEG-1 and ADPCM benchmarks, we show total reductions in schedule lengths of up to 50% while keeping control and area costs down.

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: Raul Camposano , Wayne H. Wolf, High-Level VLSI Synthesis, Kluwer Academic Publishers, Norwell, MA, 1991
• 3: Sumit Gupta , Nick Savoiu , Sunwoo Kim , Nikil Dutt , Rajesh Gupta , Alex Nicolau, Speculation techniques for high level synthesis of control intensive designs, Proceedings of the 38th conference on Design automation, p.269-272, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378481]
• 4: M. Potkonjak and J. Rabaey. Optimizing resource utlization using tranformations. IEEE Transactions on CAD, March 1994.
• 5: R. Walker and D. Thomas. Behavioral transformation for algorithmic level ic design. IEEE Transactions on CAD, October 1989.
• 6: 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
• 7: I. Radivojevic and F. Brewer. A new symbolic technique for control-dependent scheduling. IEEE Transactions on CAD, January 1996.
• 8: 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]
• 9: 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]
• 10: Minjoong Rim , Yaw Fann , Rajiv Jain, Global scheduling with code-motions for high-level synthesis applications, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.3, p.379-392, Sept. 1995 [doi>10.1109/92.406996]
• 11: Reinaldo A. Bergamaschi, Behavioral network graph: unifying the domains of high-level and logic synthesis, Proceedings of the 36th ACM/IEEE conference on Design automation, p.213-218, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309916]
• 12: J. Fisher. Trace scheduling: A technique for global microcode compaction. IEEE Transactions on Computers, 7, July 1981.
• 13: A. Nicolau. Uniform parallelism exploitation in ordinary programs. In International Conf. on Parallel Processing, 1985.
• 14: Kemal Ebcioglu , Alexandru Nicolau, A global resource-constrained parallelization technique, Proceedings of the 3rd international conference on Supercomputing, p.154-163, June 05-09, 1989, Crete, Greece [doi>10.1145/318789.318807]
• 15: L. Stok and W.J.M. Philipsen. Module allocation and comparability graphs. In IEEE International Sympoisum on Circuits and Systems, 1991.
• 16: P. G. Paulin , J. P. Knight, Scheduling and binding algorithms for high-level synthesis, Proceedings of the 26th ACM/IEEE conference on Design automation, p.1-6, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74383]
• 17: A. Mujumdar, R. Jain, and K. Saluja. Incorporating performance and testability constraints during binding in high-level synthesis. IEEE Trans. on CAD, 1996.
• 18: Soo-Mook Moon , Kemal Ebcioğlu, An efficient resource-constrained global scheduling technique for superscalar and VLIW processors, Proceedings of the 25th annual international symposium on Microarchitecture, p.55-71, December 01-04, 1992, Portland, Oregon, United States
• 19: Spark Synthesis Benchmarks FTP site. ftp://ftp.ics.uci.edu/pub/spark/benchmarks.
• 20: M. Pedram , J. Chang, Module assignment for low power, Proceedings of the conference on European design automation, p.376-381, September 1996, Geneva, Switzerland
• 21: L. Stok. Transfer free register allocation in cyclic data flow graphs. In European Conf. on Design Automation, 1992.
• 22: Jui-Ming Chang , Massoud Pedram, Register allocation and binding for low power, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.29-35, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217502]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.5 Sound and Music Computing
          Subjects: Signal analysis, synthesis, and processing

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Motion

General Terms:
Design, Experimentation, Performance