CAFE router：障害物を含む領域における連結度を考慮した複線配線手法

摘要

近年の回路動作の高速化に伴い，複数の信号線のそれぞれに対して要求される遅延量を高い精度で実現することが必要となっている．プリント基板の配線設計では，要求された遅延値に満たない信号は配線を迂回させて配線遅延量を増大させることで遅延値を調整するのが一般的である．本稿では一層配線を想定し，障害物領域を含む領域に目標の配線長がそれぞれ指定された複数の接続要求が与えられたとき，全ての信号線が交差なく，目標の配線長との誤差をできるだけ小さい配線経路を得る問題に対して，未配線領域での接続要求の連結度を考慮することで配線実現性を保障しつつ，配線を一点ずつ逐次的に延長する手法CAFE routerを提案する．計算機実験では，提案したCAFE routerは高速に比較的目標の配線長との誤差が小さい配線が得られた．