Original title: Cache-oblivious Algorithms
Translated title: Cache-oblivious Algorithms
Authors: Vaner, Michal ; Mareš, Martin (advisor) ; Falt, Zbyněk (referee)
Document type: Master’s theses
Year: 2012
Language: eng
Abstract: [eng] [cze]
In this work, we study the cache-oblivious computation model, which is inspired by the behaviour of the memory hierarchy of current computers. We study several graph algorithms and techniques of their design in this model. We consider graph searching, identifying connected components and computing maximal matching. We also study sorting and matrix multiplication as subproblems of many graph algorithms. In ad- dition to previously known algorithms, we present several new ones. We study their efficiency both by the means of asymptotic complexity and by benchmarking them on real hardware and we compare them with classical algorithms. V této práci se zabýváme výpočetním modelem cache-oblivious algoritmů, který je inspirovaný chováním paměťové hierarchie současných počítačů. V tomto modelu studujeme některé grafové algoritmy a techniky jejich návrhu. Zabýváme se zejména procházením grafu, rozkladem na komponenty souvislosti a hledáni v inkluzi maximálního párování. Taktéž zkoumáme třídění a násobení matic jako podproblémy mnohých grafových algoritmů. Mimo dříve známých algoritmů uvádíme i několik nových. Jejich efektivitu posuzujeme jak asymptoticky, tak experimentálně na reálném hardwaru a srovnáváme je s klasickými algoritmy.
Keywords: algorithms; benchmark; cache-oblivious; computation model; algoritmy; cache-oblivious; srovnávací test; výpočetní model

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/41284

Permalink: http://www.nusl.cz/ntk/nusl-485959


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses