| Article ID: | iaor1989394 |
| Country: | Japan |
| Volume: | J72-D-I |
| Issue: | 4 |
| Start Page Number: | 254 |
| End Page Number: | 261 |
| Publication Date: | Apr 1989 |
| Journal: | Transactions of the Institute of Electronics, Information and Communication Engineers |
| Authors: | Kawaguchi Tsuyoshi, Maeda Tamotsu |
| Keywords: | construction & architecture, search |
Torus is one of the most promising interconnection topologies for a multiprocessor system with a large number of processors. This paper presents a parallel branch-and-bound algorithm for a torus machine with additional global links. Using torus network, processors send subproblems to adjacent processors in order to balance their loads. Global links are used for broadcasting the newly obtained temporary solution to all processors. Using simulation experiments, performance of the proposed algorithm was compared with that of another algorithm implemented on an improved tree machine, called DON system. These experiments showed that the speedup rate obtained by the proposed algorithm is always greater than the speedup rate obtained by the algorithm implemented on the DON system. [In Japanese.]