tesina

Operazioni aritmetiche a 64bit per ARM

1. Specifiche di progetto

Il progetto che si intende realizzare consiste nella creazione di una libreria matematica per il processore ARM che implementi le 4 operazioni matematiche fondamentali (addizione, sottrazione, moltiplicazione, divisione) su 64 bit invece che su 32 bit.

Tramite l'utilizzo della suite ARM 202U sarà possibile creare un main program scritto in linguaggio C che richiami la libreria creata in ARM ed effettui le operazioni suddette.

La motivazione per cui si è scelto questo tipo di soluzione è intuitivo: si cerca di effettuare delle ottimizzazioni al livello di codice assembler che altrimenti non sarebbero possibili servendosi unicamente del linguaggio di alto livello.

Si intende infatti sfruttare tutti i vantaggi che un linguaggio di basso livello riesce a fornire al fine di rendere più efficienti le operazioni.

2. Addizione

Qualora realizzassimo in C un programma che effettua l'addizione di due interi e pone il risultato in una variabile a 64 bit, un possibile esempio di codice potrebbe essere il seguente.

Figura - Addizione in C

Questo tipo di codice, qualora decidessimo di tradurlo in linguaggio assembler per l'ARM produrrebbe il seguente risultato:

Figura - Addizione tradotta per ARM

Analizzando nel dettaglio il codice, già è possibile intuitivamente dedurre che tale codice potrebbe essere eccessivo per effettuare questo tipo di operazione: è immediato ad esempio verificare che alla riga 21 utilizza lo stack per il salvataggio di registri che potevano essere anche non utilizzati; eliminando questa operazione si sarebbe risparmiato del tempo.

Infine, usando il flag relativo al carry, si potrebbe risparmiare molto codice e quindi molte operazioni.

Utilizzando tutte le considerazioni appena introdotte possiamo riscrivere il codice dell'addizione come segue:

Figura - Codice add.s

I parametri che vengono letti dalla funzione sono 3 valori la cui struttura è riportata nella seguente immagine:

Figura - Codice add64.h

Come è possibile osservare il contenuto di a1 rappresenta il parametro in cui viene inserito il risultato, mentre a2 ed a3 sono i parametri che vengono utilizzati per passare i due valori che devono essere sommati.

Non esistendo variabili a 64 bit, è stato necessario creare una struttura che contenesse due interi che rappresentassero rispettivamente la parte alta e la parte bassa del risultato, come mostrato dalla seguente immagine:

Figura - Codice int64.h

Al fine di testare la validità del codice appena scritto, si è prodotto un main, scritto in C, per testare dati determinati input, i valori generati dalla funzione ARM appena scritta.

A tal proposito si riporta il codice scritto:

Figura - Codice addtest.c

Tramite l'uso dei parametri a e b è possibile specificare rispettivamente, prima la parte bassa e poi la parte alta del numero che si intende sommare. Il risultato viene poi posto in c e visualizzato in output sul monitor.

Di seguito sono riportati alcuni casi di test, che hanno verificato la validità del codice prodotto: nella prima colonna è inserita l'addizione effettuata usando la notazione decimale, nella seconda colonna sono stati riportati gli output inseriti e nella terza il risultato ottenuto.

Tabella - Casi di test per l'addizione

3. Sottrazione

Tutte le considerazioni appena svolte per l'addizione sono perfettamente valide anche per la sottrazione e per brevità non verranno riportate.

A tal proposito si riporta il codice di sub.s che è identico a quello dell'addizione fatta eccezioni per di due sole operazioni che, ovviamente, invece di sommare i valori li sottraggono.

Figura - Codice sub.s

Come accennato in precedenza le operazioni che sono state sostituite sono ADDS che ha lasciato spazio a SUBS e ADC che ha lasciato spazio a SBC. Il comportamento di delle operazioni si somma e sottrazione è, in linea di principio, pressoché identico.

Per completezza si riportano anche gli altri file che sono stati utilizzati dalla sottrazione.

Figura - Codice sub64.h

Il codice di int64.h corrisponde perfettamente con quello riportato in Figura 5. Mentre il codice per testare la sottrazione a 64 bit è riportato di seguito:

Figura - Codice subtest.c

Come nel caso dell'addizione, tramite l'uso dei parametri a e b è possibile specificare rispettivamente, prima la parte bassa e poi la parte alta del numero che si intende sottrarre. Il risultato viene poi posto in c e visualizzato in output sul monitor.

Di seguito sono riportati alcuni casi di test, che hanno verificato la validità del codice prodotto: nella prima colonna è inserita la sottrazione effetuata usando la notazione decimale, nella seconda colonna sono stati riportati gli output inseriti e nella terza il risultato ottenuto.

Tabella - Casi di test per la sottrazione

4. Moltiplicazione

Per quanto riguarda la moltiplicazione si è deciso di provare un algoritmo che riuscisse ad ottimizzare le prestazioni. A tal proposito prima di mostrare il codice assembler dell'ARM relativo alla moltiplicazione si propone l'algoritmo utilizzato: al fine di snellire la notazione è stato riportato un esempio su due registri da 4 bit che effettuano la moltiplicazione e pongono il loro risultato in un registro da 8, che ovviamente rappresenta un registro di dimensione doppia rispetto a quelli di partenza.

Se, come sarà evidente, si nota che le operazioni che si introducono all'interno del seguente algoritmo producono lo stesso risultato di quella che di avrebbe utilizzando il metodo classico per svolgere la moltiplicazione, allora l'algoritmo realizzato risulta corretto.

Figura - Algoritmo della moltiplicazione (11*15=165)

Come è possibile notare, si estraggono 4 numeri contenuti in registri da 4 bit ciascuno che rappresentano la somma delle quantità evidenziate in figura. Una volta che queste 4 quantità sono state estratte si effettuano una serie di operazioni di manipolazione al fine di produrre un risultato analogo a quello che si avrebbe se si effettuassero le operazioni tipiche di una moltiplicazione classica.

Innanzitutto si addizionano i due blocchi centrali ed un eventuale riporto viene sommato nella parte alta del risultato; successivamente, la parte appena sommata, viene scissa in due parti per consentire una agile addizione con la parte bassa e la parte alta del risultato finale: in particolare, viene prima sommata una parte con la parte bassa in modo tale che un eventuale carry possa essere sommato all'interno della parte alta. Alla fine il risultato viene posto nelle variabili di destinazione.

L'algoritmo appena descritto è riportato all'interno del seguente codice:

Figura - Codice mul.s

Per completezza è importante riportare anche gli altri file che sono stati creati per consentire all'algoritmo di funzionare correttamente.

Figura - Codice mul64.h

In questo caso è stata utilizzata la parola chiave __value_in_regs per consentire al programma di inserire all'interno della variabile a1 ed a2 la parte bassa e la parte alta del risultato inserito all'interno del parametro di ritorno della funzione. Per quanto riguarda int64.h, ancora una volta questo file è identico a quello riportato in Figura 5.

Infine, si intende riportare il codice che è stato utilizzato per testare il corretto funzionamento del programma realizzato:

Figura - Codice multest.c

A tal proposito si riportano all'interno della tabella seguente, i risultati ottenuti nei casi di test, che hanno verificato il corretto funzionamento dell'algoritmo.

La seguente tabella è stata organizzata come segue: nella prima colonna è stata riportata la moltiplicazione che è stata effettuata, nella colonna centrale gli operandi, mentre nella colonna finale il risultato prodotto dall'applicazione realizzata.

Tabella - Casi di test per la moltiplicazione

5. La divisione

Per quanto riguarda la divisione è stato sviluppato il seguente algoritmo: tale algoritmo risulta essere il classico metodo per risolvere una divisione di interi.

Figura - Codice div.s

L'algoritmo funziona in questo modo: innanzitutto si caricano le variabili all'interno delle variabili di appoggio v1, v2, v3, v4 mentre il risultato con rispettivamente parte bassa e parte alta verrà posto in v5 e v6; per poi essere restituito al mail che aveva invocato il metodo.

Il ciclo fondamentale consiste nel sottrarre al dividendo il divisore, se ovviamente questa operazione è lecita, ovvero se il dividendo >= divisore. Ogni qual volta che si effettua tale operazione, il risultato viene incrementato di 1: ovviamente non devono essere entrambi 0, altrimenti l'algoritmo termina.

Trattandosi di interi senza segno, invece di utilizzare le classiche BLT (branch less than) o BGE (branch greater than) è opportuno utilizzare BHI che rappresenta un comando specifico per unsigned.

Per completezza riportiamo anche gli altri file che sono stati utilizzati per fare in modo che l'algoritmo funzionasse correttamente.

Figura - Codice div64.h

Il codice relativo al file int64.h è, ancora una volta, del tutto simile a quello riportato in Figura 5. Mentre, per quanto concerne il file che è stato utilizzato per testare l'applicazione, è riportato nella seguente figura.

Figura - Codice divtest.c

A tal proposito si riportano alcuni casi di test creati per verificare la correttezza del codice scritto:

Tabella - Casi di test per la divisione

6. Creazione di una libreria

Al fine di creare un'unica libreria è necessario compattare il codice che è stato creato per ogni operazione matematica. Innanzitutto, possiamo importare all'interno del nostro progetto il file int64.h che rimarrà, ovviamente, invariato.

Risulta adesso necessario creare un nuovo file chiamato ad esempio lib64.h organizzato come segue:

Figura - Codice lib64.h

Come è possibile notare, questo file contiene tutti quante le funzioni che è possibile richiamare all'interno del main.

Una volta creato questo file, è necessario importare all'interno di un unico file, che chiameremo lib.s tutto quanto il codice che è stato creato.

Figura - Codice lib.s

Una volta creato questo tipo di file possiamo creare un main che provi a richiamare una ad una tutte le funzioni che sono state create.

Figura - Codice libtest.c

Questo potrebbe essere un esempio di codice che, in questo caso, produrrebbe il seguente output.

Figura - Risultato prodotto dal main della libreria