クラスタ段数最小化を目的としたLUT型FPGAのパッキング手法

摘要

FPGA上に回路を実装する場合，回路をLUT(Look-Up Table)で被覆した後，各LUTをクラスタと呼ばれる論理ブロックへとまとめるパッキングという作業を行う．ここで，クラスタ間の配線遅延について考えた場合，回路の配置配線が行われた後でないと実際の遅延を厳密に求めることは難しい．そこで，パッキングの段階では各クラスタ間の配線遅延を一定とした遅延モデルが用いられる．この場合，回路の遅延はパッキング後のクラスタの段数によって決定される．本稿では，クラスタ段数の最小化を目的としたFPGAのパッキング手法を提案している．提案手法は，LUTの段数を最小化する既存のマッピングアルゴリズムを基にしており，“ラベル付け”と“パッキング”という二つの工程を経てクラスタ段数が最小となる回路を生成する．ベンチマークを用いた既存アルゴリズムとの比較実験では，平均でクラスタ段数が約30％削減されていることを確認した．