stributed Computing: DAP-Technology for Parallelizing Recursive Algorithms
Gennadi Malaschonok, Alla Sidko · NaUKMA Research Papers Computer Science · 2018
This article addresses the description of a new technology of dynamic parallelization of recursive algorithms on distributed memory. The main impetus for its creation was the discovery of a large class of matrix recursive algorithms in recent decades. All of them, including the Strassen algorithms, are the development of the ideas of Karatsuba’s well-known works on the rapid multiplication of numbers and polynomials. The main objects of the new parallelization technology are drop, amine, and pine. The algorithm graph is divided into compact subgraphs (drops) which can be transferred to other processors for calculation. To calculate the drop, the algorithm is unfolded and the corresponding data structure (amine) is constructed. To save all the amines and their states, a list (pine) is created in each processor. During the calculations, until the calculation of a particular amine is completed, this amine is retained on the pine. After completing the calculations, all the memory allocated for the amine is released.Another feature of ADP-technology is the mechanism of distribution of drop-orders by processors. To manage the process of job allocation, we use a list of available drop jobs, with the depth of nesting for each job. We also use the list of child processors with information about all sent tasks, as well as a list of free processors. This list of child processors is updated each time the job is sent and when the results of the calculations are received. The list of free processors is divided equally among all the processors that receive the task with the lowest depth of nesting.To manage calculations and data exchange operations, two threads are created. The first will provide calculations and sending out the results of calculations, and the second will take care of all the management and of all the data exchange. The control thread is the master; it controls all the ports and states and falls asleep to allow the second thread to perform calculations.In addition, there is a mechanism for releasing the processor. If the processor does not have drop jobs, it adds itself to the list of free processors and forwards this list to the ᬛrst parent processor. Such a processor can receive a new drop-task, and it can also get the result from the child processor and continue the calculations in accordance with the tasks of the active amine.To explain the new parallelization technology, we provide examples of the construction of drop tasks for the inversion algorithm of the triangular matrix and for the matrix multiplication algorithm.