DIPLOMSKI RAD�PROJEKTOVANJE �HARDVERSKO-SOFTVERSKOG REŠENJA ZA AKCELERACIJU ŠAHOVSKOG PROGRAMA

DEJAN GRUBIŠIĆ

ZADATAK DIPLOMSKOG RADA

• Ubrzavanje šahovskog programa zasnovano na korišćenju hardversko-softverskog kodizajna
• Projektovanje na sistemskom nivou
• Projektovanje hardverskog modula za ubrzavanje
• Funkcionalna verifikacija hardverskog modula

MOŽE LI RAČUNAR POBEDITI ČOVEKA U ŠAHU?

MOŽE LI RAČUNAR POBEDITI ČOVEKA U ŠAHU?

• 1950. - Klod Šenon (Claude Shannon) objavljuje prvi rad koji se bavi problemom šaha na računarima
• 1951. - Alan Turing godine objavljuje algoritam za igranje šaha
• 1952. - Prvi program za nalaženje mata u dva poteza
• 1956 - Otkrivanje alfa-beta pretrage
• 1957. Prvi potpuno automatizovani program za šah
• 1997. Šahovski program Deep Blue pobeđuje aktuelnog prvaka sveta Gari Kasparova

​

MINI-MAX ALGORITAM I ALFA BETA PRETRAGA

PROBLEM KOD MINIMAX ALGORITMA

• Velik broj izračunavanja pozicija
• Procenjuje se da postoji oko 10 na 120 završnih grana na stablu, računajući od početka partije do kraja
• U koliko bi svi atomi evaluirali po jednu poziciju svaku 1ns od početka univerzuma, ne bi idalje stigli da izračunaju sve pozicije

PROJEKTOVANJE NA SISTEMSKOM NIVOU

PROJEKTOVANJE NA SISTEMSKOM NIVOU

• Izvorni C kod – Tom Kerigan (Tom Kerrigan), Simple Chess Program
• ESL metodologija: 1) Specifikacija i modelovanje� 2) Analiza pre particionisanja� 3) Particionisanje� 4) Analiza posle particionisanja� 5) Verifikacija posle particionisanja� 6) Implementacija hardvera i softvera� 7) Verifikacija implementiranog hardvera

​

​

ANALIZA PRE PARTICIONISANJA

• Funkcije attack i eval, kandidati za realizaciju u hardveru
• Funkcije search i quiesce implementiraju MINIMAX algoritam i nisu kritične vremenski, zbog čega treba da budu implementirane u softveru

PARTICIONISANJE

• Funkcija odabrana za hardversku implementaciju je eval
• Ciljana arhitektura - Zybo ploča�
• Interfejsi: Ulazni int color[64]� int piece[64]� int side

Izlazni� int result

color[10] = ‘1’ - Crni

piece[10] = ‘0’ Pešak

• Definisane su dve klase, soft i eval, koje nasleđuju baznu klasu svih komponenti sc_module
• Mogućnost upotrebe paralelnih procesa
• Mogućnost korišćenja signala za komunikaciju

SISTEM NAKON PARTICIONISANJA

IMPLEMENTACIJA MODULA EVAL

Da bi se iskoristile prednosti koje hardverska implementacija pruža potrebno je :

1) Utvrđivanje međuzavisnosti u kodu

2) Paralelizovati prolazak kroz petlje

3) Sinhronizovati komunikaciju između� odvojenih blokova

​

​

​

​

IMPLEMENTACIJA MODULA EVAL

Osnovna ideja za implementaciju u hardveru:

• Napraviti modul koji će prepoznavati figure i prosleđivati ih drugim blokovima na obradu i izračunavati RANK pešaka
• Projektovati odvojeno blokove za evaluaciju pešaka i kralja, zbog povećane kompleksnosti i implementacije preko odvojenih funkcija u izvornom kodu
• Projektovati modul za uračunavanje doprinosa ostalih figura
• Napraviti modul koji će sumirati sve doprinose

PROJEKTOVANJE MODULA EVAL U HARDVERU�

PROJEKTOVANJE MODULA EVAL U HARDVERU

• Datapath�- Memorijski elementi�- Funkcionalne jedinice�- Mreža za rutiranje

​

• Controlpath�- Logika za generisanje narednog stanja�- Registar stanja�- Izlazna logika

PROJEKTOVANJE BLOKA SELECT_PIECE U HARDVERU

• Uvođenje protočne obrade po kolonama
• Generisanje logike za upis u bafere

​

​

PROJEKTOVANJE BLOKA SELECT_PIECE U HARDVERU

• Idle – čeka na start i kada stigne započinje čitanje iz memorije i postavlja vrednosti na nulu
• Prolog – započinje upis u fifo bafere i prelazi u aktivno stanje
• Active – kada brojač dostigne ‘6’, zaustavlja se čitanje iz memorije i u sledećem taktu prelazi u stanje finished
• Finished – čeka da se završi evaluacija čitave pozicije

PROJEKTOVANJE BLOKA SELECT_PIECE U HARDVERU

• Svako od polja jedne kolone ima ovakve blokove za sve figure osim kralja i kraljice
• Realizovano for generate naredbom u VHDL-u

PROJEKTOVANJE BLOKA EVAL_PAWN U HARDVERU

• Idle – čeka start i postavlja sumu na nulu
• Active – akumulira vrednost pešaka, koje dobije na ulazu iz fifo bafera, sve dok ne dobije znak da više nema pešaka, kada ide u propagate
• Propagate – čeka da se vrednost pešaka akumulira u ukupnu sumu i prelazi u stanje finished
• Finished – čeka kraj ukupne evaluacije

PROJEKTOVANJE BLOKA EVAL_PAWN U HARDVERU

• Svaki pešak je opisan sa 7 bita, pri čemu najviši bit govori da li on postoji, a ostalih 6 opisuju poziciju
• Kada je stanje idle resetuje se akumulator

PROJEKTOVANJE MODULA MATERIAL_OF_PIECES U HARDVERU

• Idle – čeka na start i resetuje akumulatore
• Active – akumulira doprinose figura u akumulatore i čeka da sve figure budu poslate iz fifo bafera
• Finished – čeka kraj evaluacije pozicije

PROJEKTOVANJE MODULA MATERIAL_OF_PIECES U HARDVERU

• Slično kao i prethodni modul prikuplja podatke sa fifo bafera i akumulira njihov doprinos
• Kada je stanje idle resetuju se akumulatori

PROJEKTOVANJE MODULA EVAL KING U HARDVERU

• Idle – čeka na start i određuje koja se celina izvršava
• Active – evaluira zaštićenost kralja na osnovu položaja pešaka
• Finished – skalira dobijene rezultate sa materijalom protivnika

PROJEKTOVANJE MODULA EVAL KING U HARDVERU

• Na osnovu Rank-a pešaka postavljaju se negativni poeni
• Prve dve celine sadrže 5 stanja, a treća 3
• U koliko je materijal protivnika manji od 1200 uzima se vrednost iz matrice

PROJEKTOVANJE MODULA ADDER U HARDVERU

• Idle – čeka da se startuje modul i pamti stranu na potezu i prelazi u stanje active
• Active – sumira rezultate svih modula u koliko su oni završili i kada svaki od njih pošalje signal o završetku, modul adder šalje znak da je evaluacija gotova i vraća se u stanje idle

​

PROJEKTOVANJE MODULA ADDER U HARDVERU

• Kada se rezultati predhodnih modula spremni, upisuju se u ulazne registre i propagiraju do registra s_temp_result, koji u zavisnosti od strane na potezu dobija znak i šalje se na izlaz
• Paralelno sa izračunavanjem rezultata propagira se i signal da je evaluacija završena

INTEGRISANJE U SISTEM

• Pomoću Vivado IP integratora dobijamo sistem sa slike
• Na osnovu statičke vremenske analize dobijamo da period takta može biti najmanje 13,175ns, što je 75,9 MHz

• Vreme potrebno da se evaluira jedna pozicija je 454,562 ns
• Vreme potrebno da se u softveru evaluira jedna pozicija prosečno iznosi 750ns, na osnovu sledećeg dela koda

ANALIZA PERFORMANSI

• Ubrzanje hardverske u odnosu na softversku implementaciju je 1,65 puta
• Broj poziva funkcije eval prosečno iznosi 23000 puta po potezu na dubini 4
• Na osnovu ovoga može se zaključiti da je ubrzanje po potezu oko 38000 puta
• U koliko bi se povećala dubina pretrage bilo bi potrebno eksponencijalno više poziva funkcije eval, pri čemu bi se dobilo još veće hardversko ubrzanje

FUNKCIONALNA VERIFIKACIJA

FUNKCIONALNA VERIFIKACIJA

• Verifikaciono okruženje dobijeno korišćenjem UVM metodologije
• Sastoji se od generisanja ulaznih pozicija za modul i provere dobijenih rezultata
• Zasnovana na principu referentnog modela

​

TIPIČNA STRUKTURA UVM TESTBENČA

• Sekvencer – generiše ulazne signale na visokom vivou apstrakcije
• Drajver – te signale prevodi na nizak nivo razumljiv hardveru
• Monitor – nadgleda ulaze i izlaze projektovanog modula, podiže nivo apstrakcije i šalje skorbordu i monitoru
• Skorbord – upoređuje dobijene rezultate sa očekivanim
• Monitor – beleži koji su sve slučajevi provereni

KLASA EVAL_FRAME

• Obuhvata signale transakcija i ograničenja njihovih vrednosti
• Nasleđuje baznu klasu uvm_sequence_item
• Signali koji čine transakciju opisuju poziciju i kontrolne signale
• Polje rand označava da će se tim signalima dodeliti nasumična vrednost pri pozivu funkcije randomize.
• Polja color_in i piece_in dobijaju nasumične vrednosti neposredno posle randomizacije ostalih promenjivih

OGRANIČENJA

• Beli pešaci nikad nisu na osmom, odnosno crni na prvom redu
• Broj pešaka ne može biti veći od osam
• Mora da postoji jedan kralj na obe strane
• Zbir broja promovisanih figura i preostalih pešaka je manji ili jednak sa osam

SEKVENCER I DRAJVER

• Klasa sekver je generiše sekvence i nasleđuje baznu klazu uvm_sequencer
• Drajver i sekvencer su povezani preko TLM (transaction level modeling) porta
• Drajver čeka u beskonačnoj petlji da dobije transakciju, nakon čega pakuje informacije o poziciji pogodne za hardver i šalje stimulus IP bloku
• Nakon ovoga čeka kraj evaluacije i završava rukovanje sa sekvencerom

​

​

MONITOR

• Nasledjuje baznu klasu uvm_monitor
• Nadgleda signale koji se šalju IP bloku i šalje ulaznu poziciju i evaluirani rezultat skorbordu na dalju proveru
• Ovo je urađeno korišćenjem dva paralelna procesa za upis u memoriju i start signal u tasku collect_input i procesom collect result koji čeka završetak evaluacije
• Po dobijanju rezultata funkcijom write se upisuje transakcija na TLM port prema skorbordu

SKORBORD

• Nasleđuje baznu klasu uvm_scoreboard
• Implementira write funkciju preko koje mu monitor šalje transakciju
• Na osnovu ulaza transakcije izračunava očekivani rezultat na osnovu referentnog modela i upoređuje ga sa dobijenim rezultatom od monitora
• Ukoliko rezultati nisu isti prijavljuje se greška

VERIFIKACIONA OKOLINA

• Nasleđuje baznu klasu uvm_env
• Instancira komponente sekvencera, drajvera i monitora u sklopu agenta
• Instancira i povezuje monitor i skorbord preko TLM portova

POVEZIVANJE SA IP MODULOM

• U top modulu se instancira IP blok koji se verifikuje i povezuje se sa virtuelnim interfejsima, preko kojih komunicira sa ostatkom verifikac
• Dizajn je sam po sebi statička komponenta, dok se komponente verifikacionog okruženja dinamički alociraju ionog okruženja
• U ovom modulu se definišu takt, reset i pokreću se simulacioni testovi

POKRIVENOST

• Strukturna (Code Coverage)�- daje informacije o stepenu izvršavanja svih linija koda dizajna�- može biti pokrivenost linija, naredbi, grananja, FSM stanja…�-automatski se generiše

• Funkcionalna (Functional Coverage)�- utvrđuje da li dizajn implementira sve zadate osobine�- poziva se eksplicitno generisanjem grupa pokrivenosti�- mogu se pamtiti vrednosti signala na neki događaj, ili pozivom funkcije sample

​

REZULTATI STRUKTURNE POKRIVENOSTI

• Projektovani dizajn je prošao kroz sva stanja
• Svi moduli osim select_piece imaju punu pokrivenost naredbi i grananja
• Select_piece u sebi sadrži fifo registre, koji nikada neće biti popunjeni do kraja, zbog čega i rezultati strukturne pokrivenosti nisu na 100 posto

REZULTATI FUNKCIONALNE POKRIVENOSTI

• Definisane su četiri grupe pokrivenosti:

1) piece_number_value_cg – proverava da li je broj figura istog tipa (osim pešaka i kralja) bio svaki broj iz opsega od 0-5

2) pawn_number_value_cg – da li je broj pešaka bio od 0-8

3) side_value_cg – da li je na potezu bio i beli i crni

4) square_value_cg – da li je svako polje imalo svaki tip figure

REZULTATI FUNKCIONALNE POKRIVENOSTI

• Rezultati za pokrivenost polja svakom figurom nisu na 100 posto, jer prvi i osmi red nikad neće imati pešake, što se može videti iz tabele

ZAKLJUČAK

• U ovom radu urađeno je modelovanje hardversko softverskog sistema, projektovanje IP modula eval i njegova verifikacija
• Maksimalna frekvencija rada modula je 75,9 MHz čime je postignuto ubrzanje od 1,65 puta po jednoj evaluaciji, odnosno prosečno 38000 puta po potezu
• Sistem je verifikovan skupljanjem pokrivenosti po prisutnosti figura na svakom polju, broja figura istog tipa i igrača na potezu

HVALA NA PAŽNJI