| Item type |
Trans(1) |
| 公開日 |
2018-08-03 |
| タイトル |
|
|
タイトル |
タスクスケジューリング問題における探索ノード数削減によるPDF/IHS法の高速化 |
| タイトル |
|
|
言語 |
en |
|
タイトル |
A Speedup Method for PDF/IHS by Reducing of Branching Nodes in Task Scheduling Problems |
| 言語 |
|
|
言語 |
jpn |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
タスクスケジューリング，PDF/IHS法，分枝限定法，並列処理 |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| 著者所属 |
|
|
|
千葉工業大学大学院情報科学研究科情報科学専攻 |
| 著者所属 |
|
|
|
千葉工業大学 |
| 著者所属 |
|
|
|
千葉工業大学大学院情報科学研究科情報科学専攻 |
| 著者所属 |
|
|
|
千葉工業大学情報科学部情報工学科 |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Information and Computer Science, Chiba Institute of Technology |
| 著者所属(英) |
|
|
|
en |
|
|
Chiba Institute of Technology |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Information and Computer Science, Chiba Institute of Technology |
| 著者所属(英) |
|
|
|
en |
|
|
Department of Computer Science, Faculty of Information and Computer Science, Chiba Institute of Technology |
| 著者名 |
松瀨, 弘明
中村, あすか
富永, 浩文
前川, 仁孝
|
| 著者名(英) |
Hiroaki, Matsuse
Asuka, Nakamura
Hirobumi, Tominaga
Yoshitaka, Maekawa
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
本論文では，タスクスケジューリング問題を高速に解くために，レディ状態を削減したPDF/IHS（Parallelized Depth First/Implicit Heuristic Search）法の探索ノード数を削減するアルゴリズムを提案する．PDF/IHS法は，階層的挟み撃ち探索を用いた並列探索アルゴリズムであり，実行可能なタスクをPE（Processing Element）に割り当てる組合せをすべて列挙することで分枝限定法の探索木を生成する．このため，問題規模が大きくなるほど探索ノード数が膨大になり，探索ノード数の削減が必要となる．PDF/IHS法の探索ノード数を削減するために，不必要なレディ状態を割当てた部分問題を枝刈りする手法が提案されている．不必要なレディ状態を割り当てた部分問題を枝刈りする法は，割り当てたタスク情報のみを用いて枝刈りするため，探索する必要のない部分問題のすべてを枝刈りできない．そこで本論文では，探索する必要のないすべての部分問題を枝刈りするために，探索済みノード情報を利用する．評価の結果，探索済みノードを利用した枝刈りをすることで，スレッド数2のとき相乗平均約1.39倍高速に求解できることを確認した． |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
This paper proposes a reduction algorithm of branching nodes for the PDF/IHS (Parallelized Depth First/Implicit Heuristic Search) using allocations of idle tasks method for solving task scheduling problems fast. The PDF/IHS is parallel search method using HPAS (Hierarchical Pincers Attack Search). The search method creates the search tree by enumerating all combinations of the allocatable tasks to PE (Processing Element). Therefore, it is necessary to reduce the number of search nodes to solve large-scale problems having many search nodes. We proposed the bounding method of the number of search nodes allocating unnecessary idle tasks to reduce search nodes of PDF/IHS. This method can not cut all of subproblems which do not need to search, because this method cuts subproblems using information of allocated tasks. Therefore, it is necessary to reduce all unnecessary nodes to perform further speedup. The proposed method reduces unnecessary subproblems by using searched subproblems. As a result of evaluation, the speedup ratio of the proposed method with the PDF/IHS is about 1.39 times on geometric average at 2 threads. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AA11833852 |
| 書誌情報 |
情報処理学会論文誌コンピューティングシステム（ACS）
巻 11,
号 2,
p. 17-26,
発行日 2018-08-03
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
1882-7829 |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-TACS1102005.pdf (1.2 MB)
