Haarautumisen ennakointi
Haarautumisen ennakointi (engl. branch prediction) on tietokoneen suorittimen ominaisuus, joka tähtää suorituskyvyn parantamiseen.[1] Jotta käskykannan liukuhihna toimii tehokkaasti on sen vaiheet pidettävä täytettyinä.[1]
Haarautumisen ennakointi pyrkii ennakoimaan miten ehtolause tai toistorakenne tullaan suorittamaan ja parhaassa tapauksessa liukuhihna pysyy täytenä.[1][2] Pidemmällä liukuhihnalla väärin ennakoinnin kustannus seuraa syvemmällä liukuhihnan vaiheessa.[2]
Toistorakenteet yleensä suoritetaan useita kertoja ja taaksepäin suuntautuvat haarat yleensä suoritetaan.[2] Yksinkertaisin ennakointi katsoo haaran suunnan ja ennakoi taaksepäin suuntautuvan suorittamisen.[2] Tätä kutsutaan staattiseksi haaran ennakoimiseksi koska se ei riipu ohjelmasuorituksen historiasta.[2]
Eteenpäin suuntautuvat haarat ovat vaikeasti ennakoitavissa tietämättä enempää tietystä ohjelmasta.[2] Tätä varten suorittimet käyttävät dynaamista haaran ennakoimista, jolloin käytetään ohjelmasuorituksen historiaa arvioimisessa kumpi haara suoritetaan.[2] Dynaamista ennakointia varten suorittimet pitävät taulua viimeisistä sadoista (tai tuhansista) haarautumiskäskyistä.[2] Yhden bitin dynaaminen ennakointi muistaa suoritettiinko haara viimeksi ja ennakoi tapahtuuko sama seuraavalla kerralla.[2] Kahden bitin dynaaminen ennakointi sisältää neljä tilaa: vahva suoritus, heikko suoritus, heikko ohitus, vahva ohitus.[2]
Virheellisestä ennakoinnista aiheutuva suorituskykyhaitta voi olla merkittävästi suurempi kuin liukuhihnan uudelleentäyttöön tarvittava aika.[3]
Haarautumisen ennakointiin perustuvaa spekulatiivista suoritusta käytettiin jo IBM 7030 -tietokoneessa.[4]
Spectre-tietoturva-aukko perustuu haarautumisen ennakoinnissa ja spekulatiivisessa suorituksessa olevaan virheeseen.[5]
Lähteet
[muokkaa | muokkaa wikitekstiä]- ↑ a b c Branch Prediction users.cs.fiu.edu. Viitattu 26.1.2020. (englanniksi)
- ↑ a b c d e f g h i j Harris, David Money & Harris, Sarah L.: Digital Design and Computer Architecture, s. 446–447. (Second Edition) Morgan Kaufmann, 2013. ISBN 978-0-12-394424-5
- ↑ Characterizing the Branch Misprediction Penalty (PDF) users.elis.ugent.be. Viitattu 30.9.2020. (englanniksi)
- ↑ Mark Smotherman: IBM Stretch (7030) -- Aggressive Uniprocessor Parallelism people.cs.clemson.edu. Viitattu 26.1.2020. (englanniksi)
- ↑ James Sanders: Massive Intel CPU flaw: Understanding the technical details of Meltdown and Spectre techrepublic.com. 4.1.2018. Viitattu 24.9.2020. (englanniksi)