Vliv cache na efektivitu třídění

• Thesis title in thesis language (Slovak): Vliv cache na efektivitu třídění
• Thesis title in Czech: Vliv cache na efektivitu třídění
• Thesis title in English: The influence of caches on the efficiency of sorting
• Academic year of topic announcement: 2006/2007
• Thesis type: diploma thesis
• Thesis language: slovenština
• Department: Department of Software Engineering (32-KSI)
• Supervisor: RNDr. Alena Koubková, CSc.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 10.10.2006
• Date of assignment: 10.10.2006
• Date and time of defence: 25.05.2009 09:00
• Date of electronic submission: 25.05.2009
• Date of proceeded defence: 25.05.2009
• Opponents: RNDr. Jakub Yaghob, Ph.D.

Guidelines

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.

References

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.