Parallel bio-inspired single source shortest path algorithms

2017
Arslan, Hilal
Real-world shortest path problems that usually dynamically change are challeng- ing and computationally expensive, and earlier studies in the literature require pro- hibitively long time to obtain the solution. To cope with such problems, we introduce novel bio-inspired parallel algorithms based on Physarum Solver. The first proposed algorithm is a fast and efficient parallel Physarum Solver with the objective to find the shortest path for static graphs with positive edge weights. Next, we propose a novel fully-dynamic bio-inspired parallel algorithm in order to find the shortest path on dynamically changing graphs with positive edge weights. The proposed dynamic algorithm efficiently computes the shortest path when the edge weights of the graph increases, decreases, or both over time. The proposed algorithms include various improvements and optimizations for Physarum Solver. We parallelize the sequential Physarum Solver proposed by Tero, Kobayashi and Nakagaki in 2006. Furthermore, Physarum Solver requires the solution of linear systems whose coefficient matrix is a symmetric M-matrix and we note that this step is the most time consuming step. In the literature, however, there are not any studies that take an advantage of M-matrix property of the coefficient matrix to solve the linear systems efficiently in Physarum Solver and they are often solved by using a direct method, which is infeasible for large scale problems. We efficiently solve such linear systems using a parallel it- erative solver with a preconditioner based on M-matrix property of the coefficient matrix. Finally, we propose a novel hybrid algorithm in order to compute the shortest path exactly since Physarum Solver is not guaranteed to find the exact shortest path. This underlines the accuracy of the hybrid method to compute the shortest path ex- actly. In the hybrid algorithm, Physarum Solver is used in order to detect the edges which cannot form the shortest path tree. The algorithm, first, sparsifies a given graph by removing the edges which cannot form the shortest path tree and then we apply a classical shortest path algorithm, such as Dijkstra, or Breadth First Search (if the graph is unweighted) on the sparser graph with positive edge weights. The proposed method is, therefore, a two stage hybrid algorithm. The accuracy and the required solution time by the proposed hybrid method are compared against a state-of-the-art implementation of the Dijkstra’s algorithm on the original graph as the baseline. The results show that the proposed hybrid method achieves a significant speed improve- ment compared to the baseline. In order to evaluate the parallel algorithms, we use three different large graph models representing diverse real life applications. The par- allel scalability, running time and accuracy of the proposed algorithms are presented and compared against ∆-stepping which is the most representative parallel implemen- tation of Dijkstra’s algorithm. The proposed algorithms exhibit remarkable parallel speedup with comparable accuracy for sparse large graphs. This underlines the effec- tiveness of the proposed algorithm to deal with hard real-life problems requiring long running time using classical algorithms.

Suggestions

Parallel sparse and banded matrix – multiple vectors multiplication
Cincioğlu, Meftun; Manguoğlu, Murat; Department of Computer Engineering (2014)
In this thesis, performance of two important primitives, namely sparse and banded matrix – multiple vectors multiplication are studied. Sparse matrix – multiple vectors multiplication (SpMM) is one of the basic and most time consuming operations in many problems in science and engineering. Hence, any improvement in the performance of SpMM operations has a great impact on the wide spectrum of problems. One of the objectives of this thesis is to improve the performance of parallel SpMM operation by reducing i...
Parallel Minimum Norm Solution of Sparse Block Diagonal Column Overlapped Underdetermined Systems
Torun, F. Sukru; Manguoğlu, Murat; Aykanat, Cevdet (2017-03-01)
Underdetermined systems of equations in which the minimum norm solution needs to be computed arise in many applications, such as geophysics, signal processing, and biomedical engineering. In this article, we introduce a new parallel algorithm for obtaining the minimum 2-norm solution of an underdetermined system of equations. The proposed algorithm is based on the Balance scheme, which was originally developed for the parallel solution of banded linear systems. The proposed scheme assumes a generalized band...
Intelligent design objects applied to the spatial allocation problem
Zaratiegui Fernandez, Javier Ignacio; Sorguç, Arzu; Computational Design and Fabrication Technologies in Department of Architecture (2014)
This thesis approaches the spatial allocation problem as a multi-objective optimization problem. It proposes the use of Intelligent Design Objects (IDO) model to help designers with this task. Solutions are generated and evaluated, according the user defined criteria. Iterative improvement is proposed as a help to visualize candidate solutions and conceive the desired spatial relations. By defining the criteria and rating it numerically, both designer and client are able compare the solutions obtained. The ...
PARALLEL MULTILEVEL FAST MULTIPOLE ALGORITHM FOR COMPLEX PLASMONIC METAMATERIAL STRUCTURES
Ergül, Özgür Salih (2013-11-09)
A parallel implementation of the multilevel fast multipole algorithm (MLFMA) is developed for fast and accurate solutions of electromagnetics problems involving complex plasmonic metamaterial structures. Composite objects that consist of multiple penetrable regions, such as dielectric, lossy, and plasmonic parts, are formulated rigorously with surface integral equations and solved iteratively via MLFMA. Using the hierarchical strategy for the parallelization, the developed implementation is capable of simul...
ALGORITHMS FOR EFFICIENT VECTORIZATION OF REPEATED SPARSE POWER-SYSTEM NETWORK COMPUTATIONS
AYKANAT, C; OZGU, O; Güven, Ali Nezih (1995-02-01)
Standard sparsity-based algorithms used in power system applications need to be restructured for efficient vectorization due to the extremely short vectors processed, Further, intrinsic architectural features of vector computers such as chaining and sectioning should also be exploited for utmost performance, This paper presents novel data storage schemes and vectorization algorithms that resolve the recurrence problem, exploit chaining and minimize the number of indirect element selections in the repeated s...
Citation Formats
H. Arslan, “Parallel bio-inspired single source shortest path algorithms,” Ph.D. - Doctoral Program, Middle East Technical University, 2017.