Koncepcja metody zwiększania lokalności danych na poziomie pamięci podręcznej oparta na transformacjach pętli programowych

• Autorzy: Kraska K. , Kamińska A.
• Języki publikacji: PL

Abstrakty

PL

W artykule omówiono problem lokalności danych oraz zaprezentowano istniejące techniki zwiększania lokalności danych polegające na transformacji kodu zródłowego pętli w celu lepszego wykorzystania możliwości pamięci podręcznej procesora. Zaprezentowano również koncepcję metody zwiększania lokalności danych na poziomie pamięci podręcznej opartej na znanych transformacjach pętli programowych oraz obliczeniowo-doświadczalnej analizie metryk lokalności danych. Przedstawiono model koncepcyjny modułu programowego implementujacego uzyskiwane wyniki badań.

EN

This paper presents in outline the idea of hierarchical organization of memory, focusing on cache memory. It also discusses in brief popular software techniques and approaches which can be used in order to more greatly benefit from the specific nature and potential of cache memory. In this context, one presents herein the conception of a new method for shortening the execution time of various executable programs. The new method aims at increasing data locality at the cache memory level, based on transforms of program loops. A proposal of applying the new method in practice is described herein as well.

Słowa kluczowe

PL

umiejscowienie danych; pamięć ukryta; transformacja pętli; kompilatory

EN

data locality; cache memory; loop transformations; compilers

• Wydawca: Komisja Informatyki Polskiej Akademii Nauk, Oddział w Gdańsku
• Czasopismo: Metody Informatyki Stosowanej
• Rocznik: 2010
• Tom: nr 2 (23)
• Strony: 63--72
• Opis fizyczny: Bibliogr. 15 poz., rys.

Twórcy

autor

Kraska K.

autor

Kamińska A.

• Zachodniopomorski Uniwersytet Technologiczny w Szczecinie, Wydział Informatyki

Bibliografia

• [1] Aho A.V., Lam M.S., Ullman J.D. Compilers. Principles, Techniques, and Tools. 2nd Edition. Addison Wesley, 2007
• [2] Allen R., Kennedy K. Optimizing Compilers for Modern Architectures: A Dependence based Approach. Morgan Kaufmann Publishers, 2001.
• [3] Bielecki W. Essentials of Parallel and Distributed Computing. Informa, 2002
• [4] Bielecki W. Przetwarzanie równoległe i rozproszone. Część 1. Metody zrównoleglenia algorytmów i tworzenia aplikacji. Wydawnictwo Uczelniane Politechniki Szczecinskiej, 2007
• [5] Bielecki W., Kraska K. Analiza metod transformacji programów zwiększających lokalność danych: stan, problemy, perspektywy. Metody Informatyki Stosowanej, Nr 4/2006, Tom 10, s. 515-522
• [6] Bielecki W., Kraska K. Zwiększenie lokalności programów wykonywanych w komputerach równoległych. Metody Informatyki Stosowanej, Nr 2/2007, Tom12, s. 15-25
• [7] Klukowski J., Nabiałek I. Algebra dla studentów. Wydawnictwa Naukowo-Techniczne, 1999
• [8] Kraska K. Zastosowanie Intel® VTune™ Performance Analyzer do badania lokalności danych aplikacji równoległych opartych na tworzeniu niezależnych wątków obliczeń. Metody Informatyki Stosowanej, Nr 1/2009, Tom 18, s. 45-52
• [9] Mahapatra N.R., Venkatrao B. The Processor-Memory Bottleneck: Problems and Solutions. Crossroads 5.3 Spring 1999. Computer Architecture, ACM New York
• [10] Stallings W. Organizacja i architektura systemu komputerowego. Projektowanie systemu a jego wydajność. Wydawnictwa Naukowo-Techniczne, 2004
• [11] Wolfe M. High Performance Compilers for Parallel Computing. Addison‑Wesley, 1996
• [12] 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, June 26-28, 1991
• [13] Drepper U. Understanding Application Memory Performance, Red Hat Summit, Boston 2008
• [14] Lim A.W. Improving Parallelism and Data Locality with Affine Partitioning, PhD thesis. Department of Computer Science, Stanford University, 2001
• [15] Threading Methodology: Principles and Practices. Version 2.0. Intel Corporation, 2004