著者

多田 昭雄 中村 良三

出版者

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

雑誌

電子情報通信学会技術研究報告. SS, ソフトウェアサイエンス (ISSN:09135685)

巻号頁・発行日

vol.101, no.97, pp.25-32, 2001-05-21

---

並列タスクスケジューリングにおいて, タスク依存グラフよりタスクの実行順序を効率よく求める並列アルゴリズムを提案する. 具体的には, はじめに2つのタスク間の実行順序を示す有向辺を出節点と入節点の組で表したタスク依存グラフすなわちDAGを入出次数が高々1の節点からなる線形リストに分割する. 次に, 線形リストをリストの最終節点に至る流れの単位でグループに分割し, グループ内のリストの細を併合しながらタスクの実行順序を求め, 最後にタスク全体の実行順序を求める並列アルゴリズムである. すなわち, タスクの並列Topological Sortingを提案する.