Volume 23, Issue 4 pp. 1-13
Article
Full Access

An asynchronous parallel branch-and-bound algorithm

Tsuyoshi Kawaguchi

Tsuyoshi Kawaguchi

Faculty of Engineering, Miyazaki University, Miyazaki, Japan 889-21

Tsuyoshi Kawaguchi: graduated in 1974 from the Department of Communication Engineering, Faculty of Engineering, Osaka University, where he obtained a Dr. of Eng. degree in 1981. He joined Sharp Corporation in 1974. In 1981, he joined the Faculty of Engineering, Ryukyu University as a Research Associate, and later was appointed an Associate Professor. In 1990, he became an Associate Professor in the Department of Electronics, Faculty of Engineering, Miyazaki University. He is engaged in research on scheduling algorithms and parallel processing. He is a member of IEEE; ACM; and the Information Processing Society of Japan.

Search for more papers by this author
Hiroshi Masuyama

Hiroshi Masuyama

Members

Faculty of Engineering, Miyazaki University, Miyazaki, Japan 889-21

Hiroshi Masuyama: graduated in 1966 from the Department of Electrical Engineering, Nihon University, and in 1969 he obtained a Master's degree from Hiroshima University. In the same year he joined the Faculty of Engineering, Hiroshima University as a Research Associate. He was an Associate Professor on the Faculty of Engineering, Miyazaki University and is currently a Professor there teaching electronic control engineering. He has been engaged in research on construction and fault counterplan of nonlinear parallel control systems, computer networks, and test of software function and structure. He has also been involved in education and research on evaluation of an instruction method based on group learning response and optimal management of score files. He is a member of IEEE and of the Information Processing Society of Japan.

Search for more papers by this author
Tamotsu Maeda

Tamotsu Maeda

Associate Member

Faculty of Engineering, University of the Ryukyus, Okinawa, Japan 903-01

Tamotsu Maeda: graduated in 1988 from the Department of Electronic Information Engineering, Faculty of Engineering, Ryukyu University, where in 1990, he obtained a Master's degree. The same year he joined NEC Corp. While at the university, he was engaged in research on parallel processing methods.

Search for more papers by this author

Abstract

This paper presents a parallel branch-and-bound algorithm which is applicable to a loosely coupled multiprocessor with nonhierarchical interconnection network such as torus or hypercube. This algorithm is asynchronous and processing elements (PEs) start evaluation of nodes without being synchronized. Thus, when each PE finishes evaluation of one node, it can immediately start the evaluation of the next node.

First, we compared the performance for parallel branch-and-bound algorithms which have almost the same communication overhead. From the simulation results it was confirmed that when the proposed algorithm is applied to a torus machine, an efficiency (speed-up rate divided by the number of PEs) is obtained which is about twice better than that of the existing synchronous algorithm for the improved tree machine and about 1.4 times better than that of the synchronous algorithm for a torus machine proposed by the authors. Interconnection networks among PEs suitable for parallelization of branch-and-bound algorithms were investigated by applying the algorithm in this paper to several kinds of interconnection networks among PEs.

As the results, it was found that even in the case in which communication time between adjacent PEs has very little effect on the execution time of an algorithm, a hypercube machine realizes almost the same efficiency as that of an interconnection network with a larger degree of PEs.

The full text of this article hosted at iucr.org is unavailable due to technical difficulties.