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

摘要

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