Synchronous algorithm for parallel reconstruction of three-dimensional images based on the MPI system
Authors: Золотарев С.А. , Венгринович В.Л. , Смагин С.И. 
Published: October 2021

Одни из наиболее важных вычислительных задач разработка и адаптация итерационных методов для решения сверхбольших разреженных систем алгебраических уравнений. К таким вычислительным задачам приводит задача итерационной параллельной реконструкции трехмерных изображений промышленных изделий. Важно, что итерационные методы решения вычислительных задач большой размерности реализуются на параллельных структурах намного эффективнее, чем прямые методы их решения. В этой работе описан синхронный параллельный алгоритм, основанный на использовании системы MPI для решения задачи реконструкции трехмерных изображений промышленных изделий.

Purpose. Currently, one of the most important tasks is the development and adaptation of iterative methods for solving ultra-large sparse systems of algebraic equations. Such computational problems are caused by the iterative parallel reconstruction of three-dimensional images of industrial products. It is important that iterative methods for solving computational problems of large size are implemented on parallel structures much more efficiently than direct methods for solving them. This paper describes a synchronous parallel algorithm based on the MPI system for solving the problem of reconstruction of three-dimensional images of industrial products. Methodology. It is important that iterative methods for solving computational problems of larger dimensionality on parallel structures are implemented more efficiently than the direct ones. Most algorithms based on direct solving methods have a significant hereditary sequential structure and require a large number of processors interactions which cannot be executed in parallel mode. Iterative methods, for the most part, require a significantly smaller number of interactions of this type and are relatively easily mapped onto parallel computational structures. Equally important, in most cases parallel implementations of classical iterative methods are more effective in terms of computational speed. The parallel execution of the algorithm is based on the distribution of the process in some way between various groups of processors. Depending on the interaction method between local processors, two different types of parallel iterative algorithms execution are distinguished: synchronous and asynchronous. In the former case, it is assumed that the processors complete the calculations and exchange all the necessary results before the start of a new iteration. The main disadvantage of synchronous parallel algorithms is that they require synchronization of iterations. This is a very difficult task, especially with large number of processors. In addition, the overall calculation speed is limited by the speed of the slowest processor. At the same time, faster processors spend most of their time in the waiting mode. But, nevertheless, the implementation of these parallel algorithms can be effectively achieved using the MPI standard. Findings. Synchronous parallel computing algorithms and program codes for threedimensional tomographic reconstruction in a conical beam were developed. Program code debugging and numerical calculations were performed on a hybrid cluster based on the OpenPOWER architecture using the MPI system. For designing a parallel threedimensional tomographic reconstruction, a voxel form of parallelism was used. Originality. Implemented parallel iterative technology of three-dimensional images reconstruction has undeniable advantages over traditional sequential iterative tomographic reconstruction. It allows reducing the time of tomographic reconstruction as many as tens of times, provides the ability to reconstruct products with sizes of 5123 to 10243 voxels with simultaneous storage of the submatrix node of the projection matrix in RAM, which eliminates the need for recalculation of matrix coefficients for each new iteration.