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 widely used to solve this kind of combinatorial problems. The technique is known to produce near optimal solutions in much shorter time than the exhaustive search method. We adopted the technique to determine the orders of microprogram sequences. A fast and accurate cost estimation procedure is still the key point in this strategy. There are two technologies for implementing the instruction decoder; one is PLA which is used to implement two-level logic expressions and the other is standard cell which is used to implement multi-level logic expressions. We proposed an area-minimal PLA implementation method for the instruction decoder. Using the concepts developed in output encoding fields, we devised a fast and accurate cost estimation procedure; our procedure was more than 100 times faster and more accurate than ESPRESSO-II with fast option. Using a simulated annealing technique in which our cost estimation procedure was incorporated, we obtained, on the average, 10$\sim$40\% reduction of the number of product terms for the resulting instruction decoder PLA compared to the results of random encoding for various sizes of examples. We also obtained, on the average, 11\% better results for the same examples in about 100 times faster CPU time compared to those of the simulated annealing technique which uses ESPRESSO-II as a cost estimation procedure. We also proposed an area-minimal multi-level implementation method for the instruction decoder. To devise a fast and accurate cost estimation procedure, we adopted and modified the concepts of FSM encoding methods and used the fact that an optimal two-level implementation is usually transformed to a good multi-level implementation. Using a simulated annealing technique incorporated with our cost estimation procedure, we obtained, on the average, 9.8$\sim$34.4\% reduction of the number of literals for the resulting factored form expression of the instruction decoder compared to the results of random encoding for the same examples used in chapter II. Our cost estimation procedure was more than 1000 times faster than misII with standard script. Finally, our methods were applied to a real design example of the instruction decoder of k386 which is a 32-bit general purpose CISC-type microprocessor. We first showed that the proposed problem formulation can easily be extended to accommodate conditional jumps and subroutine calls in microprogramming. We also proposed a divide-and-conquer technique to handle large problems with more than 100 outputs in a reasonable computing time on workstations. The instruction decoder of the k386 has 379 symbols to be encoded using one of our methods. An experiment showed that it would take about 2,400 CPU hours on SPARCstation-2 to get a near optimal solution by considering all the symbols simultaneously. So, we used the divide-and-conquer technique and, in about 6 CPU hours on SPARCstation-10, we got 14\% better result for PLA implementation and about 8\% better result for standard cell implementation of the instruction decoder compared to those of our microcode development group obtained.
본 논문에서는 마이크로프로그램을 사용한 컨트롤방식을 채택하는 시스템에서의 명령어 해독기를 최소면적을 사용하여 설계하는 방법을 연구하였다. 명령어 해독기의 입력은 시스템의 기계언어이고 출력은 입력된 기계연어를 순차적으로 해석하는 마이크로프로그램의 시작번지가 된다. 일반적으로 기계언어는 2진수로 코드화되어 있고, 같은 계열의 시스템에서는 고정되어 있다. 그렇지 않은 경우에는 기존의 입력 부호화 방법으로 보다 나은 2진수 코드를 얻을 수 있으므로, 본 논문에서는 다루지 않았다. 앞에서 말한 바와 같이 명령어 해독기의 면적을 줄이기 위한 고려는 출력 부호화로 한정된다. 기존에 연구되어 있는 출력 부호화 방법으로 이 문제를 다룰 수 없는 이유는 다음과 같다; 출력의 코드로 사용될 수 있는 것은 마이크로프로그램을 저장하고 있는 메모리 소자의 주소공간으로 한정되며, 일반적으로 어떤 기계언어에 대응하는 마이크로프로그램 루틴은 1 보다 크거나 같은 불특정한 길이를 갖게되므로, 이들 중에서도 제한된 것들만이 사용되게 된다. 또한, 이 제한된 코드들도 마이크로프로그램 루틴들이 배치되기 전까지는 정해진 것이 아니다. 본 논문에서는 먼저 마이크로그램 방식을 조건부점프와 서브루틴 콜이 없는 단순방식으로 한정하면, 출력 부호화 문제는 마이크로프로그램 루틴들을 1차원적으로 순서를 정하여 배치하는 문제로 정의할 수 있음을 보였다(2장2절 참조). 이와같은 문제에서는, 어떤 순서가 최소면적을 갖는 출력부호들을 내어줄 것인지를 결정할 수 있는 수단이 필요하게 된다. 이러한 수단이 갖추어야 할 필수요건은 빠름과 정확함이다. N개의 마이크로프로그램 루틴들이 있는 경우에, 최소면적을 갖는 순서를 찾기 위하여 살펴보아야 하는 경우의 수는 N!로 주어지기 때문이다. 정확도를 높이기 위하여는 기존의 2단계 논리함수 최소화 프로그램(ESPRESSO-II) 또는 다단계 논리함수 최소화 프로그램(misII)을 사용할 수 있지만, 비교적 작은 명령어 해독기의 경우에도, 이들을 이용하여 N!의 경우를 살펴보는데는 비현실적으로 많은 CPU time이 소용된다. 살펴보아야 할 경우의 수가 이와같이 방대할 경우에 주로 사용되는 기법은 시뮬레이티드 어닐링이다. 이 기법은, 일부의 경우의 수 만을 살펴보면서도 최소에 가까운 해답을 얻을 수 있는 방법으로 널리 사용되고 있다. 본 논문에서는 이 기법에 의하여 마이크로프로그램 루틴들의 1차원적인 순서를 정하였다. 이 문제해결기법의 성패는, 주어진 순서의 좋고 나쁨을 판단하는 수단의 빠름과 정확함에 크게 의존한다. 명령어 해독기를 구현하는 기술은 크게 두가지로 분류된다; 그 하나는 2 단계 논리함수를 구현하는 것으로 PLA가 있으며, 다른 하나는 다단계 논리함수를 구현하는 것으로 스탠다드 셀이 있다. 2장에서는 명령어 해독기를 최소면적을 같는 PLA로 구현하기 위한 방법을 제시하였다. 종래의 부호화 방법에서 연구된 개념을 도입하여 빠르고 정확한 판단수단을 개발하 였으며, 이 판단수단을 사용한 시뮬레이티드 어닐링기법으로 빠른 시간내에 좋은 결과를 얻을 수 있었다; 개발된 판단수단이 기존의 ESPRESSO-II(with fast option)보다 100배 이상 빠른 것과 정확히 판단하는 것을 실험적으로 살펴보았으며, 이를 사용한 시뮬레이티드 어닐링기법으로 랜덤인코딩기법보다는 평균적으로 10$\sim$40\%, ESPRESSO-II(with fast option)를 판단수단으로 사용한 시뮬레이티드 어닐링기법보다는 100배 정도 빠른 시간내에 평균적으로 11\% 나온 결과를 얻을 수 있었다. 3장에서는 명령어 해독기를 최소면적을 갖는 다단계 논리회로로 구현하기 위한 방법 을 제시하였th?. 2장에서와 같이, 빠른 판단수단을 개발하고 이를 이용하는 시뮬레이티드어닐링기법으로 문제를 해결하였다. 판단수단을 개발하기 위하여는, 종래에 스테이트머신의 부호화에 쓰여온 방법을 수정하여 이용하였으며, 또한, "어떤 논리함수의 2단계 논리회로의 크기와 이의 다단계 논리회로의 크기는 일반적으로 비례한다"는 사실을 이용하였다. 이와같이 하여 개발된 판단수단을 이용한 시뮬레이티드 어닐링기법으로 랜덤인코딩기법보다 평균 9.8$\sim$34.4\% 정도 나온 결과를 얻을 수 있었다. 개발된 판단수단은 기존의 수단(misII with standard script)보다 1000배 이상 빠른 것으로 관찰되었다. 4장에서는 2장과 3장에서 제안된 방법들을 실제의 명령어 해독기(32비트 범용 마이크로프로세서(k386)의 명령어해독기)를 구현하는 데 적용하여 보았다. 여기서는 마이크로프로그램에서의 조건부 점프와 서브루틴 콜을 다룰 수 있도록 제안된 방법을 확장할 수 있다는 것을 보였다. 또한, 문제의 크기가 $N>100$으로 되는 커다란 문제를 워크스테이션 정도의 컴퓨터에서 적정한 시간내에 해결할 수 있도록 하는 일종의 divide-and-conquer기법을 제안하였다. k386의 명령어 해독기는 N=379 인 문제로, 이와같은 기법을 도입하지 않을 경우에는 SPARCstation-2 컴퓨터로 대략 2,400 CPU hours의 시간이 필요한 것으로 추산되었다. 따라서 이와같은 기법이 필요하며, 이 기법으로 SPARCstation-10에서 약 6 CPU hours만에 얻은 결과는 k386의 마이크로프로그램 개발팀이 얻은 결과보다 2단계 논리회로의 경우 14\%, 다단계 논리회로의 경우에는 8\% 정도 나은 결과를 보였다.
