Progetto-Architetture

Progetto realizzato in gruppo per il corso "Architetture e Programmazione dei Sistemi di Elaborazione"

---

Obiettivo: Sviluppare in linguaggio assembly x86-32+SSE e x86-64+AVX e openMP l'algoritmo "Polynomial Regression and Stochastic Gradient Descent"

---

Dato un insieme di osservazioni concernenti le variabili x e y e fissata una famiglia di funzioni f(x,Θ) da usare per approssimare la relazione tra x e y, ossia

y∼f(x,Θ)

il problema consiste nel trovare i parametri Θ della funzione f per cui sia minimizzato l’errore di approssimazione. Θ = [θ₁, ..., θ_t] è in generale un vettore di t parametri. In particolare, in questo progetto assumiamo che la funzione f sia una funzione polinomiale di grado deg e che l’algoritmo di ricerca dei parametri si basi sulla discesa stocastica del gradiente.

Preliminari

Un’osservazione è una coppia (x, y) dove x = [x₁, ..., x_d] ∈ R^d è un vettore d dimensionale e y ∈ R è un reale. Dato un insieme di osservazioni D = {(x₁, y₁),... ,(x_n, y_n)}, |D| = n indica la cardinalità dell’insieme D, ossia il numero di osservazioni presenti in D.

Regressione Polinomiale

Dato un insieme di osservazioni concernente la variabile d dimensionale x ∈ R^d e la variabile uni-dimensionale y ∈ R, la regressione rappresenta un metodo di stima della variabile dipendente y dato il valore della variabile multi dimensionale indipendente x = [x₁, ..., x_d] nell’ipotesi che f sia una funzione polinomiale di un certo grado deg, ovvero:

dove [d] rappresenta l’insieme {1, ..., d} e [d]^h indica il prodotto cartesiano

L’equazione (1) può essere rappresentata in forma vettoriale

dove ⟨·, ·⟩ indica il prodotto scalare e, dato un vettore x d dimensionale, x^* indica il vettore i cui elementi x^*_j sono ottenuti come

Quindi, ad esempio, nel caso in cui x = [x] sia una variabile uni-dimensionale, ossia d = 1, e deg = 4 si ottiene

o, rinominando i parametri,

o in forma vettoriale

Nel caso in cui x = [x₁, x₂] sia una variabile bi-dimensionale, ossia d = 2, e deg = 4 si ottiene

o, rinominando i parametri,

o in forma vettoriale

con

e

Si noti che ci sono termini omessi, perchè generano termini accorpabili a quelli espressi, si consideri ad esempio il caso h = 3, si avrebbe

e quindi

semplificabile come

e θ_1,1,2 + θ_2,1,1 + θ_1,2,1 è di fatto un unico parametro così come θ_1,2,2 + θ_2,1,2 + θ_2,2,1.

Il problema da risolvere è quindi specificato dalla Definizione 1.

Definizione 1 Dato un data set D = [x, y] e un grado deg , trovare i parametri Θ della funzione f(x, Θ) specificata dall’Equazione 1 per cui sia minimizzato l’errore quadratico medio calcolato come:

Discesa Stocastica del Gradiente

La discesa stocastica del gradiente è un metodo iterativo che, ad ogni iterazione, sostituisce il valore esatto del gradiente della funzione costo con una stima ottenuta valutando il gradiente solo su un sottinsieme degli addendi. È ampiamente usato per l’allenamento di una varietà di modelli di apprendimento automatico, come macchine a vettori di supporto, regressione logistica e modelli grafici. Più in detttaglio, l’algoritmo stima i parametri Θ che minimizzano una funzione di costo C(Θ, x, y), aggiornando iterativamente Θ e, in particolare, Θ_t+1 viene ottenuto sottraendo a Θ_t il gradiente della funzione di costo C calcolato rispetto a Θ, dove Θ_t indica il valore dei parametri all’interazione t. In formula:

Nel caso particolare di funzione di costo pari all’errore quadratico medio,

Lo pseudo codice relativo all’algoritmo, considerando regressione polinomiale ed errore quadratico medio come funzione di costo, è descritto dalla funzione SGD, la variante utilizzante un batch di k campioni è descritto dalla funzione SGDBATCH e la variante utilizzante l’algoritmo AdaGrad come acceleratore è descritto dalla funzione AdaGrad.

Descrizione dell’attività progettuale

Obiettivo del progetto è mettere a punto un’implementazione dell’algoritmo di Regressione Polinomiale in linguaggio C e di migliorarne le prestazioni utilizzando le tecniche di ottimizzazione basate sull’organizzazione ell’hardware. L’ambiente sw/hw di riferimento è costituito dal linguaggio di programmazione C (gcc), dal linguaggio assembly x86-32+SSE e dalla sua estensione x86-32+AVX (nasm) e dal sistema operativo Linux (ubuntu).

In particolare il codice deve consentire di trovare i parametri relativi alla regressione polinomiale in un insieme di osservazioni dato in input con l’algoritmo SGDBATCH (parametro -batch ), con eventuale accelerazione AdaGrad, dato il grado del polinomio (parametro -degree ), il valore di η (parametro -eta ) e la specifica adagrad (parametro -adagrad). Quindi la chiamata avrà la seguente struttura:

si noti che il parametro adagrad è opzionale e la sua presenza indica che l’algoritmo deve prevedere l’accelerazione AdaGrad. Qualora un valore di un parametro (sia esso di default o specificato dall’utente) non sia applicabile, il codice deve segnalarlo con un messaggio e terminare.

• Sono richieste due soluzioni software, la prima per l’architettura x86-32 SSE e la seconda per l’architettura x86-64+AVX.

• È inoltre richiesta per ogni soluzione, una versione che faccia uso delle istruzioni OpenMP. I nomi dei relativi file dovranno contenere il suffisso “_omp” (es. regression32 omp.c).