Multiprocesoare simetrice: coerența cache-urilor
Seria: arhitectura modernă a calculatoarelor

Mihai Budiu -- mihaib+@cs.cmu.edu
http://www.cs.cmu.edu/~mihaib/

octombrie 1998

Subiect:
cum se implementează coerența cache-urilor în mașinile multiprocesor
Cunoștințe necesare:
cache, programare în limbaj mașină, noțiuni elementare despre arhitectura calculatoarelor
Cuvinte cheie:
multiprocesoare simetrice, coerență, cache, atomat finit


Contents




În ultimele numere din PC Report am văzut o serie de articole deosebit de interesante despre arhitectura internă a unor procesoare moderne (Pentium, AMD K6, etc.). Articolele erau bine documentate, și prezentau o cantitate impresionantă de informații într-un spațiu mai curînd restrîns. Ca atare mi-am propus să scriu o întreagă serie de articole numite generic ``arhitectura modernă a calculatoarelor'' în care să explic pe îndelete noțiunile esențiale care apar în proiectarea acestor bijuterii tehnologice. Voi încerca pe rînd să ``demistific'' noțiuni ca ``superscalar'', ``pipelined'', ``stație de rezervare'', ``paralelism la nivel de instrucțiune'', ``multiprocesoare simetrice'', ``redenumirea regiștrilor'', ``forwarding'', ``protocol de coerență'', ``predicția salturilor'', ``execuție speculativă'', ``prefetching'', etc.

Adevărul este că în ultimii 10 ani arhitectura calculatoarelor a suferit niște modificări uriașe. În urmă cu 20 de ani gama de putere și preț ale calculatoarelor avea extreme foarte îndepărtate; PCul era o jucărioară în comparație cu stațiile de lucru, care la rîndul lor erau puse în umbră de ``mainframes''; la vîrful ierarhiei tronau supercalculatoarele. Cu fiecare an trecut, extremele s-au apropiat simțitor; practic toate firmele care făceau numai supercalculatoare au dat faliment1, iar diferențele între puterea de calcul a unui PC și a unei stații de lucru s-au redus enorm; idei care se foloseau pe vremuri în proiectarea supercalculatoarelor sunt acum în mod comun implementate în procesoarele PCurilor de pe biroul fiecăruia. Complexitatea design-urilor și ingeniozitatea soluțiilor sunt extrem de surprinzătoare pentru cel care nu a rămas la curent cu evoluția domeniului fie și pentru puțină vreme.

Complexitatea aparatelor este uriașă, iar viteza cu care apar inovațiile depășește cu mult viteza cu care pot tasta eu texte, așa că nu voi putea face decît o ilustrare a conceptelor esențiale, care sper să poată da o idee generală despre anatomia unui calculator contemporan.

Prima tema pe care mi-am ales-o are de-a face cu arhitectura calculatoarelor cu mai multe procesoare; din spectrul larg de implementări (despre care vorbesc pe scurt în secțiunea 2) voi ataca o singură opțiune, dar care este dominantă economic: cea a multiprocesoarelor simetrice cu memorie partajată bazate pe o magistrală comună.

Paralelism și performanță

De vreo douăzeci de ani încoace se prezice moartea paradigmei arhitecturale numită ``von Neumann'', a calculatoarelor cu un singur procesor și o unitate de memorie. Unii experți se încăpățînează să prezică plafonarea performanțelor sistemelor bazate pe astfel de arhitecturi, iar fabricanții de sisteme se încăpățînează să contrazică prin sistemele construite predicțiile sumbre. În trecere vreau să observ că numele ``arhitectură von Neumann'', folosit adesea peiorativ pentru a indica o arhitectură depășită, nu este întru totul potrivit; John von Neumann, care a murit în 1956, a fost conștient pe deplin de importanța paralelismului; a și scris niște cărți foarte interesante pe tema asta; von Neumann însă era un inginer extraordinar (de fapt era profesor de matematică la Princeton, cu o diplomă în inginerie chimică de la universitatea din Budapesta, dar nu o să ne incomodeze astfel de distincții din a-l trata drept ``inginer''), și a realizat că pentru a rezolva problemele ele trebuie adesea simplificate, sparte în bucăți mai mici care sunt apoi tratate independent. Starea catastrofală a componentelor electronice disponibile pe vremea aceea (relativ la ziua de azi) făcea proiectarea și întreținerea unui sistem atît de complex ca un calculator o sarcină supraomenească, așa că von Neumann a făcut problema tractabilă și a rezolvat-o cu atît de mult succes încît și acum, după 50 de ani, organizarea propusă de el este dominantă.

Oricum, fie că se plafonează sau nu performanțele unui microprocesor, să ai mai multe nu poate să strice prea tare, nu? Unde-s mai multe capete se gîndește mai bine. Că lucrurile nu stau întotdeauna așa reiese din următoarea întrebare: ``dacă un ins sapă o groapă în 60 de secunde, 60 de inși sapă o groapă într-o secundă?'' E (aproape) clar că nu orice poate fi rezolvat în paralel cu eficacitate. Asupra consecințelor acestui enunț, care sunt exprimate și de celebra lege a lui Amdahl, vom reveni în alte articole.

Oricum, anumite activități se pot într-adevăr face relativ repede dacă avem mai multe resurse computaționale la-ndemînă. De exemplu, într-o întreagă suită de articole despre sistemele de operare, am observat că sistemele de operare moderne permit executarea simultană a mai multor programe printr-un mecanism simplu numit time-sharing, care constă în executarea întrețesută a grupe de instrucțiuni din programe diferite (adică programul 1 merge 10 milisecunde, după care programul 2 10 milisecunde, etc.). Dacă avem mai multe procesoare, atunci putem executa cu adevărat mai multe programe deodată: cîte unul pe fiecare procesor.

Multiprocesoare

 

Există mai multe feluri de mașini cu mai multe procesoare, dar noi ne vom ocupa de unul singur în acest articol. Celelalte variante merită desigur mențiune; să le-o dăm.

Putem împărți multiprocesoarele în două mari categorii, care diferă din modul în care se accesează memoria în care se află programele și datele.

Trebuie spus că tipul în care se încadrează o mașină depinde foarte mult de nivelul la care o privim. De pildă dacă luăm o colecție de stații de lucru, la nivel hardware acestea categoric comunică prin mesaje. Pe de altă parte putem instala pe ele un nivel software (cum ar fi de pildă sistemul de operare Mach), care folosind tehnici de memorie virtuală permite mașinilor să partajeze un același spațiu de adrese virtual, astfel încît ce scrie o mașina la adresa 5 celelalte pot citi de la adresa 5; în cazul ăsta mașinile au ceea ce se numește memorie distribuită partajată (DSM: Distributed Shared Memory), care este un tip de NUMA.

Un alt exemplu despre fragilitatea clasificării: chiar mașinile cărora acest articol le este dedicat, multiprocesoarele simetrice, sunt categorisite drept mașini UMA. Dar vom vedea că fiecare procesor dintr-un sistem SMP are de fapt un cache (o memorie locală mică), la care accesul este mult mai rapid decît la memoria globală a sistemului; la acest nivel mașina arată de fapt ca o NUMA...

O mașină cu mai multe procesoare se numește ``simetrică'' dacă toate procesoarele au roluri egale: fiecare procesor poate executa orice tip de cod. Prin contrast, mașinile asimetrice dedică anumite procesoare anumitor treburi, cum ar fi executarea codului întreruperilor, executarea codului sistemului de operare, etc. Pe noi ne vor interesa procesoarele simetrice pentru că sunt cele mai reprezentate în mașinile comerciale; există și PCuri cu 2 sau 4 procesoare Pentium.

În fine, vom mai disocia calculatoarele cu memorie partajată în două categorii distincte, după felul în care ajung la memorie. Tipul care ne va interesa, și din care cele mai multe mașini SMP fac parte, este cel al mașinilor bazate pe o magistrală comună (bus): toate procesoarele pun cererile de acces la memorie pe o singură sîrmă. Vom vedea că acesta este un factor crucial. PCurile SMP sunt de acest tip, ca și cele mai multe mașini comerciale (stațiile ULTRASparc, SGI Challenge, etc.)

Pe de altă parte, există mașini care au o rețea de interconectare interconnection network între procesoare și (de obicei multiplele) module de memorie.

sistem bazat pe magistrala comuna     sistem bazat pe retea de interconectare  
     -----------                              ------------------ 
     | memorie |                              |    retea de    | 
     -----------                              | interconectare | 
          ||                                  ------------------ 
     ===========   magistrala                    |    |    | 
     |    |    |                                ---- ---- ----
    ---- ---- ----                              |m1| |m2| |m3| memorie locala
    |c1| |c2| |c3| cacheuri                     ---- ---- ---- 
    ---- ---- ----                               |    |    | 
     |    |    |                                ---- ---- ---- 
    ---- ---- ----                              |c1| |c2| |c3| cacheuri 
    |p1| |p2| |p3| procesoare                   ---- ---- ---- 
    ---- ---- ----                               |    |    | 
                                                ---- ---- ---- 
                                                |p1| |p2| |p3| procesoare 
                                                ---- ---- ----

Diferența esențială este de scalabilitate: este extrem de greu de construit o mașină bazată pe bus cu multe procesoare, din cauză că, așa cum e ușor de imaginat, de de la un anumit număr de procesoare încolo bus-ul devine factorul care limitează viteza de comunicare.

Pe de altă parte, mașinile cu rețea de interconectare pot crește mai bine, pînă la sute sau chiar mii de procesoare (mașina IBM care l-a bătut pe Kasparov, un SP2, e bazată pe o rețea care interconectează pînă la o mie de procesoare).

Trebuie spus că multiprocesoarele sunt încă departe de a fi panaceul universal în a rezolva probleme computaționale dificile, mai ales din cauză că scrierea de programe pentru astfel de mașini este extrem de dificilă. Oricum, cercetarea în domeniu este în continuare febrilă, și o mulțime de schimbări revoluționare așteaptă probabil la cotitură.

Cache-uri

Chiar dacă avem un singur procesor, viteza de răspuns a unei memorii DRAM este de vreo 15 ori mai mică decît viteza cu care procesorul dorește date și instrucțiuni, iar disparitatea de viteză tinde să crească. Din cauza aceasta fiecare procesor modern este echipat cu o memorie SRAM rapidă, plasată foarte aproape de procesor, numită cache. (SRAMul este mult mai scump decît DRAMul; pentru acest motiv nu înlocuim tot DRAMul cu SRAM.) Despre cache am scris cel puțin două articole în PC Report: unul în martie 1997 și unul luna trecută, în octombrie 1998. Dacă nu aveți revistele sunteți bineveniți să luați articolele din pagina mea de web. Cu toate astea vom vedea că subiectul nu a fost epuizat, pentru că miezul acestui articol tot despre cache-uri va vorbi.

Ideea de bază este relativ simplă: programele au nevoie foarte rar de o cantitate mare de date sau instrucțiuni simultan; ele tind să refolosească de mai multe ori o cantitate relativ mică de date. Această proprietate, verificată empiric, se numește ``localitate''. Din cauza asta un cache este util: dacă cuprinde toate datele necesare, sau măcar o mare parte dintre ele, atunci eficiența crește simțitor, pentru că timpul mediu de acces este redus simțitor.

Procesoarele dintr-un sistem SMP nu fac excepție: fiecare este echipat cu un cache (sau chiar două, de mărimi diferite, unul fiind mai mare și mai lent).

Problema coerenței

Toate bune și frumoase, aparent: în loc să punem un procesor pe magistrală punem două, și mașina merge de două ori mai repede. Hopa, să nu ne grăbim. O grămadă de probleme urîte apar de îndată.

Să luăm un exemplu simplu, în care două procesoare accesează aceeași adresă de memorie. Iată o posibilă evoluție în timp:

  Instrucțiune cache  
Timp Procesor 1 Procesor 2 Procesor 1 Procesor 2 Memorie
0         mem[5]=3
1 read 5   cache[5]=3   mem[5]=3
2   read 5 cache[5]=3 cache[5]=3 mem[5]=3
3 write 5, 4   cache[5]=4 cache[5]=3 mem[5]=3
4   write 5,2 cache[5]=4 cache[5]=2 mem[5]=3

Avem acum nu mai puțin de 3 valori diferite pentru adresa 5: un 4 în cache-ul procesorului 1, un 2 la procesorul 2 și 3 în memoria însăși. Noi am pus procesoarele la aceeași memorie tocmai ca să poată comunica mai ușor; dacă vroiam izolare foloseam două calculatoare. Care este acum de fapt conținutul real al adresei 5? Cache-urile au devenit ne-coerente.

Trebuie menționat că problema coerenței nu apare numai în sistemele SMP; ea apare la o mulțime de nivele în proiectarea sistemelor, oricînd avem de-a face cu replicarea (copierea) informației; ea apare de exemplu cînd avem de-a face cu replicarea unor servere de web, sau cu sisteme de fișiere în rețea (Network File System, Andrew File System, etc), sau în oricare sistemele cu un singur procesor atunci cînd un alt controler de magistrală (de pildă discul) accesează memoria prin acces direct (DMA: Direct Memory Access).

Problema aceasta apare de îndată ce cineva poate modifica o copie a datelor; problema este că celelalte copii vor avea valori diferite. Din cauza asta trebuie luate măsuri speciale ca celelalte valori să fie aduse la zi imediat. Orice întîrziere se poate solda cu efecte bizare pentru programator, care se așteaptă ca efectele execuției unei instrucțiuni să fie imediat vizibile.

Deși problema pare relativ simplă, există zeci de soluții foarte diferite calitativ, fiecare cu avantajele și dezavantajele ei. Ele diferă prin complexitatea implementării în hardware, prin gradul de scalabilitate (cît de bine se pot implementa pentru mașini cu mai multe procesoare), prin modul în care se manifestă pentru programator, prin gradul de performanță pe care îl oferă.

Interesant este că soluțiile cele mai economice din punct de vedere al impactului administrativ (overhead) cer colaborarea explicită a programatorului și oferă o vedere puțin bizară asupra memoriei. În acest articol vom vedea însă o soluție relativ ``simplă''.

Un protocol bazat pe ascultarea magistralei

Acum vom vedea cum multiprocesoarele simetrice bazate pe o magistrală comună reușesc să sincronizeze cache-urile. Faptul că avem o singură magistrală pentru toate procesoarele este crucial. Iată de ce: orice transfer de date între memorie și un cache se va petrece pe magistrală. Magistrala este din punct de vedere electric un singur circuit, conectat la toate cache-urile. Astfel, atunci cînd procesorul 1 aduce cuvîntul 5 din memorie în cache-ul său local, transferul se desfășoară pe magistrală și toată lumea vede acest lucru. Celelalte procesoare vor ști deci că o copie a cuvîntului 5 se află la procesorul 1, așa că atunci cînd vor dori să o modifice vor negocia cu acesta.

Pentru că fiecare cache se uită la magistrală și atunci cînd alții discută, acest gen de protocoale se numesc ``snoopy bus-based''. ``To snoop'' înseamnă ``a-și băga nasul în treburile altora'', adică exact ceea ce se întîmplă.

Ca să înțelegem avantajul schemei, să ne gîndim la schema alternativă, care folosește o rețea de interconectare. Cînd procesorul P1 ia ceva din memorie, această tranzacție nu este vizibilă pentru nimeni altcineva. Asta înseamnă că P2 o să trebuiască să afle acest lucru (de la memorie) abia cînd încearcă să acceseze același obiect, și abia după aceea poate să inițieze negocierea cu P1.

Perfect; avem un mecanism extrem de ieftin pentru a strînge informații despre plasamentul datelor (trasul cu urechea). Acum mai trebuie să punem la punct un protocol care să folosească această informație.

Problema centrală sunt scrierile; atunci cînd vrem să modificăm o valoare, ca să garantăm consistența, trebuie să fim siguri că nu mai există alte copii care după modificare vor avea valori diferite. (Soluția de a modifica toate copiile simultan pune mari dificultăți tehnice.) Ce vom face: atunci cînd vrem să scriem la adresa 5, vom face în așa fel încît nimeni altcineva să nu mai aibă o copie a datelor de acolo. Din cauză că am făcut ``snoop'' știm precis cine are copii; ceea ce avem de făcut este să rugăm pe toți aceștia să invalideze copiile lor, scoțîndu-le din cache. Cînd nimeni nu mai are o copie, luăm noi una, pe care o putem modifica apoi în deplină siguranță.

Detaliile protocolului

Chiar dacă lucrurile par simple, pînă la o implementare completă și corectă mai sunt mulți pași de făcut, și chiar multe alegeri. Noi o să dăm o anumită posibilă implementare, și o să indicăm pe alocuri unde sunt posibile variațiuni. Vom fi relativ compleți în detalii, în așa fel încît un arhitect să poată implementa în mod neambiguu din descrierea noastră un sistem.

Tipul de cache:

fiecare procesor va avea un cache write-back. Asta înseamnă că atunci cînd procesorul scrie date, valoarea modificată rămîne în cache și nu este trimisă spre memorie. (Varianta alternativă, write-through ar utiliza magistrala, și așa supra-încărcată, la fiecare scriere, pentru a trimite datele în memorie.)

Bus master:

În fiecare clipă un singur cache va avea dreptul de a folosi magistrala. Dacă două procesoare simultan găsesc datele în cache-urile proprii, atunci ele pot continua execuția în paralel. Dacă însă amîndouă vor să acceseze memoria, atunci unul dintre ele va trebui să aștepte pînă celălalt termină. Regula după care se decide cine are dreptul să folosească magistrala se numește arbitrarea magistralei; există mai multe protocoale pentru asta, dar, pentru a nu ne îneca în detalii, nu o să discutăm despre cum se face asta.

Copiile datelor:

Fiecare informație din memorie se poate afla simultan în mai multe cache-uri, dacă nu este modificată; o informație care are mai multe copii nici nu poate fi modificată (e ``read-only''). Dacă cineva vrea să modifice o valoare, trebuie să obțină o copie exclusivă. Odată obținută o astfel de copie, după modificare valoarea este marcată ca ``murdărită'' (dirty).

Propagarea copiilor:

Dacă un cache dorește să obțină o copie, o să facă o cerere pe magistrală. Memoria va oferi datele dacă acestea sunt ``curate'', altfel ele vor veni de la cache-ul posesor. Cînd niște date ``murdare'' sunt copiate la un alt procesor, ele sunt copiate și în memorie, și devin apoi ``curate''.

Semnalele

Să facem o schemă care arată cum vor comunica procesorul, cache-ul și magistrala. Fiecare săgeată arată direcția în care informația este transportată.

                                  cache
    ________     adresa     _________________               | m |
   |        |------------->|adresa stare date|  operatie    | a |
   |        |     date     |-----------------|------------->| g |
   |procesor|<------------>|  1    curat   3 |   adresa     | i |
   |        | scrie/citeste|  2    murdar  2 |------------->| s |
   |        |------------->|  3   invalid  - |    date      | t |
   |        | gata / blocat|                 |<------------>| r |
   |________|<-------------|_________________|              | a |
                                                            | l |
                                                            | a |

Starea blocului

Așa cum indică și desenul anterior, fiecare bloc dintr-un cache va fi într-una din următoarele stări:

Curat:
valoarea din bloc este validă și nu poate fi modificată de posesor; aceeași valoare se află în memoria principală, și poate și în alte cache-uri;
Murdar:
blocul este modificat de procesorul curent, și nu există nici o altă copie a sa; valoarea din memorie nu este corectă;
Invalid:
acest bloc nu se găsește de loc în cache.

Operațiile pe magistrală

Cînd un procesor devine master de magistrală, comanda lansată de acesta va fi pusă pe magistrală și observată de toată lumea. Vom presupune că din clipa în care un procesor devine master de magistrală el rămîne astfel pînă cînd tranzacția dorită de el a fost terminată. Această presupunere este destul de restrictivă pentru sistemele reale, în care timpul de reacție al memoriei poate fi de sute de cicli; un sistem real complicat va permite executarea operațiilor în două faze diferite, cerere-răspuns (astfel de operații se numesc split-transaction: tranzacție despicată, din motive evidente). Din păcate protocoalele cu tranzacții despicate devin extrem de complicate, mai ales dacă vrem să ne asigurăm de corectitudinea lor.

Pe magistrală se poate afla una din următoarele cereri:

Citește:
procesorul vrea să citească o copie ne-exclusivă;
Scrie:
unicul procesor care posedă un bloc murdar trimite valoarea lui spre memorie (sau/și un alt cache);
Invalidează:
masterul vrea să modifice blocul indicat; pentru aceasta roagă pe toată lumea care are o copie să o invalideze, iar pe eventualul posesor exclusiv să scrie valoarea copiei sale.

Comunicația

Vom folosi următorul tabel cu 7 linii pentru a indica semnalele care circulă de la/spre un cache:

Cine inițiază operația procesor / bus
Operația cerută citire / scriere / invalidare
Este blocul cerut în cache da / nu
Operația executată pe bus citire / scriere / nimic / invalidare
Datele aflate pe bus adresa
Modificarea în cache-ul local adresa
Ce face procesorul local citește / scrie / blocat

Primele trei rînduri descriu o cerere care sosește la un cache; următoarele 4 rînduri indică cum acea cerere este executată de către un cache. Figurile care urmează conțin astfel de tabele, dar numai coloana a doua.

Automatul finit al bus-master-ului

Dificultatea proiectării unui astfel de sistem este mare din cauză că trebuie să descriem ce face fiecare părticică avînd la dispoziție numai informația vizibilă acelei părticele. Noi, ca proiectanți, putem ``vedea'' sistemul în ansamblul său, dar un cache nu poate să vadă decît sîrmele cu care e conectat; cacheul 1 nu are nici cea mai mică idee despre conținutul lui 2 (înafară de ceea ce a inferat pe parcurs).

Modul în care se descrie comportarea fiecărei entități este folosind un automat finit. Noi vom construi automatul finit al unui cache, care arată exact ce acțiune trebuie acesta să facă ca răspuns la fiecare stimul venit din afară.

Un automat finit este o colecție de stări, în care circuitul se poate afla la un moment dat. Voi indica în desene stările prin cerculețe. Între stări există săgeți numite tranziții. Fiecare tranziție este etichetată cu o tabelă ca cea de mai sus; primele rînduri indică cererile făcute asupra cache-ului, fie că ele vin din partea procesorului local, fie dinspre bus, de la masterul de magistrală; ultimele rînduri indică reacția cache-ului.

În realitate, fiecare cuvînt din cache are un astfel de automat finit; noi vom arăta cum se comportă automatul finit asociat cuvîntului din cache care trebuie modificat de tranzacția curentă. Pentru a simplifica expunerea, vom desena două automate finite, unul care este valabil pentru procesorul master de magistrală, și unul care este valabil pentru celelalte procesoare. Fiecare procesor va acționa după una din reguli, depinzînd de starea lui la acel moment de timp.

Figura 1 arată automatul asociat unui master de magistrală. Automatul este destul de complicat, și are 10 tranziții posibile, numerotate în figură (sunt doar 5 săgeți, dar unele tranziții folosesc aceeași săgeată). Le vom analiza una cîte una. Rîndurile albe din tabele indică faptul că nu contează ce se află acolo, sau că acolo nu se află nimic.

Figure 1: Acțiunile unui master de magistrală atunci cînd procesorul vrea să opereze asupra blocului x iar în cache se află blocul y.
\begin{figure}\centerline{\epsfxsize=12cm\epsffile{master.eps}}\end{figure}

Cititorul care este plictisit de minuțiozitatea detaliilor din desen și text va trebui cu siguranță să-și caute o meserie înafara proiectării de calculatoare; modelul pe care îl prezentăm aici este de fapt o simplificare pedagogică substanțială; ceea ce se construiește în realitate în procesoarele pe care le folosim în fiecare zi este cu mult mai complicat. Voi spune cîteva cuvinte mai jos despre încrederea pe care o putem avea în astfel de design-uri.

Pe de altă parte uneltele pe care le prezint aici pentru a descrie comportarea sunt chiar cele folosite de către designerii profesioniști: automate finite cu reguli detaliate de tranziție.

Iată explicația tranzițiilor, în ordine crescătoare a dificultății:

Tranziția numărul 3:
Procesorul (linia 1 din tabelul nr. 3) dorește să citească (indicat de linia 2) de la adresa x. Cuvîntul este prezent în cache (linia 3), și este ``curat'' (starea curentă este ``curat''). Rezultatul este foarte simplu: nici o acțiune nu este inițiată pe magistrală (liniile 4, 5 sunt goale în tabel); cuvîntul este imediat servit procesorului, care termină operația de citire (linia 7).

Tranziția 8:
Procesorul dorește să citească de la adresa x, care este în cache, și este marcată ``murdară''. Citirea se poate face imediat, fără a implica magistrala.

Tranziția 7:
Procesorul vrea să scrie la adresa x, iar cuvîntul de la adresa x este prezent și este deja murdar. Scrierea se poate face imediat, fără a implica magistrala.

Primele trei tranziții descrise mai sus sunt foarte simple, pentru că datele sunt imediat disponibile și pentru că nu trebuie recurs la magistrală. Iată acum trei situații care se pot rezolva cu cîte o tranziție fiecare, dar care au nevoie de magistrală:

Tranziția 1:
Procesorul dorește să citească de la adresa x. În cache obiectul de la adresa x este marcat ca fiind invalid. În cazul asta pe magistrală este lansată comanda de citire (linia 4 din tabel) de la adresa x (linia 5). Modelul nostru presupune că datele de la adresa x vor fi trimise imediat de cel care le posedă (memoria sau un alt cache), deci ele vor fi încărcate în cache (linia 6); simultan ele vor fi trimise la procesor, care termină astfel operația de citire (linia 7). Pentru că procesorul are de acum o copie a valorii, blocul este marcat ca ``curat'' (tranziție de la Invalid la Curat).

Tranziția 4:
Procesorul vrea să citească x, dar în cache în acel loc se află altceva (linia 3), care este curat. Pentru că acea valoare este curată, ea este imediat ștearsă din cache (există o copie în memorie), pe bus este pusă o cerere pentru x (linia 5); presupunem că x vine imediat. x este apoi încărcat în cache, și procesorul termină citirea.

Tranziția 6:
Vreau să scriu în cuvîntul de la adresa x, am o copie a lui, dar nu sunt singurul. Atunci pun o cerere de invalidare (linia 4) a adresei x (linia 5) pe magistrală; în acest fel toți posesorii lui x sunt rugați să-l invalideze (știu că nimeni nu are o copie murdară). Toată lumea va reacționa corect la această cerere, așa că putem modifica valoarea lui x în cache-ul local. Valoarea ca atare devine ``murdară''.

Și astea trei situații au fost relativ simple, datorită modelului nostru care nu folosește ``split transaction'' (am presupus că datele cerute vin imediat; dacă durează mai mulți cicli, practic procesorul master și bus-ul sunt blocate pînă cînd datele așteptate de master ajung la destinație).

Operațiile rămase sunt mult mai încîlcite, și cer o succesiune de mai multe tranziții pentru a fi îndeplinite. Presupunem, din nou pentru a simplifica, că același cache rămînă master de magistrală pînă termină operația începută, chiar daca asta implică mai multe transferuri pe magistrală.

Iată niște operații care cer cîte două tranzacții pentru a fi executate (pe bus trebuie să circule două valori diferite). Procesorul master este deci blocat timp de două operații.

Tranziția 5 (+6):
Vreau să scriu în cuvîntul de la x, dar nu-l am. Atunci fac doi pași: întîi obțin o copie a cuvîntului (tranziția 5), după care continui cu tranzacția 6, invalidînd celelalte copii și scriind valoarea. Tranziția 5 va bloca procesorul (linia 7) pînă se termină tranziția 6 (abia atunci pot să fac ceea ce mi s-a cerut).

Tranziția 9 (+1):
Vreau să citesc la adresa x, dar locul e ocupat de cuvîntul de la y, care e și murdar pe deasupra. Atunci, în tranziția 9, pun acest cuvînt pe bus, și rog memoria să-l copieze. Blochez procesorul. După ce am scris cuvîntul, marchez linia ca invalidă și execut tranziția 1, pentru a citi cuvîntul cerut.

Tranziția 2 (+6):
Vreau să scriu la adresa x, dar nu am nici o copie a lui x (e marcată ``invalidă''). Atunci în primul rînd (tranziția 2) obțin o copie a lui x ca la o citire (linia 4) obișnuită, după care pot face scrierea (tranziția 6).

În fine, avem o situație, cea mai neplăcută, cînd pentru a face ceea ce procesorul ne cere, trebuie să facem nu mai puțin de 3 tranziții! Situația apare cînd vreau să scriu într-un cuvînt, dar am în acel loc un altul murdar.

Tranziția 10 (+1, +6):
Încep prin a goli cuvîntul murdar cu tranziția 10; marchez linia ``invalidă''. Apoi fac tranziția 1, pentru a obține o copie ``curată'', și apoi fac tranziția 6, pentru a invalida celelalte copii și marchez copia curentă ca murdară.

Automatul finit al unui cache non-master

Bravo! Dacă ați ajuns pînă aici sunteți foarte răbdători, sau ați sărit suficient de multe paragrafe.

Ce-a rămas este mult mai simplu: descrierea acțiunilor unui cache ``sclav'' (care nu e master de magistrală). Schema este mult mai simplă, pentru că un astfel de cache nu poate folosi de loc magistrala, cu o singură excepție: cînd primește o cerere de citire a unui bloc murdar, în care caz trebuie să-l pună pe magistrală pentru master. Toată schema este în figura 2.

Figure 2: Acțiunile unui sclav.
\begin{figure}\centerline{\epsfxsize=12cm\epsffile{sclav.eps}}\end{figure}

Tranziția 4:
bus-ul vrea o anumită adresă pe care nu o avem; nu facem nimic;

Tranziția 3:
bus-ul vrea o adresă pe care o avem, dar care e curată; atunci memoria o să satisfacă această cerere, deci iarăși nu facem nimic;

Tranziția 2:
bus-ul vrea o adresă pe care nu o am; nu fac nimic;

Tranziția 1:
primesc o cerere de invalidare a unui bloc curat pe care îl am: atunci marchez blocul ca invalid;

Tranziția 5:
bus-ul vrea să citească un bloc pe care îl am murdar; atunci pun valoarea pe bus, memoria va copia această valoare. Eu o marchez curată.

Corectitudine

Perfect; am specificat fiecare acțiune în funcție de circumstanțe suficient de detaliat pentru a putea fi implementată. Dar cum de știm că protocolul este corect?

De pildă poate părea ciudat că în ultima diagramă nu e nici o săgeată din starea ``murdar'' care să aibă în tabel o invalidare. Este cumva o omisiune? Nu, pentru că așa cum am proiectat protocolul, un cache poate lansa o invalidare numai după ce are o copie a datelor, deci ele nu pot fi simultan murdare altundeva.

Inutil de spus că verificarea unor sisteme reale este o treabă extrem de grea; modelul nostru este simplificat într-o mulțime de privințe. Ceea ce e într-un Pentium este de multe ori mai complicat decît modelul prezentat (Pentium are cache-uri ne-blocante, și dacă procesorul nu primește niște date pe care le-a cerut, el poate cere altele; datele pot sosi într-o ordine diferită de cea a cererilor!).

Marile companii de hardware (ex. Intel, IBM) folosesc pentru a verifica corectitudinea unor astfel de scheme tot calculatoarele. Pe de o parte se folosesc simulări și teste complete: sistemul este implementat ca un program, care apoi este testat pe toate combinațiile posibile de ordini de evenimente care pot apărea. Treaba asta este extrem de complicată, pentru că numărul de teste crește enorm cu complexitatea circuitului, ajungînd rapid la valori impractice chiar pentru cele mai performante calculatoare.

O altă metodă este cea de a folosi scule speciale pentru a verifica corectitudinea; o ramură specială a științei calculatoarelor se numește ``model theory'' și se ocupă cu metode de a analiza sisteme finite extrem de complicate folosind ecuațiile care descriu traiectoria sistemului. Un automat finit este o descriere suficient de precisă pentru a face o analiză exactă posibilă. Metodele se bazează pe teorii matematice destul de sofisticate, pentru a reduce substanțial spațiul căutărilor (logici temporale, diagrame binare de decizie, simulare și bisimulare, abstracție, etc.). Din păcate metodele practice sunt cam cu 10 ani în urma tehnologiei: nici nu se pune problema de a verifica exhaustiv circuitele contemporane, chiar și cu scule atît de sofisticate.

Un exemplu: SGI Challenge

Iată caracteristicile tehnice ale unei mașini reale care folosește tehnicile prezentate: SGI Challenge; acesta este cel mai mare multiprocesor bazat pe bus, cu 36 de procesoare MIPS R4400, o adevărată minune tehnologică.

Procesoare pînă la 36
Memorie pînă la 16 Gb
Lățime bus (date) 256 biți
Lățime bus (adrese) 40 biți
Rata de transfer 1.22 Gb/sec
Tranzacții model ``split''
Frecvența magistralei 50Mhz
Penalizarea pentru un rateu în cache > 164 cicli

Costul unei operații care nu găsește datele în cache este extrem de substanțial, datorită complexității protocoalelor (în articolul anterior din PC Report am văzut ca la un Pentium uniprocesor durata este de ordinul a 13 cicli de procesor). Din cauza asta implementarea unor protocoale de coerență eficiente este extrem de importantă, dar performanța obținută datorită unui număr ridicat de procesoare compensează costul ridicat al execuției fiecăruia.

Voi încheia acest articol aici, deși îmi propusesem să mai atac și alte subiecte; rezultatul însă pare destul de consistent, așa că o să amîn pentru alte ocazii discuții despre subiecte subtile cum ar fi: alte protocoale de coerență, sau impactul modului în care e implementat un protocol de coerență pentru performanța anumitor construcții din programele utilizatorilor. Vă îndemn să studiați cu atenție diagramele de mai sus. Chiar dacă conceptele sunt pe alocuri simplificate, scenariile sunt toate plauzibile. În definitiv e foarte plăcut să înțelegi sculele cu care lucrezi, nu?



Footnotes

... faliment1
La ora asta supercalculatoare mai fabrică numai Intel, IBM, Silicon Graphics -- care a cumpărat în 1987 cea mai celebră firmă de supercalculatoare, Cray Research -- Hitachi și dacă nu mă înșel Fujitsu.