Designers of CMOS VLSI circuits can take advantage of logic modules to achieve better performance and better turn-around time. For synthesizing the logic modules automatically, two problems are to be solved; one is the problem of minimizing the widths of logic modules, and the other is the problem of determining the heights of logic modules, that is, minimizing the sum of all row heights in standard cell layouts satisfying the delay time and minimum dimension constraints, both of which are known as NP-complete. In this thesis, three algorithms are devised for solving these two problems.
Our first algorithm solves the former problem, where the problem is converted to that of decomposing the transistor connection graph into a minimum number of subgraphs, each having a pair of Euler trails with the same sequence of input labels on the N-graph and P-graph, which are portions of the graph corresponding to NMOS and PMOS parts, respectively, and some heuristics are used to yield a nearly minimum number of Euler trails from the trail representation formula which represents the given logic function. Subtrail merging is done through a list processing scheme where the pair of trails which results in the lowest cost is successively merged from all candidate merge pairs until no further trail merging and further reduction of number of subgraphs are possible. A salient feature of our proposed algorithm is that virtually all permutations of the subtrails are considered within the time complexity of $O(n^3)$, which has to be contrasted with the time complexity of $O(n^n)$ in [2] and [3] considering all permutations within each subtrail.
Our second algorithm also solves the former problem, where the problem is converted to that of determining the covering sets for each of the given Boolean logic expression and merging all the covering sets in all possible ways to find the optimum solution being characterized by the minimum number of dual trails, corresponding to the minimum number of diffusion islands. The concepts of 18 canonical symbols (CS's), 18 canonical environments (CE's), merging cost between each CS and each CE, dominant canonical symbol sets (DCSS's), and complete set of merging sequences are introduced and utilized for finding the optimal layout of CMOS complex module. The second algorithm helps reduce the computing time by avoiding the unnecessary search and always finds the optimal results.
In standard cell layouts, it is frequently assumed that the height of each cell in the same row is identical, while the height of each cell-row can be different from those of other cell-rows. The third algorithm solves the latter problem of determining the height og each cell-row in the standard cell layout, that is, minimizing the total sum of the heights of all cell-rows while satisfying the constraints of delay times of given primary input-primary output pairs and minimum dimension of transistor gate widths, assuming the position of each cell were given by a standard cell placement procedure.
The third algorithm always finds the optimum results systematically. The delay model used here is based on the current drive capability of a transistor network. The objective cost is reduced in a discrete manner, that is reduced by unit-step size during each iteration. Each iteration consists of two basic operations; one operation relaxes the constraint margins, and the other operation reduces the transistor gate width by a unit-step size if it causes no constraint violation. The algorithm terminates when no reduction of the objective cost is possible due to the violation of one or more imposed constraints.
CMOS VLSI 회로를 설계할 때는 향상된 기능과 신속한 설계 진행을 위해 논리 모듈을 사용하는데 이러한 논리 모듈을 자동으로 합성하는 데 있어서 다음 두 가지 문제를 해결 하여야 한다.
첫 번째 문제는 입력된 논리식들에 대하여 생성될 각각의 논리 모듈의 폭을 최소화하는 것인데 이를 주어진 논리식을 커버하는 최소 수의 트레일을 찾는 문제와 일치한다. 두 번째 문제는 이와같이 생성된 논리 모듈들을 배치 및 배선과정을 거친 후 전체 회로의 시간적 제약 및 최소 크기적 제약을 만족하면서 전체 회로 레이아웃의 높이, 즉 각 열의 높이 (각 열에 속해 있는 모든 NMOS 혹은 PMOS 트랜지스터들의 폭은 상호같다고 제안했기 때문에 각 열의 높이는 NMOS 트랜지스터의 폭과 PMOS트랜지스터의 폭의 합으로 나타낸다.) 합을 최소화하는 것이다. 상기한 두 가지 문제들의 연산 복잡도는 NP-complete 으로 알려져 있다.
첫 번째 문제를 다룬 기존의 논문들을 살펴보면, 대부분이 주어진 논리식에 대해 그 논리식이 가지는 논리가 변경되지 않는 한도 내에서 취할 수 있는 입력의 모든 순열에 대해 고려하지 않고 있다. 그래서 그들은 알고리즘의 입력으로서 논리식을 취하지 않고 논리회로를 취하였다. 본 논문에서는 입력의 순열을 고려하면서 첫 번째 문제를 해결할 수 있는 두 가지 알고리즘을 제시한다.
첫 번째 알고리즘은 그래프 이론에 입각한 경험적 비용을 산출한 후 이를 이용하여 효과적으로 최적 결과를 얻게하고 두 번째 알고리즘은 최적 결과를 도출할 가능성이 있는 최소수의 모든 경우를 고려함으로써 보증된 최적 결과를 체계적으로 얻게 한다.
두 번째 문제를 다룬 기존의 논문들을 살펴보면 불연속적인 방식을 취하는 알고리즘들 중에서 도출된 결과가 최적이라고 보증하는 것들은 없었다. 본 논문에서는 도출된 문제가 최적임을 보증하면서 두 번째 문제를 체계적으로 해결할 수 있는 한 알고리즘을 제시한다.
먼저 첫 번째 문제를 해결하는 경험적 알고리즘에 대해 설명하여 보면 다음과 같다. 입력된 논리식은 순열 가능한 최소 단위의 트레일로 바뀐다. 각 트레일은 다른 트레일과 서로 연결하는데 사용되는 두 개의 트레일 핸드를 가지고 있는데 존재 가능한 모든 트레일 핸드는 10개의 유형으로 분류된다. 한 쌍의 트레일 핸드들을 결합하여 다른 한 트레일을 생성시키는 것에 관한 모든 정보를 결합표로 만들어 두었고 실제로 그들의 결합이 일어날 지의 여부를 결합가능판단표로 만들어 두었다. 모든 결합 가능한 트레일 핸드쌍에 대해 경험적 비용을 산출하고 이에 의거하여 순서적으로 결합을 실시한다. 우리의 경험적 알고리즘으로 얻은 결과를 타 대표적 알고리즘들에 의해 얻은 결과들과 비교하여 본 바 우리의 경험적 알고리즘이 우수함을 알 수 있었다.
다음에 첫 번째 문제를 해결하는 이론적 알고리즘에 대해 설명하여 보면 다음과 같다. 한 논리식이 주어지면 입력의 순열을 허가하는 경우, 많은 수의 회로 구조가 결정될 수 있고 각 회로 구조에 대응하는 그래프 모델에 대해 많은 수의 카버링 세트를 생각할 수 있다. (그래프 모델에서 하나의 듀얼 에지는 두 가지 형태로 트레이스 할 수 있으므로 하나의 그래프 모델에 대해 많은 경우의 수로 트레이스 할 수 있는데 각 경우의 트레이스를 카버링 세트라고 한다.) 모든 종류의 카버링 세트는 결합 관점에 의거하여 비추어 보면 18개의 대표 심볼들로써 표현될 수 있다. 비슷한 방식으로 논리를 비약해 보면 임의의 한 대표 심볼이 가질 수 있는 모든 주위 환경도 18개의 대표 환경들로서 표현될 수 있다. 하나의 논리식에 대한 모든 대표 심볼들 중에서 18개의 대표 환경들에 대해 열등한 것들을 제외한 나머지 대표 심볼들의 집합을 지배적 대표 심볼 집합이라고 정의한다. 입력으로서 한 논리식이 주어지면 이는 논리 나무 구조로 표현되게 되는데 각 말단 노드들은 최소 단위의 부논리에 대한 지배적 대표 심볼 집합들로써 표현된다. 깊이-우선 노드 결합 방식에 의거하여 체계적으로 결과를 얻게 되며 이 결과는 최적임을 보증할 수 있다.
마지막으로 두 번째 문제를 해결하는 알고리즘에 대해 설명하여 보면 다음과 같다. 두번째 문제를 정형화하여 보면 비용 함수는 선형 함수로, 시간제약 함수는 컨벡스 함수로, 최소크기제약 함수는 선형 함수로 표현되는데 이와같은 경우에는 국부적 최소점이 존재하지 않는다. 이 최적화 문제에서 고려해야 하는 모든 변수들(즉 트랜지스터의 폭들)을 원소로 하는 벡터를 폭 벡터라 하고 각 원소들은 단위 스텝 크기 만큼 씩만 변화된다고 한다. 모든 제약 조건을 만족시키는 하나의 현재 폭 벡터가 주어졌을 때 다음에 설명하는 바를 반복하여 수행 함으로써 비용 함수를 감소시킨다. 주어진 현재 폭 벡터에 대해 산출된 비용과 동일한 비용을 갖는 폭 벡터중 모든 제약 조건을 만족시키는 폭 벡터들만을 주어진 현재 폭 벡터에 가까운 순서대로 고려한다. 고려 중에 있는 폭 벡터의 임의의 한 원소만을 단위 스텝 크기만큼 감소했을 때 그 폭 벡터가 모든 제약 조건을 만족시키면 다음 반복 시의 현재 폭 벡터가 되고 이러한 폭 벡터가 발견되지 않으면 반복 수행을 중단한다. 이와같은 방식으로 구한 최종해로서의 폭 벡터는 최적임을 보증할 수 있다.
