Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We address the problem of instruction selection for Multi-Output Instructions (MOIs), producing more than one result. Such inherently parallel hardware instructions are very common in the area of Application Specific Instruction Set Processors (ASIPs) and Digital Signal Processors (DSPs) which are frequently used in System-on-Chips as programmable cores. In order to provide high-level programmability, and consequently guarantee widespread acceptance, sophisticated compiler support for these programmable cores is of high importance. Since it is not possible to model Multi-Output Instructions as trees in the compiler's Intermediate Representation (IR), traditional approaches for code selection are not sufficient. Extending traditional code-generation approaches for MOI-selection is essentially a graph covering problem, which is known to be NP-complete. We present a new heuristic algorithm incorporated in a retargetable code-generator generator capable of exploiting arbitrary inherently parallel MOIs. We prove the concept by integrating the tool into the LCC compiler which has been targeted towards different Instruction Set Architectures based on the MIPS architecture. Several network applications as well as some DSP benchmarks were compiled and evaluated to obtain results.

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: Guido Araujo , Sharad Malik , Mike Tien-Chien Lee, Using register-transfer paths in code generation for heterogeneous memory-register architectures, Proceedings of the 33rd annual conference on Design automation, p.591-596, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240630]
• 3: Christopher W. Fraser , David R. Hanson, A Retargetable C Compiler: Design and Implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 4: Nathan Clark , Amir Hormati , Scott Mahlke , Sami Yehia, Scalable subgraph mapping for acyclic computation accelerators, Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176760.1176779]
• 5: C. Devine. http://xyssl.org, 2007.
• 6: E. Eckstein, O. Koening, and B. Scholz. Code Instruction Selection Based on SSA Graphs. In Proc. of the Workshop on Software and Compilers for Embedded Systems (SCOPES), pages 49--65, Oct. 2003.
• 7: M. Anton Ertl, Optimal code selection in DAGs, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.242-249, January 20-22, 1999, San Antonio, Texas, United States [doi>10.1145/292540.292562]
• 8: C. W. Fraser, D. R. Hanson, and T. A. Proebsting. Engineering Efficient Code Generators Using Tree Matching and Dynamic Programming. Technical Report TR-386-92, 1992.
• 9: C. W. Fraser, R. R. Henry, and T. A. Proebsting. BURG--fast optimal instruction selection and tree parsing. Technical Report CS-TR-1991-1066, 1991.
• 10: Michael R. Garey , David S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1990
• 11: 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]
• 12: Andreas Hoffmann , Heinrich Meyr , Rainer Leupers, Architecture Exploration for Embedded Processors with Lisa, Kluwer Academic Publishers, Norwell, MA, 2002
• 13: Kingshuk Karuri , Mohammad Abdullah Al Faruque , Stefan Kraemer , Rainer Leupers , Gerd Ascheid , Heinrich Meyr, Fine-grained application source code profiling for ASIP design, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065666]
• 14: Matthias Gries , Kurt Keutzer, Building ASIPs: The Mescal Methodology, Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 15: 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
• 16: 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
• 17: C. Liem, T. May, and P. Paulin. Instruction-set Matching and Selection for DSP and ASIP Code Generation. In Proc. of the European Design and Test Conference (ED & TC), pages 31--37, 1994.
• 18: M. Willems and V. "Živojnović. DSP-Compiler: Product Quality for Control-Dominated Applications? In Proc. of the Int. Conf. on Signal Processing Applications and Technology (ICSPAT), Oct. 1996.
• 19: MIPS technologies Inc. MIPS 4Kc Processor Core Datasheet, Jun. 2000.
• 20: S. Kobayashi, Y. Takeuchi, A. Kitajima, M. Imai. Compiler Generation in PEAS-III: an ASIP Development System. In Workshop on Software and Compilers for Embedded Processors (SCOPES), 2001.
• 21: Shuichi Sakai , Mitsunori Togasaki , Koichi Yamazaki, A note on greedy algorithms for the maximum weighted independent set problem, Discrete Applied Mathematics, v.126 n.2-3, p.313-322, 15 March 2003 [doi>10.1016/S0166-218X(02)00205-6]
• 22: Hanno Scharwaechter , David Kammler , Andreas Wieferink , Manuel Hohenauer , Kingshuk Karuri , Jianjiang Ceng , Rainer Leupers , Gerd Ascheid , Heinrich Meyr, ASIP architecture exploration for efficient IPSec encryption: A case study, ACM Transactions on Embedded Computing Systems (TECS), v.6 n.2, p.12-es, May 2007 [doi>10.1145/1234675.1234679]
• 23: S. W. K. Tjiang. An Olive Twig. Technical report, Synopsys Inc., 1993.
• 24: A. Todd. Least-Cost Instruction Selection in DAGs is NP-Complete . In "http://research.microsoft.com/¿toddpro/papers/proof.htm", Feb. 2007.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Microprocessor/microcomputer applications

General Terms:
Design

Keywords:
ASIP, ISS, code-selection, compiler/architecture co-design