{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,24]],"date-time":"2023-10-24T06:10:30Z","timestamp":1698127830095},"reference-count":7,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2007,3,21]],"date-time":"2007-03-21T00:00:00Z","timestamp":1174435200000},"content-version":"vor","delay-in-days":5558,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Systems &amp; Computers in Japan"],"published-print":{"date-parts":[[1992,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper presents a parallel branch\u2010and\u2010bound 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.<\/jats:p><jats:p>First, we compared the performance for parallel branch\u2010and\u2010bound 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\u2010up 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\u2010and\u2010bound algorithms were investigated by applying the algorithm in this paper to several kinds of interconnection networks among PEs.<\/jats:p><jats:p>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.<\/jats:p>","DOI":"10.1002\/scj.4690230401","type":"journal-article","created":{"date-parts":[[2007,7,7]],"date-time":"2007-07-07T23:32:43Z","timestamp":1183851163000},"page":"1-13","source":"Crossref","is-referenced-by-count":0,"title":["An asynchronous parallel branch\u2010and\u2010bound algorithm"],"prefix":"10.1002","volume":"23","author":[{"given":"Tsuyoshi","family":"Kawaguchi","sequence":"first","affiliation":[]},{"given":"Hiroshi","family":"Masuyama","sequence":"additional","affiliation":[]},{"given":"Tamotsu","family":"Maeda","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2007,3,21]]},"reference":[{"issue":"6","key":"e_1_2_1_2_2","first-page":"403","article-title":"Parallelization of branch\u2010and\u2010bound algorithm and its evaluation","volume":"62","author":"Imai M.","year":"1979","journal-title":"Trans. (D) I.E.I.C.E."},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1984.1676453"},{"key":"e_1_2_1_4_2","first-page":"4Q\u20105","volume-title":"A Parallelization Method for Optimized Multiprocessor Scheduling","author":"Itoh A.","year":"1987"},{"issue":"9","key":"e_1_2_1_5_2","first-page":"1002","article-title":"A double\u2010tree\u2010structured multicomputer system and its application to combinatorial problems","volume":"9","author":"Imai M.","year":"1986","journal-title":"Trans. I.E.I.C.E., Japan"},{"key":"e_1_2_1_6_2","doi-asserted-by":"crossref","unstructured":"O.Vornberger.Implementing branch\u2010and\u2010bound in a ring of processors. CONPAR'86 Proc. Conf. on Algorithms and Hardware for Parallel Processing Aachen pp.157\u2013164(1986).","DOI":"10.1007\/3-540-16811-7_166"},{"issue":"4","key":"e_1_2_1_7_2","first-page":"254","article-title":"Branch\u2010and\u2010bound algorithm on torus\u2010type multiprocessor system","volume":"72","author":"Kawaguchi T.","year":"1989","journal-title":"Trans. (D\u2010I) I.E.I.C.E."},{"key":"e_1_2_1_8_2","unstructured":"T.Ibaraki.On Combinatorial Optimization and Branch\u2010and\u2010Bound Method. Lecture on Mathematical Programming 8 Sangyo\u2010Tosho (1983)."}],"container-title":["Systems and Computers in Japan"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fscj.4690230401","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/scj.4690230401","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,23]],"date-time":"2023-10-23T20:44:36Z","timestamp":1698093876000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/scj.4690230401"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,1]]},"references-count":7,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1992,1]]}},"alternative-id":["10.1002\/scj.4690230401"],"URL":"https:\/\/doi.org\/10.1002\/scj.4690230401","archive":["Portico"],"relation":{},"ISSN":["0882-1666","1520-684X"],"issn-type":[{"value":"0882-1666","type":"print"},{"value":"1520-684X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,1]]}}}