SPS - Simple Perceptron Simulator
© RADU Ciprian-Vasile
All rights reserved.

Notiuni teoretice generale

 În cadrul procesoarelor pipeline pot aparea situatii defavorabile (hazarduri) care determina stagnarea (întârzierea) procesarii, având o influenta negativa asupra ratei de executie a instructiunilor. Se disting trei categorii de hazarduri: structurale, de date si de ramificatie.

Hazardurile structurale sunt determinate de conflicte la resurse comune, adica atunci când mai multe procese simultane aferente mai multor instructiuni în curs de procesare acceseaza o resursa comuna. Eliminarea (sau reducerea) prin hardware se realizeaza prin multiplicarea resurselor sau modificari arhitecturale (bus-uri si cache-uri separate vs. unificate).

Hazardurile de date apar când o instructiune depinde de rezultatele unei instructiuni anterioare din banda de asamblare. Se clasifica în 3 categorii, dependent de ordinea acceselor de citire, respectiv scriere în cadrul instructiunilor: RAW, WAR, WAW. Ultimele 2 tipuri de hazarduri nu reprezinta conflicte reale, ci doar conflicte de nume care pot fi eliminate prin "renaming" aplicat registrilor. Reducerea efectelor defavorabile provocate de hazardurile RAW se realizeaza hardware prin "forwarding" (pasarea anticipata a rezultatului instructiunii i, nivelului de procesare aferent instructiunii j care are nevoie de acest rezultat).

Hazardurile de ramificatie sunt generate de instructiunile de ramificatie (branch-uri) si determina pierderi de performanta mai importante decât hazardurile structurale si de date. Reducerea efectelor defavorabile se poate face prin metode software (scheduling = reorganizarea programului sursa) sau prin metode hardware (predictie = determinarea în avans - daca saltul se face - a noului PC program counter). Frecventa instructiunilor de salt în programele de calcul este de 2 ÷ 8% din instructiunile programului (pentru salturi neconditionate) si 11 ÷ 17% din instructiunile programului (pentru salturi conditionate). De asemenea statisticile arata ca, salturile conditionate simple se fac cu probabilitate de 50%, buclele (loops) se fac cu probabilitate de 90% si salturile orientate pe bit nu se prea fac.

Predictia prin hardware reprezinta una din cele mai performante strategii actuale de gestionare a ramificatiilor de program. Strategiile hardware de predictie a branch-urilor au la baza un proces de predictie "run - time" a ramurii de salt conditionat precum si determinarea în avans a noului PC. Ele sunt comune atât procesoarelor scalare cât si celor cu executii multiple ale instructiunilor. Avantajul metodelor hardware fata de cele software îl constituie independenta fata de masina. Cercetari recente insista pe aceasta problema, întrucât s-ar elimina necesitatea reorganizarilor soft ale programului sursa si deci s-ar obtine o independenta fata de masina.

Necesitatea predictiei, mai ales în cazul procesoarelor cu executii multiple ale instructiunilor (VLIW, EPIC, superscalare) este imperios necesara. Este o dovada clara ca sunt necesare acurateti ale predictiilor foarte apropiate de 100% pentru a nu se "simti" efectul defavorabil al ramificatiilor de program asupra performantei procesoarelor avansate. O metoda consacrata în acest sens o constituie metoda "branch prediction buffer" (BPB).

O metoda pentru o predictie mai buna a branch-urilor poate fi predictia cu ajutorul unui predictor neuronal de tip perceptron simplu, metoda folosita de acest simulator.

Retele neuronale

Din punct de vedere al scopului, domeniul retelelor neuronale, se încadreaza în domeniul mai mare al recunoasterii formelor, iar acesta în inteligenta artificiala prin necesitatea învatarii, iar din punct de vedere al metodei aplicate, se încadreaza în cel al proceselor distribuite paralel (PDP).

Retelele neuronale încearcã sã simuleze structura neurofiziologicã a creierului uman. Creierul este alcãtuit dintr-o multime de neuroni interconectati. Fiecare neuron primeste informatii de la alti neuroni prin intermediul dendritelor si transmite la rândul sãu un semnal prin intermediul axonului. Acest model poate fi implementat pe calculator, considerând legaturile dintre neuroni numere (ponderi) care se modificã în functie de cât de des este activatã legãtura.

O retea neurala este un sistem de procesare a informatiei format dintr-o multime de neuroni (puternic) interconectati. Conceptul de retele neurale artificiale a fost inspirat de retelele neurale biologice. Neuronii biologici sunt considerati a fi constituantii structurali ai creierului care desi sunt mult mai înceti decât o poarta logica, implementata în siliciu, realizeaza inferente si gândesc mult mai rapid si, în orice caz, mai profund si mai nuantat decât cel mai bun calculator actual. Creierul compenseaza operatiile relativ încete (operatii luate individual) printr-un numar imens de neuroni interconectati, prin paralelism masiv, reusind sa se adapteze mediului înconjurator, sa "mânuiasca" informatii vagi, imprecise si probabilistice, sa generalizeze de la situatii si exemple cunoscute la situatii necunoscute, robustete, toleranta la erori. Retele neurale artificiale încearca sa imite o parte a caracteristicilor descrise mai sus ale retelelor neurale biologice si consta dintr-o multime de neuroni artificiali interconectati, de mici procesoare care executa doar operatii de baza.

Primul model de retea neuronalã a apãrut în 1958, când Frank Rosenblatt publicã prima sa lucrare despre perceptron, denumire datã retelei sale neuronale [Burj01]. Lumea oamenilor de stiinta si nu numai, a ramas fascinata de posibilitatile pe care le ofereau retelele neuronale, care puteau fi folosite la formelor. Dar în 1969, Marvin Minsky si S. Papert au analizat posibilitãtile de învatare ale perceptronului si au ajuns la concluzii destul de sceptice, dovedind imposibilitatea rezolvarii de catre perceptronul cu un singur strat a unor probleme simple, cum ar fi învatarea functiei XOR (functie care nu este liniar separabila). Ca urmare, interesul pentru acest domeniu de cercetare a scazut dramatic. Relansarea interesului oamenilor de stiintã s-a produs în 1986, odatã cu aparitia unor modele si tehnici noi de învatare supervizata (metodele propagãrii înapoi). În fapt, paternitatea metodei apartine lui Paul Werbos care a preentat-o în premiera în teza sa de doctorat, la Universitatea din Berkeley, în 1974.

Modelul matematic al unui neuron artificial propus de McColloch si Pitts calculeaza o suma ponderata de n semnale de intrare si genereaza o singura iesire de 1 daca aceasta suma este mai mare decât o anumita valoare (numita prag) si 0 daca este mai mica [Sbe00].

perceptron

Figura 1. Modelul matematic al unui neuron artificial

Continut fisiere trace

Partea practica a lucrarii consta în simulare efectuata pe benchmark-urile HSA (Hatfield Superscalar Architecture) Stanford. Pentru simulare, sunt folosite fisiere trace cu extensia (*.tra). Aceste fisiere sunt o prelucrare a programelor scrise în mnemonica de asamblare (*.ins) si a trace-urilor originale (*.trc), cu scopul de a evidentia toate salturile (inclusiv cele care nu se fac).

Întregul fisier trace (*.trc) este o înlantuire de triplete <TipInstr AdrCrt AdrDest>, unde

Desi simularea poate ignora instructiunile Load / Store din trace, deoarece în acest caz suntem interesati numai de comportarea branch-urilor, exista totusi o deficienta a acestor trace-uri: nu evidentiaza salturile care nu se fac.

Din acest motiv s-au generat noile trace-uri (fisierele *.tra). Acestea contin doar branch-urile (atât cele care se fac cât si cele care nu se fac) si exclude instructiunile Load / Store. Forma acestor fisiere este urmatoarea:

 

BT 12 30

BS 32 98

BM 100 33

NT 36 37

BRA 2& 100

MOV PC, RA (RETURN)

 

Reprezentarea salturilor se face tot sub forma unor triplete <TipBr AdrCrt AdrDest>, unde TipBr se prezinta sub forma unei codificari pe doua caractere,

  1. primul dintre ele indica daca saltul se face ('B' - saltul se face, 'N' - saltul nu se face),

  2.  iar al doilea caracter indica tipul saltului: 'T' sau 'F' - salturi conditionate, 'S' - apeluri de tip Call, 'M' - apeluri de tip Return, 'R' - salturi neconditionate. Alegerea acestei codificari a fost inspirata de mnemonicile întâlnite în sursa în limbaj de asamblare (BT, BF - salt conditionat, BSR - instructiune de tip Call, BRA - salt neconditionat si MOV PC, RA - instructiune de tip Return).

Perceptron Simplu

Notiunea de perceptron a fost introdusa de Frank Rossenblat, denumire data retelei sale neuronale. In ciuda aplicatiilor variate care puteau fi rezolvate prin intermediul retelelor neuronale , in 1969, Marvin Minsky si S.Papert au analizat posibilitatile de invatare ale perceptronului si au ajuns la concluzii destul de sceptice. Acestia au dovedit incapacitatea perceptronului cu un singur strat de a rezolva unele probleme simple, cum ar fi invatarea functiei XOR (functie care nu este liniar separabila), ca urmare, interesul pentru acest domeniu a scazut foarte mult.

Perceptronul este una dintre cele mai simple modele de retele neurale fiind utilizat la clasificarea paternurilor. Perceptronul consta dintr-un singur neuron cu ponderi ajustabile, (w1, w2... wn), si functie de activare de tip treapta.

 Desi gama de probleme pe care un perceptron cu un singur strat le poate rezolva este destul de limitata, el reprezinta punctul de plecare pentru retele mult mai complexe cu aplicatii practice.

Algoritm de invatare

Perceptronul simplu foloseste algoritmul de invatare propus de catre Daniel Jimenez, cercetator de la Universitatea Rutgers SUA. Acesta este un algoritm simplu care poate fi rezumat astfel:

Ponderile reprezinta gradul de corelatie pozitiva, respectiv negativa, dintre comportamentul saltului curent care trebuie prezis si comportamentul unui salt trecut (vazut de pe nivelul de intrare). Cu cat ponderea este mai mare cu atat influenta asupra predictiei este mai mare.

 Model

Simulatorul de fata realizeaza predictia salturilor folosind un predictor bazat pe o retea neurala simpla de tip perceptron.

functionare perceptron

Aceasta figura ilustreaza modelul grafic al perceptronului. Acesta este descris printr-un vector de intrari ale carui elemente sunt ponderile, numere intregi cu semn reprezentate pe 8 biti. Iesirea perceptronului se determina ca produs scalar intre vectorul de intrare x1...n, x0 fiind intotdeauna 1, oferind o pondere de baza (bias) , si vecotrul de ponderi w (0...n).

Ponderea de baza - bias - reflecta (invata) in ce masura comportamentul saltului curent este independent de istoria salturilor anterioare.

Intrarile perceptronului - x (1...n) - sunt bipolare, o valoare -1 aferenta unei intrari semnificand salt care nu s-a facut (not taken), iar 1 inseamna salt care s-a facut (taken).

Iesirea perceptronului - y - calculat prin produsul scalar al celor doi vectori (vector intrare si vector de ponderi) este interpretata ca predictie not taken daca are o valoare negativa, respectiv predictie taken pentru o valoare pozitiva.