Upraszczanie afinicznych relacji i zbiorów w celu podniesienia wydajności generowanego kodu równoległego

• Autorzy: Pałkowski M.
• Języki publikacji: PL

Abstrakty

EN

A representation of relations and sets determines the amount of instructions and the form of loops in generated parallel code with using the Omega Calculator [1,2]. An unsimplified set of iterations may cause unnecessary instructions in parallel code and longer time of code execution. Algorithms of the simplification of relations and sets by means of the operation are presented. Under experiments, code of generated loops along with execution time is examined. The algorithms can be used also to reduce amount of one-conjunct relations and sets.

Słowa kluczowe

EN

dependence relation; mathematical representation of relations and sets; Presburger; arithmetic; parallel computing; hull; relation simplification

• Wydawca: Komisja Informatyki Polskiej Akademii Nauk, Oddział w Gdańsku
• Czasopismo: Metody Informatyki Stosowanej
• Rocznik: 2008
• Tom: nr 3 (Tom 16)
• Strony: 213--222
• Opis fizyczny: Bibliogr. 13 poz., rys., tab.

Twórcy

autor

Pałkowski M.

• Politechnika Szczecińska, Wydział Informatyki

Bibliografia

• [1] Pugh W., Wonnacott D. An exact method for analysis of value-based array data dependences. Workshop on Languages and Compilers for Parallel Computing, 1993.
• [2] Kelly W., Maslov V., Pugh W., Rosser E., Shpeisman T., Wonnacott D. The omega library interface guide. Technical Report CS-TR-3445, University of Maryland, 1995.
• [3] Bielecki W., Beletska A., Pałkowski M., San Pietro P. Extracting synchronizationfree chains of dependent iterations in non-uniform loops, ACS 2007, 14th International Multi-Conference.
• [4] Bielecki W., Pałkowski M., Siedlecki K. Badania efektywności metod wyszukiwania gruboziarnistej równoległości w pętlach programowych. X Sesja Naukowa Wydziału Informatyki Politechniki Szczecińskiej, 213-228, Szczecin 2005.
• [5] Kelly W., Pugh W., Rosser E., Shpeisman T. Transitive Closure of Infinite Graphs and its Applications. International Journal of Parallel Programming, 1996, v. 24, n. 6, s. 579-598.
• [6] Pugh W., Rosser E. Iteration Space Slicing and Its Application to Communication Optimization, in: Proceedings of the International Conference on Supercomputing, 1997, s. 221-228.
• [7] Bielecki W., Siedlecki K. Wyszukiwanie równoległości nie wymagającej synchronizacji w pętlach idealnie zagnieŜdŜonych. X Sesja Naukowa Wydzialu Informatyki Politechniki Szczecińskiej, s. 193-212, Szczecin 2005.
• [8] Bielecki W., Siedlecki K. Wyszukiwanie początków niezaleŜnych wątków obliczeń w dowolnie zagnieŜdŜonych pętlach programowych. Metody informatyki stosowanej w technice i technologii, s. 199-206, Szczecin 2004.
• [9] Bielecki W., Siedlecki K. Finding Free Schedules for Non-uniform Loops, In Proceedings of the Euro-Par 2003, Lecture Notes in Computer Science, Springer, pp. 297-302, 2003.
• [10] Kelly W., Pugh W., Rosser E., Shpeisman T. Transitive Closure of Infinite Graphs and its Applications, International Journal of Parallel Programming, 1996, v. 24, n. 6, s. 579-598.
• [11] Foster I. Designing and Building Paralel Programs. Addison Wesley, 1994.
• [12] Dokumentacja pakietu Mathematica, http://mathworld.wolfram.com/ConvexHull.html
• [13] Bielecki W., Pałkowski M. Extracting coarse-grained parallelism in computer simulation applications, ACS 2006, 13th International Multi-Conference, Vol. II, 237-246, Szczecin 2006