Scalable subgraph mapping for acyclic computation accelerators

ABSTRACT

Computer architects are constantly faced with the need to improve performance and increase the efficiency of computation in their designs. To this end, it is increasingly common to see acyclic com-putation accelerators appear in embedded processor designs. One major problem with adding accelerators to a design is that it is difficult to generate high-quality code utilizing them. Hand-written assembly code is typical, and if compiler support does exist, it is implemented using only greedy algorithms. In this work, we investigate more thorough techniques for compiling to processors with acyclic accelerators. Where as greedy solutions only explore one possible solution, the techniques presented in this paper explore the entire design space, when possible. Intelligent pruning methods are employed to ensure compilation is both tractable and scalable. Overall, our new compilation algorithms produce code that performs on average 10%, and up to 32% better than standard greedy methods. These algorithms also run in less than one second for more than 98% of basic blocks tested.

REFERENCES

• 1: Alfred V. Aho , Mahadevan Ganapathi , Steven W. K. Tjiang, Code generation using tree matching and dynamic programming, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.4, p.491-516, Oct. 1989 [doi>10.1145/69558.75700]
• 2: ARM Ltd. ARM926EJ-S Technical Reference Manual, Jan. 2004. http://www. arm. com/pdfs/DDI0198D 926 TRM. pdf.
• 3: Kubilay Atasu , Laura Pozzi , Paolo Ienne, Automatic application-specific instruction-set extensions under microarchitectural constraints, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775897]
• 4: Partha Biswas , Sudarshan Banerjee , Nikil Dutt , Laura Pozzi , Paolo Ienne, ISEGEN: Generation of High-Quality Instruction Set Extensions by Iterative Improvement, Proceedings of the conference on Design, Automation and Test in Europe, p.1246-1251, March 07-11, 2005 [doi>10.1109/DATE.2005.191]
• 5: Anne Bracy , Prashant Prahlad , Amir Roth, Dataflow Mini-Graphs: Amplifying Superscalar Capacity and Bandwidth, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.18-29, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.15]
• 6: Philip Brisk , Adam Kaplan , Ryan Kastner , Majid Sarrafzadeh, Instruction generation and regularity extraction for reconfigurable processors, Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems, October 08-11, 2002, Grenoble, France [doi>10.1145/581630.581672]
• 7: Randal E. Bryant, Symbolic Boolean manipulation with ordered binary-decision diagrams, ACM Computing Surveys (CSUR), v.24 n.3, p.293-318, Sept. 1992 [doi>10.1145/136035.136043]
• 8: Nathan Clark , Jason Blome , Michael Chu , Scott Mahlke , Stuart Biles , Krisztian Flautner, An Architecture Framework for Transparent Instruction Set Customization in Embedded Processors, Proceedings of the 32nd Annual International Symposium on Computer Architecture, p.272-283, June 04-08, 2005
• 9: Nathan T. Clark , Hongtao Zhong , Scott A. Mahlke, Automated Custom Instruction Generation for Domain-Specific Processor Acceleration, IEEE Transactions on Computers, v.54 n.10, p.1258-1270, October 2005 [doi>10.1109/TC.2005.156]
• 10: Roberto Cordone , Fabrizio Ferrandi , Donatella Sciuto , Roberto Wolfler Calvo, An efficient heuristic approach to solve the unate covering problem, Proceedings of the conference on Design, automation and test in Europe, p.364-371, March 27-30, 2000, Paris, France [doi>10.1145/343647.343799]
• 11: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 12: E. Goldberg, L. Carloni, T. Villa, R. Brayton, and A. Sangiovanni-Vincentelli. Negative thinking in branch-and-bound: the case of unate covering. IEEE TCAD, 19(3):281--294, Mar. 2000.
• 13: David Goodwin , Darin Petkov, Automatic generation of application specific processors, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951730]
• 14: J. R. Hauser , J. Wawrzynek, Garp: a MIPS processor with a reconfigurable coprocessor, Proceedings of the 5th IEEE Symposium on FPGA-Based Custom Computing Machines, p.12, April 16-18, 1997
• 15: S. Hu, I. Kim, M. H. Lipasti, andJ. E. Smith. Anapproachfor implementing efficient superscalar cisc processors. In Proc. 12th HPCA, pages 213--226, 2006.
• 16: Shiliang Hu , James E. Smith, Using Dynamic Binary Translation to Fuse Dependent Instructions, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.213, March 20-24, 2004, Palo Alto, California
• 17: I. Huang and A. M. Despain. Synthesis of application specific instruction sets. IEEE TCAD, 14(6):663--675, June 1995.
• 18: R. Kastner , A. Kaplan , S. Ogrenci Memik , E. Bozorgzadeh, Instruction generation for hybrid reconfigurable systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.4, p.605-627, October 2002 [doi>10.1145/605440.605446]
• 19: Evgeny B. Krissinel , Kim Henrick, Common subgraph isomorphism detection by backtracking search, Software—Practice & Experience, v.34 n.6, p.591-607, May 2004 [doi>10.1002/spe.588]
• 20: R. Leupers , P. Marwedel, Instruction selection for embedded DSPs with complex instructions, Proceedings of the conference on European design automation, p.200-205, September 1996, Geneva, Switzerland
• 21: Stan Liao , Srinivas Devadas , Kurt Keutzer , Steve Tjiang, Instruction selection using binate covering for code size optimization, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.393-399, November 05-09, 1995, San Jose, California, United States
• 22: Nadeem Malik , Richard J. Eickemeyer , Stamatis Vassiliadis, Interlock collapsing ALU for increased instruction-level parallelism, Proceedings of the 25th annual international symposium on Microarchitecture, p.149-157, December 01-04, 1992, Portland, Oregon, United States
• 23: Krishna V. Palem , Surendranath Talla , Weng-Fai Wong, Compiler Optimizations for Adaptive EPIC Processors, Proceedings of the First International Workshop on Embedded Software, p.257-273, October 08-10, 2001
• 24: A. Peymandoust et al. Automatic instruction set extension and utilization for embedded processors. In 14th ASAP, pages 108--120, June 2003.
• 25: J. Phillips , S. Vassiliadis, High-Performance 3-1 Interlock Collapsing ALU's, IEEE Transactions on Computers, v.43 n.3, p.257-268, March 1994 [doi>10.1109/12.272427]
• 26: Rahul Razdan , Michael D. Smith, A high-performance microarchitecture with hardware-programmable functional units, Proceedings of the 27th annual international symposium on Microarchitecture, p.172-180, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192749]
• 27: Peter G. Sassone , D. Scott Wills , Gabriel H. Loh, Static strands: safely collapsing dependence chains for increasing embedded power efficiency, Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 15-17, 2005, Chicago, Illinois, USA
• 28: J. R. Ullmann, An Algorithm for Subgraph Isomorphism, Journal of the ACM (JACM), v.23 n.1, p.31-42, Jan. 1976 [doi>10.1145/321921.321925]
• 29: Scott J. Weber , Kurt Keutzer, Using minimal minterms to represent programmability, Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 19-21, 2005, Jersey City, NJ, USA [doi>10.1145/1084834.1084854]
• 30: Zhi Alex Ye , Andreas Moshovos , Scott Hauck , Prithviraj Banerjee, CHIMAERA: a high-performance architecture with a tightly-coupled reconfigurable functional unit, Proceedings of the 27th annual international symposium on Computer architecture, p.225-235, June 2000, Vancouver, British Columbia, Canada
• 31: Sami Yehia , Nathan Clark , Scott Mahlke , Krisztiàn Flautner, Exploring the design space of LUT-based transparent accelerators, Proceedings of the 2005 international conference on Compilers, architectures and synthesis for embedded systems, September 24-27, 2005, San Francisco, California, USA [doi>10.1145/1086297.1086301]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
compilation, embedded processors