Wyniki wyszukiwania - Biblioteka Nauki

1

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

100%

Pałkowski M.

Metody Informatyki Stosowanej

|

2008

|

tom nr 3 (Tom 16)

213--222

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.

2

Automatic Extraction of Parallelism for Mobile Devices

100%

Pałkowski M.

Przegląd Elektrotechniczny

|

2015

|

tom R. 91, nr 11

162-166

EN

This paper presents the Iteration Space Slicing (ISS) framework aimed at automatic parallelization of code for Mobile Internet Devices (MID). ISS algorithms permit us to extract coarse-grained parallelism available in arbitrarily nested parameterized loops. The loops are parallelized and transformed to multi-threaded application for the Android OS. Experimental results are carried out by means of the benchmark suites (UTDSP and NPB) using an ARM quad core processor. Performance benefits and power consumption are studied. Related and future work are discussed.

XX

Artykuł przedstawia ekstrakcję niezależnych fragmentów kodu dla urządzeń przenośnych. Narzędzie pozwala na zrównoleglenie gruboziarniste dowolnie zagnieżdżonych pe˛ tli programowych z parametrami do kodu wielowątkowego dla systemu Android. Eksperymenty przeprowadzono na zestawach pętli testowych (UTDSP i NPB) za pomocą czterordzeniowego procesora ARM. Przedstawiono analizę wydajności i poboru mocy oraz pokrewne rozwiązania.

3

Rozszerzenie biblioteki Omega Calculator do celów zrównoleglania pętli programowych

100%

Pałkowski M.

Metody Informatyki Stosowanej

|

2007

|

tom nr 2(Tom 12)

103-112

PL

W niniejszym artykule przedstawiono zestaw funkcji poszerzających możliwości generowania relacji w pakiecie Omega Calculator. Funkcje umożliwiają dowolne kopiowanie ograniczeń z podmianą zmiennych w zbiorach i relacjach oraz dodawanie specjalnych ograniczeń np. porządku leksykograficznego.

EN

The extended mathematical representation of dependence relations and sets, used in algorithms for automatic parallelization, is presented. The article describes functions and implementation details of computing relations with examples. The project uses of the Omega Calculator library in Pressburger arithmetic operations on relations and sets. The extended library allows easy constructing sets and relations with additional mathematical constraints.

4

Tiling arbitrarily nested loops by means of the transitive closure of dependence graphs

63%

Bielecki W. , Pałkowski M.

International Journal of Applied Mathematics and Computer Science

|

2016

|

tom Vol. 26, no. 4

919--939

EN

A novel approach to generation of tiled code for arbitrarily nested loops is presented. It is derived via a combination of the polyhedral and iteration space slicing frameworks. Instead of program transformations represented by a set of affine functions, one for each statement, it uses the transitive closure of a loop nest dependence graph to carry out corrections of original rectangular tiles so that all dependences of the original loop nest are preserved under the lexicographic order of target tiles. Parallel tiled code can be generated on the basis of valid serial tiled code by means of applying affine transformations or transitive closure using on input an inter-tile dependence graph whose vertices are represented by target tiles while edges connect dependent target tiles. We demonstrate how a relation describing such a graph can be formed. The main merit of the presented approach in comparison with the well-known ones is that it does not require full permutability of loops to generate both serial and parallel tiled codes; this increases the scope of loop nests to be tiled.

5

Prywatyzacja zmiennych skalarnych dla wyznaczania równoległości w pętlach programowych

63%

Pałkowski M. , Bielecki W.

Pomiary Automatyka Kontrola

|

2012

|

tom R. 58, nr 2

180-183

PL

Wynikiem automatycznego zrównoleglenia pętli programowych jest kod tożsamy z sekwencyjnym odpowiednikiem, który honoruje wszystkie zależności. Zastosowanie prywatyzacji określonych zmiennych programu pozwala na wyeliminowanie zależności danych, co zmniejsza złożoność obliczeniową wyznaczania równoległości w pętlach programowych a także pozwala zwiększyć stopień wyznaczanej równoległości. W artykule zaprezentowano zastosowanie technikę prywatyzacji zmiennych operującej na zależnościach zapisanych w postaci relacji. Zbadano stosowalność proponowanego rozwiązania na pętlach programowych z benchmarku NAS.

EN

Extracting synchronization-free slices allows us to automatically generate parallel loops. The code can be executed on multi-processors machines in a reduced period of time. Privatization of data is an important technique used by compilers to parallelize loops by eliminating storage-related dependences. A scalar variable defined within a loop is said to be privatizable with respect to that loop if and only if every path from the beginning of the loop body to a use of X within that body must pass through a definition of X before reaching that use. In this paper there is presented an approach to automatic privatization of variables involved in data dependences that permits for extracting loop parallelism. The algorithm input is a set of relation dependences, the output is a parallel loop when appropriate. The scope of the approach applicability is illustrated by means of the NAS Parallel Benchmark suite. The obtained results are compared with another automatic parallelizer and locality optimizer for multicores - Pluto. The future work is considered.

6

Wpływ redukcji zależności na możliwość obliczenia tranzytywnego domknięcia grafu zależności

63%

Siedlecki K. , Pałkowski M.

Pomiary Automatyka Kontrola

|

2012

|

tom R. 58, nr 2

188-192

PL

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.

EN

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.

7

Wyznaczanie równoległości pętli programowych w aplikacjach dedykowanych dla procesorów graficznych

63%

Bielecki W. , Pałkowski M.

|

tom R. 57, nr 8

963-965

PL

Ekstrakcja równoległości w postaci niezależnych fragmentów kodu pozwala wygenerować równoległe pętle programowe w sposób automatyczny. Kod taki umożliwia wykorzystanie mocy obliczeniowej maszyn równoległych, w tym wieloprocesorowych kart graficznych. W niniejszym artykule poddano analizie zastosowanie algorytmów wyznaczania fragmentów kodu dla aplikacji dedykowanych dla procesorów graficznych. Zbadano przyspieszenie i efektywność obliczeń oraz skalowalność wygenerowanego kodu równoległego.

EN

Extracting synchronization-free slices allows automatically generating parallel loops. The code can be executed on multi-processors machines in a reduced period of time. Slicing techniques enable also generating parallel code for graphics processing in general purpose computing. Nowadays, graphic cards support executing multi-threaded applications. GPU systems consist of tens or hundreds of processors. CUDA (an acronym for Compute Unified Device Architecture) is a parallel computing architecture developed by NVIDIA. Graphics processing units (GPUs) are accessible to software developers through variants of industry standard programming languages. Using CUDA, the latest NVIDIA GPUs become accessible for computation like CPUs. The model for GPU computing is to use a CPU and GPU together in a heterogeneous co-processing computing model. The sequential part of the application runs on the CPU and the computationally-intensive part is accelerated by the GPU. From the user's perspective, the application just runs faster because it uses the high-performance of the GPU to boost performance. In this paper slicing algorithms are examined for generating a parallel code for graphic cards are examined. A short example of the code is presented. CUDA statements and technique are explained. Memory cost and transfer data is considered. Speed-up, efficiency and scalability of the code are analyzed.

8

Wyznaczenie punktów reprezentatywnych niezależnych fragmentów kodu w grafie zależności pętli programowych

51%

Bielecki W. , Pałkowski M. , Klimek T.

Metody Informatyki Stosowanej

|

2010

|

tom nr 1 (22)

13-20

PL

W artykule przedstawiono nowy algorytm wyznaczania punktów reprezentatywnych cechujacy się mniejszą złożonością obliczeń w porównaniu do rozwiazania [6-7]. Powodzenie wyznaczania punktów jest zależne tylko od obliczenia dokładnego tranzytywnego domknięcia unii relacji zależności pętli. Oprócz tego należy wykonać szereg podstawowych operacji, jak: część wspólna, iloczyn skalarny, unia, aplikacja relacji na zbiorze, inwersja, projekcja. Relacja RUSC budowana jest wieloetapowo dzięki czemu można dokonywać pośrednich uproszczeń jej postaci. Opisane podejście zostało zaimplementowane i przetestowane pod kątem skuteczności na zbiorze pętli testowych NAS. W dalszych badaniach planowane jest zbadanie proponowanego algorytmu z innymi zbiorami pętli testowych oraz dalsze udoskonalanie algorytmów do wyznaczania fragmentów dla dowolnej topologii zależności pod kątem generowania wydajnego kodu równoległego.

EN

An algorithm of finding representatives of synchronization-free slices available in program loops is presented. It based on the transitive closure of a union of dependence relations describing all the dependences in program loops. An algorithm to calculate transitive closure is studied. Both the algorithms are implemented by means of the Omega library. The results of experiments with the NAS Parallel Benchmark are discussed.