A decentralized load balancing approach for parallel search-tree optimization

Faisal Abu Khzam; A.E. Mouawad

doi:10.1109/PDCAT.2012.16

A decentralized load balancing approach for parallel search-tree optimization

Faisal Abu Khzam, A.E. Mouawad

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings › peer-review

Abstract

Current generation supercomputers have over one million cores awaiting highly demanding computations and applications. An area that could largely benefit from such processing capabilities is naturally that of exact algorithms for N P-hard problems. We propose a general implementation framework that targets highly scalable parallel exact algorithms for N P-hard graph problems. We tackle the problems of efficiency and scalability by combining a fully decentralized dynamic load balancing strategy with special implementation techniques for exact graph algorithms. As a case-study, we use our framework to implement parallel algorithms for the VERTEX COVER and DOMINATING SET problems. We present experimental results that show notable improved running times on all types of input instances.

Original language	English
Title of host publication	Proceedings of 13th International Conference on Parallel and Distributed Computing, Applications, and Technologies, PDCAT 2012
Publisher	IEEE, Institute of Electrical and Electronics Engineers
Pages	173-178
Number of pages	6
ISBN (Print)	978-0-7695-4879-1
DOIs	https://doi.org/10.1109/PDCAT.2012.16
Publication status	Published - 2012
Externally published	Yes
Event	International Conference on Parallel and Distributed Computing, Applications, and Technologies (PDCAT 2012 13th) - Beijing, China, Beijing, China Duration: 1 Jan 2012 → … Conference number: 2012 (13th)

Conference

Conference	International Conference on Parallel and Distributed Computing, Applications, and Technologies (PDCAT 2012 13th)
Abbreviated title	PDCAT
Country/Territory	China
City	Beijing
Period	1/01/12 → …

Access to Document

10.1109/PDCAT.2012.16

Cite this

@inproceedings{bc81e21c4516431aa4c3b890df4b250a,

title = "A decentralized load balancing approach for parallel search-tree optimization",

abstract = "Current generation supercomputers have over one million cores awaiting highly demanding computations and applications. An area that could largely benefit from such processing capabilities is naturally that of exact algorithms for N P-hard problems. We propose a general implementation framework that targets highly scalable parallel exact algorithms for N P-hard graph problems. We tackle the problems of efficiency and scalability by combining a fully decentralized dynamic load balancing strategy with special implementation techniques for exact graph algorithms. As a case-study, we use our framework to implement parallel algorithms for the VERTEX COVER and DOMINATING SET problems. We present experimental results that show notable improved running times on all types of input instances.",

author = "{Abu Khzam}, Faisal and A.E. Mouawad",

year = "2012",

doi = "10.1109/PDCAT.2012.16",

language = "English",

isbn = "978-0-7695-4879-1",

pages = "173--178",

booktitle = "Proceedings of 13th International Conference on Parallel and Distributed Computing, Applications, and Technologies, PDCAT 2012",

publisher = "IEEE, Institute of Electrical and Electronics Engineers",

address = "United States",

note = "International Conference on Parallel and Distributed Computing, Applications, and Technologies (PDCAT 2012 13th), PDCAT ; Conference date: 01-01-2012",

}

Abu Khzam, F & Mouawad, AE 2012, A decentralized load balancing approach for parallel search-tree optimization. in Proceedings of 13th International Conference on Parallel and Distributed Computing, Applications, and Technologies, PDCAT 2012. IEEE, Institute of Electrical and Electronics Engineers, pp. 173-178, International Conference on Parallel and Distributed Computing, Applications, and Technologies (PDCAT 2012 13th), Beijing, China, 1/01/12. https://doi.org/10.1109/PDCAT.2012.16

A decentralized load balancing approach for parallel search-tree optimization. / Abu Khzam, Faisal; Mouawad, A.E.

Proceedings of 13th International Conference on Parallel and Distributed Computing, Applications, and Technologies, PDCAT 2012. IEEE, Institute of Electrical and Electronics Engineers, 2012. p. 173-178.

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings › peer-review

TY - GEN

T1 - A decentralized load balancing approach for parallel search-tree optimization

AU - Abu Khzam, Faisal

AU - Mouawad, A.E.

N1 - Conference code: 2012 (13th)

PY - 2012

Y1 - 2012

N2 - Current generation supercomputers have over one million cores awaiting highly demanding computations and applications. An area that could largely benefit from such processing capabilities is naturally that of exact algorithms for N P-hard problems. We propose a general implementation framework that targets highly scalable parallel exact algorithms for N P-hard graph problems. We tackle the problems of efficiency and scalability by combining a fully decentralized dynamic load balancing strategy with special implementation techniques for exact graph algorithms. As a case-study, we use our framework to implement parallel algorithms for the VERTEX COVER and DOMINATING SET problems. We present experimental results that show notable improved running times on all types of input instances.

AB - Current generation supercomputers have over one million cores awaiting highly demanding computations and applications. An area that could largely benefit from such processing capabilities is naturally that of exact algorithms for N P-hard problems. We propose a general implementation framework that targets highly scalable parallel exact algorithms for N P-hard graph problems. We tackle the problems of efficiency and scalability by combining a fully decentralized dynamic load balancing strategy with special implementation techniques for exact graph algorithms. As a case-study, we use our framework to implement parallel algorithms for the VERTEX COVER and DOMINATING SET problems. We present experimental results that show notable improved running times on all types of input instances.

U2 - 10.1109/PDCAT.2012.16

DO - 10.1109/PDCAT.2012.16

M3 - Conference Paper published in Proceedings

SN - 978-0-7695-4879-1

SP - 173

EP - 178

BT - Proceedings of 13th International Conference on Parallel and Distributed Computing, Applications, and Technologies, PDCAT 2012

PB - IEEE, Institute of Electrical and Electronics Engineers

T2 - International Conference on Parallel and Distributed Computing, Applications, and Technologies (PDCAT 2012 13th)

Y2 - 1 January 2012

ER -

A decentralized load balancing approach for parallel search-tree optimization

Abstract

Conference

Access to Document

Fingerprint

Cite this