Automatic generation of operation tables for fast exploration of bypasses in embedded processors

ABSTRACT

Customizing the bypasses in an embedded processor uncovers valuable trade-offs between the power, performance and the cost of the processor. Meaningful exploration of bypasses requires bypass-sensitive compiler. Operation Tables (OTs) have been proposed to perform bypass-sensitive compilation. However, due to lack of automated methods to generate OTs, OTs are currently manually specified by the designer. Manual specification of OTs is not only an extremely time consuming task, but is also highly error-prone. In this paper, we present AutoOT, an algorithm to automatically generate OTs from a high-level processor description. Our experiments on the Intel XScale processor model running MiBench benchmarks demonstrate that AutoOT greatly reduces the time and effort of specification. Automatic generation of OTs makes it feasible to perform full bypass exploration on the Intel XScale and thus discover interesting alternate bypass configurations in a reasonable time. To further reduce the compile-time overhead of OT generation, we propose another novel algorithm, AutoOTDB. AutoOTDB is able to cut the compile-time overhead of OT generation by half.

REFERENCES

• 1: Pritpal S. Ahuja , Douglas W. Clark , Anne Rogers, The performance impact of incomplete bypassing in processor pipelines, Proceedings of the 28th annual international symposium on Microarchitecture, p.36-45, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 2: E. S. Davidson. The design and control of pipelined function generators. Int. IEEE Conf. on Systems Networks and Computers, pages 19--21, 1971.
• 3: E. S. Davidson. Effective control for pipelined processors. IEEE COMPCON, pages 181--184, 1975.
• 4: M. Freericks. The nML machine description formalism. T.U. Berlin, Fachbereich Informatik, Berlin, 1991.
• 5: Peter Grun , Ashok Halambi , Nikil Dutt , Alex Nicolau, RTGEN: an algorithm for automatic generation of reservation tables from architectural descriptions, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.11 n.4, p.731-737, August 2003 [doi>10.1109/TVLSI.2003.813011]
• 6: John C. Gyllenhaal , Wen-mei W. Hwu , B. Ramabriohna Rau, Optimization of machine descriptions for efficient use, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.349-358, December 02-04, 1996, Paris, France
• 7: George Hadjiyiannis , Silvina Hanono , Srinivas Devadas, ISDL: an instruction set description language for retargetability, Proceedings of the 34th annual conference on Design automation, p.299-302, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266108]
• 8: Ashok Halambi , Peter Grun , Vijay Ganesh , Asheesh Khare , Nikil Dutt , Alex Nicolau, EXPRESSION: a language for architecture exploration through compiler/simulator retargetability, Proceedings of the conference on Design, automation and test in Europe, p.100-es, January 1999, Munich, Germany [doi>10.1145/307418.307549]
• 9: Christopher W. Milner , Jack W. Davidson, Quick piping: a fast, high-level model for describing processor pipelines, Proceedings of the joint conference on Languages, compilers and tools for embedded systems: software and compilers for embedded systems, June 19-21, 2002, Berlin, Germany
• 10: Stefan Pees , Andreas Hoffmann , Vojin Zivojnovic , Heinrich Meyr, LISA—machine description language for cycle-accurate models of programmable DSP architectures, Proceedings of the 36th ACM/IEEE conference on Design automation, p.933-938, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.310101]
• 11: Aviral Shrivastava , Nikil Dutt , Alex Nicolau , Eugene Earlie, PBExplore: A Framework for Compiler-in-the-Loop Exploration of Partial Bypassing in Embedded Processors, Proceedings of the conference on Design, Automation and Test in Europe, p.1264-1269, March 07-11, 2005 [doi>10.1109/DATE.2005.236]
• 12: Aviral Shrivastava , Eugene Earlie , Nikil Dutt , Alex Nicolau, Operation Tables for Scheduling in the Presence of Incomplete Bypassing, Proceedings of the International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS'04), p.194-199, September 08-10, 2004 [doi>10.1109/CODES+ISSS.2004.43]
• 13: Chuck Siska, A processor desription language supporting retargetable multi-pipeline DSP program development tools, Proceedings of the 11th international symposium on System synthesis, p.31-36, December 02-04, 1998, Hsinchu, Taiwan, China
• 14: Synopsys Inc., http://www.synopsys.com/products/logic/design_compiler.html. Synopsys Design Compiler, 2001.
• 15: G. Zimmermann, The MIMOLA design system a computer aided digital processor design method, Proceedings of the 16th Conference on Design automation, p.53-58, June 25-27, 1979, San Diego, CA, United States