クリティカルパスによる通信時間を考慮したタスクスケジューリング-様々なネットワークトポロジーへの適用-

飯島 伸一  諏訪 和徳  曽禰 元隆  

誌名
電子情報通信学会論文誌 D   Vol.J84-D1   No.12   pp.1623-1634
発行日: 2001/12/01
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 論文
専門分野: ソフトウェアシステム
キーワード: 
スケジューリング,  クリティカルパス,  通信時間,  トポロジー,  マルチプロセッサシステム,  

本文: PDF(1.6MB)
>>論文を購入


あらまし: 
マルチプロセッサシステムで並列処理するには,ユーザプログラム及びデータを分割し各プロセッサに分配する,いわゆるスケジューリングを必要とする.先行制約,使用プロセッサ数,マルチプロセッサの構成,通信時間等に制限されないという一般的条件下でのスケジューリングは,多項式時間の最適化アルゴリズムでは実現困難であり,ヒューリスティックアルゴリズムの適用が考えられる.本論文では,クリティカルパス(以下CP)法を基本として,完全,不完全結合にとらわれない様々なトポロジーのマルチプロセッサシステムに利用可能な,スケジューリング手法を提案する.提案法はタスクを割り当てる点は既存法と同様であるが,更に通信時間により修正,最適化を図ることを特徴とする.また,プロセッサの配置と中継の適正化も加味されている.提案法の効果を評価するため,既存法と同一のタスクグラフで比較した.また,大規模タスクグラフへの適用の効果を評価するために,実システム(32基DSPシステム)に実装し,電力系統解析プログラムに応用した.その結果,提案法は様々なトポロジーにおいて一様に有効であり,実用化に際しても十分な性能をもつことが実証された.