トーラス型マルチプロセッサシステム上での分枝限定アルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 1988-05-20
• タイトル: トーラス型マルチプロセッサシステム上での分枝限定アルゴリズム
• タイトル / 言語: en
• タイトル: A Parallel Branch -and- Bound Algorithm for a Torus Machine
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 琉球大学工学部
• 著者所属: 琉球大学工学部
• 著者所属: 琉球大学工学部
• 著者所属(英): en
• 著者所属(英): University of the Ryukyus
• 著者所属(英): en
• 著者所属(英): University of the Ryukyus
• 著者所属(英): en
• 著者所属(英): University of the Ryukyus
• 著者名: 川口, 剛; 真栄田, 保; 喜屋武, 盛基
• 著者名(英): Tsuyoshi, Kawaguchi; Tamotsu, Maeda; Seiki, Kyan
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: トーラス型マルチプロセッサシステム上での並列分枝限定アルゴリズムを提案する。並列分技限定アルゴリズムに関する研究は、負荷分散手法の容易さのため、主に共有メモリ型システムに対して行われているが、このシステムは並列度に関して限界がある。一方、トーラス型システムは、木型システムと同様、高並列度を実現するのに適した構造をもつ。提案するアルゴリズムでは、部分問題を各プロセッサに均一に配分するための負荷分散手法が工夫されている。そして、ナップサック問題を用いた場合のシミュレーション結果から、本論文で提案するアルゴリズムの加速指数が、木型システムを改良したDONシステム（二重結合木型システム）に対する既存のアルゴリズムの加速指数より大きくなることが確かめろる。また、DONシステムに対するアルゴリズムと同様、問題の規模が大きくなるほど加速指数が増加し、しかも比較的計算時間を多く要す問題では加速指数がプロセッサの数より大きくなることが確かめられる。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper we propose a parallel algorithm to execute branch-and-bound procedure on a torus machine with additional global links. The torus network is used when processors send subproblems to the respective adjacent processors in order to get a balanced work load. And global links are used for broadcasting the newly obtained temporary solution to all processors. Using the knapsack problem, the performance of the proposed algorithm is evaluated and is compared with the performance of a parallel brnch-and-bound algorithm for an improved tree machine.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10116224
• 書誌情報: 情報処理学会研究報告マルチメディア通信と分散処理（DPS）; 巻 1988, 号 35(1988-DPS-037), p. 89-96, 発行日 1988-05-20
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会