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. In this paper we extend the ideas from [3] of template programming for a certain class of problems which could be solved by using general master‐slave paradigm. The template is suitable for solution of the coarse grain and middle grain granularity problem set. Actually, it could be applied to solve any problem P, which is decomposable into a set of tasks P = U _i ^N=0^ti. The most effective application cases are obtained for the problems where all t_i are independent. The template programming sets some requirements for the sequential version of the user program: 
1) The main program must comprise of several code blocks: data initialization, computation of one task t_i and the processing of the result;
2) The user has to define the data structures: initial data, one task data, the result data. These requirements do not require to rewrite the existing sequential code but to organize it into some logical parts. After these requirements (and naming conventions) are fulfilled, the parallel version of the code is obtained automatically by compiling and linking the code with the Master‐Slave Template library. 
In this paper we introduce the idea of the template programming and describe the layer structure of the Master‐Slave Template library. We show how the user has to adjust the sequential code to obtain a valid parallel version of the initial program. We also give examples of the prime number search problem and the Mandelbrot set calculation problem.

Programų išlygiagretinimas, panaudojant programinius šablonus

Santrauka. 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 (Seimininkas‐darbininkai (SD) biblioteka). ŠD biblioteka naudotina stambaus ir vidutinio grūdėtumo uždaviniams. Ji gali būti taikoma bet kokiam uždaviniui P, kuri galima išskaidyti į užduotis P = U_i ^N=0^ti. Efektyviausia ŠD biblioteką taikyti, kai visos užduotys t_i 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 t_i 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.

First Published Online: 14 Oct 2010

Keyword : -