解析的配置におけるセルの重なりを考慮した半周近似配線長最小化のための劣勾配法の適用

摘要

継続する微細加工技術の進展により集積回路の設計規模は増大しEDAにおける配置は依然重要な技術である。配置手法の中でも解析的配置がもっとも期待され研究されて来た。これまでに提案されてきた解析的配置は大きく分けてネットをクリークとみなしバネモデルに基づき2次関数を目的関数とする手法と半周近似配線長（HPWL）を微分可能なlog-sum-exp関数で近似して最適化する手法の2つである。これらの手法の目的関数は微分可能なため解析的に効率的に最適化できるという利点もある。一方，配置結果の評価は通常，微分可能ではない半周近似配線長で行われてきた。すでに劣勾配法を使って微分可能でないHPWLをそのまま最小化することを試みた。本論文ではこれをもとに配置処理で必須であるセルのオーバーラップを削減する手順をラグランジュ緩和を用いて劣勾配法の枠内で行う手法を提案する。小規模なテストデータに適用した結果も示す。