動的負荷分散のための並列木探索(DTS)アルゴリズムの拡張 : 並列計算機AP1000でのライブラリ化  [in Japanese] Extension of Distributed Tree Search for Dynamic Load Balancing and Its Implementation as a Library on AP1000  [in Japanese]

Search this Article

Author(s)

Abstract

疎結合並列計算機上で木探索を行なう際に問題となるプロセッサ間の木構造管理や動的負荷分散機能の実現方法として,並列木探索(DTS)アルゴリズムを基にした拡張並列木探索(EDTS)アルゴリズムを提案する.本アルゴリズムは様々な木探索問題や動的負荷分散方式を実現可能であり,これをライブラリ化することにより,木探索問題一般を対象とした言語環境として利用できる.並列計算機AP1000上での実装と性能評価の結果,このライブラリが実行速度・台数拡張性ともに良好であることが示された.

For programmers of tree searching applications on loosely-coupled multiprocessors, it is troublesome to manage the tree structure spread across processors, and to balance the load of processors dynamically. As a solution of these problems, we propose EDTS, an extension of Distributed Tree Search algorithm. Various tree search applications and dynamic load balancing schemes can be realized with this algorithm, and the implementation as a library is useful as a programming environment for general tree search problems. The result of implementation and evaluation on multiprocessor AP1000 shows good performance and scalability of the library.

Journal

  • 情報処理学会研究報告. [プログラミング-言語基礎実践-]

    情報処理学会研究報告. [プログラミング-言語基礎実践-] 93(73), 57-64, 1993-08-19

    Information Processing Society of Japan (IPSJ)

Codes

  • NII Article ID (NAID)
    110002929375
  • NII NACSIS-CAT ID (NCID)
    AN10464060
  • Text Lang
    JPN
  • Data Source
    NII-ELS 
Page Top