A conversion of "while" and "do-while" loops to allow dependency analysis by existing tools

• Autorzy: Poliwoda M. , Błaszyński P.

Warianty tytułu

PL

Konwersja pętli "while" i "do-while" w celu analizy zależności przez istniejące narzędzia

• Języki publikacji: EN

Abstrakty

EN

In this paper there are presented methods for conversion of "while" and "do-while" loops to the form of "for" loops. The aim of this conversion is to allow dependence analysis by many existing tools. The dependence analysis allows determining which parts of the analyzed program code must be executed sequentially, and which can be executed independently. Such an analysis is used to reduce the use of resources in embedded systems. Automating the analysis also allows specifying types of classes of algorithms and their implementation which can be the subject of optimization. The nature of optimization can also be determined.

PL

Większość narzędzi analizujących zależności "LooPo", "Clan" i "Petit" posiada możliwość analizy pętli typu for, w których wykonuje się operacje na tablicach za pomocą operatorów indeksowania. W chwili obecnej pętle while są analizowane przez analizator "LooPo". Analizatory zależności "clan" i "petit" analizują jedynie pętle for. Zasadną więc jest koncepcja konwersji konstrukcji typu "while", "do-while" do postaci pętli "for", gdyż po wykonaniu konwersji możliwe staje się użycie dowolnego narzędzia do analizy zależności. Użycie różnych narzędzi do analizy zależności daje możliwość uzyskania wyników analizy w postaci odpowiedniej dla zaimplementowanych algorytmów zrównoleglających, co pozwala na uzyskanie większego zbioru propozycji zrównoleglenia kodu pętli. Wykonanie konwersji umożliwi również zastosowanie szeroko implementowanego popularnego standardu OpenMP w celu podziału przestrzeni iteracji między niezależne wątki. Docelowa postać pętli spełnia wymagania dotyczące pętli for przedstawione w specyfikacji OpenMP v3.0. Zastosowanie zgodności z tym standardem umożliwia analizę zależności w pętli przez większość analizatorów pętli w języku C i zapisanie zrównoleglonej postaci pętli zgodnie ze standardem. Algorytm opisany w tym artykule jest zrealizowany kompilatorze "Stepson", który jest aktualnie rozwijany. Informacje o skompilowanym programie są przechowywane w postaci drzewa. Opisany algorytm pozwala zwiększyć liczbę pętli, które można automatycznie analizować.

Słowa kluczowe

EN

compiler; loop conversion; dependency analysis

PL

kompilator; konwersja pętli; analiza zależności

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2010
• Tom: R. 56, nr 12
• Strony: 1501--1503
• Opis fizyczny: Bibliogr. 8 poz., rys., wzory

Twórcy

autor

Poliwoda M.

autor

Błaszyński P.

• West Pomeranian University of Technology, Faculty of Computer Science and Information Technology, ul. Żołnierska 49, 71-210 Szczecin,

Bibliografia

• [1] Rauchwerger L. and Padua D.: Parallelizing While Loops for Multiprocessor Systems. Proc. of the 9th Int. Parallel Processing Symposium, April 1995, Santa Barbara, CA, pp. 347-356.
• [2] Griebl Martin: The Mechanical Parallelization of Loop Nests Containing while Loops. Dissertation, Universitat Passau pp. 80-85.
• [3] C’edric Bastoul: Code Generation in the Polyhedral Model Is Easier Than You Think. PACT’13 IEEE International Conference on Parallel Architecture and Compilation Techniques, September 2004, pp. 7-16.
• [4] Wolfe Michael: The tiny loop restructuring research tool. In Proc of 1991 International Conference on Parallel Processing, pages II-46 - II-53, 1991.
• [5] Li Wei and Pingali Keshav: A singular loop transformation framework based on non-singular matrices. In 5th Workshop on Languages and Compilers for Parallel Computing, pages 249-260, Yale University, August 1992.
• [6] Allen R., Kennedy K.: Optimizing Compilers for Modern Architectures. Morgan Kaufmann, 2001.
• [7] Banerjee U.: Loop Transformations for Restructuring Compilers. Kluwer Academic, 1993.
• [8] The Omega Project [online] http://www.cs.umd.edu/projects/omega/ [dostęp: 2010]