@techreport{oai:ipsj.ixsq.nii.ac.jp:00036182,
 author = {川口, 剛 and 真栄田, 保 and 喜屋武, 盛基 and Tsuyoshi, Kawaguchi and Tamotsu, Maeda and Seiki, Kyan},
 issue = {35(1988-DPS-037)},
 month = {May},
 note = {トーラス型マルチプロセッサシステム上での並列分枝限定アルゴリズムを提案する。並列分技限定アルゴリズムに関する研究は、負荷分散手法の容易さのため、主に共有メモリ型システムに対して行われているが、このシステムは並列度に関して限界がある。一方、トーラス型システムは、木型システムと同様、高並列度を実現するのに適した構造をもつ。提案するアルゴリズムでは、部分問題を各プロセッサに均一に配分するための負荷分散手法が工夫されている。そして、ナップサック問題を用いた場合のシミュレーション結果から、本論文で提案するアルゴリズムの加速指数が、木型システムを改良したDONシステム（二重結合木型システム）に対する既存のアルゴリズムの加速指数より大きくなることが確かめろる。また、DONシステムに対するアルゴリズムと同様、問題の規模が大きくなるほど加速指数が増加し、しかも比較的計算時間を多く要す問題では加速指数がプロセッサの数より大きくなることが確かめられる。, 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.},
 title = {トーラス型マルチプロセッサシステム上での分枝限定アルゴリズム},
 year = {1988}
}