乱択アルゴリズムに基づく高速パス配線手法

摘要

本稿では，乱択アルゴリズムを用いたパス配線の高速手法を提案する．近年のLSIの製造技術の進歩により，配線はこれまでの最短経路から，より複雑な評価を考慮する必要がでてきた．その結果，今までの発見的手法では，能力として不十分となっている．この解決法の一つとして，高速にパスを列挙する手法が考えられる．そこで，本稿では，更なる高速化を実現するため，乱択アルゴリズムを利用し，平均計算時間の削減を目指した．その結果，約9.5倍もの高速化が実現できた．