Obliczeniowe szacowanie lokalności danych dla programów ANSI-C

• Autorzy: Kraska K. , Wierciński T. , Kamińska A.

Warianty tytułu

EN

Estimation of data locality for ANSI-C source codes

• Języki publikacji: PL

Abstrakty

PL

Krytycznym czynnikiem warunkującym wydajność obliczeniową oprogramowania jest lokalność dostępu do danych. Dlatego oczekuje się od narzędzi kompilacji automatyzacji procesu przekształcenia nieoptymalnego kodu do postaci charakteryzującej się wysoką lokalnością danych. W artykule przedstawiono podejście pozwalające na oszacowanie lokalności danych programów na podstawie kodu źródłowego w języku ANSI-C. Omówiono wyniki przeprowadzonych badań eksperymentalnych oraz wskazano kierunki dalszych prac.

EN

Good data locality, comprehended as such placement of program data in memory that program data requested by the processor are available immediately on demand, is a critical software requirement for achieving high efficiency in data processing. One of the ways to achieve good data locality is to transform source codes at the compilation stage so as to improve their usage of the cache memory and, thus, fully benefit from the concept of memory hierarchy. Modern compilers are expected to carry out this kind of optimization automatically, by adopting relevant transformations. In order to select the transformation which is best for this purpose for a given source code, the compiler should be able to compare, from this point of view, the available transformations and indicate the one that produces a semantically identical code of the shortest execution time possible. The paper briefly describes Wolfe's method of esti-mating data locality based on calculations carried out directly on the source code under analysis, without any need to carry out time consuming compilation of the source code to its executable form and to collect memory access metrics at run time. The paper also presents in outline how the authors implemented in C++ a software module estimating data locality for ANSI-C source codes based on Wolfe's method. The paper discusses the results of adopting the proposed approach to some selected source codes and indicates directions of further works.

Słowa kluczowe

PL

lokalność danych; pamięć podręczna; blokowanie; kompilatory optymalizujące

EN

data locality; cache memory; tiling; optimizing compilers

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2011
• Tom: R. 57, nr 8
• Strony: 951--953
• Opis fizyczny: Bibliogr. 6 poz., rys., tab.

Twórcy

autor

Kraska K.

autor

Wierciński T.

autor

Kamińska A.

• Zachodniopomorski Uniwersytet Technologiczny, Wydział Informatyki, Żołnierska 49, 71-210 Szczecin,

Bibliografia

• [1] Stallings W.: Organizacja i architektura systemu komputerowego. Projektowanie systemu a jego wydajność, Wydawnictwa Naukowo-Techniczne, 2004.
• [2] Wolfe M.: High Performance Compilers for Parallel Computing, Addison Wesley, 1996.
• [3] Wolf M. E., Lam M. S.: A Data Locality Optimizing Algorithm. Proceedings of the ACM SIGPLAN’91 Conference on Programming Language Design and Implementation. Toronto, Ontario, Canada, 1991.
• [4] Kraska K., Kamińska A.: Koncepcja metody zwiększania lokalności danych na poziomie pamięci podręcznej oparta na transformacjach pętli programowych. Metody Informatyki Stosowanej, Nr 2/2010, s. 63-72.
• [5] Bastoul C., Cohen A., Girbal S., Sharma S., Temam O.: Putting Polyhedral Loop Transformations to Work, LCPC’16 International Workshop on Languages and Compilers for Parallel Computers, LNCS 2958, 2003.
• [6] Uday Bondhugula: Effective Automatic Parallelization and Locality Optimization Using The Polyhedral Model, Ohio State University 2008.