Równoległe przetwarzanie nieregularnych zagnieżdżonych pętli programowych

• Autorzy: Sosnówka A.
• Języki publikacji: PL

Abstrakty

EN

There are a bench of methods which are allowing full or part parallelization of nested loops with uniform dependencies, however very small amount of those which are dealing with nonuniform, irregular loops computation . This paper presents a set of techniques used and examples of recognised problems when approaching parallelization of nested loops with nonuniform dependencies. The approach is to find a solution to one of or all of them in order to be able to perform computation of those loops.

Słowa kluczowe

PL

przetwarzanie równoległe; zagnieżdżone pętle programowe; stosunek zależności; niejednolitość pętli

EN

parallel computing; dependence relation; relation simplification; nested loop partitioning; non-uniform loops

• Wydawca: Komisja Informatyki Polskiej Akademii Nauk, Oddział w Gdańsku
• Czasopismo: Metody Informatyki Stosowanej
• Rocznik: 2009
• Tom: nr 3 (20)
• Strony: 195--202
• Opis fizyczny: Bibliogr. 13 poz., rys.

Twórcy

autor

Sosnówka A.

• Zachodniopomorski Uniwersytet Technologiczny w Szczecinie, Wydział Informatyki

Bibliografia

• [1] Ju J., Chaudhary V. Unique Sets Oriented Parallelization of Loops with Non-uniform Dependences. Wayne State University, Detroit, 1997
• [2] Pałkowski M. Upraszczanie afinicznych relacji i zbiorów w celu podniesienia wydajności generowanego kodu równoległego, Politechnika Szczecińska, Wydział Informatyki, Szczecin, 2008
• [3] Unger S., Mueller F. Handling Irreducible Loops: Optimized Node Splitting, Institut für Informatik, Berlin, 2000
• [4] Zaafrani A., Ito M. Parallel region execution of loops with irregular dependencies, Proceeding of International Conference on Parallel Processing, II, 11-19, 1994
• [5] Pugh W., Wonnacott D. Statit analysis of upper and lower bounds on dependences and parallelism, ACM Transactions on Programming Lanuguages and Systems, 16, 1248-1278, 1994
• [6] Kelly W., Pugh W., Rosser E., Shpeisman T. Transitive Closure of Infinite Graphs and its Applications, Department of Computer Science University of Maryland
• [7] Bielecki W., Drążkowski R. Finding Free Schedules for Perfectly Nested Loops with Parameterized Affine Dependences, Politechnika Szczecińska, Wydział Informatyki, Szczecin
• [8] Yu Y., D’Hollander E. H. Partitioning Loops with Variable Dependence Distances, Department of Electronics and Information Systems University of Ghent, Belgium
• [9] Tzen Y. H., Ni L. M. Dependence uniformization: A loop paralelization technique. IEEE Transactions on Parallel and Distributed Systems, 4, 547-558, 1993
• [10] Punyamurtula S., Chaudhary V., Ju J., Roy S. Compile time partitioning of nested loop iteration spaces with non-uniform dependences. Journal of Parallel Algorithms and Applications (special issue on Optimising Compilers for Parallel Languages), 1996
• [11] Chen D, Yew P. On effective execution of non-uniform doacross loops. IEEE Transactions on Parallel and Distributed Systems, 7, 463-476, 1996
• [12] Chen Z., Shang W. On uniformizaton of affine dependence algorithms, Proceeding of the Fourth IEEE Symposium on Parallel and Distributed Systems, 40, 723-742, 1992
• [13] Tseng S., King C., Tang C. Minimum dependence vector set: a new compiler technique for enhancing loop parallelism. Proceeding of 1992 International Conference on Parallel and Distributed Systems, 340-346