Rinnakkaisen ohjelmakoodin analysointi

Muutamia määritelmää

• Flop: Floating-point operation, liukulukuoperaatio
• Flops: Flop/s, liukulukuoperaatiota sekunnissa
• Mop: Memory operation, muistioperaatio, luku tai kirjoitus
• Mops: Mop/s, muistioperaatiota sekunnissa

Suoritusnopeus (execution speed)

• Olkoon \(W\) tehtävän työmäärä (workload) ja \(T\) on tehtävän suoritusaika
• Tällöin suoritusnopeus on

\[ v = \frac{W}{T} \]

• Työkuormaa voidaan mitata esimerkiksi liukulukuoperaatioina (Flop), jolloin suoritusnopeuden yksikö olisi Flop/s eli Flops

Latenssi (latency)

• Latenssi määritellään suoritusnopeuden käänteislukuna: \[ L = \frac{1}{v} = \frac{T}{W} \]
• Latenssi kertoo siis paljonko työmäärän tekemiseen kuluu aikaa

Suoritusteho (throughput)

• Olkoon \(\rho\) suoritustiheys (execution density) ja \(A\) suorituskapasiteetti (execution capacity)
• Tällöin suoritusteho on

\[ Q = \rho vA = \frac{\rho AW}{T} = \frac{\rho A}{L} \]

Esimerkki suoritustehon laskemisesta

• Olkoon
  • \(\rho\) = yhteen käskyyn sisältyvien liukulukuoperaatioiden määrä,
  • \(v\) = yhden prosessoriytimen yhden sekunnin aikana suorittamien käskyjen määrä ja
  • \(A\) = prosessoriytimien määrä.
• Tällöin
  • suoritustehon yksikkö olisi Flops ja
  • suoritusteho antaisi laitteiston teoreettisen laskentatehon eli montako liukulukuoperaatiota laitteisto kykenee (ideaaliolosuhteissa) suorittamaan sekunnin aikana.

Esimerkki suoritustehon laskemisesta (jatkuu)

• Tarkastellaan Nvidian Tesla K40c -näytönohjainta:
  • \(\rho = 2 \frac{\text{Flop}}{\text{käsky}}\) (fused multiply–add käsky, johon sisältyy yksi kertolasku ja yksi yhteenlasku)
  • \(v = 1 \frac{\text{ käsky}}{\text{kellojakso}} \times 0.745 \text{Ghz}\) (yksi käsky per kellojakso @ 0.745 Ghz)
  • \(A = 15 \times 64 = 960\) (15 laskentayksikköä, joista jokaisessa 64 prosessointielementtiä / ydintä)
• Suoritustehoksi saadaan siis \[ Q = 2 \frac{\text{Flop}}{\text{käsky}} \times 1 \frac{\text{ käsky}}{\text{kellojakso}} \times 0.745 \text{Ghz} \times 690 \approx 1430 \text{ GFlops} \]

Huomautus liittyen latenssiin ja suoritustehoon

• Latessi ja suoritusteho voivat liittyä käytettyyn laitteistoon tai kehitettyyn ohjelmakoodiin
• Laitteiston tapauksessa työmäärän yksikkö on tyypillisesti Flop, Mop tai tavu
• Ohjelmiston tapauksessa työmäärän yksikkö voi olla esimerkiksi lineaarinen yhtälöryhmä tai valokuva
  • Latenssi kertoisi tällöin yhtälöryhmän ratkaisemiseen tai valokuvan käsittelyyn kuluneen ajan
  • Suoritusteho voisi kertoa esimerkiksi montako yhtälöryhmää voidaan ratkaista tai montako valokuvaa voidaan käsitellä sekunnissa

Nopeutus (speedup)

• Nopeutus latenssin mielessä määritellään seuraavasti: \[ S_{l} = \frac{L_1}{L_2} = \frac{T_1 W_2}{T_2 W_1}, \] jossa \(L_1\) ja \(L_2\) ovat kaksi vertailtavaa tapausta
• Nopeutus \(S_{l}\) kertoo kuinka paljon nopeampi tapaus \(L_2\) on verrattuna tapaukseen \(L_1\)
• Nopeutus \(S_{l}\) ottaa huomioon suoritusajan ja työmäärän

Rinnakkaistamiseen liittyvä nopeutus

• Yksinkertaisemmassa tapauksessa voisimme vertailla sarjamuotoisen ja rinnakkaisen toteutuksen kykyä käsitellä sama työmäärä
• Olkoon \(T_{s}\) sarjamuotoisen toteutuksen työmäärän \(W\) käsittelyyn käyttämä seinäkelloaika ja \(T_{r}\) rinnakkaisen toteutuksen saman työmäärän käsittelyyn käyttämä seinäkelloaika. Tällöin saavutettu nopeutus on \[ S_{l} = \frac{T_{s} W}{T_{r} W} = \frac{T_{s}}{T_{r}}. \]
• Nopeutus kertoo siis kuinka paljon nopeampi rinnakkainen toteutus on verrattuna sarjamuotoiseen toteutukseen. Vertailu pitää tehdä tarkastellulle alustalle parasta sarjamuotoista toteutusta käyttäen! Joskus parhaiten rinnakkaistuva algoritmi on jopa laskentamäärältään asymptoottisesti vaativampi kuin paras peräkkäinen algoritmi!

Havaittu nopeutus (Observed speedup)

• Olkoon \(w_{s}\) rinnakkaisen toteutuksen käyttämä seinäkelloaika sarjalaskennassa (suoritettu yhdellä laskentayksiköllä)
• Olkoon \(w_{rn}\) rinnakkaisen toteutuksen käyttämä seinäkelloaika rinnakkaislaskennassa (suoritettu useammalla laskentayksiköllä)
• Tällöin havaittu nopeutus on \[ S_h = \frac{w_{s}}{w_{r}} \]
• Havaittu nopeutus on ehkä suosituin nopeutusta mittaava indikaattori

Nopeutus työtehon mielessä

• Nopeutus työtehon mielessä määritellään seuraavasti: \[ S_{tt} = \frac{Q_2}{Q_1} = \frac{\rho_2 A_2 T_1 W_2}{\rho_1 A_1 T_2 W_1} = \frac{\rho_2 A_2}{\rho_1 A_1} S_l, \] jossa \(Q_1\) ja \(Q_2\) ovat kaksi vertailtavaa tapausta
• Nopeutus \(S_{tt}\) kertoo kuinka paljon nopeampi tapaus \(Q_2\) on verrattuna tapaukseen \(Q_1\)

Esimerkki suoritustehoon liittyvän nopeutuksen käytöstä

• Olkoon
  • \(S_l\) = latenssiin liittyvä nopeutus kun vertaillaan alustan 1 prosessoriytimen ja alustan 2 prosessoriytimen yhden sekunnin aikana suorittamien käskyjen määrää
  • \(\rho_i\) = yhteen käskyyn sisältyvien liukulukuoperaatioiden määrä alustalla \(i\)
  • \(A_i\) = prosessoriytimien määrä alustassa \(i\)
• Tällöin suoritustehoon liittyvä latenssi kertoisi kuinka paljon enemmän Flop'peja alusta 2 voi käsitellä sekunnissa kuin alusta 1

Esimerkki suoritustehoon liittyvän nopeutuksen käytöstä (jatkuu)

• Tarkastellaan Nvidian GeForce GTX580 ja Tesla K40c näytönohjaimia:
  • \(S_l = L_{\text{GTX580}} / L_{\text{K40c}} = \frac{0.745 \text{ Ghz}}{1/8 \times 1.544 \text{ Ghz}} \approx 3.86\) (laskennallinen arvio)
  • \(\rho_{\text{GTX580}} = \rho_{\text{K40c}} = 2 \text{ Flop}/\text{käsky}\)
  • \(A_{\text{GTX580}} = 16 \times 32 = 512\), \(A_{\text{K40c}} = 15 \times 64 = 960\)
• Tällöin \[ S_{tt} = \frac{2 \text{ Flop}/\text{käsky} \times 960}{2 \text{ Flop}/\text{käsky} \times 512} \times 3.86 \approx 7.2 \] eli K40c on noin 7.2 kertaa nopeampi kuin GTX580

Tehokkuus (Efficiency)

• Tarkastellaan tilannetta, jossa tehtävän suorittamiseen käytettävien resussien määrää on kasvatettu
• Olkoon \(S\) tehtävän yhteydessä esiintynyt kokonaisnopeutus (latenssi, havaittu tai työteho) ja alkoon \(s\) resurssien lisäämisestä hyötyneen tehtävän osan nopeutus (latenssi, havaittu tai työteho)
• Tällöin tehokkuus määritellään: \[ \eta = S/s \]
• Parhaassa tapauksessa \(\eta = 1 = 100\%\)

Tehokkuus rinnakkaislaskennassa

• Rinnakkaislaskennan tapauksessa voidaan tarkastella \(N\):n prosessoriytimen tuomaa tehokkuutta
• Oletaan, että \(s = N\) (rinnakkaistamisesta hyötyvän osan tehokkuus on 100%)
• Tällöin voimme määritellä prosessoriytimien määrästä riippuvan tehokkuuden: \[ \eta(N) = S(N)/N, \] jossa \(S(N)\) on \(N\):nän prosessoriytimen avulla saavutettu nopeutus verrattuna yhteen prosessoriytimeen

Superlineaarinen nopeutus

• On olemassa tilanteita, joissa \(1 < \eta\). Tällöin puhutaan superlineaarisesta nopeutuksesta.
• Esimerkkitilanne: Työmäärä jaetaan niin moneen osaan, että yhdelle rinnakkaiselle tehtävälle kuuluva data mahtuu kokonaan prosessorin välimuistiin (ja muut saman välimuistin jakavat tehtävät eivät merkittävissä määrin kilpaile samoista välimuistiriveistä). Tällöin efektiivinen muistikaista ja muistin latenssi saattavat muuttua useamman kertaluokan verran, joka johtaa nopeutuksen superlineaariseen käytökseen rinnakkaisien tehtävien funktiona.

Karkea havainnekuva superlineaarisesta käytöksestä

Amdahlin laki

• Johdetaan seuraavaksi kuuluisa Amdahlin laki, joka antaa teoreettisen (latenssiin liittyvän) nopeutuksen kun tehtävän työmäärä pysyy samana (\(W_1 = W_2 = W\))
• Olkoon \(T_1\) - resurssien kasvatusta edeltävä - tehtävän kokonaissuoritusaika ja olkoon \(p\) resurssien lisäämisestä hyötyvän osan osuus \(T_1\):stä eli \[ T_1 = (1-p)T_1 + \underbrace{p T_1}_{=: T_p}, \; 0 \leq p \leq 1 \]

Amdahlin lain johtaminen (jatkuu)

• Oletetaan seuraavaksi, että resurssien lisäämisestä hyötyvän tehtävän osan (latenssiin liittyvä) nopeutus on \(S_p\) eli \[ S_p = \frac{T_p W_p}{\hat{T}_p W_p} \iff \hat{T}_p = \frac{T_p}{S_p}, \] jossa \(W_p\) on resurssien lisäämisestä hyötyvän osan työmäärä ja \(\hat{T}\) on resurssien lisäämisestä hyötyvän tehtävän osan suoritusaika resurssien lisäämisen jälkeen

Amdahlin lain johtaminen (jatkuu)

• Nyt tiedämme, että resurssien lisäämisen jälkeinen tehtävän kokonaissuoritusaika on \[ \begin{align} T_2 &= (1-p)T_1 + \hat{T}_p = (1-p)T_1 + \frac{T_p}{S_p} \\ &= (1-p)T_1 + \frac{p T_1}{S_p} \end{align} \]

Amdahlin lain johtaminen (jatkuu)

• Koko tehtävän (latenssiin liittyväksi) nopeutukseksi saadaan siis \[ S_l = \frac{T_1 W}{T_2 W} = \frac{(1-p)T_1+pT_1}{(1-p)T_1 + \frac{pT_1}{S_p}} \]
• Sieventämällä saadaan Amdahlin laki: \[ S_l = \frac{1}{(1-p)+p/S_p} \]

Amdahlin laki rinnakkaislaskennassa

• Amdahlin laki kertoo muun muassa paljonko ohjelmakoodia voidaan potentiaalisesti nopeuttaa \(N\):n prosessoriytimen avulla
• Oletaan, että \(S_p = N\) (rinnakkaistamisesta hyötyvän osan tehokkuus on 100%)
• Tällöin \(N\):n prosessoriytimien avulla saavutettavissa oleva nopeutus on \[ S_l(N) = \frac{1}{(1-p) + p/N} \]

Amdahlin lain seuraukset

• Ensin havaitaan, että \[ S_l(S_p) = \frac{1}{(1-p)+p/S_p} \leq \frac{1}{1-p} \]
• Lisäksi \[ \lim_{N \to \infty} S_l(S_p) = \lim_{N \to \infty} \frac{1}{(1-p) + p/S_p} = \frac{1}{1-p} \]
• Suurin mahdollinen nopeutus on siis \(\frac{1}{1-p}\)

Amdahlin lain seuraukset (jatkuu)

• Amdahlin seurauksena tehokkuudeksi saadaan \[ \eta(S_p) = S_l(S_p)/S_p = \frac{1}{(1-p) S_p + p} \]
• Erityisesti \[ \lim_{S_p \to \infty} \eta(S_p) = \begin{cases} 1 &, \text{kun } p = 1 \\ 0 &, \text{kun } p < 1 \end{cases} \]
• Käytännössä \(p < 1\) eli resurssien lisäämisestä saatavat hyödyt noudattavat vähenevän tuoton lakia

Amdahlin lain käytös eri \(p\):n arvoilla

Amdahlin lain ennustaman tehokkuuden käytös eri \(p\):n arvoilla

Gustafsonin laki

• Johdetaan seuraavaksi Gustafsonin laki, joka antaa teoreettisen (latenssiin liittyvän) nopeutuksen kun tehtävän suoritusaika pysyy samana (\(T_1 = T_2 = T\))
• Olkoon \(W_1\) - resurssien kasvatusta edeltävä - tehtävän ajassa \(T\) suorittama työmäärä ja olkoon \(p\) resurssien lisäämisestä hyötyvän osan osuus \(W_1\):stä eli \[ W_1 = (1-p)W_1 + \underbrace{p W_1}_{=: W_p}, \; 0 \leq p \leq 1 \]

Gustafsonin lain johtaminen (jatkuu)

• Oletetaan seuraavaksi, että tehtävän resurssien lisäämisestä hyötyvän osan (latenssiin liittyvä) nopeutus on \(S_p\) eli \[ S_p = \frac{T_p \hat{W}_p}{T_p W_p} \iff \hat{W}_p = S_p W_p, \] jossa \(T_p\) on resurssien lisäämisestä hyötyvän osan suoritusaika ja \(\hat{W}_p\) on resurssien lisäämisestä hyötyvän osan tekemä työmäärä ajassa \(T_p\) resurssien lisäämisen jälkeen

Gustafsonin lain johtaminen (jatkuu)

• Nyt tiedämme, että resurssien lisäämisen jälkeinen tehtävän tekemä työmäärä on \[ \begin{align} W_2 &= (1-p)W_1 + \hat{W}_p = (1-p)W_1 + S_p W_p \\ &= (1-p)W_1 + S_p p W_1 \end{align} \]

Gustafsonin lain johtaminen (jatkuu)

• Koko tehtävän (latenssiin liittyväksi) nopeutukseksi saadaan siis \[ S_l = \frac{T W_2}{T W_1} = \frac{(1-p)W_1+S_p p W_1}{(1-p)W_1 + pW_1} \]
• Siventämällä saadaan Gustafsonin laki: \[ S_l = 1 - p + S_p p \]

Gustafsonin laki rinnakkaislaskennassa

• Gustafsonin laki kertoo muun muassa paljonko ohjelmakoodia voidaan potentiaalisesti nopeuttaa \(N\):n prosessoriytimen avulla
• Oletaan, että \(S_p = N\) (rinnakkaistamisesta hyötyvän osan tehokkuus on 100%)
• Tällöin \(N\):n prosessoriytimien avulla saavutettavissa oleva nopeutus on \[ S_l(N) = 1 - p + Np \]

Gustafsonin lain seuraukset

• Gustafsonin seurauksena tehokkuudeksi saadaan \[ \eta(S_p) = S_l(S_p)/S_p = \frac{1-p}{S_p} + p \]
• Erityisesti \[ p \leq \eta(S_p) \leq 1 \; \text{ ja } \; \lim_{S_p \to \infty} \eta(S_p) = p \]

Gustafsonin lain käytös eri \(p\):n arvoilla

Gustafsonin lain ennustaman tehokkuuden käytös eri \(p\):n arvoilla

Huomautus Amdahlin ja Gustafsonin lakeihin liittyen

• Amdahlin laki kertoo kuinka paljon nopeammin tehtävä voidaan ratkaista resurssien lisäämisen jälkeen. Työmäärä pysyy samana.
• Gustafsonin laki kertoo kuinka paljon enemmän tehtäviä voidaan ratkaista saman ajanjakson aikana resurssien lisäämisen jälkeen. Suoritusaika pysyy samana.
• Amdahlin ja Gustafsonin lait antavat teoreettisen ylärajan nopeutukselle, oikeassa elämässä nopeutukset ovat pienempiä!

Skaalautuvuus (scalability)

• Skaalautuvuus on ohjelmiston tai laitteiston kyky osoittaa suorituskyvyn suhteellista kasvua laskentaresurssien määrän kasvaessa: lisää tehoa \(\implies\) lisää vauhtia
• Skaalautuvuuteen vaikuttavat tekijät: algoritmin luonne, laitteisto (esim. muistikaista ja verkko), parallel overhead
• Skaalautuvuutta voidaan mitata:
  • vahvalla skaalautuvuudella
  • heikkolla skaalautuvuudella

Vahva skaalautuvuus (strong scalability)

• Vahvan skaalautumisen tapauksessa työmäärä pysyy samana, mutta rinnakkaisien tehtävien / prosessoriytimien määrä muuttuu
• Olkoon \(T_1\) toteutuksen käyttämä seinäkelloaika yhdellä prosessoriytimellä suoritettuna, olkoon \(N\) käytettyjen prosessoriytimien määrä ja olkoon \(T_N\) toteutuksen käyttämä seinäkelloaika \(N\):nällä prosessoriytimellä suoritettuna
• Tällöin vahva skaalautuvuus määritellään seuraavasti: \[ s_{vahva} = \frac{T_1}{N T_N} \times 100\% \]

Lisää vahvasta skaalautuvuudesta

• Amdahlin laki ja erityisesti siitä johdettu tehokkuus ennustavat vahvan skaalautuvuuden käytöstä
• Vahvaa skaalautuvuutta käytetään tyypillisesti tilanteissa, joissa laskennan hienojakoisuus on karkea ja tehtävän suoritusaika on pitkä
• Vahvan skaalautuvuuden avulla on mahdollista löytää ns. "sweet spot" eli määrä prosessoriytimiä, jolla tehtävä voidaan ratkaista nopeasti parallel overheadin määrän pysyessä edelleen mielekkäänä

Esimerkki vahvasta skaalautuvuudesta

#define N 10000000
...
void axpy(double *y, const double *x, double a, int n) {
    #pragma omp parallel for
    for(int i = 0; i < n; i++)
        y[i] = a * x[i] + y[i];
}
...
axpy(x, y, a, N);

$ for((i=1;i<=12;i++)); do OMP_NUM_THREADS=$i ./strong; done
Suoritusaika 1 säikeellä: 0.0114419
Suoritusaika 2 säikeellä: 0.00692391
Suoritusaika 3 säikeellä: 0.00632405
Suoritusaika 4 säikeellä: 0.006181
...

Esimerkki vahvasta skaalautuvuudesta (jatkuu)

Heikko skaalautuvuus (weak scalability)

• Heikon skalautuvuuden tapauksessa yksittäisen prosessoriytimen tekemä työmäärä pysyy samana, mutta prosessoriytimien määrä muuttuu
• Olkoon \(T_1\) toteutuksen käyttämä seinäkelloaika yhdellä prosessoriytimellä suoritettuna ja olkoon \(T_N\) toteutuksen käyttämä seinäkelloaika \(N\):nällä prosessoriytimellä suoritettuna
• Tällöin heikko skaalautuvuus määritellään seuraavasti: \[ s_{heikko} = \frac{T_1}{T_N} \times 100\% \]

Lisää heikosta skaalautuvuudesta

• Gustafsonin laki ja erityisesti siitä johdettu tehokkuus ennustavat heikon skaalautuvuuden käytöstä
• Heikkoa skaalautuvuutta käytetään tyypillisesti tilanteissa, joissa tehtävä käyttää paljon muistia ja muita resursseja
• Ohjelmat joissa kommunikointi tapahtuu ns. lähimpien naapureiden välillä skaalautuvat yleensä hyvin heikossa mielessä, globaalia kommunikointia käyttävät taas eivät

Esimerkki heikosta skaalautuvuudesta

#define N 10000000
...
void axpy(double *y, const double *x, double a, int n) {
    #pragma omp parallel for
	for(int i = 0; i < n; i++)
		y[i] = a * x[i] + y[i];
}
...
int n = threadCount*N; // Säikeen tekemä työ pysyy vakiona
...
axpy(x, y, a, n);

$ for((i=1;i<=12;i++)); do OMP_NUM_THREADS=$i ./weak; done
Suoritusaika 1 säikeellä: 0.0115819
Suoritusaika 2 säikeellä: 0.013674
Suoritusaika 3 säikeellä: 0.0196369
Suoritusaika 4 säikeellä: 0.024848
...

Esimerkki heikosta skaalautuvuudesta (jatkuu)

Roofline-malli

• Roofline-malli on analysointityökalu, joka ottaa teoreettisen laskentatehon (laskentaan liittyvä suoritusteho) lisäksi huomioon myöskin käytettävissä olevan muistikaistan (datan siirtoon liittyvä suoritusteho)
• Muistikaistan huomioon ottaminen on tärkeää erityisesti moniydinprosessorien yhteydessä sillä käytettävissä oleva muistikaista ei välttämättä kasva samassa tahdissa ytimien määrän kanssa
• Tällöin törmätään herkästi tilantaisiin, joissa saavutettu laskentateho jää kauas teoreettisesta maksimista

Lisää motivaatiota

• Esimerkiksi luentomonisteen alkupuolella esitetyssä CUDA-esimerkissä päästiin pelkästään vajaaseen 200 GFlopsin laskentatehoon vaikka Nvidian Tesla K40c -näytönohjaimen teoreettinen tuplatakkuuslaskentateho on 1430 GFlops
• Roofline-malli ennustaa saavutettavissa olevan laskentatehon \(\Lambda\)
• Malli sisältää kaksi käytettävästä laitteistosta riippuvaa ylärajaa saavutettavissa olevalle laskentateholle: \(\gamma_1\) ja \(\gamma_2\)
• Varsinainen saavutettu laskentateho \(\lambda\) mitataan empiirisesti

Operaatiointensiteetti ja laskentateho

• Roofline-malli esitetään yleensä log-log-skaalaisena pistekaaviona:
  • x-akselilta löytyy ns. operaatiointensiteetti (operational intensity)
  • y-akselilta löytyy laskentateho

Operaatiointensiteetti ja laskentateho (jatkuu)

• Operaatiointensiteetti (\(\tau\)) ottaa huomioon laskentakapasiteetin ja käytettävissä olevan muistikaistan
• Tarkemmiin sanottuna \(\tau\) on määritelty seuraavasti: \[ \tau = \frac{\text{laskentaoperaatioiden määrä [Flop]}}{\text{siirretty data [Byte]}} \]

Ylärajat

• Ensimmäinen yläraja on laitteiston teoreettinen laskentateho (\(\Gamma\)): \[ \gamma_1(\tau) = \Gamma \]

Ylärajat (jatkuu)

• Toinen yläraja riippuu laitteiston teoreettisesta muistikaistasta (\(\Delta\)): \[ \gamma_2(\tau) = \Delta \times \tau \]

Laitteiston tasapainopiste

• Jokaiselle laitteistolle voidaan laskea tasapainopiste (\(\Phi\)): \[ \Phi = \frac{\Gamma}{\Delta} \]
• Tasapainopiste voidaan piirtää koordinaateihin \((\Phi, \Gamma)\):

Menetelmän operaatiointensiteetti

• Numeerisen menetelmän operaatiointensiteetti (\(\upsilon\)) saadaan selville laskemalla menetelmässä esiintyneet liukulukuoperaatiot ja siirretty datamäärä
• Olkoon \(F_{count}\) ohjelman sisältyvien laskentaoperaatioiden määrä ja \(M_{bytes}\) siirretyn datan määrä tavuina. Tällöin \[ \upsilon = \frac{F_{count}}{M_{bytes}}. \]

Menetelmän operaatiointensiteetti (jatkuu)

• Kolme mahdollisuutta:
  • \(\upsilon < \Phi\): Yläraja \(\gamma_2\) dominoi, menetelmä on muistikaistarajoitteinen
  • \(\upsilon > \Phi\): Yläraja \(\gamma_1\) dominoi, menetelmä on laskentatehorajoitteinen
  • \(\upsilon = \Phi\): Kumpikin yläraja on voimassa, menetelmä on sekä muisti- että laskentatehorajoitteinen
• Menetelmän saavutettavissa oleva laskentateho on \[ \Lambda = \min (\gamma_1(\upsilon), \gamma_2(\upsilon)) \]

Menetelmän operaatiointensiteetti (jatkuu)

• Menetelmän operaatiointensiteetti voidaan piirtää kuvaan nuolena \((\upsilon, 0) \to (\upsilon, \Lambda)\)

Menetelmän operaatiointensiteetti (jatkuu)

• Visuaalinen tulkinta:
  • nuoli laitteiston tasapainopisteen vasemmalla puolella \(\implies\) muistikaistarajoitteinen
  • nuoli laitteiston tasapainopisteen oikealla puolella \(\implies\) laskentatehorajoitteinen

Saavutettu laskentateho

• Saavutettu laskentateho (\(\lambda\)) mitataan empiirisesti ja piirretään kuvaajaan koordinaatteihin \((\upsilon, \lambda)\):

Saavutettu laskentateho (jatkuu)

• Helpoin tapa \(\lambda\):n laskemiseksi on mitata ohjelman suoritusaika (\(t\)), jolloin \[ \lambda = \frac{F_{count}}{t} \]
• Saavutetun laskentatehon tulisi olla lähellä saavutettavissa olevaa laskentatehoa

Miksi roofline-malli toimii?

• Laskentaa sisältävä ohjelman osuus voidaan käsitellä parhaimmassa tapauksessa ajassa \[ t_{F} = \frac{F_{count}}{\Gamma} \] ja datan siirtoa käsittelevä osuus voidaan vastaavasti käsitellä ajassa \[ t_{M} = \frac{M_{bytes}}{\Delta} \]

Miksi roofline-malli toimii? (jatkuu)

• Mikäli \(t_{F} < t_{M}\), saadaan saavutettavissa olevaksi laskentatehoksi \[ \Lambda = \frac{F_{count}}{t_{M}} = \frac{F_{count}}{M_{bytes}/\Delta} = \Delta \times \upsilon, \] joka vastaa ylärajaa \(\gamma_2\)
• Jos taas \(t_{M} < t_{F}\), saadaan saavutettavissa olevaksi laskentatehoksi \[ \Lambda = \frac{F_{count}}{T_{F}} = \frac{F_{count}}{F_{count}/\Gamma} = \Gamma, \] joka vastaa ylärajaa \(\gamma_1\)

Huomautuksia roofline-mallin liittyen

• Malliin voidaan piirtää lisää ylärajoja. Esimerkiksi:
  • Erillinen yläraja tilanteissa, joissa ECC-muisti rajoittaa muistikaistaa
  • Erillinen yläraja tilanteissa, joissa voidaan hyödyntää FMA-käskyä tai AVX-käskykantalaajennosta (vektorilaskentaa)
• Samaan malliin voi sisällyttää useita mittauspisteitä
• Teoreettisen laskentatehon ja muistikaistan lisäksi suorituskykyyn vaikuttavat myös monet muutkin tekijät. Tämän takia käytäntö ei välttämättä vastaa teoriaa.

Esimerkki roofline-mallista (Nvidia GeForce GTX580)