動的リコンフィギャラブルプロセッサへの時間制約付き機能モジュール群分割アルゴリズムの検討

摘要

本稿では,マルチコンテキスト型動的再構成可能プロセッサへ時間制約を持つ実時間システムの機能モジュール群を分割し割り当てるためのアルゴリズムについて述べる.対象とするシステムを,時間制約を持つタスクグラフで表現し,それぞれのタスクをコンテキストに割り当てることでシステムの分割を実現する.本間題をコンテキストの最大サイズを最小化する整数線形計画問題(ILP)として定式化を行った.その際,解の品質を落とすことなくILP問題にするための様々な制約を考案した.また,大規模なタスク割当問題に対処できるよう,二段階のヒューリスティックアルゴリズムを考案し,いくつかの例題に適応した結果,最適解の1.1から1.3倍程度のサイズの分割結果を比較的短時間で導出できることが分かった.