PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 36

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

help Ogranicz wyniki do:
first rewind previous Strona / 2 next fast forward last
1
Content available Dynamic tile free scheduling for code with acyclic inter-tile dependence graphs
Bielecki W., Skotnicki P.
Computer Science
|
2017
|
Vol. 18 (2)
195--216
EN
Free scheduling is a task ordering technique under which instructions are executed as soon as their operands become available. Coarsening the grain of computations under the free schedule, by means of using groups of loop nest statement instances (tiles) in place of single statement instances, increases the locality of data accesses and reduces the number of synchronization events, and as a consequence improves program performance. The paper presents an approach for code generation that allows for the free schedule for tiles of arbitrarily nested affine loops at run-time. The scope of the applicability of the introduced algorithms is limited to tiled loop nests whose inter-tile dependence graphs are cycle-free. The approach is based on the polyhedral model. Results of experiments with the PolyBench benchmark suite, demonstrating significant tiled code speed-up, are discussed.
2
Content available Tiling arbitrarily nested loops by means of the transitive closure of dependence graphs
Bielecki W., Pałkowski M.
International Journal of Applied Mathematics and Computer Science
|
2016
|
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.
3
Content available Statistical models to accelerate software development by means of iterative compilation
Kamińska A., Bielecki W.
Computer Science
|
2016
|
Vol. 17 (3)
407--435
EN
Minimization of data-processing time and reduction of software-development time are important practical problems to be tackled by modern computer science. This paper presents the authors’ proposal of a family of statistical models for the estimation of program execution time, which is an approach focused on both of the above problems at the same time. The family consists of a general model and specific models and has been elaborated based on empirical data collected for pattern-program loops representing some arbitrarily selected features related to the program structure and the specificity of a program-execution environment. The paper presents steps to elaborate the aforementioned family as well as the results of the carried-out experimental research. The paper demonstrates how the elaborated models can be applied in iterative compilation for optimization purposes, allowing us to reduce the time of software development and produce code with minimal execution time.
4
Content available remote Statistical models for the estimation of execution time of coarsegrained OpenMP programs
Kamińska A., Bielecki W.
Przegląd Elektrotechniczny
|
2015
|
R. 91, nr 2
22-26
EN
This paper presents a family of statistical models for the estimation of program execution time. The paper discusses the possibilities of how to apply the family to reduce iterative compilation duration and in consequence, software development duration. The discussion is supported with the results of experimental research carried out for program loops selected from the NAS Parallel Benchmarks test suite.
PL
W artykule przedstawiono autorską koncepcję rodziny modeli statystycznych do oszacowania czasu wykonania programu oraz omówiono możliwości wykorzystania jej w celu skrócenia czasu wykonywania kompilacji iteracyjnej (a w konsekwencji czasu wytwarzania oprogramowania). Przedstawiono także wyniki przeprowadzonych badań eksperymentalnych.
5
Content available remote On the maximal dimensionality of tiles in tiled code generated by means of Affine Transformations
Bielecki W., Pałkowski M.
Przegląd Elektrotechniczny
|
2015
|
R. 91, nr 11
158-161
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.
6
Content available remote Concurrent Start Tiling of Stencil Computations based on the Transitive Closure of a Data Dependence Graph
Bielecki W., Skotnicki P.
Przegląd Elektrotechniczny
|
2015
|
R. 91, nr 11
167-170
EN
Stencil computations stand at the core of a wide range of scientific and engineering solutions. Load-balanced execution of stencil kernels, allowing for full utilization of processing units from the very beginning, is therefore the subject of a considerable amount of research. This paper presents a novel approach to generating parallel tiled code of stencil loops, based on the application of the transitive closure of a data dependence graph and a combination of the polyhedral model and the iteration space slicing framework.
PL
Iteracyjne obliczenia, będące funkcja wartości punktów pewnej przestrzeni w czasie, stanowią podstawe˛ szerokiego zakresu rozwiązań naukowych i inżynieryjnych. Efektywne wykonanie realizujących je pętli programowych, poprzez pełne i zrównowaz˙one wykorzystanie dostępnych jednostek obliczeniowych od samego początku, jest przedmiotem znacznej liczby badań. Artykuł prezentuje nowe podejście do blokowania omawianych pętli, bazujące na zastosowaniu domknięcia przechodniego grafu zależności danych oraz technice podziału przestrzeni iteracji.
7
Content available remote Model for the estimation of the execution time of parallel program loops
Kamińska A., Bielecki W.
Przegląd Elektrotechniczny
|
2014
|
R. 90, nr 2
125--127
EN
This paper presents the assumptions and proposition of the model for the estimation of the execution time of parallel program loops. The model is intended to be used in iterative compilation. The model has been elaborated with the focus on shortening the duration of iterative compilation.
PL
W artykule przedstawiono założenia i propozycję modelu do oszacowania czasu wykonania zrównoleglonych pętli programowych. Przewidywanym obszarem zastosowania modelu jest kompilacja iteracyjna. Model został opracowany pod kątem skrócenia czasu kompilacji iteracyjnej.
8
Content available remote Estimation of the execution time of coarse-grained parallel program loops
Kamińska A., Bielecki W.
Przegląd Elektrotechniczny
|
2014
|
R. 90, nr 2
85--88
EN
This paper presents results of experimental research on possibilities of estimating the execution time of coarse-grained parallel program loops based on a regression model. The intended use of the model in question is iterative compilation.
PL
W artykule przedstawiono wyniki badań eksperymentalnych dotyczących możliwości obliczeniowego szacowania czasu wykonania gruboziarnistych, zrównoleglonych pętli programowych w oparciu o model regresyjny. Przewidywanym obszarem zastosowania przedmiotowego modelu jest kompilacja iteracyjna.
9
Content available remote Programming NVIDIA cards by means of transitive closure based parallelization algorithms
Palkowski M., Bielecki W.
Przegląd Elektrotechniczny
|
2012
|
R. 88, nr 10b
217-222
EN
Massively parallel processing is a type of computing that uses many separate CPUs or GPUs running in parallel to execute a single program. Because most computations are contained in program loops, automatic extraction of parallelism available in loops is extremely important for many-core systems. In this paper, we study speed-up and scalability of parallel code scanning synchronization-free slices and time partitions by means of a 960 CUDA Cores machine, Tesla S1070.
PL
Przetwarzanie równoległe na wielką skalę wykonywane jest za pomocą wielu procesorów (również graficznych) wykonujących jednocześnie instrukcje pojedynczego programu. Ponieważ większość obliczeń zlokalizowana jest w pętlach programowych, automatyczne zrównoleglanie kodu jest ważne dla maszyn wielordzeniowych. W artykule zbadano przyspieszenie i skalowalność równoległego kodu złożonego z niezależnych fragmentów lub harmonogramowania swobodnego za pomocą maszyny Tesla S1070 zbudowanej z 960 rdzeni CUDA.
10
Content available remote Dependence analysis and extraction of coarse-grained parallelism for parameterized perfectly-nested loops
Bielecki W., Kraska K., Poliwoda M.
Przegląd Elektrotechniczny
|
2012
|
R. 88, nr 10b
231-234
EN
This paper expands an approach presented in [1] to extraction of coarse-grained parallelism available in parameterized uniform and quasi-uniform perfectly-nested loops. It introduces a dependence analysis that is characterized by a polynomial time complexity and enables computing dependence distance vectors when the Petit dependence analyser fails to produce dependences. It permits to examine the performance of the approach for all parameterized perfectly-nested loops from the NAS Parallel Benchmark Suite.
PL
W artykule przedstawiono rozwinięcie zaprezentowanego we wcześniejszej pracy [1] podejścia do ekstrakcji gruboziarnistej równoległości w jednorodnych oraz quasi-jednorodnych pętlach programowych idealnie zagnieżdżonych. Rozwinięcie uprzednich wyników zostało osiągnięte poprzez wprowadzenie analizy zależności o wielomianowej złożoności obliczeniowej jednocześnie umożliwiającej obliczenie wektorów zależności w tych przypadkach, w których uprzednio wykorzystany analizator zależności Petit sygnalizował brak możliwości analizy źródła. Stworzyło to ostatecznie warunki do oceny skuteczności działania proponowanego podejścia dla wszystkich sparametryzowanych pętli idealnie zagnieżdżonych zawartych w zestawie testowym NAS Parallel Benchmark Suite.
11
Content available Prywatyzacja zmiennych skalarnych dla wyznaczania równoległości w pętlach programowych
Pałkowski M., Bielecki W.
Pomiary Automatyka Kontrola
|
2012
|
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.
12
Content available Wyznaczanie równoległości pętli programowych w aplikacjach dedykowanych dla procesorów graficznych
Bielecki W., Pałkowski M.
Pomiary Automatyka Kontrola
|
2011
|
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.
13
Content available Wpływ redukcji zależności w pętlach programowych na zużycie zasobów w systemach wbudowanych
Bielecki W., Siedlecki K.
Pomiary Automatyka Kontrola
|
2011
|
R. 57, nr 8
833-835
PL
Zaprezentowano wpływ redukcji zależności na zużycie zasobów dla pętli programowych zapisanych w języku ANSI-C. Do redukcji zależności wykorzystane zostały popularne techniki (redukcja zmiennych skalarnych, indukcja zmiennych, przekoszenie pętli, podział i łączenie pętli oraz rozszerzenie zmiennych skalarnych) jak również nowe pozwalające na redukcję zależności bez konieczności modyfikacji kodu pętli. Omówiono zużycie zasobów pamięciowych w zależności od zastosowanej transformacji. Dla przykładowych pętli przedstawiono analizę zużycia zasobów w kontekście systemów osadzonych.
EN
The influence of dependence removal techniques on computer resource utilization for program loops is investigated. Source loops are represented in the C language. Removing redundant dependence relations allows reducing time complexity of algorithms whose input is a set of dependence relations while output is a parallel program. In addition, removing dependences leads to reducing computer resource utilization. Well-known techniques and those proposed by the authors are examined. The following well-known techniques are investigated: scalar reduction, induction variable elimination, loop skewing, loop splitting, loop fissioning, and scalar expansion. All techniques are illustrated by means of examples. Additional techniques being examined are removing dependence relations describing the same dependences as well as removing dependence relations representing linear dependent distance vectors. For a chosen example, for each technique under examination, its effectiveness is presented and the effect of com-puter resource utilization is shown.
14
Content available Programming synchronization-free parallelism using Intel Threading Building Blocks
Bielecki W., Palkowski M.
Pomiary Automatyka Kontrola
|
2011
|
R. 57, nr 11
1380-1383
EN
Extracting synchronization-free parallelism by means of the Iteration Space Slicing Framework results in parallel pseudo-code that is independent on a parallel computer architecture and API/library, hence it cannot be directly compiled. For producing parallel programs for shared memory multiprocessors, Threading Building Blocks (TBB) can be applied that is a library supporting scalable parallel programming based on the standard C++ language. In this paper, we present how to benefit from TBB in practice on the basis of pseudo-code representing synchronization-free slices produced by a tool using the Omega Library. Results of experiments with the NAS benchmarks suite are presented.
PL
Zastosowanie techniki opartej na ekstrakcji równoległości pozbawionej synchronizacji w pętlach programowych pozwala na wygenerowanie pseudokodu, który jest niezależny od architektury komputera oraz języka lub biblioteki programowania. Taki kod nie może być wprost kompilowany. Jest wymagane przekształcenie takiego pseudokodu na rzeczywisty kod równoległy. W tym celu może być zastosowane narzędzie Intel Threading Building Blocks, które jest biblioteką wspierająca skalowalne programowanie równoległe w standardzie C++. Nie wymaga specjalnego języka programowania i specjalnych kompilatorów. Zaletą biblioteki Threading Building Blocks jest możliwość uruchomienia w dowolnym środowisku programowo-sprzętowym i systemie operacyjnym. W artykule przedstawiono korzyści wynikające z tworzenia aplikacji równoległych za pomocą TBB. Wyjaśniono sposób poszukiwania instancji instrukcji fragmentów kodu przy użyciu biblioteki Omega i tworzenie najpierw równoległego pseudo-kodu, a dalej transformacja pseudokodu na kod równoległy z wykorzystaniem TBB. Proponowane podejście zostało zweryfikowane za pomocą zbioru pętli testowych z benchmarku NAS. Zbadano przyspieszenie i efektywność kodu równoległego oraz skalowalność w aspekcie do zmiennego rozmiaru obliczeń badanych pętli.
15
Obliczeniowe szacowanie lokalności danych na poziomie pamięci podręcznej
Kamińska A., Bielecki W.
Metody Informatyki Stosowanej
|
2011
|
nr 4
33-44
EN
In order to effectively use cache memory, it is essential to ensure good data locality at the cache memory level. This can be achieved by appropriately transforming the source code of a program to a semantically equivalent form. The problem is, however, how – based only on the form of the source code of a program – to assess the data locality it involves and apply this assessment for selection of the source code of the shortest execution time. The paper presents Wolfe’s method of estimating data locality and - using the matrix multiplication problem for reference – discusses the possibilities of applying Wolfe’s method for the purpose of estimating the program execution time. The paper also presents software prepared by the authors and dedicated for estimating data locality.
16
Content available Using transitive closure and transitive reduction to extract coarse-grained parallelism in program loops
Bielecki W., Pałkowski M., Siedlecki K.
Pomiary Automatyka Kontrola
|
2010
|
R. 56, nr 8
976-979
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ń.
17
Content available Non-repudiation of Electronic Health Records in distributed healthcare systems
Hyla T., Bielecki W., Pejaś J.
Pomiary Automatyka Kontrola
|
2010
|
R. 56, nr 10
1170-1173
EN
Healthcare systems managing Electronic Health Records (EHR) are being implemented around the world to facilitate access to patients' health data. The primary idea of the EHR is to gather all health information about a subject of care in one place. When a countrywide EHR system is fully implemented, it is assumed that all newly created documentation is stored in the system. Distributed healthcare systems, which connect national or regional healthcare system, are necessary to allow access to patient' health data in any of connected nationwide healthcare systems. In such complex systems, due to high commercial value and sensitiveness of medical data, security is a very important issue. The paper presents a solution for maintaining evidence records, which can ensure a non-repudiation of EHR content, stored in many nationwide systems. In other words, the verifier using the registry evidence records can proof the non-repudiation of EHR content, which is stored outside a patient home healthcare system.
PL
Systemy ochrony zdrowia zarządzające elektronicznymi dokumentami zdrowotnymi (EHR) są wdrażane na całym świecie w celu ułatwienia dostępu do danych o zdrowiu pacjentów. Podstawową ideą EHR jest zebranie wszystkich informacji medycznych dotyczących jednego pacjenta w jednym miejscu. Gdy ogólnokrajowy system EHR jest w pełni wdrożony, zakłada się, że wszystkie nowo utworzone dokumenty są przechowywane w systemie. Rozproszone systemy ochrony zdrowia łączące narodowe lub regionalne systemy ochrony zdrowia są konieczne aby umożliwić specjalistom ds. ochrony zdrowia dostęp do wszystkich danych dotyczących jednego pacjenta. W tak skomplikowanych systemach, z uwagi na dużą wrażliwość danych medycznych i ich dużą wartość komercyjną np. na rynku ubezpieczeń, bezpieczeństwo jest jednym z głównych priorytetów. W artykule przedstawiono rozwiązanie pozwalające na zarządzanie rekordami poświadczeń rejestrów, za pomocą których można wykazać niezaprzeczalność zawartości EHR, przechowywanego w wielu ogólnokrajowych systemach EHR. Zewnętrzny weryfikator używając rekordów poświadczeń rejestrów może wykazać, że zawartość EHR jest oryginalna i niezmodyfikowana.
18
Content available Ekstrakcja równoległości w programach ANSI C dla systemów osadzonych
Bielecki W., Siedlecki K., Kraska K.
Pomiary Automatyka Kontrola
|
2010
|
R. 56, nr 7
697-700
PL
W artykule zaprezentowano nowe podejście do ekstrakcji równole-głości w programach ANSI C dla architektur wieloprocesorowych polega-jące na wyznaczaniu niezależnych fragmentów obliczeń w pętlach programowych dowolnie zagnieżdżonych. Przedstawione podejście pozwala na ekstrakcję równoległości dla szerszego spektrum pętli programowych w porównaniu z transformacjami afinicznymi, uznawanymi dotychczas za najbardziej efektywne. Przedstawiono analizę zastosowania proponowanego podejścia dla wybranych źródeł języka ANSI C. Omówiono wyniki badań eksperymentalnych oraz wskazano kierunki dalszych prac.
EN
The application of embedded computer systems extends from small consumer products to complex industrial solutions. Performance critical solutions require application of more efficient controllers using parallel architectures such as VLIW or multiprocessor (multi cores) architectures. The interest in using the parallelism in embedded systems puts up new challenges for science and engineering and requires new methods and tools. The paper presents a new approach to the extraction of parallelism in ANSI C programs for multiprocessor architectures, consisting of synchronization free threads of computations (slices). The presented approach allows the extraction of parallelism on a wider range of program loops than that extracted by the affine transformation framework identified as the most efficient. Scientific results achieved are implemented as an academic source to source parallelizing compiler. The analysis of applying the approach to selected ANSI C sources is presented. Experimental results are depicted and discussed. Conclusions and future research are discussed.
19
Content available An approach to form affine time partitioning for statement instances of arbitrarily nested loops
Bielecki W., Siedlecki K., Wernikowski S.
Pomiary Automatyka Kontrola
|
2010
|
R. 56, nr 10
1186-1189
EN
A novel approach to form affine time partitioning for statement instances of arbitrary nested loops is presented. It is based on extracting free-scheduling which next is used to form a system of equations to produce legal time partitioning. The approach requires an exact dependence analysis. To carry out experiments, the dependence analysis by Pugh and Wonnacott was chosen. Examples illustrating the approach and the results of experiments are presented.
PL
Przedstawiona została nowa metoda do tworzenia afinicznych odwzorowań czasowych instancji instrukcji dla pętli dowolnie zagnieżdżonych. Metoda bazuje na ekstrakcji harmonogramu swobodnego, wykorzystywanego do tworzenia legalnego odwzorowania czasowego. Metoda wymaga dokładnej analizy zależności. Do przeprowadzenia eksperymentów, wybrana została analiza zależności zaproponowana przez Pugh'a and Wonnacott'a. W analizie tej zależności reprezentowane są przez relacje zależności, natomiast przestrzeń iteracji przez zbiory. Do tworzenie zbiorów i relacji zależności wykorzystywana jest arytmetyka Presburgera. Zostały przedstawione przykłady ilustrujące działanie metody dla pętli idealnie zagnieżdżonej, jak i dla pętli nieidealnie zagnieżdżonej. Eksperymenty przeprowadzone zostały na procesorach graficznych firmy nVidia z wykorzystaniem technologii CUDA w trybie zgodności z wersją 1.1. Wyniki zostały przedstawione w formie tabelarycznej. Zostały przedstawione prace pokrewne oraz kierunek dalszych badań.
20
Zwiększenie zbieżności iteracyjnego algorytmu obliczania tranzytywnego domknięcia unii sparametryzowanych relacji zależności
Bielecki W., Klimek T.
Metody Informatyki Stosowanej
|
2010
|
nr 2 (23)
37-47
PL
W artykule przedstawiono udoskonalony algorytm mający na celu poprawienie zbieżności iteracyjnego obliczania tranzytywnego domknięcia sparametryzowanych relacji zależności, których ograniczenia składają się z wielu koniunkcji. Opisane podejście zostało zaimplementowane i przebadane pod kątem skuteczności na zbiorze pętli testowych NAS [13] i UTDSP [14]. Pozwala ono na rozszerzenie możliwości uzyskania dokładnego wyniku w porównaniu z algorytmami zaproponowanymi w [8], [10] i [15]. W dalszych badaniach planowane jest przetestowanie proponowanego algorytmu z innymi zbiorami pętli testowych oraz dalsze jego udoskonalanie. W ogólnym przypadku dla relacji opisującej zależności afiniczne, obliczenie tranzytywnego domknięcia złożonych, sparametryzowanych relacji zależności może być niemożliwe ze względu na nieafiniczne ograniczenia [8], co w konsekwencji utrudnia nam wyznaczenie całkowitej równoległości niewymagającej synchronizacji. Istotne zatem staje się opracowanie algorytmów umożliwiających obliczenie dokładnego tranzytywnego domknięcia dla szerszego spektrum pętli programowych i tym samym zwiększenia ich stopnia równoległości i lokalności.
EN
A novel algorithm for calculating the transitive closure of a multiple conjunct relation (union of single conjunct relations) is presented. It is based on both non-iterative and iterative techniques. Non-iterative techniques are to calculate transitive closure for particular subsets while iterative techniques are to produce final result - the transitive closure for whole space being the union of the range and the domain of an input relation. The advantage of the algorithm is its larger scope of applicability in comparison with known iterative and non-iterative techniques. The algorithm is implemented by means of the Omega Library and applied to NAS and UTDSP benchmarks. Experimental results demonstrate the algorithm effectiveness.
first rewind previous Strona / 2 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ć.