集合対間配線における総配線長および配線長差の削減手法

摘要

プリント基板上の配線問題のひとつである集合対間配線問題では，接続要求は端子集合に与えられる．プリント基板の設計では，回路の高速化を図るために配線遅延を細かく制御することが要求され，配線間の配線長差の削減が求められることが多い．平面上の集合対間配線問題に対して，配線間の配線長差を削減するための手法として，総配線長最小配線を総配線長を増大させることなく接続端子対を変更することで，逐次的に配線を修正する手法が提案されているが，必ずしも十分な配線長差の削減は達成できていない．本研究では，総配線長を大きく増大させることなく，既存手法に比べ配線長差がより削減された配線を得るための手法を提案する．提案手法は，既存手法を用い総配線長最小の条件で配線長差を削減したのち，R-Flipを用いて配線長が短い配線を冗長化することで配線長差を効果的に削減する．また，実験により提案手法の有効性を示す．