Šakojimosi prognozės įrenginio modeliai

 VILNIAUS GEDIMINO TECHNIKOS UNIVERSITETAS ELEKTRONIKOS FAKULTETAS Kompiuterių architektūros kursinis darbas Šakojimosi prognozės įrenginio modeliai Projektą atliko: Vilnius 2009 Turinis: 1. Įvadas........................................................................................................3 2. Modeliuojamo įrenginio struktūrinės schemos.....................................4 Bimodalinis šakojimosi spėjimas......................................................4 Lokalusis šakojimosi spėjimas..........................................................4 Globalusis šakojimosi spėjimas..........................................................6 Globalusis spėjimas taikant pasirinktą indeksavimą..........................7 Globalusis spėjimas taikant apibendrintąjį indeksavimą.....................8 Kombinuotasis šakojimosi spėjimas....................................................9 3. Apkrovos programos esamos ir sukurtos...............................................11 4. Šakojimosi įrenginio modelio sudarymas ir tyrimas.............................14 5. Apibendrinimas.........................................................................................27 6. Informacijos šaltiniai.................................................................................27 1. Įvadas: Šakojimosi instrukcijos – arba kitaip vadinamos pareigos „jump“. Instrukcijos vienas iš operandų turi rodyti kitos iš eilės vykdomos instrukcijos adresą. Dažniausiai tai būna sąlyginio šakojimosi „conditional branch“ instrukcijos, kurioms esant šakojimasis (programinio skaitiklio turinio keitimas adresu, kurį nusako instrukcijos operandas) vyksta tik tuo atveju, jei atitinka tam tikrą sąlygą. Priešingu atveju – jei sąlygos neatitinka, vykdoma kita instrukcija iš eilės (programinis skaitiklis didinamas vienetu). Naudojant simuliatorių sim-outoder galime ištirti teisingai nuspėtų šakojimosi krypčių santykinius skaičius ir instrukcijų vienam procesoriaus ciklui skaičius keičiant metodus bei jų parametrus. Šio kursinio tikslas stebėti šakojimosi prognozes naudojant tokius metodus: taken, nottaken,bimodal, 2 level, combined. 2. Modeliuojamo įrenginio struktūrinės schemos 2.1. Bimodalinis šakojimosi spėjimas Tipiškųjų šakojimosi įvykių pobūdis kompiuterinėse programose nėra visiškai atsitiktinis. Tyrimu rezultatai rodo, jog tam tikru šakojimusi dauguma dažniausiai arba priimama (šakojimasis įvyksta), arba atmetama. Bimodalinis šakojimosi spėjimo metodas remiasi tokiu šakojimosi įvykių bimodaliniu pobūdžiu ir siekia atskirti visuomet priimamus šakojimus nuo visuomet atmetamu. Metodas gali būti įgyvendintas įvairiais budais. Viena iš paprasčiausių schemų pateikta 1 paveiksle. 1 pav. Bimodalinio šakojimosi spėjimo schema Šioje schemoje taikoma skaitikliu lentele (masyvas), kuri indeksuojama pagal žemiausiuosius programinio skaitiklio adresu bitus. Visi lenteles skaitikliai yra dviejų bitu ilgio. Šakojimąsi programoje vykdant {taken}, atitinkamo skaitiklio turinys didinamas vienetu. Panašiu būdu šakojimąsi programoje nevykdant {not-taken}, atitinkamo skaitiklio turinys mažinamas vienetu. Be to, visi skaitikliai apsaugoti nuo įsisotinimo t. y. skaitikliu turinys nemažinamas mažiau už nuli ir nedidinamas daugiau už trijų. Aukščiausiasis tam tikro skaitiklio bitas apibudina šakojimosi spėjimą (aukščiausiasis bitas vienetinis – spėjama, jog šakojimasis vykdomas, aukščiausiasis bitas nulinis – spėjama, jog šakojimasis atmetamas). Tokiu būdu programoje pasikartojantys šakojimaisi bus spėjami teigiamai {taken}, o pasikartojantys atmetami šakojimaisi bus spėjami neigiamai {not-taken}. Taikant 2 bitų skaitiklį spėjimo įrenginys toleruoja pavienius šakojimosi nukrypimus ir išsaugo (iki dviejų nepataikymų iš eiles) nuspėtą įprastą šakojimosi krypti. Didelėms skaitiklių lentelėms esant kiekviena programos šakojimosi instrukciją (jos adresą) atitinka pavienis skaitiklis. Mažesnių skaitiklių lentelių atveju kelios šakojimosi instrukcijos kolektyviai naudoja tą patį skaitiklį tokiu būdu mažindamos spėjimo tikslumą. Projektuojant spėjimo įrenginį, kurio veikimas remiasi bimodaliniu spėjimo metodu, ieškoma kompromiso tarp spėjimo tikslumo ir skaitiklių lentelės dydžio. 1.1. Lokalusis šakojimosi spėjimas Bimodalinį spėjimą galima pagerinti tik pripažinus, jog daugelyje šakojimusi vykdomos pasikartojančios instrukcijų sekos. Geriausiu pavyzdžiu šiuo atveju yra ciklo šakojimosi valdymas. Išnagrinėkime, tarkime tokį ciklą: for(i=1; i1) . . . Pagal globalųjį šakojimosi spėjimą antras spėjimas remiasi informacija apie pirmo šakojimosi kryptį. Pateiktame pavyzdyje matyti, kad tuo atveju jeigu (x>=1) nėra titiksliai žinoma kuria kryptimi įvyks šakojimasis, tačiau tikimybinė informacija leidžia pasirinkti vieną ar kitą kryptį. Šiuo atveju spėjimas bus tikslesnis turint informaciją apie kintamąjį x. 3 pav. Globaliosios istorijos spėjimo įrenginio schema Kitas privalumas, kuriuo pasižymi globalusis spėjimas – lokaliojo šakojimusi spėjimo rezultatu pakartotinis naudojimas. Tai gali atsitikti, kai globaliojoje istorijoje yra visos, tiksliam spėjimui priimti būtinos, lokaliosios istorijos. 1.3. Globalusis spėjimas taikant pasirinktą indeksavimą Tyrimai rodo , kad identifikuojant esama šakojimąsi, informacija apie globaliąja istorija ne tokia efektyvi kaip paprastai taikant šakojimosi instrukcijos adresą (lokaliosios istorijos spėjimo ir net Bimodalinio spėjimo atveju). Darytina prielaida, jog spėjimas bus tikslesnis taikant kartu ir šakojimosi instrukcijos adresą, ir globaliąja istorija. Šiuo atveju skaitikliu lentele indeksuojama sujungus globaliosios istorijos bitus ir šakojimosi instrukcijos adresą. 7.4 paveiksle pateiktoje schemoje matyti, kad n žemiausiųjų GR registro ir m žemiausiųjų programos skaitiklio bitu sujungiami. n + m junginys tiksliai apibudina viena iš skaitikliu lentelėje. Bendruoju atveju n ir m skaičiai pasirenkami laisvai (jų bendras skaičius turi atitikti skaitikliu, skaitikliu lentelėje, skaičių – 2 . n + m), tačiau tai gali turėti įtakos spėjimo tikslumui. 4 pav. Spėjimo taikant globaliąją istoriją su pasirinktinu indeksavimu schema 2.2. Globalusis spėjimas taikant apibendrintąjį indeksavimą Tyrimais nustatyta , kad informacija apie globaliąja istorija prastai identifikuoja esama šakojimosi instrukcija. Darytina prielaida, jog GR registre yra tam tikras informacijos perteklius. Turint pakankama adreso bitu (iš programos skaitiklio) skaičių, šakojimosi instrukcijai identifikuoti galima bandyti juos su GR registro bitais kombinuoti, o ne tiesiogiai jungti pagal n + m schema. Kombinuoti bitus galima įvairiais budais atliekant išskirtinio ARBA {exclusive OR} logine operacija tarp GR registro ir šakojimosi instrukcijos adreso bitais bus gauta daugiau informacijos (tikslesnis indeksas i skaitikliu lentele) nei taikant kiekviena komponente atskirai. 2 lentelėje patektas dvejų šakojimosi instrukcijų adresų apdorojimo pavyzdys. 2 lentelė. Šakojimosi instrukcijų adresų apdorojimo pavyzdys Šakojimosi instrukcijos adresas (iš čia imama m žemiausiųjų bitų) GR registro turinys (iš čia imama n žemiausiųjų bitų) Pasirinkimas indeksavimas 4/4 (n=4; m=4) Apibendrintasis indeksavimas 8/8 (n=8; m=8) 0000 0000 0000 0001 0000 0001 0000 0001 0000 0000 0000 0000 0000 0000 0000 0000 1111 1111 0000 0000 1111 0000 1111 1111 1111 1111 1000 0000 1111 0000 0111 1111 2 lentelėje matyti, kad pagal pasirinktino indeksavimo 4/4 strategiją kartu jungiami 4 žemiausieji šakojimosi instrukcijos adreso bitai ir 4 žemiausieji globaliojo registro bitai. Pagal apibendrintojo indeksavimo 8/8 strategiją indeksas į skaitiklių lentelę gaunamas atliekant išskirtinio ARBA loginę operaciją tarp šakojimosi instrukcijos adreso ir globaliosios istorijos (GR registro) bitų. Lyginant abi strategijas matyti, jog tik apibendrintasis indeksavimas leidžia atskirti visus keturis šakojimosi atvejus. Pasirinktinio indeksavimo strategija neturi galimybės įvertinti keturių aukščiausiųjų adreso ir GR registro bitų. Apibendrintojo indeksavimo strategija galima modifikuoti (kaip ir pasirinktinio indeksavimo strategija) mažinant apdorojime taikomu globaliosios istorijos (GR registro) bitu skaičių. Šiuo atveju išskirtinio ARBA logine operacija bus atliekama ne tarp visu GR registro ir šakojimosi instrukcijos adreso bitų, o tik tarp kelių aukščiausiųjų bitų, taikant žemiausiuosius adreso bitus be keitimo. Taip modifikuota strategija gali duoti tikslesni spėjimą (5 pav.). 5 pav. Spėjimo taikant globaliąją istoriją su apibendrintuoju indeksavimu schema 2.3. Kombinuotasis šakojimosi spėjimas Šakojimosi spėjimo schemos išnagrinėtos 2.1.–2.5. poskyriuose pasižymi įvairiais pranašumais. Natūraliai kyla klausimas ar negalima butu apjungti kelias schemas ir tokiu būdu gauti nauja, tikslesni spėjimo metodą. Vieno tokio spėjimo metodo schema pateikta 7.6 paveiksle. Šioje kombinuotoje spėjimo sistemoje yra du spėjimo įrenginiai P1 ir P2, kuriu veikimas remiasi anksčiau išnagrinėtais metodais arba bet kuriais kitais spėjimo metodais. Be to, kombinuotoje sistemoje tam tikram spėjimo įrenginiui pasirinkti numatyta papildoma skaitikliu lentele (masyvas). Kaip ir kitose spėjimo schemose šioje lentelėje taikytini 2 bitu reversyviniai įsisotinantys skaitikliai. Kiekvienas toks skaitiklis apibudina tinkamiausia spėjimo įrenginį toms šakojimosi instrukcijoms, kurios kartu naudoja esama lenteles skaitiklį. 6 pav. Kombinuotoji šakojimosi spėjimo sistema Nagrinėjamoje sistemoje P1 ir P2 spėjimo įrenginiai veikia lygiagrečiai, ir nepriklausomai vienas nuo kito priima sprendimus apie šakojimosi krypti pagal juose įgyvendintus spėjimo metodus. Įrenginiu sprendimai šiuo atveju žymimi P1c ir P2c atitinkamai; 0 – reiškia spėjimą, kad šakojimasis atmetamas, o 1 – šakojimasis turi buti vykdomas. Pagal P1c ir P2c signalu reikšmes didinamas arba mažinamas tam tikras masyvo (lenteles) skaitiklis. Remiantis atnaujintu skaitiklio turiniu taikomas tik vienas P1c arba P2c spėjimas. Visi įmanomi spėjimo sistemos veikimo scenarijai pateikti 3 lentelėje. 3 lentelė. Kombinuotosios šakojimosi spėjimo sistemos veikimo scenarijai Spėjimo įrenginių signalai Skaitiklių valdymas Komentaras P1c P2c P1c – P2c 0 0 0 nekeisti P1 ir P2 įrenginiai priėmė sprendimą, kad esamą šakojimąsi reikia atmesti. Skaitiklio reikšmė nekeičiama. 0 1 -1 mažinti vienetu P1 įrenginys spėja, kad šakojimąsi reikia atmesti, tuo tarpu P2 spėjam kad šakojimasis turi būti vykdomas. Skėtiklio reikšmė mažinama vienetu. 1 0 1 padidinti vienetu P1 įreginys spėja, kad šakojimąsis turi buti vykdomas, tuo tarpu P2 spėja, kas šakojimąsi būtina atmesti. Skaitiklio reikšmė didinama vienetu. 1 1 0 nekeisti P1 ir P2 įrenginiai priėmė sprendimus, kad esamą šakojimąsi reikia vykdyti. Skaitiklio reikšmė nekeičiama. 3. Apkrovos programos esamos ir sukurtos Apkrovos programa – hipotetinio, kaip ir tikrojo, kompiuterio esminė funkcija – vykdyti programas. Taigi, norint paleisti bet kurią sumodeliuoto kompiuterio simuliaciją, jį būtina „apkrauti“ – nurodyti jam vkditi tam tikrą apkrovos programą. Dažniausiai naudojamos apkrauties programos kurias turi Simplescalar paketas. Go.ss – viena iš įdomiausiu apkrovos programų Simplescalar programų pakete. Tai senovės kinų sugalvotas intelektualinis žaidimas. Testo metu žaidimo ėjimus atlieka du virtualieji žaidėjai: „juodasis“ ir „baltasis“. Šioje programoje naudojama 64 (8x8) langelių dydžio lenta ir nustatomas 5 žaidimo sunkumo lygis. Nuo šių nustatymų priklauso modeliuojamo procesoriaus apdorotų instrukcijų skaičius ir bendra simuliacijos atlikimo trukmė. test-math - apkrovos programa tai nesudėtinga ir sparti programa, kuri atlieka paprastas matematines operacijas. Jai nereikia nurodyti jokių pradinių parametrų ar kurti aritmetinių operacijų sąrašo, kad apkrovos programa pateiktų rezultatus. Ši programa išsikviečia matematinės bibliotekos funkcijas, kad įvykdytų visas jos programos kode parašytas operacijas. test-math programa dirba ir su sveikųjų skaičių, ir su slankaus kablelio instrukcijomis. test-fmath - apkrovos programa, kaip ir test-math apkrovos programa, yra nesudėtinga ir sparti tik šiek tiek trumpesnė programa, kuri atlieka paprastas matematines operacijas. Jai taip pat nereikia nurodyti jokių pradinių parametrų ar kurti aritmetinių operacijų sąrašo, kad apkrovos programa pateiktų rezultatus. Ši programa išsikviečia matematinės bibliotekos funkcijas, kad įvykdytų visas jos programos kode parašytas operacijas. testmath programa dirba ir su sveikųjų skaičių, ir su slankaus kablelio instrukcijomis. test-llong - apkrovos programa taip pat paprasta ir greita programa, kuri atlieka veiksmus su atminties adresais. Jai, kaip ir kitoms testinėms programoms nereikia nurodyti jokių pradinių parametrų ar kurti aritmetinių operacijų sąrašo, kad apkrovos programa pateiktų rezultatus. Anagram - Pagal enciklopedijos apibrėžimą anagram – žodžio raidžių ar skiemenų sukeitimas, kai yra sudaromas kitas žodis arba prasminga frazė. Pavyzdžiui, Dievas – Veidas; Lėkiau – Kiaulė; Likti – Kilti; Gimti – Migti; Semti – Mesti ir kt. Anksčiau anagramos buvo kuriamos įvairių žodžio raidžių variacijų pagalba, dabar specialių programų pagalba yra sukurti specialūs raidžių ir iš jų galimų sudaryti prasmingų žodžių generatoriai. Vienas tokių generatorių kaip tik naudojamas SimpleScalar programų pakete. Mano programa pavadinimu keitiklis keičia dvejetaini, trejetaini, septintaini, aštuntaini skaičius į dešimtainius. Kintamiesiems priskirtus atitinkamus skaičius programa ciklu ir sąlygų pagalba paverčia dešimtainiu skaičių. Pvz. Programos kodas: #include

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!