タスクスケジューリング問題における探索ノード数削減によるPDF/IHS法の高速化  [in Japanese] A Speedup Method for PDF/IHS by Reducing of Branching Nodes in Task Scheduling Problems  [in Japanese]

Access this Article

Search this Article

Abstract

本論文では,タスクスケジューリング問題を高速に解くために,レディ状態を削減したPDF/IHS(Parallelized Depth First/Implicit Heuristic Search)法の探索ノード数を削減するアルゴリズムを提案する.PDF/IHS法は,階層的挟み撃ち探索を用いた並列探索アルゴリズムであり,実行可能なタスクをPE(Processing Element)に割り当てる組合せをすべて列挙することで分枝限定法の探索木を生成する.このため,問題規模が大きくなるほど探索ノード数が膨大になり,探索ノード数の削減が必要となる.PDF/IHS法の探索ノード数を削減するために,不必要なレディ状態を割当てた部分問題を枝刈りする手法が提案されている.不必要なレディ状態を割り当てた部分問題を枝刈りする法は,割り当てたタスク情報のみを用いて枝刈りするため,探索する必要のない部分問題のすべてを枝刈りできない.そこで本論文では,探索する必要のないすべての部分問題を枝刈りするために,探索済みノード情報を利用する.評価の結果,探索済みノードを利用した枝刈りをすることで,スレッド数2のとき相乗平均約1.39倍高速に求解できることを確認した.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.

Journal

  • 情報処理学会論文誌コンピューティングシステム(ACS)

    情報処理学会論文誌コンピューティングシステム(ACS) 11(2), 17-26, 2018-08-03

Codes

  • NII Article ID (NAID)
    170000149667
  • NII NACSIS-CAT ID (NCID)
    AA11833852
  • Text Lang
    JPN
  • Article Type
    Article
  • ISSN
    1882-7829
  • Data Source
    IPSJ 
Page Top