Lygiagrečiųjų algoritmų šablonų tyrimas ir kūrimas

Abstract

Parallel computations are used in many areas where large computation amounts are required and/or faster response is critical. The development of parallel algorithms and parallel programming are complicated and require additional knowledge. To ease the parallel programming and algorithm parallelization many tools are developed. One class of such tools is algorithm templates. The idea of algorithm templates is to separate the problem specific and general parts of the algorithm. The general part can be implemented as a reusable module. The problem specific part of the algorithm should be implemented by the user. When these ideas are used for parallel programming, the template has to specify the main parts of the parallel algorithm: partitioning, communications, mapping, synchronization. Master – slave algorithms are very popular and widely used in parallel programming. It is efficient both for homogeneous and heterogeneous parallel computers. Parallelization tools of master – slave algorithms using popular communication libraries are useful. Many problems of engineering, economics and other fields are formulated as optimization problems. Optimization problems are often complicated and computation intensive. Therefore the creation of automatic parallelization tools of popular branch and bound optimization algorithms is relevant. Grillage type foundations are popular in case of weak grounds. It consists of beams that are supported by piles or reside on other beams. In order to reduce the number of piles preserving the required safety the computation intense optimization is required and parallel calculations are useful. The main aims and tasks of the work are: 1. To extend the functionality of the master – slave algorithm template by including the possibility to use it with different communication libraries. For this purpose the template layer structure is formed and it is adjusted to use PVM and MPI communication libraries. 2. To create the branch and bound algorithm template that would allow: a) to test different variants of sequential branch and bound algorithm, b) automatic parallelization of branch and bound algorithms, c) to test new algorithms based on branch and bound algorithm logic. 3. To use parallel global optimization algorithms for optimization of grillage type foundations.