Microcode compression algorithms

Author(s)

Edson Borin

• Document type: Doctoral Thesis
• Press: Campinas, SP.
• Institution: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Defense date: 2007-04-04

Examining board members

Guido Costa Souza de Araújo; Edil Severiano Tavares Fernandes; Mauricio Breternitz Junior; Paulo Cesar Centoducatte; Rodolfo Jardim de Azevedo; Luiz Claudio Villar dos Santos; Sandro Rigo

• Advisor: Guido Costa Souza de Araújo

Abstract

Microprogramming is a widely known technique used to implement processor control units. Microcode makes the control unit design process easier, as it can be modified to enhance functionality and to apply patches to an existing design. As more features get added to a CPU core, the area and power costs associated with the microcode increase. In a recent Intel internal design, targeted to low power and small footprint, the area and the power consumption costs associated with the microcode approached 20% of the total die. In this work, we investigate the use of compression techniques to reduce the microcode size. Based on the constraints imposed by high performance processor design, we analyze the existing microcode and code compression techniques and show that the two level microcode compression technique is the most appropriate to compress the microcode on high performance processor. This technique replaces the original microinstructions by pointers to dictionaries that hold bit patterns extracted from the microcode. The ¿pointer arrays¿ and the ¿dictionaries¿ are ROMs that store the pointers and the bit patterns, respectively. The technique allows the microcode columns to be grouped into clusters, so that the number of bit patterns inside the dictionaries is reduced. In order to maximize the microcode compression, similar columns must be grouped together. The main contribution of this thesis is a set of algorithms to group similar microcode columns into clusters, so as to maximize the microcode size reduction. Experimental results, using microcodes from production processors and processors in advanced development stages, show that the proposed algorithms improve from 6% to 20% the compression results found by previous works and compress the microcode to 50% of its original size. We show the importance of compressing microcode under design constraints such as the number of dictionaries and the number of columns per dictionary. We also prove that, under these constraints, the problem of grouping similar columns is NP-Complete. Finally, we propose an algorithm to group similar columns under such constraints. The experimental results show that the proposed algorithm provides good compression results (AU)