Identyfikatory
Warianty tytułu
Impact of reducing dependence on possibility of calculating transitive closure of dependency graph
Języki publikacji
Abstrakty
W artykule zaprezentowano wpływ redukcji zależności na możliwość obliczenia tranzytywnego domknięcia grafu zależności. Redukcje zależności wykonano przy pomocy znanych technik (redukcja zmiennych skalarnych i indukcyjnych, przekoszenie pętli, podział i łączenie pętli, rozszerzenie zmiennych skalarnych). Przedstawiono problemy związane z obliczeniem tranzytywnego domknięcia grafu zależności. Dla zbioru pętli testowych z benchmarku NAS przedstawiono wyniki statystyczne z przeprowadzonych badań. Dla wybranej pętli zaprezentowano wykorzystanie metod redukcji zależności, ich wpływ na liczbę relacji zależności oraz na możliwość obliczenia tranzytywnego domknięcia grafu zależności.
The paper presents the impact of reducing dependence on possibility of calculating the transitive closure. The reductions were made according to the well known techniques (scalar reduction, induction variable elimination, loop skewing, loop splitting, loop fissioning, scalar expansion). The publication presents the background associated with data dependencies. In addition, reduction techniques (with simple examples) used in the experiments are presented. The problems associated with the transitive closure calculation are discussed. There are given the statistic results of experimental studies on a set of benchmark loop. For a chosen loop from NAS Parallel Benchmark the effectiveness of each reduction technique is shown. The impact of reduction on the transitive closure calculation is described for a selected example, where the impact of each reduction technique on the number or dependency relations is presented in detail. In the last section the experimental observations are summarized and the importance of reducing dependence is explained.
Wydawca
Czasopismo
Rocznik
Tom
Strony
188--192
Opis fizyczny
Bibliogr. 13 poz., tab., wzory
Twórcy
autor
autor
- Katedra Inżynierii Oprogramowania, Wydział Informatyki, Zachodniopomorski Uniwersytet Technologiczny, ul. Żołnierska 49, 71-210 Szczecin, ksiedlecki@wi.zut.edu.pl
Bibliografia
- [1] Beletska A., Bielecki W., Cohen A., Palkowski M., Siedlecki K.: Coarse-grained loop parallelization: Iteration Space Slicing vs affine transformations, Parallel Computing 37, s. 479-497, 2011.
- [2] Bielecki W. Palkowski M.: Extracting both affine and non-linear synchronization-free slices in program loops, Lecture Notes in Computer Science, Volume 6067/2010, 196-205, 2010.
- [3] Kelly W., Pugh W., Rosser E., Shpeisman T.: Transitive Closure of Infinite Graphs and its Applications, International Journal of Parallel Programming, 1996.
- [4] Nuutila E.: Efficient Transitive Closure Computation in Large Digraphs, Mathematics and Computing in Engineering Series No. 74 PhD thesis Helsinki University ofTechnology. Helsinki 1995.
- [5] Verdoolaege S.: Integer Set Library - Manual, www.kotnet.org/ ~skimo//isl/manual.pdf, 2010.
- [6] Beletska A., Barthou D., Bielecki W., Cohen A.: Computing the Transitive Closure of a Union of A?ne Tuple Relations. In Proc. of the Third Annual Conference on Combinatorial Optimization and Applications (COCOA’2009), s. 98-109, LNCS 5573, 2009.
- [7] Bielecki W., Klimek T., Palkowski M., Beletska A.: An Iterative Algorithm of Computing The Transitive Closure of A Union of Parameterized Affine Integer Tuple Relations, Lecture Notes in Computer Science, 2010, Volume 6508, Combinatorial Optimization and Applications, s. 104-113.
- [8] Kelly W., Maslov V., Pugh W., Rosser E., Shpeisman T., Wonnacott D.: The omega library interface guide, University of Maryland, Technical Report CS-TR-3445, 1995, http://www.cs.umd.edu/projects/ omega/
- [9] NAS Parallel Benchmarks v.3.2, 2010, http://www.nas.nasa.gov/Resources/Software/npb.html
- [10] Bielecki W., Siedlecki K.: Finding Sources of Synchronization-free Slices in Perfectly Nested Loops, ELECTRONIC MODELING, vol. 29, No. 3, Kijów 2007, ss. 41-53,
- [11] Bielecki W., Siedlecki K.: Extracting Synchronization-free Slices in Perfectly Nested loops, ELECTRONIC MODELING, vol. 29, No. 6, Kijów 2007, ss. 61-76.
- [12] Chen C.: Omega+ Presburger Engine & CodeGen+ Z-Polyhedra Scanning, wersja 2.2.1, http://chunchen.info/omega/, 2011.
- [13] The OpenMP® API specification for parallel programming, http://openmp.org/
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BSW4-0117-0008