We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
DiGTreeS: a distributed resilient framework for generalized tree search.
- Authors
Jamal, Md Arshad; Kailasam, Sriram; Goyal, Bhumanyu; Singh, Varun
- Abstract
Exact combinatorial search algorithms have applications in several areas of computational algebra, AI, discrete optimization, etc. These problems are compute-intensive and have a highly irregular search tree. Most of the earlier efforts to parallelize these algorithms used a fixed degree of parallelism during runtime. We show that such an approach leads to poor resource utilization as the parallel run-time efficiency of an irregular search application varies over time. We propose DiGTreeS, a distributed resilient framework for generalized tree search that supports elastic scaling. It features an easy-to-use API for expressing combinatorial search and hides away the system concerns such as load balancing, fault tolerance, and elastic scaling. We evaluate the DiGTreeS framework for different scaling strategies and show its effectiveness on four representative problem instances: Traveling Salesman Problem, 0–1 Knapsack, N-queens, and Generic State Space Search Application.
- Subjects
TRAVELING salesman problem; FAULT tolerance (Engineering); SEARCH algorithms; PARALLEL algorithms; TREES; KNAPSACK problems
- Publication
Journal of Supercomputing, 2024, Vol 80, Issue 10, p15006
- ISSN
0920-8542
- Publication type
Article
- DOI
10.1007/s11227-024-06017-9