Lygiagrečiųjų algoritmų šablonų tyrimas ir kūrimas
Barauskas, Rimantas | Disertacijos gynimo komisijos narys / Dissertation Defense Board Member |
Mockus, Jonas | Disertacijos gynimo komisijos narys / Dissertation Defense Board Member |
Baronas, Romas | Disertacijos gynimo komisijos narys / Dissertation Defense Board Member |
Dzemyda, Gintatutas | Disertacijos gynimo komisijos pirmininkas / Dissertation Defence Board Chairman |
Baušys, Romualdas | Disertacijos gynimo komisijos narys / Dissertation Defense Board Member |
Daugelyje mokslo sričių susiduriama su uždaviniais, kuriuos išspręsti esamais kompiuteriais užtruktų nepriimtinai ilgai arba neįmanoma dėl tų uždavinių dydžio ir skaičiavimų apimties. Lygiagrečiaisiais skaičiavimais siekiame spręsti uždavinius greičiau, arba spręsti didesnius uždavinius. Tačiau tiek lygiagrečiųjų algoritmų sudarymas, tiek jų programinis realizavimas yra sudėtingi procesai, reikalaujantys daug žinių ir įgūdžių. Taupant laiką ir pastangas, yra kuriami lygiagretinimo įrankiai, lengvinantys įvairių lygiagrečiųjų programų ar metodikų naudojimą. Šeimininkas – darbininkai algoritmai yra dažnai naudojami ir paplitę įvairiose lygiagrečiųjų skaičiavimų srityse. Lygiagrečiųjų ���eimininkas – darbininkai algoritmų programų kūrimo automatizavimas palengvina daugelio uždavinių sprendimą. Šeimininkas – darbininkai algoritmas efektyvus vykdant tiek homogeniniuose, tiek heterogeniniuose lygiagrečiuosiuose kompiuteriuose. Duomenims tarp procesorių perduoti naudojamos duomenų perdavimo bibliotekos sparčiai vystomos. Nemažai anksčiau kurtų lygiagretinimo įrankių naudoja PVM duomenų perdavimo biblioteką. Išpopuliarėjus MPI duomenų perdavimo bibliotekai aktualu pritaikyti įrankius jos naudojimui. Daug praktinių uždavinių gali būti formuluojami kaip optimizavimo uždaviniai. Daugelis optimizavimo uždavinių sudėtingi ir reikalaujantys daug skaičiavimų. Šakų ir rėžių algoritmo principai taikomi kuriant tikslius ir euristinius algoritmus optimizavimo uždavinių sprendimui. Optimizavimo algoritmų lygiagretinimas yra sudėtingas uždavinys. Aktualu ruošti įrankius tiek lengvinančius optimizavimo algoritmų taikymą įvairiems uždaviniams, tiek algoritmų lygiagretinimui, tiek naujų algoritmų kūrimui ir testavimui.
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.