A decentralized load balancing approach for parallel search-tree optimization

Faisal Abu Khzam, A.E. Mouawad

Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedingspeer-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 languageEnglish
Title of host publicationProceedings of 13th International Conference on Parallel and Distributed Computing, Applications, and Technologies, PDCAT 2012
PublisherIEEE, Institute of Electrical and Electronics Engineers
Pages173-178
Number of pages6
ISBN (Print)978-0-7695-4879-1
DOIs
Publication statusPublished - 2012
Externally publishedYes
EventInternational 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

ConferenceInternational Conference on Parallel and Distributed Computing, Applications, and Technologies (PDCAT 2012 13th)
Abbreviated titlePDCAT
CountryChina
CityBeijing
Period1/01/12 → …

Fingerprint

Dive into the research topics of 'A decentralized load balancing approach for parallel search-tree optimization'. Together they form a unique fingerprint.

Cite this