ハイパキューブにおける通信路競合を考慮したスケジューリング法

紺谷　精一  佐藤　哲司  

誌名
電子情報通信学会論文誌 D   Vol.J76-D1   No.7   pp.347-353
発行日: 1993/07/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 論文
専門分野: 計算機システム
キーワード: 
スケジューリング,  通信コスト,  通信路競合,  ハイパキューブ,  

本文: PDF(446.8KB)>>
論文を購入



あらまし: 
通信路で結合されたマルチプロセッサのスケジューリングでは，プロセッサ間の通信コストや通信路競合の影響のためタスクの実行が遅らされる場合がある. 本論文では，通信コストおよび通信路競合を考慮したハイパキューブを対象とするタスクスケジューリング法を提案する．提案法は，タスクに通信コストを含めた優先度を与え，優先度順に通信路競合を考慮してプロセッサにタスクを配置する．プロセッサへの配置前に計算できる最遅開始時刻をタスクの優先度とし，すべての先行タスクの割当てが終了したタスクを割当て可能タスクとすることで，実行タイミングのトレースを不要とし高速化を図っている．本提案法をランダムに生成したタスクグラフに適用した結果，タスク数が1,024の場合でもプロセッサ数が2から32の範囲でほぼ直線的なスケーラビリティが得られ，完了時間の下限の2倍以内で実行できることを確認した．