English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Supercomputers are equipped with an increasingly large number of cores to usecomputational power as a way of solving problems that are otherwiseintractable. Unfortunately, getting serial algorithms to run in parallel totake advantage of these computational resources remains a challenge for severalapplication domains. Many parallel algorithms can scale to only hundreds ofcores. The limiting factors of such algorithms are usually communicationoverhead and poor load balancing. Solving NP-hard graph problems to optimalityusing exact algorithms is an example of an area in which there has so far beenlimited success in obtaining large scale parallelism. Many of these algorithmsuse recursive backtracking as their core solution paradigm. In this paper, wepropose a lightweight, easy-to-use, scalable framework for transforming almostany recursive backtracking algorithm into a parallel one. Our framework incursminimal communication overhead and guarantees a load-balancing strategy that isimplicit, i.e., does not require any problem-specific knowledge. The key ideabehind this framework is the use of an indexed search tree approach that isoblivious to the problem being solved. We test our framework with parallelimplementations of algorithms for the well-known Vertex Cover and DominatingSet problems. On sufficiently hard instances, experimental results show linearspeedups for thousands of cores, reducing running times from days to just a fewminutes.

An Easy-to-use Scalable Framework for Parallel Recursive Backtracking