Predictor de Valori Last2Value

Să se implementeze în mediul SimpleScalar 3.0 un predictor de valori bazat pe perceptron numit Last-2Value. Pentru simulare se folosesc benchmark - urile SPEC’95.

Scopul proiectului :

Explorarea conceptului de reţea neuronală şi investigarea aplicabilităţii acesteia în procesul de predicţie a valorilor folosite de instrucţiunile cu acces la memorie (în cazul de faţă instrucţiunile LOAD) şi determinarea localităţii valorilor existente la nivelul acestor instrucţiuni.

1. Introducere : Reţele neuronale.

Reţelele neuronale artificiale sunt sisteme neliniare formate dintr-un număr mare de procesoare elementare relativ simple, numite neuroni (sau unităţi, sau perceptroane) care operează în paralel şi urmăresc să interacţioneze cu mediul înconjurător într-un mod asemănător creierului biologic şi care prezintă capacitatea de a învăţa. Cunoştinţele sistemului sunt reprezentate prin ponderile asociate legăturilor dintre neuroni. Învăţarea se realizează prin modificarea ponderilor interconexiunilor.

Neuronul care are ca funcţie de activare o funcţie prag bipolară, cu intrarea de prag conectată la valoarea –1, căruia i se aplica un algoritm de antrenare ce consta în modificarea ponderilor sinaptice şi are scopul de a îmbunătăţi performanţele lui, se numeşte Perceptron.

Perceptronul este una dintre cele mai simple modele de reţele neurale fiind utilizat la clasificarea patern - urilor.

{ x1, x2, …, xn} – datele de intrare.

{ w1, w2, …, wn} – ponderile legăturilor

x0 = {-1,0,1} furnizează tipul valorii de prag.

w0 – termen liber

Y – ieşirea neuronului

Perceptronul este o unitate de procesare a informaţiei care constă din următoarele trei elemente de bază :

- un set de sinapse, sau legături de interconectare, sau ponderi, care transmit semnalele de intrare xi prin intermediul unei ponderi proprii. Astfel, un semnal xi conectat pe intrarea i a neuronului k, va fi multiplicat la propagarea prin sinapsă cu ponderea sinaptică wki. Dacă wki>0, sinapsa asociată este excitatoare, iar dacă wki<0, sinapsa asociată este inhibitoare;

- o intrare de prag, w0, termen liber care reprezintă tendinţa intrinseca a ieşirii independent de intrări, cu x0=1; utilizarea valorii de prag are efectul unei transformări afine asupra sumei liniare ponderate a intrărilor neuronului;

- un sumator, care sumează semnalele de intrare ponderate prin intermediul ponderilor sinaptice şi intrarea de prag;

- funcţie de activare, liniară sau neliniară, care în general limitează amplitudinea semnalului de la ieşirea neuronului la intervalele [0,1], sau [-1,1].

Funcţia de baza a perceptronului este de clasificare liniar separabilă.

Suma tuturor semnalelor de intrare furnizează potenţialul intern Y.

Dându-se un vector de intrare x=(x1, x2, ..., xn) şi vectorul de ponderi corespunzător w=(w1, w2, ..., wn), ieşirea neuronului artificial va fi :

Fiecare intrare este ponderată şi reprezintă gradul de corelaţie al fiecărei intrări cu ieşirea. O pondere pozitivă reprezintă o intrare excitatoare. O pondere negativă reprezintă o intrare inhibitoare . Ponderile wi sunt modificate în timpul procesului de antrenament în conformitate cu regula de învăţare.

Funcţia de prag (engleza : hard - limiter), este definită de relaţiile :

În cazul în care valoarea rezultatul este sub pragul ales, este necesar ca reţeaua să mai “înveţe” (să se actualizeze) până când rezultatul va fi cel dorit (peste pragul ales).

În esenţă, perceptronul funcţionează ca un element de clasificare, fiind capabil să clasifice setul vectorilor de intrare în două clase, cu condiţia ca mulţimea acestora să conţină elemente liniar separabile.

2. Corelaţia Predicţie - Perceptron

O tendinţă proeminentă în domeniul cercetării arhitecturilor de calcul este legată de îmbunătăţirea performanţelor sistemului, prin adăugarea de predicţie şi speculaţie la arhitectura acestora.

Predicţiile sunt necesare în mare parte pentru salturi si valori. Faţă de mecanismul de predicţie a salturilor care are ca rezultat un bit ce specifică ramura potrivită pentru execuţia secvenţială a programului, mecanismul de predicţie a valorilor returnează direct valoarea instrucţiunii. În principiu, predicţia de valori permite execuţia programului într-un timp mai scurt decât cel mai mic timp de execuţie impus de limitarea dataflow.

În acest proiect se încearcă studierea predicţiei de valori în cazul instrucţiunilor LOAD care sunt mari consumatoare de timp datorită faptului că în cel mai rău caz trebuie să acceseze valoarea necesară din memorie. Predicţia de valori este eficientă în cazul dependenţelor de date, deci, instrucţiunile ce referă aceeaşi “dată” se vor executa speculativ, în schimb mai rapid.

Scheme de predicţie a valorii : predictoare computaţionale (generează predicţia pe baza istoriei valorilor memorate, prelucrându-le după un algoritm stabilit) respectiv contextuale (lucrează la nivel de o singură instrucţiune şi încearcă să prezică viitoarea valoare care va fi produsă de instrucţiune bazându-se pe repetarea unor contexte anterior generate). Întrucât respectivele scheme încearcă să înmagazineze o cât mai mare istorie de predicţie, aceasta implică tabele hardware de mari dimensiuni şi costuri ridicate de implementare.

Problema care apare este că o instrucţiune poate lua una din 2w valori unde w reprezintă lungimea registrului. Conform observaţiilor lui Kai Wang în “Highly Accurate Data Value Prediction Using Hybrid Predictors”, un procentaj substanţial din instrucţiunile dinamice au 4 sau câteva valori unice in istoria lor recentă. Prin stocarea a maxim 4 ultime valori unice ale fiecărei instrucţiuni, şi codând binar