FPGA-friendly code compression for horizontal microcoded custom IPs

ABSTRACT

Shrinking time-to-market and high demand for productivity has driven traditional hardware designers to use design methodologies that start from high-level languages. However, meeting timing constraints of automatically generated IPs is often a challenging and time-consuming task that must be repeated every time the specification is modified. To address this issue, a new generation of IP-design technologies that is capable of generating custom datapaths as well as programming an existing one is developed. These technologies are often based on Horizontal Microcoded Architectures. Large code size is a well-know problem in HMAs, and is referred to as "code bloating" problem.In this paper, we study the code size of one of the new HMA-based technologies called NISC. We show that NISC code size can be several times larger than a typical RISC processor, and we propose several low-overhead dictionary-based code compression techniques to reduce the code size. Our compression algorithm leverages the knowledge of "don't care" values in the control words to better compress the content of dictionary memories. Our experiments show that by selecting proper memory architectures the code size of NISC can be reduced by 70% (i.e. 3.3 times) at cost of only 9% performance degradation. We also show that some code compression techniques may increase number of utilized block RAMs in FPGA-based implementations. To address this issue, we propose combining dictionaries and implementing them using embedded dual-port memories.

REFERENCES

• 1: M. Byatt, "Data plane processing with configurable architectures", ARM white paper, 2003.
• 2: N. Clark, H. Zhong, K. Fan, S. Mahlke, K. Flautner, K. Van Nieuwenhove, "OptimoDE: Programmable Accelerator Engines Through Retargetable Customization", Hot Chips, 2004.
• 3: S. Bashford, U. Bieker, B. Harking, R. Leupers, P. Marwedel, A. Neumann, D. Voggenauer, "The MIMOLA Language - Version 4.1. Technical Report." Computer Science Dept., University of Dortmund, 1994.
• 4: http://www.cecs.uci.edu/~nisc
• 5: Mehrdad Reshadi , Daniel Gajski, A cycle-accurate compilation algorithm for custom pipelined datapaths, 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.1084845]
• 6: Mehrdad Reshadi , Bita Gorjiara , Daniel Gajski, Utilizing Horizontal and Vertical Parallelism with a No-Instruction-Set Compiler for Custom Datapaths, Proceedings of the 2005 International Conference on Computer Design, p.69-76, October 02-05, 2005 [doi>10.1109/ICCD.2005.112]
• 7: 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]
• 8: A. Agrawala, T. Rauscher, Foundations of Microprogramming: Architecture, Software, and Applications, Academic Press, ISBN: 0120451506, 1976.
• 9: Roman Lysecky , Frank Vahid, A Study of the Speedups and Competitiveness of FPGA Soft Processor Cores using Dynamic Hardware/Software Partitioning, Proceedings of the conference on Design, Automation and Test in Europe, p.18-23, March 07-11, 2005 [doi>10.1109/DATE.2005.38]
• 10: MiBench benchmark: http://www.eecs.umich.edu/mibench/
• 11: MAD: MPEG Audio Decoder: http://www.underbit.com/products/mad/
• 12: Keith D. Cooper , Nathaniel McIntosh, Enhanced code compression for embedded RISC processors, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.139-149, May 01-04, 1999, Atlanta, Georgia, United States
• 13: Darko Kirovski , Johnson Kin , William H. Mangione-Smith, Procedure based program compression, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.204-213, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 14: Saumya K. Debray , William Evans , Robert Muth , Bjorn De Sutter, Compiler techniques for code compaction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.2, p.378-415, March 2000 [doi>10.1145/349214.349233]
• 15: A. Halambi , A. Shrivastava , P. Biswas , N. Dutt , A. Nicolau, An Efficient Compiler Technique for Code Size Reduction Using Reduced Bit-Width ISAs, Proceedings of the conference on Design, automation and test in Europe, p.402, March 04-08, 2002
• 16: S. Y. Liao , S. Devadas , K. Keutzer, Code density optimization for embedded DSP processors using data compression techniques, Proceedings of the 16th Conference on Advanced Research in VLSI (ARVLSI'95), p.272, March 27-29, 1995
• 17: Simon Segars , Keith Clarke , Liam Goudge, Embedded Control Problems, Thumb, and the ARM7TDMI, IEEE Micro, v.15 n.5, p.22-30, October 1995 [doi>10.1109/40.464580]
• 18: R. Grehan, "16-bit: The good, the bad, your options," Embedded Systems Programming, 1997 {Online}. Available: http://www.embedded.com/1999/9908/9908sr.htm
• 19: Andrew Wolfe , Alex Chanin, Executing compressed programs on an embedded RISC architecture, Proceedings of the 25th annual international symposium on Microarchitecture, p.81-91, December 01-04, 1992, Portland, Oregon, United States
• 20: IBM, CodePack PowerPC code Compression Utility User's Manual Version 3.0, IBM, 1998.
• 21: T. M. Kemp , R. K. Montoye , J. D. Harper , J. D. Palmer , D. J. Auerbach, A decompression core for powerPC, IBM Journal of Research and Development, v.42 n.6, p.807-812, November 1998
• 22: Charles Lefurgy , Eva Piccininni , Trevor Mudge, Evaluation of a high performance code compression method, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.93-102, November 16-18, 1999, Haifa, Israel
• 23: G. Pechanek, S. Larin, T. Conte, "Any-size instruction abbreviation technique for embedded DSPs", ASIC/SoC Conference, 2002.
• 24: Marc L. Corliss , E. Christopher Lewis , Amir Roth, DISE: a programmable macro engine for customizing applications, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 25: C. Fraser. "An instruction for direct interpretation of LZ77-compressed programs." Technical Report MSR-TR-2002-90, Microsoft Research, Microsoft Corporation, 2002.
• 26: 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
• 27: T. Jensen, B. Toft, Graph coloring problems. Wiley-Interscience, New York, 1995, ISBN 0-471-02865-7.
• 28: Xilinx Product Specification, "Block memory generator", version 1.1, 2006.
• 29: Bita Gorjiara , Mehrdad Reshadi , Pramod Chandraiah , Daniel Gajski, Generic netlist representation for system and PE level design exploration, Proceedings of the 4th international conference on Hardware/software codesign and system synthesis, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176254.1176323]

INDEX TERMS

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

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
FPGA, dictionary-based compression, memory optimization, microcoded architectures, no-instruction-set computer