Incremental placement takes an initial placement and modifies the placement to achieve de- sign closure. We address two key problems in incremental placement, timing- and routability- driven placements. First, an incremental timing-driven placement algorithm is presented. It optimizes timing critical paths through a blockage-aware path smoothing. The gates on criti- cal paths are relocated to free spaces around smoothed paths, so legalization is not necessary, while incremental static timing analysis is involved to accurately assess timing changes due to the relocation. Next, we propose an algorithm for timing-driven unified latch placement and cloning. Given a latch and the locations of the fanin and fanout gates, it relocates the latch based on a linear delay model such that the slack is maximized. The latch can be cloned into multiple latches to further improve the slack; each of the replicated latches drives a subset of the fanouts of the original latch. Finally, an incremental placement for pin-accessibility op- timization is presented. We propose two inaccessibility measures of pins which can identify the hard-to-access pins in a cell as well as in a placement. Its application to the placement optimization for improving accessibility of each cell is then presented.
본 학위논문에서는 타이밍과 배선 가능성 향상을 위한 3가지 점증적 배치기법을 제안하였다. 우선 크리티컬 패스 평탄화를 이용한 점증적 배치기법을 제시한다. 제안 방법은 패스를 평탄하게 함 으로써 배선 길이를 줄이고, 이를 통해 타이밍을 향상케 한다. 또한, 크리티컬 패스 상의 게이트를 평탄화된 경로 주변의 여유 공간으로 재배치하여 배치 합법화 과정이 필요하지 않다. 이어서 타이밍 향상을위한래치배치및복제알고리즘을제시한다. 래치와팬인및팬아웃게이트의위치를부여 하면 타이밍 슬랙이 최대화되도록 래치를 재배치한다. 이때 최적의 래치 위치는 선형 지연 모델을 이용하여 빠르게 계산하며, 하나의 래치를 여러 개의 래치로 복제하여 슬랙을 더욱 개선하는 것도 가능하다. 마지막으로 배선 가능성 향상을 위한 점진적 배치 기법을 제시한다. 셀에서 접근하기 어려운 핀을 식별하기 위한 두 개의 척도를 제안한 뒤 배치상에서 배선이 힘든 셀을 파악하는 데 사용한다. 각 셀의 핀 액세스 가능성을 향상하기 위한 배치 최적화 알고리즘 또한 제안한다.
