Coordinated transformations for high-level synthesis of high performance microprocessor blocks

ABSTRACT

High performance microprocessor designs are partially characterized by functional blocks consisting of a large number of operations that are packed into very few cycles (often single-cycle) with little or no resource constraints but tight bounds on the cycle time. Extreme parallelization, conditional and speculative execution of operations is essential to meet the processor performance goals. However, this is a tedious task for which classical high-level synthesis (HLS) formulations are inadequate and thus rarely used. In this paper, we present a new methodology for application of HLS targeted to such microprocessor functional blocks that can potentially speed up the design space exploration for microprocessor designs. Our methodology consists of a coordinated set of source-level and fine-grain parallelizing compiler transformations that targets these behavioral descriptions, specifically loop constructs in them and enables efficient chaining of operations and high-level synthesis of the functional blocks. As a case study in understanding the complexity and challenges in the use of HLS, we walk the reader through the detailed design of an instruction length decoder drawn from the Pentium®-family of processors. The chief contribution of this paper is formulation of a domain-specific methodology for application of high-level synthesis techniques to a domain that rarely, if ever, finds use for it.

REFERENCES

• 1: M. Potkonjak and J. Rabaey. Optimizing resource utlization using tranformations. IEEE Trans. on CAD, March 1994
• 2: R. Walker and D. Thomas. Behavioral transformation for algorithmic level IC design. IEEE Trans. on CAD, Oct. 1989
• 3: N. Park and A. Parker. Sehwa: A software package for synthesis of pipelines from behavioral specifications. IEEE Trans. on Computer-Aided Design, March 1988
• 4: P. G. Paulin and J. P. Knight. Force-Directed Scheduling for the Behavioral Synthesis of ASIC's. IEEE TCAD, June 1989
• 5: 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
• 6: I. Radivojevic and F. Brewer. A new symbolic technique for control-dependent scheduling. IEEE TCAD, January 1996
• 7: 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]
• 8: 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]
• 9: Sumit Gupta , Nick Savoiu , Nikil Dutt , Rajesh Gupta , Alex Nicolau, Conditional speculation and its effects on performance and area for high-level snthesis, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada [doi>10.1145/500001.500040]
• 10: J. Fisher. Trace scheduling: A technique for global microcode compaction. IEEE Trans. on Comps., July 1981
• 11: 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
• 12: R.K. Brayton, R. Camposano, G. De Micheli, R.H.J.M. Otten, and J. van Eijndhoven. The Yorktown Silicon Compiler System, Silicon Compilation. Addison-Wesley, 1988
• 13: Ram Lakhan Gupta , Anshul Kumar , A. Van Der Werf , G. Natalino Busa, Synthesizing a long latency unit within VLIW processor, Proceedings of the The 14th International Conference on VLSI Design (VLSID '01), p.460, January 03-07, 2001
• 14: 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]
• 15: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 16: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 17: 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
• 18: A. Nicolau and S. Novack. Trailblazing: A hierarchical approach to percolation scheduling. In International Conference on Parallel Processing, 1993
• 19: Intel Inc., PentiumPro registered Programmer's Reference Manual

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design

Additional Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.3 Microcomputers
          Subjects: Microprocessors

General Terms:
Design

Keywords:
high-level synthesis, microprocessor design