ARM程式碼之分離式字典壓縮技術

Abstract

對嵌入式處理器（Embedded processor）而言，深深受限於製造成本、電力消耗與晶片尺寸等因素，使得在嵌入式平台上，應用系統的發展遭遇瓶頸。一般而言，愈大的晶片面積或愈寬的匯流排往往使得製造成本提高以及造成更多的功率消耗。在大部分的嵌入式處理器中，程式記憶體（Program memory）常佔有整個晶片面積的絕大部分，而壓縮程式碼可以減低處理器對程式記憶體的需求，進而減小處理器晶片的尺寸與製造成本。在本篇論文中，有別於傳統字典壓縮法中利用單一字典存放完整的指令序列，我們引用操作碼（ Opcode）和運算元（Operand）序列分開建立字典的想法，以及提出五種進階的壓縮技術—提出條件欄位、運算元重新導向、多數運算元取代、壓縮跳躍指令和子字典成員重新索引，進一步地壓縮字典大小，並利用剩餘的空間引入更多的字典成員，使得程式碼可以被壓縮得更小。舉例來說，導入運算元重新導向（Operand remapping）和多數運算元（Operand majority）的方法，就是利用比較少的位元數分別記錄在一個運算元序列中運算元的相依性與出現次數最多的運算元。實驗結果顯示，新的壓縮方法可以達到平均38%的壓縮率，相較於傳統字典壓縮方法或ARM所提出的Thumb指令集可達到的70%壓縮率，可以說是一項重大的改進。

For most embedded systems, program memory occupies a significant portion of the circuit. A larger die size or wider bus causes more cost and power consumption. Compressing program code will not only reduce the cost of embedded systems by reducing instruction memory requirement, but also reduce the demand of external instruction fetch bandwidth. In this thesis, we use a code compression approach that establishes partitioned dictionaries according to the opcode and operand sequences rather than a single dictionary with full 32-bit instruction sequences. We also propose five advanced compression techniques – factorizing condition field in ARM instructions, using operand remapping and operand majority, compressing across branch instructions, and redirecting the index of sub-dictionary entry – to reduce the dictionary size in advance and include more dictionary entries to make the programs smaller. For example, operand remapping and operand majority use less bits to record the dependencies and the most frequent operands in the operand sequences, respectively. Experimental results show that on average 38% compression ratio can be achieved. Compared with 70% compression ratio of the traditional dictionary-based compression method or the Thumb instruction set proposed by ARM, the partitioned dictionary-based code compression with the operand remapping techniques presented in this thesis contributes a great deal.