Repository logo
 
Publication

An autonomic parallel strategy for exhaustive search tree algorithms on shared or heterogeneous systems

authorProfile.emailbiblioteca@isel.pt
datacite.subject.fosEngenharia e Tecnologia::Engenharia Eletrotécnica, Eletrónica e Informática
dc.contributor.authorGonçalves de Oliveira Passos, Fernanda
dc.contributor.authorRebello, Vinod E. F.
dc.date.accessioned2025-07-29T10:56:54Z
dc.date.available2025-07-29T10:56:54Z
dc.date.issued2025-03-10
dc.description.abstractBacktracking branch-and-prune (BP) algorithms and their variants are exhaustive search tree techniques widely employed to solve optimization problems in many scientific areas. However, they characteristically often demand significant amounts of computing power for problem sizes representative of real-world scenarios. Given that their search domains can often be partitioned, these algorithms are frequently designed to execute in parallel by harnessing distributed computing systems. However, to achieve efficient parallel execution times, an effective strategy is required to balance the nonuniform partition workloads across the available resources. Furthermore, with the increasing integration of servers with heterogeneous resources and the adoption of resource sharing, balancing workloads is becoming complex. This paper proposes a strategy to execute parallel BP algorithms more efficiently on even shared or heterogeneous distributed systems. The approach integrates a self-adjusting dynamic partitioning method in the BP algorithm with a dynamic scheduler, provided by an application middleware, which manages the parallel execution while addressing any issues of imbalance. Empirical results indicate better scalability with efficiencies above 90% for instances of an application case study for the discretizable molecular distance geometry problem (DMDGP). Improvements of up to 38% were obtained in execution speed-ups compared to a more traditional parallel BP implementation for DMDGP.eng
dc.identifier.citationPassos, F. G., & Rebello, V. E. (2024). An autonomic parallel strategy for exhaustive search tree algorithms on shared or heterogeneous systems. Concurrency and Computation-Pratice & Experience, 36(6), 1-23.
dc.identifier.doihttps://doi.org/10.1002/cpe.7955
dc.identifier.eissn1532-0634
dc.identifier.issn1532-0626
dc.identifier.urihttp://hdl.handle.net/10400.21/21984
dc.language.isoeng
dc.peerreviewedyes
dc.publisherWiley
dc.relation.hasversionhttps://onlinelibrary.wiley.com/doi/10.1002/cpe.7955
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/
dc.subjectAutonomic computing
dc.subjectHeterogeneous distributed systems
dc.subjectParallel branch-and-prune algorithms
dc.subjectSearch tree algorithms
dc.subjectSelf-configuring parallel algorithms
dc.titleAn autonomic parallel strategy for exhaustive search tree algorithms on shared or heterogeneous systemseng
dc.typeresearch article
dspace.entity.typePublication
oaire.citation.endPage23
oaire.citation.issue6
oaire.citation.startPage1
oaire.citation.titleConcurrency and Computation: Pratice and Experience
oaire.citation.volume36
oaire.versionhttp://purl.org/coar/version/c_be7fb7dd8ff6fe43
person.familyNameGonçalves de Oliveira Passos
person.givenNameFernanda
person.identifier2279041
person.identifier.ciencia-idA011-8F84-2C21
person.identifier.orcid0000-0002-6647-9822
person.identifier.ridS-8574-2018
person.identifier.scopus-author-id57190971014
relation.isAuthorOfPublication814ce7a3-e7e6-475f-b574-26299b7ea5b0
relation.isAuthorOfPublication.latestForDiscovery814ce7a3-e7e6-475f-b574-26299b7ea5b0

Files

Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
An autonomic_FGOPassos.pdf
Size:
3.78 MB
Format:
Adobe Portable Document Format
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
4.03 KB
Format:
Item-specific license agreed upon to submission
Description: