Parallel Branch and Bound Algorithm with the Hierarchical Master-Worker Paradigm on the Grid

• Item type: Trans(1)
• 公開日: 2006-09-15
• タイトル: Parallel Branch and Bound Algorithm with the Hierarchical Master-Worker Paradigm on the Grid
• タイトル / 言語: en
• タイトル: Parallel Branch and Bound Algorithm with the Hierarchical Master-Worker Paradigm on the Grid
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: グリッド
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Tokyo Institute of Technology/PRESTO JST Presently with Tokyo Institute of Technology
• 著者所属: University of Virginia
• 著者所属: Tokyo Institute of Technology Presently with NTT Communications Corporation
• 著者所属(英): en
• 著者所属(英): Tokyo Institute of Technology/PRESTO, JST,Presently with Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): University of Virginia
• 著者所属(英): en
• 著者所属(英): Tokyo Institute of Technology,Presently with NTT Communications Corporation
• 著者名: Kento, Aida; Yoshiaki, Futakata; Tomotaka, Osumi
• 著者名(英): Kento, Aida; Yoshiaki, Futakata; Tomotaka, Osumi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: This paper proposes a parallel branch and bound algorithm that efficiently runs on the Grid. The proposed algorithm is parallelized with the hierarchical master-worker paradigm in order to efficiently compute fine-grain tasks on the Grid. The hierarchical algorithm performs master-worker computing in two levels computing among PC clusters on the Grid and that among computing nodes in each PC cluster and reduces communication overhead by localizing frequent communication in tightly coupled computing resources or a PC cluster. On each PC cluster granularity of tasks dispatched to computing nodes is adaptively adjusted to obtain the best performance. The algorithm is implemented on the Grid testbed by using GridRPC middleware Ninf-G and Ninf. In the implementation communication among PC clusters is securely performed via Ninf-G using the Grid Security Infrastructure and fast communication in each PC cluster is performed via Ninf. The experimental results showed that parallelization with the hierarchical master-worker paradigm using combination of Ninf-G and Ninf effectively utilized computing resources on the Grid in order to run a fine-grain application. The results also showed that the adaptive task granularity control automatically gave the same or better performance compared to performance with manual control.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper proposes a parallel branch and bound algorithm that efficiently runs on the Grid. The proposed algorithm is parallelized with the hierarchical master-worker paradigm in order to efficiently compute fine-grain tasks on the Grid. The hierarchical algorithm performs master-worker computing in two levels, computing among PC clusters on the Grid and that among computing nodes in each PC cluster, and reduces communication overhead by localizing frequent communication in tightly coupled computing resources, or a PC cluster. On each PC cluster, granularity of tasks dispatched to computing nodes is adaptively adjusted to obtain the best performance. The algorithm is implemented on the Grid testbed by using GridRPC middleware, Ninf-G and Ninf. In the implementation, communication among PC clusters is securely performed via Ninf-G using the Grid Security Infrastructure, and fast communication in each PC cluster is performed via Ninf. The experimental results showed that parallelization with the hierarchical master-worker paradigm using combination of Ninf-G and Ninf effectively utilized computing resources on the Grid in order to run a fine-grain application. The results also showed that the adaptive task granularity control automatically gave the same or better performance compared to performance with manual control.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11833852
• 書誌情報: 情報処理学会論文誌コンピューティングシステム（ACS）; 巻 47, 号 SIG12(ACS15), p. 193-206, 発行日 2006-09-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7829
• 出版者 / 言語: ja
• 出版者: 情報処理学会