(A) study on the output encoding method for the practical design of the instruction decoder for microprogrammed controllers

Abstract

This thesis presents area-minimal design methods for the instruction decoder of microprogrammed controllers. The input and output of the instruction decoder are set of macroinstructions and set of starting addresses for the corresponding microprogram sequences, respectively. In general, the macroinstructions are encoded with binary code and they are fixed in a family of systems. Otherwise, they can be encoded using already known input encoding methods. Therefore, we do not consider the encoding of macroinstructions in this thesis. The remaining variable to be considered for an area-minimal design of the instruction decoder is the encoding of outputs. However, we can not apply any existing output encoding methods to the encoding of outputs. Unlike conventional output encoding problems, the encoding space is constrained to be within the address space of microcode memory and only a part of the whole address space of the microcode memory can be used as candidates for output codes. Moreover, the partial code set changes dynamically according to the rearrangement of the order of each microprogram sequence in microcode memory. In this thesis, we first show that the problem of encoding outputs of the instruction decoder is equivalent to determining linear orders of microprogram sequences if we exclude conditional jump and subroutine call in microprogramming. To solve this problem, we need a procedure that assesses an ordering in terms of area required to implement the instruction decoder which is specified by the ordering. This cost estimation procedure must be fast and accurate. When there are N microprogram sequences, we have to search N$!$ cases using a cost estimation procedure to find an optimum ordering. To increase accuracy of this search process, we can use two-level logic minimizer such as ESPRESSO-II or multi-level logic minimizer such as misII. However, this strategy takes too much time even for small instruction decoders. Simulated annealing technique is wi...