安定なLSE法とその解析的配置への応用

摘要

近年のLSI配置では，要求性能が高度化している．特に配線長への要求はその傾向が顕著である．そこで，目的関数を直接最適化する解析的配置（Analytical Placement）が広く利用されるようになっている．このAnalytical Placementでは，目的関数は微分可能であることが求められる．そのため，微分不可能なmax関数の微分可能な近似関数としてLog-Sum-Exponential（LSE）が提案されている．このLSEには，収束性が高く得られる結果が比較的高性能という長所がある反面，数的安定性に欠けるという欠点が存在する．そこで，本稿では，LSEの最適化性能を保持しつつ，このLSEの欠点を解消するStable-LSE（SLSE）法を提案する．そして，Stable-LSE法を用いたAnalytical Placementとして，総配線長最小化と最大配線長最小化の2問題を定式化した．そして，総配線長最小化について計算機に実装し，その性能を確認した．%In the recent LSI design, the required performance for chip becomes high. Especially, the optimization of the wire length has such tendency significantly. Thus, the analytical placement which optimizes its objective function directly is widely used for the placement. To use the analytical placement, its objective function needs to be differentiable. To approximate the max function, Log-Sum-Exponential (LSE) function is proposed for the differentiability. While the LSE has high convergence and its result achieves high performance, it has the numerically instability problem. In this paper, we propose Stable-LSE which resolves the instability of LSE without loss of its efficiency. We formalize the total wire-length minimization and the maximum wire-length minimization with the Stable-LSE based analytical placement. We also implement the total wire-length minimization with Stable-LSE. We confirm the efficiency of Stable-LSE empirically.