不完全結合マルチプロセッサシステムに対するタスク割当て法の提案と評価

小林 真也  

誌名
電子情報通信学会論文誌 D   Vol.J79-D1   No.2   pp.69-78
発行日: 1996/02/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 論文
専門分野: ソフトウェア基礎
キーワード: 
マルチプロセッサシステム,  並列処理,  タスク割当て,  通信オーバヘッド,  

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


あらまし: 
マルチプロセッサシステムでは,処理速度を最も速くするためにどのように各プロセッサにタスクを割り当てていくか,つまりタスクスケジューリングが重要な問題である.実際のマルチプロセッサシステムのタスクスケジューリングではプロセッサ間の通信にも時間がかかり,個々のタスクの処理時間のみならず,通信時間も考慮しなければならない.本論文ではこの問題に対する最適解への近似精度の高い一方式を提案する.提案方式は,リストスケジューリングの一種であり,各タスクの処理時間のみによって決定されるプレプライオリティと,タスクとプロセッサごとに求められる通信削減時間によりタスクプライオリティリストを決定する.各タスクのプレプライオリティの値はそのタスクに依存する複数のタスク依存系列のうちの最長パスの長さである.また,通信削減時間とは,他のプロセッサで実行した場合に必要であるがプライオリティを求めようとするプロセッサで実行する場合には必要のない通信の時間である.常微分方程式の数値解法の一つであるRunge-Kutta法と,FFTの二つのプログラムを対象に,完全網システムにおいて従来方式との比較を行い提案方式の優位性を示す.また,不完全網システムに対しても提案方式が良好な割当てを行えることを示す.更に,乱数を用いて生成したタスク集合に対しても,提案方式が優れていることを示す.また,割当てに要する時間を実測し,提案方式が問題の規模に対して多項式時間で解けることを示す.