Bitmask-based control word compression for NISC architectures

ABSTRACT

Implementing a custom hardware is not always feasible due to cost and time considerations. No instruction set computer (NISC) architecture is one of the promising direction to design a custom datapath for each application using its execution characteristics. A major challenge with NISC control word is that they tend to be at least 4 to 5 times larger than regular instruction size, thereby imposing higher memory requirement. A promising approach is to compress these control words to reduce the code size of the application. This article proposes an efficient bitmask-based compression technique to drastically reduce the control word size while keeping the decompression overhead minimal. The main contributions of our approach are: i) efficient don't care resolution for maximum bitmask coverage using limited dictionary entries, ii) run length encoding to significantly reduce repetitive control words, and iii) smart encoding of constant and less frequently changing bits. Our experimental results demonstrate that our approach improves compression efficiency by an average of 20% over the best known control word compression, giving a compression ratio of 25% to 35%.

REFERENCES

• 1: 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
• 2: Charles Lefurgy , Peter Bird , I-Cheng Chen , Trevor Mudge, Improving code density using compression techniques, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.194-203, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 3: Bita Gorjiara , Daniel Gajski, FPGA-friendly code compression for horizontal microcoded custom IPs, Proceedings of the 2007 ACM/SIGDA 15th international symposium on Field programmable gate arrays, February 18-20, 2007, Monterey, California, USA [doi>10.1145/1216919.1216935]
• 4: Haris Lekatsas , Jörg Henkel , Venkata Jakkula, Design of an one-cycle decompression hardware for performance increase in embedded systems, Proceedings of the 39th annual Design Automation Conference, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513929]
• 5: T. Jensen and B. Toft. Graph coloring problems. Discrete Mathematics and Optimization. Wiley-Interscience, 1995.
• 6: N. Ishiura and M. Yamaguchi. Instruction code compression for application specific VLIW processors based of automatic field partitioning. SASIMI, 105--109, 1997.
• 7: Mohammad Reshadi , Daniel Gajski, No-instruction-set-computer (nisc) technology modeling and compilation, California State University at Long Beach, Long Beach, CA, 2007
• 8: S. Liao, S. Devadas and K. Keutzer. Code density optimization for embedded DSP processors using data compression techniques. Adv. Res. VLSI, 393--399, 1995.
• 9: S. Seong and P. Mishra. Bitmask-based code compression for embedded systems. IEEE Trans. CAD, 27(4): 673--685, 2008.

INDEX TERMS

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

General Terms:
Algorithms, Design

Keywords:
compression, no instruction set computer