58304101 Muistihierarkia-algoritmit
(Algorithms for Memory Hierarchies)
Seminaari (2 ov) - kevät 2004
Tohtoriass. Juha Kärkkäinen 20.1.-4.5. ti 10-12 A319
Aihepiiri
Perinteinen algoritmien suunnittelu ja analyysi pohjautuu RAM (Random
Access Machine) -malliin, jossa muistiviittauksen kustannus on aina
sama. Todellisuudessa tietokoneiden muisti muodostaa kuitenkin
hierarkian ulottuen nopeasta mutta pienestä (prosessorin rekisterit)
isoon mutta hitaaseen (levymuisti). Hierarkian ääripäiden välisten
erojen ja sovellusten tietomäärien jatkuvasti kasvaessa RAM-mallin
rajoittuneisuus tässä suhteessa on
yhä useammin ongelma. Varsinkin ero keskusmuistin ja levymuistin
välillä on niin suuri, että useimmat RAM-malliin pohjautuvat
algoritmit ja tietorakenteet lakkaavat käytännössä toimimasta, kun
muistintarve ylittää keskusmuistin koon.
Muistihierarkian huomioon ottavia algoritmeja ja tietorakenteita on kehitetty tietojenkäsittelytieteen alkuajoista lähtien, mutta yhtenäisen teoreettisen pohjan puute on rajoittanut tutkimuksen yksittäistapauksiin ja erikoisalueille. Viimeisen kymmenen vuoden aikana PDM (Parallel Disk Machine) -malli on kuitenkin vakiinnuttanut asemansa muistihierarkia-algoritmien suunnittelussa ja analyysissä ja niiden tutkimus on edennyt pitkin harppauksin.
Seminaarissa tutustutaan PDM-malliin ja siihen pohjautuviin algoritmeihin ja tietorakenteisiin sekä niiden suunnittelu- ja analyysimenetelmiin. Mukaan voidaan ottaa myös joitakin laajemmin muistihierarkioihin liittyviä aiheita, esim. välimuistialgoritmeja.
Esitiedot
Esitietoina edellytetään Algoritmien suunnittelu ja analyysi -kurssi.
Etusijalla ovat muitakin algoritmilinjan laudatur-tason opintoja
suorittaneet.
Juha.Karkkainen@cs.Helsinki.FI