Share:


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=0ti. The most effective application cases are obtained for the problems where all ti 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 ti 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 = UN=0ti. 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.


First Published Online: 14 Oct 2010

Keyword : -

How to Cite
Baravykaite, M., & Šablinskas, R. (2002). The template programming of parallel algorithms. Mathematical Modelling and Analysis, 7(1), 11-20. https://doi.org/10.3846/13926292.2002.9637173
Published in Issue
Jun 30, 2002
Abstract Views
391
PDF Downloads
305
Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.