Search

Search Results

• CONVERSION OF THE SEQUENTIAL INFORMATION GRAPH OF THE THOMAS ALGORITHM INTO A PARALLEL FORM

  D. V. Mikhailov

  177-188

  2021-10-05

  Abstract ▼

  Many computational tasks can be represented in the form of a sequential information graph. In the general case, such an information graph cannot be reduced to a parallel form in order to speed up the execution of its operations. But if the vertices of this graph have the properties of associativity, distributivity, etc., such a graph can be transformed into a parallel-pipeline form. These transformations can be performed not only on graphs containing elementary operations - addition, multiplication, logical AND, etc. - but also over graphs containing macro operations. One example of such graphs is the information graph for solving SLAEs by the sweep method (Thomas's method). The article considers a solution for tridiagonal linear systems. The infor-mation graph of the sweep method consists of two parts: the forward move, in which the transition from the three-diagonal form to the two-diagonal form is performed, and the reverse move, in which the values of the variables are directly calculated. Despite the fact that the operations that make up the basic macro-operation of the sweep method have the property of associativity, a sim-ple transformation of the graph to a pyramidal form will not give the desired result. It is necessary to transform the basic macro operations in a special way and change what data is received on them. After that, it will be possible to bring the graph to a pyramidal form. For the reverse move, a similar transformation of the graph and its constituent base subgraphs is applied. Since in order to start computations in the reverse run, we need to complete the computations of the forward run, we should switch from two specialized types of computational blocks to one universal one, and build a universal computational structure on its basis.