SAに基づくFPGA配置アルゴリズムの領域分割による並列化

摘要

配置処理はFPGA自動設計フローの中で最も時間を費やす工程の一つである．近年では，FPGAの性能向上によって実装回路の大規模化が進み，自動設計に要する時間が急激に増加しているため，FPGA配置の高速化は重要な課題となっている．本稿では，最も広く用いられているSAに基づくFPGA配置を対象として，クラスタコンピュータ上で領域分割による並列化を適用する．本来，SAは逐次性の強いアルゴリズムであり，並列化には適していない．しかし，FPGAは一般に規則的構造を持つため，物理的領域に従って問題を分割することが可能である．評価の結果，領域分割による並列化が大規模回路の配置に適しており，大規模回路において線形に近い速度向上を数％のコスト劣化で達成可能であることが分かった．