Următorul conținut este
furnizat sub o
licență Creative Commons.
Sprijinul dumneavoastră va ajuta
MIT OpenCourseWare să
continue să ofere
gratuit resurse educaționale de înaltă calitate.
Pentru a face o donație sau pentru a
vizualiza materiale suplimentare
din sute de cursuri MIT,
vizitați MIT OpenCourseWare
la ocw.mit.edu.
CHARLES LEISERSON:
Deci bine ai venit la 6.172.
Numele meu este Charles
Leiserson și sunt unul
dintre cei doi lectori din acest trimestru.
Celălalt este
profesorul Julian Shun.
Suntem amândoi în EECS și în CSAIL
la etajul 7 al
clădirii Gates.
Dacă nu știți, sunteți
în ingineria performanței
sistemelor software, așa că
dacă v-ați găsit
în locul greșit,
acum este momentul să părăsiți.
Vreau să încep azi prin
a vorbi puțin despre motivul pentru care
facem
ingineria performanței, apoi voi
face puțină
administrare,
apoi mă voi scufunda într-un
fel de studiu de caz care
vă va oferi o idee bună
despre unele dintre ele.  lucrurile pe care le vom

face pe parcursul mandatului.
Am pus administrația
la mijloc,
pentru că e ca, dacă din mine că
îți spun despre curs
nu vrei să
faci curs, atunci
e ca, de ce să asculți
administrația, nu?
E ca...
Deci hai să ne scufundăm imediat, bine?  Așa
că primul lucru pe care trebuie să-l
înțelegi întotdeauna
ori de câte ori
faci ceva este
o perspectivă asupra a ceea ce
contează în ceea ce faci.
Deci, pe tot parcursul termenului, vom
face ingineria performanței software-ului
.
Și, deci, acest lucru este destul de
interesant,
pentru că se dovedește că
performanța nu este, de obicei,
în partea de sus a ceea ce îi
interesează oamenii atunci când
construiesc software.
BINE?
Care sunt unele dintre
lucrurile care sunt mai
importante decât performanța?
Da?
PUBLIC: Termenele limită.
CHARLES LEISERSON: Termenele limită.
Bun.
PUBLIC: Cost.
CHARLES LEISERSON: Cost.
PUBLIC: Corectitudine.
CHARLES LEISERSON: Corectitudine.
PUBLIC: Extensibilitate.
CHARLES LEISERSON:
Extensibilitate.
Da, poate am
putea continua și mai departe.
Și cred că
probabil că ați putea
face o listă destul de lungă.
Am făcut o listă scurtă
cu tot felul
de lucruri care sunt mai
importante decât performanța.
Deci, dacă programatorii
sunt atât de dispuși să sacrifice
performanța pentru
aceste proprietăți,
de ce studiem performanța?
BINE?
Deci, acesta este un fel de
paradox și un pic de puzzle.
De ce studiezi
ceva care în mod clar
nu se află în fruntea
listei de ceea ce le
pasă celor mai mulți oameni atunci când
dezvoltă software?
Cred că răspunsul la
asta este că performanța
este moneda de calcul.
BINE?
Folosiți performanța pentru a cumpăra
aceste alte proprietăți.
Așa că veți spune
ceva de genul, la naiba,
vreau să fie
ușor de programat
și, prin urmare, sunt dispus
să sacrific niște performanțe
pentru a face ceva
ușor de programat.
Sunt dispus să sacrific
unele performanțe pentru a mă asigura
că sistemul meu este sigur.
BINE?
Și toate aceste lucruri provin
din bugetul tău de performanță.
Și în mod clar, dacă performanța se
degradează prea mult,
lucrurile tale devin inutilizabile.
BINE?
Când vorbesc cu oamenii,
cu programatorii și spun... știi
, oamenilor le place să
spună, ah, performanță.
Oh, faci performanță?
Performanța nu contează.
Nu mă gândesc niciodată la asta.
Apoi vorbesc cu oameni
care folosesc computere
și mă întreb, care este principala ta
plângere cu privire la
sistemele de calcul pe care le folosești?
Răspuns?
Prea încet.
[Chicotește] OK?
Deci este interesant,
indiferent dacă ești producător
sau orice altceva.
Dar răspunsul real este că
performanța este ca moneda.
Este ceva ce cheltuiește.
Dacă te uiți...
știi, aș prefera
100 de dolari sau un galon de apă?  Ei
bine, apa este
indispensabilă vieții.
Sunt circumstanțe, cu
siguranță,
în care aș prefera
să am apă.
BINE?
Mai mult de 100 USD.
BINE?
Dar în societatea noastră modernă
, pot cumpăra
apă cu mult mai puțin de 100 de dolari.
BINE?
Așa că, deși apa
este esențială pentru viață
și mult mai importantă decât
banii, banii sunt o monedă,
așa că prefer să am
bani pentru că pot
cumpăra doar lucrurile de care am nevoie.
Și acesta este același tip
de analogie a performanței.
Nu are valoare intrinsecă,
dar contribuie la lucruri.  Îl
poți folosi pentru a cumpăra
lucruri la care îți pasă,
cum ar fi utilitatea sau
testabilitatea sau ceea ce ai tu.
BINE?
Acum, în primele
zile ale computerului, ingineria
performanței software-ului
era obișnuită,
deoarece
resursele mașinii erau limitate.
Dacă te uiți la aceste
mașini din 1964 până în 1977...
Adică, uită-te la câți octeți
au pe ele, nu?
În '64, există un computer
cu 524 de kilobytes.
BINE?
Era o
mașină mare pe atunci.
Adică kiloocteți.
Nu sunt megaocteți,
nu sunt gigaocteți.
Adică kiloocteți.
BINE?
Și multe programe ar solicita
resursele mașinii, bine?
Rata de ceas pentru acea
mașină a fost de 33 de kiloherți.
Care este
rata obișnuită a ceasului astăzi?
PUBLIC: 4 gigahertzi.
CHARLES LEISERSON: Despre ce?
PUBLIC: 4 gigahertzi.
CHARLES LEISERSON: 4 gigaherți,
3 gigaherți, 2 gigaherți,
undeva sus.
Da, undeva
în intervalul ăsta, bine?
Și aici
operau cu kiloherți.  Atât de
multe programe nu s-ar potrivi
fără o inginerie intensă de performanță
.
Și unul dintre lucruri, de asemenea,
sunt o mulțime de vorbe
care au apărut din acea epocă.
Donald Knuth, care este un
câștigător al premiului Turing, un
informatician absolut fabulos
din toate punctele de vedere,
a scris: „Optimizarea prematură
este rădăcina tuturor relelor”.
Și vă invit,
apropo, să căutați
citatul ăla pentru că de
fapt este scos din context.
BINE?
Așa că încercarea de a optimiza lucrurile
prea devreme era îngrijorat.
BINE?
Bill Wulf, care a proiectat
limbajul BLISS
și a lucrat la
PDP-11 și altele,
a spus: „Sunt comise mai multe păcate de calcul

în numele eficienței
fără a o atinge neapărat
decât din orice alt
motiv, inclusiv
prostia oarbă”.
BINE?
Și Michael Jackson
a spus: „Prima regulă
de optimizare a programului--
nu o faceți. A
doua regulă de
optimizare a programului,
numai pentru experți--
nu o faceți încă”.
[Chicotește]
OK?
Așa că toată lumea
avertizează, pentru că atunci când
începi să
faci lucrurile mai repede,
codul tău devine ilizibil.
BINE?
Crearea unui cod care să fie
lizibil și rapid -- acum
aici
este arta și sperăm că vom
învăța puțin
despre acest lucru.
BINE?
Și într-adevăr, nu
avea niciun rost să
lucrezi prea
mult la
ingineria performanței timp de mulți ani.
Dacă te uiți la
scalarea tehnologiei
și te uiți la
câți tranzistori
sunt pe diferite
modele de procesoare, până în aproximativ 2004,
aveam legea lui Moore
în plină accelerație, OK?
Cu densitatea așchiilor
dublându-se la fiecare doi ani.
Și într-adevăr destul de uimitor.
Și împreună cu asta, pe măsură ce au
micșorat dimensiunile
cipurilor --
pentru că prin miniaturizare --
viteza ceasului ar crește în mod
corespunzător, de asemenea.
Așa că, dacă ați descoperit că
ceva a fost prea lent,
așteptați câțiva ani.
BINE?
Așteptați câțiva ani.
Va fi mai rapid.
BINE?
Și așa, știți,
dacă urma să
faceți ceva cu software-ul
și să vă faceți software-ul urât,
nu a existat o
răsplată foarte bună în comparație
cu doar așteptarea.
Și în acea epocă, a
existat ceva
numit scalare Dennard,
care, pe măsură ce lucrurile s-au micșorat,
a permis vitezei ceasului
să crească, practic
prin reducerea puterii.  Ai
putea reduce puterea și
totuși menține totul rapid
și vom vorbi despre
asta într-un minut.
Deci, dacă te uiți la ce s-a
întâmplat între 1977 și 2004,
iată computere Apple
cu etichete de preț similare
și poți vedea că
rata ceasului a crescut vertiginos.
1 megaherți, 400 megaherți,
1,8 gigaherți, bine?
Și căile de date au trecut
de la 8 biți la 30 la 64.
Memoria,
în mod corespunzător, crește.
Cost?
Aproximativ la fel.
Și aceasta este moștenirea
legii lui Moore
și a progreselor extraordinare
în tehnologia semiconductoarelor.
Și astfel, până în 2004,
legea lui Moore și scalarea
frecvenței de ceas,
așa-numita scalare Dennard,
a fost în esență o
tiparnă pentru moneda
performanței.
BINE?
Nu trebuia să faci nimic.
Tocmai ai făcut ca
hardware-ul să meargă mai repede.
Foarte usor.
Și toate acestea s-au încheiat - ei
bine, o parte din ele s-au
încheiat -
în 2004, când
viteza ceasului a crescut.
BINE?
Deci, dacă te uiți la
asta, în jurul anului 2005,
poți vedea toate vitezele --
am atins, știi,
2 până la 4 gigaherți
și nu am reușit
să facem ca cipurile să meargă mai repede
decât atât în ​​vreun
mod practic de atunci.
Dar densitățile
au continuat să meargă foarte bine.
Acum, motivul pentru care
viteza ceasului s-a aplatizat
a fost din cauza densității puterii.
Și acesta este un slide de la
Intel din acea epocă,
privind creșterea
densității puterii.
Și ceea ce proiectau ei
era
că temperaturile de joncțiune
ale tranzistoarelor de pe cip,
dacă continuă să crească așa cum
au fost scalate,
ar începe să se
apropie, în primul rând, de
temperatura unui
reactor nuclear, apoi de
temperatura
unui  duza rachetei
și apoi suprafața soarelui.
BINE?
Ca să nu
construim puțină tehnologie
care să răcească atât de bine.
Și chiar dacă ai putea
rezolva un pic,
scrisul era pe perete.  Nu mai
putem scala
frecvențele de ceas.
Motivul pentru aceasta este că,
inițial, frecvența ceasului
a fost scalată presupunând
că cea mai mare parte a puterii
era putere dinamică,
care mergea
atunci când comutai circuitul.
Și ceea ce s-a întâmplat pe măsură ce am continuat
să reducem asta și să reducem
, adică ceva ce
era înainte în zgomot, și anume

curenții de scurgere, OK, au început
să devină semnificativi până
la punctul în care --
acum, astăzi --
puterea dinamică este
mult mai mică.  este o îngrijorare
decât puterea statică
de la doar circuitul care
stă acolo care se scurge,
iar când miniaturizi,
nu poți opri acest efect
să se întâmple.
Deci, ce au
făcut vânzătorii în 2004 și 2005
și din moment ce au
spus, o, Doamne,
avem toți acești
tranzistori de folosit,
dar nu putem folosi tranzistorii
pentru a face lucrurile să meargă mai repede.
Deci, ceea ce au făcut este că au
introdus paralelismul
sub formă de
procesoare multicore.
Au pus mai mult de un
nucleu de procesare într-un cip.
Și pentru a crește performanța,
ar avea, știți,
mai multe nuclee, iar fiecare
generație a legii lui Moore
acum dubla
numărul de nuclee.
Și, așadar, dacă te uiți la ce s-a
întâmplat cu nucleele de procesor,
vezi că în jurul anilor
2004, 2005, am început
să obținem mai multe
nuclee de procesare per cip, în măsura în
care astăzi, este
practic imposibil
să găsești un cip cu un singur nucleu
pentru un laptop sau  o stație de lucru
sau orice altceva.
Totul este multicore.
Nu poți cumpăra doar unul.
Trebuie să cumpărați un
procesor paralel.
Și astfel impactul a
fost că performanța
nu mai era gratuită.
Nu puteai doar să
accelerezi hardware-ul.
Acum, dacă voiai să
folosești acel potențial,
trebuia să faci
programare paralelă
și asta nu este ceva pe
care nimeni din industrie
a făcut-o cu adevărat.
Așadar, astăzi, sunt
multe alte lucruri
care s-au întâmplat în acel
interval de timp.
Avem unități vectoriale ca
părți comune ale mașinilor noastre;
avem GPU-uri;  avem
ierarhii de cache mai abrupte;
avem logica configurabila pe
unele masini;  si asa mai departe.
Și acum depinde de
software să se adapteze la el.
Și așa, deși
nu vrem să avem de-a
face cu
performanța, astăzi
trebuie să te ocupi de performanță.
Și în timpul vieții tale,
va trebui să te
confrunți cu
performanța în software
dacă vei avea un
software eficient.
BINE?
Puteți vedea ce
s-a întâmplat, de asemenea,
acesta este un studiu
pe care l-am făcut
privind erorile software dintr-o varietate
de proiecte open-source
în care se menționează
cuvântul „performanță”.
Și puteți vedea că în 2004,
cifrele încep să crească.
Știi, unii dintre
ei... nu este la
fel de convingător pentru
unele lucruri ca pentru altele,
dar, în general, există
o tendință ca, după 2004,
oamenii au început să se preocupe
mai mult de performanță.
Dacă te uiți la
locurile de muncă de dezvoltator de software,
de la începutul anilor 2000 --
„oh oh,” din 2000,
cred, OK –
vezi încă o dată că mențiunea
„performanței” în locuri de muncă
este în creștere.
Și din punct de vedere anecdotic,
pot să vă spun, am
avut un student care a venit
la mine după primăvară,
după ce luase
6.172, și mi-a spus,
știți, am fost și am
aplicat pentru cinci locuri de muncă.
Și fiecare job mi-a cerut,
la fiecare interviu de angajare, mi-au
pus o
întrebare la care nu aș fi putut
răspunde dacă nu aș fi luat
6.172 și am primit cinci oferte.
BINE?
Și când am comparat
aceste oferte,
ele tindeau să fie cu 20% până la
30% mai mari decât oamenii
care sunt doar maimuțe web.
BINE?
Oricum.
[Râsete]
Asta nu înseamnă că ar
trebui neapărat să
iei acest curs, OK?
Dar vreau doar să subliniez
că ceea ce vom învăța
va fi interesant
din punct de vedere practic,
adică viitorul tău.
BINE?
La fel și
puncte de vedere teoretice
și puncte de vedere tehnice.
BINE?
Deci, procesoarele moderne
sunt cu adevărat complicate,
iar marea întrebare
este cum
scriem software pentru a folosi acel
hardware modern în mod eficient?
BINE?
Vreau să vă dau un exemplu
de inginerie a performanței
unei probleme foarte bine studiate și
anume înmulțirea matriceală.
Cine nu a văzut niciodată această problemă?
[RÂDE] Da.
Bine, așa că avem niște glumeți
în clasă, văd.
BINE.
Deci, știi, este nevoie de
n operații cubite,
pentru că practic
calculezi n
produse punctice pătrate.
BINE?
Deci, în esență, dacă adunați
numărul total de operații,
este aproximativ 2n cub, deoarece
există în esență
o înmulțire și o adunare
pentru fiecare pereche de termeni
care trebuie acumulați.
BINE?
Deci este practic 2n cub.  Ne
vom
uita la asta presupunând
pentru simplitate că n-ul nostru
este o putere exactă de 2, OK?
Acum, mașina la care ne vom
uita
va fi una dintre
cele la care veți
avea acces în AWS.
BINE?
Este o mașină optimizată pentru calcul
,
care are o
microarhitectură Haswell care rulează
la 2,9 gigaherți.
Există 2 cipuri de procesor
pentru fiecare dintre aceste mașini
și 9 nuclee de procesare per
cip, deci un total de 18 nuclee.
Deci, aceasta este cantitatea
de procesare paralelă.
Face hyperthreading în două sensuri, cu
care de fapt
nu ne vom ocupa prea mult.
Hyperthreading vă oferă
puțin mai multă performanță,
dar face și cu adevărat
dificil să măsurați lucrurile,
așa că, în general, vom
dezactiva hyperthreading.
Dar performanța pe care o
obțineți tinde
să fie corelată cu ceea ce
obțineți atunci când faceți hyperthread.
Pentru
unitatea cu virgulă mobilă de acolo,
este capabil să facă 8 operații de
precizie dublă
.
Acestea sunt operațiuni în virgulă mobilă pe 64 de biți
,
inclusiv o adăugare de multiplicare fuzionată
per nucleu, per ciclu.
BINE?
Deci aceasta este o unitate vectorială.
Deci, practic, fiecare
dintre aceste 18 nuclee
poate face 8 operații cu precizie dublă
,
inclusiv un fuzionat-multiplicare-adăugare,
care este de fapt 2 operațiuni.
BINE?
Modul în care
numără aceste lucruri, bine?
Are o dimensiune a liniei cache
de 64 de octeți.
Icache-ul este de 32 kilobytes,
care este asociativ cu 8 căi.
Vom vorbi despre
unele dintre aceste lucruri.
Dacă nu știi toți
termenii, este în regulă.
Vom acoperi majoritatea
acestor termeni mai târziu.  Are
un dcache
de aceeași dimensiune.  Are
un cache L2
de 256 kiloocteți
și un
cache L3 sau ceea ce se
numește uneori un
LLC, Last-Level Cache,
de 25 de megaocteți.
Și apoi are 60 de
gigabytes de DRAM.
Deci aceasta este o
mașinărie mare care claxonează.
BINE?
Este ca... poți să aduci
lucruri pe care să le cânți pe asta, bine?
Dacă te uiți la
performanța de vârf,
este viteza de ceas ori
2 cipuri de procesor
ori 9
nuclee de procesare per cip, fiecare capabil
de, dacă poți folosi atât
înmulțirea cât și adăugarea,
16 operațiuni în virgulă mobilă
, și asta înseamnă
doar  scurt de teraflop, bine?
836 gigaflopi.
Deci e multă putere, bine?
Asta e multă putere.
Acestea sunt
mașini distractive, de fapt, bine?
Mai ales când intrăm în
lucruri precum AI-ul de joc
și lucruri pe care le facem
pentru al patrulea proiect.
Vei vedea.
Sunt foarte distractive.
Poți avea o mulțime
de calcule, ok?
Acum iată codul de bază.
Acesta este codul complet
pentru Python pentru
multiplicarea matricei.
Acum, în general, în Python,
nu ați folosi acest cod
pentru că doar apelați o
subrutină de bibliotecă care
face multiplicarea matricei.
Dar uneori
ai o problemă.  O să
ilustrez
cu înmulțirea matriceală,
dar uneori aveți
o problemă pentru care
trebuie să scrieți codul.
Și vreau să vă dau o idee
despre ce fel de performanță
obțineți din Python, bine?
În plus, cineva trebuie să
scrie -- dacă există o
rutină de bibliotecă, cineva
trebuia să o scrie,
iar persoana respectivă era
inginer de performanță,
pentru că a scris-o să
fie cât mai rapid posibil.
Și astfel, acest lucru vă va oferi
o idee despre ce puteți
face pentru ca codul să ruleze rapid, OK?
Deci, când rulați acest cod,
astfel încât să puteți vedea că
ora de începere,
știți, înainte de
bucla triplu imbricată,
chiar aici, înainte de
bucla triplu imbricată,
luăm o
măsurătoare de timp și apoi
luăm o altă
măsurarea timpului la sfârșit,
apoi imprimăm
diferența.
Și atunci asta este doar această
buclă clasică triplu imbricată
pentru multiplicarea matricei.
Și deci, când rulezi asta,
cât timp durează,
crezi?
Orice presupuneri?
Să vedem.
Ce zici... hai să facem asta.
Funcționează timp de 6 microsecunde.
Cine crede că 6 microsecunde?
Ce zici de 6 milisecunde?
Ce zici de... 6 milisecunde.
Ce zici de 6 secunde?
Ce zici de 6 minute?
BINE.
Ce zici de 6 ore?
[Râsete]
Ce zici de 6 zile?
[Râsete]
OK.
Desigur, este important
să știți ce dimensiune are.
Este 4.096 pe 4.096, așa cum se
arată în cod, OK?
Și cei dintre voi
care nu ați votat...
treziți-vă.
Să fim activi.
Aceasta este o învățare activă.
Pune-te acolo, bine?
Nu contează dacă
ai dreptate sau greșit.  Vor
fi o grămadă de oameni
care au primit răspunsul corect,
dar nu au idee de ce.
[Râsete]
OK?
Deci, se pare că durează
aproximativ 21.000 de secunde,
adică aproximativ 6 ore.
BINE?
Uimitor.
Este rapid?
PUBLIC: (SARCASTIC) Da.
[Râsete]
CHARLES LEISERSON: Da, corect.
Duh, nu?
Este rapid?
Nu.
Știi, cum ne dăm seama
dacă este rapid sau nu?
BINE?
Știi, la ce ar trebui să ne
așteptăm de la mașina noastră?
Așa că haideți să facem un

calcul din spate a... [
Râsete]
--a câte
operațiuni există
și cât de repede ar trebui să putem
face asta.  Am
trecut
și am spus care
sunt toți parametrii
mașinii.
Deci, există 2n operații cub
care trebuie efectuate.
Nu facem algoritmul lui Strassen
sau ceva de genul
ăsta.
Facem doar o
buclă direct triply imbricată.
Deci sunt 2 la 37 de
operații în virgulă mobilă, OK?
Timpul de rulare
este de 21.000 de secunde,
așa că înseamnă că obținem
aproximativ 6,25 megaflopi
din mașina noastră când
rulăm acel cod, OK?
Doar împărțind-o,
câte operații în virgulă mobilă
pe secundă obținem?
Luăm numărul de operații
împărțit la timp, bine?
Vârful, după cum vă amintiți,
a fost de aproximativ 836 gigaflopi, bine?
Și primim
6,25 megaflopi, bine?
Deci obținem aproximativ
0,00075% din vârf, bine?
Acest lucru nu este rapid.
BINE?
Acest lucru nu este rapid.
Deci haideți să facem ceva
foarte simplu.
Să-l codificăm în Java și
nu în Python, bine?
Deci luăm doar acea buclă.
Codul este aproape același, bine?
Doar bucla triplu imbricată.  Îl
rulăm în Java, bine?
Și timpul de rulare
acum, se pare,
este de aproximativ
3.000 de secunde,
adică aproximativ 46 de minute.
Același cod.
Python, Java, bine?
Avem o accelerare de aproape 9 ori,
pur și simplu
o codificăm într-o
altă limbă, OK?  Ei
bine, să încercăm C.
Acesta este limbajul pe care îl vom
folosi aici.
Ce se întâmplă când
îl codificați în C?
Este exact același lucru, bine?
Vom folosi
compilatorul Clang/LLVM 5.0.
Cred că folosim 6.0
acest termen, nu-i așa?
Da.
OK, ar fi trebuit să reluez aceste
numere pentru 6.0, dar nu am făcut-o.
Deci acum, sunt practic
1.100 de secunde,
ceea ce înseamnă aproximativ 19 minute,
așa că am ajuns, atunci, aproximativ--
este de două ori mai rapid decât Java
și de aproximativ 18 ori mai rapid
decât Python, OK?
Deci, iată unde ne aflăm până acum.
BINE?
Avem timpul de rulare al
acestor diverse lucruri, bine?
Iar accelerarea relativă
este cât de mult mai rapidă
decât rândul anterior,
iar accelerația absolută este
modul în care este comparată
cu primul rând,
iar acum reușim să
obținem, acum, 0,014% din vârf.
Deci suntem încă lenți,
dar înainte să mergem și să încercăm să-l
optimizăm în continuare,
cum ar fi, de ce este Python
atât de lent și C atât de rapid?
Stie cineva?
PUBLIC: Python este
interpretat, deci trebuie să--
deci există un
program C care practic
analizează instrucțiunile Python pycode
, ceea ce
ocupă cea mai mare parte a timpului.
CHARLES LEISERSON: OK.
E cam pe drumul cel bun
.  Mai
are cineva vreo... să
explice puțin
de ce Python este atât de lent?
Da?
PUBLIC: Când scrieți,
cum ar fi, înmulțiți și adăugați,
acestea nu sunt singurele
instrucțiuni pe care le face Python.
Face mult
cod pentru, cum ar fi,
trecerea prin obiecte Python
și numere întregi și bla-bla-bla.
CHARLES LEISERSON: Da, da.
OK bine.
Deci, principalul motiv pentru care Python
este lent și C este atât de rapid
este că Python este interpretat
și C este compilat direct
în codul mașinii.
Și Java este undeva
la mijloc,
deoarece Java este compilat
în bytecode, care este apoi
interpretat și apoi
compilat just-in-time
în coduri de mașină.
Așa că permiteți-mi să vorbesc
puțin despre aceste lucruri.
Deci, interpreții, cum ar fi în
Python, sunt versatili, dar lenți.
Este unul dintre aceste
lucruri în care au spus că vom
lua
o parte din performanța noastră
și o vom folosi pentru a crea
un mediu mai flexibil,
mai ușor de programat.
BINE?
În principiu, interpretul
citește, interpretează
și execută fiecare
instrucțiune de program și apoi
actualizează starea mașinii.
Deci nu este doar -- de fapt
trece prin și, de fiecare dată,
citește codul tău,
își dă seama ce face
și apoi îl implementează.
Așa că există toate
aceste cheltuieli generale în comparație
cu doar efectuarea operațiunilor sale.
Deci, interpreții pot
suporta cu ușurință funcții de programare la nivel înalt
și pot face lucruri
precum modificarea dinamică a codului
și așa mai departe cu
prețul performanței.
Așa că, știți, de obicei,
ciclul pentru un interpret
este, citiți următoarea afirmație,
interpretați declarația.
Apoi executați
instrucțiunea, apoi
actualizați starea
mașinii
și apoi preluați
următoarea instrucțiune.
BINE?
Și treci
prin asta de fiecare dată,
iar asta se face în software.
BINE?
Când aveți lucruri
compilate în codul mașinii,
trece printr-un
lucru similar, dar este
foarte optimizat doar pentru
lucrurile pe care le fac mașinile.
BINE?
Și astfel, atunci când compilați,
puteți profita
de hardware-ul și de interpretul
instrucțiunilor mașinii,
iar aceasta este mult, mult mai mică
decât
costul general de software mare pe care îl obțineți cu Python.
Acum, JIT este undeva la
mijloc, ceea ce este folosit în Java.
Compilatoarele JIT pot recupera
o parte din performanță
și, de fapt, au făcut o
treabă destul de bună în acest caz.
Ideea este că atunci când
codul este executat pentru prima dată,
este interpretat, iar
apoi sistemul de rulare
ține evidența cât de des sunt executate
diferitele bucăți de cod
.
Și ori de câte ori constată că
există o bucată de cod pe
care o execută
frecvent,
apelează compilatorul pentru a
compila acea bucată de cod
și apoi, ulterior,
rulează codul compilat.
Așa că încearcă să obțină marele
avantaj al performanței
prin compilarea doar a
lucrurilor care sunt necesare --
știi, pentru
care de fapt va
plăti să
invoci compilatorul să le facă.
BINE?
Deci, oricum, asta este
marea diferență
cu astfel de lucruri.
Unul dintre motivele pentru care nu
folosim Python în această clasă
este că
modelul de performanță este greu de înțeles.
BINE?
C este mult mai aproape de metal,
mult mai aproape de siliciu, bine?
Și deci este mult mai ușor
să ne dăm seama ce se
întâmplă în acel context.
BINE?
Dar vom avea o
prelegere invitată despre care vom
vorbi despre
performanță în
limbaje gestionate precum
Python, așa că nu
vom
ignora subiectul.
Dar vom învăța cum să
facem ingineria performanței
într-un loc în care
este mai ușor să o facem.
BINE?
Acum, unul dintre lucrurile pe care le
va face un compilator bun este--
știi, odată ce ajungi la-- să
presupunem că avem
versiunea C, care
este locul în care vom
trece de la acest punct,
deoarece acesta este
cel mai rapid pe care îl avem.  până
acum, se pare
că puteți schimba
ordinea buclelor
din acest program
fără a afecta
corectitudinea.
BINE?
Așa că iată-ne-- știi
, pentru i, pentru j,
pentru k, fă actualizarea.
BINE?
Altfel am putea face -- am
putea face, pentru i, pentru k, pentru j,
facem actualizarea și calculează
exact același lucru.
Sau am putea face, pentru k, pentru
j, pentru i, să facem actualizările.
BINE?
Deci putem schimba
ordinea fără a afecta
corectitudinea, OK?
Și deci crezi că ordinea
buclelor contează pentru performanță?
Duh.
Știi, aceasta este ca
această întrebare principală.
Da?
Întrebare?
PUBLIC: Poate pentru
localitățile cache.
CHARLES LEISERSON: Da.
BINE.
Și ai exact dreptate.
Localitatea cache este ceea ce este.
Deci, când facem asta, obținem...
ordinea buclei afectează
timpul de rulare cu un factor de 18.
Uau.
Doar prin schimbarea comenzii.
BINE?
Ce se intampla acolo?
BINE?
Ce se întâmplă?
Așa că o să vorbim despre
asta mai în profunzime, așa că voi
trece prin
asta, pentru că asta doar
vă arată tipurile
de considerații pe care le faceți.
Deci, în hardware, fiecare
procesor citește și scrie
memoria principală în
blocuri învecinate numite linii cache.
BINE?

Liniile de cache accesate anterior sunt
stocate într-o
memorie mică numită cache,
care se află lângă procesor.
Când procesorul
accesează ceva,
dacă este în
cache, primești un hit.
Este foarte ieftin, ok și rapid.
Dacă ratați, trebuie să mergeți
fie într-un cache de nivel mai profund,
fie
în memoria principală.
Este mult, mult
mai lent și vom
vorbi despre așa ceva.
Deci, ceea ce se întâmplă pentru
această problemă matrice este că
matricele sunt așezate în
memorie în ordinea principală a rândurilor.
Asta înseamnă că iei...
știi, ai o
matrice bidimensională.
Este așezat în
ordinea liniară
a adreselor de memorie,
luând, în esență, rândul 1,
apoi, după rândul 1, lipiți rândul
2 și după aceea, lipiți rândul 3
și așa mai departe și desfășurându-l.
Există o altă comandă prin care
lucrurile ar fi putut fi
stabilite -- de fapt,
sunt în Fortran --
care se numește
coloana-comandă majoră.
BINE?
Deci, se dovedește că C și Fortran
funcționează în ordine diferite.
BINE?
Și se dovedește că
afectează performanța, în
ce fel o face.
Deci, să aruncăm o privire la
modelul de acces pentru ordinea
i, j, k.
BINE?
Deci, ceea ce facem este că, odată ce ne
dăm seama ce este i și ce
este j, vom
trece prin k.
Și pe măsură ce parcurgem
k, OK, C i, j
rămâne același pentru tot.
Primim acea
localitate spațială excelentă
pentru că doar
accesăm aceeași locație.  De
fiecare dată, va
fi în cache.
Mereu va fi acolo.  Va
fi
rapid să accesați C.
Pentru A, ceea ce se întâmplă este că
trecem într-o ordine liniară
și obținem o
localitate spațială bună.
Dar pentru B, trece
prin coloane,
iar acele puncte sunt
distribuite departe în memorie,
așa că procesorul va
aduce 64 de octeți
pentru a opera pe un
anumit datum.
BINE?
Și apoi ignoră 7 din cele
8 cuvinte în virgulă mobilă
de pe acea linie cache și
trece la următoarea.
Deci se irosește
foarte mult, bine?
Deci, acesta are o
localitate spațială bună,
deoarece este totul adiacent
și ați folosi
liniile cache în mod eficient.
Acesta, vă
despărțiți de 4.096 de elemente.
Are o
localitate spațială slabă, bine?
Și asta pentru acesta.
Deci, dacă ne uităm la celelalte
diferite --
acesta, ordinea i, k, j -- se
dovedește că obțineți o
localitate spațială bună atât pentru C,
cât și pentru B și excelentă pentru A. OK?
Și dacă te uiți
chiar și la altul,
nu ajungi la fel de
bun ca celelalte,
așa că există o
gamă întreagă de lucruri.
BINE?
Acesta, te descurci
optim prost în ambele, bine?
Și astfel încât să le puteți
măsura pe diferite
și se dovedește că puteți
folosi un instrument pentru a înțelege acest lucru.
Și instrumentul pe care îl vom
folosi se numește Cachegrind.
Și este una dintre
suitele de cache Valgrind.
Și ceea ce va face
este că vă va spune
care sunt ratele de ratare pentru
diferitele bucăți de cod.
BINE?
Și vei învăța cum să folosești
acel instrument și vei da seama,
oh, uită-te la asta.
Avem o rată de ratare mare
pentru unii și nu pentru alții,
așa că poate de aceea
codul meu rulează lent.
BINE?
Așa că, când îl alegeți pe
cel mai bun dintre aceștia,
OK, am primit o
viteză relativă de aproximativ 6 și 1/2.
Deci, ce alte
schimbări simple putem încerca?
Există de fapt o
colecție de lucruri
pe care le-am putea face și care nici
măcar nu ne fac să atingem codul.
Ce altceva am putea
face, pentru cei care s-au
jucat cu compilatoare și altele?
Sugestie, indiciu.
Da?
PUBLIC: Puteți
schimba steagurile compilatorului.
CHARLES LEISERSON: Da,
schimbați steagurile compilatorului, bine?
Deci Clang, care este
compilatorul pe care îl vom folosi,
oferă o colecție de
comutatoare de optimizare
și puteți specifica o
comutare la compilator
pentru a-i cere optimizarea.
Deci faci minus O
și apoi un număr.
Și 0, dacă te uiți la
documentație, scrie
„Nu optimiza”.
1 spune „Optimizează”.
2 spune: „Optimizați și mai mult”.
3 spune: „Optimizați și mai mult”.
BINE?
În acest caz, se dovedește că,
deși a optimizat mai mult
în O3, se pare că O2
a fost o setare mai bună.
BINE?
Acesta este unul dintre aceste cazuri.
Nu se întâmplă tot timpul.
De obicei, O3 se descurcă mai bine
decât O2, dar în acest caz O2 este
de fapt optimizat
mai bine decât O3,
deoarece optimizările
sunt într-o oarecare măsură euristice.
BINE?
Și există și alte
tipuri de optimizare.  Îl
puteți pune să facă
optimizare ghidată de profil,
în care vă uitați la ce
performanță a fost și trimiteți-o
înapoi în cod,
iar apoi compilatorul
poate fi mai inteligent în ceea ce privește
modul în care se optimizează.
Și există o varietate
de alte lucruri.
Deci, cu această tehnologie simplă,
alegând un semnal de optimizare bun --
în acest caz, O2 --
am primit gratuit, practic,
un factor de 3,25, OK?
Fără a fi nevoie să
lucrezi deloc, bine?
Și acum începem de fapt să ne
apropiem de
1% din performanța maximă.
Avem un punct de 0,3% din
performanța maximă, bine?
Deci, ce cauzează
performanța scăzută?
De ce nu obținem cea mai
mare parte a performanței
din această mașină?
De ce crezi?
Da?
PUBLIC: Nu
folosim toate nucleele.
CHARLES LEISERSON: Da,
nu folosim toate nucleele.
Până acum folosim
un singur nucleu
și câte nuclee avem?
PUBLIC: 18.
CHARLES LEISERSON: 18, nu?
18 nuclee.
Ah!
18 nuclee stau
acolo, 17 stau
inactiv, în timp ce
încercăm să optimizăm unul.
BINE.
Deci multicore.
Deci avem 9 nuclee pe cip
și există 2 dintre aceste cipuri
în mașina noastră de testare.
Deci rulăm doar pe unul
dintre ele, așa că să le folosim pe toate.
Pentru a face asta, vom
folosi infrastructura Cilk
și, în special,
putem folosi ceea ce
se numește o buclă paralelă, pe care
în Cilk, l-ai numi cilk_for,
și așa vei transmite doar acea
buclă exterioară -- de exemplu,
în acest caz, spuneți
cilk_for, spune,
faceți toate acele
iterații în paralel.
Compilatorul și sistemul de rulare
sunt libere să le programeze
și așa mai departe.
BINE?
Și am putea face asta și
pentru bucla interioară, ok?
Și se dovedește că nu o poți
face și pentru bucla din mijloc,
dacă te gândești bine.
BINE?
Așa că vă las să faceți, asta este
o mică
problemă de teme -- de ce nu pot face doar
un cilk_for al buclei interioare?
BINE?
Deci întrebarea este, care
versiune paralelă funcționează cel mai bine?
Deci putem paralela bucla i,
putem paralela bucla j
și putem face i și j împreună.
Nu poți să faci k doar
cu o buclă paralelă
și să te aștepți să obții ceea ce
trebuie.
BINE?
Și asta este.
Deci, dacă te uiți...
wow!
Ce diferență de
timpi de rulare, nu?
BINE?
Dacă paralelizez doar
bucla i, este de 3,18 secunde,
iar dacă paralelizez
bucla j, de fapt încetinește,
cred, nu?
Și apoi, dacă fac și
i și j, tot e rău.
Vreau doar să fac
bucla exterioară acolo.  Se pare că
asta are de-a face
cu programarea cheltuielilor generale
și vom afla despre
programarea cheltuielilor generale
și cum preziceți
asta și așa ceva.
Deci, regula generală aici
este, paralelizați buclele exterioare,
mai degrabă decât buclele interioare, OK?
Și atunci când facem
bucle paralele,
obținem o viteză de aproape 18x
pe 18 nuclee, OK?
Așa că permiteți-mi să
vă asigur că nu tot codul
este atât de ușor de paralelizat.
BINE?
Dar acesta se întâmplă să fie.
Deci acum ajungem la, ce, cam
peste 5% din vârf.
BINE?
Deci unde
pierdem timpul aici?
OK, de ce primim doar 5%?
Da?
PUBLIC: Deci o altă zonă a
paralelismului care [INAUDIBIL]..
Deci am putea, de exemplu,
vectoriza multiplicarea.
CHARLES LEISERSON: Da.
Bun.
Deci, acesta este unul și
există unul pe
care nu îl folosim
foarte eficient.
BINE.
Acesta este unul și acestea
sunt cele două optimizări pe care le vom
face pentru a obține
un cod foarte bun aici.
Deci care este celălalt?
Da?
PUBLIC:
Operația de înmulțire și adunare.
CHARLES LEISERSON:
De fapt, este legat
de aceeași întrebare, bine?
Dar există o altă
sursă de oportunitate complet diferită
aici.
Da?
PUBLIC: Am putea face, de asemenea, mult
mai bine în gestionarea
ratelor de cache.
CHARLES LEISERSON: Da.
OK, de fapt putem gestiona
mai bine pierderile de cache.
BINE?
Deci, să revenim
la cache-urile hardware
și să restructurăm
calculul
pentru a reutiliza datele din
cache cât mai mult posibil.
Deoarece pierderile din cache sunt
lente, iar accesările sunt rapide.
Și încercați să profitați la
maximum de memoria cache
reutilizand datele
care sunt deja acolo.
BINE?
Deci haideți să aruncăm o privire.
Să presupunem că vom
calcula doar un rând de C, OK?
Așa că trecem printr-un rând de
C. Asta ne va lua--
deoarece este un vector lung de 4.096
acolo,
acesta va fi practic
4.096 scrieri pe care le vom
face.
BINE?
Și vom obține o
localitate spațială acolo,
ceea ce este bine, dar
practic
facem-- procesorul
face 4.096 de scrieri.
Acum, pentru a calcula acel rând,
trebuie să accesez 4.096 de citiri
de la A, bine?
Și am nevoie de tot B, bine?
Pentru că merg pe fiecare
coloană a lui B pe măsură ce
parcurg pentru a
calcula complet C. Văd oamenii asta?
BINE.
Deci trebuie să
calculez doar un rând de C,
trebuie să accesez un rând
de A și tot B. OK?
Pentru că primul element din
C are nevoie de întreaga coloană
a lui B. Al doilea element de C
are nevoie de întreaga a doua coloană
a lui B. Încă o dată, nu vă faceți
griji dacă nu înțelegeți pe deplin
acest lucru,
pentru că acum sunt
doar  rupând
asta cu viteză mare.
Vom aprofunda acest lucru
în clasă
și vom avea suficient
timp pentru a stăpâni aceste lucruri.
Dar principalul lucru
de înțeles este că
treci prin
tot B, apoi
vreau să calculez un
alt rând de C. O să
fac același lucru.
Voi trece din nou printr-
un rând de A și tot B
, astfel încât când termin să
facem aproximativ 16 milioane,
17 milioane de
accesări la memorie în total.
BINE?
Asta înseamnă mult acces la memorie.
Și dacă, în loc să
fac asta,
fac lucruri în blocuri, bine?
Deci, ce se întâmplă dacă vreau să calculez
un bloc de 64 cu 64 de C,
mai degrabă decât un rând de C?
Deci, să aruncăm o privire
la ce se întâmplă acolo.
Deci, amintește-ți,
apropo, acest număr...
16, 17 milioane, bine?
Pentru că o să
comparăm cu ea.
BINE?
Deci, ce zici de a
calcula un bloc?
Deci, dacă mă uit la un bloc,
acesta va lua--
64 cu 64 necesită și 4.096
scrieri către C. Același număr, OK?
Dar acum trebuie să
fac aproximativ 200.000 de
citiri din A pentru că trebuie
să accesez toate acele rânduri.
BINE?
Și apoi pentru B, trebuie să
accesez 64 de coloane din B, OK?
Și asta înseamnă încă
262.000 de citiri din B, bine?
Care ajunge să fie o jumătate de
milion de accesări la memorie în total.
BINE?
Așa că ajung să fac mult
mai puține accesări, OK,
dacă acele blocuri se vor
încadra în cache-ul meu.
BINE?
Deci fac mult mai puțin pentru a calcula
amprenta de aceeași dimensiune
dacă calculez un bloc, mai degrabă
decât să calculez un rând.
BINE?
Mult mai eficient.
BINE?
Și aceasta este o schemă
numită tiling,
și deci, dacă faceți înmulțirea matricei în mosaic
, ceea ce faceți
este să vă spargeți matricele
în, să spunem, 64
cu 64 submatrici,
și apoi faceți
două niveluri de înmulțire a matricei.
Faceți un nivel exterior de
înmulțire a blocurilor folosind
același algoritm, iar
apoi când apăsați pe interior,
pentru a face o înmulțire a matricei 64 cu 64
,
fac apoi alte
trei bucle imbricate.
Deci ajungi cu
6 bucle imbricate.
BINE?
Și, deci,
practic, o faci așa.
Și există un
parametru de reglare, desigur,
care este, știi, cât de
mare îmi fac dimensiunea plăcii?
Știi, dacă e s by s,
ce ar trebui să fac la frunzele de
acolo?
Ar trebui să fie 64?
Ar trebui să fie 128?
Ce număr ar trebui să folosesc acolo?
Cum găsim valoarea corectă
a lui s, acest parametru de reglare?
BINE?
Idei despre cum l-am putea găsi?
PUBLIC: Vă puteți da seama
cât de mult este în cache.
CHARLES LEISERSON:
Ai putea face asta.  S-
ar putea să obții un număr,
dar cine știe ce
se mai întâmplă în cache
în timp ce faci asta.
PUBLIC: Testează doar
câteva dintre ele.
CHARLES LEISERSON: Da,
testează o grămadă de ele.
Experiment!
BINE?
Încercați-le!
Vezi care îți dă
numere bune.
Și când faci
asta, se dovedește
că 32 îți oferă cea
mai bună performanță, OK,
pentru această problemă specială.
BINE?
Așa că îl poți bloca, și
apoi poți deveni mai rapid,
iar când faci asta, asta ne-a
oferit o accelerare de aproximativ 1,7.
BINE?
Deci acum suntem până la...
ce?
Suntem aproape 10% din vârf, bine?
Și celălalt lucru este
că, dacă utilizați Cachegrind
sau un instrument similar,
vă puteți da seama
câte referințe cache
există și așa mai departe
și puteți vedea
că, de fapt, a
scăzut destul de considerabil atunci când
faceți placarea față de doar
bucle paralele drepte.
BINE?
Deci, încă o dată, puteți folosi instrumente
care să vă ajute să înțelegeți acest lucru
și să înțelegeți
cauza a ceea ce se întâmplă.
Ei bine, se
pare că cipurile noastre
nu au doar un singur cache.
Au trei
niveluri de cache.
BINE?
Există cache L1, bine?
Și există date
și instrucțiuni,
așa că ne gândim
la date aici,
pentru datele pentru matrice.
Și are un L2-cache,
care este, de asemenea, privat
pentru procesor, și
apoi un L3-cache partajat,
iar apoi
ieși la DRAM--
poți merge și la
procesoarele vecine
și altele.
BINE?
Și sunt de dimensiuni diferite.
Puteți vedea că cresc în dimensiune--
32 kilobytes, 256
kilobytes, până la 25 megabytes,
la memoria principală, care
este de 60 gigaocteți.
Deci, ceea ce puteți face este, dacă
doriți să faceți tiling pe două niveluri,
OK, puteți avea doi
parametri de reglare, s și t.
Și acum trebuie să faci--
nu poți face căutare binară
pentru a-l găsi, din păcate,
pentru că este multidimensional.
Trebuie să o
faci în mod exhaustiv.
Și când faci asta,
ajungi cu... [
Râsete]
- cu 9 bucle imbricate, OK?
Dar, desigur, nu
vrem cu adevărat să facem asta.
Avem trei niveluri
de stocare în cache, bine?
Poate cineva să-și dea seama
numărul inductiv?
Pentru trei niveluri de stocare în cache,
câte niveluri de tiling
trebuie să facem?
Acesta este un dați-mi, nu?
PUBLIC: 12.
CHARLES LEISERSON: 12!
Bun, 12, bine?
Da, atunci faci 12.
Și omule, știi, când spun că
codul devine urât când
începi să faci lucrurile să meargă repede.
BINE?
Dreapta?
Acesta este ca, ughhh!
[Râsete]
OK?
Bine, dar se pare că există
un truc.
Puteți plăti pentru
fiecare putere de 2
simultan, doar rezolvând
problema recursiv.
Așa că ideea este că
împărțiți și cuceriți.
Împărți fiecare dintre matrice
în 4 submatrici, bine?
Și apoi, dacă te uiți la
calculele pe care trebuie să le faci,
trebuie să rezolvi 8
subprobleme de jumătate din dimensiune
și apoi să faci o adunare.
BINE?
Și astfel aveți
8 înmulțiri
de mărime n peste 2 cu n peste 2 și
1 adunare a n cu n matrice,
și asta vă oferă răspunsul.
Dar atunci, desigur,
ceea ce vei face
este să rezolvi fiecare dintre
acestea în mod recursiv, bine?
Și asta
vă va oferi, în esență,
același tip de performanță.
Iată codul.
Nu mă aștept să
înțelegi asta,
dar am scris asta
folosind în paralel,
pentru că se dovedește că poți
face 4 dintre ele în paralel.
Iar generația Cilk de aici spune:
du-te și fă această subrutină, care
este, în principiu, o subproblemă, și
apoi, în timp ce faci asta,
ai voie să mergi și să executi
următoarea instrucțiune - pe care o
vei face o altă generare și
un alt spawn și în sfârșit asta.
Și apoi această
afirmație spune, ah,
dar nu începe
faza următoare până nu
termini prima fază.
BINE?
Și vom învăța
despre aceste lucruri.
OK, când facem asta,
obținem un timp de rulare
de aproximativ 93 de secunde, care
este de aproximativ 50 de ori mai lent
decât ultima versiune.
Folosim cache-ul mult
mai bine, dar se dovedește, știi
, nimic nu este gratuit,
nimic nu este ușor, de obicei,
în ingineria performanței.
Trebuie să fii inteligent.
Ce s-a intamplat aici?
De ce s-a înrăutățit asta,
deși... se dovedește că,
dacă te uiți
la numerele de stocare în cache,
primești
rezultate grozave pe cache.
Adică, foarte puține
rateuri de cache, o mulțime de accesări în cache,
dar suntem încă mai încet.
De ce crezi că este?
Lasă-mă să iau pe cineva...
da?
PUBLIC: Overhead pentru a începe
funcțiile și [INAUDIBLE].
CHARLES LEISERSON:
Da, overhead
până la începutul funcției
și, în special, locul
în care contează este la
începutul calculului.
BINE?
Deci ceea ce facem este că avem
un caz de bază foarte mic.
Facem această suprasarcină până la
n egal cu 1.
Deci, există un
apel de funcție, chiar și atunci când
înmulțiți 1 cu 1.
Deci, hai, să alegem un prag,
iar sub acel prag,
să folosim doar un bun standard.
algoritm pentru acel prag.
Și dacă suntem peste asta, ne vom
împărți și vom cuceri, bine?
Deci ceea ce facem este să numim --
dacă suntem mai mici decât
pragul, numim un caz de bază,
iar cazul de bază seamănă foarte
mult cu o multiplicare matriceală obișnuită
.
BINE?
Și așa, când faci asta,
poți să te uiți din nou
pentru a vedea care este cea mai bună
valoare pentru cazul de bază
și se dovedește că în acest
caz, cred că este 64.
OK?
Ajungem la 1,95 secunde.
Nu am făcut cazul de bază
de 1, pentru că am încercat asta,
și acesta a fost cel care
ne-a dat performanțe groaznice.
PUBLIC: [INAUDIBIL]
CHARLES LEISERSON: Îmi pare rău.
32-- oh, da.
32 este chiar mai bine.
1.3.
Bine, da, așa că am ales 32.
Cred că chiar... oh,
nu l-am evidențiat.
BINE.  Ar fi trebuit să
subliniez
asta pe diapozitiv.
Deci, atunci când facem asta,
acum obținem 12% din vârf.
BINE?
Și dacă numărați
câte rateuri de cache avem,
puteți vedea că --
iată cache-ul de date pentru
L1, iar cu divider
și cucerire paralel este cel
mai mic, dar și acum la fel
este și cache-ul de ultimul nivel.
BINE?
Și atunci și numărul total de
referințe este mic.
Deci, împărțiți și cuceriți se
dovedește a fi o mare victorie aici.
BINE?
Acum, celălalt lucru pe care l-am
menționat, și anume că
nu folosim hardware-ul vectorial.  Toate
aceste lucruri au vectori pe
care putem opera, bine?
Au hardware vectorial care
procesează datele în ceea ce se numește
SIMD, ceea ce înseamnă
flux cu instrucțiuni unice,
date multiple.
Asta înseamnă că dai
o singură instrucțiune
și face operații
pe un vector, OK?
Și așa cum am menționat,
avem 8 unități în virgulă mobilă
per nucleu, dintre care putem
face și un fuzionat-multiplicare-adăugare, OK?
Deci, fiecare registru vectorial
conține mai multe cuvinte.
Cred în mașina pe care o
folosim acest termen, sunt 4 cuvinte.
Așa cred.
BINE?
Dar este important când
le folosești, nu
le poți folosi doar vrând-nevrând.
Trebuie să operați asupra datelor
ca o bucată de date vectoriale.
Nu poți, știi
, ca această bandă
a unității vectoriale să facă un
lucru și o bandă diferită
să facă altceva.
Toți trebuie să facă
în esență același lucru,
singura diferență fiind
indexarea memoriei.
BINE?
Deci, când faci asta...
deci deja am
profitat de asta.
Dar puteți produce un
raport de vectorizare solicitând
asta, iar sistemul
vă va spune ce fel de lucruri
sunt vectorizate, ce
lucruri sunt vectorizate și
care nu.
Și vom vorbi despre
modul în care vectorizați lucruri pe
care compilatorul nu
vrea să le vectorizeze.
BINE?
Și, în special, majoritatea mașinilor
nu acceptă cele mai noi seturi
de instrucțiuni vectoriale,
astfel încât compilatorul
folosește instrucțiunile vectoriale în mod
conservator în mod implicit.
Deci, dacă compilați
pentru o anumită mașină,
puteți spune, utilizați acea
anumită mașină.
Și iată câteva dintre
steaguri de vectorizare.
Puteți spune, folosiți
instrucțiunile AVX dacă aveți AVX.
Puteți utiliza AVX2.
Puteți utiliza instrucțiunile
vectoriale fuzionate-multiplicare-adăugați
.
Puteți da un
șir care vă spune
arhitectura pe care
rulați,
pe acel lucru special.
Și poți spune, ei bine, folosește
orice mașină pe care
compilez în prezent, OK,
și va da seama
ce arhitectură este aceea.
BINE?
Acum, numerele în virgulă mobilă, despre cum vom
vorbi,
se dovedesc a avea unele
proprietăți nedorite,
ca și cum nu ar fi asociative,
așa că dacă faceți A ori B
ori C, modul în care puneți parantezele
vă poate oferi
două numere diferite.
Și așadar, dacă dați o
specificație a unui cod,
de obicei, compilatorul
nu va schimba
ordinea asociativității,
deoarece spune,
vreau să obțin exact
același rezultat.
Dar îi puteți da
un steag numit
rapid matematică, minus ffast-math,
care îi va permite
să facă acest tip de reordonare.
BINE?
Dacă nu este important
pentru tine, atunci
va fi aceeași cu
comanda implicită, OK?
Și când utilizați asta -
și în special folosind
arhitectura nativă
și matematică rapidă, obținem de fapt o
performanță dublă
din vectorizare,
doar avându-l
pe compilator să o vectorizeze.
BINE?
Da, întrebare.
PUBLIC: Tipurile de date sunt
în matricea noastră, sunt pe 32 de biți?
CHARLES LEISERSON:
Sunt pe 64 de biți.
Da.
În zilele noastre, 64 de biți
este destul de standard.
Ei numesc asta precizie dublă,
dar este destul de standard.
Cu excepția cazului în care faceți
aplicații AI, caz în care este
posibil să doriți să faceți
aritmetică de precizie mai mică.
PUBLIC: Deci float și
double sunt ambele la fel?
CHARLES LEISERSON:
Nu, plutitorul are 32 de ani, bine?
Deci, în general, oamenii care
fac calcule serioase de algebră liniară
folosesc 64 de biți.
Dar, de fapt, uneori
pot folosi mai puțin
și atunci poți
obține mai multă performanță
dacă descoperi că
poți folosi mai puțini
biți în reprezentarea ta.
Vom vorbi și despre asta.
BINE?
Deci ultimul lucru pe care îl vom
face
este să puteți folosi
instrucțiunile,
instrucțiunile vectoriale,
mai degrabă decât să vă
bazați pe compilator pentru a face acest lucru.
Și există un întreg manual
de instrucțiuni intrinseci pe
care le puteți apela din C, care
vă permit să faceți, știți,
instrucțiunile vectoriale specifice
pe care ați dori să le faceți.
Deci compilatorul nu
trebuie să-și dea seama.  De
asemenea, puteți folosi mai
multe informații pentru a face lucruri
precum: puteți face
preprocesare și
puteți transpune matricele,
ceea ce se dovedește a fi de ajutor,
și faceți alinierea datelor.
Și există o mulțime de alte
lucruri care folosesc algoritmi inteligenți
pentru cazul de bază, OK?
Și faci mai multă
inginerie de performanță.  Te
gândești la ce faci
, faci coduri, apoi
alergi, alergi, alergi
pentru a testa, și acesta este
un motiv bun pentru a avea
cloud, pentru că poți face teste
în paralel.
Așa că îți ia mai puțin timp să-ți
faci testele în ceea ce privește, știi
, să stai în jurul orei
când faci ceva.
Tu spui, oh, vreau
să fac 10 teste.
Să învârtim 10 mașini și să facem
toate testele în același timp.
Când faci asta --
și principalul pe care îl
ieșim din asta
este intrinseca AVX --
obținem până la 0,41
de vârf, deci 41% din vârf și
obținem aproximativ 50.000 de accelerare.
BINE?
Și se pare că
acolo am renunțat.
BINE?
Iar motivul este
pentru că


în acel moment am depășit Biblioteca Math Kernel de la Intel, proiectată profesional.
[Râsete]
OK?
Știi, o
întrebare bună este, de ce nu
ajungem la maxim?
Și știi, te invit să
încerci să-ți dai seama, bine?
Se pare,
totuși, că Intel MKL este
mai bun decât ceea ce am făcut noi, deoarece am
presupus că este o putere de 2.
Intel nu presupune
că este o putere de 2
și sunt mai robusti,
deși câștigăm pe 496
prin  496 de matrici, ele câștigă
pe alte dimensiuni de matrice,
deci nu sunt toate lucrurile.
Dar sfârșitul poveștii
este, ce am făcut?
Tocmai am făcut un
factor de 50.000, bine?
Dacă te-ai uita la
economia de gaz, OK, a unui avion jumbo
și ai obține
performanța pe
care tocmai l-am obținut în termeni
de mile pe galon,
ai putea să rulezi un jumbo
jet pe un mic scuter Vespa
sau orice tip de
scuter.  asta este în ordine?
Atât am
reușit să o facem.
În general,
permiteți-mi să vă avertizez,
nu veți vedea amploarea
îmbunătățirii performanței pe
care am obținut-o pentru
multiplicarea matricei.
BINE?
Acesta se dovedește a fi unul în care...
este un exemplu foarte bun
pentru că este atât de dramatic.
Dar vom vedea câteva
numere substanțiale
și, în special,
în 6.172, veți
învăța cum să tipăriți singur această
monedă de performanță,
astfel încât să
nu trebuiască să luați
biblioteca altcuiva.
Poți, știi, să spui, oh,
nu, eu sunt un inginer în asta.
Permiteți-mi să menționez încă un lucru.
În acest curs, ne vom
concentra pe calculul multicore.
Nu vom face, în special,
GPU-uri
sau sisteme de fișiere sau
performanțe de rețea.
În lumea reală, acestea
sunt extrem de importante, bine?
Ceea ce am descoperit, totuși,
este că este mai bine
să înveți un anumit
domeniu și, în special,
acest domeniu anume --
oamenii care stăpânesc
ingineria performanței multicore,
de fapt, continuă să facă
aceste alte lucruri
și sunt foarte buni la asta, OK  ?
Pentru că ai învățat
felul de bază, baza,
fundația...