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.

Straipsnyje praplečiamos [3] idejos apie uždaviniu, kuriuos galima spresti šeimininkas ‐darbininkai tipo algoritmais, lygiagrečiuju programu konstravima, panaudojant pusiau automatinio programu išlygiagretinimo irankius (Seimininkas ‐ darbininkai (SD) biblioteka). ŠD biblioteka naudotina stambaus ir vidutinio grūdetumo uždaviniams. Ji gali būti taikoma bet kokiam uždaviniui P, kuri galima išskaidyti j užduotis P = U _i ^N=0 ^t i. Efektyviausia ŠD biblioteka taikyti, kai visos užduotys t_i yra nepriklausomos.

Straipsnyje parodoma, kad lygiagretusis algoritmas yra sukuriamas automatiniu būdu, panaudojant ŠD biblioteka, su salyga, kad vartotojo programa tenkina tokius reikalavimus:

1. Pagrindine programa turi sudaryti duomenu inicializavimo, vienos užduoties t_i skaičiavimo ir rezultatu apdorojimo blokai.

2. Vartotojas turi apibrežti pradiniu duomenu, vienos užduoties duomenu ir rezultatu struktūras.

Pertvarkius programa, kad tenkintu šiuos reikalavimus, lygiagrečioji programos versija gaunama kompiliavimo metu. Straipsnyje pristatomos pusiau automatinio išlygiagretinimo idejos, kuriant nepriklausomus programinius sluoksnius/lygius. Pateikiami pirminiu skaičiu radimo ir Mandelbrot aibes skaičiavimo programu pavyzdžiai.

¹The additional testing and debugging may be needed in case the user does not follow the recommendations described in section 2.1