Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 12

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
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.
EN
Tiling(blocking) is a very important iteration reordering transformation for both improving data locality and extracting loop nest parallelism. Affine transformations are one of the most power approach to generate tiled code. Tile dimensionality has a strong impact on tiled code performance. This paper presents a way allowing one to discover before tiling what is the maximal dimensionality of tiles in code generated by means of affine transformations.
XX
Blokowanie jest bardzo ważną transformacja reorganizacji iteracji zarówno dla poprawy lokalności pętli jak i dla ekstrakcji równoległości w gniezdzie pętli programowej. Przekształcenia afiniczne są jednym z najbardziej mocnych podejść do implementacji techniki blokowania. W artykule przedstawiono sposób, za pomocą którego można odkryć przed zastosowaniem blokowania jaki jest maksymalny wymiar bloków w kodzie generowanym za pomocą przekształceń afinicznych, który ma silny wpływ na wydajność kodu.
3
Content available remote Automatic Extraction of Parallelism for Mobile Devices
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.
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.
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.
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.
EN
A technique for extracting coarse-grained parallelism available in loops is presented. It is based on splitting a set of dependence relations into two sets. The first one is to be used for generating code scanning slices while the second one permits us to insert send and receive functions to synchronize the slices execution. The paper presents a way demonstrating how to remove redundant synchronization in generated code by means of the transitive reduction operation. Results of experiments - how many synchronization points can be removed, speed-up and efficiency of examined parallel loops are discussed.
PL
W artykule zaprezentowano technikę ekstrakcji równoległości grubo-ziarnistej w pętlach programowych. Bazuje ona na podziale relacji zależności na dwa zbiory: na podstawie pierwszego generowany jest kod skanujący niezależne fragmenty, natomiast drugi służy do wstawienia funkcji send i receive (wyślij i odbierz) służących do synchronizacji tych fragmentów. Operacje te zrealizowano za pomocą semaforów, możliwe jest jednak wykorzystanie innej konstrukcji, bardziej wydajnej dla danego środowiska. Algorytm generuje kod z zaznaczonymi punktami synchronizacji, nie narzuca jednak ich implementacji. W artykule przeanalizowano technikę wyszukiwania i eliminacji zbędnych punktów synchronizacji. Ekstrakcja równoległości za pomocą fragmentów kodu bazuje na operacji tranzytywnego domknięcia, znanej także z teorii grafów. Operacja ta jest również wykorzystana do obliczenia tranzytywnej redukcji, za pomocą której eliminowana jest nadmiarowa synchronizacja. Usuwanie zbędnej komunikacji pomiędzy wątkami obliczeń jest istotne, ponieważ ich obsługa zwłaszcza dla komputerów z pamięcią dzieloną, w których ich koszt obsługi jest istotny. Docelowe jest zatem uzyskanie gruboziarnistego kodu równoległego. Zbadano także wyniki przeprowa-dzonych eksperymentów pod kątem przyspieszenia i efektywności obliczeń.
PL
W artykule przedstawiono technikę automatycznego zrównoleglenia kodu aplikacji w celu efektywnego wykorzystania mocy obliczeniowej procesorów wielordzeniowych w systemach wbudowanych. Technika ta opiera się na analizie zależności danych w pętlach programowych, podziału ich przestrzeni iteracji i wyznaczeniu niezależnych fragmentów kodu. Rezultatem transformacji jest równoległy kod zgodny ze standardem OpenMP, tożsamy z jego sekwencyjnym odpowiednikiem oraz możliwość przyspieszenia obliczeń komputera przemysłowego.
EN
In a fairly conservative group of solutions, such as industrial computers, more perfect miniaturization of processing units is becoming noticeable. Size and power consumption of units are important, however efficiency of processing is also significant. Installing multi-core processors in embedded systems allows executing the parallel code with OpenMP standard. Multi-core programming enables speeding up calculations, i.e. for test and measurement-processing systems the amount of measurement data processed is increased. For this purpose, techniques of transforming program code to a parallel form are necessary, in particular loop parallelization transformations are significant, because the vast majority of calculations is included in loops. There are many techniques for loop prallelization, such as unimodular and affine transformations. However, these techniques allow only extraction of parallelism for specified set of loops and fail to find full parallelism in a loop because of high inability. In this paper, the Iteration Space Slicing Framework is presented. The framework was designed for automatic extracting parallelism in loops and overcoming limitations of well-known techniques. The result of transformation is the parallel code including OpenMP pragmas. The speedup, efficiency and locality of the code is examined. The continuation of the work in the future is considered.
PL
Prezentowane wyniki badań wskazują na zbliżoną skuteczność obu bibliotek w implementacji algorytmów ekstrakcji niezależnych fragmentów kodu. Dla badanego zestawu pętli testowych operacje tranzytywnego domknięcia unii relacji zależności oraz ekstrakcji punktów reprezentatywnych fragmentów kodu zostały policzone dla podobnych zbiorów pętli z zestawu testowego NAS. Biblioteka Omega Calculator wydaje się być projektem bardziej kompletnym, oprócz funkcji do przeprowadzania obliczeń z zakresu arytmetyki Presburgera, zawiera także analizator zależności Petit oraz funkcje generującą kod na podstawie zbioru krotek. Biblioteka ISL nie zawiera własnego analizatora zależności. Wprowadzenie do niej relacji zależności wymaga opracowania dodatkowych konwerterów. Do generowania kodu także należy wykorzystać inne narzędzia, np. Cloog [6]. Zaletami biblioteki ISL jest ciągły rozwój i częste aktualizacje oraz zgodność z najnowszymi wersjami kompilatora języka C. Wpływa to na szybkość wykonywania algorytmów (potwierdzonych w powyższych badaniach), co jest głównym plusem tego narzędzia w przeprowadzonym porównaniu. Algorytmy wyznaczania niezależnych fragmentów kodu nie narzucają zastosowania konkretnego środowiska i narzędzi, co świadczy także o ich uniwersalności. Wymagana jest dokładna reprezentacja zależności w postaci relacji oraz zdolność do przeprowadzania operacji arytmetyki Presburgera na nich. Umiejętna implementacja i dobór narzędzi stanowi o praktycznej użyteczności opracowywanych algorytmów do ekstrakcji równoległości. W przyszłych badaniach zamierzona jest dalsza weryfikacja możliwości omawianych narzędzi z wykorzystaniem innych zestawów pętli testowych.
EN
Finding synchronization-free slices is a technique of extracting parallelism available in loops. In this paper, two implementations of slicing algorithms are compared using the two polyhedral model libraries: the Omega Calculator and the Integer Set Library (ISL). These tools allow us to execute calculations using Presburger arithmetic. Results of experiments with the NASA Parallel Benchmark Suite are presented. The goal of experiments was to examine whether these both tools are able to calculate the transitive closure of a union of dependence relations, slice representatives, and synchronization-free slices.
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.
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.
12
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.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.