Zwiększenie wydajności aplikacji wykonywanych w systemach osadzonych poprzez zwiększenie lokalności danych

• Autorzy: Bielecki W. , Kraska K.

Warianty tytułu

EN

Improving the application performance of embedded systems by increasing data locality

• Języki publikacji: PL

Abstrakty

PL

Efektywne użycie pamięci jest krytycznym warunkiem uzyskania wysokiej wydajności przez oprogramowanie wykonywane na współczesnych architekturach z hierarchią pamięci. W systemach osadzonych efektywne wykorzystanie pamięci przez aplikacje umożliwia przede wszystkim zmniejszenie wymagań dla sprzętu przy ustalonych kryteriach wydajnościowych, redukcję rozmiaru pamięci jak i zmniejszenie zużycia energii. Wskazane czynniki bezpośrednio wpływają na koszt budowy systemu osadzonego. Osiągnięcie wysokiego poziomu efektywności użycia pamięci wymaga tworzenia oprogramowania uwzględniającego lokalność danych. Oprogramowanie intensywnie eksploatujące pamięć, takie jak chociażby aplikacje multimedialne, zazwyczaj przetwarza w pętlach programowych znaczne ilości danych umieszczonych w tablicach. Sposo-bem na zwiększenie lokalności takich programów jest transformacja pętli programowych do postaci bardziej optymalnego kodu. W artykule przedstawiono aktualny stan badań w zakresie metod transformacji programów zwiększając.

EN

The effective use of memory subsystem is the critical condition for software to achieve the high performance on the contemporary architectures with hierarchy of memory. In embedded systems the effective utilization of the memory subsystem mainly enables to decrease requirements for hardware with respect to established performance criteria, reduce the size of memory and decrease the energy consumption. The indicated factors influence on cost of building an embedded system directly. The achievement of high efficiency of memory subsystem requires creating of software with high data locality. Software that intensely explores memory, such as multimedia applications, usually processes within program loops considerable quantities of data placed in arrays. The transformation of program loops to more optimal code is the way on improvement data locality. In the paper, the state of the art of loop transformation methods improving data locality was presented. Additionally, the possibility of estimating a level of data loality and improving data locality for perfectly nested loop were examined. Finally, the results of analysis investigations were introduced illustrating the efficiency of considered transformations.

Słowa kluczowe

PL

lokalność danych; zrównoleglenie programów; transformacje pętli programowych; kompilatory

EN

data locality; parallelization of programs; loop transformations; compilers

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2007
• Tom: R. 53, nr 7
• Strony: 86--88
• Opis fizyczny: Bibliogr. 11 poz., rys., wzory

Twórcy

autor

Bielecki W.

autor

Kraska K.

• Wydział Informatyki, Politechnika Szczecińska,

Bibliografia

• [1] M. E. Wolf, M. S. Lam: A data locality optimizing algorithm, Proceedings of the ACM SIGPLAN`91 Conference on Programming Language Design and Implementation, 1991.
• [2] M. E. Wolf M. S. Lam: A loop transformation theory and an algorithm to maximize parallelism, Transactions on Parallel Distributed Systems, 1991.
• [3] S. Cart, K. S. McKinley, C. W. Tseng: Compiler optimizatimizations for improving data locality, Proceedings of the Sixth Intemational Conference on Architectural Support for Programming Languages and Operating Systems, 1994.
• [4] K. Kennedy, K. S. McKinley: Optimizing for parallelism and data locality, Proceedings of the 1992 ACM International Conference on Supercomputing, 1992.
• [5] N. Ahmed, N. Mateev, K. Pingali: Synthesizing transformations for locality enhancement of imperfectly nested loop nests, Proceedings of the 2000 ACM International Conference on Supercomputing, 2000.
• [6] I. Kodukula, N. Ahmed, K. Pingali: Data centric multi level blocking, Proceedings of the ACM SIGPLAN'97 Conference on Programming Language Design and Implementation, 1997.
• [7] V. Sarkar, G. R. Gao: Optimization of array accesses by collective loop transformations, Proceedings of the 1991 ACM Intemational Conference on Supercomputing, 1991.
• [8] G. R. Gao, R. Olsen, V. Sarkar, R. Thekkath: Collective loop fusion for array contraction, Proceedings of the Fifth Workshop on Languages and Compilers for Parallel Computing, 1992.
• [9] Y. Song, R. Xu, C. Wang, Z. Li: Array contraction for memory reduction, Workshop on Solving the Memory Wall Problem, 2000.
• [10] W. Bielecki, K. Siedlecki: Extracting synchronization free slices in perfectly nested uniform and non uniform loops, to be published in Electronic Modeling, 2007 (artykuł jest przyjęty do wydania).
• [11] R. Allen, K. Kennedy: Optimizing Compilers for Modem Architectures: A Dependence based Approach, Morgan Kaufmann Publishers, 2001.