A parallel branch-and-bound algorithm for MIN-based multiprocessors

Myung K. Yang; Chita R. Das

doi:10.1145/107971.108000

A parallel branch-and-bound algorithm for MIN-based multiprocessors

Myung K. Yang
, Chita R. Das

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Scopus citations

Abstract

A parallel "Decomposite Best-First" search Branch-and-Bound algorithm (pdbsbb) for MIN-based multiprocessor systems is proposed in this paper. A conflict free mapping scheme, known as step-by-step spread, is used to map the algorithm efficiently on to a MIN-based system for reducing communication overhead. It is shown that the proposed algorithm provides better speed-up than other reported schemes when communication overhead is taken into consideration.

Original language	English (US)
Title of host publication	Proceedings of the 1991 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1991
Publisher	Association for Computing Machinery, Inc
Pages	222-223
Number of pages	2
ISBN (Print)	0897913922, 9780897913928
DOIs	https://doi.org/10.1145/107971.108000
State	Published - Apr 2 1991
Event	1991 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1991 - San Diego, United States Duration: May 21 1991 → May 24 1991

Publication series

Name	Proceedings of the 1991 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1991

Other

Other	1991 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1991
Country/Territory	United States
City	San Diego
Period	5/21/91 → 5/24/91

All Science Journal Classification (ASJC) codes

Computational Theory and Mathematics
Software

Access to Document

10.1145/107971.108000

Cite this

Yang, M. K., & Das, C. R. (1991). A parallel branch-and-bound algorithm for MIN-based multiprocessors. In Proceedings of the 1991 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1991 (pp. 222-223). (Proceedings of the 1991 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1991). Association for Computing Machinery, Inc. https://doi.org/10.1145/107971.108000

Yang, Myung K. ; Das, Chita R. / A parallel branch-and-bound algorithm for MIN-based multiprocessors. Proceedings of the 1991 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1991. Association for Computing Machinery, Inc, 1991. pp. 222-223 (Proceedings of the 1991 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1991).

@inproceedings{6e6f62b203634b5bbe93a189e79b1418,

title = "A parallel branch-and-bound algorithm for MIN-based multiprocessors",

abstract = "A parallel {"}Decomposite Best-First{"} search Branch-and-Bound algorithm (pdbsbb) for MIN-based multiprocessor systems is proposed in this paper. A conflict free mapping scheme, known as step-by-step spread, is used to map the algorithm efficiently on to a MIN-based system for reducing communication overhead. It is shown that the proposed algorithm provides better speed-up than other reported schemes when communication overhead is taken into consideration.",

author = "Yang, \{Myung K.\} and Das, \{Chita R.\}",

note = "Publisher Copyright: {\textcopyright} 1991 ACM.; 1991 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1991 ; Conference date: 21-05-1991 Through 24-05-1991",

year = "1991",

month = apr,

day = "2",

doi = "10.1145/107971.108000",

language = "English (US)",

isbn = "0897913922",

series = "Proceedings of the 1991 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1991",

publisher = "Association for Computing Machinery, Inc",

pages = "222--223",

booktitle = "Proceedings of the 1991 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1991",

}

Yang, MK & Das, CR 1991, A parallel branch-and-bound algorithm for MIN-based multiprocessors. in Proceedings of the 1991 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1991. Proceedings of the 1991 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1991, Association for Computing Machinery, Inc, pp. 222-223, 1991 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1991, San Diego, United States, 5/21/91. https://doi.org/10.1145/107971.108000

A parallel branch-and-bound algorithm for MIN-based multiprocessors. / Yang, Myung K.; Das, Chita R.
Proceedings of the 1991 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1991. Association for Computing Machinery, Inc, 1991. p. 222-223 (Proceedings of the 1991 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1991).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - A parallel branch-and-bound algorithm for MIN-based multiprocessors

AU - Yang, Myung K.

AU - Das, Chita R.

PY - 1991/4/2

Y1 - 1991/4/2

N2 - A parallel "Decomposite Best-First" search Branch-and-Bound algorithm (pdbsbb) for MIN-based multiprocessor systems is proposed in this paper. A conflict free mapping scheme, known as step-by-step spread, is used to map the algorithm efficiently on to a MIN-based system for reducing communication overhead. It is shown that the proposed algorithm provides better speed-up than other reported schemes when communication overhead is taken into consideration.

AB - A parallel "Decomposite Best-First" search Branch-and-Bound algorithm (pdbsbb) for MIN-based multiprocessor systems is proposed in this paper. A conflict free mapping scheme, known as step-by-step spread, is used to map the algorithm efficiently on to a MIN-based system for reducing communication overhead. It is shown that the proposed algorithm provides better speed-up than other reported schemes when communication overhead is taken into consideration.

UR - https://www.scopus.com/pages/publications/51649109865

UR - https://www.scopus.com/pages/publications/51649109865#tab=citedBy

U2 - 10.1145/107971.108000

DO - 10.1145/107971.108000

M3 - Conference contribution

AN - SCOPUS:51649109865

SN - 0897913922

SN - 9780897913928

T3 - Proceedings of the 1991 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1991

SP - 222

EP - 223

BT - Proceedings of the 1991 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1991

PB - Association for Computing Machinery, Inc

T2 - 1991 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1991

Y2 - 21 May 1991 through 24 May 1991

ER -

Yang MK, Das CR. A parallel branch-and-bound algorithm for MIN-based multiprocessors. In Proceedings of the 1991 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1991. Association for Computing Machinery, Inc. 1991. p. 222-223. (Proceedings of the 1991 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1991). doi: 10.1145/107971.108000

A parallel branch-and-bound algorithm for MIN-based multiprocessors

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this