集合対間配線における配線長差削減を考慮した端子対間配線手法

摘要

接続要求が端子集合間に与えられる集合対間配線問題において，本稿では，総配線長および配線長差の削減を目的とする配線手法を提案する．提案手法では，まず，最大配線長および配線長差が小さい初期配線を生成するために，目標端子対選択に混雑予想を評価尺度として取り入れ，混雑度の小さい領域で接続可能な端子対が目標として選択されやすくすることで，より多くの目標端子対が初期配線で接続されることを目指す．また，短い配線の冗長化による配線長差削減を効果的に行うために，短い配線の周囲を避けるよう他の配線の経路を修正する．実験では，既存手法と比較して，最大配線長が等しく配線長差が短い配線パターンが得られることを示す．