Architektury poˇ c´ıtaˇ cov´ ych syst´ em˚ u
Katedra informatiky a v´ypoˇcetn´ı techniky ˇ e vysok´e uˇcen´ı technick´e, fakulta elektrotechnick´a Cesk´
Vektorov´e poˇc´ıtaˇce Ing. Tom´aˇs Zahradnick´y doc. Ing. R´obert L´orencz, CSc.
10. prosince 2007 Ing. Tom´ aˇs Zahradnick´ y doc. Ing. R´ obert L´ orencz, CSc. Vektorov´ e poˇ c´ıtaˇ ce
Architektury poˇ c´ıtaˇ cov´ ych syst´ em˚ u
Pamˇet’ov´e banky S v´yhodou pouˇz´ıv´ame pamˇet’ s prokl´ adan´ ym cyklem pro urychlen´ı pˇr´ıstupu. Souˇcasnˇe se tak ˇcte z n pamˇet’ov´ych bank a rychlost ˇcten´ı je tedy cca n−n´asobn´a. Rychlost ˇcten´ı je tak´e ovlivnˇena stˇr´ıdou. Pˇr´ıklad: Uvaˇzujme pamˇet’ se 4 bankami s prokl´adan´ym cyklem obsahuj´ıc´ı vektor V se stˇr´ıdou (stride) s = 7. 1. Naznaˇcte um´ıstˇen´ı prvn´ıch ˇctyˇr sloˇzek vektoru v pamˇet’ov´ych bank´ach, pokud je sloˇzka V [0] um´ıstˇena v modulu ˇc. 2. 2. Napiˇste formuli urˇcuj´ıc´ı ˇc´ıslo pamˇet’ov´eho modulu, ve kter´em bude um´ıstˇena sloˇzka V [i] (moduly jsou ˇc´ıslov´any od 0).
Ing. Tom´ aˇs Zahradnick´ y doc. Ing. R´ obert L´ orencz, CSc. Vektorov´ e poˇ c´ıtaˇ ce
Architektury poˇ c´ıtaˇ cov´ ych syst´ em˚ u
Pamˇet’ov´e banky, pokraˇcov´an´ı ˇ sen´ı: Reˇ 2, V[0]
1. Viz obr´azek. Kaˇzd´y prvek vektoru V [i] oznaˇcen vˇcetnˇe jeho adresy v pamˇeti. 2. Sloˇzka V [i] m´a adresu a = 2 + 7i (V [0] je v bance 2 a stˇr´ıda je 7). Danou banku b vypoˇcteme jako zbytek po dˇelen´ı adresy a poˇctem bank:
9, V[1]
16, V[2] 23, V[3]
30, V[4]
0
a ≡ b (mod 4).
Ing. Tom´ aˇs Zahradnick´ y doc. Ing. R´ obert L´ orencz, CSc. Vektorov´ e poˇ c´ıtaˇ ce
1
2
3
Obr´azek: Um´ıstˇen´ı sloˇzek vektoru
Architektury poˇ c´ıtaˇ cov´ ych syst´ em˚ u
Gather & Scatter I Instrukce cvi v1, r1 uloˇz´ı do registru v1 takov´e adresy element˚ u d´elky r1, kter´e odpov´ıdaj´ı nastaven´ym bit˚ um ve vektorov´em maskovac´ım registru vm, 0 ≤ i ≤ vlr. Pˇr´ıklad: Jak´y bude v´ysledek pro r1 = 7 a vm = 0x93. ˇ sen´ı: v1 = [0, 7, 28, 49]. Reˇ vm
1
0
0
1
0
0
1 1
i · r1 49 42 35 28 21 14 7 0 vm[i] · i · r1 49
0
0
28
0
0
7 0
Pozn´ amka: Tento pˇr´ıklad oˇcek´av´a pamˇet’ orientovanou po bytech. Norm´alnˇe b´yv´a velikost prvku mocninou 2. Ing. Tom´ aˇs Zahradnick´ y doc. Ing. R´ obert L´ orencz, CSc. Vektorov´ e poˇ c´ıtaˇ ce
Architektury poˇ c´ıtaˇ cov´ ych syst´ em˚ u
Gather & Scatter II Techniky gather a scatter slouˇz´ı pro manipulaci s ˇr´ıdk´ymi vektory. Pomoc´ı tˇechto instrukc´ı lze snadno pracovat s ˇr´ıdk´ymi maticemi, rozpt´ylen´ymi pamˇet’ov´ymi strukturami, atd. ˇz´adn´a z uveden´ych instrukc´ı se neˇr´ıd´ı obsahem registru vm. Gather: Instrukce lvi v1, r1, v2, prov´ad´ı sbˇer dat a nahraje do registru v1 prvky z relativn´ıch adres, kter´e jsou obsahem vektoru v2 b´azovan´e k r1. Vektor relativn´ıch adres lze z´ıskat napˇr´ıklad pomoc´ı instrukce cvi. v1[i] = M [r1 + v2[i]]. Scatter: Instrukce svi r1, v2, v1 je pˇresn´ym opakem instrukce lvi a slouˇz´ı tedy k rozpt´ylen´ı dat vektoru v1 na adresy specifikovan´e elementy vektoru v2. M [r1 + v2[i]] = v1[i].
Ing. Tom´ aˇs Zahradnick´ y doc. Ing. R´ obert L´ orencz, CSc. Vektorov´ e poˇ c´ıtaˇ ce
Architektury poˇ c´ıtaˇ cov´ ych syst´ em˚ u
Gather & Scatter III Pˇr´ıklad: Nahrajte do registru v1 prvky hlavn´ı diagon´aly ˇctvercov´e matice A dimenze 4 uloˇzen´e v pamˇeti M s poˇc´ateˇcn´ı adresou v r2. Prvky matice jsou cel´a ˇc´ısla a kaˇzd´e z nich zab´ır´a 4 bajty. ˇ sen´ı: Prvky, kter´e chceme maj´ı indexy 0, 5, 10 a 15 a to Reˇ odpov´ıd´a maskovac´ımu vektoru vm = 0x8421. Vygenerujeme adresy prvk˚ u a pouˇzijeme instrukci lvi k naˇcten´ı diagon´aly. 1. Nastav´ıme registr masky vm na hodnotu 0x8421. 2. Nastav´ıme registr r1 na hodnotu 4 (d´elka jednoho elementu). 3. Pouˇzijeme instrukci cvi v1, r1 na v´ypoˇcet relativn´ıch adres prvk˚ u odpov´ıdaj´ıc´ıch masce. 4. Pouˇzijeme instrukci lvi v2, r2, v1 k naˇcten´ı tˇechto prvk˚ u.
Ing. Tom´ aˇs Zahradnick´ y doc. Ing. R´ obert L´ orencz, CSc. Vektorov´ e poˇ c´ıtaˇ ce
Architektury poˇ c´ıtaˇ cov´ ych syst´ em˚ u
ˇ Spetka terminologie Iniciaˇ cn´ı interval (startup): ˇcas potˇrebn´y k nastartov´an´ı dan´e jednotky. Na konci iniciaˇcn´ıho intervalu je jiˇz k dispozici jeden v´ysledek. Konvoj: Mnoˇzina vektorov´ych instrukc´ı, kter´e se mohou zaˇc´ıt vykon´avat v tom sam´em ˇcase (bez struktur´aln´ıch nebo datov´ych hazard˚ u), konvoje se nepˇrekr´yvaj´ı. Chime: Pˇribliˇzn´y ˇcas pro vektorovou operaci. Chaining: V´ystup jedn´e jednotky je pipelineov´an rovnou na vstup druh´e.
Ing. Tom´ aˇs Zahradnick´ y doc. Ing. R´ obert L´ orencz, CSc. Vektorov´ e poˇ c´ıtaˇ ce
Architektury poˇ c´ıtaˇ cov´ ych syst´ em˚ u
DLXV DAXPY Pˇr´ıklad: Vektory X a Y maj´ı d´elku 64 prvk˚ u. Mˇejme smyˇcku DAXPY. Iniciaˇcn´ı intervaly jednotliv´ych jednotek jsou: I jednotka L/S 11 takt˚ u; I sˇ c´ıtaˇcka 5 takt˚ u; I n´ asobiˇcka 6 takt˚ u. D´ale pˇredpokl´adejme, ˇze vektorov´e funkˇcn´ı jednotky generuj´ı nebo konzumuj´ı jeden prvek operandu kaˇzd´y takt. 1. Rozdˇelte instrukce do konvoj˚ u. L/S jednotka je schopna pouze jednoho pˇr´ıstupu do pamˇeti a m´ame pouze jednu n´asobiˇcku. Proved’te s a bez pouˇzit´ı chainingu. 2. Nakreslete diagram zpracov´an´ı a spoˇctˇete kolik takt˚ u pˇripad´a na v´ypoˇcet jednoho prvku v´ysledn´eho vektoru. 3. Urˇcete konfiguraci DLXV aby se dal program prov´est jako jedin´y konvoj. Ing. Tom´ aˇs Zahradnick´ y doc. Ing. R´ obert L´ orencz, CSc. Vektorov´ e poˇ c´ıtaˇ ce
Architektury poˇ c´ıtaˇ cov´ ych syst´ em˚ u
DLXV DAXPY, pokraˇcov´an´ı I lv v1 , multsv v2 , lv v3 , addv v1 , sv (ry),
1. Rozdˇelen´ı do konvoj˚ u: 4, protoˇze 3 L/S instrukce 2. V´ypoˇcet a graf Startup
I
V´ ypoˇ cet
(rx) f0, v1 (ry) v2 , v3 v1
Bez chainingu 74 11
74
68
74
63 6 11
63 63 5
63 11
63
cycCPU = 74 + 74 + 68 + 74 = 290 . To ˇcin´ı pr˚ umˇernˇe 290/64 = 4.53 takt˚ u na element. Ing. Tom´ aˇs Zahradnick´ y doc. Ing. R´ obert L´ orencz, CSc. Vektorov´ e poˇ c´ıtaˇ ce
Architektury poˇ c´ıtaˇ cov´ ych syst´ em˚ u
DLXV DAXPY, pokraˇcov´an´ı II I
S chainingem Vzhledem k tomu, ˇze smyˇcka DAXPY obsahuje 3 L/S instrukce a m´ame k dispozici pouze jednu LS jednotku, mus´ıme ji rozdˇelit do 3 konvoj˚ u n´asleduj´ıc´ım zp˚ usobem: 80 11
79
74
63 6
63 11
63 5
63 11
63
cycCPU = 80 + 79 + 74 = 233 . Pr˚ umˇernˇe 233/64 = 3.64 takt˚ u na element.
Ing. Tom´ aˇs Zahradnick´ y doc. Ing. R´ obert L´ orencz, CSc. Vektorov´ e poˇ c´ıtaˇ ce
Architektury poˇ c´ıtaˇ cov´ ych syst´ em˚ u
DLXV DAXPY, pokraˇcov´an´ı III 3. N´avrh vylepˇsen´ı DLXV Vzhledem k tomu, ˇze nejvˇetˇs´ı probl´em p˚ usob´ı nedostatek L/S jednotek, doporuˇcujeme tedy pˇridat 2 dalˇs´ı L/S jednotky (2×L, 1×S), ˇc´ımˇz by se mohl program prov´est jako jeden konvoj (a nikoliv jako 3 v pˇr´ıpadˇe s chainingem). I
Vylepˇsen´a verze s chainingem s dalˇs´ımi jednotkami 96 11
63 6
63
11
63 5
63 11
63
cycCPU = 11 + 6 + 5 + 11 + 63 = 96 Pr˚ umˇernˇe 96/64 = 1.5 taktu na element.
Ing. Tom´ aˇs Zahradnick´ y doc. Ing. R´ obert L´ orencz, CSc. Vektorov´ e poˇ c´ıtaˇ ce
Architektury poˇ c´ıtaˇ cov´ ych syst´ em˚ u
´ Ukol Pˇr´ıklad: Pro n´asleduj´ıc´ı program (konfigurace viz DAXPY): 1. Rozdˇelte instrukce do konvoj˚ u. L/S jednotka je schopna pouze jednoho pˇr´ıstupu do pamˇeti a m´ame pouze jednu n´asobiˇcku. Proved’te s a bez pouˇzit´ı chainingu. 2. Nakreslete diagram zpracov´an´ı a spoˇctˇete kolik takt˚ u pˇripad´a na v´ypoˇcet jednoho prvku v´ysledn´eho vektoru. 3. Urˇcete konfiguraci DLXV jedin´y konvoj. lv multsv multsv addv sv Ing. Tom´ aˇs Zahradnick´ y doc. Ing. R´ obert L´ orencz, CSc. Vektorov´ e poˇ c´ıtaˇ ce
aby se dal program prov´est jako v1, (rx) v2, f0, v1 v3, f1, v1 v4, v2, v3 (ry), v4
Architektury poˇ c´ıtaˇ cov´ ych syst´ em˚ u
´ Ukol 2I Pˇr´ıklad: Je d´an 32-bitov´y procesor DLXV s jednobr´anovou pamˇet´ı, ˇıˇrka kaˇzd´e banky je 64 bit˚ kter´a je rozdˇelena celkem do 4 bank. S´ u. Latence (vybavovac´ı doba poloˇzky) kaˇzd´e banky je rovna 4 takt˚ um procesoru DLXV. Adresov´e bity A(4:3) urˇcuj´ı ˇc´ıslo banky. Adresov´e bity A(31:5) jsou pˇrivedeny na adresn´ı vstupy kaˇzd´e banky, kde kaˇzd´a banka m´a kapacitu 1 GB v organizaci 128M × 64b. Pozn´ amka: Pro jednoduchost je z kaˇzd´eho 64b ˇc´ısla zobrazeno pouze spodn´ıch 8 bit˚ u.
Ing. Tom´ aˇs Zahradnick´ y doc. Ing. R´ obert L´ orencz, CSc. Vektorov´ e poˇ c´ıtaˇ ce
Architektury poˇ c´ıtaˇ cov´ ych syst´ em˚ u
´ Ukol 2 II A(31:5) 0...00000000 0...00000001 0...00000010 0...00000011 0...00000100
00 01 0A 02 AB AA
A(4:3) 01 10 03 05 0B 0C 04 06 CD DE BB A5
11 07 0D 08 FF 5A
D´ale je d´an stav procesoru DLXV: r2 = 0x10, r3 = 0x20, r4 = 16, vlr = 8
1. Graficky zn´azornˇete ˇcasov´y pr˚ ubˇeh a urˇcete d´elku prov´adˇen´ı pro instrukce:
lv v0, (r2) lvws v1, (r3), r4
2. Urˇcete obsah registr˚ u v0 a v1 po proveden´ı tˇechto instrukc´ı. 3. Jak m˚ uˇze vektorov´y procesor ˇc´ıst/zapisovat data ˇr´ıdk´ych matic? 4. Jak m˚ uˇze vektorov´y procesor prov´adˇet operace s vybran´ymi sloˇzkami vektoru? Ing. Tom´ aˇs Zahradnick´ y doc. Ing. R´ obert L´ orencz, CSc. Vektorov´ e poˇ c´ıtaˇ ce
Architektury poˇ c´ıtaˇ cov´ ych syst´ em˚ u
ˇ sen´ı I Reˇ 1. Graficky zn´azornˇete ˇcasov´e pr˚ ubˇehy a d´elku instrukc´ı. Banky jsou oznaˇceny ˇc´ast´ı adresy A(4:3): lv v0, (r2)
lvws v1, (r3), r4
10 11
00 10 00
00
10
01 10
00
11
10 00
00 01 11
2. Urˇcete obsahy registr˚ u v0 a v1: v0 = {05, 07, 0A, 0B, 0C, 0D, 02, 04} v1 = {0A, 0C, 02, 06, AB, DE, AA, A5} Ing. Tom´ aˇs Zahradnick´ y doc. Ing. R´ obert L´ orencz, CSc. Vektorov´ e poˇ c´ıtaˇ ce
10 17
Architektury poˇ c´ıtaˇ cov´ ych syst´ em˚ u
ˇ sen´ı II Reˇ 3. Jak m˚ uˇze vektorov´y procesor ˇc´ıst/zapisovat data ˇr´ıdk´ych matic? Data ˇr´ıdk´ych matic lze ˇc´ıst/zapisovat pomoc´ı operac´ı scatter&gather — tedy pomoc´ı instrukc´ı lvws a svws. 4. Jak m˚ uˇze vektorov´y procesor prov´adˇet operace s vybran´ymi sloˇzkami vektoru? Nad vybran´ymi sloˇzkami lze pracovat pomoc´ı maskov´an´ı — viz instrukce lvi a svi.
Ing. Tom´ aˇs Zahradnick´ y doc. Ing. R´ obert L´ orencz, CSc. Vektorov´ e poˇ c´ıtaˇ ce
