Paper Info
Title
A Message-Passing Based Algorithm for k-Terminal Reliability
Abstract
As the exact computation of the k-terminal reliability is an NP-Complete problem, runtime and memory requirements grow exponentially with the input size. Shared memory parallelization algorithms were developed for reducing runtime. However, even a relatively high amount of memory can already be exhausted within a short period of time. A message-passing based algorithm is proposed in order to circumvent the memory limitation of shared memory implementations. It is the first message-passing based algorithm for the k-terminal problem. The new algorithm is designed for the currently most efficient BDD-based method. New data structures such as the distributed BDD and a distributed hash table lead to good speedup results and load-balanced task distributions. Now the size of computable inputs are limited to the memory carried along by the available cores. The two-terminal reliability of a 17 node complete network was computed on 1024 cores of the SuperMUC within 7 minutes, using 1.28 Terabyte of memory and resulting in more than 6 billion BDD nodes.
Year
DOI
Venue
2018
10.1109/EDCC.2018.00022
2018 14th European Dependable Computing Conference (EDCC)
Keywords
Field
DocType
k-terminal reliability,distributed memory,parallel algorithms,BDD,dependability analysis
Data structure,Shared memory,Computer science,Terabyte,Algorithm,Memory management,Message passing,Computation,Distributed hash table,Speedup
Conference
ISBN
Citations 
PageRank 
978-1-5386-8061-2
0
0.34
References 
Authors
12
2
Name
Order
Citations
PageRank
Minh Lê182.29
Josef Weidendorfer211517.98