Appunti Architettura ed Elaboratori

M:

riga rispetto all’indirizzo iniziale

.BSS

M: .DSB R*C*L

.DATA

O: .DCW 0, C*L, 2*C*L, …, (R-1)*C*L

Mentre i puntatori dell’array P sono da 4 byte, gli offset

di O possono spesso essere da 2 o da 1 byte;

Un unico array O di offset può essere utilizzato per

tutte le matrici dello stesso tipo (stesso numero di righe

e di colonne e stessa lunghezza degli elementi). © 2016

Architettura degli Elaboratori

Accesso con array ausiliario di offset - 2 13

Usando l’array O di offset, con L=2, i in R1 e j in R2, il trasferimento

si può ottenere così:

R0 M[i,j]

®

W i*2 (offset di O[i] in O)

ASLL 1, R1 ; 30

O[i]®R1 (offset della riga i-esima)

MOVW O(R1), R1 ; j*2 (offset nella riga i-esima)

ASLL 1, R2 ; O[i]+(j*2) (offset di M[i,j])

ADDL R2, R1 ; di M[i,j]]

R0

MOVW R0, M(R1) ; ®W[M+offset

W

Disponendo in un indirizzamento con reg. base e reg. indice:

i*2 (offset di O[i] in O)

ASLL 1, R1 ; O[i]®R1 (offset della riga i-esima)

MOVW O(R1), R1 ; j*2 (offset nella riga i-esima)

ASLL 1, R2 ; R0

MOVW R0, M(R1, R2) ; ®W[M+R1+R2]

W

Il metodo può essere esteso al caso di una matrice Z di N dimensioni

(con N indici x , x , …, x ), usando N-1 array ausiliari (uno per ciascuno

1 2 N

dei primi N-1 indici): gli elementi dell’array ausiliario associato

all’indice x (con K=1..N-1) forniscono gli offset delle sottomatrici di

K

N-K dimensioni (con indici x , x , ..., x ).

K+1 K+2 N © 2016

Architettura degli Elaboratori

Liste LIFO (stack) 14

Definizionedi un’ area di

memoria di 4KB riservata ad

uno stack: 30

STL = 4096 Stack

.DSB STL Pointer

ST: .DSB 1 Indirizzi

Inizializzazione dello stack crescenti

R7:

pointer Organizzazione di uno stack

MOVL #ST, R7

Operazione push di un

elemento lungo un word (R0 ):

W

MOVW R0, -(R7)

Operazione pop:

MOVW (R7)+, R1 © 2016

Architettura degli Elaboratori

Liste FIFO (coda) - 1 15

Una lista FIFO è in genere costituita da una struttura

buffer circolare:

di dati che prende il nome di 30

POUT OUT

PIN IN

Organizzazione di un buffer circolare © 2016

Architettura degli Elaboratori

Liste FIFO (coda) - 2 16

Nel PD32 le direttive per definire un buffer circolare

sono indicate nel seguente esempio: 30

L = 1 ; lunghezza di un elemento

QL = 100 ; numero di elementi

.BSS

QUE: DSB (QL-1)*L

LAST: DSB L

.DATA

PIN: .DCL QUE ; puntatore inserzione

POUT: .DCL QUE ; puntatore estrazione

Agli indirizzi PIN e POUT, sono mantenuti i

puntatori usati per l’inserzione (IN) e per ~ ~

l’estrazione (OUT). PIN IN

Inizialmente (coda vuota) essi puntano OUT

entrambi al primo elemento della lista. POUT © 2016

Architettura degli Elaboratori

Inserzione di un elemento nel buffer circolare 17

Inserzione di un elemento (il byte R0 )

B

; puntatore per l’inserzione

MOVL PIN, R1 30

; inserzione

MOVB R0, (R1)+ ; aggiornamento del puntatore

MOVL R1, PIN bit

; R1-(LAST+L)® di condizione

CMPL #LAST+L, R1 ; se C=0, R1 < LAST+L (R1 LAST)

JNC OK ≤

; (nella sottrazione, C=0 se

; c’è un “prestito”)

; altrimenti R1 LAST+L

MOVL #QUE, PIN ≥

; (R1 > LAST)

OK: …… © 2016

Architettura degli Elaboratori

Estrazione di un elemento dal buffer circolare 18

Estrazione di un elemento (nel byte R0 )

B

; puntatore per l’estrazione

MOVL POUT, R1 30

; estrazione

MOVB (R1)+, R0 ; aggiornamento del puntatore

MOVL R1, POUT bit

; R1-(LAST+L)® di condizione

CMPL #LAST+L, R1 ; se C=0, R1 < LAST+L (R1 LAST)

JNC OK1 ≤

; (nella sottrazione, C=0 se

; c’è un “prestito”)

; altrimenti R1 LAST+L

MOVL #QUE, POUT ≥

; (R1 > LAST)

OK1: …… © 2016

Architettura degli Elaboratori

Buffer circolare: offset anziché puntatori - 1 19

Il ripristino del valore iniziale dei puntatori,

LAST, si ottiene in modo

quando questi superano 30

più agile se l’estensione del buffer è pari ad una

q

potenza intera di 2 (2 ). puntatori, si possono

In tal caso, al posto dei

offset

usare gli relativi all’inizio del buffer,

q

2 .

incrementati modulo

Quest’ultima operazione può essere effettuata

q bit meno significativi del

considerando solo i

valore incrementato, che si possono isolare

q

AND con il valore 2 - 1.

eseguendo un © 2016

Architettura degli Elaboratori

Buffer circolare: offset anziché puntatori - 2 20

Esempio: 30

Definizione di un buffer circolare, avente una

8 =256 byte:

estensione di 2

.BSS

BQUE: .DSB 256

.DATA offset

XIN: .DCB 0 ; iniziale di inserzione

offset

XOUT: .DCB 0 ; iniziale di estrazione

© 2016

Architettura degli Elaboratori

Buffer circolare: offset anziché puntatori - 3 21

Inserzione di un elemento (il byte R0 )

B 30

offset

MOVB XIN, R1 ; per l’inserzione

ANDL #$FF, R1 ; azzera i 3 MSBy

MOVB R0, BQUE(R1) ; inserzione offset

ADDL #1, R1 ; incremento dell’ offset

MOVB R1, XIN ; aggiornamento dell’

; (estrae da R1 solo il LSBy)

© 2016

Architettura degli Elaboratori

Buffer circolare: offset anziché puntatori - 4 22

Estrazione di un elemento (nel byte R0 )

B 30

offset

MOVB XOUT, R1 ; per l’estrazione

ANDL #$FF, R1 ; azzera i 3 MSBy

MOVB BQUE(R1), R0 ; estrazione offset

ADDL #1, R1 ; incremento dell’ offset

MOVB R1, XOUT ; aggiornamento dell’

; (estrae da R1 solo il LSBy)

© 2016

Architettura degli Elaboratori

Buffer circolare pieno/vuoto 23

Le operazioni vanno precedute dalla verifica che il buffer

non sia già pieno o, rispettivamente, vuoto. 30

Quando il buffer è pieno si ha XIN = XOUT

(XIN, fatto il “giro” raggiunge XOUT dopo aver occupato l’ultimo

elemento libero del buffer).

Ma …

Anche quando il buffer è vuoto si ha XIN = XOUT

(XOUT, fatto il “giro” raggiunge XIN dopo aver estratto l’ultimo

elemento presente nel buffer).

La condizione XIN = XOUT non consente di distinguere

i due casi.

Conviene considerare pieno il buffer circolare

Þ quando c’è un solo elemento libero. © 2016

Architettura degli Elaboratori

Buffer circolare: verifica se pieno 24

Inserzione di un elemento (il byte R0 )

B 30

offset

MOVB XIN, R1 ; per l’inserzione

ANDL #$FF, R1 ; azzera i 3 MSBy

MOVB R0, BQUE(R1) ; elemento inserito comunque

offset

ADDL #1, R1 ; incremento dell’

CMPB XOUT, R1 ; se era l’ultimo libero …

JZ PIENA ; … allora la coda è piena:

; XIN non viene aggiornato!

MOVB R1, XIN ; aggiornamento di XIN

. . . ; inserzione avvenuta

PIENA: . . . ; inserzione non avvenuta © 2016

Architettura degli Elaboratori

Buffer circolare: verifica se vuoto 25

Estrazione di un elemento (nel byte R0 )

B 30

offset

MOVB XOUT, R1 ; per l’estrazione

ANDL #$FF, R1 ; azzera i 3 MSBy

CMPB XIN, R1 ; XIN=XOUT?

JZ VUOTA ; si: la coda è vuota,

; non si estrae

MOVB BQUE(R1), R0 ; estrazione offset

ADDL #1, R1 ; incremento dell’

MOVB R1, XOUT ; aggiornamento di XOUT

. . . ; estrazione avvenuta

VUOTA: . . . ; estrazione non avvenuta © 2016

Architettura degli Elaboratori

Liste concatenate 26

30

• Ad ogni elemento di una lista concatenata (linked list) è

puntatore che individua l’elemento successivo.

associato un

• Gli elementi contengono un campo puntatore (4 byte) e

possono trovarsi ovunque in memoria.

Nel PD32 le direttive con cui definire una lista

- concatenata (inizialmente vuota) sono:

NIL = -1

HEAD: .DCL NIL

Se R1 punta a un elemento, con l’istruzione:

- MOVL (R1), R1

R1 punta all’elemento successivo (e si percorre la lista).

© 2016

Architettura degli Elaboratori

Liste concatenate: inserzione 27

Esempio:

inserzione, a fine lista, di un elemento (puntato da R0) 30

; puntatore iniziale

MOVL #HEAD, R1 ; campo indirizzo

CERCA: MOVL (R1), R2 ; è l’ultimo elemento?

CMPL #NIL, R2 ; si, è l’ultimo

JZ ULTIMO ; elemento successivo

MOVL R2, R1

JMP CERCA ; aggancio

ULTIMO: MOVL R0, (R1) ; l’elemento inserito è

MOVL #NIL, (R0) ; ora l’ultimo © 2016

Architettura degli Elaboratori

Liste concatenate: estrazione 28

Esempio:

estrazione del primo elemento (puntatore in R0) 30

MOVL #HEAD, R1 ; puntatore iniziale

MOVL (R1), R0 ; puntatore all’elemento

; da estrarre

CMPL #NIL, R0 ; lista vuota?

JZ VUOTA ; si, non estrae

MOVL (R0), (R1) ; estrazione: il campo

; puntatore dell’elemento

; estratto viene ricopiato

; in L[HEAD]

VUOTA: …… …… © 2016

Architettura degli Elaboratori

Liste concatenate: esercizi proposti 29

Gli esempi visti (inserzione alla fine, estrazione

dalla testa) corrispondono ad usare la lista con 30

modalità FIFO (coda);

Si propongono altri esercizi:

1. inserzione e estrazione usando la lista con modalità

LIFO (entrambe dalla testa);

2. inserzione di un dato in una lista ordinata (va prima

individuato il punto in cui effettuare l’inserzione);

3. ricerca di un dato in una lista ordinata;

4. estrazione di un elemento da una lista ordinata, se

.

presente © 2016

Architettura degli Elaboratori

Alberi 30

Ciascun elemento della struttura comprende una lista di

puntatori ad altri elementi della struttura. 30

Gli elementi terminali hanno NIL nei campi puntatore.

Nel caso dell’albero binario: © 2016

Architettura degli Elaboratori Fine

04.a Le Strutture di dati

Introduzione ad ARM

e al processore S3C2440

03.a C. Fantozzi, A. Gardich

(revisione di S. Congiu, M.Moro)

Che cosa è ARM? 1

ARM = Advanced RISC Machine 46

ARM Ltd non produce microprocessori:

progetta e vende proprietà intellettuale

ARM è una architettura:

insieme dei registri e delle istruzioni disponibili

▪ modi d’indirizzamento

▪ gestione delle interruzioni

▪

Esistono molte versioni dell’architettura,

e molti processori per versione © 2016

Architettura degli Elaboratori

ARM nella vita quotidiana: esempi 2

SAMSUNG Galaxy S6 [Cortex A53+Cortex A57]

iPHONE 6 [Cortex A72 (A8)+Cortex M3 (M8)] 46

Nintendo 3DS (ARM11 quadcore)

Molte calcolatrici e palmari ... © 2016