超大規模計算の高速算法自動合成の理論

点击翻译按钮获取中文摘要

本年度は,前年度に引き続き超大規模計算アルゴリズムの実装技術としての動的かつ部分的再構成可能システムに着目し,高速に計算処理を実行するための計算スケジューリング手法について検討を行った.動的再構成とは,アプリケーション実行時にVLSI上で(部分的に)論理的機能を変更する機能であり,汎用CPU上でのソフトウエア実装に匹敵する実装対象の規模と多様性に関する柔軟性と,特定のアプリケーション専用に設計されたVLSI計算システム(ASIC)に匹敵する計算速度を実現する能力を持つものである.こうしたシステム上でのアルゴリズムの実装には,各部分計算ブロックの時間軸上での再構成時刻・計算開始時刻と二次元平面内での再構成場所の決定,すなわち3次元的スケジューリングが必要となる.本年度は,昨年度開発されたルーブを持たない実装対象アルゴリズム(DAG)に対する3次元スケジュール解表現の繰り返し実行アルゴリズム(本体アルゴリズムが繰り返し実行される)に対する3次元スケジューリング表現への拡張を行った.スケジュール長の最小化が最適化の目的となるDAGスケジューリングと異なり,繰り返し実行アルゴリズムのスケジューリングでは,サンプリング周期,スループットを決める繰り返し周期の最小化が目的となる.このため,連続して実行される本体計算の間での実行時刻の重なり(ループパイプライン化)の積極的な導入が不可欠である.スケジュール解のコード表現とそのデコード手法では,任意にループパイプライン化されたスケジュール解を表現するための拡張型constrained sequence quintupleを提案した.一方最適解の探索にあたっては有効な解(実現可能解)のみを生成する必要があり,こうした実行可能解のためのコード条件を明確にした.以上の拡張,考察に基づき,実行可能コード空間を確率的手法にて探索するスケジュール最適化手法を提案・システム開発を行い,合成実験により,提案するスケジュール手法が動的再構成システムが持つ本質的能力を十分に引き出したアルゴリズム実装を実現できることを確認している.