Calcolatori Elettronici II - Tesina

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

<h2>Variabile a 64 bit</h2>
<p>Un possibile esempio di codice potrebbe essere il seguente.</p>

<h3>Figura 1 - Addizione in C</h3>
<pre>
<code>
// Codice in linguaggio C
int64_t add(int64_t a, int64_t b) {
    return a + b;
}
</code>
</pre>

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

<h3>Figura 2 - Addizione tradotta per ARM 5</h3>
<pre>
<code>
// Codice in linguaggio assembler per ARM 5
add:
    push {r4, lr}
    add r4, r0, r1
    mov r0, r4
    pop {r4, pc}
</code>
</pre>

<p>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.</p>

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

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

<h3>Figura 3 - Codice add.s</h3>
<pre>
<code>
// Codice ottimizzato in linguaggio assembler per ARM 5
add.s:
    adds r0, r0, r1
    bx lr
</code>
</pre>

<p>I parametri che vengono letti dalla funzione sono 3 valori la cui struttura è riportata nella...</p>

La seguente immagine: Figura 4 - 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 5 - 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 6 - 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.

inoutput 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.

{0x7D, 0x0}125 + 200 = 325(0x145)

{0xC8, 0x0}10505929831125 + {0x1A3732D5, 0x98E}5245747688 =10511175578813

{0x38ABC1E8, 0x1}(0x 98F52E2F4BD)

{0xFFFFFFFF, 0x0}4294967295 + 1 = 4294967296(0x100000000)

{0x1, 0x0}

Tabella 1 - Casi di test per l'addizione

73. 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 7 - 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 delle operazioni di somma e sottrazione è, in linea di principio, pressoché identico. Per completezza si riportano anche gli altri file che sono stati utilizzati dalla sottrazione.

Figura 8 - 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 9 - Codice subtest.c 8

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 effettuata usando la

notazione decimale, nella seconda colonna sono stati riportati gli output inseriti e nella terza il risultato ottenuto.

{0xC8, 0x0}200 - 125 = 75(0x4B)

{0x7D, 0x0}10505929831125 - {0x1A3732D5, 0x98E}5245747688 =10500684083437

{0x38ABC1E8, 0x1}(0x 98CE18B70ED)

{0x0, 0x1}4294967296 – 1 = 4294967295(0xFFFFFFFF)

{0x1, 0x0}Tabella 2 - Casi di test per la sottrazione 94.

MoltiplicazionePer quanto riguarda la moltiplicazione si è deciso di provare un algoritmo che riuscisse adottimizzare le prestazioni. A tal proposito prima di mostrare il codice assembler dell’ARM relativoalla moltiplicazione si propone l’algoritmo utilizzato: al fine di snellire la notazione è stato riportatoun esempio su due registri da 4 bit che effettuano la moltiplicazione e pongono il loro risultato in unregistro da 8, che ovviamente rappresenta un registro di dimensione doppia rispetto a quelli dipartenza.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 10 - 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 11 - Codice mul.s

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

Figura 12 - 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 13 -

all'interno delle variabilidi appoggio v1, v2, v3, v4 mentre il risultato con rispettivamente parte bassa e parte alta verrà postoin 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 questaoperazione è lecita, ovvero se il dividendo >= divisore. Ogni qual volta che si effettua taleoperazione, 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 perunsigned. 13Per completezza riportiamo anche gli altri file che sono stati utilizzati per fare in modo chel'algoritmo funzionasse correttamente.

Figura 15 - 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 16 - Codice divtest.c

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

{0xC8, 0x0}200 / 100 = 2500(0x2)

{0x64, 0x0}55272978900481 / {0x3E45E601, 0x3245}9607805441 = 5752

{0x3CAB7A01, 0x2}(0x1678)

{0x0, 0x1}4294967296 / 1 = 4294967296(0x100000000)

{0x1, 0x0}{0xC8, 0x0}200 / 65535 = 0(0x0)

{0xFFFF, 0x0}

Tabella 4 - Casi di test per la divisione 14