Harjoituksia
Kirjoita kiinteän pisteen toteutus Mandelbrot-generaattorille.
a.
Huomaat, että suorituskyky on epäjohdonmukainen eri pikseleiden ja eri ruutujen välillä. Miksi näin on?
b.
Mikä on sisimmän silmukkarungon aritmeettinen intensiteetti operaatioina muistista käytettyä tavua kohti? Mikä on vastaava suorituskykyraja ARM-suorittimelle? Miten se vertautuu havaitsemaasi suorituskykyyn?
c.
Mittaroi seuraavat suorituskykymittarit sisimmän silmukkarungon osalta:
▪
ohjeet iteraatiota kohti
▪
ohjeet operaatiota kohti
▪
CPI
▪
välimuistitiedostojen ohitusnopeus
d.
Käytä inline-kokoonpanoa sisimmän silmukan rungon toteuttamiseen ja mittaa suorituskykyvaikutus suhteessa osan c mittareihin. Mikä on nopeutuminen verrattuna kääntäjän tuottamaan koodiin?
Parallelisoi Mandelbrot-joukon generaattori OpenMP:n avulla. Sovelletaan parallel-for-direktiiviä uloimpaan (rivin) silmukkaan.
a.
Mittakaa syklien keskimääräinen määrä, joka tarvitaan sisimmän silmukan jokaiseen iteraatioon (polynomin arvioimiseksi) yhdellä säikeellä ja kahdella säikeellä alkukehyksen osalta. Laske näiden mittausten avulla kahden säikeen nopeuslisäys (pikseleinä sekunnissa) verrattuna yhteen säikeeseen.
b.
Mittaroi aika, joka kuluu kaikkien ensimmäisen kehyksen pikseleiden laskemiseen käytettäessä dynaamista aikataulua verrattuna staattiseen aikatauluun.
Mikä vaikeuttaa SIMD-operaation soveltamista Mandelbrot-joukon generaattoriin? Mikä on tehokkain tapa soveltaa SIMD-operaatiota Mandelbrot-joukon generaattoriin?
Mittaroi tehokas kirjoitusläpivienti Linux Framebufferille. Vastaako se kasasta allokoidun muistimassan kirjoitusläpimenoa?
Laskekaa kuvanmuunnosohjelman aritmeettinen intensiteetti operaatioina per pikseli. Mikä on sen suorituskykyraja, kun otetaan huomioon ARM-suorittimen tehokas muistin läpäisykyky? Miten se vertautuu havaitsemaasi suorituskykyyn?
Käytä OpenMP:tä lisätäksesi moniydintuen kiinteäpisteiseen kuvamuunnosohjelmaan. Käytä tätä varten parallel for pragmaa uloimpaan (rivin) silmukkaan.
Mittaa sen suorituskyky neliytimisellä ARM-suorittimella. Miten sen suorituskyky skaalautuu, kun se suoritetaan yhdellä, kahdella, kolmella ja neljällä säikeellä?
Käytä intrinsics-ominaisuuksia lisätäksesi NEON SIMD -tuen kiinteän pisteen kuvamuunnosohjelman kiinteän pisteen versioon. Käytä nelisuuntaisia operaatioita laskeaksesi seuraavat laskutoimitukset neljän pikselin ryhmälle: lähdepikselin sijainti, murto-osan poiminta ja painolaskenta. Missä määrin tämä parantaa suorituskykyä?
Me emme voi helposti optimoida Mandelbrotin generaattoriohjelmaa SIMD-käskyjen avulla, koska naapuripikselit saattavat vaatia eri määrän polynomin evaluointeja ja jokainen polynomin iteraatio on riippuvainen edellisestä evaluoinnista. Vaihtoehtoinen lähestymistapa on toteuttaa silmukka inline-kokoonpanossa, purkaa silmukka vähintään neljällä ja käyttää sitten ohjelmistopipelointia silmukan CPI:n parantamiseksi. Tällöin on vältettävä ehdollisia haaroja kierrättämättömän silmukan sisällä. Koska poikkeavat c-arvot jatkavat poikkeamista seuraavissa evaluoinneissa, voimme odottaa silmukan poistumisehdon tarkistamista jokaisen neljän iteraation ryhmän jälkeen. Polynomien lisäarviointien suorittaminen sen jälkeen, kun Pc()-arvo mahdollisesti poikkeaa säteeltään 2:n ympyrän ulkopuolelle, edellyttää kuitenkin, että otamme huomioon kiintopistemuotomme ylimääräiset vaihteluvälivaatimukset. Laske uudelleen kiinteän pisteen aluevaatimukset tätä optimointia varten ja määritä, missä määrin tämä pienentää maksimizoomaustasoa.
Kiinteän pisteen periaatteelliset edut ovat operaation viiveen väheneminen ja mahdollisuus välttää tyyppimuunnokset tietyntyyppisissä grafiikkakoodeissa. Luvussa 2 tuodaan esiin esimerkkiohjelma, jonka suorituskyky on herkkä operaatioviiveelle, Hornerin menetelmä. Jos oletetaan, että voimme sietää kiintopisteen rajoitukset Hornerin menetelmän koodissa, parantaisiko sen muuntaminen kiintopisteeksi suorituskykyä? Selitä vastauksesi.
Luvussa 3.6.5 esiteltiin kaksi erilaista toteutusta yleistetyn kiinteän pisteen yhteenlaskun esiprosessorimakrosta. Ensimmäinen luotiin gcc:llä maksimioptimoinnilla, toinen koodattiin käsin käyttämällä inline-kokoonpanokieltä. Molemmat toteutukset tarvitsivat suunnilleen saman määrän käskyjä.
a.
Esittele read-after-write -datariippuvuudet molemmissa toteutuksissa. Jos oletetaan, että prosessori käyttää yhden käskyn, järjestyksessä antamista, ja jos oletetaan, että kaikkien kokonaislukuaritmeettisten operaatioiden latenssi on neljä sykliä, kuinka monta vertaa molempien toteutusten tarvitsemien datan pysäytyssyklien määrää.
b.
Kirjoita uudelleen kiinteän pisteen yhteenlaskumakron inline-kokoonpanoversio ajoittamaan käskyt siten, että riippuvaiset käskyt on erotettu toisistaan niin paljon kuin mahdollista. Missä määrin pysähtymiset vähenevät, kun oletetaan osassa a annettu latenssi?
c.
Kirjoita koodi, joka osoittaa, miten kaikkia kolmea toteutusta (kääntäjän luoma, rivikokoonpano ja ajastettu rivikokoonpano) voidaan luonnehtia suorituskyvyn kannalta.
Tässä kysymyksessä tarkastellaan kohdassa 3.6.6 kuvatun yleistetyn kiintopistekertolaskennan inline-kokoonpanototeutusta.
a.
Miten se vertautuu käskyjen määrän ja ajonaikaisen suorituskyvyn suhteen vastaavaan kääntäjän tuottamaan koodiin:
res = (((long long)op1 * (long long long)op2) >> (rp1>rp2?rp1:rp2))) +(rp1>rp2 ? ((((long long)op1 * (long long long)op2) >> (rp1-1))&1) :
((((long long)op1 * (long long long)op2) >> (rp2-1))&1))));
Varmista, että käytät kytkimiä ”-O3” ja ”-marm” kääntäessäsi gcc:llä.
b.
Suunnittele multiply-makron rivikokoonpanoversion käskyjä minimoidaksesi datariippuvuuden aiheuttamat pysähtymiset. Mittaa sen suorituskyky suhteessa kappaleessa 3.6.6 annettuun versioon.
c.
Kuinka paljon enemmän inline assembly -toteutuksessa saavutetaan kauttaaltaan, jos sitä muutetaan siten, että radix-pisteiden sijainnit ovat kiinteitä sen sijaan, että ne olisivat muuttuvia kuten koodissa? Käytä tässä kysymyksessä sekä ohjeiden lukumäärää että todellista ajoaikakäyttäytymistä.
Mandelbrot-joukon pikseliarvojen laskeminen edellyttää funktiota, jolla iteraatioluku muunnetaan R-, G- ja B-värikanaviksi. Kaikkien kolmen kanavan asettaminen samaan arvoon tuottaa harmaan kuvan, joten kunkin värikanavan funktion kaltevuuden tulisi olla yksilöllinen, ja se, kumpi kaltevuus on suurin, määrittää kuvan värisävyn.
Kuten luvussa 3.8.1 on kuvattu, polynomin evaluointien määrä voi olla suurempi kuin värikanavan vaihteluvälin ylittävä arvo. Mahdollisen ylivuodon välttämiseksi sinun on käytettävä kyllästävää aritmetiikkaa laskiessasi kutakin pikseliarvoa. Tällä tavoin, jos laskettu arvo ylittää suurimman sallitun arvon, se asetetaan suurimpaan arvoon.
Kirjoita C-makro, joka suorittaa 8-bittisen ennenmerkittömän saturoivan kertolaskun. Funktio ottaa kaksi 8-bittistä operandia ja tuottaa 8-bittisen tuloksen, joka asetetaan arvoon 255, jos tulo ylittää arvon 255. Makro ei saa sisältää haarautumiskäskyjä, ja se on ajoitettava datariippuvuuksien varalta.
Tässä harjoituksessa tutkitaan Mandelbrot-generaattorin kiintopistetyyppien tarkkuuden kasvattamista 64-bittiseksi.
a.
Käyttäen zoomausnopeutta 1.5zoom, mihin tasoon kehystä voidaan zoomata ennen kuin tarkkuus ylitetään?
b.
Määrittele C:ssä makro, jolla voidaan laskea yhteen kahta kiinteäpisteistä arvoa 64,56. Makro voi suorittaa 128-bittisen yhteenlaskun käyttämällä neljää 32-bittistä yhteenlaskua ja käyttää siirtolippua toteuttaakseen siirrot jokaisesta 32-bittisestä ryhmästä seuraavaksi merkitsevimpään 32-bittiseen ryhmään.
c.
Määrittele makro C:ssä kahden (64,56)-kiintopistemäärän kertomista varten. Rakenna tämä makro osan b 64-bittisen add-makron päälle.
Kuten kuvassa 3.6 on esitetty, yksinkertainen tapa suorittaa 64-bittinen kertolasku on suorittaa sarja neljää 32-bittistä kerto-/siirto-/kertolaskuoperaatiota, jotka kukin tuottavat 64-bittisen tuloksen.
Kuva 3.6. 8-bittinen kertoja, joka on toteutettu 4-bittisillä kertojilla.
Kuvassa kaksi 4-bittistä arvoa A ja B, jotka pitävät hallussaan arvoja 1110 ja 1410, on kumpikin erotettu kahteen 2-bittiseen ylä- ja alaosaan, jotka on nimetty A1, A0 ja B1 ja B0. Olettaen, että tuotteet ovat 4-bittisiä, 8-bittinen tuote lasketaan seuraavasti: (A1*B1) ≪ 4 + (A1*B0) ≪ 2 + (A0*B1) ≪ 2 + (A0*B0).
Jos tätä halutaan soveltaa 64-bittiseen kerrannaislukuun, kumpikin kahdesta 64-bittisestä arvosta on pidettävä kahdessa 32-bittisessä rekisterissä. Jokainen kertolasku tuottaa 64-bittisen tuloksen, mikä mahdollistaa 128-bittisen lopputuotteen.
d.
Toteuta näiden makrojen avulla 64-bittinen Mandelbrot-joukon generaattori ja mittaa tuloksena syntyvä suorituskykyero.
e.
Toteuta molemmat makrot inline-kokoonpanokielellä ja mittaa Mandelbrot-joukon generaattorin tuloksen nopeutuminen verrattuna d-osan nopeutumiseen.