The template programming of parallel algorithms

Abstract

The parallel programming tools and packages are evolving rapidly. However the complexity of parallel thinking does not allow to implement many algorithms for the end user. In most cases only expert programmers risk to involve in parallel programming and program debugging. [...].

Straipsnyje praplečiamos [3] idėjos apie uždavinių, kuriuos galima spręsti šeimininkas - darbininkai tipo algoritmais, lygiagrečiųjų programų konstravimą, panaudojant pusiau automatinio programų išlygiagretinimo įrankius {Šeimininkas - darbininkai (ŠD) biblioteką). ŠD biblioteka naudotina stambaus ir vidutinio grūdėtumo uždaviniams. Ji gali būti taikoma bet kokiam uždaviniui P, kurį galima išskaidyti į užduotis P=U{i=0}^{N}ti. Efektyviausia ŠD biblioteką taikyti, kai visos užduotys ti yra nepriklausomos. Straipsnyje parodoma, kad lygiagretusis algoritmas yra sukuriamas automatiniu būdu, panaudojant ŠD biblioteką, su sąlyga, kad vartotojo programa tenkina tokius reikalavimus: 1. Pagrindinę programą turi sudaryti duomenų inicializavimo, vienos užduoties ti skaičiavimo ir rezultatų apdorojimo blokai. 2. Vartotojas turi apibrėžti pradinių duomenų, vienos užduoties duomenų ir rezultatų struktūras. Pertvarkius programą, kad tenkintų šiuos reikalavimus, lygiagrečioji programos versija gaunama kompiliavimo metu. Straipsnyje pristatomos pusiau automatinio išlygiagretinimo idėjos, kuriant nepriklausomus programinius sluoksnius/lygius. Pateikiami pirminių skaičių radimo ir Mandelbrot aibės skaičiavimo programų pavyzdžiai.