The design of control unit in VLSI requires careful attention. It must guarantee maximal performance of the data path. Also it should not require excessive area nor introduce critical paths. But current VLSI technology made designers difficult to optimize the cost functions at hand because of the increase in the level of integration. In this thesis, algorithmic methods which can optimize objective functions of control units such as power and area are addressed.
In chapter 2, the problem of minimizing the control store width is addressed. It is very important in the design of microprogrammed processors, because it is directly related to the silicon area of control unit. For the minimization of the control store width three approaches are presented. The first two methods target minimal encoding scheme. One of them uses integer linear programming formulation by representing the cost function in linear form. It gives optimal solutions for only small-sized problems. The other is a heuristic approach using the graph partitioning algorithm. The minimal encoding scheme is modeled by graph partitioning problem. This approach gives nearly optimal solutions with the reasonable amount of time. And the last approach is based on the notion of minimal dependence sets. The problem can be transformed into the minimal column covering. An heuristic method for minimal column covering is given. The experimental results show that this method is efficient for highly parallel microcode.
In chapter 3, a state assignment algorithm of Finite State Machines for minimal switching power consumption is proposed. Low power is essential due to not only packaging and cooling costs but also lifetime of integrated circuits and batteries. The proposed algorithm minimizes the switching activity caused by state transitions by assigning codes closer in Hamming distance to the states with higher state transition probabilities. First, the proposed algorithm calculates the state transition probabilities. Next, the state assignment is transformed into graph partitioning problem. The nodes of the graph model are partitioned such that Hamming distance between each pair of nodes with high edge density is to be minimized. Experimental results show that the proposed algorithm is efficient in minimizing switching power consumption even though it requires more area than those algorithms targeting area minimization.
VLSI 시스템의 제어기를 설계하기 위해서는 여러가지의 사항을 고려하여야 한다. 먼저 제어기는 데이타 경로의 최대 성능을 보장할 수 있어야 한다. 또한 과다한 면적을 차지하거나 임계 경로를 형성해서는 안 된다. 그러나 현재의 VLSI 기술은 복잡도가 갈수록 높아져 가기 때문에 설계자가 면적이나 속도, 또는 파워와 같은 비용 함수를 직접 최적화하기가 힘들어 졌다. 본 논문에서는 제어기의 면적이나 파워와 같은 비용 함수들을 최적화할 수 있는 알고리즘들을 제안하였다.
2장에서는 제어 메모리의 폭을 최소화하는 방법들이 제안되었다. 제어 메모리는 마이크로 프로그램 방식의 프로세서에서 대부분의 면적을 차지하기 때문에 이의 면적을 줄이는 것은 중요하다. 먼저 최소 부호화를 위한 ILP formulation을 제안하였다. 이 방법은 작은 크기의 문제에 대해서 최적해를 줄 수 있다. 이 방법의 대안으로 그래프 모델을 이용한 휴리스틱 알고리즘을 제안하였다. 이 방법은 빠른 시간 안에 거의 최적해에 가까운 결과를 준다. 마지막 방법으로 최소 의존 집합의 개념을 이용한 방법을 제안하였다. 이 방법은 최소 의존 집합을 구하는 것을 최소 칼럼 커버를 구하는 문제로 변환하여 해를 찾았다. 실험 결과로 부터 최소 부호화 방법은 병행성이 적은 마이크로 코드에, 최소 의존 집합을 이용한 방법은 하나의 마이크로 인스트럭션에서 동시에 나오는 마이크로 오퍼레이션의 숫자가 많을수록 효과적임을 알 수 있었다.
3장에서는 FSM의 스윗칭에 의한 파워 소비를 최소화할 수 있는 알고리즘이 제안되었다. 저 전력 소모는 패키지와 냉각을 위해 필요한 비용을 줄이기 위해서 뿐만 아니라 집적회로와 배터리의 수명을 연장하기 위해서 꼭 필요한 것이다. 제안된 알고리즘은 상태 천이가 많은 상태 사이에 해밍 거리 상에서 가까운 코드를 부여함으로써 스윗칭 파워를 최소화하였다. 먼저 각 상태 사이의 천이 확률을 구하고 구해진 확률로 그래프 모델을 만들었다. 이 그래프모델의 모서리의 가중치를 잘 반영하도록 그래프를 분할함으로써 상태 천이가 많은 상태 사이에 해밍 거리 상에서 가까운 코드를 부여하였다. 실험 결과로 부터 제안된 알고리즘은 면적을 최소화하기 위한 알고리즘 보다는 좀 더 많은 면적을 필요로 하지만 스윗칭 파워를 줄이는 데에 있어서는 효과적임을 알 수 있었다.
