Methods of Tuning Threshold Voltages for Power Recovery and Refining Placement Legalization for Wire Recovery = 전력 및 배선 회복을 위한 임계전압 조정 기법과 배치 최적화 기법

다국어 초록 (Multilingual Abstract)

As CMOS technology scales into advanced nodes, modern low-power, high-performance system-on-chip (SoC) designs increasingly rely on both multi-threshold voltage technology and mixed-cell-height standard cell libraries. In such designs, small perturbations in device threshold voltages (VT) can cause large fluctuations in leakage power, while the increased complexity of legalization for mixed cell heights can cause large deviations from the timing- and routability-driven global placement solution. In this context, this dissertation studies two related optimization problems that arise at different stages of the design implementation flow: (i) recovering leakage power by tuning VT values in timing-closed multi-threshold voltage designs at the post-route stage, and (ii) recovering wirelength and placement quality by refining legalization for mixed-cell-height layouts during the placement stage of the physical design flow.
For the first problem, given a timing-closed design typically at the post-route stage whose leakage power has already been optimized for nominal VT values, we reinterpret VT tuning as a design-side upper-bound and guidance problem. Specifically, we (i) quickly estimate the maximum leakage power reduction achievable by applying small threshold-voltage shifts to each VT type (e.g., RVT/LVT/SLVT for nMOS/pMOS) without violating timing constraints, and (ii) use the resulting continuous optimum to guide practical choices from a discrete pool of VT options provided by the process/library. To this end, we develop a near-optimal approximation framework based on a piecewise-linear programming formulation that embeds delay and leakage sensitivities into linear constraints and objective. By replacing repeated full-chip static timing analysis (STA) over sampled VT configurations with a single linear-programming (LP) solve over piecewise-linear delay and power models, the proposed method avoids slow STA loops while providing fast upper-bound estimation and actionable guidance; it achieves five orders of magnitude speedup over conventional VT tuning flows, while obtaining, on average, 5.45% additional leakage power reduction under the given timing budgets.
For the second problem, we propose a window-based legalization refinement framework tailored for mixed-cell-height designs. Starting from a legal placement delivered by a commercial tool or an MGL-style legalizer, our method iteratively scans windows, generates slots by aggregating candidate cells and adjacent whitespace, and solves a min-cost perfect matching problem between candidate cells and slots. This formulation enables cooperative multi-cell rearrangements and explicitly supports substitution among functionally equivalent cells with different heights, reflecting modern library trends. We further introduce displacement-like priority metrics to guide candidate selection and exploit independent window sets for multiprocessing on multi-core platforms. Experiments on OpenCores benchmark circuits implemented using the ASAP7 7.5-track standard cell library show that, over commercial legalizations, the proposed refinement reduces average displacement, maximum displacement, and half-perimeter wirelength (HPWL) by an average of 25.7%, 52.5%, and 6.6%, respectively, leading to a 38.7% improvement in a composite score inspired by the ICCAD-2017 multi-deck legalization contest, with up to 66.47% score improvement on extremely dense designs.
Taken together, these two contributions provide a unified methodology for improving both power and interconnect quality in advanced-node designs. VT tuning globally reshapes the leakage–delay trade-off at the device and cell level in timing-closed post-route designs, while mixed-height legalization refinement locally rearranges cells and whitespace during placement to recover wirelength and placement metrics and better preserve the intent of the timing-driven global placement.

국문 초록 (Abstract)

전력 및 성능 요구가 점점 더 엄격해지는 첨단 공정에서, 최신 저전력 · 고성능 시스템온칩(SoC) 설계는 다중 임계전압 기술과 혼합 셀 높이(mixed-cell-height) 표준셀 라이브러리에 점점 더 의존하고 있다. 이러한 설계에서는 소자의 임계전압(VT)이 미세하게 변화하더라도 누설 전력이 크게 요동칠 수 있으며, 복수 높이 셀을 포함하는 배치 합법화(legalization) 과정이 복잡해지면서, 배선 및 타이밍 품질을 고려해 정밀하게 최적화된 글로벌 배치 해로부터 심각하게 벗어나는 문제가 발생한다. 본 학위논문은 이러한 배경에서, 설계 구현(implementation) 흐름의 서로 다른 단계에서 등장하는 두 가지 밀접하게 연관된 최적화 문제, 즉 (i) 포스트-라우팅 단계의 타이밍-클로즈드 다중 임계전압 설계에서 VT 조정을 통한 누설 전력 회복, (ii) 물리 설계의 배치 단계에서 혼합 셀 높이 배치의 legalization 정제를 통한 배선 및 배치 품질 회복 문제를 다룬다.
첫 번째 문제와 관련하여, 본 논문은 포스트-라우팅 단계의 타이밍-클로즈드 회로를 대상으로, 이미 공정상 명목 VT 값에 대해 누설 전력이 최적화된 설계에서 각 VT 타입의 VT 값을 연속적인 공간에서 재탐색함으로써, 타이밍 제약을 위반하지 않는 범위 내에서 전체 누설 전력을 추가로 감소시키는 기법을 제안한다. 또한 본 기법의 연속해는 공정의 VT 포인트 변경을 요구하기 위한 결과가 아니라, 주어진 라이브러리/허용 변동 범위 내에서 달성 가능한 누설 전력 감소의 상한(upper bound)을 빠르게 추정하고, 실제 PDK가 제공하는 이산(discrete) VT 옵션 풀에서 평가할 만한 후보를 좁히는 가이드로 활용된다. 즉, 반복적인 STA 루프 없이 전체 VT 공간을 효율적으로 평가하고, 소수 후보만을 sign-off STA로 검증하는 실무 친화적 분석 프레임워크를 제공한다. 이를 위해 지연 및 누설 전력 민감도를 선형 제약식과 목적함수에 내재화한 분할 선형화(piecewise-linear) 기반 선형계획법(LP) 근사 프레임워크를 개발하였다. 제안 기법은 이산 VT 샘플에 대해 반복적으로 정적 타이밍 분석(STA)을 수행하는 전통적인 VT 튜닝 흐름을, 분할 선형 지연 · 전력 모델에 대한 단일 LP 풀이로 대체함으로써, 기존 기법 대비 약 5자릿수의 속도 향상을 달성하면서도 동일한 타이밍 예산 하에서 평균 5.45%의 추가 누설 전력 감소를 달성한다.
두 번째 문제와 관련하여, 본 논문은 혼합 셀 높이 설계를 대상으로 한 윈도우 기반 배치 합법화 정제(window-based legalization refinement) 프레임워크를 제안한다. 상용 도구 또는 MGL 방식 legalizer가 생성한 초기 legal 배치를 입력으로 받아, 윈도우들을 반복적으로 스캔하면서 후보 셀과 인접한 공백 공간(whitespace)을 집약하여 슬롯(slot)을 생성하고, 후보 셀과 슬롯 사이의 최소 비용 완전 매칭(min-cost perfect matching) 문제를 해결함으로써 배치를 정제한다. 이와 같은 슬롯 기반 정식화는 복수의 셀이 공백 공간을 공유하며 협조적으로 이동하는 다중 셀 재배치를 가능하게 할 뿐 아니라, 동일한 논리 기능을 가지면서 높이가 서로 다른 셀 간 치환을 명시적으로 허용함으로써 최신 셀 라이브러리의 특성을 효과적으로 반영한다. 또한, 윈도우 내에서 우선적으로 다룰 셀을 선택하기 위해 효과적 변위(effective displacement)와 변위 감소 가능 영역 비율(displacement reduction region ratio)과 같은 변위 유사(priority) 지표를 도입하고, 서로 겹치지 않는 윈도우 집합을 구성하여 멀티코어 환경에서 병렬 처리를 수행한다. ASAP7 7.5-track 표준셀 라이브러리를 이용하여 구현한 OpenCores 벤치마크 회로에 대한 실험 결과, 상용 도구의 초기 legal 배치에 대해 제안 기법은 평균 변위, 최대 변위, 반 둘레 배선 길이(HPWL)를 각각 평균 25.7%, 52.5%, 6.6% 감소시키며, ICCAD-2017 multi-deck legalization 콘테스트의 평가 지표를 변형한 복합 점수 S∗를 평균 38.7% 개선하고, 90% 이상의 고밀도 설계에서는 최대 66.47%까지 점수 향상을 달성함을 보였다.
요약하면, 본 학위논문에서 제안하는 두 가지 기법은 첨단 공정 설계에서 전력과 배선 품질을 동시에 향상시키기 위한 통합적인 물리 설계 최적화 방법론을 제공한다. VT 조정 기법은 타이밍이 닫힌 포스트-라우팅 회로에서 소자 및 셀 수준의 누설 전력–지연 트레이드오프를 전역적으로 재구성하고, 혼합 셀 높이 배치 정제 기법은 배치 단계에서 셀과 공백 공간을 국소적으로 재배치함으로써 배선 길이와 배치 품질을 개선하여 타이밍 구동 글로벌 배치의 의도를 더 잘 보존한다.

목차 (Table of Contents)

• Abstract i
• Contents iii
• List of Tables v
• List of Figures vii
• 1 Introduction 1
• 1.1 Threshold Voltage Tuning Technique for Leakage Power Recovery 1
• 1.2 Placement Legalization Refinement to Mixed-cell-height Standard Cells 4
• 1.3 Contributions of This Dissertation 8
• 2 Threshold Voltage Tuning Technique for Leakage Power Recovery 11
• 2.1 Motivation and Optimization Flow 11
• 2.1.1 Motivation 11
• 2.1.2 Proposed VT Optimization Flow 13
• 2.2 Step 1: Building piecewise-linear power and delay functions 15
• 2.2.1 Delay Function 16
• 2.2.2 Leakage Power Function 18
• 2.3 Step 2: Formulating VT tuning with timing constraints into LP 19
• 2.3.1 Timing Constraints 19
• 2.3.2 Leakage Power Objective 23
• 2.4 Guiding Discrete VT-Pool Selection Using the Continuous LP Optimum 23
• 2.5 Experimental Results 24
• 2.5.1 Selection of Critical Paths for Timing Constraints 24
• 2.5.2 Power Recovery under Timing Constraints 27
• 2.5.3 Effectiveness of Our Approach 27
• 3 Placement Legalization Refinement to Mixed-cell-height Standard Cells 32
• 3.1 Problem Formulation 32
• 3.1.1 Preliminaries 32
• 3.1.2 Terminology 36
• 3.2 Algorithm and Implementation Details 38
• 3.2.1 Overall Framework 38
• 3.2.2 Slot Generation 41
• 3.2.3 Slot Insertion Evaluation 44
• 3.2.4 Multiprocessing Implementation 45
• 3.3 Experimental Results 45
• 3.3.1 Experimental Setup 45
• 3.3.2 Comparison with Prior Works 47
• 3.3.3 Impact of Design Characteristics 50
• 3.3.4 Parameter Tuning 52
• 3.3.5 Parallel Scalability 57
• 3.3.6 Candidate Selection Strategies and Future Work 57
• 4 Conclusions 61
• 4.1 Chapter 2 61
• 4.2 Chapter 3 62
• Abstract (In Korean) 68