Lähes kaikissa tietokoneohjelmissa on koodin osia, jotka haarautuvat erillisiin polkuihin. Esimerkiksi jos-niin-else-lauseella on kaksi mahdollista tulosta. Nämä lausunnot eivät aiheuta ongelmia peräkkäisille prosessoreille, koska CPU käsittelee jokaisen komennon järjestyksessä. Haarat ovat suuri ongelma liukuhihnaprosessoreille, koska useita käskyjä suoritetaan kerralla.
Skenaario
Jos ohjelmassa on haarautumislause, jolla on kaksi mahdollista lopputulosta, kaksi mahdollista koodipolkua eivät voi olla samassa paikassa. Kummankin vaihtoehdon suorittamiseen vaadittava käsittely on erilainen. Muuten ohjelma ei haarautuisi. Todennäköisesti tulee olemaan melkoinen määrä haarautuvia lauseita, jotka otetaan vain kerran, kuten if-lause.
On myös haarautuvia lauseita, jotka muodostavat silmukan. Vaikka nämä eivät ehkä ole numeerisesti yhtä yleisiä kuin kertakäyttöiset lausunnot, ne toistuvat yleensä tilastollisesti. Voidaan olettaa, että on todennäköisempää, että haara vie sinut takaisin silmukan ympäri kuin ei.
Miksi tämä on ongelma?
Sillä ei ole väliä, kuinka tämä ongelma ilmaistaan täysin peräkkäisessä prosessorissa. Se ei yksinkertaisesti ole ongelma. Mikä haara otetaan, tiedetään ennen seuraavan ohjeen ensimmäisen osan käsittelyä.
Liukuhihnaprosessorissa seuraavat ohjeet ovat kuitenkin jonossa. Niitä käsitellään jo, kun prosessori tietää, mikä haara on otettu. Joten miten prosessorin pitäisi käsitellä tätä skenaariota? Vaihtoehtoja on muutama. Pahinta on yksinkertaisesti odottaa ja jättää putkisto tyhjäkäynnille odottaessaan vastausta mihin haaraan ottaa. Tämä tarkoittaisi, että joka kerta, kun sinulla on haarautumislause, menetät aina vähintään yhtä monta prosessoriajan jaksoa kuin sinulla on käsittelyssä olevia vaiheita.
Vaihtoehtoisesti voit yrittää suorittaa molemmat vaihtoehdot käsittelyssä ja hylätä väärän valinnan. Tästä aiheutuisi puolet siitä rangaistuksesta, että ei tehdä mitään, mutta silti siitä aiheutuisi suoritusrangaistus jokaisesta haarautuneesta lausunnosta. Koska nykyaikaiset suorittimet voivat myös suorittaa ohjeita epäkunnossa, voit mahdollisesti yrittää suorittaa kaikki haarautumisohjeet mahdollisimman pian. Joten sen tulos tiedetään ennen kuin sitä tarvitaan. Tämä vaihtoehto voi olla hyödyllinen, paitsi että se ei ole skaalautuva. Oletetaan, että sinulla on suhteellisen suuri tiheys haarautuvia lauseita. Siinä tapauksessa et yksinkertaisesti voi suorittaa niitä kaikkia aikaisin ilman joutoaikaa.
Miten tähän ongelmaan todella puututaan
Todellisuudessa prosessori sisältää haaran ennustajan. Haaraennustaja yrittää arvata, mikä haarautumisvalinnan tulos valitaan. Prosessori olettaa sitten, että ennuste on oikea ja ajoittaa ohjeet. Jos haaran ennustaja on tarkka, suorituskykyrangaistusta ei ole.
Jos haaran ennustaja tekee virheen, sinun on huuhdeltava liukuhihna ja aloitettava todellisen tuloksen käsittely. Tämä johtaa hieman huonompaan suoritusrangaistukseen kuin olla tekemättä mitään ja vain odottanut tulosta. Parhaan suorituskyvyn saavuttamiseksi on tärkeää varmistaa, että haaran ennustaja on mahdollisimman tarkka. Tähän on olemassa useita erilaisia lähestymistapoja.
Vastaava koodi
Konekoodissa haara on aina valinta, luetko seuraavan käskyn vai hyppäätkö käskysarjaan muualla. Jotkut haaran ennustajien varhaiset toteutukset olettivat yksinkertaisesti, että kaikki haarat otettaisiin aina tai ei koskaan. Tällä toteutuksella voi olla yllättävän hyvä onnistumisprosentti, jos kääntäjät tietävät tämän käyttäytymisen ja tietävät suunniteltu säätämään konekoodia niin, että todennäköisin tulos on linjassa prosessorin yleisen kanssa oletus. Tämä vaatii paljon viritystä ja ohjelmistokehitystottumusten säätämistä.
Toinen vaihtoehto oli oppia tilastosta, että silmukat otetaan yleensä ja hypätään aina, jos haara menee taaksepäin käskyvirtaa äläkä koskaan hyppää, jos hyppy on eteenpäin, koska se olisi tavallisesti tilastollisesti epätodennäköisempi tila silmukka. Nämä ovat molemmat staattisen haaran ennusteen tyyppejä, joissa haaran tulos ennustetaan käännöshetkellä.
Dynaamiset haaran ennustajat
Nykyaikaiset haaran ennustajat ovat dynaamisia, ja ne käyttävät parhaillaan käynnissä olevan ohjelman tilastoja paremman ennusteen onnistumisprosentin saavuttamiseksi. Kyllästyslaskuri on kaikkien nykyisten haaran ennustajien perusta. Ensimmäinen arvaus päätetään staattisesti tai satunnaisesti. Kun haara on otettu tai sitä ei ole otettu, tulos tallennetaan muistin osaan. Seuraavan kerran, kun sama haara tulee, haaran ennustaja ennustaa saman tuloksen kuin aiemmin.
Tämä johtaa luonnollisesti hyviin ennustusnopeuksiin silmukoille. Tästä on kaksi versiota. Varhaiset versiot käyttivät vain yhtä databittiä osoittamaan, oliko haara otettu vai ei. Myöhemmissä versioissa käytetään kahta bittiä osoittamaan heikosti tai voimakkaasti otettua tai tekemättä valintaa. Tämä asennus voi silti ennustaa silmukan ottamisen tuloksen, jos ohjelma palaa siihen, mikä yleensä lisää onnistumisastetta.
Seurantamallit
Kuvioiden seuraamiseksi jotkin haaran ennustajat pitävät kirjaa tehdyistä valinnoista. Oletetaan esimerkiksi, että silmukkaa kutsutaan jatkuvasti, mutta se kiertää vain neljä kertaa ennen kuin se katkeaa silmukasta. Siinä tapauksessa kaksitasoinen adaptiivinen ennustaja voi tunnistaa tämän kuvion ja ennustaa sen tapahtuvan uudelleen. Tämä lisää onnistumisprosentteja entisestään yksinkertaisella kyllästetyllä laskurilla. Nykyaikaiset haaran ennustajat kehittävät tätä edelleen käyttämällä hermoverkkoa havaitsemaan ja ennustamaan kuvioita.
Jotkut haaran ennustajat käyttävät useita algoritmeja ja vertailevat sitten tuloksia päättääkseen, mitä ennustetta käytetään. Jotkut järjestelmät seuraavat jokaista haarautumiskäskyä erikseen ns. paikallishaaraennusteessa. Toiset käyttävät globaalia haaran ennustejärjestelmää kaikkien viimeaikaisten haarautumisohjeiden seuraamiseen. Molemmilla on käyttötarkoituksensa ja huonot puolensa.
Johtopäätös
Haaraennustaja on liukuhihna-prosessorin erityinen osa. Se yrittää ennustaa haarautumiskäskyn lopputuloksen ennen varsinaisen käskyn käsittelyä. Tämä on liukuhihnaprosessorin ydintoiminto, koska sen avulla CPU voi pitää liukuhihnan kylläisenä, vaikka se ei olisikaan varma, mitä ohjeita on suoritettava. Ne eivät vähennä suorituskykyä, kun ne ovat oikein. Nykyaikaiset algoritmit voivat olla tarkkoja suhteellisen ennustettavissa olevissa työkuormissa jopa 97 % ajasta.
Täydellistä ennustusmenetelmää ei ole, joten toteutukset vaihtelevat. Väärän ennusteen tekemisen tehokkuusvaikutus riippuu putkilinjan pituudesta. Tarkemmin sanottuna putkilinjan pituus ennen kuin voidaan määrittää, oliko ennuste väärä. Se riippuu myös siitä, kuinka monta käskyä kussakin liukuhihnavaiheessa on. Nykyaikaisissa huippuluokan työpöytäsuorittimissa on noin 19 liukuhihnavaihetta ja ne voivat suorittaa vähintään neljä käskyä samanaikaisesti kussakin vaiheessa.