Automatyczna ekstrakcja zależności i transformacje pętli w języku C do przekształceń optymalizujących w systemach osadzonych

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

Warianty tytułu

EN

Automatic extraction of dependencies and loop transformations in C language for optimising transformations in embedded systems

• Języki publikacji: PL

Abstrakty

PL

W poniższym artykule zaprezentowano metody wyszukiwania pętli programowych i zależności między ich iteracjami. Analiza zależności pozwala na określenie, które fragmenty analizowanego kodu programu mogą zostać wykonane niezależnie. Przedstawiono analizę programów w ANSI C, ze wskazaniem możliwości wykorzystania wyników analizy do zmniejszenia użycia zasobów w systemach osadzonych. Zautomatyzowanie analizy pozwala określić klasy algorytmów i ich implementacje, które mogą być optymalizowane, oraz charakter tych optymalizacji.

EN

In the paper there are presented methods of searching for program loops and dependencies between iteration of these loops. Analysis of the dependencies allows determining which parts of the analysed code of the program must be executed sequentially, and which can be executed independently. There are given the results of the analysis of simple algorithms written in ANSI C language, indicating the possibility of using the analysis to reduce the use of resources in embedded systems. Automating the analysis process also allows specifying the types of algorithm classes and their implementation, which can be subjected to optimisation, as well as the nature of these optimisations. In the introduction there is discussed the range of topics dealt with in the paper. In the second paragraph the method for determining the dependencies between instructions is described. Fig. 2 shows the iteration space of the sample loop. The third paragraph presents the basic techniques of loop transformation, which are possible due to the dependency analysis between iterations. The above (and others obtained during the tests) results show the possibilities of allowing the code designer to improve devices and embedded systems. Transformation selection algorithms need different types of dependence description as an input data. The aim of the project described in the paper, which is devoted to the dependency analysis is to provide a variety of the dependency collection description.

Słowa kluczowe

PL

kompilator; systemy osadzone; analiza zależności

EN

compiler; embedded system; dependency analysis

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2010
• Tom: R. 56, nr 7
• Strony: 708--710
• Opis fizyczny: Bibliogr. 16 poz., rys., wykr., wzory

Twórcy

autor

Błaszyński P.

autor

Poliwoda M.

• Zachodniopomorski Uniwersytet Technologiczny, ul. Żołnierska 49, 71-210 Szczecin,

Bibliografia

• [1] Allen, R, Kennedy, K.: Optimizing Compilers for Modern Architectures. Morgan Kaufmann, 2001.
• [2] Banerjee U.: Loop Transformations for Restructuring Compilers. Kluwer Academic, 1993.
• [3] Wolfe M.: High Performance Compilers for Parallel Computing. Addison-Wesley Publishing Company, 1995.
• [4] Darte A., Robert Y., Vivien F.: Scheduling and Automatic Parallelization. Birkhäuser Boston, 2000.
• [5] Lamport L.: The Parallel Execution of DO Loops. Communications of the ACM, Vol. 17, No 2, Feb. 1974, pp. 83-93.
• [6] Wolf M. E. and Lam M. S.: A data locality optimizing algorithm. In Proc. ACM SIGPLAN 91 Conference on Programming Language Design and Implementation, pages 30-44, June 1991.
• [7] The Omega Project [online] http://www.cs.umd.edu/projects/omega/ [dostęp: 2009]
• [8] PIPS: Automatic Parallelizer [online] http://www.cri.ensmp.fr/~pips/ [dostęp: 2009]
• [9] Poliwoda M.: Automatyczne zrównoleglenie pętli programowych, implementacja metody hiperpłaszczyzn. Metody i narzędzia wytwarzania oprogramowania, 14-16 maja, Szklarska Poręba, Polska 2007.
• [10] Schrijver: Theory of Linear and Integer Programming. Wiley, Chichester, 1986.
• [11] Wei Li and Keshav Pingali: 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.
• [12] Allen R., Callahan D. and Kennedy K.: Automatic decomposition of scientific programs for parallel execution. In Conference Record of the Fourteenth ACM Symposium on Principles of Programming Languages, pages 63-76, January 1987.
• [13] Allen J. R. and Kennedy K.: Automatic translation of Fortran programs to vector form. ACM Transactions on Programming Languages and Systems, 9 (4):491-542, October 1987.
• [14] Vivek Sarkar and Radhika Thekkath: A general framework for iteration-reordering loop transformations. In ACM SIGPLAN’92 Conference on Programming Language Design and Implementation, pages 175-187, San Francisco, California, June 1992.
• [15] Steve Carr and Ken Kennedy: Compiler blockability of numerical algorithms. In Proceedings Supercomput-ing’92, pages 114-125, Minneapolis, Minnesota, Nov 1992.
• [16] Polychronopoulos C.: Parallel Programming and Compilers. Kluwer Academic Publishers, 1988.