著者

多田 昭雄 中村 良三

出版者

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

雑誌

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

巻号頁・発行日

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

---

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

著者

右田 雅裕 多田 昭雄 中村 良三

出版者

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

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.103, no.538, pp.9-16, 2003-12-15

---

本橋では,CREW-PRAM並列計算機モデルのもとで,DAG (Directed Acyclic Graph)の最長路を求める効率よい並列アルゴリズムを提案する.また,従来の推移的閉包行列の計算方法を用いない並列トポロジカル整列アルゴリズムを示し,これを用いて最長路を求める並列アルゴリズムである.具体的には,はじめにDAGのトポロジカル整列を行い節点のランクを求め,次にその逆向き線形リストに対して同様の方法でランクを求めて,これらのランクを用いてすべての最長路を求める並列アルゴリズムである.DAGにおいて節点数n,辺数mとすると,提案するアルゴリズムの計算量はCREW-PRAM並列計算機モデルでプロセッサ数がO(n+m),時間量がO(log^2m)である.