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 and Srinivas Devadas. Instruction Selection, Resource Allocation and Scheduling in the AVIV Retargetable Code Generator. In Proc. of the Design Automation Conference (DAC), pages 510--515, 1998.
3. Thomas M. Conte, Sanjeev Banerjia, Sergei Y. Larin, Kishore N. Menezes and Sumedh W. Sathaye. Instruction Fetch Mechanisms for VLIW Architectures with Compressed Encodings. In Proc. 29th Int'l Symposium on Microarchitecture, pages 201--211, 1996.
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. M. Kozuch and A. Wolfe. Compression of Embedded System Programs. In Proc. of the Int'l Conference on Computer Design (ICCD), pages 270--277, 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 and Thomas M. Conte. Code Size Efficiency in Global Scheduling for ILP Processors. 6th Annual Workshop on ICCA, 2002.
8. Jong-eun Lee, Kiyoung Choi and Nikil Dutt. Efficient Instruction Encoding for Automatic Instruction Set Design of Configurable ASIPs. In Proc. of the Int'l Conference on Computer Aided Design (ICCAD), 2002.
9. "Hoon Choi, Jong-Sun Kim, Chi-Won Yoon, In-Cheol Park, Seung Ho Hwang and Chong-Min Kyung. Synthesis of Application Specific Instructions for Embedded DSP Software. IEEE Transactions on Computers, 1999.
10. Rainer Leupers and Peter Marwedel. Instruction Selection for Embedded DSPs with Complex Instructions. In Proc. of the European Design Automation Conference (EURO-DAC), 1996.
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 and Niraj K. Jha. Synthesis of Custom Processors Based on Extensible Platforms. In Proc. of the Int'l Conference on Computer Aided Design (ICCAD), 2002.
13. Kubilay Atasu, Laura Pozzi and Paolo Ienne. Automatic Application-Specific Instruction-Set Extensions under Microarchitectural Constraints. In Proc. of the Design Automation Conference (DAC), 2003.
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. S.S. Muchnick. Advanced Compiler Design and Implementation, Morgan Kaufmann, 1997.
17. Ashok Halambi, Peter Grun, Vijay Ganesh, Asheesh Khare, Nikil Dutt and Alex Nicolau. EXPRESSION: A language for architecture exploration through compiler/simulator retargetability. In Proc. of the Conference on Design, Automation and Test in Europe (DATE), 1999.
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

• Computer systems organization

  • Architectures

    • Other architectures