Obliczenie potęgi k znormalizowanej afinicznej relacji

• Autorzy: Bielecki, W. , Klimek, T. , Trifunovic, K.
• Języki publikacji: PL

Abstrakty

PL

W artykule rozważane są idealnie zagnieżdżone pętle afiniczne, w których dolne oraz górne granice pętli, a także odwołania do tablic oraz instrukcji warunkowych są określane przy pomocy funkcji afinicznych, których argumentami są indeksy otaczających pętli oraz opcjonalnie parametry stukturalne.

EN

An approach to calculate the power k of an affine normalized relation is presented. A way to normalize an arbitrary affine relation is discussed. The approach is illustrated by an example. It is clarified how to calculate the positive transitive closure and transitive closure of a relation on the basis of the power k of the relation. Results of experiments are discussed. It is demonstrated how the calculated power k of a relation can be used for extracting both coarse- and fine-grained parallelism available in program loops. Feature, research is outlined.

Słowa kluczowe

PL

relacja afiniczna; zależność; struktura danych; program przekształceniowy; równoległość

EN

affine loops; dependence; transitive closure; program transformation; parallelization

• Czasopismo: Metody Informatyki Stosowanej
• Rocznik: 2008
• Tom: nr 2 (Tom 15)
• Strony: 5-20
• Opis fizyczny: Bibliogr. 27 poz., tab.

Twórcy

autor

Bielecki, W.

autor

Klimek, T.

autor

Trifunovic, K.

• Politechnika Szczecińska, Wydział Informatyki

Bibliografia

• [1] Darte A., Robert Y.. Vivien F. Scheduling and Automatic Parallelization. Birkhauser Boston, 2000
• [2] Pugh W., Wonnacot D. An Exact Method, for Analysis of Value-based Array Data Dependences. Workshop on Languages and Compilers for Parallel Computing. 1993.
• [3] Kelly W.. Pugh W., Rosser E., Shpeisman T. Transitive, clousure of infinite graphs and its applications. Languages and Compilers for Parallel Computing, 1995.
• [4] Feautrier P. Some Efficient Solutions to the Affine Scheduling Problem, Part I. One-Dimensional Time. International Journal of Parallel Programing, Vol 21(5), 1992.
• [5] Feautrier P. Some Efficient Solution to the Affine Scheduling Problem, Part, II. Multi-Dimensional Time. International Journal of Parallel Programing, Vol. 21(6), 1992.
• [6] Kelly W., Maslov V., Pugh W., Rosser E., Shpeisman T., Wonnacott D. The Omega library interface guide. Technical Report CS-TR-3445, Dept. of Computer Science, University of Maryland, College Park, March 1995.
• [7] Wolf M. E., Lam M. S. A Loop Transformation Theory and an Algorithm to Maximize, Parallelism. IEEE Transactions on Parallel and Distributed Systems, Vol. 2(4), 1992.
• [8] Bielecki W., Drążkowski R. Approach to building free schedules for loops with affine dependences represented with a single dependence relation. WSEAS Transactions on Computers, Issue 11, Volume 4, 2005.
• [9] Bielecki W., Siedlecki K. Finding Free Schedules for Non-uniform Loops. Proceedings of the Euro-Par 2003, Lecture Notes in Computer Science, 2003.
• [10] Bielecki W., Siedlecki K. Wyszukiwanie równoległości nie wymagajqcej synchronizacji w pętlach idealnie zagnieżdżonych. X Sesja Naukowa Wydziału Informatyki Politechniki Szczecińskiej, Szczecin 2005.
• [11] Bielecki W., Siedlecki K. Wyszukiwanie poczqtków niezależnych wątków obliczeń w dowolnie zagnieżdżonych pętlach programowych. Metody Informatyki Stosowanej w Technice i Technologii, Szczecin 2004.
• [12] Kelly W., Pugh W. Minimizing communication while preserving parallelism. ACM International Conference on Supercomputing, 1996, s. 52-60 .
• [13] Pugh W., Rosser E. Iteration Space, Slicing and its Application to Communication Optimization. Proceedings of International Conference on Supercomputing, 1997.
• [14] Lim W., Lam M. S. Communication-free parallelization via affine transformations. Proceedings of the seventh workshop on languages and compilers for parallel computting.
• [15] Beletsky V. Finding Synchronization-Free Parallelism for Non-uniform. Loops. Proceedings of the Computational Science - ICCS'2003, Lecture Notes in Computer Science, Springer (2003), v. 2658 s. 925-934.
• [16] Bielecki W., Palkowski M., Siedlecki K. Badania efektywności metod wyszukiwania gruboziarnistej równoległości w pętlach programowych. Materiały X Sesji Naukowej Informatyki 2006.
• [17] Bielecki W., Trifunovic K. Algorytmy zrównoleglenia zagnieżdzonych pętli programowych - stan wiedzy, kierunki badania.. Materiały XI Sesji Naukowej Informatyki 2007.
• [18] Bacon D., Graham S., Sharp O. Compiler transformations for high-performance. computing. Computing Surveys, Vol. 26(4), 1994, s. 345-420.
• [19] Boulet P., Darte A., Silber G.-A., Vivien F. Loop paralellelization algorithms: from parallelism extraction to code generation. Technical Report 97-17, LIP, ENS-Lyon, France, June, 1997.
• [20] Darte A., Robert. Y. Constructive methods for scheduling uniform loop nests. IEEE Transactions on Parallel and Distributed Systems, Vol. 5, No. 8, 1994, s. 814-822.
• [21] Darte A.. Vivien F. On the optimality of Allen and Kennedy's algorithm for parallelism, extraction in nested loops. Journal of Parallel Algorithms and Applications, Special issue on "Optimizing Compilers for Parallel Languages", Vol. 12, 1997, s. 83-112.
• [22| Darte A., Vivien F. Optimal Fine and Medium Grain Parallelism Detection in Polyhedral Reduced Dependence Graphs. International Journal of Parallel Programming, Vol. 25(6), 1997, s. 447-496.
• [23] http: www.maplesoft.com
• [24] http://www.wolfram.com
• [25] http://maxima.sourceforge.net
• [26] http://www.mupad.com
• [27] Bagnara R. et al. The automatic solution of recurrence relations. I. Linear recurrences of finite order with constant coefficients. Quaderno 334, Dipartimento di Matematica, Univcrsitf di Parma, Italy, 2003.