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ähteetMuokkaa

  1. a b c Branch Prediction users.cs.fiu.edu. Viitattu 26.1.2020. (englanniksi)
  2. 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.
  3. Characterizing the Branch Misprediction Penalty (PDF) users.elis.ugent.be. Viitattu 30.9.2020. (englanniksi) 
  4. Mark Smotherman: IBM Stretch (7030) -- Aggressive Uniprocessor Parallelism people.cs.clemson.edu. Viitattu 26.1.2020. (englanniksi) 
  5. James Sanders: Massive Intel CPU flaw: Understanding the technical details of Meltdown and Spectre techrepublic.com. 4.1.2018. Viitattu 24.9.2020. (englanniksi) 

Aiheesta muuallaMuokkaa