With the advent of mobile computing and communications, the power consumption of microprocessors becomes an increasingly important issue. In particular, the investigation of power consumption in individual sub-blocks of processors has shown that power consumed by memory components accounts the greatest percentage of the total power consumption in microprocessors. In the controller design of microprogrammed processors, minimizing the control memory size is crucial in many power-critical applications since the size of the memory is directly related to the power consumption. It is also true for the instruction memory in application-specific VLIW (Very Long Instruction Word) processors.
In this thesis, we present a heuristic algorithm called CLASSIC for the minimization of the control memory width in microprogrammed processors or the instruction memory width of application-specific VLIW processors. CLASSIC results in nearly optimal solutions with the time complexity of $O(n^2)$, where n denotes the number of microoperations. In this thesis, we also propose the so-called incompleteness relations which are exploited for the minimization of the control memory width. Compared to the compatibility class method which applies to fields of mutually exclusive microoperations, our method applies to fields of mutually incomplete microoperations. Since incomplete relation includes exclusive relation, candidate fields in our method are the superset of those in the compatibility class method. This is the reason why our method always achieves better compression ratio than the compatibility class method.
The key features of our algorithm are that 1) it can exploit more combinations of microoperations than compatibility class scheme, and that 2) it can exploit a larger set of incompleteness combinations than the pure AND/OR set scheme. Moreover, CLASSIC can obtain nearly optimal solutions in a reasonable computation time even for big examples, which were not successfully handled by the exhaustive enumeration-based methods.
Experiments using various examples have shown that CLASSIC always achieves smaller microprogram widths compared to the earlier techniques based on the maximal compatibility class or the minimal AND/OR set. The results show that CLASSIC can reduce the control memory width by 34.2% on average compared with a heuristic compatibility class algorithm.
모빌컴퓨팅과 이동통신의 출현과 함께, 잠차적으로 마이크로 프로세서의 전력 소모가 주요 쟁점으로 부각되었다. 특히, 프로세서 각각의 서브 블럭들의 전력 소모에 대한 조사에서는 마이크로 프로세서의 전체 소모 전력 중 메모리 구성부가 가장 많은 부분을 차지하고 있는 것으로 나타나고 있다. 마이크로 프로그램 방식 프로세서의 제어기 설계에 있어 제어 메모리의 크기를 최소화 하는 것은 소모전력에 민감한 많은 응용 분야에 있어 매우 중요한 사안이 되고 있으며, 이것은 메모리의 크기가 전력 소모에 직접적인 영향을 주기 때문이다. 이는 특정 응용의 VLIW에 있어서도 마찬가지이다.
본 논문에서는 마이크로 프로그램 방식 프로세서의 제어 메모리의 폭이나 특정 응용의 VLIW의 명령어 메모리의 폭을 최소화하기 위해 CLASSIC이라 명명된 휴리스틱 알고리즘을 제안하였다. 이 CLASSIC은 거의 최적에 가까운 해를 $O(n^2)$의 계산 시간 복잡도(Time Complexity)를 가지고 구해내고 있다. 또한, 본 논문에서는 제어 메모리의 폭의 최소화를 위해 이용되는 불완전 관계(Incompleteness Relation)를 정의하였다. 기존의 Compatibility Class 방법은 상호 배타성을 이용하는데 비해 본 방법은 상호 불완전성을 이용하고 있으며, 본 방법의 대상 필드는 기존 방법의 필드를 포함하고 있다. 따라서, 본 논문의 제안 방법은 기존의 방법보다 항상 좋은 압축률을 얻을 수 있는 것이다.
본 알고리즘의 주요 특징은 첫째로 Compatibility Class 방법에 비해 보다 많은 마이크로 오퍼레이션의 조합을 이용하며, 둘째로 단순한 AND/OR Set 방법보다 더 큰 불완전성 조합을 이용한다는 것이다. 더욱이, 본 휴리스틱 방법은 완전 탐색 방법으로는 해를 구하기 힘든 큰 예제에서도 만족할 만한 시간에 거의 최적에 가까운 해를 구해낼 수 있었다.
여러가지 예제로서 실험을 해본 바, CLASSIC은 Compatibility Class 나 AND/OR Set에 기초를 둔 기존의 방법보다 항상 좋은 결과를 나타내었다. 그 시험 결과는 CLASSIC이 기존의 휴리스틱 방법에 비해 제어 메모리의 폭을 평균적으로 34.2%까지 더 줄일 수 있음을 보여주고 있다.