Solving Linear Diophantine Systems on Parallel Architectures
Solving Linear Diophantine Systems on Parallel Architectures
复制标题
在并行架构上求解线性丢番图系统
DOI：
10.1109/tpds.2018.2873354
复制
发表时间：
2019
影响因子：
5.3
通讯作者：
J. Dongarra
中科院分区：
文献类型：
--
作者：
D. Zaitsev;S. Tomov;J. Dongarra
求解线性丢番图方程组应用于离散事件系统、模型检查、形式语言和自动机、逻辑编程、密码学、网络、信号处理和化学。为了使用 Petri 网对离散系统进行建模，需要非负整数的解，这是一个棘手的问题。因此，以显着的加速解决此类任务受到高度赞赏。在本文中，我们基于系统族的并行顺序组合设计了一种新的线性丢番图系统求解器。使用基于 MPI 和 OpenMP 的两级并行化概念，研究并实现了该求解器，使其能够在并行架构上运行。可分解系统通常用稀疏矩阵表示；分解的最小部落规模限制了技术的颗粒化。 MPI 用于在分布式内存计算节点上使用并行顺序组合来解决部落系统，而 OpenMP 用于使用多个核心在单个节点上解决单个不可分解系统。开发了一个动态任务调度子系统，用于在组合求解过程中将系统分布在节点上。计算加速是在一系列测试示例中获得的，例如，说明最佳值构成了在 5 个节点（每个节点有 20 个核心）上获得的高达 45 倍的加速。
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.