Wyniki 1-8 spośród 8 dla zapytania: authorDesc:"WŁODZIMIERZ BIELECKI"

Translacja pętli for języka VHDL do postaci równań boolowskich

Czytaj za darmo! »

Instrukcja pętli for jest jedną z instrukcji sekwencyjnych języka VHDL. Umożliwia wykonanie bloku instrukcji ściśle ustaloną ilość razy. Translacja tego typu konstrukcji w przypadku klasycznych języków programowania nie stwarza większych problemów. Inaczej jest jednak, gdy rozpatrywana jest synteza logiczna [19]. Należy pamiętać, że wynikiem pracy kompilatora będzie rzeczywisty układ scalony[...]

Badania lokalności aplikacji równoległych bazujących na tworzeniu niezależnych wątków obliczeń

Czytaj za darmo! »

Współczesne problemy naukowo-inżynierskie wymagają zastosowania złożonych obliczeniowo aplikacji, skutkując zwiększeniem czasu wykonania kodu programu. Naturalnym sposobem uzyskania przyśpieszenia - zwłaszcza dziś, gdy wieloprocesorowe architektury SMP (ang. Symmetric Multiprocessing) z pamięcią dzieloną są powszechne - jest zrównoleglenie programów sekwencyjnych i wykonanie w środowisku wieloprocesorowym. Skalowalność architektur SMP jest jednak ograniczona wydajnością magistrali/przełącznicy. Poprawę skalowalności uzyskuje się poprzez zastosowanie wielopoziomowej hierarchii pamięci, w której poziomy pamięci kolejno oddalone od procesora są tańsze, większe pod względem rozmiaru lecz cechują się dłuższym czasem dostępu. Aktualnie rynek oferuje wiele układów wieloprocesorowych [...]

Estimation of the execution time of coarse-grained parallel program loops DOI:10.12915/pe.2014.02.23

Czytaj za darmo! »

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. Streszczenie. 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. (Obliczeniowe szacowanie czasu wykonania gruboziarnistych, zrównoleglonych pętli programowych). Keywords: iterative compilation; program execution time; performance estimation. Słowa kluczowe: Kompilacja iteracyjna, czas wykonania programu, szacowanie wydajności. doi:10.12915/pe.2014.02.23 Introduction In many practical applications of computers, one of the most crucial problems is the duration of program execution. A common trend is that the duration of program execution has to be as short as possible. One uses various approaches and techniques in order to achieve the purpose set by this trend. An approach that is worth noticing here is parallel computing which focuses on both software and hardware aspects related to duration of program execution. In parallel computing, an original problem to be solved is divided into smaller ones, which are then solved concurrently ("in parallel") which in consequence results in shortening the time spent on solving the original problem. An important characteristic of so comprehended parallelism is its granularity, i.e. the number of operations which are executed between communication or synchronization events. There are two types of granularity (hence, parallelism): coarse-grained granularity (coarsegrained parallelism) and fine-grained granularity (finegrained parallelism). An application exhibits coarse-grained parallelism if the number of communication or[...]

Model for the estimation of the execution time of parallel program loops DOI:10.12915/pe.2014.02.33

Czytaj za darmo! »

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. Streszczenie. 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. (Model do oszacowania czasu wykonania zrównoleglonych pętli programowych). Keywords: iterative compilation; program execution time; performance estimation. Słowa kluczowe: Kompilacja iteracyjna, czas wykonania programu, szacowanie wydajności. doi:10.12915/pe.2014.02.33 Introduction Despite continuous development and improvement of computer hardware, laws of physics impose limits on the possible increase of the clock rate of a microprocessor. Since the duration of data processing by a computer system is crucial in many practical applications of such systems, use of multiprocessor computers supporting parallel computing has become an alternative for increasing the clock rate of a microprocessor. Parallel computing is based on the principle that a large problem can often be divided into smaller problems, which are then solved concurrently ("in parallel") and in a shorter time than it would take to solve an original large problem. Parallel applications used in parallel computing can be created either manually or automatically. In case of the manual creation, a developer either writes a parallel application from scratch or parallelizes an already existing, sequential application. In case of the automatic creation, dedicated parallelizing compilers automatically convert sequential applications into parallel equivalents. Because of active involvement of a human being in the [...]

Statistical models for the estimation of execution time of coarsegrained OpenMP programs DOI:10.15199/48.2015.02.06

Czytaj za darmo! »

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. Streszczenie. 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. (Modele statystyczne do oszacowania czasu wykonania aplikacji gruboziarnistych w standardzie OpenMP). Keywords: program execution time, iterative compilation, statistical models. Słowa kluczowe: czas wykonania programu, kompilacja iteracyjna, modele statystyczne. Problem statement Limitations resulting from laws of physics impose a barrier on further miniaturization and increase of the speed of uniprocessors. On the other hand, data processing duration is crucial in many practical applications of computers. For these reasons, the use of multiprocessor computers allowing for parallel computing has become an alternative for reducing data processing time by increasing the speed of uniprocessors. Parallel applications can be created either manually (i.e. by a developer) or automatically (i.e. by dedicated parallelizing compilers). Since the manual creation of parallel applications is very time consuming and more error prone than it is desired, the automatic creation of parallel applications is a more popular approach, especially in case of commercial software development. The idea of this approach is to transform, at the compilation stage, a sequential program into a semantically equivalent[...]

On the maximal dimensionality of tiles in tiled code generated by means of Affine Transformations DOI:10.15199/48.2015.11.39

Czytaj za darmo! »

158 PRZEGLA˛D ELEKTROTECHNICZNY, ISSN 0033-2097, R. 91 NR 11/2015 ⎡ ⎣ 1 2 n+ m-n+ m-n+ -1 ⎤ ⎦. In the following section, we present a theorem which allows us to discover on the basis of a dependence matrix what is the maximal tile dimensionality in tiled code generated by means of affine transformations. Discovering the maximal tile dimensionality Let us remind that loops are fully permutable if they can be permuted arbitrarily without changing the semantics of the original program [7]. It is also well-known that a k-deep fully permutable loop nest can be always tiled in k-dimensions [7]. The features of tiled code generated by means of affine transformations are as follows: tile dimensionality is defined by the number of fully permutable loops in a band; the structure of tiles is the same (except from boundary tiles) and defined by affine transformations applied; the number of iterations within a tile is the same (except from boundary tiles) and defined by input constants denoting a tile size. If an original loop nest is not fully permutable, we can try to convert it to a fully permutable one. With this purpose, we have to set up the time-partition constraints of a loop nest [5, 7, 9] that represent the condition that if one iteration is depend upon the other, then the first must be assigned to a time that is no earlier than that of the second; if they are assigned to the same time, then the first has to be executed after the second. For a perfect loop nest, the time-partition constraints can be written as follows [2] DT ∗ C  0 where C is the unknown integer vector, DT is the transposed dependencematrix for the loop nest, and 0 is the zero vector. It is well-known that if there exist k linearly independent solutions to the time-partition constraints of a loop nest, then it is possible to transform this loop nest to have k outermost fully permutable loops [7, 9]. That is the maximal num[...]

Concurrent Start Tiling of Stencil Computations based on the Transitive Closure of a Data Dependence Graph DOI:10.15199/48.2015.11.41

Czytaj za darmo! »

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. Streszczenie. Iteracyjne obliczenia, be˛da˛ce funkcja˛wartos´ci punktów pewnej przestrzeni w czasie, stanowia˛ podstawe˛ szerokiego zakresu rozwia˛zan´ naukowych i inz˙ynieryjnych. Efektywne wykonanie realizuja˛cych je pe˛ tli programowych, poprzez pełne i zrównowaz˙one wykorzystanie doste˛pnych jednostek obliczeniowych od samego pocza˛tku, jest przedmiotem znacznej liczby badan´ . Artykuł prezentuje nowe podejs´cie do blokowania omawianych pe˛ tli, bazuja˛ce na zastosowaniu domknie˛cia przechodniego grafu zalez˙nos´ci danych oraz technice podziału przestrzeni iteracji. (Transformacja pe˛ tli programowych przez blokowanie z równoczesnym rozpocze˛ciem obliczen´ za pomoca˛ domknie˛cia przechodniego grafu zalez˙nos´ci danych) Keywords: optimizing compilers, tiling, stencil, transitive closure, parallel computing, dependence graph, code locality Słowa kluczowe: kompilatory optymalizuja˛ce, blokowanie pe˛ tli, domknie˛cie przechodnie, obliczenia równoległe, graf zalez˙nos´ci, lokalnos´c´ kodu Introduction Stencil computations are a commonly used class of iterative kernels which involve updating a D-dimensional spatial grid over T time steps. A new value of each grid point at time t is defined as a function of the values of neighboring points at the time steps preceding t. Algorithms for solving partial differential equations as well as image processing methods are the examples of scientific problems where computations foll[...]

Dependence analysis and extraction of coarse-grained parallelism for parameterized perfectly-nested loops

Czytaj za darmo! »

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. Streszczenie. 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 (Analiza zależności oraz ekstrakcja gruboziarnistej równoległości sparametryzowanych pętli idealnie zagnieżdżonych). Keywords: parallelizing compilers, dependence analysis, quasi-uniform dependences, loop transformation. Słowa kluczowe: kompilatory zrównoleglające, analiza zależności, zależności quasi-jednorodne, transformacja pętli. Introduction In paper [1] an approach is presented that enables the extraction of coarse-grained parallelism available in parameterized perfectly-nested static-control loops, where loop bounds as well as array subscripts are symbolic parameters. Most steps of the approach are characterized by a polynomial time complexity while other contemporary outstanding [...]

 Strona 1