Vliv cache na efektivitu třídění
Název práce v jazyce práce (slovenština): | Vliv cache na efektivitu třídění |
---|---|
Název práce v češtině: | Vliv cache na efektivitu třídění |
Název v anglickém jazyce: | The influence of caches on the efficiency of sorting |
Akademický rok vypsání: | 2006/2007 |
Typ práce: | diplomová práce |
Jazyk práce: | slovenština |
Ústav: | Katedra softwarového inženýrství (32-KSI) |
Vedoucí / školitel: | RNDr. Alena Koubková, CSc. |
Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
Datum přihlášení: | 10.10.2006 |
Datum zadání: | 10.10.2006 |
Datum a čas obhajoby: | 25.05.2009 09:00 |
Datum odevzdání elektronické podoby: | 25.05.2009 |
Datum proběhlé obhajoby: | 25.05.2009 |
Oponenti: | RNDr. Jakub Yaghob, Ph.D. |
Zásady pro vypracování |
Klasické algoritmy pro třídění v interní paměti byly navrženy za předpokladu, že tato paměť je homogenní. V moderních počítačích je ale struktura paměti hierarchická s rozdílnou rychlostí jednotlivých hladin. Doba výpočtu algoritmu pak závisí nejen na počtu provedených operací (např. porovnávání prvků), ale i na počtu transferů dat mezi jednotlivými hladinami (výpadků z cache). Interní algoritmy tak získávají některé rysy algoritmů externích. Úkolem diplomanta bude stručně shrnout dosavadní přístupy k této problematice a popsat známá vylepšení klasických algoritmů navržená pro práci v nehomogenní paměti. Podle možností experimentálně prověřit chování alespoň některých třídicích algoritmů na reálných počítačích s různou architekturou. |
Seznam odborné literatury |
A. LaMarca, R. E. Ladner: The influence of caches on the performance of sorting. Journal of Algorithms 31 (1999), 66 - 104.
S. Sen, S. Chatterjee: Towards a theory of cache-efficient algorithms. Proc. 11-th annual ACM-SIAM symposium on Discrete algorithms 2000, 829 - 838. R. Wickremesinghe, L. Arge, J. S. Chase, J. S. Vitter: Efficient sorting using registers and caches. Journal of Experimental Algorithmics 7 (2002), p. 9. |