Cache-oblivious Algorithms

• Thesis title in Czech: Cache-oblivious Algorithms
• Thesis title in English: Cache-oblivious Algorithms
• Key words: algoritmy, cache-oblivious, výpočetní model, srovnávací test
• English key words: algorithms, cache-oblivious, computation model, benchmark
• Academic year of topic announcement: 2010/2011
• Thesis type: diploma thesis
• Thesis language: angličtina
• Department: Department of Applied Mathematics (32-KAM)
• Supervisor: Mgr. Martin Mareš, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 12.11.2010
• Date of assignment: 12.11.2010
• Date and time of defence: 14.05.2012 10:00
• Date of electronic submission: 12.04.2012
• Date of submission of printed version: 12.04.2012
• Date of proceeded defence: 14.05.2012
• Opponents: RNDr. Zbyněk Falt, Ph.D.

Guidelines

Úkolem diplomanta je prostudovat známé cache-oblivious algoritmy a datové struktury pro jednoduché (například grafové nebo maticové) algoritmické problémy, srovnat je se známými klasickými a cache-aware algoritmy jak teoreticky, tak v implementaci na skutečném hardwaru, a případně navrhnout jejich vylepšení nebo zobecnění.

References

E. Demaine: Cache-Oblivious Algorithms and Data Structures, in Lecture Notes from the EEF Summer School on Massive Data Sets, Lecture Notes in Computer Science, BRICS, University of Aarhus, Denmark, June 27?July 1, 2002.

E. Demaine et al.: An Optimal Cache-Oblivious Priority Queue and its Application to Graph Algorithms, SIAM Journal on Computing, volume 36, number 6, March 2007, pages 1672?1695.