大規模ゲートアレーにおける配線混雑緩和を目的とした“padding”による配置改善の一手法

摘要

大規模ゲートアレー用の“padding”に基づく配置改善手法を提案する．この手法はセルサイズの仮想的拡大（padding）のフェーズ、セル間の重なりをとる再配置と、高速な反復改善のフェーズからなる．チップ上の局所的な配線混雑を緩和するために，既発表のアプローチであるpaddingにおいて、チップ全面を分割した各領域に対する配線混雑度に応じて、セルの拡大率を変動させる独自の手法を用いる．paddingの後，すべてのセルを重なりなく再配置する．我々は，再配置によってセルの相対的な位置関係が変わらないという想定のもとでセルの拡大サイズから再配置後の配線混雑を予測する式を立てた．この式を用いることにより，paddingフェーズはチップ上の配線混雑を均一化するようなセルの拡大サイズを決めることができる．提案手法による配置改善プログラムを大規模ゲートアレーの回路で実験したところ本手法により配置のroutabilityは大きく改善した．