In this thesis, a new strategy for combining placement and global routing for macrocell layout is studied and analytical strategies for detailed routing on channels and switch boxes are proposed for a complete layout. The first strategy solves a layout problem by interlocking placement and global routing in stepwise motion. This approach can avoid the shortcomings resulting from the conventional approaches which partition IC layout problems into smaller steps and then solve each step sequentially step by step in order to reduce the complexity of overall layout problem, while their solutions may be distant from the global optimum solution. The strategy uses an FDR (Force Directed Relaxation)[10][11] result as an initial placement because the result is a nearly global optimum solution without consideration of inter-module overlaps. The proposed strategy consists of module orientation, global routing, block size enlargement according to the global routing result and diffusion[28][29], which is defined as the process of relieving the inter-module overlaps by spreading the modules from overcrowded regions to less-crowdes regions. Experimental results run on several benchmark[30] examples and show the potential advantages of the proposed strategy over the conventional approaches.
For detailed routing for channels, an analytic procedure which is not only to two-layer but also to three-layer channel routing problems, is presented. The channel routing problem is formulated as a quadratic 0-1 integer programming where the quadratic function represents the amount of inter-net overlaps. The 0-1 variables in the formulation indicate the movement of each net segment generated by net partitioning. The proposed procedure analytically decides on the parallel moves of all the net segments from one track to the neighboring track, followed by a postprocessing heuristic procedure to improve the result. Experiments on the benchmark examples produced good results. The proposed procedure successfully applied to gridless channel routing and a routing problem on a rectilinear channel region.
Channel routing problem is solved by performing the analytic procedure for one-dimension, i.e., upward and downward. Detail routing problem for switch boxes can be solved by expanding the analytic procedure to two-dimensional version, i.e., by moving the net segments eastward, southward, westward, and northward. The two-dimensional analytic procedure can handle the detour of nets which is impossible to be handled in the one-dimensional procedure. And by ignoring the layer assignment constraint that one layer is assigned to the vertical wiring net segments, the routing procedure can be more efficient. Experiment on a switch box routing example obtained an optimal solution.
집적회로 레이아웃 설계 문제에서, 매크로 셀 레이아웃 문제는 그 셀들의 불규칙성으로 인하여 많은 어려움을 가지고 있고 아직도 설계상의 여러 단계에서 연구가 행해지고 있다. 이 레이아웃 문제는 전체적인 최적 해를 구해내는 것이 극히 어려우므로, 지금까지의 연구에서는 그 복잡성을 줄이기 위하여 전체 문제를 여러 단계로 세분화한 다음 각 단계내에서 최적해를 찾는 여러 연구가 행해졌었다. 하지만 이 방법은 각 단계 내의 국부적인 최적 해를 찾으므로 최종 해가 구해졌을 때 그 해가 전체적인 최적해에서 멀어질 가능성을 내포하고 있다.
본 논문에서는, 이러한 문제점을 해결하기 위하여 레이아웃 설계상의 중요한 두 단계인 배치와 거시적 배선을 상호 결합하여 처음에는 대략적인 배치와 배선을 수행하고 점점 세부적인 배치 및 배선을 수행해 나가는 방법으로써 배치와 거시적 배선을 동시에 수행함으로써 전체적인 최적 해에 보다 근접한 해를 찾아내는 기법을 제안하였다. 이를 위하여 배치 알고리즘은 거시적 배선의 결과를 충분히 고려하는 방법으로 그 배선 결과에 따라서 모듈 크기를 증가시켜서 배선 영역을 미리 준비하고, 배선 알고리즘의 특성은 대b}ダ岵? 배치 상태에서도 배선이 가능해야 하므로 모듈들간의 중첩에 상관없이 배선을 수행할 수 있는 특성들을 가지고 있다.
배치 및 거시적 배선이 끝나고 나면 세부적 배선을 수행함으로써 매크로 셀 레이아웃을 완성할 수 있다. 이를 위하여 채널 배선 및 스위치 박스 배선을 수행하는 해석적 기법이 연구되어졌다. 이 기법은 최초의 임의의 배선 상태로부터 점점 배선의 최적해로 접근시켜 가는 방법으로서, 채널 배선에서 나타나는 수평 제약조건, 즉 서로 다른 두 연결선이 같은 트랙에 중복된 상태로 놓여질 수 없다라는 조건과 수직 제약조건, 즉 수직 방향으로 발생하는 연결선의 중복을 피하기 위한 조건을 비용함수로 공식화한 다음, 여기에 패널티 함수를 더하여 최종적인 목적함수로 삼음으로써 채널배선 문제를 이차함수의 0-1 정수계획법 문제로 변환시킨다. 이렇게 모델링된 이차함수적 0-1 정수계획법 문제를 풀어서 최적해를 구하는데 이 과정을 연결선들의 중복이 없어질 때까지 반복함으로써 최종해를 구해낸다.
채널 배선 문제는 이 해석적 방법을 일차원적으로 적용시켰으나 이를 이차원적 즉 연결선들의 이동을 동서남북 방향으로 적용시킴으로써 채널배선 뿐 아니라 스위치 박스 배선도 가능하게 되었다. 채널배선 문제에서는 배선 층이 수평 및 수직에 대해 고정되어 있었지만, 여기에서는 그러한 제약을 제거함으로써 보다 나은 배선 결과를 얻을 수 있었다.
