Mihai Budiu -- mihaib+@cs.cmu.edu
http://www.cs.cmu.edu/~mihaib/
16 septembrie 1998
Acest articol va construi un mic set de rutine pentru a măsura durata execuției unor bucățele de program după care va folosi aceste rutine pentru a estima tot felul de parametri arhitecturali. Am spart articolul în două bucăți: în prima voi discuta despre măsurători în general; apoi voi construi infrastructura necesară măsurătorilor, după care arăt cum putem măsura anumiți parametri ai calculatorului. În a doua parte a articolului urmează să fac o muncă ``detectivistă'' care arată cum se pot folosi măsurătorile de performanță pentru a trage concluzii despre anumiți parametri arhitecturali care influențează viteza doar în mod indirect. Ca exemplu, intenționez să ilustrez cum se pot face tot felul de măsurători ale caracteristicilor cache-ului microprocesorului Pentium II. Majoritatea ideilor și codului din acest articol au fost dezvoltate ca teme la cursul de arhitectura calculatoarelor pe care autorul l-a luat în toamna anului 1997 la CMU. Creditul pentru aceste idei i se cuvine unuia dintre profesori, Randy Bryant.
Într-un articol anterior, despre natura cercetării în ``sisteme'' (PC Report din martie 1998), discutam despre importanța evaluării programelor. Majoritatea articolelor de cercetare din domeniu conțin măsurători ample, care controlează feluriți parametri și studiază variația altora. Măsurarea unui sistem complex este foarte dificilă, și există o sumedenie întreagă de tehnici care se pot utiliza. Importanța măsurătorilor a fost recunoscută și de proiectanții de microprocesoare: toate procesoarele moderne oferă suport extins pentru măsurarea a tot felul de evenimente importante. Un articol recent din PC Report (``Tehnologia MMX, partea a II-a'', Iulie 1998, de Valer Bocan) arăta lista tuturor măsurătorilor pentru care procesorul Pentium are suport din fabricație: o pagină întreagă.
Există foarte multe feluri de măsurători; o privire superficială poate distinge următoarele clasificări:
Probabil cele mai frecvente măsurători sunt cele făcute pentru a vedea unde un program își petrece cel mai mult timp. Acest tip de măsurătoare se numește profiling. Metoda obișnuită pentru astfel de măsurători este de a genera periodic întreruperi și de a marca locul execuției programului în clipa întreruperii. Acesta este un exemplu tipic de măsurătoare statistică. Compilatoarele de C generează cod cu măsurători prin folosirea opțiunii -p. Programe ca prof și gprof sunt folosite pentru a analiza rezultatele.
Este inutil de zis că a construi un simulator foarte precis este o treabă extrem de complicată. Se întîmplă adesea ca unele dintre fenomenele care nu sunt luate în considerare de către simulare să aibă în realitate un impact foarte important asupra performanței.
Pe de altă parte, atunci cînd măsurăm un program, putem modifica programul însuși pentru a înregistra chiar el numai evenimentele importante. Problema este că aceste modificări afectează programul însuși; nu numai din cauză că strîngerea informației ia timp, dar și pentru că așezarea codului și datelor în memorie se schimbă, de unde tot felul de efecte noi în cache-uri, în interferențe cu memoria virtuală, etc.
Înainte de a plonja în concret să menționăm și faptul că interpretarea rezultatelor testelor este adesea foarte dificilă. După cum vom vedea în partea a doua a acestui articol, mai multe fenomene pot da naștere unor efecte similare, iar atunci cînd putem avea de-a face cu interferența mai multor fenomene este foarte greu de depistat cauza reală a unor rezultate.
După ce am vorbit despre tot felul de metode, care mai de care mai sofisticate, voi ilustra în acest articol o metodă foarte simplă de auto-instrumentare a unui program, care poate fi folosită pentru a măsura destul de precis chiar evenimente foarte scurte.
Măsurarea timpului este o treabă a sistemului de operare, așa că avem nevoie de un oarecare suport din partea acestuia. Voi folosi pentru exemplificare sistemul de operare Unix; programele din acest text au fost testate pe mai multe sisteme, incluzînd Linux, SunOs, Solaris și Digital Unix. Metodologia poate fi probabil însă folosită și pe sisteme din familia Windows, în măsura în care contabilizarea timpului pentru programe se face într-un fel asemănător (acest subiect îmi este, din păcate, străin).
Nucleul unui sistem Unix menține pentru fiecare proces trei contoare independente, numite ``ceasuri de interval'' (interval timers). Utilizatorul are la dispoziție două funcții de bibliotecă pentru a citi și scrie aceste ceasuri; scrierea se face cu setitimer() iar citirea cu getitimer().
Timpul însuși este reprezentat într-o structură care se numește struct timeval. Pe sistemele citate anterior structura aceasta este foarte simplă:
struct timeval {
long tv_sec; /* secunde */
long tv_usec; /* microsecunde */
};
Un ``itimer'' (interval timer) are două astfel de structuri înauntru:
struct itimerval {
struct timeval it_interval; /* timer interval */
struct timeval it_value; /* current value */
};
Cînd un astfel de ceas ``expiră'', nucleul trimite procesului în cauză un semnal. Din fericire pe noi nu ne vor interesa semnalele: vom folosi aceste ceasuri într-un mod mai simplu, pentru a măsura durata unor evenimente: setăm valoarea curentă a lui it_value, executăm codul de măsurat, și apoi citim it_value din nou; făcînd diferența vom afla cît a durat execuția.
Unix este un sistem de operare multitasking: mai multe procese se pot executa ``simultan''. De obicei nu avem la dispoziție tot atîtea procesoare cît procese de executat, așa că modul în care mai multe programe își ``împart'' calculatorul este prin time-sharing: o bucățică de timp se execută unul, apoi programul este suspendat și se execută un al doilea, etc.
Nucleul oferă deci două feluri de timere pentru procese (de fapt trei, dar numai două ne interesează pe noi acum): unul care măsoară timpul real scurs (numit și timpul ceasului de pe perete: ``wall-clock time'') și unul care măsoară timpul ``virtual'': numai timpul cît procesul măsurat a fost în execuție.
Noi vom folosi ambele timere, în funcție de ceea ce vrem să măsurăm.
Vom scrie trei funcții de bază care manipulează aceste timere; iată declarațiile lor în fișierul etime.h:
/* fisierul etime.h */
#ifndef _ETIME_H
#define _ETIME_H
void init_etime(void); /* initializeaza ceasurile */
double get_etime(void); /* calculeaza timpul virtual scurs de la
initializarea ceasurilor, in secunde */
double get_ewtime(void);/* timpul real scurs de la initializarea
ceasurilor */
#endif
Aceste funcții sunt relativ simplu de scris, dacă citim cu atenție explicațiile din manual ale funcțiilor getitimer și setitimer. Am presupus că nici unul dintre programele măsurate nu se va executa mai mult de o zi, și de aceea am pus lungimea intervalului de măsurat la 24 * 60 * 60 = 86400 secunde. Iată codul:
/* fisierul etime.c: manipulare de timere */
#include "etime.h"
#include <stdio.h>
#include <sys/time.h>
/* memoreaza timpul virtual ramas */
static struct itimerval init_virtual;
/* timpul real ramas */
static struct itimerval init_real;
#define MAX_ETIME 86400 /* o zi = un interval foarte mare. */
void init_etime(void)
{
init_virtual.it_interval.tv_sec = 0;
init_virtual.it_interval.tv_usec = 0;
init_virtual.it_value.tv_sec = MAX_ETIME;
init_virtual.it_value.tv_usec = 0;
setitimer(ITIMER_VIRTUAL, &init_virtual, NULL);
/* ultimul argument al lui setitimer citeste valoarea
timerului inainte de a fi modificat; nu ne intereseaza,
deci folosim NULL */
init_real.it_interval.tv_sec = 0;
init_real.it_interval.tv_usec = 0;
init_real.it_value.tv_sec = MAX_ETIME;
init_real.it_value.tv_usec = 0;
setitimer(ITIMER_REAL, &init_real, NULL);
}
double get_etime(void)
/* elapsed time: timp scurs */
{
struct itimerval curent;
getitimer(ITIMER_VIRTUAL, &curent);
/* cite secunde au trecut de cind am setat init_virtual? */
return (double)((init_virtual.it_value.tv_sec -
curent.it_value.tv_sec) +
(init_virtual.it_value.tv_usec -
curent.it_value.tv_usec) * 1e-6);
/* 1e-6 = marimea unei microsecunde in secunde. */
}
double get_ewtime(void)
/* elapsed wall time: timp scurs real */
{
struct itimerval curent;
getitimer(ITIMER_REAL, &curent);
return (double) ((init_real.it_value.tv_sec - curent.it_value.tv_sec) +
(init_real.it_value.tv_usec - curent.it_value.tv_usec)*1e-6);
}
Deși sunt multe litere, ce se întîmplă ar trebui să fie evident. Observați că ceasurile numără ``în jos'' (descresc de la valoarea inițială spre 0), și de aceea scad valoarea curentă din cea inițială și nu invers.
Buun. Avem deci o metodă pentru a măsura cît timp a trecut. Primul lucru pe care o să-l facem este să vedem ce rezoluție are timerul însuși. Cu alte cuvinte: cu ce frecvență bate ceasul? Nu ne putem aștepta ca valoarea timer-ului să fie ajustată foarte frecvent, pentru că aceasta ar lua foarte mulți cicli din execuția programelor însele.
Pentru a măsura rezoluția ceasului ne vom folosi de faptul că ceasul se mișcă relativ încet. Mult mai încet decît durata executării unei funcții sau a unui apel de sistem. Cu alte cuvinte, pot executa de multe ori funcția get_etime între două bătăi ale ceasului. Acest lucru este fundamental pentru buna funcționare a programelor de măsurare pe care le scriem, și îl vom verifica puțin mai tîrziu. În orice caz, știm din folclor (sau, dacă nu, din alte articole din PC Report) că un apel de sistem pe o mașină modernă durează de ordinul zecilor de microsecunde, pe cînd rezoluția ceasului este în zona milisecundelor (de sute de ori mai mică).
Vom scrie deci un program foarte simplu care nu face decît să citească ceasul în mod repetat pînă sesizează o schimbare. Din cauză că citirile vor fi mult mai dese decît ticăirile ceasului, suntem siguri că vom vedea cu cît se schimbă ceasul la fiecare bătaie. Funcția delta() calculează rezoluția ceasului:
/* functia delta(): masuratoarea rezolutiei ceasului SO */
double delta(void)
{
double curent, inainte,
mindelta = 10; /* valoare ridicol de mare */
int repetam = 3; /* masuram de mai multe ori, ca sa fim siguri */
inainte = get_etime();
while (repetam) {
curent = get_etime();
if ((curent - inainte) > 1e-6) {
repetam--;
if ((curent - inainte) < mindelta)
/* avem o estimare mai buna pentru rezolutie */
mindelta = curent - inainte;
inainte = curent;
}
}
return mindelta;
}
(Observați metoda de a compara valori double). Încercați-o:
/* exemplu: masurarea delta() */
#include <stdio.h>
#include "etime.h"
double delta(void);
int main(void)
{
init_etime();
printf("Rezolutia ceasului este %2.3fms\n", delta()*1000);
return 0;
}
Ce ne facem însă cu intervalele foarte scurte? Cum poți să măsori un eveniment care durează o microsecundă dacă ai un ceas care are ca unitate de măsură de 10ms? Din fericire nu e prea greu: un calculator e foarte bun la a repeta aceeași operațiune de milioane de ori. Ce trebuie să facem este să executăm operația de măsurat de -- să zicem -- un milion de ori, și să împărțim rezultatul măsurătorii la un milion.
De fapt trebuie să fim ceva mai grijulii, din două motive:
Acestea fiind zise, vom purcede la a scrie o funcție generică numită ftime care are trei argumente:
Pentru a limita eroarea, trebuie să facem un pic de aritmetică. Să presupunem că vrem ca eroarea să fie sub 1 procent. Atunci dacă ceasul bate cu perioada de X, trebuie să măsurăm numai durate de cel puțin 101X. De ce? Orice măsurătoare este eronată cu cel mult +/-X, deci eroarea va fi sub 1 procent.
Mai general, dacă vrem o eroare mărginită de 
procente
și rezoluția ceasului este 
atunci trebuie să rulăm testul
timp de
. Formula nu e prea greu de
demonstrat riguros, dar datorită formatului PC Report formulele
matematice sunt ceva mai greu de tehnoredactat. Voi adăuga
demonstrația ca anexă în varianta articolului care se găsește în
pagina mea de web.
/* functia ftime: masuratoarea duratei unei alte functii */
#include "etime.h"
/* puneti functia delta() aici */
double ftime(void (*de_masurat)(void), double epsilon, int timp_real)
{
double durata; /* cit timp trebuie executat testul */
unsigned long repetitii;
double inceput, sfirsit;
static double Delta;
static int initializat = 0;
double (*masoara)(void);
masoara = timp_real ? get_ewtime : get_etime;
if (!initializat) {
/* prima oara calculam Delta */
initializat = 1;
Delta = delta();
}
durata = (1 + epsilon) * Delta / epsilon;
for (repetitii = 1; ; repetitii *= 2) {
int i;
inceput = masoara();
for (i=repetitii; i > 0; i--)
de_masurat();
sfirsit = masoara();
if (sfirsit - inceput >= durata) break;
}
return ((sfirsit - inceput) / (double)repetitii);
}
Funcția este destul de simplă: va dubla numărul de repetiții al
executării funcției de măsurat pînă cînd în total repetițiile
depășesc suficient durata necesară pentru a mărgini eroarea.
Dacă vă îngrijorează numărul mare de execuții al buclei,
observați că numărul de execuții al funcției de măsurat descrie
o serie geometrică (se execută de 1, 2, 4, 8, etc. ori), deci
numărul total de execuții nu va depăși niciodată 2*durata,
unde durata este durata necesară pentru a limita eroarea (și
asta e ușor de demonstrat). Pentru calculatorul meu este
10ms, deci pentru o eroare de 1% durata este 1s. Durata
măsurătorii nu va depăși deci 2 secunde (decît dacă funcția de
măsurat durează mai mult).
Știu că vă grăbiți să încercați codul, așa că dați-i drumul:
/* prima masuratoare */
#include <stdio.h>
#include "etime.h"
/* puneti aici delta() si ftime() */
void f(void)
{
/* scrieti aici codul de masurat, ce vreti */
}
int main(void)
{
init_etime();
printf("Durata executarii lui f este %2.2fsec\n", ftime(f, 0.01, 0));
return 0;
}
Din păcate am văzut (din fugă) că un sistem care se auto-măsoară este supus la perturbații (un fel de principii de incertitudine a la Heisenberg). Nici programul nostru nu este scutit de astfel de probleme. Nu putem face foarte mult pentru a le corecta, dar este foarte bine să le avem în vedere. Iată unele posibile interferențe:
Sau să luăm un alt caz: apariția unui pachet pe rețea. Nucleul trebuie să citească pachetul și probabil să-l trimită pe o altă interfață, sau să-l livreze unui proces. Dar din momentul apariției pachetului pînă la livrare nu este încă evident cui îi este destinat acesta (poate unei alte mașini). Ori timpul de procesare al pachetului trebuie contabilizat și el undeva. În general toate întreruperile (de disc, de la tastatură, etc.) suferă de problema asta.
Din această cauză, măsurătorile vor fi mai precise dacă mașina nu este deloc încărcată (nu execută prea multe procese) și nu este conectată la rețea. Cît de mare este eroarea vă invit să experimentați făcînd măsurători pe două mașini: una aglomerată și una liberă.
Conflicte de cache pot fi și între sistemul de operare și programul de măsurat etc. O cutie a Pandorei, ce mai.
Hai să exersăm acum procedurile de mai sus pe niște operațiuni interesante. Vom măsura pentru început cea mai scurtă durată din calculator: frecvența de tact a microprocesorului! Aceasta este efectiv uriașă: un procesor la 333Mhz are un ceas de 3ns, de 3 milioane de ori mai mică decît rezoluția Delta (10ms) a ceasului!
Cum putem să măsurăm o durată atît de scurtă? În primul rînd, cum putem scrie un program atît de scurt? Nici nu putem. Dar vom face același truc: vom repeta aceeași instrucțiune foarte scurtă de multe ori.
Ce instrucțiune durează exact un ciclu de ceas? Practic, pe toate procesoarele RISC sau CISC o adunare de numere întregi durează exact un ciclu de ceas.
Va trebui să fim atenți însă cînd scriem codul la următoarele aspecte:
/* masurarea ceasului microprocesorului */
int ax; /* niste variabile globale pentru a impiedica optimizari */
int bx;
int cx;
/* niste macrouri simpatice pentru a genera 100 de repetitii */
#define DOI(x) x x
#define PATRU(x) DOI(x) DOI(x)
#define CINCI(x) x PATRU(x)
#define DOUASCINCI(x) CINCI(CINCI(x))
#define OSUTA(x) PATRU(DOUASCINCI(x))
void add_test(void)
{
register int a = ax;
register int b = bx;
register int c = cx;
OSUTA(a += b; a += c;) /* doua adunari dependente! */
ax = a+b+c; /* pentru ca scriem intr-o variabila globala
compilatorul nu va scoate nici o adunare
din program */
}
void add_dummy(void)
{
register int a = ax;
register int b = bx;
register int c = cx;
ax = a+b+c;
}
double mhz(double epsilon)
{
double secs;
secs = ftime(add_test, epsilon, 0) - ftime(add_dummy, epsilon, 0);
return (200.0 / secs) / 1e6; /* add_test are 200 instr.
mai mult decit add_dummy */
}
Am fost foarte atent să compensez diferența între costul celor 200 de instrucțiuni de adunare și instrucțiunile suplimentare, calculînd durata unei proceduri add_dummy, care conține numai codul parazit și scăzînd cele două valori. Am testat codul ăsta pe o mașină rapidă: un Pentium II la 266Mhz astfel:
#include <stdio.h>
#include "etime.h"
/* puneti aici ftime(), delta(), mhz() si prietenii lor */
int main(void)
{
init_etime();
printf("Frecventa ceasului este %gMhz\n", mhz(0.02));
return 0;
}
Cu o eroare tolerată de 2% am ob'tinut r'aspunsul: 266.3MHz. Destul de bine, nu?
Asta este deja o treaba foarte simplă de calculat. Pur și simplu folosim programul de mai sus, numit ``prima măsurătoare'', fără a pune nimic în corpul funcției f. Pe sistemul meu timpul a ieșit 33.9ns, adică aproximativ 9 cicli de procesor.
Este interesant de măsurat care este durata executării unui apel de sistem (un serviciu elementar oferit de nucleu). Măsurarea timpului însăși folosește funcția getitimer() care la rîndul ei folosește un apel de sistem.
Trebuie să fim însă foarte atenți să măsurăm apeluri de sistem idempotente, adică a căror execuție repetată va da mereu aceleași rezultate. De exemplu, probabil că nu putem măsura durata citirii dintr-un fișier folosind metoda noastră, pentru că numai prima citire va accesa discul; a doua va lua datele din cache. Aceasta este o limitare importantă a testelor repetitive, ca cel pe care l-am scris.
De asemenea, pentru că nu este foarte clar cui îi atribuie nucleul timpul petrecut în timpul unui apel de sistem, vom măsura timpul real. Dacă apelul nu este blocant, avem șanse ca în timpul testului să nu fie executat nici un alt proces. Această măsurătoare e musai sa fie executată pe o mașină ne-încărcată, pentru că altfel rezultatele vor fi puternic distorsionate de celelalte procese.
Oricum, pentru un apel de sistem foarte simplu, cum e getpid() (pentru multe alte detalii privitoare la acesta vedeți și articolul meu din PC Report ianuarie 1998, ``Anatomia unui apel de sistem'') putem rula următorul cod:
/* masurarea unui apel de sistem */
/* nu uitati sa includeti get_etime(), etc... */
#include <unistd.h>
int main(void)
{
init_etime();
printf("Un apel de sistem dureaza %fs\n", ftime(getpid, 0.02, 1));
/* o sa obtineti un warning la compilare din cauza ca
getpid intoarce de fapt un intreg; nu-i problema. */
return 0;
}
Pe aceeași mașină, rulînd Linux 2.0.30, am obținut un timp de 2.00 microsecunde pentru un apel de sistem. Am avut deci dreptate: un apel de sistem e mult mai scurt decît rezoluția ceasului.
În fine, încheiem această parte a articolului cu o măsurătoare a duratei comutării între două procese.
Vom scrie două procese care știm că se blochează reciproc, în așa fel încît execuția se pasează de la unul la celălalt. Din nou, măsurăm timpul real.
Programul acesta cere cîteva cunoștințe elementare despre Unix; unele dintre funcțiile componente le-am explicat mai demult, de exemplu în articolul ``Shell-ul'' din PC Report iunie 1997.
Ideea este simplă: deschid două țevi și fac două procese: unul citește din una și scrie în cealaltă cîte un caracter și viceversa. Cînd un proces încearcă să citească dintr-o țeavă goală se blochează; în acest fel la fiecare citire/scriere se produce și o comutare de procese. Măsurătoarea se face numai de către procesul părinte.
/* masurarea timpului de comutare intre procese */
#include <unistd.h>
int p[2], r[2];
char c;
void t(void)
{
write(r[1], &c, 1);
read(p[0], &c, 1);
}
double forktest(void)
{
int copil;
if (pipe(p) < 0 || pipe(r) < 0) exit(1);
copil = fork();
if (copil) {
double rv = ftime(t, 0.01, 1);
kill(copil, 9);
return rv;
}
else {
while (1) {
read(r[0], &c, 1);
write(p[1], &c, 1);
}
return 0;
}
}
int main(void)
{
init_etime();
printf("Comutarea intre 2 procese dureaza %gus\n", 1e6*forktest());
return 0;
}
Pe mașina mea rezultatul afișat a fost: 17.8528us. Asta include evident și costul a patru apeluri de sistem (cîte un read și un write în fiecare din procese) și două comutări (dus-întors). Asta înseamnă că o comutare de fapt durează cam 17 - 4*2 / 2 = 4.5 microsecunde. Asta este o performanță excelentă pentru un sistem de operare, fiind și una dintre explicațiile succesului Linux.
Nu pot decît să vă invit să exersați măsurătorile pe tot felul de alte probleme. De exemplu, este mult mai greu să măsurați timpul de creare al unui proces, din cauza ne-idempotenței. Măsurați apoi tot felul de alte lucruri, ca timpul de acces la disc, timpul de transfer în rețea, etc. Vedeți ce iese. În partea a doua vom continua explorările utilizărilor măsurătorilor pe niște cazuri mult mai complicate.
În numărul anterior din PC Report (septembrie 1998) am văzut cum putem măsura intervale de timp folosind instrumentele puse la dispoziție de către sistemul de operare; de asemenea am folosit aceste instrumente pentru a ne face o idee despre durata unora dintre activitățile fundamentale, cum ar fi tactul procesorului, durata unui apel de procedură, durata unui apel de sistem, etc. Codul procedurilor din acel articol este disponibil și din pagina de web a autorului, pentru cei care nu au cumpărat numărul anterior al revistei, sau pentru cei care sunt prea leneși ca să tasteze.
În acest articol vom continua să folosim măsurătorile de timp, dar de data aceasta în scopuri indirecte. Activități de acest gen sunt foarte des întîlnite în proiectarea sistemelor de calcul: măsurarea directă a unor parametri este adesea imposibilă, și ca atare proiectanții trebuie să măsoare fenomene diferite, iar apoi printr-un raționament de la efecte spre cauze să deducă motivele cărora rezultatele li se datorează.
Cu cît sistemele în cauză sunt mai complicate, cu atît mai dificil de interpretat devin rezultatele. Dacă un efect poate fi produs de cauze multiple, din care unele nu sunt sub controlul direct al experimentatorului, atunci devine foarte greu de explicat cu exactitate în ce măsura rezultatul este o interferență a părților componente și ce contribuție are fiecare dintre ele.
Chiar și acest articol, care măsoară un sistem relativ simplu și aflat în întregime (aproape) la dispoziția experimentatorului, va avea pe alocuri dificultăți în a explica unele dintre fenomene. Pentru că informațiile pe care le voi extrage din măsurători sunt în mare parte nepublicate de către fabricanți, nici nu avem o metodă directă de a le verifica; este posibil ca erori de interpretare să se fi strecurat în raționamentele mele. Cititorii care le vor decela sunt invitați să le comunice autorului.
O figură marcantă în galeria celebrităților proiectanților de sisteme este Mahadev Satyanarayanan1. Domnului Satyanarayanan îi este atribuit un citat care afirmă că în proiectarea sistemelor există doar două unelte fundamentale:
Aserțiunea este cel puțin spectaculoasă și este rezultatul distilării experienței de zeci de ani de proiectare a unor sisteme complexe. Eu personal nu sunt capabil să argumentez pro sau contra, dar îmi sprijin inserția acestui citat pe autoritatea incontestabilă a domnului Satyanarayanan.
Despre cache-uri am publicat un articol amplu în PC Report din martie 19972; cu toate acestea, sunt departe de a fi spus totul despre ele (chiar în textul de față ne vom întîlni cu multe lucruri noi). Pentru că de fapt restul articolului va fi consacrat în întregime cache-ului asociat microprocesorului, o să spun doar cîteva cuvinte despre noțiunea de indirectare, din dorința de completitudine.
Indirectarea este oferită de către ``referințe'' (pointeri): în loc de a vorbi despre o valoare vorbești despre locul unde se află acea valoare. Noțiunea de variabilă este un exemplu de indirectare: cînd vorbesc despre X nu spun ce valoare are X, dar am la dispoziție o metodă pentru a afla această valoare atunci cînd am nevoie. Un nume dat unui obiect este o indirectare pentru acel obiect. Numele simbolice din Internet sunt indirectări pentru adrese reale ale calculatoarelor, un callback este o indirectare pentru o funcție care trebuie chemată, un număr de inod este un nivel de indirectare pentru un fișier pe disc în Unix, etc.
Să revenim acum la cache-uri. Dacă vreți un studiu detaliat al arhitecturii cache-urilor de microprocesor atunci trebuie să citiți capitolul 5 din cartea ``Computer Architecture: A Quantitative Approach'', ediția a IIa, Morgan Kaufmann, 1995, de David Patterson, de la universitatea Berkeley și John Hennessy, de la universitatea Stanford3. Această carte (și versiunea ei oarecum simplificată ``Computer Organization and Design: The Hardware/Software Interface'', de aceeași autori, 1998) este baza majorității cursurilor de arhitectura calculatoarelor din Statele Unite. Capitolul 5 numai are 100 de pagini și rezumă circa 1600 de articole de cercetare publicate numai între 1989 și 1995.
Pentru concretețe voi studia cache-ul atașat procesorului mașinii aflate pe biroul meu, un Pentium II la 266Mhz, vechi de un an (poate între timp detaliile arhitecturale s-au schimbat).
Știm că programul și datele pe care acesta le prelucrează se află în mod normal în memoria calculatorului (iar atunci cînd calculatorul este stins, pe disc). O memorie DRAM tipică pentru un calculator modern are un timp de acces de ordinul a 50 de nanosecunde; asta înseamnă că din clipa în care procesorul vrea să ia un cuvînt din memorie pînă la livrarea lui trec 50 de nanosecunde.
Procesorul meu însă (pe lîngă faptul că este o mașină superscalară, deci poate executa mai multe instrucțiuni deodată) poate executa o instrucțiune în fiecare ciclu de ceas; la 266Mhz asta înseamnă ceva mai puțin de 4 nanosecunde pentru o instrucțiune.
Discrepanța între acești timpi este foarte mare. Soluția de a folosi memorii mult mai rapide, SRAM, nu este practică pentru că SRAMul este de cîteva zeci de ori mai scump decît DRAMul, deci prețul calculatorului ar crește prea mult.
Din fericire procesorul tinde să re-folosească fiecare dintre instrucțiunile executate și dintre datele prelucrate de mai multe ori în intervale scurte de timp; această proprietate (observată empiric) a programelor se numește ``localitate'', și este cea care permite ingenioasa soluție a cache-urilor: construim o memorie intermediară numită ``cache'' (de la ``ascuns''), cu timp mic de acces, dar de capacitate mică. Atunci cînd procesorul vrea să prelucreze date le aduce în cache. Prima oară o să aștepte, dar a doua oară timpul de acces va fi redus simțitor. Cînd cache-ul se umple procesorul elimină dintre datele care probabil nu vor mai fi folosite în curînd.
Asta e ideea de bază, și este extrem de practică. Noi înșine, oamenii, tindem să repetăm materia înaintea unui examen, pentru a împrospăta cunoștințele din ``cache'' (memoria de scurtă durată și capacitate mică), folosind aceeași observație despre localitate (și anume că putem uita totul de îndată ce examenul a trecut).
O încercare de acces care găsește datele în cache se numește ``lovitură'' (hit); un rateu în engleză se cheamă ``miss''. Evident, un rateu este întotdeauna mai costisitor (ca timp) decît o nimereală.
Dacă datele cerute nu sunt în cache, atunci de obicei procesorul este blocat (stalled) pînă cînd se face transferul din memoria lentă.
Pentru că în cache se pot afla simultan doar o parte din octeții din memorie, fiecare cuvînt din cache este însoțit de o ``etichetă'' (tag) care arată de unde vine acel cuvînt.
În primul nostru experiment vom încerca să măsurăm cît de mare este cache-ul asociat procesorului.
Cum facem asta? Simplu: citim din memorie date aflate una lîngă cealaltă. Dacă datele încap toate în cache, durata unei citiri repetate va fi în medie mică. Dacă datele nu încap însă, de fiecare cînd citim o dată nouă una veche va trebui să fie scoasă și cea nouă adusă din memorie. În felul acesta, de îndată ce citim mai multe date decît încap în cache, trebuie să observăm o încetinire a vitezei de execuție.
Am scris deci următorul program:
/* Masurarea ratei de transfer din memorie (cache) */
#include "ftime.h" /* procedurile pentru masurat */
#define MAXTRANSFER (4 * 1024 * 1024) /* 4 Mb */
typedef int unitate; /* unitatea de transferat: 4 octeti */
union {
char array[MAXTRANSFER];
unitate aliniament;
} de_transferat;
int TRANSFER; /* citi octeti transferam */
register dummy;
#define UNROLL 64
#define ACCES(adresa) a += *(adresa);
#define ACCES4(adresa) \
ACCES(adresa+0) ACCES(adresa+1) \
ACCES(adresa+2) ACCES(adresa+3)
#define ACCES16(adresa) \
ACCES4(adresa+0) ACCES4(adresa+4) \
ACCES4(adresa+8) ACCES4(adresa+12)
#define ACCES64(adresa) \
ACCES16(adresa+0) ACCES16(adresa+16) \
ACCES16(adresa+32) ACCES16(adresa+48)
void citire(void)
{
register int i;
register unitate a;
register int *b = (int*)de_transferat.array;
for (i = TRANSFER / sizeof(unitate); i >= 0; i -= UNROLL) {
ACCES64(b)
b += UNROLL;
}
dummy = a;
}
void citire_ajustare(void)
{
register int i;
register unitate a;
register unitate *b = (unitate*)de_transferat.array;
for (i = TRANSFER / sizeof(unitate); i >= 0; i -= UNROLL) {
b += UNROLL;
}
dummy = a;
}
int main(void)
{
int i;
double Mhz, durata_ciclu;
init_etime();
Mhz = mhz(0.02);
durata_ciclu = 1.0 / Mhz / 1e6;
printf("Frecventa ceasului este %gMhz\n", Mhz);
for (i=0; i < MAXTRANSFER; i++)
de_transferat.array[i] = 0;
for (TRANSFER=512; TRANSFER < MAXTRANSFER; TRANSFER <<= 1) {
double t = ftime(citire, 0.01, 0) - ftime(citire_ajustare, 0.01, 0);
printf("Cantitate %d, rata %2.2fMb/s, %2.2fcicli/cuvint\n",
TRANSFER,
(double)TRANSFER / t / (1024*1024),
t / durata_ciclu / TRANSFER);
}
return 0;
}
Ce se întîmplă trebuie să fie destul de clar pentru cei care au citit prima parte a articolului. Cu toate acestea trebuie să fim atenți la anumite subtilități.
Folosim funcțiile mhz(), init_etime(), ftime(), dezvoltate data trecută. Facem măsurătoarea citind cuvinte adiacente dintr-un vector foarte mare. Pentru că citim cîte un întreg odată, care are probabil 4 octeți, trebuie să luăm niște măsuri de precauție. Multe calculatoare nu permit citirea datelor ne-aliniate: orice cuvînt de 4 octeți trebuie să fie accesat la o adresă multiplu de 4. Acesta este și scopul acelei union din programul de mai sus: vectorul de caractere numit array va fi aliniat în același fel cu întregul numit aliniament, pe care compilatorul de C garantează să-l pună la o adresă multiplu de 4. Pentru Pentium aliniamentul nu contează de fapt, dar codul de mai sus funcționează și pentru alte procesoare.
O altă tehnică foarte interesantă și demnă de reținut este desfășurarea buclei (loop unrolling). În loc să repetăm de un număr de ori o citire din memorie repetăm de 64 de ori mai puțin 64 de citiri din memorie.
De ce facem asta? Pentru că în felul acesta facem de 64 de ori mai puține incrementări ale contorului buclei, și facem de 64 de ori mai puține teste de terminare a buclei. Din cauza asta măsurătoarea este mai precisă. Tehnica aceasta este folosită cu succes și de către compilatoarele care optimizează. Pe lîngă faptul că numărul de instrucțiuni utile executate crește, o buclă cu un corp mai lung oferă mai multe oportunități pentru ``scheduling'', dînd posibilitatea procesorului să execute mai multe instrucțiuni simultane mai des.
Variabila dummy este folosită pentru a împiedica compilatorul să optimizeze prea tare codul (întreaga buclă ar deveni inutilă altfel).
Esențială este execuția buclei for care inițializează toată matricea de_transferat.array cu 0: dacă nu facem treaba asta sistemul de operare nici măcar nu va aloca pentru noi memoria respectivă și orice citire din acea memorie va da automat un rezultat 0, fără ca memoria să fie citită de fapt. (Mi-au ieșit peri albi pînă am înțeles de ce măsurătorile care nu inițializau matricea dădeau rezultate aberante.)
Iată și rezultatele măsurătorii:
| Octeți | MB/s | Cicli/cuvînt |
| 512 | 961.50 | 1.06 |
| 1024 | 972.92 | 1.05 |
| 2048 | 934.09 | 1.09 |
| 4096 | 958.68 | 1.06 |
| 8192 | 971.47 | 1.05 |
| 16384 | 933.42 | 1.09 |
| 32768 | 474.40 | 2.15 |
| 65536 | 474.23 | 2.15 |
| 131072 | 474.15 | 2.15 |
| 262144 | 426.70 | 2.39 |
| 524288 | 316.05 | 3.23 |
| 1048576 | 228.57 | 4.47 |
| 2097152 | 228.57 | 4.47 |
| 4194304 | 224.56 | 4.55 |
Observăm imediat un rezultat foarte interesant: viteza de transfer are 3 paliere, la 1Gb/sec, jumătate de Gb/s și un sfert de Gb/sec. De ce cele 3 valori diferite?
Din cauză că viteza procesoarelor crește -- datorită avansului tehnologiei -- mult mai repede decît viteza de răspuns a memoriei, calculatoarele moderne au de fapt 2 nivele de cache, unul mai mic și mai rapid, numit L1, de obicei din SRAM, și unul mai mare și ceva mai lent (L2). La procesorul Pentium II cache-ul L1 este pe același integrat cu procesorul, iar cache-ul L2 este în același soclu. Cache-ul L2 este de de obicei DRAM lent, dar are un bus extrem de lat și scurt, deci poate susține o rată de transfer relativ mare comparativ cu memoria de bază.
Măsurătorile de mai sus indică un cache L1 de 16Kb și un cache L2 de 512Kb.
Rata de transfer nu descrește subit la paliere ci se degradează pe măsură ce ocupăm mai mult din cache pentru că programul însuși și sistemul de operare folosesc părți din cache, care concurează pentru spațiu în cache cu matricea array. Efectul este însă destul de pronunțat.
Atunci cînd procesorul scrie date, ce se întîmplă cu cache-ul? La întrebarea asta atît de simplă există o multitudine de răspunsuri posibile.
Prima alegere pe care o are de făcut un designer este între a păstra valoarea scrisă numai în cache (asta se numește write-back) sau de a propaga simultan valoarea scrisă în nivelul următor al ierarhiei de memorie (write-through).
Avantajul metodei din urmă este că în fiecare clipă știm că ceea ce se găsește în cache la o anumită adresă este o copie fidelă a ceea ce se găsește în memorie (copiile sunt coerente). Asta simplifică oarecum lucrurile cînd avem de-a face cu mai multe microprocesoare care accesează aceeași memorie; de asemenea avem certitudinea că în cazul cînd anumite cuvinte sunt scoase din cache pentru a face loc altora valoarea lor nu mai trebuie salvată în nivelul inferior.
Pe de altă parte write-through nu poate scrie mai repede decît poate absorbi nivelul următor din ierarhia de memorii (e clar: pe o șosea nu pot intra mai multe mașini decît ies decît pentru foarte puțin timp).
Am rescris testul anterior astfel:
#define ACCES(a) (*(a) = 0);
....
void atinge(void) {
int i, a;
for (i=0; i < TRANSFER/sizeof(unitate); i++)
a += de_transferat.array[i];
dummy = 0;
}
int main(void)
{
for (...) { /* ca mai sus */
atinge();
.... /* ca mai sus */
}
}
Am schimbat macro-ul ACCES pentru a scrie în loc de a citi. În plus am scris o funcție mică, numită atinge(), care citește fiecare cuvînt din array înainte de a face măsurătoarea. Vom vedea în secțiunea următoare de ce vrem să atingem fiecare cuvînt înainte de a măsura.
Iată și rezultatele:
| Octeți | MB/s | Cicli/cuvînt |
| 512 | 849.79 | 1.20 |
| 1024 | 873.34 | 1.17 |
| 2048 | 856.00 | 1.19 |
| 4096 | 861.86 | 1.18 |
| 8192 | 857.57 | 1.19 |
| 16384 | 855.45 | 1.19 |
| 32768 | 237.11 | 4.31 |
| 65536 | 237.07 | 4.31 |
| 131072 | 237.05 | 4.31 |
| 262144 | 213.34 | 4.79 |
| 524288 | 158.02 | 6.46 |
| 1048576 | 88.88 | 11.50 |
| 2097152 | 76.19 | 13.41 |
| 4194304 | 75.29 | 13.57 |
Din nou avem trei paliere dar, exceptîndu-l pe primul, performanța este substanțial mai mică. Cu toate acestea putem afirma că cele două nivele sunt write-back. De ce? Dacă L1, de pildă, era write-through, am fi avut exact aceeași rată de transfer pentru tot domeniul 512 octeți -- 512 Kb.
De ce e rata de scriere mai mică decît cea de citire? Sunt mai multe posibile motive la mijloc:
Diferența între citire și scriere este că la citire pașii 2 și 3 de mai sus pot fi inițiați simultan. Pentru scriere însă pașii 2 și 3 trebuie efectuați strict unul după altul.
O altă alegere pe care o pot face proiectanții este dacă atunci cînd se scrie într-un cuvînt care nu se află în cache cuvîntul trebuie adus în cache sau scrierea trebuie făcută direct în nivelul următor. Dacă cuvîntul este totuși adus, cache-ul se cheamă ``write-allocate on write miss'', din motive evidente. Altfel cache-ul se numește ``write-around''. În general, un cache write-through este și write-around și invers, un cache write-back este write-allocate.
Pentru a verifica ipoteza este suficient să scoatem din programul anterior apelul funcției atinge(); măsurătorile ne confirmă că Pentium are un cache write-allocate pentru că performanța este foarte asemănătoare.
O întrebare la care este mult mai greu de răspuns este dacă există unul sau două cache-uri separate pentru program și date. Modul de acces la instrucțiuni este foarte diferit de modul de acces la date, așa că are sens ca două cache-uri diferite să se ocupe de cele două zone diferite. În plus, în general, datele și codul sunt puse în memorie în zone complet diferite.
Pentru a putea răspunde la această întrebare ar trebui să scriem un program care se auto-modifică și care poate controla propria sa așezare în memorie; treaba este posibilă dar relativ încîlcită, așa că o lăsăm ca un exercițiu pentru cititorul cu înclinații de hacker.
O căutare pe serverul de web de la Intel ne va indica faptul că există două cache-uri L1, ambele de 16K, unul pentru cod și unul pentru date. Numele tradiționale sunt I-cache (instruction-cache) și D-cache (data-cache).
L2 este însă un cache unificat: 512K pentru ambele foloase.
Gradul de asociativitate al unui cache arată cît de ușor poate fi localizat un cuvînt în cache. Cele mai simple cache-uri (numite direct-mapped) caută un cuvînt într-un mod foarte simplu: ignoră primii biți din adresă și indexează în cache cu adresa obținută. Dacă mărimea cache-ului este M, atunci toate cuvintele de memorie aflate la o adresă de forma kM + o, cu k întreg, se vor afla în același loc în cache, la adresa o (desigur, nu toate simultan; cel mult unul dintre ele la un moment dat). Cache-urile directe sunt foarte simplu de construit, sunt mici (ca circuite hardware) și foarte rapide.
Varianta alternativă este ca un cuvînt din memorie să se poată afla într-unul din mai multe locuri din cache. Dacă avem un cache de mărime asociativ pe n căi4 atunci există n locuri în care un cuvînt de la o adresă se poate afla. Și anume cuvîntul de la adresa X se poate afla la oricare din adresele multiple de X mod (M/n).
De exemplu pentru M=16 (ridicol de mic), n=4, cuvîntul de la adresa 1 din memorie se poate afla în cache în oricare din adresele 1, 5, 9 și 13.
Un cache asociativ este mult mai flexibil decît unul direct. De exemplu, în cache-ul asociativ de mai sus, se pot afla simultan cuvintele din memorie de la adresele 1 și 17, pe cînd într-un cache direct cu aceeași capacitate M=16 nu.
Cache-ul extrem, pentru care n=M, se numește complet asociativ (fully associative). Cu cît gradul de asociativitate (n) crește, cu atît complexitatea circuitului crește. Cu tehnologia curentă este complet ne-practic de implementat în hardware un cache complet asociativ mai mare de 256 de cuvinte.
Din această rațiune la Pentium II cache-ul L1 este asociativ pe 4 căi, iar L2 este direct. Cum am aflat asta? Am scris un mic test care încearcă să-l ghicească pe n. Ne-am bazat exact pe observația de mai sus.
Pentru cache-ul ipotetic de mai sus, cu M=16, am putea face următoarele teste:
Dacă primul test indică o rată de transfer la fel de mare ca transferul unor date consecutive, atunci știm că n >= 2, pentru că 1 și 17 încap simultan înauntru. Dacă viteza este substanțial mai mică știm însă că n = 2.
Dacă n >= 2, al doilea test ne va spune dacă n >= 4 în exact același fel. Ați prins ideea?
/* masurarea asociativitatii cache-ului L1 */
#define L1 (16 * 1024) /* tocmai am masurat astea */
#define L2 (512 * 1024)
int ASOC;
int BLOC;
void asociativitate(void)
{
register int i;
register unitate a;
register unitate *b = (unitate*)de_transferat.array;
for (i=ASOC; i > 0; i--) {
ACCES64(b);
b += BLOC;
}
dummy = a;
}
void asociativitate_ajustare(void)
{
register int i;
register unitate a;
register unitate *b = (unitate*)de_transferat.array;
for (i=ASOC; i > 0; i--) {
b += BLOC;
}
dummy = a;
}
int main(void)
{
int i;
double Mhz, durata_ciclu;
init_etime();
Mhz = mhz(0.02);
durata_ciclu = 1.0 / Mhz / 1e6;
printf("Frecventa ceasului este %gMhz\n", Mhz);
BLOC = L1;
for (i=1; i <= 16; i <<= 1) {
double t;
ASOC = i;
t = ftime(asociativitate, 0.01, 0)
- ftime(asociativitate_ajustare, 0.01, 0);
printf("Distanta %d, %2.2cicli/cuvint\n",
ASOC, t / durata_ciclu / ASOC / UNROLL);
}
return 0;
}
Testele măsoară cuvinte aflate la BLOC octeți unul de altul în RAM, cuvinte despre care știm că se vor bate pe aceeași linie din cache. Făcînd pe BLOC = L1 măsurăm asociativitatea lui L1 (și similar pentru L2). Încercăm felurite asociativități, toate puteri ale lui 2. Ne oprim la 16 în programul de mai sus, dar dacă asta nu e suficient putem continua testele.
Rezultatele numerice pentru L1 sunt următoarele:
| Distanța | cicli/cuvînt |
| 1 | 1.12 |
| 2 | 1.10 |
| 4 | 1.47 |
| 8 | 2.14 |
| 16 | 2.12 |
Asta ne confirmă într-adevăr că avînd un asociativitatea cache-ului L1 este 4.
Cum putem măsura asociativitatea cache-ului L2 fără a fi încurcați de faptul că L1 este asociativ el însuși? Trebuie să controlăm accesele în așa fel încît rateurile să se producă și în L1 și în L2, deși L1 va încerca să păstreze cît mai multe date.
Din moment ce știm deja asociativitatea lui L1 am scris un program care încarcă toate cele 4 linii unde se poate afla o adresă în L1, după care referă o altă linie care se bate cu prima pentru o linie în L2. Rezultatul arată cam așa:
/* masurarea asociativitatii cache-ului L2 */
void asociativitate_L2(void)
{
register int i;
register unitate a;
register unitate *b = (unitate*)de_transferat.array;
for (i=ASOC; i > 0; i--) {
ACCES16(b);
ACCES16(b+L1);
ACCES16(b+L1+L1);
ACCES16(b+L1+L1+L1);
b+=L2;
}
dummy = a;
}
void asociativitate_L2_ajustare(void)
{
register int i;
register unitate a;
register unitate *b = (unitate*)de_transferat.array;
for (i=ASOC; i > 0; i--) {
b += L2;
}
dummy = a;
}
int main() { /* etc. */ }
A trebuit să măresc MAXTRANSFER la 17Mb ca să nu ies din marginile array-ului (cînd ASOC = 8, 8 cuvinte la 512Kb distanța înseamnă 16Mb). Măsurătorile au arătat că pentru L2 gradul de asociativitate este 1, deci cu alte cuvinte L2 este direct-mapped.
Cache-urile asociative costă foarte mult; cu cît crește gradul de
asociativitate cu atît complexitatea hardware este mai mare, dar cu
atît performanțele pe o gamă largă de programe vor fi mai bune.
Proiectanții de cache-uri au găsit o soluție ingenioasă care
rezolvă cazuri patologice de acces la memorie cu un cost minim.
Ideea este de a adăuga unui cache asociativ pe 
căi un cache
extrem de mic (pînă în 10 cuvinte, poate chiar unul singur), dar
complet asociativ. Atunci cînd un cuvînt este evacuat din cache-ul
primar el va fi pus în acest ``depozit'' în speranța că va fi
folosit din nou în curînd. Acest minuscul cache se numește, din
motive, sper evidente, cache-victimă. Simulările arată că pentru
o gamă largă de programe cache-ul victimă este extrem de eficace
în a reduce rateurile care nu pot fi evitate de gradul de
asociativitate. Față de costul redus al hardware-ului beneficiile
sale sunt remarcabile.
Pentium II este un procesor foarte modern, deci este destul de plauzibil să fie echipat cu un cache-victimă pentru L1. Cum putem să determinăm dacă e adevărat și să măsurăm capacitatea sa?
Simplu: ne bazăm chiar pe observația precedentă, cum că acest cache este folosit pentru a ține informațiile care scapă din memoria asociativă. Atunci vom concepe un test care face din ce în ce mai multe cuvinte să se bată pentru cache-ul victimă, pînă cînd vom observa o degradare a performanței.
De data asta nu avem voie să atingem mai multe cuvinte consecutive; trebuie să citim exact 5, 6, 7, etc. cuvinte care se bat pe aceeași linie, iar atunci cînd observăm o degradare a performanței putem trage concluzia că am depășit capacitatea victimei.
Testul pentru cache-ul victima:
__________
|__________| ^
|__________| | grad de asociativitate
|__________| v
|__________| ^ bataie pentru victima
|__________| v
Primul test pe care l-am făcut, cu 5 cuvinte, a arătat deja o descreștere substanțială a ratei de transfer, deci am tras concluzia ca Pentium de fapt nu are cache victimă.
/* Masurarea cache-ului victima */
void victima(void)
{
register unitate a;
register unitate *b = (unitate*)de_transferat.array;
ACCES(b);
ACCES(b+L1);
ACCES(b+L1+L1);
ACCES(b+L1+L1+L1);
ACCES(b+L1+L1+L1+L1);
dummy = a;
}
void victima_ajustare(void)
{
register unitate a;
register unitate *b = (unitate*)de_transferat.array;
dummy = a;
}
int main(void)
{
/* etc. */
t = ftime(victima, 0.01, 0) - ftime(victima_ajustare, 0.01, 0);
printf("%2.2fcicli/cuvint\n", t / durata_ciclu / 5);
}
Din motive de economie și localitate octeții din cache nu sunt independenți, ci sunt grupați în blocuri sau linii. Astfel, dacă unul dintre octeții dintr-un bloc este referit de către procesor, toți ceilalți octeți din linie sunt și ei aduși în cache. Economia care se obține în acest fel este de etichete de adresa (tags): toți octeții dintr-o linie au aceeași etichetă.
(La scriere lucrurile pot varia: unele procesoare pot suporta modificarea și salvarea numai unora dintre octeții dintr-o linie).
Cum putem măsura mărimea liniei? În ceea ce privește L2 nu am reușit să concep un test suficient de discriminator, mai ales pentru că probabil linia din L2 este mai mică decît cea din L1, deci nu pot să evit interferențele! Cititorul care concepe un test este rugat să mi-l aducă la cunoștință.
Mărimea liniei din L1 poate fi determinată după cum arată următoarea figură:
Determinarea marimii liniei de cache L1:
_ ...
|_| ^
|_| | ASOC (grad de asociativitate
|_| | incluzind victima)
_............|_|.v.
|_|..............
<---LINIE------->
^
| Se bate octetul asta cu cei ``verticali'' pentru o linie?
Daca da, atunci marimea liniei este cel putin LINIE, altfel
marimea este mai mica.
Testul acesta trebuie făcut cu grijă, pentru că dacă o linie este mai mare decît bus-ul pe care se transportă datele nu toți octeții dintr-o linie vor veni deodată. De exemplu dacă linia din L1 are 16 octeți (128 de biți) și dacă transferul între L2 și L1 se face pe cîte 64 de biți, o linie trebuie adusă de fapt în doi pași.
Măsurătoarea pe care am pus-o la cale se desfășoară astfel: pun un cuvînt în cache, si după aia accesez alte 4 cuvinte. Dacă linia octetului cu pricina concurează cu liniile celorlalți 4 am o idee despre lungimea liniei.
Iată și programul:
int LINIE;
void linie(void)
{
register unitate *b = (unitate*)de_transferat.array;
register unitate a;
ACCES(b);
ACCES(b+LINIE);
ACCES(b+LINIE+L1);
ACCES(b+LINIE+L1+L1);
ACCES(b+LINIE+L1+L1+L1);
dummy = a;
}
void linie_ajustare(void)
{
register unitate a = 0;
dummy = a;
}
int main(void)
{
/* init etc. */
for (LINIE=20; LINIE >= 1; LINIE-=1) {
double t;
t = ftime(linie, 0.01, 0) - ftime(linie_ajustare, 0.01, 0);
printf("Linie %d, %2.2fciclii/cuvint\n",
LINIE, t / durata_ciclu / 5);
}
}
Iată rezultatele:
| Linie | cicli/cuvînt | Linie | cicli/cuvînt |
| 20 | 2.29 | 10 | 2.32 |
| 19 | 2.26 | 9 | 2.32 |
| 18 | 2.29 | 8 | 3.44 |
| 17 | 2.32 | 7 | 4.44 |
| 16 | 2.57 | 6 | 3.27 |
| 15 | 2.57 | 5 | 3.22 |
| 14 | 2.29 | 4 | 3.36 |
| 13 | 2.32 | 3 | 3.39 |
| 12 | 2.29 | 2 | 3.36 |
| 11 | 2.35 |
Valorile obținute sugerează dimensiunea liniei de 8* sizeof(unitate) = 32 de octeți = 128 de biți. Valorile sunt relativ mari pentru că execut numai 5 instrucțiuni de citire în întreaga buclă, deci nu amortizez suficient costul buclei (ca mai înainte prin ``unrolling'').
Închei acest articol cu o provocare pentru cititor. Măsurători făcute de mine indică faptul că cache-ul Pentium nu este blocant. Va invit să verificați această aserțiune.
Procesoarele moderne pot lansa în execuție mai multe instrucțiuni, care adesea operează asupra unor date diferite. În acest caz ar fi detrimental performanței ca în momentul în care o instrucțiune dă un rateu în cache toate celelalte să fie forțate să aștepte. Un cache ne-blocant permite execuția altor instrucțiuni în timp ce servește din memoria lentă rateul uneia. În felul acesta se poate întîmpla ca datele cerute de două instrucțiuni să sosească în ordine inversă cererilor!
Cache-urile ne-blocante sunt niște dispozitive hardware extrem de sofisticate. Dar atunci cînd ai 15 milioane de tranzistori la dispoziție (cît conține Pentium II) nu te dai în lături de la nimic pentru o creștere a performanței în execuție.
Calculatoarele sunt niște sisteme din ce în ce mai complicate; miniaturizarea și tehnologiile înalte au permis realizarea fizică a unor sisteme extrem de sofisticate. Balanța dintre părțile componente este în continuă schimbare: dacă în urmă cu 20 de ani viteza de acces a memoriilor și viteza de calcul a procesoarelor erau relativ egale, în ziua de azi procesoarele evoluează cu o rată de creștere a performanței de 55% pe an, fa't'a de memorii care cresc cu numai 7% 'in aceea'si perioad'a. Designerii sunt deci for'ta'ti să inventeze tot felul de noi dispozitive care să crească performanța întregului sistem (care tinde să fie la fel de lent ca cea mai lentă componentă).
Din cauza asta măsurarea performanței unui sistem este crucială pentru a înțelege ce îmbunătățiri trebuie aduse. Adesea măsurătorile se pot face numai indirect, și sunt influențate de o multitudine de parametri independenți. Proiectarea unor măsurători interesante și interpretarea rezultatelor devin adevărate meșteșuguri.
Una peste alta, arhitecții calculatoarelor nu vor rămîne prea curînd șomeri.
A-propos, ce meserie v-ați ales?
Pentru început vom calcula valoarea minimă și maximă a timpului real de execuție în funcție de valoarea timpului măsurat și de precizia ceasului.
Să facem următoarele notații:
: rezoluția ceasului sistemului de operare;
: timpul de pornire al măsurătorii, cum e raportat de
get_etime();
: timpul final al măsurătorii, raportat de
get_etime();
: timpul măsurat de execuție;
: timpul real de pornire (``timp absolut'': Newtonian);
: timpul real final;
: timpul real de execuție;
Știm că următoarele relații sunt adevărate:
Atunci:
Deci avem:
Acum vom demonstra următoarea relație între , și
eroarea maximă relativă dorită :
.
Fie 
un întreg pozitiv astfel încît 
; putem
presupune fără a pierde din generalitate că avem 
.
Din 1 avem
Împărțind prin avem:
Termenul din mijloc este chiar eroarea relativă pe care vrem s-o
mărginim. Acum exprimăm eroarea relativă ca funcție de raportul
:
Din ecuațiile 2 and 3 obținem:
sau
Pentru că vrem ca eroarea relativă să fie mărginită de
, trebuie să avem:
QED.
divide pe 
.
