リニアアレーを使った大規模LD分解に対するマルチプロセッサスケジューリング法

飯国 洋二  酒井 英昭  得丸 英勝  

誌名
電子情報通信学会論文誌 A   Vol.J72-A    No.4    pp.685-691
発行日: 1989/04/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5707
論文種別: 論文
専門分野: アルゴリズムとデータ構造,計算複雑度
キーワード: 


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



あらまし: 
マルチプロセッサシステムの性能の向上を計るためには,タスクのプロセッサへの割り当て,およびその実行順序を決めるマルチプロセッサスケジューリング問題が重要になってくる.本論文では,リニアアレーを使った大規模LD分解において,各プロセッサにおける処理の規則性,リニアアレーにおける通信の局所性を利用することによって,プロセッサへのプロセスの最適な割り当てを行う方法を示す.まず,スループットと処理時間を評価規範として,スケジューリングの評価式を導出する.但し,評価式はプロセッサ間通信の同期法にも依存するので,同期式,非同期式について別々に考察をする.次に,導出した評価式に対してMulti-Fit Decreasing法あるいはLevenberg Marquardt Morrison法を適用することにより,簡単にスケジューリングが行えることを示す.