Submitted by scrawford on

Title | Solving Linear Diophantine Systems on Parallel Architectures |

Publication Type | Journal Article |

Year of Publication | 2019 |

Authors | Zaitsev, D., S. Tomov, and J. Dongarra |

Journal | IEEE Transactions on Parallel and Distributed Systems |

Volume | 30 |

Issue | 5 |

Pagination | 1158-1169 |

Date Published | 2019-05 |

Keywords | Mathematical model, Matrix decomposition, Parallel architectures, Petri nets, Software algorithms, Sparse matrices, Task analysis |

Abstract | Solving linear Diophantine systems of equations is applied in discrete-event systems, model checking, formal languages and automata, logic programming, cryptography, networking, signal processing, and chemistry. For modeling discrete systems with Petri nets, a solution in non-negative integer numbers is required, which represents an intractable problem. For this reason, solving such kinds of tasks with significant speedup is highly appreciated. In this paper we design a new solver of linear Diophantine systems based on the parallel-sequential composition of the system clans. The solver is studied and implemented to run on parallel architectures using a two-level parallelization concept based on MPI and OpenMP. A decomposable system is usually represented by a sparse matrix; a minimal clan size of the decomposition restricts the granulation of the technique. MPI is applied for solving systems for clans using a parallel-sequential composition on distributed-memory computing nodes, while OpenMP is applied in solving a single indecomposable system on a single node using multiple cores. A dynamic task-dispatching subsystem is developed for distributing systems on nodes in the process of compositional solution. Computational speedups are obtained on a series of test examples, e.g., illustrating that the best value constitutes up to 45 times speedup obtained on 5 nodes with 20 cores each. |

URL | https://ieeexplore.ieee.org/document/8482295 |

DOI | 10.1109/TPDS.2018.2873354 |