Vectorizare cu shuffle. Transferuri DMA

Obiective

În cadrul acestui laborator vom explora două modalități prin care poate fi exploatat paralelismul în programarea procesoarelor cu arhitectură Cell: calculul vectorial și împărțirea sarcinii de lucru pe SPE-uri. Ideal este, desigur, ca programele noastre să combine, pe cât posibil, aceste două modalități pentru a atinge un maxim de performanță.

Calcul vectorial

Noțiunea de calcul vectorial a fost introdusă în laboratorul trecut. Reamintim câteva dintre ideile principale pe această temă:

  • atât PPU, cât și SPU au fiecare registre pe 128 de biți, proiectate special pentru operații vectoriale (fiecare poate găzdui un număr de elemente cu tip de bază, care pot fi procesate în același timp de unitățile de procesare din cadrul PPU și SPU)
  • atât PPU, cât și SPU au definite, în extensia pe care Cell SDK o aduce bibliotecilor standard C, tipuri de date vector (un element de formă vector <tip> va avea atâtea elemente <tip> câte încap în 16 octeți, sau într-un registru de 128 de biți) și instrucțiuni aritmetico-logice (acestea vor primi ca parametrii două elemente de tip vector și vor declanșa operația vectorială corespunzătoare)
  • :!: cerința de bază în folosirea operațiilor vectoriale este ca operanzii (fie ei declarați static sau dinamic) să fi fost alocați aliniat.

În acest laborator, vom relua ideea de calcul vectorial și o vom discuta pe cazul particular a două operații: adunare vectorială (spu_add) si permutare (spu_shuffle).

spu_add

Reluăm exemplul de data trecută pentru a discuta adunarea vectorială. Aceasta se poate realiză cu ajutorul funcției spu_add din spu_intrinsics. De asemenea, operatorul + este supraîncărcat astfel încât, dacă detectează operanzi de tip vectorial, va executa de fapt spu_add.

#define N 8
...
 
unsigned int a[N] __attribute__ ((aligned(16)))  = {10, 20, 30, 40, 50, 60, 70, 80};
unsigned int b[N] __attribute__ ((aligned(16)))  = {1, 2, 3, 4, 5, 6, 7, 8};
unsigned int c[N] __attribute__ ((aligned(16)));
....
 
/* lucru cu scalari */
for (i = 0; i < N; i++){
     c[i] = a[i] + b[i];
}
 
/* lucru cu vectori */
vector unsigned int *va = (vector unsigned int *) a;
vector unsigned int *vb = (vector unsigned int *) b;
vector unsigned int *vc = (vector unsigned int *) c;
int n = N/(16/sizeof(unsigned int));
for (i = 0; i < n; i++){     // N/4 iterații
     vc[i] = va[i] + vb[i];  // putea fi folosit si vc[i] = spu_add(va[i], vb[i])
}
 
int i;
for (i=0; i<N; i+=4)
     printf("%d %d %d %d ", c[i], c[i+1], c[i+2], c[i+3]);

:!: Dacă în exemplul anterior dimensiunea vectorilor nu era multiplu de 4, atunci restul elementelor trebuiau adunate ca scalari sau făcut 'padding' la vectori.

spu_shuffle

Două funcții importante, și mai greu de înțeles la început sunt:

  • d = spu_sel(a, b, pattern) - selectează biții din a sau b în funcție de un pattern dat. Patternul este o variabilă pe 128 de biți, pentru fiecare bit din pattern, dacă este 0 se pune în d pe poziția respectivă bitul din a, altfel se pune bitul din b
  • d = spu_shuffle(a, b, pattern) - se creează un vector d cu bytes din a și b selectați conform unui pattern. Pattern-ul este un array cu 16 elemente (pentru că sunt 16 bytes într-o variabilă vector) ce poate fi reprezentat printr-o variabila vector de 16 chars. În fiecare element din pattern se pune numărul byte-ului din a sau b care se dorește a fi copiat în vector-ul rezultat.

Un exemplu de folosire spu_shuffle este selecția elementelor de pe pozițiile impare din două variabile vector.

    vector unsigned char pattern = (vector unsigned char){0,1,2,3,16,17,18,19,8,9,10,11,24,25,26,27};
    //vector unsigned char pattern = (vector unsigned char) {0x00,0x01,0x02,0x03,0x10,0x11,0x12,0x13,0x08,0x09,0x0A,0x0B,0x18,0x19,0x1A,0x1B};
    vector unsigned int a, b, d;
    a = spu_splats((unsigned int)0);
    b = (vector unsigned int){1, 2, 3, 4};
    d = spu_shuffle(a, b, pattern);

 Exemplu spu_shuffle

Pentru a opera doar pe elementele dintr-o singură variabilă vector putem da ca al doilea parametru al funcției spu_shuffle același vector ca pentru primul parametru. În exemplul următor se inversează câte două elemente din vector.

Exemplu spu_shuffle pe un singur vector

În cod, această inversare arată astfel:

vector unsigned char pattern = (vector unsigned char){4,5,6,7,0,1,2,3,12,13,14,15,8,9,10,11};
vector unsigned  int a = {1, 2, 3, 4};
vector unsigned  int d; 
d = spu_shuffle(a, a, pattern);

Observați în pattern cum se folosesc secvențe de câte patru numere consecutive, pentru a desemna cei patru octeți consecutivi care constituie un unsigned int. Spre exemplu, octeții 4,5,6,7 vor desemna elementul cu valoarea 2 din a. Astfel, după operația de mai sus d == {2, 1, 4, 3}.

Transfer DMA

Transferul DMA este folosit pentru a trimite date între spațiul principal de stocare și memoria locală. SPE-urile pot folosi transfer DMA asincron (folosind unitatea specializata MFC) pentru a ascunde latența memoriei și overhead-ul, ocupându-se în paralel de calcule.

Conform arhitecturii CELL, datele alocate în codul PPU sunt alocate în Main Storage (echivalent RAM, memorie mare, ~GB, accesibilă prin MIC), iar cele alocate în codul SPU sunt alocate în Local Store (memoria locala SPU, relativ redusa ca dimensiune, 256KB, dar mai rapidă - on-chip, la nivelul procesorului).

Prin urmare, un pointer din codul PPU nu poate fi folosit direct în codul SPU și vice-versa. Cele doua procesoare au spatii de adresare diferite.

Orice operație de citire/scriere de date din/în spatiul principal de stocare (main storage) se face de catre SPU prin MFC folosind mecanismul de transfer DMA. Optimizarea acestor transferuri joacă un rol crucial în scrierea de programe eficiente pentru Cell. În acest laborator vom discuta concepte de bază pentru înțelegerea mecanismului DMA, urmând ca în laboratorul următor să discutăm mecanisme avansate de folosire DMA (de exemplu, double-buffering).

Mărimea unui transfer DMA poate avea una din valorile: 1, 2, 4 sau 8 bytes, sau multiplu de 16 bytes, dar nu mai mult de 16KB.


Roluri: sender și receiver

Direcția transferului DMA este denumită din perspectiva SPU:

  • pentru transfer de date la SPU, adică din spatiul principal de stocare în memoria locală (de la Main Storage in Local Store), se folosesc comenzi de tip get
  • pentru transfer de date de la SPU, adică din memoria locală în spațiul principal de stocare (de la Local Store la Main Storage), se folosesc comenzi de tip put

Cu toate acestea, din punctul de vedere al MFC, atât SPU asociat, cât și PPU sau alte SPE-uri pot iniția transferul DMA. MFC gestionează doua cozi pentru comenzile fără caracter imediat: MFC SPU command queue (cu 16 intrari) pentru comenzi venite de la SPU asociat si MFC proxy command queue (cu 8 intrari) pentru comenzi venite de la PPU sau alte SPE-uri.

In concluzie, atentie la directia de transfer (de exemplu, daca PPU cere date de la un SPU va folosi comanda de tip put).


Ordonarea transferurilor: fence si barrier

Comenzile DMA pot fi procesate și în altă ordine decât FIFO.

Dacă situația o cere, este important să se folosească forme speciale ale comenzilor get si put (e.g. getf, putb etc.) care utilizează mecanisme de sincronizare de tip fence sau barrier. Mai mult decât atât, MFC dispune și de comenzi de sincronizare (e.g. barrier, mfceieio, mfcsync etc.).

Pentru realizarea sincronizării se folosește conceptul de tag group. Fiecărei comenzi MFC care intră în coada de comenzi îi este asociat un tag group ID de 5 biți. Tag group-urile sunt independente de la o coadă la alta (MFC proxy command queue vs. MFC SPU command queue). În implementarea de Linux a libspe2, tag group id poate lua valori între 0 și 31.

Comenzi get si put cu fence sau barrier

Comenzile cu sufix ce indică fence impun completarea în prealabil a tuturor comenzilor DMA din același tag group inițiate înaintea comenzii curente de tip fence. Astfel, o comandă inițiată anterior comenzii curente nu se poate executa după comanda curentă în timp ce o comanda inițiata ulterior comenzii curente se poate executa înaintea acesteia din urma.

Comenzile cu sufix ce indică barrier impun completarea în prealabil a tuturor comenzilor DMA din același tag group. Astfel, comenzile inițiate anterior comenzii curente nu se pot executa după comanda curentă cum nici comenzile inițiate ulterior comenzii curente nu se pot executa înainte de comanda curentă.

Comenzi de sincronizare

Comanda barrier (functia mfc_barrier pe SPU, indisponibila pe PPU), în contrast cu formele cu bariera ale comenzilor get și put, impune finalizarea tuturor comenzilor MFC din coada de comandă DMA (DMA command queue) lansate în prealabil, indiferent de tag group. Comanda barrier nu are efect asupra comenzilor DMA cu caracter imediat: getllar, putllc, putlluc, care nu pot apartine unui tag group.

Comanda mfcsync (functia mfc_sync pe SPU, intrinsic __sync pe PPU) asigură completarea operațiilor get și put din tag group-ul specificat înaintea altor unități de procesare și mecanisme din sistem.

Pentru o listă completă a comenzilor de sincronizare consultați [2] pagina 119


DMA la nivel de cod

Atât SPU, cât și PPU au funcții ce mapează comenzi de tip get si put (* indică posibilitatea de adăugare de sufixe):

  • Un program SPU poate apela funcții definite în spu_mfcio.h de tipul:
    • mfc_put*
    • mfc_get*
  • Un program PPU poate apela funcții definite în libspe2.h de tipul:
    • spe_mfcio_put*
    • spe_mfcio_get*

Mai multe informații despre spu_mfcio.h găsiți în [3.3] (IBM C/C++ Language Extensions for Cell Broadband Engine Architecture), iar despre libspe2.h în [3.4] (IBM SPE Runtime Management Library). SDK 3.0 definește și un nou set de funcții pentru DMA în cbe_mfc.h, care nu sunt foarte clar descrise, dar sunt considerate mai performante.

Atât comenzile get, cât și cele put au mai multe forme, prin adăugarea de sufixe (e.g. mfc_get, spe_mfcio_getf, mfc_putlf etc.). Sufixele au următoarele semnificații:

Atenție! Nu toate combinațiile de sufixe formează instrucțiuni valide. Pentru o listă completă a comenzilor consultați [2] , paginile 113-115.

Să luăm, spre exemplu, o instrucțiune de SPU și una pentru PPU (celelalte se tratează în mod asemănător):

(void) mfc_get(volatile void *ls, uint64_t ea, uint32_t size, uint32_t tag, uint32_t tid, uint32_t rid)

Implementare:

spu_mfcdma64(ls, mfc_ea2h(ea), mfc_ea2l(ea), size, tag, ( (tid«24)|(rid«16)|MFC_GET_CMD) )

respectiv:

int spe_mfcio_put (spe_context_ptr_t spe, unsigned int lsa, void *ea, unsigned int size, unsigned int tag, unsigned int tid, unsigned int rid)

Din punct de vedere al parametrilor este important de remarcat că locația din spațiul principal de stocare este dată de parametrul ea (effective address), iar cea din memoria locală de parametrul ls/lsa (local store address). Între ceilalți parametri mai recunoaștem size (dimensiunea datelor transmise) și tag (care reprezintă tag group id-ul ales). Funcția pentru PPU are în plus, evident, parametrul spe (prin care se alege SPU-ul cu care se comunică).

În mod explicit am amintit doar de o parte din funcțiile MFC disponibile pentru lucrul cu DMA. Acestea sunt numeroase și apar clasificate în:

  • tag manager (e.g. mfc_tag_reserve, mfc_tag_release)
  • comenzi DMA (e.g. mfc_put, mfc_get)
  • comenzi pentru liste DMA (e.g. mfc_putl, mfc_getl)
  • operații atomice (e.g. mfc_getllar, mfc_putllc)
  • comenzi de sincronizare (e.g. mfc_barrier)
  • comenzi pentru statusul DMA (e.g. mfc_stat_cmd_queue, mfc_read_tag_status) etc.

Pentru o referință completă recomandăm [2] , secțiunea 4: Programming Support for MFC Input and Output.

Funcții de bază pentru transfer

(void) mfc_get (volatile void *lsa, uint64_t ea, uint32_t size, uint32_t tag, uint32_t tid, uint32_t rid) 
(void) mfc_put (volatile void *lsa, uint64_t ea, uint32_t size, uint32_t tag, uint32_t tid, uint32_t rid)
  • lsa : adresa din Local Store
  • ea : adresa efectivă din memoria principală
  • size: dimensiunea transferului DMA (în bytes)
  • tag : identificator (tag) al transferului DMA
  • tid : transfer class identifier
  • rid : replacement class identifier

Exemplu folosire:

#define wait_tag(t) mfc_write_tag_mask(1<<t); mfc_read_tag_status_all();
 
[....] 
 
uint32_t tag = mfc_tag_reserve();
if (tag==MFC_TAG_INVALID){
    printf("SPU: ERROR can't allocate tag ID\n"); return -1;
}
 
// local_var, local_res - variabile declarate in spu (aliniate la 16)
// var, res - variabile din memoria principala, de tip float*
// trebuie facut cast la 32 de biti, pentru ca pe SPU, float* este pe 32, iar parametrul functiei este pe 64 de biti
// fara acest cast bitii cei mai semnificativi vor fi pusi pe 1 (extensie de semn) si adresa devine invalida
 
mfc_get ((void *)local_var, (unsigned int) var, num_bytes, tag, 0, 0); 
wait_tag(tag);
 
mfc_put ((void *)local_res, (unsigned int) res, num_bytes, tag, 0, 0); 
wait_tag(tag);

Reguli pentru transferurile DMA

Dacă dimensiunea transferului este de cel puțin 16 bytes

  1. Dimensiunea trebuie să fie multiplu de 16 bytes;
  2. Adresele sursă și destinație trebuie să fie aliniate la 16 bytes (128 bytes pentru performanță mai bună);
  3. Dimensiunea poate fi cel mult 16 KB.

Dacă dimensiunea transferului este de 1, 2, 4 sau 8 bytes

  1. Adresele sursă și destinație trebuie să fie multiplu al dimensiunii transferului;
  2. Adresele sursă și destinație trebuie să aibă aceeași 4 biți în jumătatea inferioară (e.g. se pot transfera 2 bytes de la adresa 0x123406 către adresa 0x4506, dar nu la adresle 0x4500, 0x4502 etc.)

Sfaturi pentru performanță

SPE-urile folosesc transfer DMA asincron pentru a ascunde latența memoriei și overhead-ul transferului, ocupându-se în paralel de calcule (mai multe pe această temă în laboratorul următor).

Performanța unui transfer DMA (mai mare de 128 de octeți) este maximă atunci când adresele sursă și destinație sunt aliniate la dimensiunea liniei de cache.

Sunt de preferat transferurile inițiate de SPE în favoarea celor inițiate de PPE, deoarece: sunt de 8 ori mai multe SPE-uri, iar într-un MFC coada de comenzi pentru SPU este de două ori mai mare decât cea pentru PPE și celelalte SPE-uri (16 intrări față de 8), transferurile inițiate de 'consumatori' sunt mai ușor de sincronizat etc. [3.2]

Pentru a ne face o idee cu privire la costul unui transfer: un thread rulând pe SPU poate face o cerere DMA în 10 cicli de ceas (în condiții de încărcare optimă). Pentru fiecare dintre cei cinci parametri ai unei comenzi cum ar fi mfc_get se scriu date pe un canal SPU (latența instrucțiunilor pentru canale SPU este de 2 cicli de ceas). Latența de la emiterea comenzii de către DMA și până la ajungerea acesteia în EIB este de aproximativ 30 de cicli (dacă se cere aducerea unui element al unei liste se pot adăuga alți 20 de cicli) [1] . Faza de comandă a transferului necesită o verificare a elementelor de pe magistrală și are nevoie de circa 50 de cicli magistrală (100 de cicli SPU). Pentru operații get, se mai adaugă latența de aducere a datelor din memoria off-chip la controller-ul de memorie, apoi pe magistrala la SPE, după care se scriu în Local Store. Pentru operații put, latența DMA include doar transmiterea datelor până la controller-ul de memorie, fără transferul acestora pe memoria off-chip. [1]


Pentru exemple practice urmăriți tutorialele de pe pagina DMA 101


Exerciții

În cadrul laboratoarelor și temelor vom folosi sistemele Cell BE puse la dispoziție în cluster, conform tutorialului de pe wiki: Rulare programe Cell in Cluster

Activitate practică - folosirea transferurilor DMA

Se dau doi vectori A și B de câte 32768 de elemente de tip float. Se dorește realizarea unor operații pe aceste date și stocarea rezultatelor în vectorii C și D. Fiecare SPE va procesa seturi de 4096 de elemente. Dimensiunea unui transfer DMA va fi de 16kB (kilobytes). Este nevoie de un singur transfer DMA pentru a aduce datele necesare pe SPE-uri.

Vectorul C va fi creat după următoarea formulă: C[i] = A[i] * B[i], i=1-32768
Pentru vectorul D vom procesa datele pe grupuri de 4 elemente:
- fie [A0, A1, A2, A3] un grup de 4 elemente din vectorul A
- fie [B0, B1, B2, B3] grupul corespondent din vectorul B
- grupul rezultat din vectorul D va fi: [A0 + B0, A2 + A3, A1 + B2, A1 + B1]

Se pornește de la scheletul de cod din aceasta arhivă. Se vor implementa, pe rând, următoarele cerințe:

  1. (2p) Observați că va trebui ca SPU-ul să știe o locație din A, o locație din B, o locație din C și o locație din D. Prin urmare argumentele din spe_context_run nu mai sunt suficiente. Din acest motiv, a fost definita structura de tip pointers_t în lab8_common.h. Fiecare SPU va face un transfer DMA inițial cu această structură. Folosiți argumentele lui spe_context_run pentru a trimite adresa acestui transfer DMA inițial.
  2. (2.5p) Transferați un set de date din A și unul din B, atât cât vă permit regulile pentru transferul DMA.
  3. (1p) Pornind de la punctul anterior, folosiți operații vectoriale pentru a înmulți element cu element porțiunea din A și porțiunea din B transferate la SPU. Este util să vă amintiți secțiunea Exemplu de vectorizare din Laboratorul 7.
  4. (2.5p) Transferați rezultatul înmulțirii înapoi către PPU.
  5. (2p) Realizați calculele necesare pentru a obține rezultatul din array-ul D folosind spu_shuffle. Transferați rezultatul înapoi către PPU.
  6. (Bonus 2p) Modificați dimensiunea array-urilor A și B la 131072 elemente. În acest caz este nevoie de mai multe runde de procesare pentru a realiza calculele cerute. Realizați modificările necesare.


Resurse

Linkuri utile

asc/lab8/index.txt · Last modified: 2017/04/11 00:29 by emil.slusanschi
CC Attribution-Share Alike 3.0 Unported
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0