Airgap is an intentional void formed in inter-metal dielectric (IMD). It brings about reduced coupling capacitance, and so can be used to improve circuit timing. Airgap can be utilized in a limited number of metal layers due to its high process cost. For given airgap layers, two problems should be addressed to insert airgap: relocate some metal segments in non-airgap layers into airgap layers (called layer reassignment) and determine the amount of airgap for each metal segment in airgap layers (airgap insertion). Two problems are solved together in this dissertation with a goal of maximizing setup total negative slack (TNS) while assuring no hold violations. It is formulated as mixed integer quadratically constrained programming (MIQCP); heuristic algorithm is proposed for practical application and its performance against MIQCP is experimentally assessed using small test circuits. Experiments demonstrate that TNS and WNS are improved by 41% and 10%, respectively, while simple minded approach achieves 13% and 5% less improvements compared to the proposed method.
에어갭은 메탈 간 유전체 안에 형성된 의도된 빈 공간이다. 이는 커플링 캐패시턴스의 감소를 가져오고, 그러므로 회로의 타이밍을 향상시킬 수 있다. 에어갭은 그것의 높은 공정 비용 때문에, 한정된 메탈 레이어들에 적용시킬 수 있다. 에어갭 레이어가 주어져 있을 때, 에어갭을 삽입하기 위해 두 가지 문제를 풀어야 한다: 에어갭 레이어가 아닌 레이어에 있는 몇몇의 메탈 세그먼트들을 에어갭 레이어로 재배치하는 것 (레이어 재할당) 과 에어갭 레이어에 있는 각 메탈 세그먼트에 대해 에어갭의 양을 정하는 것 (에어갭 삽입) 이다. 이 학위 논문에서는 홀드 위반들을 일으키지 않으면서 셋업 총 음수 슬랙을 최대화하기 위한 목표에 대해 두 문제를 함께 풀어볼 것이다. 이 문제는 제약조건에 2차 항을 갖는 혼합 정수 계획법으로 공식화된다; 실제적인 적용을 위해 휴리스틱 알고리즘을 제안하고, 제약조건에 2차 항을 갖는 혼합 정수 계획법 대비 이것의 성능은 작은 테스트 회로들을 통해 실험적으로 평가한다. 실험 결과는 총 음수 슬랙과 최악 음수 슬랙이 각각 41%와 10% 향상되는 것을 증명하고, 반면 간단한 접근법은 이에 대해 제안된 방법과 비교하여 각각 13%와 5% 적은 향상을 이룬다.
