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

摘要

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