2入力AND-nodeをもつSWITCH-lessプログラムネットの最適2－プロセッサスケジューリングに関する考察

摘要

マルチプロセッサのスケジューリング問題は，タスクグラフに対して実行時間を最小にするためにタスクをプロセッサに割り当てる順序を決めることである．限られた資源の中，マルチプロセッサで最適に計算していくためには，そのスケジューリングが重要となる．マルチプロセッサシステムの1つであるデータフローマシンは，プログラムのデータの流れを重視したものであり，そのプログラムをグラフで表現したものをプログラムネットという．プログラムネットには3種類のノード，AND-node，OR-node，SWITCH-nodeがあり，それぞれ，算術／論理演算，データの併合，条件分岐を表している．本論文では，2入力AND-nodeをもつacyclic SWITCH-lessプログラムネットにおける2－プロセッサスケジューリング問題について検討する．まずは，新しい優先リストを提案し，そのリストに関するいくつかの性質について述べる．さらに，具体的な例を用いて従来のリストとの比較を行い，提案したリストの有効性を示す．