Reducing code size for heterogeneous-connectivity-based VLIW DSPs through synthesis of instruction set extensions

ABSTRACT

VLIW DSP architectures exhibit heterogeneous connections between functional units and register files for speeding up special tasks. Such architectural characteristics can be effectively exploited through the use of complex instruction set extensions (ISEs). Although VLIWs are increasingly being used for DSP applications to achieve very high performance, such architectures are known to suffer from increased code size. This paper addresses how to generate ISEs that can result in significant code size reduction in VLIW DSPs without degrading performance. Unfortunately, contemporary techniques for instruction set synthesis fail to extract legal ISEs for heterogeneous-connectivity-based architectures. We propose a Heuristic-based algorithm to synthesize ISEs for a generalized heterogeneous-connectivity-based VLIW DSP architecture. We achieve an average code size reduction of 25% on the MiBench suite with no penalty in performance by applying our ISE generation algorithm on the TI TMS320C6xx, a representative VLIW DSP.

REFERENCES

• 1: http://www.ti.com. TI TMS320C6xx user manual.
• 2: Silvina Hanono , Srinivas Devadas, Instruction selection, resource allocation, and scheduling in the AVIV retargetable code generator, Proceedings of the 35th annual conference on Design automation, p.510-515, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277184]
• 3: Thomas M. Conte , Sanjeev Banerjia , Sergei Y. Larin , Kishore N. Menezes , Sumedh W. Sathaye, Instruction fetch mechanisms for VLIW architectures with compressed encodings, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.201-211, December 02-04, 1996, Paris, France
• 4: Shail Aditya, Scott A. Mahlke and B. Ramakrishna Rau. Code Size Minimization and Retargetable Assembly for EPIC and VLIW Instruction Formats. Technical Report, HP Labs PL-2000-141.
• 5: Michael Kozuch , Andrew Wolfe, Compression of Embedded System Programs, Proceedings of the1994 IEEE International Conference on Computer Design: VLSI in Computer & Processors, p.270-277, October 10-12, 1994
• 6: Stan Y. Liao, Srinivas Devadas and Kurt Keutzer. Code Density Optimization for Embedded DSP Processors using Data Compression Techniques. IEEE Transactions on CAD, 17(7):601--608, 1998.
• 7: Huiyang Zhou , Thomas M. Conte, Code Size Efficiency in Global Scheduling for ILP Processors, Proceedings of the Sixth Annual Workshop on Interaction between Compilers and Computer Architectures, p.79, February 03-03, 2002
• 8: Jong-eun Lee , Kiyoung Choi , Nikil Dutt, Efficient instruction encoding for automatic instruction set design of configurable ASIPs, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.649-654, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774668]
• 9: Hoon Choi , Jong-Sun Kim , Chi-Won Yoon , In-Cheol Park , Seung Ho Hwang , Chong-Min Kyung, Synthesis of Application Specific Instructions for Embedded DSP Software, IEEE Transactions on Computers, v.48 n.6, p.603-614, June 1999 [doi>10.1109/12.773797 ]
• 10: 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
• 11: Marnix Arnold and Henk Corporaal. Instruction Set Synthesis Using Operation Pattern Detection. 5th Annual Conference of ASCI, 1999.
• 12: Fei Sun , Srivaths Ravi , Anand Raghunathan , Niraj K. Jha, Synthesis of custom processors based on extensible platforms, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.641-648, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774667]
• 13: 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]
• 14: Partha Biswas and Nikil Dutt. Greedy and Heuristic-based Algorithms for Synthesis of Complex Instructions in Heterogeneous-Connectivity-based DSPs. UCI-ICS TR 03-16, 2003.
• 15: R.M. Karp. Reducibility Among Combinatorial Problems. Complexity of Computer Computations, Plenum Press, 1972.
• 16: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 17: 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]
• 18: Mathew R. Guthaus, Jeffrey S. Ringenberg, Dan Ernst, Todd M. Austin, Trevor Mudge and Richard B. Brown. MiBench: A Free Commercially Representative Embedded Benchmark Suite. http://www.eecs.umich.edu/jringenb/mibench/.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles

General Terms:
Algorithms, Design, Performance

Keywords:
dependence conflict graph, heterogeneous-connectivity-based DSP, instruction set architecture, instruction set extensions, restricted data dependence graph, static single assignment