著者

小林 真也

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-コンピュータ (ISSN:09151915)

巻号頁・発行日

vol.79, no.2, pp.69-78, 1996-02-25

参考文献数

12

被引用文献数

9

---

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