Merged Dictionary Code Compression for FPGA Implementation of Custom Microcoded PEs

ABSTRACT

Horizontal Microcoded Architecture (HMA) is a paradigm for designing programmable high-performance processing elements (PEs). However, it suffers from large code size, which can be addressed by compression. In this article, we study the code size of one of the new HMA-based technologies called No-Instruction-Set Computer (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 its code size. Our compression algorithm leverages the knowledge of “don't care” values in the control words and can reduce the code size by 3.3 times, on average. Despite such good results, as shown in this article, these compression techniques lead to poor FPGA implementations because they require many on-chip RAMs. To address this issue, we introduce an FPGA-aware dictionary-based technique that uses the dual-port feature of on-chip RAMs to reduce the number of utilized block RAMs by half. Additionally, we propose cascading two-levels of dictionaries for code size and block RAM reduction of large programs. For an MP3 application, a merged, cascaded, three-dictionary implementation reduces the number of utilized block RAMs by 4.3 times (76%) compared to a NISC without compression. This corresponds to 20% additional savings over the best single level dictionary-based compression.

REFERENCES

• 1: Agrawala, A. and Rauscher, T. 1976. Foundations of Microprogramming: Architecture, Software, and Applications. Academic Press.
• 2: Codwell, R., Nix, R., Donnell, J., Papworth, D., and Rodman, P. 1987. A VLIW architecture for a trace scheduling compiler. ACM SIGOPS Operat. Syst. Rev. 21, 4.
• 3: 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
• 4: Fraser, C. 2002. An instruction for direct interpretation of LZ77-compressed programs. Tech. rep. MSR-TR-2002-90, Microsoft Research, Microsoft Corporation.
• 5: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 6: Gorjiara, B. 2007. Synthesis and optimization of custom low-power NISC processors. Ph.D. dissertation, University of California, Irvine.
• 7: Gorjiara, B. and Gajski, D. 2005. Custom processor design using NISC: A case-study on DCT algorithm. In Proceedings of the IEEE Workshop on Embedded Systems for Real-Time Multimedia (ESTIMedia).
• 8: Gorjiara, B. and Gajski, D. 2007. A novel profile-driven technique for simultaneous power and code-size optimization of nanocoded IPs. In Proceedings of the International Conference on Computer Design (ICCD).
• 9: Bita Gorjiara , Daniel Gajski, Automatic architecture refinement techniques for customizing processing elements, Proceedings of the 45th annual conference on Design automation, June 08-13, 2008, Anaheim, California [doi>10.1145/1391469.1391571]
• 10: 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]
• 11: Grehan, R. 1997. 16-bit: The good, the bad, your options. Embed. Syst. Prog.
• 12: Ishiura, N. and Yamaguchi, M. 1997. Instruction code compression for application specific VLIW processors based on automatic field partitioning. In Proceedings of the International Conference on Synthesis and System Integration of Mixed Information System (SASIMI).
• 13: Jensen, T. and Toft, B. 1995. Graph Coloring Problems. Wiley-Interscience. New York.
• 14: 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
• 15: Jeremy Lau , Stefan Schoenmackers , Timothy Sherwood , Brad Calder, Reducing code size with echo instructions, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951724]
• 16: 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
• 17: Haris Lekatsas , Jörg Henkel , Venkata Jakkula, Design of an one-cycle decompression hardware for performance increase in embedded systems, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513929]
• 18: J. Prakash , C. Sandeep , Priti Shankar , Y. N. Srikant, A Simple and Fast Scheme for Code Compression for VLIW Processors, Proceedings of the Conference on Data Compression, p.444, March 25-27, 2003
• 19: R. E. Krichevskii, Universal Compression and Retrieval, Kluwer Academic Publishers, Norwell, MA, 1994
• 20: B. Ramakrishna Rau , David W. L. Yen , Wei Yen , Ross A. Towie, The Cydra 5 Departmental Supercomputer: Design Philosophies, Decisions, and Trade-Offs, Computer, v.22 n.1, p.12-26, 28-30, 32-35, January 1989 [doi>10.1109/2.19820]
• 21: Mohammad Reshadi , Daniel Gajski, No-instruction-set-computer (nisc) technology modeling and compilation, California State University at Long Beach, Long Beach, CA, 2007
• 22: 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]
• 23: Mehrdad Reshadi , Daniel Gajski, Interrupt and low-level programming support for expanding the application domain of statically-scheduled horizontal-microcoded architectures in embedded systems, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
• 24: 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]
• 25: Mehrdad Reshadi , Bita Gorjara , Daniel Gajski, C-based design flow: a case study on G.729A for voice over internet protocol (VoIP), Proceedings of the 45th annual conference on Design automation, June 08-13, 2008, Anaheim, California [doi>10.1145/1391469.1391489]
• 26: Montserrat Ros , Peter Sutton, A hamming distance based VLIW/EPIC code compression technique, Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems, September 22-25, 2004, Washington DC, USA [doi>10.1145/1023833.1023853]
• 27: Saghir, M. 1998. Application-specific instruction-set architectures for embedded SDP applications. Ph.D. thesis, University of Toronto.
• 28: 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]
• 29: Jelena Trajkovic , Mehrdad Reshadi , Bita Gorjiara , Daniel Gajski, A Graph Based Algorithm for Data Path Optimization in Custom Processors, Proceedings of the 9th EUROMICRO Conference on Digital System Design, p.496-503, August 30-September 01, 2006 [doi>10.1109/DSD.2006.7]
• 30: Wang, K. 2001. Code compaction for VLIW instructions. M.S. thesis, University of Toronto.
• 31: 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]
• 32: 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
• 33: Yuan Xie , Wayne Wolf , Haris Lekatsas, A code decompression architecture for VLIW processors, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

General Terms:
Algorithms, Design, Experimentation, Performance

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