文献

J-GLOBAL ID：201402271221124842   整理番号：14A1007165

多様なタスクスケジューリング問題への解集合プログラミングの適用

Application of Answer Set Programming to Various Forms of the Task Scheduling Problem

著者 (4件)： 小林弘幸 (大阪大 大学院情報科学研究科) ,  中川博之 (大阪大 大学院情報科学研究科) ,  小島英春 (大阪大 大学院情報科学研究科) ,  土屋達弘 (大阪大 大学院情報科学研究科)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 114  号： 127(SS2014 9-24)  ページ： 25-30  発行年： 2014年07月02日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 近年,シングルコアプロセッサからなるCPUでの性能向上の鈍化に伴いマルチコアプロセッサを採用したCPUが広く用いられるようになったが,マルチコアプロセッサで効率的に処理を行うためには,その性能を最大限に引き出すためにタスクを並列実行するスケジューリングが必要になるが,このスケジューリングは強NP困難な問題に分類される。またタスクスケジューリング問題は,ケースによって多種の問題が存在し,それら全てに対応するプログラムを作成するのは難しい。そこでモジュール設計が容易であり,多岐に渡るタスクスケジューリング問題に対応しやすい解集合プログラミング(Answer Set Programming:ASP)を用いてスケジューリングを行うプログラムを作成した。また多少問題形式の異なる並列機械問題におけるベンチマークに適応し,動作を確認した。その結果,与えられた問題を解くために全体を修正することなく,一部に修正を加えるだけで実現可能であることを示した。(著者抄録)

シソーラス用語： *スケジューリング ,  *論理プログラミング ,  モジュラ設計 ,  マイクロプロセッサ ,  制約プログラミング ,  並列処理 ,  グラフ
準シソーラス用語： タスクグラフ ,  *タスクスケジューリング ,  マルチコアプロセッサ ,  *解集合プログラミング

分類 (1件)： 計算機システム開発  (JD02010R)

引用文献 (13件)：

• H. Kasahara and S. Narita, “Practical multiprocessor scheduling algorithms for efficient parallel processing,” IEEE Trans. Comput., vol.33, no.11, pp.1023-1029, Nov. 1984. http://dx.doi.org/10.1109/TC.1984.1676376
• T.G. Lewis and H. El-Rewini, INTRODUCTION TO PARALLEL COMPUTING, Prentice-Hall inc., 1992.
• Y.-K. Kwok and I. Ahmad, “Static scheduling algorithms for allocating directed task graphs to multiprocessors,” ACM Comput. Surv., vol.31, no.4, pp.406-471, Dec. 1999. http://doi.acm.org/10.1145/344588.344618
• “The international sat competitions web page”. http://www.satcompetition.org/.
• M. Gebser, T. Schaub, and S. Thiele, “Gringo: A new grounder for answer set programming,” Logic Programming and Nonmonotonic Reasoning, pp.266-271, Springer, 2007.

タイトルに関連する用語 (2件)： タスクスケジューリング ,  解集合プログラミング