A Double-Tree Structured Multicomputer System and Its Application to Combinatorial Problems

Masaharu IMAI

Summary :

In this paper, a combinatorial problem oriented multicomputer system called DON (Double-Tree Structured Network Machine) is proposed. And a parallel branch-and-bound program scheme for the DON system is described. The DON system is composed of two binary-tree structured subsystems and a system controller. The DON system works as a post-end processor of a host computer system. The DON system is designed to achieve high parallelism and efficient pipeline ability. One of the most distinctive features of the DON system, compared to a conventional single-tree machine, is that the algorithms with pipeline features can be easily implemented and executed more efficiently. From the experimental results through simulation, it appears that the DON system can solve large scale combinatorial problems more efficiently than a conventional single-tree machine.

• Publication: IEICE TRANSACTIONS on transactions Vol.E69-E No.9 pp.1002-1010
• Publication Date: 1986/09/25
• Type of Manuscript: PAPER
• Category: Computer System

Authors

Masaharu IMAI

Keyword