Soluzioni - italy-s3-mhe-prod.s3-website-eu-west...

Soluzioni

Questo documento contiene le soluzioni alla quasi totalita degli esercizi proposti nel libroArchitettu-ra e organizzazione dei calcolatori elettronici - Fondamenti, Mc-Graw Hill 2004. Le soluzioni vengonoriportate capitolo per capitolo, mantenendo la numerazione del libro, senza ripetere il testo degli esercizi.

Il lettore si accorgera presto che il modo di esporree alquanto schematico e che in piu passaggil’italiano potrebbe essere migliorato.

Molti degli esercizi proposti sono di carattere progettuale e pertanto viene presentata per essiunasoluzione tra le tante possibili (nonla soluzione). Non escludo che un lettore attento possa identificaresoluzioni migliori. Quel lettoree invitato a comunicarmele, in modo da arricchire questo documen-to a vantaggio dei lettori futuri. Anche chi formulasse migliori algoritmi riguardanti gli esercizi sullaprogrammazione assemblere invitato a comunicarmeli.

Ho fatto il possibile per rendere lo scritto privo di errori, ma so che questoe un obiettivo (quasi) ir-raggiungibile. Saro grato a coloro che mi segnaleranno errori di qualunque genere. Naturalmente saroaltrettanto e piu grato a chi mi segnalera errori nel volume sopra menzionato.

Prego di inviare le segnalazioni a questo indirizzo:[email protected]

Giacomo Bucci

Aggiornato al 4 maggio 2007

1

Attenzione! C’ e un errore malizioso

L’inchiostro della stampa non aveva finito di asciugarsi quando sie scoperto che a pagina 214 del testosi nasconde un errore capace di portare fuori strada. Trattandosi di un errore piuttosto rilevante abbiamodeciso di darne avviso anche in questo documento.

La sequenza corretta di passi per l’esecuzione dell’istruzioneST V[Rb],RA e questa:

T1: RBout, TIinT2: 016||IR[15:0]out, ADD, TOin

T3: TOout, MARin

T4: RAout, SELDTRdir, DTRin

T5: SELDTRdir, DTRout, MWRT6: SELDTRdir, DTRout, MWR

Conseguentemente la sequenza completa (fetch-esecuzione)e questa:

T1: PCout, MARin, SEL4, ADD, TOin

T2: MRD, TOout, PCin

T3: MRD, DTRin

T4: DTRout, IRin

T5: RBout, TIinT6: 016||IR[15:0]out, ADD, TOin

T7: TOout, MARin

T8: RAout, SELDTRdir, DTRin

T9: SELDTRdir, DTRout, MWRT10: SELDTRdir, DTRout, MWR

A pagina 217 il periodo:

T4 da tutte le istruzioni e su T8 e T9 dall’istruzioneST. Dunque il comando DTRout puo essere espressocome:

DTRout = T4 + (T8+T9)·ST

si trasforma nel seguente:

T4 da tutte le istruzioni e su T9 e T10 dall’istruzioneST. Dunque il comando DTRout puo essere espressocome:

DTRout = T4 + (T9+T10)·ST

Naturalmente sono stati trovati altri errori e refusi nel testo. Si suggerisce vivamente di esaminarel’Errata corrige sul sito.

2

1

Esercizio 1.3

Dal 1985 ad oggi (2004) ci sono 19 anni. Al tasso di crescita del 60% all’anno avremmo avuto crescitapari a(1, 6)19 ∼= 7556.Conviene ragionare in millisecondi: 1,5 min= 1,5× 60× 1000= 90000 ms. Ne consegue che oggioccorrerebbero

900007556

∼= 11, 9ms

Sessanta giri in meno di un secondo: un po’ difficile per lo spettatore seguire lo svolgersi della corsa!

Esercizio 1.4

Cogliamo l’occasione per risolvere anche l’Esercizio 1.2.Dal 1991 ad oggi (2004) ci sono 13 anni. Essendo, per ipotesi, pari a 1 le prestazioni nel 91, al tasso dicrescita del 60% all’anno avremmo prestazioni pari a(1, 6)13 = 450, 4.Se la crescita fosse stata solo tecnologica le prestazioni sarebbero pari a(1, 44)13 = 114, 5.Se la crescita fosse stata solo architetturale le prestazioni sarebbero pari a(1, 16)13 = 6, 9.

Esercizio 1.5

Il lasso di tempoe pari a2004 − 1995 = 9 anni. Le prestazioni della CPU sarebbero cresciute di(1, 6)9 = 68, 72 volte; quelle della memoria di(1, 07)9 = 1, 84. Dunque le prestazioni complessivesarebbero cresciute di un fattore pari a

0, 5× 68, 72 + 0, 5× 1, 84 = 35, 28

Con un impatto della CPUe pari al 30% le prestazioni complessive sarebbero cresciute di un fattore paria

0, 3× 68, 72 + 0, 7× 1, 84 = 21, 90

Esercizio 1.6

Dal 1998 al 2004 ci sono 6 anni. In 6 anni la crescita delle prestazioni della CPU sarebbe pari a(1, 6)6 =16, 78. Le prestazioni della memoria sarebbero cresciute di(1, 07)6 = 1, 50 volte.

Se le prestazioni del sistema nel suo complesso fossero cresciute come quelle della CPU, esse sa-rebbero pari a 1678. Se fossero cresciute come quelle della memoria sarebbero pari a 150.Poiche la crescitae stata di 3 volte, si deduce che la CPU ha contribuito solo per un 10% al migliora-mento delle prestazioni. Si deve concludere che il nostro produttore fabbrica sistemi mal bilanciati e chela sua produzione non tiene dietro allo sviluppo tecnologico.

2

Esercizio 2.1

La conversione da base decimale a binaria di un numero intero si ottiene per successive divisioni per 2(Paragrafo 2.2.1). La successione dei resti rappresenta, dalla cifra meno significativa alla piu significati-va, il numero binario.

Mostriamo il processo di conversione in riferimento al numero14310. La successione di quozienti eresti ottenuti dividendo per 2e:

(71,1), (35,1), (17,1), (8,1), (4,0), (2,0), (1,0), (0,1)

dunque:14310 = 100011112.Applicando lo stesso procedimento si ottiene:31210 = 1001110002 ; 9110 = 10110112

Per quanto si riferisce ai numeri frazionari si tratta di applicare la tecnica del Paragrafo 2.5. Consideran-do, ad esempio, il numero 0,7155 e limitandoci alle prime otto cifre significative si ha:

0, 7155× 2 = 1, 4310, 431× 2 = 0, 8620, 862× 2 = 1, 7240, 724× 2 = 1, 4480, 448× 2 = 0, 8960, 896× 2 = 1, 7920, 792× 2 = 1, 5840, 584× 2 = 1, 168

Dunque0, 715510 = 0, 101101112

Per i numeri in virgola si applicano ambedue le regole. Considerando il numero 11,77, relativamente a11 si ha questa successione di quozienti e resti ottenuti dividendo per 2:

(5,1), (2,1), (1,0), (0,1)

dunque:1110 = 10112 mentre per la parte frazionaria (fermandosi alla sesta cifra decimale) si ha:

0, 77× 2 = 1, 540, 54× 2 = 1, 080, 08× 2 = 0, 160, 16× 2 = 0, 320, 32× 2 = 0, 640, 64× 2 = 1, 28

(2.1)

dunque0, 7710 = 0, 1100012. In conclusione11, 77 = 1011, 1100012.

Esercizio 2.2

Per la conversione da binario a decimale si calcola il polinomio delle potenze di 2 i cui coefficientisono dati dalla stringa binaria di partenza (Paragrafo 2.2.1). Pertanto al numero10112 corrisponde ilpolinomio:

1× 23 + 0× 22 + 1× 21 + 1× 20 = 1110

In modo del tutto analogo si ottiene:10001112 = 7110 e10100012 = 8110

Esercizio 2.3

La conversione da una generica base alla base decimale si ottiene col metodo del calcolo del polinomiodi potenze della base di partenza.

Al numero1AB016 corrisponde il polinomio:

1× 163 + A× 162 + B × 161 + 0× 160 = 1× 163 + 10× 162 + 11× 161 + 0× 160 = 683210

Esercizio 2.4

Per la conversione del numero760228 si ha:

7× 84 + 6× 83 + 0× 82 + 2× 81 + 2× 80 = 3176210

Esercizio 2.5

La conversione dalla base decimale ad una base generica si ottiene per successive divisioni del numeroda convertire per la base di arrivo. Per il numero350010 si ottiene:

3500: 1612 218: 16

10 13

Tenuto conto che1210 = C16, 1010 = A16, 1310 = D16, ne consegue:

350010 = DAC16

La conversione a base 8 si ottiene in modo del tutto analogo:

3500: 84 437: 8

5 54: 86 6

Dunque350010 = 66548.

Analogamente si ottiene:53110 = 21316; 53110 = 10238

Esercizio 2.6

La conversione tra basi che sono potenze l’una dell’altra si ottiene raggruppando opportunamente le cifredel numero espresso nella base piu piccola (Paragrafo 2.2.2). Dunque basta convertire prima il numerodato nella base piu piccola e poi effettuare le altre conversioni. Ad esempio:

D1516 = 1101 0001 01012 = 110 100 010 101 = 64258

= 1 10 11 10 10 00 00 01 = 3101114

In maniera analoga:

672018 = 110 111 010 000 0012 = 1 10 11 10 10 00 00 01 = 123220014

= 110 1110 1000 0001 = 6E8116

4

Esercizio 2.7

La conversione tra basi che non comprendono la base decimale ne siano tra loro potenze l’una dell’altra,richiede il passaggio dalla base di partenza alla base decimale calcolando il polinomio corrispondente edalla base decimale alla base di arrivo utilizzando le successive divisioni.

Per la converversione di201102 da base 3 a base 16 si ha:

2011023 = 2× 35 + 0× 34 + 1× 33 + 1× 32 + 0× 31 + 2× 30 = 52410

Segue:

524: 16C 32: 16

0 2

In conclusione:2011023 = 20C16

Per la conversione di 3201 da base 4 a base 7 si ha:

3× 43 + 2× 42 + 0× 41 + 1 ∗ 40 = (225)10

e quindi:

225: 71 32: 7

4 4

Dunque:

32014 = (441)7

Per le altre conversioni si ha:3034 = 1236; 7549 = 26816

Esercizio 2.8

Il numero 9e una potenza del 3; dunque il passaggio tra le due basi si ottiene raggruppando opportuna-mente le cifre (come nel passaggio tra la base 2 e la base 4). A tal fine si faccia riferimento alla Tabella2.1.

827049 = 22 02 21 00 113 = 22022100113

2112002123 = 2 11 20 02 123 = 246259

Esercizio 2.9

Nell’illustrazione che segue viene calcolato il risultato della prima somma binaria (si indica il riportosolo see 1):

1 1 1 Riporti1 1 0 0 1 0 1 + Primo addendo1 0 0 1 1 0 1 = Secondo addendo

1 0 1 1 0 0 1 0 Risultato

Mancano moltiplicazioni e divisioniDunque11001012 + 10011012 = 101100102 In modo analogo si ha:0112 + 1002 = 1112

Per quanto riguarda le sottrazioni binarie si ha invece (si indica il prestito solo see 1):

1 Prestiti1 0 1 1 0 + Minuendo0 0 1 1 1 = Sottraendo0 1 1 1 1 Risultato

Dunque101102 − 001112 = 011112 Analogamente:1112 − 0112 = 1002

5

Esercizio 2.10

L’operazione di somma si esegue cifra per cifra come se fosse in base dieci; al risultato si toglie ilnumero degli elementi della base in cui sono espressi i numeri da sommare. Cio che si ottienee unrisultato parziale della somma richiesta. Si procede cosı fino al termine tenendo conto dei riporti dellesomme parziali precedenti. Per la somma 202+101 in base 3 si ha:

1 Riporti2 0 2 + Primo addendo1 0 1 = Secondo addendo

1 0 1 0 Risultato

Per la differenza 257-167 in base 8 si ha:

1 Prestiti2 5 7 − Minuendo1 6 7 = Sottraendo0 7 0 Risultato

Naturalmente il modo meno soggetto a errore per eseguire operazioni aritmetiche fra numeri espressiin una base diversa da quella decimale, si convertono i numeri nella base dieci, si esegue l’operazione inquesta base e si converte poi il risultato nella base di partenza.

Essendo4125 = 10710 e1015 = 2610 ed essendo10710×2610 = 278210; poiche278210 = 421125

ne consegue4125 × 1015 = 421125

Analogamente:54206 = 123610 e 46 = 410; 123610 : 410 = 30910; poiche 30910 = 12336 neconsegue54206 : 46 = 12336

Esercizio 2.11

Scegliamo di effettuare l’operazione richiesta in base ottale, per cui, si ha:

A0E316 = 10100000111000112 = 1203438

ovvero1203438 − 67558 = 1113668 = 3762210

Verifica:A0E316 = A× 163 + 0× 162 + E × 161 + 3× 160 = 4118710

67558 = 6× 83 + 7× 82 + 5× 81 + 5× 80 = 356510

Quindi41187− 3565 = 37622

Esercizio 2.14

Considerando quanto detto al Paragrafo 2.7 si ha:14, 310 = 1110, 010011001100110011002 = 1, 11001001100110011001100× 10011,

Quindi la trasformazione richiestae:Segno=0;Mantissa=11001001100110011001100Esponente=10000010

Esercizio 2.16

Ponendo la sequenza in ordine testuale e rappresentandola a byte si ha:

4C 31 6A 79 33 37

Dalla tabella di codifica ASCII si ottiene la stringa

L 1 y 3 7

6

Esercizio 2.17

Mostriamo la soluzione in forma del tutto generale. Si assume che la stringa di caratteri ASCII sia memo-rizzata nel vettore V di dimensioni pari alla lunghezza della stringa. Si assuma inoltre che tutti i carattericontenuti in V siano effettivamente caratteri corrispondenti ai 10 digit decimali (0,1,...9). L’algoritmo diconversione della stringa in rappresentazione binaria puo essere schematizzato come:

Z ← 0for i = 1 to nZ ← Z × 10 + num(V [i])

dovenum(c)e la funzione che trasforma la codifica ASCII di un carattere numerico nel corrispondentevalore. In pratica si tratta di sottrarre dalla codifica ASCII del carattere il numero esadecimale 30 corri-spondente alla codifica di ”0”. Nel caso specifico la stringa ”2836”e codificata in memoria con questasequenza esadecimale: 32 38 33 36.

Esercizio 2.18

Numero Codifica BCD79 0111 100148 0100 1000

Tabella 2.1 Codifica BCD dei numeri in Esercizio: i singoli raggruppamenti di quattro bit del codice BCDcostituiscono la codifica binaria delle cifre decimali.

Se si effettua la somma tra la rappresentazione binaria di due digit BCD si hanno tre possibilirisultati:

• la sommae minore di 9: il risultatoe gia codificato in BCD (es.:3 + 2 = 5);• la somma eccede 9 ma non da riporto: occorre ricodificare il risultato in BCD aggiungendo 6. Da

questa situazione puo risultare un riporto per la cifra di sinistra (es.:9+2 = 11 ovvero1001b+0010b =1011 + 0110 → 1 0001);

• la somma eccede 9 e da riporto (es.:9 + 8 = 17); anche in questo caso occorre ricodificare il risultatoaggiungendo 6.

L’esecuzione della somma procede da destra verso sinistra. Nel caso specifico si ha:

• 9 + 8 = 17 ovvero1001b + 1000b = 10001b che ricodificato in BCD (sommando 6)e 0001 0111.Dunque la cifra a destra della sommae 7 con riporto 1.

• 7 + 4 + 1 = 11 ovvero0111b + 0100b + 0001b = 1100b che ricodificato in BCD (sommando 6)e 0001 0010. Dunque la somma di 7 con 4 e col riporto della cifra a destrae 2 con riporto di 1. Inconclusione il risultatoe 127.

In Tabella 2.2 viene mostrato il processo relativo a questa somma. In Figura 2.1 lo schema a blocchidell’algoritmo di somma di due cifre BCD.

0 1 1 1 1 0 0 10 1 0 0 1 0 0 0

1 1 0 0 1 0 0 0 1 (il riporto su questa riga si somma a sinistra)0 1 1 0 0 1 1 0

1 0 0 1 0 0 1 1 1

1 2 7

Tabella 2.2 Somma BCD di 79 con 48 attraverso una somma binaria e normalizzazione.

7

Figura 2.1 Algoritmo per la somma di due cifre BCD attraverso un sommatore binario di 4 bit. Il blocco“somma 6” normalizza la rappresentazione binaria a rappresentazione BCD.

8

3

Esercizio 3.1

X Y Z XY Z X Y XY Z + X Y0 0 0 0 1 10 0 1 0 1 10 1 0 0 0 00 1 1 0 0 01 0 0 0 0 01 0 1 0 0 01 1 0 0 0 01 1 1 1 0 1

Tabella 3.1 Tabella di verita funzione (a), Esercizio 3.1.

A A B C A + C A B A B(A + C)0 1 1 0 0 1 00 1 1 1 1 1 10 1 0 0 0 0 00 1 0 1 1 0 01 0 1 0 1 0 01 0 1 1 1 0 01 0 0 0 1 0 01 0 0 1 1 0 0

Tabella 3.2 Tabella di verita funzione (b), Esercizio 3.1. Sono state riportate le variabili nella forma concui entrano nell’espressione.

Esercizio 3.2

L’espressioneX + X Y + XZ si semplifica applicando al proprieta di assorbimento.

X + X Y + XZ = X(1 + Z) + X Y = X + X Y == X + X Y = (X + X)(X + Y ) == 1(X + Y ) = X + Y

L’espressioneA(B C + B + C) si semplifica applicando la proprieta di assorbimento e successiva-mente la proprieta distributiva.

A(B + C) = AB + AC

L’espressioneA B(A + C)(B + C) si semplifica nel modo seguente

A B(A + C)(B + C) = (A BA + ABC)(B + C) = A BC(B + C) = ABC

Esercizio 3.3

La rete corrispondente alla funzione (a)e mostrata a sinistra in Figura 3.1, mentre la semplificazioneea destra. Equivalentemente la rete corrispondente alla funzione (b)e mostrata a sinistra in Figura 3.2,mentre la semplificazione a destra.

Figura 3.1 Rete originale e semplificata del punto (a) dell’ Esercizio 3.3.

Figura 3.2 Rete originale e semplificata del punto (b) dell’ Esercizio 3.3.

Esercizio 3.4

Si vuole arrivare a scrivere l’uguaglianza di De Morgan nella forma:

x1 + x2 + . . . + xn = x1 · x2 · . . . · xn

Postox2 + x3 + . . . + xn = X, sostituendo nella precedente e applicando il teorema di De Morgan perdue variabili si ha:

x1 + x2 + . . . + xn = x1 + X = x1 ·X = x1 · (x2 + . . . + xn).

Applicando iterativamente la semplificazione si ottiene l’uguaglianza richiesta.

Esercizio 3.7

Si faccia riferimento alla prima forma canonica. Data la generica funzionef(x1, x2, . . . , xn) e semprepossibile riportarla alla forma canonica:

• Sef(x1, x2, . . . , xn) contiene generici termini di somme e prodotti,e sempre possibile riportaref aduna somma di prodotti svolgendo le operazioni algebriche (i prodotti) inf .

• Quandof e in forma di somma di prodottie sempre possibile riportare i singoli prodotti a mintermini,moltiplicandoli con termini in forma(xi +xi), xi essendo una variabile che non compare nel prodotto.

10

Esempio: sia dataf(x1, x2, . . . , xn) = x1 · (x2 + x3) + x2x3.

x1 · (x2 + x3) + x2x3 = x1x2 + x1x3 + x1x3 · (x2 + x2) == x1x2 · (x3 + x3) + x1x3 · (x2 + x2) + x1x2x3 + x1x2 x3 == x1x2x3 + x1x2x3 + x1x2x3 + x1x2x3 + x1x2x3 + x1x2 x3 == x1x2x3 + x1x2x3 + x1x2x3 + x1x2 x3.

Esercizio 3.8

La funzione di uscita della rete puo essere scritta comef = wxy + wxy + wxy. Questa si semplificanel modo che segue.

f = wxy + wxy + wxy = wxy + wxy + wxy + wxy = xy + wx = x(w + y)

Esercizio 3.9

L’espressione diz si ricava direttamente dalla specifica prendendo la parola “allora” come OR e la parola“quando” come AND.

z = (x + y)c1 + xyc2 + xyc3

Con le mappe si puo verificare che questae l’espressione minima (occorre tenere conto delle condizionidi indifferenza).

Esercizio 3.10

(x + y)(x + y) = xx + xy + xy + yy = x + x(y + y) + 0 = x + x = x

Esercizio 3.11

• Per la funzione (a) si ha:F = (x + yz)(wx + z)(y + z) = wy + wz + xzy + xz + xwz + xywz + yz.

x y y w z wy wz xzy xz xywz yz F0 0 1 0 0 0 0 0 0 0 0 00 0 1 0 1 0 0 0 0 0 1 10 0 1 1 0 0 0 0 0 0 0 00 0 1 1 1 0 1 0 0 0 1 10 1 0 0 0 0 0 0 0 0 0 00 1 0 0 1 0 0 0 0 0 0 00 1 0 1 0 1 0 0 0 0 0 10 1 0 1 1 1 1 0 0 0 0 11 0 1 0 0 0 0 0 0 0 0 01 0 1 0 1 0 0 0 1 0 1 11 0 1 1 0 0 0 0 0 0 0 01 0 1 1 1 0 1 0 1 1 1 11 1 0 0 0 0 0 0 0 0 0 01 1 0 0 1 0 0 1 1 0 0 11 1 0 1 0 1 0 0 0 0 0 11 1 0 1 1 1 1 1 1 0 0 1

Tabella 3.3 Tabella di verita della funzione (a) dell’Esercizio 3.11.

La mappa di Fe in Figura 3.3. La copertura di F fornisce l’espressione minima:F = yz +yw +wz +xz.

• Per la funzione (b) si ha:F = xy(x + w(yz + yz)) = (x + y)(x + w(yz + y + z)) = (x + y)(x +wyz + wy + wz) = xywz + xwy + xwz + xy + wz + y + ywz = wz + y + xy + xwz.Riportando F sulla mappa e coprendo come in Figura 3.4 si ottiene la funzioneF = y + x + wz.

11

Figura 3.3 Mappa della funzione (a) dell’ Esercizio 3.11.

x x y y w w z z wz xy xwz F0 1 0 1 0 1 0 1 0 0 0 10 1 0 1 0 1 1 0 0 0 0 10 1 0 1 1 0 0 1 0 0 1 10 1 0 1 1 0 1 0 1 0 0 10 1 1 0 0 1 0 1 0 1 0 10 1 1 0 0 1 1 0 0 1 0 10 1 1 0 1 0 0 1 0 1 1 10 1 1 0 1 0 1 0 1 1 0 11 0 0 1 0 1 0 1 0 0 0 11 0 0 1 0 1 1 0 0 0 0 11 0 0 1 1 0 0 1 0 0 0 11 0 0 1 1 0 1 0 1 0 0 11 0 1 0 0 1 0 1 0 0 0 01 0 1 0 0 1 1 0 0 0 0 01 0 1 0 1 0 0 1 0 0 0 01 0 1 0 1 0 1 0 1 0 0 1

Tabella 3.4 Tabella di verita della funzione (b) dell’Esercizio 3.11.

Figura 3.4 Mappa di della funzione (b) dell’ Esercizio 3.11.

• Per la funzione (c) si ha:F = wxyz(x+(wx+ z)y + z(x+ y)) = wxyz(x+(wxy + z y)+ zx+ zy)= wxyz(x + wxy + z y + zx + zy) = wxyz(x) = wxyz.Non e quindi necessario procedere alla creazione della tabella di verita e della mappa in quanto lafunzionee gia ridotta al minimo.

• Per la funzione (d) si ha:F = (w + x + y + z)(y + zx) = wy + wzx + xy + zx + xyz + zy + x =x + zy + wy. E’ facile verificare che l’espressione none ulteriormente semplificabile. Del resto peressa vale la tabella di verita di Tabella 3.5 e la mappa di Karnaugh di Figura 3.5 dalla quale si ottieneF = x + zy + wy.

12

x y y w z zy wy F0 0 1 0 0 0 0 00 0 1 0 1 1 0 10 0 1 1 0 0 1 10 0 1 1 1 1 1 10 1 0 0 0 0 0 00 1 0 0 1 0 0 00 1 0 1 0 0 0 00 1 0 1 1 0 0 01 0 1 0 0 0 0 11 0 1 0 1 1 0 11 0 1 1 0 0 1 11 0 1 1 1 1 1 11 1 0 0 0 0 0 11 1 0 0 1 0 0 11 1 0 1 0 0 0 11 1 0 1 1 0 0 1

Tabella 3.5 Tabella di verita della funzione (d) dell’Esercizio 3.11.

Figura 3.5 Mappa della funzione (d) dell’Esercizio 3.11.

Esercizio 3.12

Prima di tutto si riportano le espressioni in forma SP.y = x1x2(x1x3 + x2x3x4 + x2x4) + x3x4(x1 + x2 + x3) =

= x1x2x1x3 + x1x2x2x3x4 + x1x2x2x4 + x3x4x1 + x3x4x2 + x3x4x3 == 0 + x1x2x3x4 + 0 + x3x4x1 + x3x4x2 + 0 == x1x2x3x4 + x1x3x4 + x2x3x4

d = x1x4(x2x3 + x2x3) + x1x2x3x4 = x1x2x3x4 + x1x2x3x4 + x1x2x3x4

Si disegna quindi la mappa, riportando gli 1 della funzione e le condizioni di indifferenza. Con lacopertura di Figura 3.6 si ottienef = x2x4 + x1x3x4

Esercizio 3.13

In un decodificatore BCD si hanno 6 condizioni di indifferenza, come si puo notare dalla Tabella delparagrafo 3.4.3 del testo. Si tratta quindi di coprire le caselle della mappa che in Figura 3.13 sonocondizioni di indifferenza. E’ facile verificare che si ottiene:Z = AB + AC = A(B + C) dove Ze ilsegnale che indica la presenza di codice non BCD. La Figura 3.7 mostra la rete conseguente.

13

Figura 3.6 Mappa per l’Esercizio 3.12.

Figura 3.7 Rete dell’Esercizio 3.13.

Esercizio 3.14

La dimostrazione puo essere fatta nel seguente modo:

x1 ⊕ (x2 ⊕ x3) = x1(x2 ⊕ x3) + x1(x2 ⊕ x3)= x1(x2x3 + x3x2) + x1(x2x3 + x3x2)= x1(x2x3 x3x2) + x1 x2x3 + x1x2x3

= x1(x2 + x3)(x3 + x2) + x1 x2x3 + x1x2x3

= x1(x2x3 + x2 x3) + x1 x2x3 + x1x2x3

= x1x2x3 + x1x2 x3 + x1 x2x3 + x1x2x3

Mentre:(x1 ⊕ x2)⊕ x3 = (x1 ⊕ x2)x3 + x3(x1 ⊕ x2)

= (x1x2 + x1x2)x3 + x3(x2x1 + x1x2)= x1x2 x3 + x1x2x3 + x3(x1x2 x2x1)= x1x2 x3 + x1x2x3 + x3(x1 + x2)(x2 + x1)= x1x2 x3 + x1x2x3 + x3(x1x2 + x1 x3)= x1x2 x3 + x1x2x3 + x1x2x3 + x1 x2x3

Dunquex1 ⊕ (x2 ⊕ x3) = (x1 ⊕ x2) ⊕ x3, e pertanto vale la proprieta associativa. Ne conseguex1 ⊕ (x2 ⊕ x3) = (x1 ⊕ x2)⊕ x3 = x1 ⊕ x2 ⊕ x3.

14

Esercizio 3.15

Data l’espressionex1 + x2 · (x3 + x4 · (x5 + x6 · (. . .))) complementando due volte e applicando ilteorema di De Morgan si ha:

x1 + x2 · (x3 + x4 · (x5 + x6 · (. . .))) = x1 + x2 · (x3 + x4 · (x5 + x6)) =

= x1 · x2 · (x3 + x4 · (x5 + x6)) =

= x1 | x2 · (x3 + x4 · (x5 + x6)) == x1 | (x2 | (x3 + x4 · (x5 + x6))) =

= x1 | (x2 | (x3 + x4 · (x5 + x6))) =

= x1 | (x2 | x3 · (x4 · (x5 + x6))) =

= x1 | (x2 | x3 | (x4 · (x5 + x6))) == x1 | (x2 | x3 | x4 | (x5 + x6)) == x1 | (x2 | x3 | x4 | x5 | x6).

La regolae che una rete di SPSPSP... si trasforma in una rete di soli NAND sostituendo tutte le portedella rete data con porte NAND e complementando gli ingressi di ordine dispari nell’espressione (ilprimo termine della SPSPSP... ha indice 1). Si veda la Figura 3.8. In modo analogo si prova che le retiPSPSPS... si trasformano in reti di soli NOR.

Figura 3.8 A sinistra e mostrata la rete originaria dell’Esercizio 3.15, mentre a destra la suatrasformazione in sole porte NAND.

Esercizio 3.16

La trasformazione si ottiene con la “tecnica dei pallini” del paragrafo 3.5.3 del testo. A partire dalla reteoriginale di Figura 3.9 si introducono i pallini di negazione come a sinistra di Figura 3.10. Cio richiedel’introduzione dei negatori degli ingressi A, B, C, D, E. La rete a sinistra di Figura 3.9 si ridisegna comea destra, usando l’usuale simbolo del NAND. In altre parole si tratta di sostituire tutte le porte con porteNAND e di negare gli ingressi di livello dispari (si confronti con l’Esercizio 3.15).

La Figura 3.11 mostra a sinistra l’applicazione dei pallini e a destra la rete risultate in forma di soliNOR.

Esercizio 3.17

L’aggiunta sull’uscita di una porta AND (OR) in una rete SP (PS) trasforma la rete SP (PS) in una PSP(SPS). Le reti SPS si trasformano in reti di NAND e le reti PSP in reti di NOR. Si veda l’Esercizio 3.15.

15

Figura 3.9 Rete originale Esercizio 3.16.

Figura 3.10 Successione dei passaggi per arrivare alla rete equivalente in forma di sole porte NAND.

Figura 3.11 Successione dei passaggi per arrivare alla rete equivalente in forma di sole porte NOR.

16

Esercizio 3.18

Applicando il teorema di De Morgan si ottiene che la rete a destra in Figura 3.20 del testo rappresenta la

funzione logica:F (A,B) = AB AB.

AB AB = (A + B)(A + B)= AA + AB + A B + BB

= AB + A B= (A + B)(A + B)= AB + BA= A⊕B.

Esercizio 3.19

Prima di tutto si riporta la funzione alla forma canonica attraverso espansioni e successive semplificazio-ni. Si ottiene:A = xyz + xyz + xyz + xyz, ovverof(x, y, z) =

∑(4, 5, 6, 7). Dunque le linee 4, 5, 6,

7 del mux vengono fissate a 1 mentre le rimanenti vengono impostate a 0, come in Figura 3.12.


Esercizio 3.20

Anzitutto occorre dare la forma canonica delle due funzioni di uscita.A = xy + x yz = xyz + xyz + x yz =

∑(1, 6, 7)

B = x + xy + z = = xy + x y + xyz + xyz + xz + xz= xyz + xyz + x yz + x y z + xyz + xyz + xyz + xyzx xz= x yz + x y z + xyz + xyz + xyz + xyz + xyz

1 0 2 3 5 6 7=

∑(0, 1, 2, 3, 5, 6, 7).

Le due espressioni permettono di fissare i collegamenti interni della PROM di Figura 3.13, (in essail collegamentoe rappresentato da una× cerchiata).

Esercizio 3.21

Il dispositivo SN7485 puo essere utilizzato come decodificatore attraverso l’impostazione fissa di oppor-tuni ponticelli. Il numero 240h corrisponde al numero 0010 0100 0000b. Con la realizzazione di Figura3.14, i contatori chiusi impostano lo zero quelli aperti l’uno.

17

Figura 3.13 PROM 8x2 che realizza le funzioni A = xy + yxz e B = x + xy + z.


Esercizio 3.22

Il numero esadecimale 240 corrisponde in binario al numero 0010 0100 0000.Assumendo pari a 4 il fan-in delle porte AND si puo predisporre una rete di decodifica per ogni

parola di 4 bit. L’uscita Z viene abilitata solo se gli ingressi corrispondono alla codifica binaria di 240.La retee mostrata in Figura 3.15.

18

Figura 3.15 Rete di decodifica indirizzo 240h. Esercizio 3.22.

Esercizio 3.23

Con riferimento alla Figura 3.48 del testo, si indichino conτR e conτS i tempi di commutazione che lacella FA richiede per calcolare rispettivamente il riporto e la somma. In una somma din bit il riportodeve propagarsi attraverson celle. Dunque i tempi di commutazione sono pari a4R = nτR per il riportoRn−1 e pari a4S = (n−1)τR+τS per la somma. Poiche per il full adder si haτR = 3τ eτS = 2τ , doveτ e il ritardo di commutazione della singola porta logica, si ottiene:4S = 3τ(n− 1)+2τ = (3n− 1)τ .

Esercizio 3.24

Il look-ahead carry generator in Figura 3.50 ha in totale 29 porte:

8 XOR14 NAND4 OR3 NOT

Esercizio 3.25

Il sommatore a 64 bite composto da:

• 16 full adder a quattro bit conτR = 3τ• 4 look-ahead carry generator 1 livello con τR = τ• 1 look-ahead carry generator 2 livello con τR = τ

Poiche con il look-ahead carry generator non si deve attendere la propagazione del riporto ne deriva che4R = 3τ + τ + τ = 5τ . Per quanto si riferisce alla somma si ha4S = 6τ , in quanto si deve tener contodi un ulteriore tempoτ di commutazione della porta XOR.

Esercizio 3.26

Con riferimento alla Figura 3.58 del testo si osservi chec3 = 1 comportaRi = 0. Cio rende rende0 le uscite delle tre porte AND a due ingressi nella parte a destra. Ne consegue che l’unico contributodiverso da zero, come ingresso alla porta che restituisceSi, puo essere fornito solo dalla porta AND a tre

19

ingressi. PoicheRi−1 = 1 la porta in questione ha in ingressoAi Bi della stessa Figura. Adesso, poichec1 = 1 l’ingressoAi di Figura 3.58 corrisponde adAi di Figura 3.56, mentre l’ingressoBi corrisponde,sempre in Figura 3.56 e 3.57, all’ingressoBi. In conclusione, con riferimento alla schematizzazionedi Figura 3.57, la configurazione di controlloc3c2c1c0Ri−1 = 1 − 111 fa generare alla ALU l’uscitaS = AB.

20

4

Esercizio 4.1

La rete di Figura 4.1 del testoe un latch realizzato con porte NOR. Sostituendo le porte NOR con porteNAND si ottiene la rete di Figura 4.1.


Nella Tabella 4.1 si puo analizzare il comportamento del dispositivo in funzione degli ingressi. Sievidenzia che, nel caso di ingresso 00, la rete sequenziale ha le uscite Z non determinate.

S R A Z1 1 q q1 0 q 00 1 q 10 0 - -

Tabella 4.1 Comportamento del latch in funzione degli ingressi.

Esercizio 4.2

Seguendo la “tecnica dei pallini”, dalla Figura 4.1 del testo, riportata a sinistra in Figura 4.2, si ottiene illatch a destra. Successivamente, si esegue la sostituzione con porte NAND, ottenendo il latch a sinistradi Figura 4.3, la cui realizzazione in logica negativae mostrata a destra. Rispetto al precedente latch diNOR la differenza che intercorre tra i duee la stessa che esiste tra la logica positiva e negativa; ovverole reti hanno lo stesso funzionamento a patto di considerare gli 0 come 1 e viceversa. (Si veda anchel’Esercizio 4.1)

Figura 4.2 Latch di soli NOR di Figura 4.1 del testo e sua trasformazione in rete di NAND.

Figura 4.3 Latch di soli NAND in logica positiva, a sinistra, e in logica negativa, a destra.

Esercizio 4.4

In Figura 4.4 viene presentato lo schema generale di soluzione del problema. Si tratta di definire la retecombinatoria che nel caso (a) ha come ingressi S, R e y, e la cui uscita T ha l’effetto di far commutareil flip flip in modo che appaia come un SR. Questo schema, mutatis mutandis, si usa per qualunquetrasformazione tra diversi tipi di flip flop.

Figura 4.4 Schematizzazione del problema della creazione di un FFSR sfruttando un FFT. Lo schemae valido anche nel caso generale.

Il problema del caso (a)e schematizzato in Figura 4.4. In Tabella 4.2 sono mostrati gli ingressirichiesti per le possibili transizioni dei due tipi di FF.

La mappa di y’ in funzione di S, R e ye mostrata a sinistra in Figura 4.5, applicando il procedimentodescritto al paragrafo A.5 del testo, dalla mappa di y’ si passa alla mappa di T, che assume la forma adestra in Figura 4.5, la cui copertura porta alla seguente espressione per T:

T = Sy + Ry

22

y → y’ S R T0→ 0 0 - 00→ 1 1 0 11→ 0 0 1 11→ 1 - 0 0

Tabella 4.2 Transizioni di stato e corrispondenti ingressi per i Flip Flop SR e T.

La rete corrispondentee riportata in Figura 4.6.

Figura 4.5 Mappe Esercizio 4.4a.

Figura 4.6 Rete Esercizio 4.4a.

Il punto (b) chiede di ricavare un FFSR da un FFD e un FFJK da un FFD. In Tabella 4.3 sonomostrate le 3 tabelle di transizione per i FF usati. Mentre in Figura 4.7 le mappe relative alle transizioni.

y → y’ S R J K D0→ 0 - - 0 0 00→ 1 1 0 1 0 11→ 0 0 1 0 1 01→ 1 - 0 0 0 1

Tabella 4.3 Transizioni di stato e corrispondenti ingressi per i FFSR, FFJK e FFD

Poiche per un FFD vale l’equazione di statoy′ = D, si tratta semplicemente di imporreD = S+Ryper il caso della trasformazione FFSR→ FFD eD = Jy + Ky per la trasformazione FFJK→ FFD. Sitrovano cosı le reti mostrate rispettivamente a sinistra e destra in Figura 4.8.

23

Figura 4.7 Mappa Esercizio 4.4b (FFSR e FFJK da FFD).

Figura 4.8 Reti che realizzano, a sinistra un FFSR a partire da un FFD, mentre a destra un FFJK da unFFD.

Per quanto ci si riferisce alla costruzione di un FFD da un FFT, si riportano in Tabella 4.4 letransizioni di stato e in Figura 4.9 le mappe di T corrispondenti. In Figura 4.10 la rete risultante.

y → y’ T D0→ 0 0 00→ 1 1 11→ 0 1 01→ 1 0 1

Tabella 4.4 Transizioni di stato e corrispondenti ingressi per i FFT e FFD

Figura 4.9 Mappa Esercizio 4.4c (FFD da FFT). T = y ⊕D.

24

Figura 4.10 Rete che realizza un FFD da un FFT.

Esercizio 4.5

Il valore F0h corrisponde a 1111 0000b. Qualunque sia il tipo di FF utilizzato per realizzare il registro, sitratta di legare PR e CL a massa o a Vcc in modo da portare i singoli FF al valore richiesto all’atto dellamessa sotto tensione (Figura 4.11). La rete a destra di Figura 4.11 genera il segnale Clear/Set quandoviene asserito R. Si noti la presenza di un inverterSchmitt triggered, per generare un’onda il piu possibilequadra.

Figura 4.11 A sinistra i collegamenti necessari per il caricamento in presenza di un segnale di Clear/Set;a destra la rete che genera il segnale Clear/Set.

Esercizio 4.6

La rete che deve essere progettata, ha un unico ingresso (x) e una sola uscita (z) che al 5 clock presentala parita, mentre sui precedenti presentax. In Figura 4.12e mostrato lo schema in questione.

Figura 4.12 Schema per l’ Esercizio 4.6.

In Figura 4.13 c’e il diagramma di transizione degli stati. La notazione usata per etichettare gli archi

25

e quella relativa al modello di Mealy. La colonna a sinistra (senza apici) individua un numero pari di 1,quella a destra un numero dispari. Supponendo di seguire lo schema a “parita pari”, sul 5 clock si haz=0 se sie nello stato 4, altrimentiz=1 se sie nello stato 4’, (indipendentemente dax).

Figura 4.13 Diagramma degli stati per l’Esercizio 4.6.

Si puo ora ricavare la tabella di flusso e delle transizioni di stato (Tabella 4.5).

SP x z0 1,0 1’,11 2,0 2’,12 3,0 3’,13 4,0 4’,14 0,0 0,01’ 2’,0 2,12’ 3’,0 3,13’ 4’,0 4,14’ 0,1 0,1

Tabella 4.5 Tabella di flusso corrispondente al diagramma di stato di Figura 4.13

Codificando gli stati come sotto si ottengono le mappe in Figura 4.14.0:00001:0001 1’:10012:0010 2’:10103:0011 3’:10114:0100 4’:1100

Si noti che questa none la codifica piu conveniente in termini di minimizzazione della rete, maequella piu naturale (rende comprensibile lo stato). Dalle mappe si ricavano le seguenti funzioni di statoe uscita, dalle quali puo essere dedotto lo schema della rete.

y′0 = y1(y0 ⊕ x)y′1 = y2(y3 + y0)y′2 = y0y3 + y0y1 y2

y′3 = y3(y0y2 + y0y2) + y0 y1 y2 y3

z = y0y1y2 y3 x + x(y0 + y1).

26

Figura 4.14 Mappe che rappresentano la Tabella 4.5 secondo la codifica indicata.Esercizio 4.6.

Soluzione alternativa

Possiamo scomporre il problema in modo da avere

• Un contatore che fornisce il segnalec sul 5 clock• Una rete che calcolap (parita)• Una rete che presenta suz il segnalex sui clock da 0 a 3, ep clock 4.

Ne deriva lo schema di Figura 4.15.

Figura 4.15 Schema riassuntivo della soluzione alternativa all’ Esercizio 4.6.

Il generatore di parita di Figura 4.15 ha il diagramma di stato di Figura 4.16. Il diagramma rap-presenta una macchina di Mealy. In ingresso c’e la coppiax, c. L’ ingressoc e dato dall’uscita di unsemplice contatore modulo 5. Dalla copertura della mappa si ricava:

p = yx + yc + yxc

La rete che realizza il generatore di parita e in Figura 4.17.

27

Figura 4.16 A sinistra e mostrato il diagramma di stato del generatore di parita dell’Esercizio 4.6, sugliarchi viene riportato xc/p . A destra la mappa relativa.

Figura 4.17 Generatore di parita dell’ Esercizio 4.6 risultante dalla soluzione alternativa.

28

Esercizio 4.7

La sequenza riconosciutae 10011.Z1=1 solo dopo il fronte di clock che ha fatto caricare nel registroquesta configurazione (il quinto fronte). Con riferimento alla notazione di Figura 4.18, se i FF commu-tano sul fronte di salita (a sinistra in Figura),Z e 1 durante il41 del clock che ha caricato 10011 mentrese i flip flop commutano sul fronte di discesa (a destra in Figura),Z e 1 durante42 del medesimo clock.

Figura 4.18 Tempi di commutazione per i FF dell’Esercizio 4.7.

Esercizio 4.8

Il diagramma della macchina che riconosce la sequenza 10011e rappresentato in Figura 4.19. Essendo5 gli stati da codificare, ci servono 3 bit. Ad esempio si puo utilizzare la seguente codifica:

A 000B 001C 011D 010E 100

dalla quale deriva la Tabella delle transizioni 4.6.Notare che la rete riconosce le finestre, ma in modo non sovrapposto. A titolo di esempio si mostra

l’uscita in riferimento a un flusso di dati in ingresso:

x 1 0 0 1 1 0 0 1 1 0 0 1 1z 0 0 0 0 1 0 0 0 0 0 0 0 1

Figura 4.19 Diagramma di stato del riconoscitore della sequenza 10011, riconosciuta in ordine dasinistra a destra. Esercizio 4.8.

Le corrispondenti mappe sono mostrate nella Figura 4.20, la cui copertura porta alle funzioni a destranella stessa Figura. La retee realizzata in Figura 4.21.

Per analizzare quale delle due soluzioni sia la migliore in termini di porte e FF basta semplicementecontare. La Figura 4.60 del testo risolve il problema con uno shift register, che sara composto da 5 FF, 2

29

y1 y2 y3 x y′1 y′2 y′3 z0 0 0 1 0 0 1 00 0 0 0 0 0 0 00 0 1 1 0 0 1 00 0 1 0 0 1 0 00 1 1 1 0 0 1 00 1 1 0 0 1 0 00 1 0 1 1 0 0 00 1 0 0 0 0 0 01 0 0 1 0 0 0 11 0 0 0 0 1 1 0

Tabella 4.6 Tabella delle transizioni del riconoscitore della sequenza 10011, Esercizio 4.8.

y′1 = y2y3xy′2 = y3x + y1xy′3 = y3x + y1xz = y1x

Figura 4.20 Mappe e funzioni relative alla Tabella di transizione 4.6 dell’Esercizio 4.8.

Figura 4.21 Rete logica che riconosce la sequenza 10011. Esercizio 4.8.

porte NOT e 2 porte AND. La soluzione presentata in Figura 4.21 utilizza 1 porta NOT, 5 porte AND, 2porte OR e 3 FF. Dire quale delle due soluzioni sia la miglioree difficile.

Un’ analisi di questo tipo ha pero poco senso, in quanto va visto come i componenti vengano residisponibili sul mercato. Si hanno allora delle sorprese. Per costruire lo shift register a 5 bit di Figura 4.60occorre utilizzare il componente SN74198, un 8 bit Universale Bidirezionale Shift Register, a 28 piedini

30

mentre per le altre 4 porte si puo utilizzare, facendo qualche trasformazione, il componente SN7400,costituito da 4 porte NAND a 2 ingressi, con un totale di 14 piedini. Con 2 componenti si risolve ilcircuito. Per la rete in Figura 4.21 servono 2 componenti SN7474, ognuno dei qualie composto da 2FFD Positive Edge Triggered a 14 piedini, e per le porte, basta utilizzare 2 integrati SN7400, specificatisopra (cio presuppone pero una strutturazione della rete in forma di soli NAND).

Nel primo caso sie quindi utilizzato 2 componenti integrati con un totale di 42 piedini di collega-mento, mentre nel secondo caso sono serviti 4 integrati per un totale di 56 piedini collegati. Specifichesugli integrati, specificatamente sulla serie SN74xx si trovano su:http://www.rodaronline.com/ci/ci2.htm .

Esercizio 4.9

La rete di Figura 4.61e un contatore modulo 3 realizzato con FFJK. Tenuto conto del funzionamento delFFJK (Tabella 4.7), il comportamento della rete, a partire dallo stato 00e quello di Tabella 4.8.

J K y′

0 0 y0 1 01 0 11 1 y

Tabella 4.7 Modalita di funzionamento del flip flop JK.

Clock n y0 y1 y′0 y′10 00 011 01 102 10 00

Tabella 4.8 Funzionamento del contatore di Figura 4.61. Con y0 e y1 si indicano rispettivamente l’uscitadel FF di sinistra e di destra di Figura 4.61.

Esercizio 4.10

Utilizzando per gli stati A,B,C la seguente codifica: A 00, B 01 e C 10, si ottiene la tabella delletransizioni mostrata in Figura 4.22.

Figura 4.22 Tabella delle transizioni Esercizio 4.10.

Alla tabella delle transizioni corrispondono le mappe a destra di Figura 4.23 dalle quali si ricavanole funzioni a sinistra della stessa Figura. Infine la realizzazione della retee mostrata in Figura 4.24.

31

y′0 = y0x + y1xy′1 = y0 y1 xz = y0

Figura 4.23 Mappe e funzioni della Tabella 4.22 dell’Esercizio 4.10.

Figura 4.24 Rete logica dell’ Esercizio 4.10.

Esercizio 4.11

Cominciamo con la realizzazione tramite FFJK. Per semplicita consideriamo il cason = 2. Si tratta dicollegare i flip flop in modo tale che ciascun FF divida la frequenza del clock per 2 e di usare lo stato delFF come clock per il successivo. Con FFJK cio si ottiene come in Figura 4.25. Ovviamente sen > 2 sitratta di aggiungere il corrispondente numero di FF.

Nel caso di flip flop D, la divisione di frequenza del primo FF (y0) comporta che esso deve cambiarestato ad ogni clock, cio impone che l’ingresso sia il complemento dello stato. Dunque:

D0 = y0

da cui deriva la rete di sinistra in Figura 4.26. Per quanto riguarda il secondo FF, esso si comporteracome il precedente, ma usera come clock il segnaley0. Ne deriva la rete a destra di Figura 4.26.

32

Figura 4.25 Realizzazione del contatore dell’Esercizio 4.11 con FFJK. L’uscita y0 e un segnale periodicocon frequenza pari a meta di quella del clock. Il segnale y1 ha frequenza pari a meta di quella di y0.

Figura 4.26 A sinistra la divisione di frequenza in un FFD; a destra la realizzazione del contatore dell’E-sercizio 4.11 con FFD. L’uscita y0 e un segnale periodico con frequenza pari a meta di quella del clock.Il segnale y1 ha frequenza pari a meta di quella di y0.

Esercizio 4.12

Per progettare un contatore sincrono moduloN 6= 2n conviene partire direttamente dalla tabella di flusso,si tratta di una tabella degenere, in quantoe priva di ingressi. In Figura 4.27 vengono riportati la tabelladi flusso di un generico contatore sincrono moduloN , quella di un contatore modulo5 e la tabella delletransizioni di stato corrispondenti a quest’ultima (avendo codificato gli stati in modo naturale).

Dalla copertura delle mappe a sinistra in Figura 4.28, ricaviamo le funzioni a destra nella stessaFigura. Mentre in Figura 4.29e mostrata la rete che realizza il contatore.

33

Sp Sf0 11 2

. . . . . .N-2 N-1N-1 0

Sp Sf0 11 22 33 44 0

y1y0 y′1y′0000 001001 010010 011011 100100 000

Figura 4.27 Tabella di flusso di un contatore modulo N (a sinistra), tabella di flusso di un contatoremodulo 5 (al centro) e transizione degli statio per quest’ultimo (a destra) .

y′0 = y1y2

y′1 = y2y1 + y1y2

y′2 = y0 y2

Figura 4.28 Mappe e funzioni che realizzano il contatore modulo 5 dell’Esercizio 4.12.

Figura 4.29 Rete che realizza il contatore modulo 5 dell’ Esercizio 4.12.

Esercizio 4.13

Il flip flop T cambia stato quando l’ingresso Te a 1. Dunque, essendo tutti gli ingressi dei flip floppermanentemente a 1 essi sono soggetti a cambiare stato ad ogni clock. Il primo FF commuta in tutti iclock, il secondo essendo collegato all’uscita del primo commuta con frequenza dimezzata, il terzo confrequenza ulteriormente dimezzata. Si veda la Tabella 4.9. Si deduce che quello di Figura 4.62 del testoe un contatore asincrono modulo 8.

34

Clock n y3 y2 y1 y′3 y′2 y′10 111 0001 000 0012 001 0103 010 0114 011 1005 100 1016 101 1107 110 111

Tabella 4.9 Funzionamento della rete di Figura 4.62. In neretto le variabili di stato corrispondenti ai FFche ricevono il clock.

Esercizio 4.14

In Figura 4.30 viene riportato il diagramma di stato in cui gli stati sono gia codificati. Ad esso corrispondela Tabella 4.10 e le mappe di Figura 4.31, dalle quali si ricavano le funzioni a destra nella stessa Figura.Se si impiegano dei FFD queste espressioni corrispondono agli ingressi dei FF. Si ottiene allora la rete inFigura 4.32.

Figura 4.30 Diagramma di stato per l’ Esercizio 4.14. Sui rami sono riportati i valori dell’ingresso. Si notiche il passaggio tra le due modalita di conteggio avveniene solo in corrispondenza dello stato 100.

y0y1y2 x0 1

000 001 001001 010 010010 011 011011 100 100100 101 000101 110 110110 000 000

Tabella 4.10 Tabella transizione stati Esercizio 4.14.

35

y′0 = y1y2 + y0y2 + y0y1 x,y′1 = y0 y1 y2 + y2y1

y′2 = y0 y2 + y1 y2 y.

Figura 4.31 Mappe dell’ Esercizio 4.14, dalla cui copertura si ricavano le funzioni a destra.

Figura 4.32 Rete logica Esercizio 4.14.

Esercizio 4.15

Si faccia riferimento a un contatore sincrono realizzato con FFJK. Indicando cony1 . . . yn le uscite deiFF, il genericoFFi−esimo deve avere un ingresso pari a(y1 · y2 · . . . · yi−1)⊕ yi se conta in salita e pari a(yi+1 · yi+2 · . . . · yn)⊕ yi se conta in discesa. La Figura 4.33 illustra la struttura dell’i-esimo dispositivo.

36

Figura 4.33 FFi−esimo dell’Esercizio 4.15. Il segnale UD imposta la modalita di funzionamento. ConUD=1 conta in avanti mentre con UD=0 il dispositivo conta all’indietro.

Esercizio 4.17

Per risolvere l’Esercizio si possono usare due contatori a caricamento parallelo. Per il numero A possia-mo usare unup-coutere per B possiamo utilizzare undown-counter. Si caricano entrambi i numeri neicontatori e si inizia il conteggio. Quando si attiva il CO di B, in A avremo la somma dei due numeri. COe il segnale che un contatore attiva quando raggiunge il valore massimo, see unup-coutero minimo seeun down-counter, serve a capire se siamo arrivati a fine conteggio. Avendo fatto proseguire il conteggiodi A per B volte abbiamo eseguito la somma dei due numeri. L’unica attenzionee riguardo all’overflow,cioe A+B deve sempre essere inferiore al massimo valore conteggiabile dal contatore A, altrimenti siavrebbe un reset dello stesso e un mal funzionamento della rete. Il collegamento dei due contatorie inFigura 4.34.

Esercizio 4.18

A parte il clock, l’unico segnale di comandoe X. Esso deve servire a comandare il caricamento di RA eRB e ad avviare il conteggio, a cui sara legati il trasferimento del risultato il RC al momento dovuto.

Per quanto si riferisce al caricamento di RA e RB la specifica sottintende che esso deve essere fattoin parallelo. Si deve quindi immaginare l’esistenza di due percorsi che portano in RA e RB i dati dacaricare.Supporremo di effettuare il caricamento dei registri secondo la tecnica (sincrona) rappresentata dalleFigure 4.29 e 4.37 del testo. Facciamo l’ipotesi che il comando di caricamento prevalga sullo scorrimentoin modo che il clock che trova il segnale di caricamento a 1 faccia solo caricare. In conclusione si trattadi generare due opportuni segnali temporali noti, RAeBin e RCin. Il segnale RAeBin puo essere ancheusato per azzerare lo stato del flip flop che memorizza il riporto.

RAeBin deve essere asserito solo sul clock su cui si caricano i registri (clock 0). Poiche nonespecificata la durata di X, occorre generare RAeBin da X. Supponendo che i registri RA e RB operinosul fronte di discesa del clock, conviene che RAeBin duri esattamente un periodo di clock, ma tra i frontidi salita. Dunque RAeBin deve avere la temporizzazione di Figura 4.35. Il segnale viene portato a 1 sulfronte di salita del clock che trova X a 1 e riportato a 0 sul fronte di salita seguente. In tal modo RA e RBvengono caricati sul fronte di discesa intermedio del clock 0. I successivi 5 impulsi di clock determinanoil caricamento in RA dei bit di somma (calcolati via via).

La somma viene percio a trovarsi in RA dal fronte intermedio del clock 5. Se anche RC opera sulfronte di discesa il trasferimento del risultato in questo registro puo essere effettuato sul clock successivo(clock 6), avendo asserito RCin.

37

Figura 4.34 Sommatore A+B. Esercizio 4.17. Si noti che il passaggio a 1 di x fa operare i due contatori.Il passaggio a 1 di CO ferma l’incremento del contatore di sinistra. I valori di A e B devono essereprecaricati nei due contatori prima del passaggio a 1 di x (non mostrato in figura).

Figura 4.35 Temporizzazione dei segnali RAeBin e RC rispetto al clock ed al segnale X. Esercizio 4.18.

38

In conclusione si deve progettare la rete (di Moore, operante sui fronti di salita) che genera i segnalitemporizzati RAeBin e RCin, come in Figura 4.35. La schematizzazione della retee riportata in alto inFigura 4.36.

Figura 4.36 In alto: schema della rete per la generazione dei segnali RAeBin e RCin a partire dalsegnale X e dal clock. In basso: il diagramma di stato della rete. Le uscite sono ordinatamente, RAeBin

e RCin.

Si tratta di un problema analogo a quello della generazione del segnale di WAIT del Paragrafo 4.5.1del testo. Il diagramma di statoe quello in basso in Figura 4.36. Un eventuale ritorno a 1 di X primadella conclusione dell’operazionee ininfluente.

Si noti che, diversamente, da quanto indicato nel testo, il trasferimento in RC avviene sul (fronte didiscesa del) clock 6. In Figura 4.37e riportato lo schema finale della soluzione.

Esercizio 4.19

Per eseguire il trasferimento al 7 clock, basta aggiungere uno stato al diagramma di Figura 4.36.

Esercizio 4.20

La rete di Figura 4.52 del testo riconosce il passaggio allo stato basso di X. L’inconveniente presentatoda questa rete sta nel fatto che un disturbo su X (spike), in grado di far commutare il flip-flop a cuiepresentato come clock, induce la generazione di un WAIT.

39

Figura 4.37 Schema finale della interconnessione tra la rete di generazione dei segnali RAeBin e RCin

e lo schema di somma dell’esercizio. Si noti che il segnale RAeBin viene usato anche per azzerare lostato del flip-flop usato per tenere traccia del riporto.

40

5

Esercizio 5.1

Si riporta la sequenza di istruzioni aggiungendo come commento l’effetto della loro esecuzione.

LD R1, 10 ; R1 <- 10LD R2, 7 ; R2 <- 7ADD R3, R1, R2 ; R3 <- 10 + 7 = 17ADD R3, R3, R2 ; R3 <- 17 + 7 = 24SUB R2, R2, R2 ; R2 <- 7 - 7 = 0ADD R3, R3, R2 ; R3 <- 24 + 0 = 24

Dunque al termineR3 contiene 24.

Esercizio 5.2

Si risolve l’esercizio con riferimento al caso in cui si abbiaR1=10, R2=20, R3=30 eR4=40. Dopo iprimi 3 PUSHlo stato dello stacke quello di Figura 5.1.

Figura 5.1 Stato dello stack dopo i primi 3 PUSH.

Il POPelimina 30 dalla testa dello stack, assegnandolo aR2. Il successivoPUSH(PUSH R4), de-posita 40, per cui i duePOPsuccessivi assegnano rispettivamente i valori 40 e 20 aR1 eR3, prelevandolidallo stack. In conclusione la situazione finalee quella di Figura 5.2.

Figura 5.2 Contenuto dei registri e dello stack a conclusione delle istruzioni.

Esercizio 5.3

Per la macchina registro-registro lo statement puo essere tradotto come di seguito (si assume, ovviamente,un ampio numero di registri):

LD R1, a ; Carica le -LD R2, b ; - variabili -LD R3, c ; - nei singoli -LD R4, d ; - registri -LD R5, eMUL R6, R3, R4 ; R6 <- c * dADD R6, R6, R2 ; R6 <- R6 + bSUB R6, R6, R5 ; R6 <- R6 - eMUL R6, R6, R1 ; R6 <- R6 * aST x, R6 ; Memorizza il risultato in x

Per una macchina registro-memoria (si assume un solo registro accumulatore implicato in tutte le opera-zioni.

LD cMUL d ; ACC <- c * dADD b ; ACC <- ACC + bSUB e ; ACC <- ACC - eMUL a ; ACC <- ACC * aST x

Per una macchina a stack:

PUSH c ; Inserisce le due -PUSH d ; - variabiliMUL ; Stack <- c * dPUSH bADD ; Stack <- Stack + bPUSH eSUB ; Stack <- Stack - ePUSH aMUL ; Stack <- Stack + aPOP x ; Estrae il risultato

42

Esercizio 5.4

In forma generale l’istruzioneMOVha questo significato:

MOV dest,source

e indica che il contenuto disource viene copiato indest . Il precedente contenuto didest vieneperduto, mentre il contenuto disource resta invariato. Le combinazioni consentite sono le seguenti(source ,dest ):

• registro,memoria• memoria,registro• registro,registro• memoria,immediato• registro,immediato• memoria,registro di segmento• registro di segmento,memoria• registro,registro di segmento• registro di segmento,registro

Consente molte modalita di indirizzamento e il formatoe variabile a seconda di questo. Si riportanoalcuni esempi.

• MOV AX,VAR ; EA= Offset(VAR) e AX<-M[EA]indirizzamento diretto

• MOV VAR(BX),CX ; EA= Offset(VAR)+BX e M[EA]<-CXindirizzamento relativo ai registri

• MOV R1,R2 ; R1<-R2indirizzamento di registro

• MOV DX,2700 ;DX<-2700indirizzamento immediato

Esercizio 5.5

L’istruzione MOVS viene utilizzata nello spostamento di stringhe (dove per stringa si intende una qual-siasi sequenza di byte, word, ecc.). A tale scopo:

• Il Flag di direzione (DF) indica la direzione; posto a 0 la stringa viene processata secondo indirizzicrescenti mentre posto a 1 secondo indirizzi decrescenti. Le istruzioni per azzerare e settare il DF sonoCLD e STD;

• Il registro CX da il numero di iterazioni;• L’indirizzo iniziale della stringa sorgente in DS:SI e quello della stringa di destinazione in ES:DI;• L’itruzione in questione come operando dell’istruzione REP (e un’istruzione di ripetizione).

La sintassi che ne derivae percio:

[REP] MOVS <destinazione>, <sorgente>[REP] MOVSB <destinazione>, <sorgente>[REP] MOVSW <destinazione>, <sorgente>

dove le ultime due istruzioni sono utilizzate per il byte e la word. Ecco un esempio:

SOURCE DB ’AMBARABA’DEST DB 10 DUP(?)

CLDMOV CX, LENGTH SOURCEMOV SI, OFFSET SOURCEMOV DI, OFFSET DESTMOVSB

43

Esercizio 5.8

• Confronto tra due registri e salto se il primoe maggiore del secondo.Con la soluzione del Paragrafo 5.5.2, si esprime come:

JG R1,R2,DESTMentre con la soluzione del Paragrafo 5.5.3 occorre scrivere:

CMP R1,R2JG DEST

• Confronto tra due locazioni di memoria e salto se la secondae maggiore della prima.Con la soluzione del Paragrafo 5.5.2, si esprime con le seguenti istruzioni:

LD R1,MEM1LD R2,MEM2JG R2,R1,DEST

Mentre con la soluzione del Paragrafo 5.5.3 si richiedono le seguenti istruzioni:LD R1,MEM1LD R2,MEM2CMP R2,R1JG DEST

Esercizio 5.9

Faremo uso della terminologia relativa all’ architettura dell’8086, assumendo pero che lo stack si sviluppinel senso degli indirizzi crescenti. Il primo parametro della funzionee un intero passato per valore, ilsecondo e il terzo sono puntatori a interi.

LEA AX,c ;carica l’offset di cPUSH AX ;mette il valore nello stackLEA AX,b ;carica l’offset di bPUSH AX ;mette il valore nello stackLD AX,a ;carica in R1 il valore aPUSH AX ;mette il valore nello stackCALL F ;Chiama la subroutine F

Assumendo che gli interi siano a 16 bit, e che pure l’indirizzo di ritorno sia a 16 bit, dopo l’esecu-zione dello statementCALL F, lo stato dello stacke quello di Figura 5.3, dove BP0 e SP0 sono i valoricontenuti in BP e SP prima della sequenza di chiamata.

Figura 5.3 Stato dello stack all’atto dell’esecuzione di CALL F, (Esercizio 5.9).

All’ingresso della routine BP deve essere aggiornato in modo da avere un riferimento per i parametri.Cio richiede che prima BP venga salvato. Dunque le prime istruzioni della routine saranno:

F: PUSH BP ;Inizializza BPLD BP,SP ;Carica in BP il valore di SP

44

Figura 5.4 Stato dello stack dopo l’aggiornamento di BP. Esercizio 5.9.

Lo stato risultante dello stacke allora quello di Figura 5.4.I parametri vengono indirizzati in modo relativo a BP. Lo statementb=a+c viene tradotto come:

MOV AX,BP-4 ;Carica in AX il valore aMOV BX,BP-8 ;Carica in BX l’offset di cADD AX,[BX] ;Esegue la somma tra a e cMOV BX,BP-6 ;Carica l’offset di b in BXMOV [BX],AX ;Assegna il valore calcolato a b.

Esercizio 5.10

Verranno date due soluzioni dipendenti dal modo di operare della macchina. Ambedue le soluzioni nonconsentono ne la rientranza, ne la ricorsivita (per quanto si riferisce a questi aspetti si veda l’Esercizio5.12).

Consideriamo prima il caso in cui codice e dati siano distinti. Il passaggio dei parametri richiede lacostruzione di uno pseudo stack. Supponiamo che l’istruzione di salto al sottoprogramma (BRL) depositiin uno speciale registro (XFR) l’indirizzo di ritorno e che esistano due istruzioni ( LDX Ri e STX Ri)per caricare in un registro il contenuto di XFR e per memorizzare in XFR. Supponiamo anche che lamacchina disponga dell’istruzione LDAD per caricare un’indirizzo.

Si indichi con PSSTK la prima posizione dell’area che funge da pseudo stack e con x1, x2, . . . , xnle variabili (che supponiamo a 32 bit). La sequenza di chiamata richiede il trasferimento di parametri inPSSTK. Cio si ottiene, ad esempio, nel modo seguente:

LDAD R1,PSSTKLD R2,XnST (R1),R2ADD R1,4..ADD R1,4LD R2,X1ST (R1),R2LDAD R1,PSSTKBRL F

Entrando in F, R1 contiene l’indirizzo dell’area in cui stanno i parametri. Si noti che se F chiama asua volta un sottoprogramma F1,e necessario che prima di effettuare la chiamata, F salvi il contenuto diXFR, ovvero che esegua queste due istruzioni:

ST COPIAR1,R1LDX R2ST COPIAXFR,R2

Dove, per l’ipotesi di non rientranza in F, COPIAR1 e COPIAXFR possono essere due posizionidefinite in F. Al ritorno dal sottoprogramma F1 le prime due istruzioni saranno:

45

LD R1,COPIAR1LD R2,COPIAXFRSTX R2

La routine si concludera con l’istruzione BRX che fa saltare all’ indirizzo contenuto in XFR.

Altra soluzione

Se invece la macchina non forza la separazione tra codice e dati, si puo all’interno del codice crearei riferimenti ai parametri sistemandoli in una posizione raggiungibile attraverso l’indirizzo di ritornoche, comunque, viene passato al sottoprogramma. Questa tecnica veniva usata nei calcolatori HP21xx.Per poterla spiegaree necessario illustrare per quel che serve l’architettura in questione (i calcolatori inquestione non sono piu in produzione dalla fine degli anni ’70).

Si trattava di macchine a 16 bit del tipo registro-memoria. Esse che leggevano e scrivevano sempree solo parole di 16 bit. Gli indirizzi erano assegnati alle parole.La CPU disponeva di 2 soli registri, indicati con A e B e codificati nel set di istruzioni (per esempio: LDAstava per “load into A”, STB per “store B”). I registri non avevano alcuna funzione di indirizzamento.L’unica possibilita di indirizzamento indiretto era attraverso la memoria; ad esempio lo statementLDALOC,I (load into A the content of LOC, indirect) aveva l’effetto di caricare nel registro A il contenutodella cella di memoria il cui indirizzo si trovava in LOC (ovviamenteLDA LOCcaricava in A il conte-nuto di LOC).Era prevista l’istruzione di salto incondizionato (JMP), ma non quella di salto condizionato. Era peropresente l’istruzione (di controllo)ISZ (increment and skip if zero) che aveva l’effetto di incrementareil contenuto della posizione di memoria indirizzata e, a seconda del risultato, incrementare di 1 o di 2 ilProgram Counter, con l’effetto di saltare l’istruzione successiva se il risultato era 0. Conseguentemente,i test richiedevano due istruzioni: ISZ seguita dall’istruzione JMP; se l’effetto dell’incremento non dava0 veniva eseguito il JMP; se l’effetto dell’incremento dava 0 veniva eseguita l’istruzione successiva alJMP.Infine era prevista l’istruzioneJSB (jump to subroutine) che aveva l’effetto di scrivere l’indirizzo del-l’istruzione successiva (l’ipotetico indirizzo di ritorno) nella posizione indirizzata, passando percio ilcontrollo alla posizione successiva a quella indirizzata.

Cio detto supponiamo che la nostra funzione sia cosı dichiarata (in pratica restituisce al chiamantela somma dei tre parametri):

int f(int a, int b, int c)return a+b+c;

e supponiamo che nel corpo del programma si abbia lo statementy = f(x1, x2, x3 ).Indichiamo con X1, X2 e X3 le posizioni assegnate rispettivamente alle tre variabili che rappresen-

tano i parametri nella chiamata alla funzione e con Y quella assegnata alla variabile y. Indichiamo con Fil nome dato alla prima posizione della funzione. Nell’assembler dei calcolatori HP21xx la direttiva DW(define word) riservava una parola (con il contenuto specificato). Da qualche parte del programma chia-mante ci sarebbero state queste dichiarazioni (non indichiamo il contenuto delle posizioni di memoria inquantoe irrilevante rispetto ai nostri scopi):

X1 DW :: ;variabili definiteX2 DW :: ; da qualche parteX3 DW :: ; nel programmaY DW :: ;

La chiamata y = f(x1, x2, x3 ) poteva essere tradotta nel seguente modo:

JSB F ;chiamata a FIP1 DW X1 ; indirizzo del primo parametroIP2 DW X2 ; indirizzo del secondo parametroIP3 DW X3 ; indirizzo del terzo parametroNEXT :: ;prossima istruzione del prog chiamante

46

Nella sequenza di chiamata si sono dati dei nomi esplicativi alle varie posizioni (per esempio IP1 vuoleindicare che in quella posizione c’e il parametro n.1). Ovviamente il compilatore non assegnava questinomi, in quanto i riferimenti erano fatti in modo indiretto nel modo illustrato piu sotto.

L’esecuzione dello statementJSB F aveva l’effetto di far di scrivere in F l’indirizzo della posizionesopra designata come IP1 e di assegnare al program counter l’indirizzoF+1. Attraverso la posizione F,con un caricamento indiretto poteva essere letto il contenuto delle posizioni successive, cioe gli indirizzidei parametri. Mostriamo come riportando un possibile codice per F.

F NOP ; no operationLDB F,I ; B<- M[IP1] = indirizzo X1STB IND ; IND e di appoggio, punta a X1LDA IND,I ; A<- M[X1] = x1ISZ F ; a puntare a IP2LDB F,I ; B<- M[IP2] = indirizzo X2STB IND ; IND punta a X2ADA IND,I ; A<- A+M[X2] = x1+x2ISZ F ; a puntare a IP3LDB F,I ; B<- M[IP3] = indirizzo X3STB IND ; IND punta a X3ADA IND,I ; A<- A+M[X3] = x1+x2+x3ISZ F ; F punta a NEXTJMP F,I ; ritorna alla posizione NEXT col risultato in A

L’istruzione nella posizione NEXT sarebbe stata:

NEXT STA Y ; y=f

Come si vede il processo era laborioso. C’era un modo per alleggerirlo un poco. Si basava sulfatto che non c’erano limiti agli indirizzamenti indiretti, attraverso la memoria. Tenuto conto di cio ilcompilatore avrebbe generato un codice di questo tipo per la sequenza di chiamata:

JSB F ;chiamata a FDW X1,I ; indirizzo indiretto del primo parametroDW X2,I ; indirizzo indiretto del secondo parametroDW X3,I ; indirizzo indiretto del terzo parametro:: ;prossima istruzione del prog chiamante

Mentre il codice di F sarebbe stato:

F NOP ; no operationLDA F,I ; A<- M[M[M[F]]] = x1ISZ F ; a puntare a IP2ADA F,I ; A<- A+M[M[M[F]]] = x1+x2ISZ F ; a puntare a IP3ADA F,I ; A<- A+M[M[M[F]]] = x1+x2+x3ISZ F ; F punta a NEXTJMP F,I ; ritorna alla posizione NEXT col risultato in A

Infatti, se ad esempio consideriamo l’istruzioneLDA F,I : poiche si tratta del caricamento indirettonon viene preso il contenuto di F, ma quello della posizione cui punta F; poiche questa locazione portal’indicazione di indiretto, l’istruzione prosegue prendendo il contenuto dall’indirizzo contenuto nellalocazione stessa.1

Si noti che con queste tecniche il passaggio dei parametrie sempre per indirizzo.

1E lecito chiedersi che senso ha l’indicazione di indiretto. Si trattava semplicemente del bit piu significativo posto a 1 sulleistruzioni facenti riferimento alla memoria e sulle posizioni eventualmente indirizzate, per fare piu livelli di indiretto.

47

Esercizio 5.11

Se non si ha a disposizione lo stack per poter passare i parametri, si puo fare riferimento ai metodiadottati nell’ esercizio precedente. Supponiamo di essere nel secondo caso illustrato nella soluzionedell’esercizio 5.10. La sequenza di chiamata sara:

JSB F_A DW A ;parametri_B DW B ; passati in questo_C DW C ; ordine

Assumendo che la macchina abbia un numero ragionbevole di registri e che questi possano essereusati per indirizzare, la routine F sara come qui sotto. Si illustra solo la parte riferita allo statementc=a+b (Attenzione: none lo statement richiesto dal testo dell’esercizio), ipotizzando che sia l’unicostatement.

F NOPLD R2,F ;R2 punta alle posizioni _ALD R1,(R2) ;R1 <- indirizzo di ALD R0,(R1) ;R0 <- AADD R2,4 ;parole di 4 bitLD R1,(R2) ;R2 <- indirizzo di BADD R0,(R1) ;R0 <- A + BADD R2,4 ;LD R1,(R2)ST (R2),R0ADD R2,4JR R2 ;salto relativo a R2

Esercizio 5.12

Per ipotesi i registri sono in grado di contenere tutti i parametri di una singola chiamata, ma non sonosufficienti per chiamate in cascata.

Non essendoci stack,e necessario utilizzare la memoria come deposito dei parametri delle funzioni“padre”, lasciando nei registri solamente il collegamento all’area in cui sono memorizzati. Per semplifi-care, seguiamo il corso di un programma un cui esistono delle successive chiamate a sotto-programmi.

Supponiamo che si possa usare il registroR0 per il valore di ritorno dalla funzione. Supponiamo chel’istruzione BRL di chiamata depositi l’indirizzo di ritorno inRn−1. Questo presuppone, per il ritorno,l’istruzione BR, ovvero il salto relativo ai registri (verra eseguita l’istruzione BRRn−1). Gli altri registrivengono usati per passare i parametri.

Si supponga ora che la funzione in esecuzione chiami una ulteriore funzione. Al momento dellachiamata a sotto-funzione, si copia il contenuto del blocco di registri in memoria, prevedendo di con-servare in un registro, ad esempioRn−2, il riferimento all’area di memoria utilizzata. Gli altri registrirestano a questo punto liberi per essere utilizzati per la funzione chiamata.

La funzione chiamata, deve, per prima cosa, salvare il contenuto del registroRn−2 e Rn−1 chedovranno tornare immutati al chiamante.

Se si vogliono consentire le chiamate ricorsivee necessario che l’area in cui vengono passati iparametri sia allocata di volta in volta. Cio richiede una funzione del tipomalloc del C.

Esercizio 5.13

In Tabella 5.1e riportata la memorizzazione con ordinamento little endian. La Tabella 5.2 illustra il casodi memorizzazione con ordinamento big endian.

Esercizio 5.14

L’istruzione MOV AX,VAR[BX], con VARnome simbolico,e l’istruzione di lettura del contenuto diuna posizione di memoria e relativa copia del valore del dato letto nel registroAX. Nel caso specificol’indirizzamento della memoriae in forma relativa al registro BX. L’indirizzo effettivoe la somma delloscostamento diVARcon il contenuto diBX. L’effetto e:

AX <-- M[offset(VAR)+BX] .

48

3 2 1 0 Indirizzo di partenzaV A L ALFAA P S I ALFA + 4R E T ALFA + 8

A S E ALFA + 12

Tabella 5.1 Memorizzazione della stringa con ordinamento little endian.

3 2 1 0 Indirizzo di partenzaL A V ALFAI S P A ALFA + 4

T E R ALFA + 8E S A ALFA + 12

Tabella 5.2 Memorizzazione della stringa con ordinamento big endian.

Esercizio 5.15

Al termine della sequenza AX conterra il numero 55. Infatti, il ciclo contenuto nella sequenza non faaltro che sommare in AX i numeri da 1 a 10 (o meglio da 10 a 1). Dunque il contenuto di AX alla finedel cicloe dato da:

10 + 9 + . . . + 2 + 1 =10× 11

2= 55.

NOTA : nel testo (prima stampa) c’e un errore. L’istruzioneJMP LOOPva sostituita conJNZ LOOP.

49

6

Esercizio 6.1

La logica richiestae mostrata in Figura 6.1.

Figura 6.1 Rete logica attivazione SELDTRdir.

Esercizio 6.2

Se la macchina interpreta il corpo DEST come assoluto la fase di esecuzione dell’istruzioneJMP DESTconsiste in un solo passo, in quanto si tratta semplicemente di portare in PC il contenuto del campoindirizzo dell’istruzione.

T1: 06 ‖ IR[25 : 0]out, PCin.

Se la macchina interpreta il corpo DEST come relativo a PC, occorre sommare a PC il contenuto delcampo indirizzo. Cio richiede tre passi:

T1: 06 ‖ IR[25 : 0]out, TIinT2: PCout, ADD, T0inT3: T0out, PCin

Esercizio 6.3

I passi previsti dalla fase di esecuzione dell’operazione diSWP MEM1,MEM2sono i seguenti (si fal’ipotesi che lettura e scrittura di un dato in memoria richiedano due cicli di clock):

T1 : 019 ‖ IR[12 : 0]out, MARinT2 : MRDT3 : MRD, DTRinT4 : DTRout, TEMPinT5 : 019 ‖ IR[25 : 13]out, MARinT6 : MDRT7 : MDR, DTRinT8 : 019 ‖ IR[12 : 0]out, MARinT9 : SELDTRdir, DTRout, MWRT10: SELDTRdir, DTRout, MWRT11: 019 ‖ IR[25 : 13]out, MARinT12: SELDTRdir, TEMPout, DTRinT13: SELDTRdir, DTRout, MWRT14: SELDTRdir, DTRout, MWR

L’ esecuzione dell’operazione ha richiesto 14 cicli di clock, che sommati ai 4 cicli di fetch porta ad18 i cicli necessari a eseguire l’istruzioneSWP MEM1,MEM2.

Esercizio 6.4

L’avanzamento del contatore in presenza di WAIT, sul periodo T3 puo essere sospeso annullando il clockal contatore quando si verifica la condizione WAIT·T3. Si veda la Figura 6.2.


Naturalmente lo schema di Figura 6.2 presuppone che il contatore operi sui fronti di salita del clock.

Esercizio 6.5

Il problemae del tutto analogo a quello dell’Esercizio 6.2, con la differenza che la modifica di PCecondizionata dal verificarsi della condizione S e Z.

Nel caso in cuiDESTsia interpretato come indirizzo assoluto si ha :

T1: if (S ∨ Z) 06 ‖ IR[25 : 00]out, PCin else Restart

Nel caso in cuiDESTe lo scostamento relativo al PC:

T1: if (S ∨ Z) 06 ‖ IR[25 : 00]out, TIin else RestartT2: PCout, ADD, T0inT3: T0out, PCin

52

Si noti che in questo caso il segnaleRestart (si faccia riferimento alla Figura 6.14 del testo), asseritose la condizione S none verificata, evita l’esecuzione dei passi 2 e 3.

Esercizio 6.6

L’istruzione JE R1, R2, DEST nella fase di esecuzione confronta i due registri (tramite differenza) e, seil risultato e uguale a zero, aggiorna PC con il valore DEST. Rispetto all’Esercizio 6.5, questa volta c’eda considerare il fatto che la generazione della condizione S viene effettuata nel corso dell’esecuzionedell’istruzione e non dall’esecuzione dell’istruzione precedente. La generazione di S richiede l’impiegodei bus S1 e S2 (Figura 6.11 del testo). Poiche il campo DEST deve essere interpretato come scostamentorispetto al contenuto di PC, l’operazione puo compiersi solo se si prevede uno specifico sommatore.L’uscita di tale sommatore non puo essere portata a PC tramite il bus D perche su tale bus c’e comunquel’uscita di ALU. Occorre quindi prevedere un percorso specifico come in Figura 6.3, dove con S sieindicato il sommatore. Il multiplexer fa caricare in PC l’uscita di S se la ALU fornisce la condizione “=”.

Figura 6.3 Architettura necessaria per l’esecuzione in un solo clock dell’istruzione JE.

Esercizio 6.7

All’inizio della fase di fetch, ilµPC punta alla locazione della ROM da cui inizia la sequenza di CW lacui interpretazione da luogo alla fase di fetch. La fase di fetch inizia con il prelievo dell’istruzione e siconclude quando viene scritta in IR per essere codificata. I passi non differiscono da quelli di pagina 212del testo:

T1: PCout, MARin, SEL4, ADD, T0inT2: MRD, TOout, PCinT3: MRD, DTRinT4: DRTout, IRin

Per il formato si veda il prossimo esercizio.

53

Esercizio 6.8

L’effetto di ADD R1,R2,R3 , e di trasferire in R1 il risultato della somma del contenuto dei registri R2e R3. Poiche si assume una macchina con singolo bus interno, come in Figura 6.6 del testo, la sequenzadei passie necessariamente questa:

T1: PCout, MARin, SEL4, ADD, T0inT2: MRD, T0out, PCinT3: MRD, DTRinT4: DTRout, IRinT5: R2out, TIinT6: R3out, ADD, T0inT7: T0out, R1in

Ragionando secondo lo schema della codifica orizzontale, la parola di controllo deve conteneretanti bit quanti sono i comandi individuati. La sequenza sopra riportata prevede 16 comandi, da cuiconseguirebbe una parola di controllo di 16 bit del tipo di quella mostrata in Tabella 6.1.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

PC PC MAR SEL4 ADD T0 T0 MRD DTR DTR R1 R2 R3 IR TI TIout in in ALU in out in out in out out in in out

Tabella 6.1 Parola di controllo specifica della soluzione dell’ Esercizio 6.8. Si noti che relativamente airegistri, si e assunto che esista uno specifico bit per comandare, per ognuno di essi, sia l’ingresso chel’uscita.

Risulterebbe la sequenza di CW di Tabella 6.2.

BIT: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15T1: 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0T2: 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0T3: 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0T4: 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0T5: 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0T6: 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0T7: 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0

Tabella 6.2 Sequenza di controllo riferita alle parole aventi formato come in Tabella 6.1.

Come indicato della didascalia della Tabella 6.1, la parola di controllo ivi mostrata contiene i soli bit chesi richiedono nella specifica istruzione, e i bit relativi agli specifici registri. Seguendo questo schema,con una macchina a 32 registri occorrerebbero ben 96 bit per la selezione dei registri stessi. Convieneinvece decodificare a parte i campiRd, RS1 eRS2 dell’istruzione prevedendo che i bit 10,11 e 12 dellaparola di controllo abbiano il significatoRdin, RS1out e RS2out e prevedere che i segnali di comandodei singoli registri siano attenuti come nello schema 6.4.

54

Figura 6.4 Miglioramento rispetto alla codifica di Tabella 6.2. I bit 10,11 e 13 della parola di controlloassumono il significato riportato in figura.

Esercizio 6.9

L’istruzioneLD RA,d(RB) (schematicamenteRA<-M[d+RB] ), ha l’effetto di copiare nel registroRAil contenuto della cella di memoria di indirizzod+RB. I micro-passi della fase di esecuzione sono iseguenti:

T1: RBout, TIinT2: 016 ‖ IR[15 : 00]out, ADD, T0inT3: TOout, MARinT4: MDRT5: MDR, DTRinT6: DTRout, RAin

La lista di comandi in logica cablatae in Tabella 6.3. Ad essa corrisponde la rete di Figura 6.5 (sitenga conto che la sequenzae specifica per questa istruzione). Il segnale LD corrisponde alla istruzioneche viene eseguita.In Tabella 6.4 viene mostrata l’eventuale parola di controllo, nel caso di logica microprogrammata. LaCW e ottenuta come estensione di quella definita nell’ Esercizio 6.8. Sie assunto che la parte relativa alfetch sia quella dell’ Esercizio 6.7.La sequenza di CWe riportata in Tabella 6.5.

55

Comando µpasso attivazioneADD T2T0in T2T0out T3DTRout T6DTRin T5RBout T1TIin T1MARin T3MRD T4, T5RAin T6IRout T2

Tabella 6.3 Comandi in logica cablata (Esercizio 6.9).

Figura 6.5 Rete di codifica, della fase di esecuzione, in logica cablata. Esercizio 6.9.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

PC PC MAR SEL4 ADD T0 T0 MDR DTR DTR Rd RS1 RS2 IR TI TI IR SELDTRout in in ALU in out in out in out out in in out out dir

Tabella 6.4 Parola di controllo specifica della soluzione dell’Esercizio 6.9, ottenuta estendendo la CWdefinita dell’Esercizio 6.8.

BIT: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17T1: 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0T2: 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0T3: 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0T4: 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0

T5 (T1): 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0T6 (T2): 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0T7 (T3): 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1T8 (T4): 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0T9 (T5): 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0T10 (T6): 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0

Tabella 6.5 Formato parole di controllo (Esercizio 6.9). E’ stata aggiunta la fase di fetch; i periodi relativialla sola fase di esecuzione sono tra parentesi.

56

Esercizio 6.10

Si riporta la Tabella 6.6 in cui, rispetto a quella del testo, sono stati aggiunti i valori del numero totaledi cicli per ciascuna istruzione (Ncicli), la percentuale nel mix (xi), e il contributo dato dall’istruzione aCPI (xi × cpi). CPI viene calcolato come

∑(xi × cpi), oppure come rapporto tra il totale del numero

di cicli e il totale delle istruzioni (∑

Ncicli∑xi

). Si ottieneCPI = 7, 69.

Tipo di istruzione Xi cpi Ncicli xi (%) xi × cpi

Addizioni 20 mil. 4 80 mil. 25,64 1,03Moltiplicazioni 6 mil. 10 60 mil. 7,69 0,77Divisioni 2 mil. 40 80 mil. 2,56 1,02Memoria 40 mil. 8 320 mil. 51,28 4,10Salti 10 mil. 6 60 mil. 12,82 0,77Totale 78 mil. 600 mil. 100,00 7,69

Tabella 6.6 Calcolo del CPI .

Esercizio 6.11

Si ricorda che l’accelerazionee definita con la seguente formula:

a =tvtn

dovetv e il vecchio tempo di esecuzione etn e il nuovo tempo di esecuzione.Una accelerazione pari a 4 nelle addizioni comporta questo cambiamento nella prima riga di Tabella

6.6.


Addizioni 20 mil. 1 20 mil. 25,64 0,25

Conseguentemente l’ultima riga di Tabella 6.6 diventa:


. . . . . . . . . . . . . . . . . .

Totale 78 mil. 540 mil. 100,00 6,92

Dunque si ha una accelerazione globale pari a:7,696,92 = 1, 11.

Una accelerazione pari a 4 per la memoria comporta questo cambiamento nella quarta riga di Tabella6.6.


Memoria 40 mil. 2 80 mil. 51,28 1,02

Conseguentemente l’ultima riga di Tabella 6.6 diventa:


. . . . . . . . . . . . . . . . . .

Totale 78 mil. 360 mil. 100,00 4,61

Dunque si ha una accelerazione globale pari a:7,694,61 = 1, 66. Ovviamente conviene apportare il miglio-

ramento alla memoria.

57


Addizioni 20 mil. 1 20 mil. 25,64 0,25Moltiplicazioni 6 mil. 10 60 mil. 7,69 0,77Divisioni 2 mil. 40 80 mil. 2,56 1,02Memoria 40 mil. 2 80 mil. 51,28 1,02Salti 10 mil. 6 60 mil. 12,82 0,77Totale 78 mil. 300 mil. 100,00 3,83

Tabella 6.7 Calcolo del nuovo CPI .

Esercizio 6.12

• Imponendo una accelerazione pari a 4 sia alle operazioni di memoria che alle addizioni si ottiene lasituazione riassunta in Tabella 6.7. Ricordando dalla Tabella 6.6 che ilCPI del sistema non modificatovale 7,69 si puo scrivere l’accelerazione globale pari a7,69

3,83 = 2, 00.• L’accelerazione globale relativa deve essere calcolata considerando al numeratore ilCPI proprio del

sistema gia accelerato nelle operazioni di memoria. Recuperando questo dato dalle Tabelle dell’Eser-cizio 6.11, si ha che l’accelerazione globale relativae pari a:4,61

3,83 = 1, 20.• Come per il caso precedente l’accelerazione globale relativa deve essere calcolata considerando che al

numeratore si ha ilCPI proprio del sistema gia accelerato nelle addizioni. Recuperando questo datodalle Tabelle dell’Esercizio 6.11 si ottiene un’accelerazione globale relativa pari a:6,92

3,83 = 1, 80.

Esercizio 6.14

La Tabella 6.8 mostra i differenticpi per le diverse istruzioni.

Istruzione xi(%) cpi

JE/JZ 0,1 6MOV reg/reg 0,2 6MOV mem/mem 0,3 9CALL (near) 0,05 8RET (near) 0,05 6PUSH\POP reg 0,2 8PUSH\POP mem 0,1 12

Tabella 6.8 Tabella risolutiva Esercizio 6.14.

Il CPI totalee :

CPI =∑

cpixi =∑

(cpi · perci)/100 = 6·0, 1+6·0, 2+9·0, 3+8·0, 05+6·0, 05+8·0, 2+12·0, 1 = 8

Esercizio 6.15

Per quanto si riferisce al punto (1), nella Figura 6.6 a sinistra e a destra vengono riportati i clock richiestidalla fase di fetch e dalla fase di esecuzione per i diversi tipi di istruzione. Essi derivano dalle specifichedel testo. Per assunzione, l’8086 legge sempre parole allineate di 16 bit, mentre l’8088 legge parole di 8bit, quindi esegue un doppio ciclo di lettura in memoria per i dati a 16 bit.

Si ricorda che: CRD=CWR=4 e un istruzione occupa mediamente 3 byte.I CPI valgono:

CPI8086 =∑

xicpi = 6 + 0, 6× 3 + 0, 4× 0, 3× 7 + 0, 4× 0, 7× 7 = 10, 6

CPI8088 = 12 + 0, 6× 3 + 0, 4× 0, 3× 7 + 0, 4× 0, 7× 11 = 17, 72

Si nota che il rapporto tra le prestazioni valeP8088P8086

= 17,7210,6 = 1, 67. Cioe l’8086e il 67% circa piu

efficente dell’ 8088.

58

Fetch Execute60% 40%

30% 70%6 3 3+4 3+4


30% 70%12 3 3+4 3+4+4

Figura 6.6 Tabelle riassuntive dei clock relativi al caso (1) dell’Esercizio 6.15. A sinistra per l’8086 adestra per l’8088.

Per quanto si riferisce al punto (2) la Tabella 6.7 riporta i clock richiesti per l’8086. Per l’8088 le cosesono invariate. La fase di fetch ha subito un aumento di clock, secondo il testo dell’esercizio.


30% 70%8 3 3+4+4 3+4

Figura 6.7 Tabelle riassuntiva dei clock relativi al caso (2) dell’Esercizio 6.15 per l’8088.

L’8086 ha dunque questo indice di prestazione:

CPI8086 = 8 + 0, 6× 3 + 0, 4× 0, 3× 11 + 0, 4× 0, 7× 7 = 13, 08

Il rapporto tra le prestazioni valeP8088P8086

= 17,7213,8 = 1, 28 (l’8088 ha mantenuto invariate le sue presta-

zioni). L’aumento dei clock medi per la fase di fetch dell’8086 ha causato un aumento delle prestazionidi 2 unita, questo ha portato ad una drastica diminuzione del vantaggio dell’8086 sull’8088, in quantodal 67% di efficenza in piu si e scesi al 28%, con una perdita circa del 40% per l’8086.

59

7

Considerazioni preliminari

Prima di dare la soluzione degli esercizi, conviene fare qualche richiamo sull’indirizzamento, il paralle-lismo e la selezione degli integrati (loro allocazione nello spazio di memoria e selezione).

La memoria puo essere schematizzata come in Figura 7.1.

Figura 7.1 Schematizzazione della memoria.

Con riferimento alla Figura 7.1 faremo queste convenzioni:

• La memoriae costituita da parole1 di ampiezzap bit, pari al grado di parallelismo del bus dei dati.• Sem e il numero delle linee di indirizzo lo spazio di memoriae ampioM = 2m.• Gli indirizzi sono assegnati alle parole, indipendentemente dal grado di parallelismo.2

Di norma non tutto lo spazio di memoria viene utilizzato e, comunque, si puo sempre presentare lapossibilita che occorra costruire un blocco di memoria di una certa dimensione a partire da una posizioneprestabilita.3 Supponiamo di disporre di integrati di memoria con parallelismop, di dimensioneB = 2b

(ovvero conb linee di indirizzo). Assumiamo che gli integrati presentano un piedino di abilitazione CS(Chip Select). Conn integrati potremo costruire un blocco di memoria dinB parole contigue.

Un indirizzo di memoria puo essere sempre considerato come composto da due parti: il numero diblocco e l’indirizzo entro il blocco. Figura 7.2 mostra questa schematizzazione. Ne consegue che la

Figura 7.2 Interpretazione dell’indirizzo di una parola.

1A volte si usano anche i termini “celle”,“posizioni” e “locazioni”2Da questa convenzione segue che una memoria a 8 bit di ampiezzaM contieneM byte, mentre una memoria a 32 bit di

ampiezzaM contiene4M byte.3E il caso della memoria ROM contenete il codice di inizializzazione del sistema.

dislocazione naturale di un blocco diB parole all’interno dello spazio di memoriaM e quella che loalloca ad un indirizzo di partenza multiplo di B (incluso lo 0), come schematizzato a sinistra in Figura7.3.

Cio equivale a immaginare lo spazio di memoria come diviso in blocchi della dimensione dell’in-tegrato. Corrispondentemente l’indirizzo puo essere cosı interpretato: le linee di indirizzoAb−1 −A0

danno l’indirizzo entro il blocco, le lineeAm −Ab identificano il blocco. Ne consegue che le lineeAb−1 −A0 vanno portate alle linee indirizzi dell’integrato, mentre le restanti verranno decodificate inmodo da selezionare l’integrato attraverso il piedino CS.

Figura 7.3 Interpretazione dell’indirizzo e schematizzazione del problema della selezione edell’indirizzamento.

Vale solo la pena di osservare che, se con integrati di capacita B volessimo costruire un blocco dimemoria a partire da un indirizzo non multiplo diB, saremmo nella situazione schematizzato nella partedestra di Figura 7.3, dove sie supposto di allocare l’integrato di capacita B a cavallo tra il blocco 0 eil blocco 1 nello spazio degli indirizzi. La selezione comporta il riconoscimento del blocco di indirizzicorrispondente alla dislocazione dell’integrato, mentre l’indirizzamento al suo interno richiederebbe diriferire gli indirizzi alla base del blocco. Praticamente inattuabile!

Naturalmentee sempre possibile costruire un blocco di memoria ampioB a partire da un indirizzonon multiplo diB. Si tratta semplicemente di usare integrati di taglia inferiore, in modo che essi venganoallocati in modo “naturale” nello spazio di memoria. Con riferimento all’esempio di Figura 7.3 si trattadi usare due integrati di capacita B/2. Ovviamente questi integrati avrannob − 1 linee di indirizzo enella decodifica entrera il bit b− 1 che prima faceva parte dell’indirizzo all’interno dell’integrato.

Esempio 1 In una memoria a 8 bit,M = 1 MB, i blocchi di 256 KB hanno come posizioni na-turali quelle che iniziano agli indirizzi 0, 256 K, 512 K, 768 K. L’indirizzo entro il bloccoe dato attra-verso le lineeA17 −A0, mentre le lineeA19 −A18 servono a specificare il blocco. Per esempio, ilblocco di memoria 1 (quello che va dall’indirizzo 256 K all’indirizzo 512-1 K) viene selezionato conCS1 = A19 ·A18.

Indirizzamento al byte

Sopra sie assunto che gli indirizzi fossero assegnati alle parole. Nella pratica corrente gli indirizzi sonoassegnati ai byte. Il motivoe ovvio: mantenere la stessa modalita di indirizzamento nell’evoluzionearchitetturale, per esempio nel passare da 16 a 32 bit. Cio comporta la piena compatibilita almeno perquanto riguarda l’indirizzamento dei programmi.4

Per semplicita nella parte che segue faremo riferimento a integratiByte-wide(l’impiego di altriformati non comporta complicazioni concettuali; si veda per esempio l’esercizio 7.2).

In Figura 7.4 viene schematizzata una memoria a 32 bit. Se supponiamo che le parole siano allineateagli indirizzi multipli di 4, ovvero se chiamiamo indirizzo di parola il contenuto delle lineeAm −A2,l’indirizzo del bytee dato dall’indirizzo di parola e dall’indirizzo del byte entro la parola. L’indirizzoviene quindi interpretato come illustrato in Figura 7.4.

4Per esempio, l’istruzione Intelmov rd,mem ha la stessa codifica su 8088, 80886, 80386, ecc. Se gli indirizzi fossero statiassociati alle parole, il campo mem si dimezzerebbe nel passare dall’8088 all’8086, come pure nel passare dall’8086 all’80386.

62

Figura 7.4 Interpretazione dell’indirizzo nel caso di memoria a 32 bit. Tra parentesi gli indirizzi (i numeri)di parola.

Di norma la memoria deve consentire non solo la lettura delle parole, ma anche di semiparole o byte.Per esempio, con riferimento alla Figura 7.4, deve essere possible la lettura di un singolo byte (moval, mem ), di una semiparola (mov ax,mem), di una parola (mov eax,mem). Supponiamo che leparole siano sempre allineate a indirizzi multipli di 4 e che le semiparole siano allineate a indirizzi pari.Il problema di quali byte leggere viene risolto, per esempio, attraverso 4 linee (BE3,BE2, BE1,BE0)asserite opportunamente dalla CPU a seconda del parallelismo del trasferimento: nel caso della lettura di1 byte, sulle linee di indirizzoAm−1 −A2 appare l’indirizzo di parola e viene asserito il (BEi) relativoalla posizione del byte nella parola; nel caso di lettura di semiparola vengono asseriti oBE3, BE2 oBE1, BE0; nel caso di lettura dell’intera parola vengono asseriti tutti i 4 BE.

Come sappiamo, alcune architetture impongono che gli allineamenti siano rispettati. Diversamentedalle macchine RISC, nell’architettura Intel gli allineamenti non sono obbligatori, in quanto, se vienerichiesta la lettura di una parola non allineata, la CPU legge prima la parte di parola che si trova all’in-dirizzo dato (cioe quello della parola contenente il byte meno significativo), asserendo gli opportuni BE,quindi legge all’indirizzo della parola successiva asserendo i rimanenti BE. All’interno della CPU i bytevengono messi nell’ordine dovuto. Per esempio, se viene effettuata la lettura della parola all’indirizzo 7(Figura 7.4), viene asserito l’indirizzo di parola 1 eBE3 (determinando la lettura del byte meno signi-ficativo della parola sulle 8 linee piu significative del bus), quindi viene asserito l’indirizzo di parola 2e BE2, BE1 e BE0 (determinando la lettura dei tre byte piu significativi della parola sulle linee menosignificative del bus). Tuttavia i manuali Intel raccomandano vivamente di allineare le parole (quelle di64 bit a indirizzi multipli di 8, quelle a 32 a indirizzi multipli di 4, quelle a 16 bit a indirizzi multipli di2) fornendo numeri impressionanti (cicli di clock persi) sul peggioramento delle prestazioni a causa delnon allineamento.

Esempio 2 In una memoria a 32 bit,M = 1 GB, i blocchi di 2 MB hanno come posizioni naturaliquelle che iniziano agli indirizzi 0H, 200000H, 400000H), 600000H (rispettivamente 0, 2, 4, 6 Mega).Le parole allineate sono assegnate agli indirizzi multipli di 4: 0, 4, 8, 12, ... Gli indirizzi di parola sonodati dalle lineeA29 −A2.Supponiamo ora di voler costruire un blocco da 2 MB a partire dall’indirizzo 2 M. In 2 MB ci stanno512 K parole (da 32 bit). Per indirizzare 512 K occorrono 19 linee di indirizzo, dunque le parole all’in-terno del blocco sono selezionate attraverso i 19 bit meno significativi dell’indirizzo di parola, ovveroattraverso i bitA20 −A2. La selezione del bloccoe data daA29 ·A28 · ·A22 ·A21.

63

Esercizio 7.1

La soluzione di minor costoe quella che utilizza l’integrato da 128kbyte kbyte, i tre da 64kbyte e tantiintegrati da 32kbyte quanti ne servono per arrivare a coprire lo spazio di memoria richiesto.

Essendo per 8086, la memoria richiesta deve essere divisa un due “colonne” da 256kbyte, selezio-nate tramiteBHE e A0. Una, tra le molte possibili soluzioni,e quella di Figura 7.5.

Figura 7.5 Una possibile disposizione degli integrati nello spazio di memoria dell’Esercizio 7.1. Vengonoindicati i valori dei bit di indirizzo corrispondenti alle differenti posizioni. Poiche lo spezio degli indirizzicoperto corrisponde al mezzo megabyte inferiore, su tutta la memoria vale A19 = 0.

Per quanto si riferisce alla decodifica degli indirizzi, si osserva anzitutto che gli integrati relativial byte meno significativo devono essere selezionati da A0 (basso), mentre quello relativi al bit piusignificativo vengono selezionati da BHE (pure attivo basso). indicando con CSi i chip selectdegliintegrati, si ha:

CS5= BHE ·A19 ·A18 ·A17 CS0= A0 ·A19 ·A18

CS6= BHE ·A19 ·A18 ·A17 CS1= A0 ·A19 ·A18A17 ·A16

CS7= BHE ·A19 ·A18 ·A17 CS2= A0 ·A19 ·A18A17 ·A16

CS8= BHE ·A19 ·A18 ·A17 ·A16 CS3= A0 ·A19 ·A18A17 ·A16

CS9= BHE ·A19 ·A18 ·A17 ·A16 CS4= A0 ·A19 ·A18A17 ·A16

Dalle precedentie facile ricavare le forme corrispondenti allo schema di Figura 7.6. Ad esempio:

CS5= BHE ·A19 ·A18 ·A17 = BHE + A19 ·A18 ·A17

CS3= A0 ·A19 ·A18A17 ·A16 = A0 + A19 ·A18A17 ·A16

Esercizio 7.2

In questo caso si tratta di disporre di 8 colonne di 64Kb. Su tutti gli integrati deve essere A19 = A18 =A17 e A16 = 1. Ai due integrati da 64 Kb si portano A15−0; agli integrati di 32 Kb si portano A14−0,mentre A15 entra nel chip select; agli integrati di 16 Kb si portano A13−0, mentre A15 e A14 entrano purenel chip select; agli integrati di 8 Kb si portano A12−0, mentre A15, A14 e A13 entrano nel chip select. Inconclusione, con i numeri assegnati alle posizioni di Figura 7.7 si hanno i chip select seguenti:

CS0= A19 ·A18 ·A17 ·A16

CS1= A19 ·A18 ·A17 ·A16 ·A15 CS2= A19 ·A18 ·A17 ·A16 ·A15

CS3= A19 ·A18 ·A17 ·A16 ·A15 ·A14 CS4= A19 ·A18 ·A17 ·A16 ·A15 ·A14

CS5= A19 ·A18 ·A17 ·A16 ·A15 ·A14 CS6= A19 ·A18 ·A17 ·A16 ·A15 ·A14

64

Figura 7.6 Collegamento dei singoli integrati e rete di decodifica degli indirizzi (Esercizio 7.1). Gliintegrati sono numerati come in Figura 7.5.

CS7= A19 ·A18 ·A17 ·A16 ·A15 ·A14 ·A13 CS8= A19 ·A18 ·A17 ·A16 ·A15 ·A14 ·A13

CS9= A19 ·A18 ·A17 ·A16 ·A15 ·A14 ·A13 CS10=A19 ·A18 ·A17 ·A16 ·A15 ·A14 ·A13

CS11=A19 ·A18 ·A17 ·A16 ·A15 ·A14 ·A13 CS12=A19 ·A18 ·A17 ·A16 ·A15 ·A14 ·A13

CS13=A19 ·A18 ·A17 ·A16 ·A15 ·A14 ·A13 CS14=A19 ·A18 ·A17 ·A16 ·A15 ·A14 ·A13

Figura 7.7 Disposizione degli integrati per il caso dell’Esercizio 7.2.

Esercizio 7.3

Una soluzione ottimae quella di Figura 7.8. Ne derivano le seguenti espressioni per i chip select:

CS5 = BHE ·A19 ·A18 ·A17 CS0 = A0 ·A19 ·A18

CS6 = BHE ·A19 ·A18 ·A17 CS1 = A0 ·A19 ·A18 ·A17

CS7 = BHE ·A19 ·A18 ·A17 ·A16 CS2 = A0 ·A19 ·A18 ·A17... CS3 = A0 ·A19 ·A18 ·A17 ·A16

CS11 = BHE ·A19 ·A18 ·A17 CS4 = A0 ·A19 ·A18 ·A17 ·A16

65


Esercizio 7.4

Occorre anzitutto osservare che il blocco di memoria di 512 Kb che inizia dalla posizione A00000 deter-mina la struttura degli indirizzi di Tabella 7.1 (da A00000 a A7FFFF). Comee noto A0 e A1 non sono

A31 . . . A24 A23 A22 A21 A20 A19 A18 . . . A2 A1 A0

0 . . . 0 1 0 1 0 0 ←− . . . −→ ←− −→

Tabella 7.1 Struttura degli indirizzi per l’Esercizio 7.4.

disponibili in quanto essi sono sostituiti dai 4 segnali BE0 . . . BE3. In base alla taglia degli integrati lasoluzione ottimae quella della Figura 7.9. Ne derivano le seguenti espressioni per i chip select:

CS0 = SEL · BE0

CS10 = SEL · BE1 ·A18 CS11 = SEL · BE1 ·A18

CS20 = SEL · BE2 ·A18 CS21 = SEL · BE2 ·A18 ·A17...

...

dove il segnale SEL decodifica il campo di indirizzi corrispondenti al blocco ovvero:

SEL =A31 ·A30 · . . . ·A24 ·A23 ·A22 ·A21 ·A20 ·A19.

Esercizio 7.5

In questo caso si richiede che un blocco di 2 MByte sia dislocato a partire da un confine corrispondentea 1 MByte come illustrato in Figura 7.10. La Figura 7.10 indica chiaramente che se venissero usatiintegrati di 512 KByte questi non cadrebbero su un confine naturale e la decodifica si complicherebbealquanto. Dunque conviene rinunciare all’integrato da 512 KByte e utilizzare quelli di taglia inferiore.Con gli integrati disponibilicome da testo dell’Esercizio verrebbe a mancare la copertura di due fasce di512 KByte. Se ne deduce che il problemae mal posto. In Figura 7.11 si da una soluzione che assume ladisponibilita di 6 integrati da 256 KByte.

L’indirizzo esadecimale di partenzae 100000, dunque, per la selezione, devono essere decodificatiA31−21 = 0, A20 = 1, per tutti gli integrati.

66

Figura 7.9 Schema di memoria dell’Esercizio 7.4.

Figura 7.10 Schematizzazione del problema dell’Esercizio 7.5. A sinistra viene la divisione della memo-ria nello spazio effettivo degli indirizzi, a destra relativamente a una singola fascia corrispondente ad un1 byte della parola (ovviamente le dimensioni e gli indirizzi relativi della singola fascia sono quelli effettividivisi per 4).

Esercizio 7.6

Oltre all’integrato di 1MB e ai due da 512KB, occorrono 8 integrati da 256KB.

67

Figura 7.11 Schema di memoria dell’Esercizio 7.5 con la disponibilita di 6 integrati da 256 KByte.

L’indirizzo (esadecimale) di partenzae 400000, dunque, per la selezione, devono essere decodificatiA31−23 = 0, A22 = 1, per tutti gli integrati. All’integrato da 1MB vengono portati A21−2; ai due da512KB vengono portati A20−2, mentre A21 entra nella decodifica del chip select; agli integrati da 256KBvengono portati A19−2, mentre A21 e A20 entrano nella decodifica del chip select. Naturalmente nell’e-spressione del chip select entrano anche iBHi. Ad esempio, supponendo che l’integrato da 1MB vada acoprire il byte meno significativo, il relativo chip select sara dato da:A31 ·A30 · · ·A23 ·A22 · BH0. Seil byte piu significativoe ottenuto con 4 integrati da 256KB, quello posto nella parte piu alta avra questochip select:A31 ·A30 · · ·A23 ·A22 ·A21 ·A20 · BH3.

Esercizio 7.7

La soluzionee immediata in quanto la capacita totalee data dal prodotto dei termini riportati nel testo:

Capacita Totale =4096× 8× 1024× 512 = 16384 MB.

Esercizio 7.8

Il disco nell’esempio del Paragrafo 7.6 del testo ha una velocita di 5400 rpm, ovvero 90 giri al secondo.La velocita di trasferimentoe data dal rapporto tra il numero di byte che si trovano su una traccia e iltempo richiesto a effettuare un giro (si trascurano gli effetti legati al passaggio da settore a settore sullastessa traccia). Indicando conv la velocita di trasferimento in byte al secondo e cong il numero di girial secondo, si ha:

v = n byte per traccia× n giri al secondo

ovvero si ha che ogni traccia deve contenere:

byte per traccia =v

g=

4Mbyte/sec

90 giri/sec= 46603

Ogni settore ha una capacita di 512 byte, quindi, il numero di settori per tracciae di:

46603512

= 91 settori per traccia.

68

Esercizio 7.9

Si ricorda che in base alla (7.7) del testo, il tempo medio di accessoe:

t = hts + mtp

dove:

• t e il tempo medio di accesso al livello superiore• h e il tasso di hit al livello superiore• m e il tasso di miss(h + m = 1)• ts e il tempo di accesso al livello superiore• tp e il tempo di penalizzazione

Nel nostro caso il tempo di penalizzazionee preso pari al tempo di accesso al livello inferiore. Si hadunque:

35 = h4 + m35

Risolvendo perh, (h + m = 1) si ottiene:

4, 5 = h 4 + 35− 35h

da cuih = 0, 98.

Esercizio 7.10

I dati in questo caso sono:t = 8 ms.ts = ?h = 0, 92m = 0, 08Il tp vale il tempo di accesso al secondo livello piu il tempo di trasferimento, pari al 30%. Dunque:tp = 60 + 0, 30 · 60 = 60 + 18 = 78 ms.

Sostituendo nella (7.7) del testo si ha:

8 = 0, 92 ts + 0, 08 · 78

ovvero:

0, 92ts = 8− 6, 24 = 1, 76

da cui deriva che il tempo di accesso al livello superiorets e pari a1, 91 ms.

69

8

Esercizio 8.1

L’interfaccia richiesta non differisce molto da quella di Figura 8.10 del testo. Si differenzia solo per ilfatto che c’e una esplicita modalita di funzionamento data dal valore della coppia di bit [0,1] del registroCREG. Lo schema dell’interfacciae in Figura 8.1.

Figura 8.1 Rispetto all’interfaccia di Figura 8.10 del testo sono state aggiunte le porte che decodificanola modalita di funzionamento dell’interfaccia e che ne condiziono il funzionamento. Lo schema nonmostra la decodifica degli indirizzi; si noti che di DPORT e SREG sono allo stesso indirizzo, mentrel’indirizzo di CREG e necessariamente diverso.

Esercizio 8.2

La difficolta dell’esercizio sta nel dover provvedere una mappatura variabile di ARRAYIN in memoria.La decodifica degli indirizzi deve riuscire a individuare se l’indirizzo di lettura di memoria corrisponde auna locazione su cui in quel momentoe mappata una posizione di ARRAYIN. In tal caso la lettura deveessere trasformata in lettura in ingresso/uscita.

Cominciamo con l’osservare che nel registro XAR andra messa la base di partenza corrente di AR-RAY IN, il cui valore e determinato BAR. Assumiamo per un momento che XAR sia a 16 bit. Dalconfronto dei bit [15-12] di XAR con i corrispondenti bit del bus indirizzi, si riesce a stabilire se l’indi-rizzo generato dalla CPU cade in uno degli intervalli di mappatura. Poiche ARRAY IN ha la dimensionedi 1 kbyte, occorre assicurarsi che l’indirizzo generato sia effettivamente entro uno spazio di 1 k a partiredalla base corrente. Cio richiede che il campo di bit [11-10] del bus degli indirizzi contenga zero, ovveroche il confronto tra bus indirizzi e XAR venga esteso in modo da comprendere anche i bit [11-10], che,per costruzione, sono “0” in XAR.

Si puo ora osservare che none necessario che XAR sia a 16 bit, in quanto ai fini del confronto dicui sopra bastano soli sei bit. Si puo quindi usare un latch a 8 bit per XAR. Lo schema della logica chegenera il segnale di lettura di ARRAYIN e in Figura 8.2.

Figura 8.2 Il registro XAR e formato da un latch a 8 bit (la cui uscita e mantenuta sempre abilitata). Inumeri riportati all’interno dei bit di XAR corrispondono ai numeri d’ordine delle linee di indirizzo dellabase di ARRAY IN. I bit denominati 11 e 10 sono necessariamente sempre a “0”, mentre solo un bit, tra15, 14, 13 e 12 e a “1” in un dato istante. Il blocco COMP confronta i due ingressi (di 6 bit) e produceun’uscita vera se i due sono uguali. Nel tracciare lo schema si e supposto l’indirizzo in I/O di XARsia su 8 bit. Il segnale AR RD viene asserito quando la CPU effettua un ciclo di lettura della memoriaad un indirizzo che cade nel campo di 1 kbyte su cui in quel momento e mappato ARRAY IN. AR RDviene quindi utilizzato come segnale di abilitazione del periferico (per esempio come Output Enable dellaposizione individuata attraverso l’indirizzo su [A9-A0]). Se l’indirizzo generato dalla CPU non cade sulcampo di cui sopra, viene asserito il segnale MEM RD di lettura della memoria.

Il codice assembler corrispondente alla parte che chiama la routine MAPTO M e questo:

B_AR EQU 0E0HXAR EQU 0E2H

........MOV BX, 01000HIN AL, B_AR ;Lettura di B_ARADD AL,0 ;ai fini del testJZ CHIAMA ; case 0: mappatura a 1000MOV BX, 02000HSUB AL,1JZ CHIAMA ; case 1: mappatura a 2000MOV BX, 04000HSUB AL,1JZ CHIAMA ; case 2: mappatura a 4000MOV BX, 08000H ; case 3: mappatura a 8000

CHIAMA: OUT XAR, BH ;Predisposizione mappaturaCALL MAP_TO_M

MAP TO M assume l’aspetto che segue.

MAP_TO_M: MOV CX, 1024 ;Inizializzazione contatoreCICLO: MOV AL, [BX] ;Lettura generico elemento di ARRAY_IN

MOV [BX], AL ;Copiatura in memoriaINC BX ;Puntamento al prossimoLOOP CICLORET

72

Esercizio 8.3

Poiche a fronte di un bus dati a 8 bit l’interfaccia deve presentare 64 bit verso l’esterno, occorre prevederegli elementi di memoria necessari a mantenere l’informazione trasmessa dalla CPU. La cosa piu naturalee utilizzare 8latcha 8 bit, secondo lo schema di Figura 8.3.

Figura 8.3 Struttura dell’interfaccia con 8 latch da 8 bit. Il generico latch viene indicato con Li (i =0, 1, ..7) mentre LEi rappresenta il relativo segnale di Latch Enable che determina la memorizzazionesu Li degli 8 bit in ingresso. L’uscita del singolo latch e sempre abilitata. Il latch imo fornisce le 8 usciteda U8i+0 a U8i+7.

Essendo richiesto che la routineSETBIT aggiorni uno solo dei 64 bit di uscita, ogni scrittura sull’inter-faccia dovra avvenire in modo tale che:

a) venga scritto il latch contenente il bit selezionato;b) venga modificato il solo bit di interesse lasciando immutati i rimanenti 7.

Per rendere verificata la condizione del punto b) si puo procedere in questo modo:

1) leggere lo stato del latch su cui avviene la scrittura;2) portare a zero il bit nella posizione corrispondente a quella da aggiornare, mantenendo invariati gli

altri bit. Questo risultato si ottiene con una semplice operazione di AND con una maschera che ha “0”nella posizione da aggiornare e “1” in tutte le altre;

3) portare il bit di interesse al valore voluto. Questo risultato si ottiene effettuando una semplice opera-zione di OR.

Resta ora da stabilire come si individua il latch di destinazione e la posizione del bit di interesseentro il medesimo. Il numero d’ordine del latche dato dal quozienteQ = x/8 (parte intera), mentrela posizione entro il latche data dal restoR della medesima divisione. In termini di programmazioneassembler non conviene calcolareQ e R con operazioni di divisione1. Conviene piuttosto ragionarecome segue. Il numerox si trova sicuramente nei 6 bit meno significativi di CX all’atto della chiamatadi SETBIT . E’ facile verificare che il valore diQ e contenuto nel campo di bit [5..3] di CX, mentre ilcampo [2..0] contieneR.

Indicando conPORTl’indirizzo di base dell’interfaccia, l’indirizzamento dei singoli latch si ottienein questo modo:

MOV DX, CX ; DX:= xSHR DX, 3 ; DX:= parte intera di = x/8ADD DX, PORT ; DX:= indirizzo del latch di destinazione

Conviene assegnare all’indirizzo di base dell’interfaccia (PORT) un valore multiplo di 8 in modo cheesso venga decodificato attraverso i bitA7 −A3 (si assume che gli indirizzi di I/O stiano sempre negli8 bit della parte bassa dell’indirizzo), mentre la decodifica del contenuto diA2 −A0 fornisca il selettoredello specifico latch indirizzato. In conclusione si ottiene lo schema di Figura 8.4.

1Il lettore verifichi questa affermazione esaminando il repertorio di istruzioni 8086, analizzando come si effettua la divisionetra interi e che risultati determina.

73

Figura 8.4 Schema di decodifica degli indirizzi. Si suppone che gli indirizzi delle porte di I/O sianosempre su 8 bit, anche se trasmessi attraverso DX. Si e fatta l’ipotesi che l’interfaccia sia all’indirizzo dibase F0.

Resta infine da stabilire come si effettua la sequenza di operazioni dei precedenti punti 1), 2) e 3).Per quanto si riferisce alla determinazione dello stato del latch ci sono due alternative. La prima consistenel fare tutto per via software, ovvero prevedere un numero adeguato di variabili (di stato) interne allaroutineSETBIT che tenga traccia dello stato dei latch; la seconda consiste nel prevedere sull’interfacciala logica che permette si leggere lo stato dei latch stessi. Ovviamente la seconda soluzionee la piu“costosa” in quanto richiede della logica aggiuntiva.

Incidentalmente osserviamo che nella progettazione si presenta non di rado la necessita di decidere,per alcune delle funzionalita che un sistema deve svolgere, la loro ripartizione tra hardware e software.Il criterio generalee quello di cercare il miglior rapporto costo/prestazioni, che di solito si traduce nelfare eseguire al software quanto piu possibile. Nel caso specifico si tratta di tenere traccia in memoriadello stato dei latch, anziche prevedere la loro lettura. In generale, le soluzioni in software hanno ancheil pregio della flessibilita, mentre, al contrario, le soluzioni hardware hanno lo svantaggio della rigidita.L’allocazione di funzionalita a componenti hardware ha senso solo quando il loro svolgimento softwaree sconsigliato per motivi di assoluta inefficienza o perche la complessita che si introduce nel softwareetale da farle preferire l’aggiunta di una parte hardware specializzata.

In base ai precedenti ragionamenti occorre prevedere un vettore di 8 byte per tener traccia dello statodegli 8 latch. Chiameremo tale vettoreCOPIA. Il tratto di codice commentato che segue illustra come sieffettua la sequenza di operazioni corrispondenti ai punti 1), 2) e 3) e gli altri dettagli di programmazionedi SETBIT .

Il vettoreCOPIAsara cosi dichiarato (nel segmento dati).

COPIA DB 8 DUP (0) ; 8 byte di copia inizializ. a ‘‘0’’

La routineSETBIT (facente ovviamente parte del segmento di codice) assume questo aspetto.

SETBIT:MOV DX, CX ; DX:= xSHR DX, 3 ; DX:= parte intera del quoziente Q = x/8ADD DX, PORT ; DX:= indirizzo del latch di destinazione

;;Costruzione dell’indice in COPIA (l’indice e uguale a numero d’ordine del;latch);

MOV BX, CX ;SHR BX, 3 ; BX:= indice in COPIA

;AND CL, 111B ;CL:= R (posizione entro il latch)SHL AL, CL ;Posizionamento del bit da scrivere

;MOV AH, 1 ;PreparazioneSHL AH, CL ; della maschera di "1" eccettoXOR AH, 0FFH ; lo "0" nella posizione di interesseAND AH, COPIA[BX] ;AH:= copia latch con "0" in posizione

;OR AL, AH ;Aggiunta del bit dato

74

MOV COPIA[BX], AL ;Aggiornamento della copiaOUT [DX], AL ;Scrittura sulla porta

;RET

Osservazione.Come indicato in precedenza si poteva progettare l’interfaccia in modo da dotarladella logica per leggere lo stato dei latch. Il lettoree invitato a svolgere il relativo progetto e apportare lenecessarie modifiche aSETBIT .Una variazione sul tema.Si provi a progettare l’interfaccia che opera un modo duale rispetto a quellavista, nel senso che essa deve leggere un bit selezionato da un insieme di 64 ingressi digitali. La relativaroutine di gestioneGETBIT viene chiamata esattamente comeSETBIT , dove orax rappresenta il nu-mero d’ordine dell’ingresso digitale da leggere; la routineGETBIT restituisce nel bit 0 di AL il valoredell’ingresso digitale letto.

Si verifichi che, in linea di principio, questa interfaccia si riduce a un “grosso” selettore (multiple-xer) da 64 in 1. Se si pensa di realizzare l’interfaccia con componenti discreti non programmabili, lafunzionalita di un tale selettore deve essere costruita a partire, per esempio, da 8 selettori 8 in 1. Si puotuttavia scoprire che la soluzione piu conveniente consiste invece nel prevedere 8 semplici buffer da 8bit, lasciando al programma il compito di isolare il bit di interesse tra gli otto letti.

Esercizio 8.7

Per il buon funzionamento del driver si presuppone che la sezione di inizializzazione venga chiamata soloe sempre quando none in corso un trasferimento, cosa di cui il programmatore puo accertarsi testandolo stato della variabileBUSY.

Se assumiamo che il driver venga chiamato mentree in corso un trasferimento e facciamo l’ipotesiche durante l’esecuzione del tratto di codice della sezione di inizializzazione non si manifesti l’interruzio-ne, l’effetto della routine di inizializzazionee riconfermareBUSYasserita ma anche quello di aggiornarela variabile che tiene traccia dell’indirizzo del prossimo byte da trasmettere e della variabile di conteggio;inoltre viene trasmesso un carattere al dispositivo esterno.

La trasmissione di questo carattere puo determinare un effetto impredicibile, nel senso che essodipende dalla natura del periferico e da quantoe progredito il trattamento del carattere precedente. Inogni caso, al manifestarsi dell’interruzione, essendo cambiati l’indirizzo di prelievo e il contatore, latrasmissione dei caratteri verso l’esterno procedera sulla base dei nuovi valori assunti da le rispettivevariabili. Se, per esempio, si ipotizza di avere a che fare con una stampante, l’effetto macroscopicosarebbe l’abbandono della stampa in corso e il passaggio, senza soluzione di continuita, alla stampa delcontenuto dell’area di memoria specificata con la chiamata al driver.

L’interruzione puo anche pervenire mentree in corso di esecuzione proprio la sezione di inizializ-zazione. Si lascia al lettore l’analisi dei possibili casi che si possono determinare a seconda del punto incui si manifesta l’interruzione.

Esercizio 8.9

Sull’interfacciae necessario un contatore modulo 4, che venga caricato con il valore contenuto in ALall’atto dell’operazione diOUTe il cui stato fornisca il selettore del byte da leggere. Inoltre ad ognilettura il contatore deve avanzare. Queste considerazioni portano allo schema di Figura 8.5.

Esercizio 8.12

L’interfaccia deve prevedere, oltre al registro REG, un comparatore che asserisca la richiesta di interru-zione e la logica che porta a copiare gli ingressi in REG ad ogni lettura. Il possibile schemae mostratoin Figura 8.6.

Per quanto si riferisce alla routine di interruzionee necessario prevedere una variabile interna chetiene traccia dell’ultima lettura degli ingressi. Indichiamo conCOPIA tale variabile; essa dovra essereinizializzata all’atto dell’attivazione dell’interfaccia. Nel segmento dati dovranno esser previste questedichiarazioni:

......PUBLIC VAR

COPIA DB ? ;Copia degli ingressi

75

Figura 8.5 Schema dell’interfaccia per l’Esercizio 8.9. Il contatore modulo 4, indicato come C/4, ha unacoppia di ingressi che servono a precaricare lo stato di partenza. Il caricamento ha effetto quando vieneasserito l’ingresso Load, ovvero quando la CPU effettua una scrittura all’indirizzo dell’interfaccia (70).Le letture determinano l’abilitazione dell’uscita del buffer selezionato attraverso il contatore. Sul frontedi salita del segnale PRD il contatore avanza.

Figura 8.6 Schema dell’interfaccia per l’Esercizio 8.12. Si noti che quando il comparatore COMP rilevache gli ingressi sono diversi dal contenuto di REG, il flip-flop IFF si porta in stato alto e vi resta finoalla prossima lettura. Non e stata tracciata la rete che corrisponde al comparatore COMP, trattandosidi un banale esercizio di impiego di porte XOR. Non viene neanche mostrata la logica di decodificadell’indirizzo che genera SEL. Si noti che, essendo l’indirizzo dell’interfaccia 240 (esadecimale), occorreutilizzare DX per trasmettere l’indirizzo. L’interfaccia si abilita/disabilita trasmettendo 1/0 su D0. Sinoti che gli ingressi vengono memorizzati in REG al termine della lettura. Si osservi anche che perinizializzare l’interfaccia basta effettuare una lettura e quindi abilitarla all’interruzione.

VAR DB ? ;Variabile resa globaleINGR EQU 0240H ;IEN EQU INGR ;

......

La routine di servizio dell’interruzione corrisponde a questo codice:

INTRSEC: PUSH AX ;Salvataggio deiPUSH DX ; registri usati

76

MOV DX,INGR ;DX:= indirizzo porta di ingressoIN AL,[DX] ;Lettura della portaMOV AH,COPIAXOR AH,AL ;Trova i bit cambiatiMOV VAR,AH ; e li scrive in VARMOV COPIA,AL ;Copia ultima letturaPOP DX ;Ripristino deiPOP AX ; registri modificatiIRET

Esercizio 8.14

L’esercizio non presenta particolari difficolta dal punto di vista della logica dell’interfaccia. Uno schemapossibilee in Figura 8.7.

Figura 8.7 Schema dell’interfaccia per l’Esercizio 8.14.

Piu interessantee invece la ricerca di un algoritmo per ilDRIVER. Quello che segue opera in questomodo:

a) viene prima individuata la porta, ovvero la coppia di gruppi, su di cui deve avvenire la scrittura;b) si stabilisce se i 4 bit da modificare devono andare nella parte alta o bassa della porta;c) in base alla risultanza del punto b) si forma il byte da trasmettere.

DRIVER: MOV DX,0F0H ;Base dell’interfacciaMOV CL,AH ;AH = numero del gruppoAND CL,010B ;Si isola il bit 1 del selettore di gruppoJZ AVANTI ;Se "0" Sono stati scelti G1-G0INC DX ;Sono stati scelti G3-G2: adeguamento DX

AVANTI: IN BL,[DX] ;Lettura della portaAND AH,01B ;Si isola il bit 0 del selettore di gruppoJZ PARI ;Vale "0" per G0 e G2

;;Il controllo arriva alla parte che segue se si tratta di trasmettere;i 4 bit contenuti in AL sulla parte alta (G1 o G3) della porta .;

SHL AL,4 ;Posizionamento nuovo dato da trasmettereAND BL,0FH ;Isolamento parte invariata (di G0 o G2)OR AL,BL ;Formazione byte

EXIT: OUT [DX],AL ; e sua trasmissioneRET

;;Il controllo arriva alla parte che segue se i 4 bit contenuti in AL;devono essere trasmessi nella parte bassa (G0 o G2) della porta.

77

;PARI: AND BL,0F0H ;Isolamento parte invariata (di G1 o G3)

OR AL,BL ;Formazione byteJMP EXIT

Si noti che l’algoritmo precedente si basa in modo rilevante sul fatto che le porte sono 2. Il lettore provia generalizzare il problema, assumendo un numero qualsivoglia di porte.

Esercizio 8.16

Questo esercizio, almeno per quanto riguarda la logica, ha molte similitudini con gli esercizi 8.3 e 8.7.Lo schemae in Figura 8.8. La routine LOOKUP risulta invece di una certa complessita. Circa la modalitadi numerare i bit si faccia riferimento alla soluzione dell’Esercizio 8.3.

Figura 8.8 Schema dell’interfaccia per l’Esercizio 8.16. Il blocco di destra e un latch le cui uscite sonotenute sempre abilitate. Poiche in lettura viene usato il registro DX, si e ipotizzato di decodificare 20 bitdi indirizzo.

Saltiamo la stesura del diagramma di flusso, che lasciamo come compito non risolto al lettore, epassiamo direttamente a costruire la routine INITLKUP. Essa deve solo leggere ordinatamente le portedi ingresso memorizzare i valori letti in un vettore di appoggio, di 8 posizioni, che chiameremoCOPIA.

INITLKUP: MOV CX,8 ;CX: contatoreMOV DI,0 ;DI: indiceMOV DX,PORT ;DX: indirizzo base dell’interfaccia

;READ0: IN AL,[DX] ;Lettura

MOV COPIA[DI],AL ; memorizzazioneINC DX ;Puntamento alla porta successivaINC DI ; e incremento indiceLOOP READ0MOV DX,PORT ;DX: indirizzo porta di uscitaMOV AL,0FFH ;Inizializzata dicendo:OUT [DX],AL ; "non ci sono cambiamenti"RET

Piu difficile e scrivere LOOKUP. Al fine di evitare di costruire un algoritmo troppo intricato, convie-ne dividere LOOKUP in due parti: la prima dedicata a leggere gli ingressi, aggiornare il vettoreCOPIAe costruire il vettoreCAMBIATI; la seconda a determinare il numero d’ordine richiesto.

Per quanto abbiamo detto nel segmento dei dati si avranno questi statement:

...........COPIA DB 8 DUP (?) ;64 bit copia ultima letturaCAMBIATI DB 8 DUP (?) ;64 bit per tener traccia dei cambiati

...........

La prima parte di LOOKUP corrisponde al seguente codice:

78

LOOKUP: MOV CX,8 ;CX: ContatoreMOV DI,0 ;DI: indiceMOV DX,PORT ;DX:= indirizzo base dell’interf.

READ: IN AL,[DX] ;LetturaXOR AL,COPIA[DI] ;Calcola i cambiamentiMOV CAMBIATI[DI],AL ; e li memorizza in CAMBIATIXOR AL,COPIA[DI] ;Ripristina in AL la letturaMOV COPIA[DI],AL ; e memorizza in COPIAINC DX ;Puntamento alla porta successivaINC DI ; e incremento indiceLOOP READ

;Al termine del ciclo COPIA contiene l’ultima lettura dei 64 ingressi....segue.......

La seconda parte di LOOKUP ha lo scopo di determinare il numero d’ordine del piu basso ingressomodificato. Si tratta di effettuare la scansione del vettoreCAMBIATI, arrestandosi al riconoscimento delprimo bit a “1”. A scopo didattico, nello stendere questa parte, anziche nominare direttamente il vettoreCAMBIATI, lo si indirizza attraverso BX in modo da avere pronto il puntatore all’uscita diLOOKUP.

....segue.......MOV CX,8 ;ContatoreMOV DI,0 ;IndiceMOV BX,OFFSET CAMBIATI ;Scostamento di CAMBIATIMOV AH,0 ;AH dir a quale byte

TESTBYTE: MOV AL,[BX][DI] ;Salto a THISBYTE se....SUB AL,0 ;JNZ THISBYTE ;....c’ e almeno una variazioneINC AH ;Forse nel prossimo byteINC DILOOP TESTBYTE

;;Se il controllo arriva qui non c’ e stato alcun cambiamento;

MOV AH,0FFH ;Segnala nessun cambiamentoEXIT: OUT PORT,AH

RET;THISBYTE:;Il numero d’ordine del primo byte che presenta un cambiamento e in AH;lo si moltiplica per 8;

SHL AH,3 ;La parte alta del numero d’ordine;;Resta da ora trovare entro questo byte il bit variato di ordine minore;

MOV CX,8MOV DL,0 ;DL: posiz. del bit entro il byte

TESTBIT: MOV DH,AL ;DH copia di appoggioAND AL,1 ;Isola il bit in posizione 0JNZ THISBIT ;Salto se cambiatoINC DL ;ConteggiaMOV AL,DH ;Si riprende il byteSHR AL,DL ;Avanti col prossimo bitLOOP TESTBIT

;;Se il controllo arriva qui c’ e un errore: un byte indicava cambiamento;ma nessun bit sembra modificato. Un buon programma dovrebbe prevedere;una qualche azione di recupero. Si "finge" di saltare a un analizzatore;di disastro;

79

JMP DISASTRO;;Il numero d’ordine del bit e in DL;THISBIT: OR AH,DL ;Unione parte alta e bassa

JMP EXIT

La scrittura di LOOKUPe conclusa.

Osservazione.La routine LOOKUPe stata divisa in due parti. E’ evidente che il numero da presentaresulla porta di uscita poteva essere determinato anche all’interno del ciclo di lettura delle porte di ingresso.Il lettore e invitato a riscrivere LOOKUP in modo che operi in tal senso.

Ulteriori miglioramenti, sia estetici che di efficienza, possono essere apportati evitando i doppicontatori (CX e AH, oppure CX e DL) e utilizzando istruzioni che effettuano direttamente il test deibit.

Esercizio 8.22

Risolveremo l’esercizio senza tener conto della catena IEI-IEO; le estensioni relative sono abbastanzaimmediate.

Essendo la richiesta di interruzione di breve duratae necessario prevedere un flip-flop che memorizzila richiesta stessa. Lo schema della logica di daisy chaine in Figura 8.9.

Figura 8.9 Logica per l’Esercizio 8.22. Si e ipotizzato che la selezione dell’interfaccia faccia disasserirela richiesta di interruzione. Si noti che, essendo INTA attivo basso, non il fenomeno aleatorio non sipresenta su INTAO e quindi non e necessario l’elemento di ritardo come nelle Figure 8.20 e seguentinel testo.

Esercizio 8.23

Poiche in presenza di piu interruzioni deve presentare il VT relativo a quella piu prioritaria, si rendenecessario un codificatore di priorita (priority encoder, PE). PEe rappresentato come un blocco a 8ingressi e 3 uscite, sulle qualie codificato il numero d’ordine dell’ingresso piu prioritario asserito2;l’uscita di PE, abilitata dal segnale INTA, viene usata per formare ilvector typee pilotera i 3 bit menosignificativi del bus dati. Lo schema del PICe in Figura 8.10.

Le 3 righe di codice seguente predispongono la base dei vettori all’indirizzoCO. Si noti che in questocaso, essendo la base minore di 256 sie caricato il solo registro AL; se la base fosse stata compresa tra256 e 1024 occorreva caricare il registro AX. In ogni caso la divisione per 4 (l’istruzioneSHR) riportaentro il byte e quindi l’istruzioneOUTresterebbe invariata.

2Il lettore e invitato esaminare i dati di catalogo dei prodotti commerciali, apportando allo schema eventuali modifichedettate dal loro reale modo di funzionare.

80

Figura 8.10 Logica per l’Esercizio 8.23. Il registro di mascheramento M, come il registro T (per ilVT) sono programmabili. Il contenuto del registro M e leggibile direttamente da programma. Non estato tracciata la logica che genera i comandi RDM, WRM e WRT. Si deve assumere che al dispositivocorrispondano almeno due indirizzi, relativi al registro M e al registro T.

;; TPORT e l’indirizzo del registro T;

MOV AL, 0C0H ;Indirizzo base dei vettori di interr.SHR AL,2 ; nel PIC deve andare diviso per 4OUT TPORT,AL ;

Il seguente tratto di codice porta a 1 il bit 5 di M, lasciando immodificati gli altri bit.

;; MPORT e l’indirizzo del registro M;

IN AL,MPORTMOV AL,00100000B ; Bit 5 a 1; gli altri invariatiMOV MPORT,AL

Esercizio 8.24

Per quanto riguarda la logica dell’interfaccia, concettualmente essa none dissimile da quella dell’inter-faccia dell’Esercizio 8.12, al quale rimandiamo. Per quanto si riferisce al testo assembler della routine ainterruzione, si noti che occorrono almeno due contatori:CONT10per tener traccia del numero d’ordine(da 0 a 9) dell’interruzione corrente eCONTDUTYper tener traccia delle interruzioni che devono dareun’uscita alta. Infine, occorre una variabile (logica), che denomineremoA B per dire se sie nella partein cui l’uscita va tenuta a “1” o in quella in cui deve essere “0”. Le tre variabili potranno essere definitecome byte nel segmento dati.

INTPW: PUSH AXPUSH CX

IN AL, PORT ;Lettura della portaMOV CH,CONT10 ;Contatore per 10DEC CHJZ NUOVOPER ;se 0 e la fine di un periodo

;;Non e l’inizio di un periodo: c’ e da decidere come pilotare;il bit 0 di PORT;

81

MOV CONT10,CH ;Aggiornamento contatore in memoriaMOV AH,A_BJZ LOW ;Se 0 siamo nella seconda faseMOV CL,CONTDUTY ;Siamo nella prima faseDEC CL ;JZ ABBASSA ;Se 0 e la fine della prima fase

EXIT1 OR AL,1 ;Trasmette "1"EXIT: OUT PORT,AL

MOV CONTDUTY,CL ;Aggiornamento CONTDUTYPOPIRET

;ABBASSA: XOR AH,AH ;Si passa alla seconda fase

MOV A_B,AH ;A_B:= 0LOW: AND AL,0FEH ;Trasmette "0"

JMP EXIT;NUOVOPER: MOV CH,10 ;Inizializzazione contatore

MOV CONT10,CH ; di periodoMOV AH,1 ;Inizializzazione variabileMOV A_B,AH ; di statoMOV CL,N ;Duty cycleJMP EXIT1

Esercizio 8.28

Il possibile malfunzionamentoe questo. Si supponga che sia in corso un ciclo di INTA, in risposta a unarichiesta di interruzione effettuata da un periferico meno prioritario di quello in questione. In tale ciclo lalinea INTAO risulta asserita. Se nel corso del ciclo di INTA viene ora asserita la richiesta di interruzioneIRQ, la linea INTAO passa allo stato “0”. Ovviamente il tutto avviene in modo completamente casuale,in dipendenza dalla tempificazione dei segnali.E possibile che INTAO sia rimasta asserita quanto bastaa selezionare l’interfaccia a valle.E pero possibile che IRQ sopravvenga immediatamente dopo il frontedi INTA. In tal caso, mentre none detto quel che puo accadere a valle, l’interfaccia in questione none ingrado di selezionarsi in quanto SFF non ha commutato sul fronte di INTA.

Esercizio 8.33

Se SFF passa a “0” con il sistema di interruzione abilitato e a vallee asserita una IRQ, questa determinaimmediatamente un’interruzione (sempre che IEI in ingresso alla relativa interfaccia sia a “1” e non siadisasserita per effetto di qualche interfaccia intermedia) che ha l’effetto di interrompere la routine incorso. In altre parole, una routine meno prioritaria interrompe una piu prioritaria. Se si vuole evitarequesta “inversione della priorita” occorre che la riabilitazione del sistema di interruzione (flip-flop IE)sia l’ultima azione effettuata dalla routine in corso di esecuzione.

In questo modo si perde pero l’annidamento delle interruzioni (le piu prioritarie che interromponole meno). Il modo corretto di operaree un altro: riabilitare il sistema di interruzione durante la routinedi servizio, ma riportare SFF a “0” solo al termine della routine medesima.

Esercizio 8.35

Il progetto dell’interfaccia verra svolto in modo intuitivo e non formale. Per semplicita si fa l’assunzioneche la richiesta di interruzione generata dal periferico si mantenga almeno fino al momento in cui non siha la selezione. Si puo ragionare in questo modo:

a) quando viene asserita la richiesta di interruzione IRQ del periferico, la linea INT viene asserita solo see asserita IEI;

a) suk clock che campiona INTA asserito, se permangono le condizioni del punto precedente, si determinail passaggio allo stato “1” del flip-flop FF1, la cui uscitae in ingresso a un secondo flip-flop D (FF2);conseguentemente FF2 porta in stato “1” al clock successivo;

82

c) sull’ulteriore clock, il flip-flop SFF passa allo stato “1” se IEIe rimasto a “1”, ovvero se le interfaccea monte, non hanno fatto richiesta di interruzione. Si noti che Sono passati due periodi di clock daquando la linea INTAe stata campionata asserita. L’interfaccia risulta selezionata, IEOe disasseritocome pure IACK, che pero resta asserito solo per un ciclo (il prossimo clock riporta il FF2 in stato“0”);

Lo schema dell’interfaccia che opera come soprae in Figura 8.11.

Figura 8.11 Schema della logica di daisy chain sincrona per l’Esercizio 8.35. Si e supposto che l’even-tuale flip-flop di memorizzazione della richiesta di interruzione faccia parte delle logica del periferico. Sinoti che INTA non esce verso valle, in quanto arriva in parallelo a tutte le interfacce. Il segnale IACK hala durata di un ciclo di clock.

Si invita il lettore a effettuare il progetto in modo rigoroso, utilizzando il diagramma degli stati eprovvedendo a sintetizzare la rete.

83

9

Esercizio 9.1

Nell’architettura 8086 il segnale ALE (Address Latch Enable) viene asserito dalla CPU per indicare almondo esterno che essa sta pilotando il bus AD0-AD15 con un indirizzo. In particolare, viene asserito sulprimo periodo di clock. Il segnale puo essere utilizzato per memorizzare l’indirizzo su un latch esterno.

Esercizio 9.2

Le istruzioniMOV, JMPePUSHnon hanno effetto sui bit di stato. Per quanto riguarda le rimanenti, essehanno l’effetto illustrato.L’istruzioneADDha effetto sui flag: OF, SF, ZF, AF, CF,e PF, in accordo con il risultato della somma.

Per quanto riguarda l’istruzioneIMUL faremo riferimento all’architettura IA-321. L’istruzioneIMUL:

• Puo operare su registri o locazioni di memoria a 8,16 o 32 bit.• Ha 3 modalita di impiego, con 1,2 o 3 parametri.

Schematicamente le possibili forme dell’istruzione sono:

IMUL SRCIMUL DEST,SRCIMUL DEST,SRC1,SRC2

Nel primo casoSRCrappresenta il secondo operando, mentre l’accumulatoreAX rappresenta ilprimo operando della moltiplicazione e la destinazione in cui viene scritto il risultato. Nel caso di 2 o3 operandi,DESTe sempre rappresentato da un registro, mentreSRCpuo essere indifferentemente unalocazione di memoria o un registro. Alcuni esempi:

IMUL BL ;AX <- AL * BLIMUL AX,V1 ;AX <- AX * V1IMUL EBX,V2,V3 ;BX <- V2 * V3

dove V1,V2,V3 sono locazioni di memoria (16 o 32 bit).

Di seguito viene presentato l’algoritmo di generazione dei bit di stato, come rilasciato da Intel.

IF (NumberOfOperands = 1)THEN IF (OperandSize = 8)

THENAX <- AL * SRC (* moltiplicazione con segno * )IF AL = AXTHEN CF <- 0; OF <- 0;ELSE CF <- 1; OF <- 1;FI;

ELSE IF OperandSize = 16THEN

DX:AX <- AX * SRC (* moltiplicazione con segno * )

1Nel caso dell’8086 l’istruzioneIMUL prevede sempre e soltanto un operando che viene moltiplicato con l’accumulatore,dove poi viene scritto il risultato

IF sign_extend_to_32 (AX) = DX:AXTHEN CF <- 0; OF <- 0;ELSE CF <- 1; OF <- 1;FI;

ELSE (* OperandSize = 32 * )EDX:EAX <- EAX * SRC (* moltiplicazione con segno * )IF EAX = EDX:EAXTHEN CF <- 0; OF <- 0;ELSE CF <- 1; OF <- 1;FI;

FI;ELSE IF (NumberOfOperands = 2)

THENtemp <- DEST * SRC (* moltiplicazione con segno;

temp dimensione doppia di DEST * )DEST <- DEST * SRC (* moltiplicazione con segno * )IF temp = DESTTHEN CF <- 1; OF <- 1;ELSE CF <- 0; OF <- 0;FI;

ELSE (* NumberOfOperands = 3 * )DEST <- SRC1 * SRC2 (* moltiplicazione con segno * )temp <- SRC1 * SRC2 (* moltiplicazione con segno;

temp dimensione doppia di SCR1 * )IF temp != DESTTHEN CF <- 1; OF <- 1;ELSE CF <- 0; OF <- 0;FI;

FI;FI;

Esercizio 9.3

Il registro FLAGS contiene informazioni di stato e di controllo. Quando vale 1 il bit TF determinaun’interruzione (trap) dopo l’esecuzione di ogni singola istruzione. Un ipotetico debugger puo utilizzarequesto bit al fine dell’esecuzionesingle step. Piu specificatamente, per eseguire l’istruzione all’indirizzoI in single step mode, il debugger asserisce TF e quindi effettua il salto all’indirizzo I. L’interruzioneche segue all’esecuzione dell’istruzione viene raccolta dal debugger stesso, che puo presentare gli effetticonseguenti.

Esercizio 9.4

Nella fase di opcpde fetch non puo essere usato alcun registro in alternativa al registro CS.

Esercizio 9.5

Il registro BP (Base Pointer) viene usato normalmente come puntatore entro lo stack. Ad esempio:

MOV [BP], BX ; M[SS:BP] <- BX

ovvero assumendo il registro SS come registro di segmento. BP puo anche essere usato relativamente atutti gli altri registri di segmento. Ad esempio:

MOV DS:[BP], BX ; M[DS:BP] <- BX

Per quanto si riferisce alla seconda parte dell’esercizio, la situazione puo essere quella di dover trasferireun blocco di dati da stack a memoria, o viceversa. L’istruzione seguente, inserita dentro un ciclo (che faincrementare BP) produce tale effetto.

MOV DS:[BP], [BP] ; M[DS:BP] <- M[SS:BP]

86

Esercizio 9.6

Si supponga che il programma abbia un indice di prestazione uguale a 1 quando opera con lo stackallineato. Quando lo stack none allineato, il 20% delle istruzioni richiedono un doppio accesso allostack; quindi avviene come se questo 20% fosse duplicato, ovvero come se il programma operasse su120 istruzioni rispetto alle 100 precedenti. Dunque le prestazioni si degradano del rapporto100/120 =0.83. In conclusione il fatto che lo stack non sia allineato comporta, con questi dati, un degrado delleprestazioni del 17%.

Esercizio 9.7

• MOV AX,127 ;AX<-127ovvero l’istruzione mette in AX il valore 127;

• MOV AX,127[BX] ;AX<-M[BX+127]ovvero l’ istruzione pone in AX il contenuto della memoria all’indirizzo 127 + BX (indirizzamentorelativo al registro e scalato);

• MOV AX,127[SI][BX] ;AX<-M[127+BX+SI]ovvero l’ istruzione mette in AX il valore di memoria all’indirizzo 127 + BX + SI (indirizzamentorelativo ai registri, indiciato e scalato).

Esercizio 9.8

CS contiene la base del segmento di codice corrente, mentreIP (Istruction Pointer), contiene l’offsetdell’istruzione successiva da eseguire. L’indirizzo logico si denota allora comeA05B:F00C . Il corri-spondente indirizzo fisico si ottiene sommando il contenuto di IP con il contenuto di CS moltiplicato per16. Tenendo conto che moltiplicare per 16 un numero in esadecimale, equivale ad aggiungere uno zeroa destra, l’indirizzo fisico si calcola come:A05B0 + F00C = AF5BC.

Esercizio 9.9

L’indirizzo logico a cui fa riferimento l’istruzioneMOV AL, [BX][SI] e 104A:200A+78 . Il corri-spondente indirizzo fisicoe quindi:104A0+200A+78=12522 .

Esercizio 9.10

Illustreremo solo 3 casi:

• MOV AL,[BX] ; AL <- M[BX]Il codice prodotto dall’assemblatoree: 8A 07. In accordo con il manuale INTEL,8A e il codice diOPCODE per ilMOVla cui destinazionee un registro a 8 bit, a partire da una locazione di memoria oun registro a 8 bit.07 e il codice che identifica la destinazione inAL e la sorgente nel valore contenutonella cella di memoria il cui indirizzoe inBX.

• MOV AL,[BX][SI] ; AL <- M[BX+SI]Il codice prodotto dall’assemblatoree: 8A 00, dove8A ha il significato precedentemente esposto,mentre l’estensione00 rappresentaAL come destinazione eM[BX+SI] come sorgente.

• MOV AL,1024[BX][SI] ; AL <- M[1024+BX+SI]L’assemblatore produce:8A 80 0400 . Il valore80 rappresentaAL come destinazione e la modalitadi indirizzamento; il cui valore0400 (esadecimale) sta per 1024 decimale.

Esercizio 9.11

Nell’8086 l’istruzione IMUL esegue una moltiplicazione con segno tra l’operando sorgente e l’accumu-latore2. I flag che possono essere modificati da questa istruzione sono:CF, OF, AF, PF, SF, ZF .Ad esempio:

IMUL BL ; AX <- AL * BLIMUL CX ; AX <- AX * CX

2non nell’architettura IA32, si veda l’Esercizio 9.2.

87

L’istruzione IDIV esegue una divisione con segno tra il divisore (operando sorgente) e il dividendo(contenuto in DX). Il risultato viene riportato in AX. I flag che possono essere interessati sono:AF,CF, OF, PF, SF, ZF . Ecco un esempio:

IDIV CL ; AL = DL / CLIDIV BX ; AX = DX / BX

Per una piu dettagliata trattazione dei flag si veda l’Esercizio 9.2.

Esercizio 9.12

In base alle assunzioni del testo, l’istruzionePUSH AXrichiede i seguenti passi:

• fetch dell’istruzione (4 cicli)• esecuzione (3 cicli)• scrittura del dato (nello stack)(4 cicli)

Con le ipotesi fatte,PUSH AXviene eseguita in 11 cicli di clock. PerPOP MEMinvece i passi sono:

• fetch dell’istruzione (4 cicli)• lettura dello stack (4 cicli)• cicli addizionali di esecuzione (4 cicli)• scrittura (in memoria) (4 cicli)

Con le ipotesi fatte, l’istruzionePOP MEMrichiede quindi 16 cicli di clock.

Esercizio 9.13

L’8086 e composto di due unita fondamentali:

• Execution Unit (EU)• Bus Interface Unit (BIU)

In BIU e presente una coda di prefetch. Nei momenti in cui l’unita di esecuzione non utilizza i bus laBIU effetta il fetch delle istruzioni successive a quella in esecuzione inserendoli nella coda di prefetch.Ipotizzando la coda di prefetch vuota, la Figura 9.1 riepiloga il comportamento delle due unita per leistruzioni riportate nel testo dell’Esercizio. Si noti che nel caso dell’istruzione MOV, poiche questautilizza il bus in fase di esecuzione, none possibile effettuare il fetch da parte della BIU. Interessantee anche vedere come, all’istante 22 la coda di prefetch sia piena e, per poter effettuare il fetch si debbaattendere la fine dell’esecuzione dell’istruzione DIV all’istante 24.

88

Figura 9.1 Profilo temporale di esecuzione. (Esercizio 9.13).

Esercizio 9.14

Si assume che la funzione nel testo, abbia una chiamata dal codiceC del tipok=f(m, * n) . Denotiamocon BP0 e SP0 il contenuto dei registri BP e SP prima della chiamata della funzione. Seguendo laconvenzione C, per la quale vengono caricati prima gli ultimi parametri, lo statement viene tradotto comesegue. Si noti che si assume di usare AX per restituire al chiamante il valore calcolato dalla funzione.

LEA AX,n ;carica l’indirizzo effettivo di nPUSH AX ;deposita il valore nello stackMOV AX,m ;carica in AX il valore aPUSH AX ;deposita il valore nello stackCALL f ;Chiama la SubRoutine fADD SP,4MOV K,AX

All’ingresso inf il contenuto dello stack, per la parte di interesse,e quello mostrato in Figura 9.2:Per indicizzare gli elementi nello stack viene utilizzato BP. Per tale motivo esso deve contenere

l’indirizzo di una posizione nota di riferimento che, all’ingresso della routine,e la testa dello stack.L’aggiornamento di BP richiede il preventivo salvataggio del suo contenuto, quindi all’ingresso infvengono eseguite le seguenti istruzioni:

PUSH BPMOV BP,SPSUB SP,2 ;lascia lo spazio per x

Si noti che nell’architettura Intel lo stack cresce verso gli indirizzi piu bassi, per questo lo spazio perx si ottiene con l’istruzioneSUB. La situazione risultante nello stacke mostrata in Figura 9.3.

Si noti inoltre che all’interno della funzione, i parametrim,n e la variabile internax hanno questiscostamenti rispetto al contenuto di BP:

89

Figura 9.2 Stato dello stack immediatamente dopo l’esecuzione dell’istruzione CALL f . (Esercizio9.14).

Figura 9.3 Stato dello stack dopo l’aggiornamento di BP e l’allocazione dello spazio per il parametrointerno x.

m: +4ind n: +6

x: -2

Lo statement* n=* n/2 viene tradotto:

MOV BX,[BP+6] ;carica * nMOV AX,[BX]DIV 2 ;esegue la divisione per 2MOV [BX],AX ;salva il valore

Il successivo statementx= m + * n diventa:

MOV AX,[BP+4] ;carica il valore * nMOV BX,[BP+6] ;carica mADD AX,[BX]MOV [BP-2],AX ;carica in x il risultato

Le istruzioni corrispondenti al ritorno dalla funzione sono:

MOV AX,[BP-2] ;carica in AX il valore xMOV SP,BPPOP BPRET

90

10

Esercizio 10.1

Qui di seguito si riporta (parte del) fileLST ottenuto assemblando il sorgente. InDATA SEGMENTsonostate raccolte le definizioni dei dati, inCODE SEGMENTle istruzioni.

DATA SEGMENT

0000 02 04 A DB 2,4= 0001 B EQU 10002 01 C DB B= 0001 D EQU A+B= E EQU C

CODE SEGMENT

0000 A0 0000 R MOV AL,A0003 B0 01 MOV AL,B0005 A0 0002 R MOV AL,C0008 A0 0001 R MOV AL,D000B A0 0002 R MOV AL,E

Si osservi che la direttivaequ non alloca memoria; conseguentemente, di fianco al relativo offsetl’assemblatore pone il simbolo “=”. (La direttivaequ sta per “Equal”).

Per quanto riguarda il formato e l’effetto delle istuzioni si consideri, ad esempio,mov al,c . Dallistato si osserva che illocation counter dell’istruzione successivae avanzato di tre posizioni, dunquel’istruzione occupa tre byte, di cui il primo (A0) corrisponde al codice dello specificomov, il secondo eil terzo (0002 ) rappresentano lo scostamento dic rispetto alla base del suo segmento. Dunque l’effettodell’istruzionemov al,c e il caricamento inal del numero 1.

L’istruzionemov al,b viene assemblata in due byte, di cui il primoe il codice del particolaremov(si noti chee diverso da quello delmov descritto in precedenza), e il secondoe l’operando in formaimmediata.

Istruzione Effetto Formatomov al,a al ← 2 3 bytemov al,b al ← 1 2 bytemov al,c al ← 1 3 bytemov al,d al ← 4 3 bytemov al,e al ← 1 3 byte

Esercizio 10.2

Si riporta la parte di interesse del fileLST.

DATA SEGMENT

0000 0000 0001 0002 0003 a dw 0,1,2,3= 0003 b equ a+3= 0003 c equ 30008 04 05 06 d db 4,5,6

CODE SEGMENT

0000 A0 0000 R mov al,aerror : Operand types must match0003 A1 0009 R mov ax,a+90006 A1 0003 R mov ax,b0009 B8 0003 mov ax,c000C A0 0006 R mov al,b+cerror : Operand types must match000F A1 0006 R mov ax,b+c

Vale la pena fare un’osservazione sul listato e, in particolare, sulla prima e quarta riga, quelle chedefiniscono le posizionia e d. Si ricordi che gli indirizzi vengono assegnati in ordine crescente ai bytee che l’architettura Intel adotta l’ordinamento Little Endian che, assegna l’indirizzo della parola al bytemeno significativo. Conseguentemente per il segmento dati la situazione in memoria rappresentata aparolee la seguente:

Offset(Hex) Parola(Hex)

00 00 00 0000 02 00 0100 04 00 0200 06 00 0300 08 05 0400 0A -- 06

Nel caso in cui l’istruzione coinvolga un registro a 16 bit, nella parte bassa viene caricato il byteil cui offset e indicato nella codifica dell’istruzione, mentre nella parte alta viene caricato il contenutodella locazione di memoria avente offset immediatamente superiore. L’esecuzione delle istruzioni (quellevalide) produrrebbe questi risultati:

Istruzione Effettomov ax,a+9 ah ← 6 al ← 5mov ax,b ah ← 2 al ← 0mov ax,c ah ← 0 al ← 3mov ax,b+c ah ← 0 al ← 3

Esercizio 10.3

L’effetto della prima istruzionee il caricamento inax del valore 10. Anche la seconda istruzione ha lostesso effetto ma susi . La terza carica inbx lo scostamento dimatrix rispetto al registrods ovverolo scostamento del primo elemento dimatrix . L’ultima istruzione modifica il 31-esimo elemento dimatrix con il valore contenuto inax ovvero con 10.

Esercizio 10.4

Al solito si riporta la parte di interesse del fileLST.

DATA SEGMENT0000 51 75 65 73 74 61 20 a db ’Questa e’’ la lettera A’

65 27 20 6C 61 20 6C65 74 74 65 72 61 2041

= 0042 b equ ’B’= 0044 c equ b+2= 0042 d equ a+b= 0002 e equ a+c-d0016 0064[ f db 100 dup(’F’)

42]

92

CODE SEGMENT0000 A0 0000 R mov al,a0003 B0 42 mov al,b0005 B0 44 mov al,c0007 A0 0042 R mov al,d000A B4 02 mov ah,e

Ragionando poi nello stesso modo si ha:

Istruzione Effettomov al,a al ← ’Q’mov al,b al ← ’B’mov al,c al ← ’D’mov al,d al ← ’F’mov ah,e al ← 2

Esercizio 10.5

La variabile ALFAe definita come un vettore diDouble Word e contenente quattro elementi al suointerno.

1. al primo passo si associano scostamenti numerici a indirizzi simbolici (nomi di variabili ed etichette).Tutto si riduce all’analisi sequenziale del testo con avanzamento di ILC in base all’occupazione dimemoria e alla costruzione contestuale della tavola dei simboli SYMTAB;

2. poiche ALFA e dichiarata come prima variabile all’interno del programma, essa verra inserita all’in-terno della tavola dei simboli associandole l’indirizzo logico DS:0 (essendo 0 il valore di ILC);

3. al secondo passo l’assemblatore produce il codice oggetto dello statement sopra riportato ovverogenera i quattro numeri.

Esercizio 10.6

• La prima istruzione scrive il contenuto del registro AX dentro la locazione di memoria il cui indirizzologico e DS:BX+777;

• La seconda scrive il contenuto del registro AX dentro la locazione di memoria il cui indirizzo logicoeCS:BX+777;

• La terza istruzione muove il registro AX dentro la locazione di memoria il cui indirizzo logicoeSS:BX;

• La quarta istruzione muove il contenuto di AX dentro la locazione di memoria all’indirizzo logicoSS:BP+777.

Esercizio 10.7

Le due istruzioni hanno un effetto identico, entrambe collocano inAL il valore contenuto nello stack allalocazioneBP:100 . Il codice prodotto dall’assemblatore vale:8A 46 64 . Nel quale:

• 8A rappresenta l’opcode delMOV, quando viene utilizzato con una sorgente, registro o memoria, a 8bit e con la destinazione, un registro, a 8 bit.

• 46 e la codifica che specifica di utilizzare i registriAL e BP (rispetto allo stack) per l’operazionerichiesta.

• 64 e la codifica esadecimale dello scostamento scritto in forma decimale nell’istruzione, 100d = 64h.

Esercizio 10.8

L’effetto delle istruzionie riportato in commento:

• mov cs:[bx],ax ;M[cs:100] ←AX

• mov cs:[bx+2],cx ;M[cs:102] ←CX

• jmp cs:[bx] ;IP ←100

93

Esercizio 10.9

Inserendo la classe ’Sub’ al segmento MainSEG la mappa generata dal linker diventa la seguente:

Start Stop Length Name Class00000H 000C7H 000C8H STACK000D0H 00169H 0009AH DATA DATA00170H 001FDH 0008EH MAINSEG SUB00200H 0025EH 0005FH SUBSEG SUB

Program entry point at 0017:0000

La differenza fondamentale, rispetto alla mappa di pagina 397 del testo consiste nel fatto che, in questocaso, i segmenti non appaiono nella tabella secondo l’ordine in cui il collegatore li incontra nella scan-sione dei moduli rilocabili da collegare. Il linker associa a tutti i segmenti appartenenti alla classe SUBlocazioni contigue di memoria. La funzione della classee infatti proprio questa; associando un segmentoad una classe si ha la possibilita, in fase di collegamento, di raccogliere frammenti di segmento di tipocorrelato.

Esercizio 10.10

Il tratto di codicee un ciclo ripetuto per 100 volte. Supponiamo che le istruzioni richiedano i seguenticlock per istruzionecpi:

MOV 6ADD 6PUSH 11 (quando lo stacke allineato ai pari)DEC 6JNZ 6

La Tabella 10.1 riporta per ciascuna istruzione il numero di volte che viene eseguitani, la relativafrequenzaxi e il cpi. Dalla Tabella si ricavaCPI =

∑xicpi = 7, 2499.

Istruzione ni xi cpi xi · cpi

MOV 1 0,24% 6 0, 0144ADD 100 24,95% 6 1, 497PUSH 100 24,95% 11 2, 7445DEC 100 24,95% 6 1, 497JNZ 100 24,95% 6 1, 497

401 100% 7, 2499

Tabella 10.1 Prestazioni del programma dell’Esercizio 10.10 nel caso di stack allineato.

Se lo stack none allineato, il numero di accessi alla memoria dell’istruzionePUSHrisulta rad-doppiato. Supponendo pari a 4 il numero di cicli richiesto per l’ ulteriore accesso alla memoria, ilcpi dell’ istruzionePUSHdiventa 15. La Tabella 10.2 illustra il cambiamento. Dalla stessa si ha cheCPI =

∑xicpi = 8, 2479.

Istruzione ni xi cpi xi · cpi

MOV 1 0,24% 6 0, 0144ADD 100 24,95% 6 1, 497PUSH 100 24,95% 15 3, 7425DEC 100 24,95% 6 1, 497JNZ 100 24,95% 6 1, 497

401 100% 8, 2479

Tabella 10.2 Prestazioni del programma dell’ Esercizio 10.10 nel caso di stack non allineato.

Dunque le prestazioni degradano del rapporto7.2499/8, 2479, ovvero del 12%.

94

Esercizio 10.11

Si osservi anzitutto che la differenza tra le due versioni del codice riguarda solo l’istruzione di somma,che nel secondo caso usa un operando immediato, mentre nel primo fa riferimento alla memoria. Siipotizza che il codice oggetto corrispondente a ogni istruzione, sia formato da:

a) un byte contenente il codice operativo e la codifica del registro implicato;b) un byte se l’operandoe immediato o due see in memoria.

Per valutare le prestazioni in velocita dei due programmi si calcola il numero totale di periodi diclock necessari per l’esecuzione. In base ai dati del testo dell’ esercizio, il numero di periodi di clockrichiesto dalle singole istruzioni per la loro esecuzione,e quello riportato nelle tabelle sottostanti.

Versione A:

Istruzione Formato Periodi di clockMOV AL,VAR 3 byte 12+4+1 (n1)MOV CX,N 2 byte 8+1 (n2)

L: ADD AL,COST 3 byte 12+4+1 (n3)SUB CX,1 2 byte 8+1 (n4)JNZ L 3 byte 12+1 (n5)

Versione B:

Istruzione Formato Periodi di clockMOV AL,VAR 3 byte 12+4+1 (n1)MOV CX,N 2 byte 8+1 (n2)

L: ADD AL,COST 2 byte 8+1 (n3)SUB CX,1 2 byte 8+1 (n4)JNZ L 3 byte 12+1 (n5)

Le prime due istruzioni nelle due differenti versioni richiedono lo stesso numero di periodi di clock.Per le tre istruzioni che compongono il ciclo la differenzae relativa solo alla prima istruzione (17 contro 9periodi). Il numero di periodi di clock richiesti per il cicloeN×(n3+n4+n5), con N=100. Trascurandon1 en2, il numero totale di periodi di clock necessari per l’esecuzione delle due versioni risulta:

Versione A:100× 39 = 3900Versione B:100× 31 = 3100

da cui si deduce che la versione Be piu veloce di circa il 26%.

Esercizio 10.12

L’esercizio puo essere visto sotto due diversi aspetti, come un riordino di una stringa oppure come unacreazione di una nuova stringa, a partire dalla sorgente, secondo certe regole.

Ordinamento: L’esercizio richiedere il riordinamento degli elementi di un vettore di caratteri (la strin-ga letta da tastiera), con la complicazione di considerare maiuscole e minuscole idempotenti. Qui diseguito viene dato l’algoritmo in C. A tale scopo si indica constring[] il vettore contente la stringaASCII e Lenght(V[]) una funzione che restituisce il numero dei caratteri contenuti inV[] . ConM(c) si indica una funzione che restituisce il valore numerico (la codifica ASCII) corrispondente allaforma maiuscola del caratterec . In altre parole, sec=’x’ o c=’X’ la funzioneM(c) restituisce co-munque’X’ . Conm(c) si indica la funzione complementare diM, ovvero la funzione che restituisce lacodifica della forma minuscola.

L’algoritmo di riordinamento opera in modo convenzionale, confrontando un carattere (a partire dalprimo) con tutti i successivi e cambiandoli se il primo segue il secondo nell’ordine alfabetico. L’impiegodelle due funzioniMe mgarantisce il riordinamento nel modo richiesto. In conclusione l’algoritmoe ilseguente:

for(i=0;i<Lenght(string[]);i++) for(j=i+1;j<Lenght(string[]);j++)

if((M(string[i])>M(string[j])||(m(string[i])>m(string[j])))

95

temp=string[j];string[j]=string[i];string[i]=temp;

Questo algoritmo ha una complessita pari a

C =n(n− 1)

2.

Soluzione alternativa: Una tecnica alternativa, che sara utile per il prossimo esercizio, consiste nelconfrontare i caratteri distring[] con tutte le lettere dell’alfabeto in ordine e trasferire al vettoreDest[] i caratteri distring[] quando uguagliano la lettera di confronto. Sfruttando la funzioneM(c) vista in precedenza, il confronto puo essere riferito alle sole lettere minuscole.

j=0;for(c="a";c<="z";c++)

for(i=0;i<Lenght(string[]);i++)if((string[i]==c)||(string[i]==M(c)))

Dest[j]=string[i];j++;

La complessita del seguente algoritmoe lineare, supponendo la stringa lungan caratteri, si avrebbe:

C = 26 · 2 · n = 52n

Sen e maggiore di 26 questa sarebbe la soluzione migliore in quanto sarebbe una funzione che crescelinearmente conn, mentre la complessita della soluzione precedente sale nell’ordine din2. Nel casopero chen sia minore di 26 caratteri la prima soluzionee migliore.

Nella parte seguente si mostra una traduzione in linguaggio Assembler del secondo algoritmo. A talfine faremo esplicito riferimento al programma SECONDO del testo (Paragrafo 10.8.2), usando le macroWRITELNeREADLNdefinite in tale contesto. La traduzione richiede pochi accorgimenti:

• La definizione di due aree di memoriaString e Dest corrispondenti ai due vettori, facendo atten-zione al fato chestring deve essere definito in modo tale da soddisfare le assunzioni delle macroWRITELNeREADLN.

• L’impiego del registroSI come indicei .• L’impiego del registroDI come indicej .• L’impiego di CXcome valore restituito daLenght(V[]) .• L’uso di DL eDHcome indicec .

Il file Macro.mac contiene le routine di lettura e scrittura, che sono spiegate in dettaglio a pagina388 del testo e seguenti.

;Definizioni di macro;-------------------------------------

INCLUDE Macro.Mac

; Segmento di stack e di dati;-------------------------------------Stack SEGMENT STACK

DB 10 DUP(’stack’)Stack ENDS;-------------------------------------

Data SEGMENTCR EQU 0DHLF EQU 0AHMess DB ’Inserire una stringa>’, ’$’

96

Buffer EQU MaxMax DB Dest-strng ;Dimensione Maxn DB ? ; # caratteri lettistrng DB 30 DUP(?) ; buffer effettivoDest DB 50 DUP(?) ;

Data ENDS

CSec SEGMENTASSUME CS:CSec,DS:Data,SS:Stack

Main PROC FAR

MOV AX,DataMOV DS,AX ;DS -> Data

WRITELN Mess ;Stampa a video di MessREADLN Buffer ;Lettura stringa

MOV CX,0MOV CL,n ;E’ stato introdottoCMP CX,0 ; almeno 1 car?JE Fine ;no

MOV SI,OFFSET Buffer+1 ;muove SI all’inizio della stringa inseritaMOV DI,OFFSET Dest ;muove DI all’inizio della stringa di arrivoMOV AL,LF ;Sposta LF in ALMOV [DI],AL ;Scrive in cima all’arrivo il valore LFINC DI ;punta al successivo carattereMOV AL,CR ;idem a prima ---MOV [DI],AL ;---con CR---INC DI ;-----

CALL Ordina ;chiama la funzione di ordinamento

WRITELN Dest ;Stampa l’arrivo a video

Fine: MOV AH,4CHINT 21H

Main ENDP

Ordina PROC NEAR; In ingresso a Ordina; SI: offset della posizione dell’ultimo carattere introdotto; DI: offset della prima posizione libera di Dest; CX: numero di caratteri introdotti

PUSH SI ;salva nello stack il valore di SI (fine stringa ingresso)PUSH CX ;salva nello stack il valore di CX (lunghezza stringa)

MOV DL,41h ;inizializza DL con la ’A’MOV DH,61h ;inizializza DH con la ’a’

Findc: INC SIMOV AL,[SI] ;sposta il carattere in ALCMP AL,DH ;controlla quale lettere minuscola siaJE Xfer ;nel caso di OK, passa alla stampaCMP AL,DL ;controlla se e una lettera maiuscolaJE Xfer ;nel caso di OK, passa alla stampa

JNE Escape ;dopo le prime 2 lettere (a,A) passa alle successive

Xfer: MOV [DI],AL ;scrive la lettera trovataINC DI

Escape: DEC CXJNZ Findc ;Riesegue il ciclo di ricerca fino alla fine della stringa

;non e detto infatti che la ’a’ sia per forza;l’ultima lettera della stringa inserita....;Nel caso che la lettera in questione non sia stata trovata

ADD DL,1 ;passa al carattere maiuscolo successivoADD DH,1 ;passa al carattere minuscolo successivoCMP DL,5Bh ;controlla se si e arrivati dopo la ’Z’==5Ah

;----------------------- Nota la ’z’ vale 7Ah -----------------------

97

JE Exit ;se sono uguali esce dalla procedura

POP CX ;ripristina il valore di CX (per i loop)POP SI ;ripristina il valore di SI, per tornare in

;fondo alla stringa

PUSH SI ;risalvo il valore SIPUSH CX ;risalvo il valore CX

JMP Findc

Exit: MOV AL,’$’ ;Aggiunta del ’$’MOV [DI],AL ;- a fine stringaMOV AL,0 ; OK!RETPOP CXPOP SIRET

Ordina ENDP

CSec ENDSEND Main

Esercizio 10.13

Questo esercizio potrebbe essere risolto come un problema di riordinamento, seguito dall’eliminazionedei caratteri duplicati. Indicando ancora constring[] il vettore contentente i caratteri ASCII letti datastiera, il riordinamento risulta piu semplice rispetto al caso dell’Esercizio 10.12, infatti vale la seguenterelazione di ordinamento

z > .... > b > a > Z > ... > B > A.

L’algoritmo di riordinamento sarebbe quindi:

j=0;for(c="a";c<="Z";c++)

for(i=0;i<Lenght(string[]);i++)if((string[i]==c))

Dest[j]=string[i];j++;

Successivamente si dovrebbe prevedere l’eliminazione dei doppioni dalla stringa del risultato inaccordo con le specifiche del testo dell’esercizio.

Nella codifica ASCII vale la relazionez > . . . > b > a > Z > . . . > B > A (avendo indi-cato conA, . . . Z, a, . . . z, il valore numerico del codice della lettera), quindi otteniamo la soluzionedell’esercizio modificando l’algoritmo della soluzione alternativa dell’Esercizio 10.12 in modo da:

• Uscire dal ciclo di scansione della stringa, per passare alla lettera successiva, se la lettera in esameestata trovata instring[] , (cosı da copiarne una sola copia inDest[] )

• Utilizzare come limiti della ricerca sull’alfabeto la coppia di lettere a e Z.

La complessita del seguente algoritmoe identica alla precedente, in quanto non conoscendo la com-posizione della stringa, di deve comunque controllare la presenza di tutti i caratteri test. Vale allora, conn lunghezza della stringa:

C = n · (26 + 26).1

1In realta sarebbe maggiore, in quanto per sfruttare la condizione lineareA < Z < a < z, si deve passare da alcuni caratteridella tabella ASCII non convenzionali. Si invita a verificare il contenuto della tabella ASCII.

98

;Definizioni di macro

Include Macro.mac

; Segmento di stack e di dati;-------------------------------------Stack SEGMENT STACK

DB 10 DUP(’stack’)Stack ENDS

;-------------------------------------Data SEGMENTCR EQU 0DHLF EQU 0AHMess DB ’Inserire una stringa>’, ’$’Buffer EQU MaxMax DB Dest-strng ; Dimensione Maxn DB ? ; # caratteri lettistrng DB 30 DUP(?) ; buffer effettivoDest DB 50 DUP(?)

Data ENDS

CSec SEGMENTASSUME CS:CSec,DS:Data,SS:Stack

Main PROC FAR


WRITELN Mess ;Stampa a video di MessREADLN Buffer ;Lettura stringa


MOV SI,OFFSET Buffer+1 ;muove SI all’inizio della stringa inseritaMOV DI,OFFSET Dest ;muove DI all’inizio della stringa di arrivoMOV AL,LF ;Sposta LF in ALMOV [DI],AL ;Scrive in cima all’arrivo il valore LFINC DI ;punta al successivo carattereMOV AL,CR ;idem a prima ---MOV [DI],AL ;---con CR---INC DI ;-----

CALL Ordina ;chiama la funzione di ordinamento

WRITELN Dest ;Stampa l’arrivo a video


Main ENDP

Ordina PROC NEAR; In ingresso a Ordina; SI: offset della posizione dell’ultimo carattere introdotto; DI: offset della prima posizione libera di Dest; CX: numero di caratteri introdotti

PUSH SI ;salva nello stack il valore di SI (fine stringa ingresso)PUSH CX ;salva nello stack il valore di CX (lunghezza stringa)

MOV DL,41h ;inizializza DL con la ’A’

Findc: INC SIMOV AL,[SI] ;sposta il carattere in ALCMP AL,DL ;controlla quale lettere minuscola siaJE Xfer ;nel caso di OK, passa alla stampa

JNE Escape ;dopo le prime 2 lettere (a,A) passa alle successive

Xfer: MOV [DI],AL ;scrive la lettera trovataINC DI

99

JMP Next

Escape: LOOP Findc ;Riesegue il ciclo di ricerca fino alla fine della stringa;non e detto infatti che la ’a’ sia per forza;l’ultima lettera della stringa inserita....;Nel caso che la lettera in questione non sia stata trovata

Next: ADD DL,1 ;passa al carattere maiuscolo successivoCMP DL,7Bh ;controlla se si e arrivati dopo la ’Z’==5Ah

;-----------------------;Nota la ’z’ vale 7Ah;-----------------------

JE Exit ;se sono uguali esce dalla procedura

POP CX ;ripristina il valore di CX (per i loop)POP SI ;ripristina il valore di SI, per tornare in

;fondo alla stringa

PUSH SI ;risalva il valore SIPUSH CX ;risalva il valore CX

JMP Findc

Exit: MOV AL,’$’ ;Aggiunta del ’$’MOV [DI],AL ;- a fine stringaMOV AL,0 ; OK!RETPOP CXPOP SIRET

Ordina ENDP

CSec ENDSEND Main

Esercizio 10.14

La successione di Fibonacci si realizza impostando due valori di partenza: 0, 1 e sommando iterativa-mente. L’n + 2esimo terminee risultato della somma dei termininesimo en + 1esimo.

Il programma chiede a video il numero di iterazioni richieste. Dopo una fase d’inizializzazione deiregistri, un ciclo provvede a sommare progressivamente i termini della successione e a stamparli a video.

Ai fini della semplificazione del testo del programma, l’ingresso di un numero da tastiera vieneeffettuato tramite la routineINPUT, riportata al termine.

INCLUDE MACRO.MAC

STACK SEGMENT STACKDW 50 DUP(0)

STACK ENDS

DATA SEGMENT PUBLIC ’DATA’

LF EQU 0AHCR EQU 0DHOFLOW DB LF,CR,’Overflow’,LF,CR,’$’M_RIS DB LF,CR,’Termine della successione: ’RISULT DB 5 DUP(?)DATA ENDS

MainSEG SEGMENTASSUME CS:MainSEG, DS:DATA, SS:STACK

EXTRN INPUT: FAREXTRN BIN2ASC:FAR

FIBO LABEL FARMOV AX, DATAMOV DS, AX

CALL INPUT ; chiede un carattere a video

PUSH AX ; salva i registriPUSH BX ; nello stackMOV AL,’0’

100

MOV RISULT,ALMOV AL,’$’MOV RISULT+1,ALWRITELN M_RIS ; stampa a video 0WRITELN RISULTPOP BX ; ripristina iPOP AX ; registri dallo stack

MOV CX, 0 ; muove i primiMOV DX, 1 ; due valori in CX, DX

LOOP: MOV BX, CX ; per far avanzare la successioneADD CX, DX ; somma tra i terminiJC OFLOWR ; c’e overflow???

PUSH AX ; salva i registri per la stampaMOV AX, CX ; a videoPUSH BXPUSH CXPUSH DXMOV BX, OFFSET RISULTCALL BIN2ASC ; prepara la stringa di uscitaWRITELN M_RIS ; stampa la stringa di uscitaPOP DXPOP CXPOP BX ; ripristino della situazionePOP AX ; pre-stampa

MOV DX, BX ; scrive il nuovo valore di BX; fa avanzare la successione

DEC AX ; decrementa ’n’JNZ LOOP ; cicla il tutto fino a ’n=0’

EXIT: MOV AH, 4CH ; uscita dal programmaINT 21H

OFLOWR: WRITELN OFLOW ; uscita per overflowJMP EXIT

MainSEG ENDSEND FIBO

La routine INPUT corrisponde al codice seguente. La routine ritorna al chiamante solo quandoviene battuto un numero intero inferiore al massimo rappresentabile.

Include MACRO.MAC

DATA SEGMENT PUBLIC ’DATA’CR EQU 0DHLF EQU 0AHM_ERR2 DB LF,CR,’Overflow’,LF,CR,’$’M_ERR1 DB LF,CR,’Stringa non numerica’,LF,CR,’$’TESTO1 DB LF,CR,’Inserisci un numero positivo intero: ’,’$’BUFFER DB 50n DB ?STR DB 50 DUP(?)DATA ENDS

SubSEG SEGMENT PUBLIC ’Sub’ASSUME CS:SubSEG,DS:DATAPUBLIC INPUT

EXTRN ASC2BIN: FAR ;la routine ASC2BIN presentata a pagina 396 del testo.

INPUT PROC FAR

;In uscita AX contiene (in forma binaria) il valore immesso dall’utente

P1: PREAD BUFFER,TESTO1MOV CH, 0MOV CL, n ;CX = #caratteriMOV BX, OFFSET STR ;DS:BX -> STR

CALL ASC2BIN ; in CL il codice di errore

101

CMP CL, 1JE STRING ;numerico ?CMP CL, 2JE OFLOW ;Superiore alla capacit a?JMP OK

OFLOW: WRITELN M_ERR2 ;Troppo grossoJMP P1 ; Rileggere!!

STRING: WRITELN M_ERR1 ;Troppo grossoJMP P1 ; Rileggere!!

OK: RET

INPUT ENDPSubSEG ENDS

END

Esercizio 10.15

Il programma seguente, diversamente da quello precedente, non chiede il numero di termini della succes-sione da stampare a video ma cicla fino al raggiungimento dell’overflow. Anche in questo caso i registriutilizzati sono a 16 bit.

INCLUDE MACRO.MAC


STACK ENDS

DATA SEGMENT PUBLIC ’DATA’LF EQU 0AHCR EQU 0DHOFLOW DB LF,CR,’Overflow’,LF,CR,’$’M_RIS DB LF,CR,’Termine della successione: ’RISULT DB 5 DUP(?)DATA ENDS


EXTRN BIN2ASC:FAR

FIBO LABEL FARMOV AX, DATA ; mette in DS l’indirizzoMOV DS, AX ; del segmento DATA

PUSH AX ; salva i registri AX, BXPUSH BXMOV AL,’0’MOV RISULT,ALMOV AL,’$’MOV RISULT+1,ALWRITELN M_RIS ; stampa a video 0WRITELN RISULTPOP BXPOP AX ; ripristina AX, BX

MOV CX, 0 ; carica i primi dueMOV DX, 1 ; termini della successione

LOOP: MOV BX, CX ; salva CX per far avanzare la successioneADD CX, DX ; somma dei registriJC OFLOWR ; overflow???MOV AX, CX ; prepara il risultato per la stampaPUSH BX ; salva i registriPUSH CXPUSH DXMOV BX, OFFSET RISULT ; stampa a videoCALL BIN2ASC ; del risultatoWRITELN M_RISPOP DX ; ripristina i registriPOP CXPOP BXMOV DX, BX ; aggiorna i termini della successioneJMP LOOP ; cicla il tutto fino a overflow

102

EXIT: MOV AH, 4CH ; esce dal programmaINT 21H

OFLOWR: WRITELN OFLOW ; stampa a video del messaggio di erroreJMP EXIT


Esercizio 10.16

Il programma che seguee una modifica del programma dell’Esercizio 10.15 per il caso di numeri a 8 bit.

INCLUDE MACRO.MAC


STACK ENDS

DATA SEGMENT PUBLIC ’DATA’LF EQU 0AHCR EQU 0DHOFLOW DB LF,CR,’Overflow’,LF,CR,’$’M_RIS DB LF,CR,’Termine della successione: ’RISULT DB 5 DUP(?)DATA ENDS


EXTRN BIN2ASC:FAR

FIBO LABEL FARMOV AX, DATA ; mette l’indirizzo delMOV DS, AX ; segmento DATA in DS

PUSH AX ; salva i registriPUSH BXMOV AL,’0’MOV RISULT,ALMOV AL,’$’MOV RISULT+1,ALWRITELN M_RIS ; stampa a video 0WRITELN M_RISPOP BX ; ripristino dei registriPOP AX

MOV CL, 0 ; muove i primi dueMOV DL, 1 ; termini della successione

LOOP: MOV BL, CL ; salva il valore di CL; fa avanzare la successione

ADD CL, DL ; somma i due terminiJC OFLOWR ; overflow???

MOV AH, 0 ; salvo i valori per la stampaMOV AL, CLPUSH BXPUSH CXPUSH DXMOV BX, OFFSET RISULT ; stampa a video del risultatoCALL BIN2ASCWRITELN M_RISPOP DX ; ripristino i valoriPOP CXPOP BX

MOV DL, BL ; avanzamento della successione

JMP LOOP

EXIT: MOV AH, 4CH ; uscitaINT 21H

OFLOWR: WRITELN OFLOW ; stampa errore overflowJMP EXIT

103


La riscrittura dell’Esercizio 10.15 con una rappresentazione dei numeri su 32 e 64 bit non puo esserefatta perche non si hanno le appropriate aritmetiche. Si potrebbe codificare un metodo, lungo, tedioso edi difficile comprensione, con il quale si puo rappresentare un numero a 32 bit attraverso due registri a16 bit. Una rappresentazione di questo tipo consente la somma di numeri di 32 bit (sommando prima iregistri meno significativi e, successivamente, i registri piu significativi con il riporto). Poiche pero unregistro a 16 bit rappresenta 216 numeri (0. . . 65535) il carry flag si attivera con il trabocco del registromeno significativo. La conseguenzae che il numero ottenutoe in base 65536. La vera difficolta epercio quella di presentare a video un numero ricodificato in base 10. Di seguito i passi fondamentalidell’algoritmo di ricodifica:

• dividere la parola piu significativa per 10;• accodare da destra al resto ottenuto dalla divisione sopra la parola meno significativa;• continuare la divisione e accodare il quoziente al precedente;• ripetere fino a che i bit da accodare non sono finiti;• prendere l’ultimo resto e conservarlo come prima cifra ASCII;• ripartire con il quoziente e iterare il tutto fino a che il quoziente arriva ad annullarsi.

Esercizio 10.17

L’esercizio verra svolto presentando non solo la routine richiesta, ma anche la parte di programma che in-troduce da tastiera le dimensioni della matrice e gli elementi costituenti la stessa. A tal fine il programmaprocede attraverso i seguenti passi:

a) Richiede e legge da tastiera il numero di righemb) Richiede e legge da tastiera il numero di colonnenc) Richiede e legge da tastiera i valori dei singoli elementi. Presenta a video la matrice introdotta.d) Richiede e legge gli indici delle due righe da sommare.e) Effettua la somma, con le modalita richieste dal testo, e presenta a video il risultato.

La matrice viene definita in memoria come vettoreM DW 50 DUP(0). Con questa assunzione silimitano le dimensioni della matrice a 50 elementi. La Figura 10.1 mostra come viene interpretato ilvettoreM. L’inserimento dei valori avviene per righe.

Con riferimento alla Figura 10.1 l’elementoM(r, c) ha uno scostamento rispetto alla prima posizio-ne diMpari a:

(r − 1) · n + (c− 1)

dove:r: riga dell’elemento che di vuole trovarec: colonna dell’elemento che di vuole trovaren: numero delle colonne della matricePer esempio l’elementoM(2, 3) in una matrice3× 3, cioe il terzo elemento della seconda riga, nel

vettoreMe alla posizione assoluta:(2−1) ·3+(3−1) = 5. Per effettuare agevolmente questo calcoloestata creata la macroLOCATEche prende in ingressor e c e restituisce il valore assoluto della posizionesul vettoreM, mettendolo nel registroAX.

I passi dell’algoritmo che somma la riga i con la riga j sono i seguenti, la routine nel codiceechiamataSOMMAR:

1. Si calcola la posizione assoluta suMdella riga j e si assegna aSI2. Si deposita il valore puntato daSI in DX3. Si calcola la posizione assoluta suMdella riga i e si assegna aSI4. Si deposita il valore puntato daSI in AX5. Si esegue la somma diAXeDX6. Si deposita il risultato nella locazione diMpuntata daSI .7. Si itera in base alle dimensioni della matrice, sommando 1 ad i e j.

Il controllo di questo cicloe affidato ad un contatore, il registroCX. Il ciclo termina quandoCX euguale a N, ovvero al numero delle colonne.

104

Figura 10.1 Interpretazione del vettore M.

Nel seguito si illustra il codice in modo da attenersi strettamente ai codici di riferimento presentatisul testo, senza eseguire alcun tipo di ottimizzazione o strutturazione dello stesso ad esclusione dellaroutineINPUT introdotta nell’ Esercizio 10.14.

;Definizioni di macro;-------------------------------------

Include Macro.Mac

;la macro locate prende i valori dalla memoria, I,J per i valori totali riga e colonna;in SI e DI rispettivamente gli indici di RIGA e COLONNA;le righe e le colonne iniziano da 0,0 a (i-1),(j-1);esempio l’elemento alla posizione (r,c), si ottiene come: r * (J-1) + (c-1)

LOCATE MACRO SI,DIPUSH SIPUSH DIPUSH BXMOV BX,OFFSET JMOV AX,[BX]DEC SIMUL SIDEC DIADD AX,DI ;IN AX C’E’ IL VALORE VOLUTOPOP BX ;BX VIENE RIPRISTINATOPOP DIPOP SI

ENDM

;Segmento Dati e Stack;----------------------------------------------------------------STACK SEGMENT STACK

DB 100 DUP(?)

STACK ENDS

;-------------------------------------------------------------

105


CR EQU 0DHLF EQU 0AHI DW 0I_STR DB LF,CR,’Le righe sono: ’,’$’J DW 0J_STR DB LF,CR,’Le colonne sono: ’,’$’DIM DW 2 DUP(?)DIM_STR DB LF,CR,’La dimensione della matrice vale: ’,’$’X_ASS DW 0Y_ASS DW 0TESTO0 DB ’Inserisci la matrice, riga per riga, separando gli elementi con Enter’,LF,CR,’$’TESTO2 DB LF,CR,LF,CR,’INSERIMENTO ELEMENTI MATRICE’,LF,CR,’$’TESTO3 DB LF,CR,’INSERIMENTO NUMERO RIGHE’,’$’TESTO4 DB LF,CR,’INSERIMENTO NUMERO COLONNE’,’$’TESTO5 DB LF,CR,’La somma e stata eseguita, ecco la matrice: ’,LF,CR,’$’TESTO6 DB LF,CR,LF,CR,’SCELTA PRIMA RIGA DELLA SOMMA(ovvero locazione del risultato)’,LF,CR,’$’TESTO7 DB LF,CR,’SCELTA SECONDA RIGA DELLA SOMMA’,LF,CR,’$’X DW 0Y DW 0M_STR DB LF,CR,’Il risultato vale: ’M_RES DB 2 DUP(?)RES DB ?RISULT DB 20 DUP(?)M DW 50 DUP(0)

DATA ENDS;--------------------------------------------------------------

CSec SEGMENT

ASSUME CS:CSec,DS:Data,SS:Stack

EXTRN INPUT: FAREXTRN BIN2ASC: FAR

MATRICE PROC FAR


WRITELN TESTO0 ;stampa del messaggio di info

;chiede le dimensioni preventive della matrice, prima le righe, poi le colonne

WRITELN TESTO3 ;Lettura numero di righeCALL INPUTMOV I,AX ;I e il numero di righe

WRITELN TESTO4 ;Lettura numero di colonneCALL INPUTMOV J,AX

MOV CX,IMUL CX ;trova le dimensioni della matrice e la mette dentro AX

MOV AH,0MOV DIM,AX

;STAMPA A VIDEO DELLE DIMENSIONI. RIGHE I, COLONNE J E DIMENSIONE.

MOV AX,IMOV BX,OFFSET RESCALL BIN2ASCWRITELN I_STRWRITELN RES

MOV AX,JMOV BX,OFFSET RESCALL BIN2ASCWRITELN J_STRWRITELN RES

MOV AX,DIMMOV BX,OFFSET RESCALL BIN2ASC

106

WRITELN DIM_STRWRITELN RES

;Inserimento valori matrice:

;In AX e dentro lo stack in posizione TOP c’ e la dimensione della matrice

MOV BX,OFFSET M ;fa puntare SI all’inizio di MMOV SI,0MOV DX,0PUSH BXPUSH SIWRITELN TESTO2

Elemento: CALL INPUT

POP SIPOP BXMOV AH,0MOV [BX],AL ;inserisce il valoreINC SI ;punta alla posizione successivaADD BX,1PUSH BXPUSH SICMP SI,DIM ;Inseriti tutti i valori della matrice? SI -> continua

JNE Elemento ;altrimenti andiamo a inserire il numero successivo

CALL SOMMAR ;chiamata della funzione di richiesta e somma delle due righe

;STAMPA A VIDEO DEL RISULTATO DELLA SOMMA

Stampa:MOV BX,OFFSET M ;fa puntare SI all’inizio di MMOV SI,0PUSH BXPUSH SI

LOOP: MOV AH,0 ;azzera il valore di AXMOV AL,[BX]MOV BX,OFFSET M_RES ;utilizza la funzione BIN2ASC per presentareCALL BIN2ASC ;a schermo il valore.WRITELN M_STRPOP SIPOP BXINC BXINC SIPUSH BXPUSH SICMP SI,DIM ;stampa tutti gli elementiJNE LOOP

USCITA: MOV AH,4CHINT 21H

MATRICE ENDP

; **************************************************;INIZIO ROUTINE DI RICHIESTA E SOMMA DELLE 2 RIGHE

SOMMAR PROC NEAR

WRITELN TESTO6 ;richiesta prima rigaCALL INPUTMOV AH,0MOV X,AX ;X e la prima riga

WRITELN TESTO7 ;richiesta seconda rigaCALL INPUTMOV AH,0MOV Y,AX ;Y e al seconda riga da sommare

MOV SI,XMOV DI,1LOCATE SI,DI ;Viene chiamata la macro locateMOV X_ASS,AX ;sulla prima riga da sommare

MOV SI,Y ;Viene chiamata la macro locate

107

MOV DI,1 ;sulla seconda riga da sommareLOCATE SI,DIMOV Y_ASS,AX

MOV DI,0 ;DI e il contatore dei passi

Somma:MOV BX,OFFSET MADD BX,Y_ASS ;somma a BX lo scostamento assoluto della seconda rigaMOV DH,0MOV DL,[BX] ;mette il valore della seconda riga in DX

MOV BX,OFFSET MADD BX,X_ASS ;somma a Bx la posizione assoluta della prima rigaMOV AH,0MOV AL,[BX] ;mette il valore della prima riga in AXADD AL,DL ;esegue la somma tra i due valoriMOV [BX],AL ;sostituisce il precedente valore nella prima riga

ADD X_ASS,1 ;incrementa tutti gli indici e esegue il controlloADD Y_ASS,1 ;per vedere se siamo arrivati al numeroINC DI ;di colonne (ovvero la dimensione delle righe)CMP DI,JJNE SOMMA

WRITELN TESTO5

RET

SOMMAR ENDP

;FINE ROUTINE; *********************************************************

CSec ENDSEND MATRICE

Esercizio 10.18

Per la soluzione di questo esercizio si deve necessariamente far riferimento all’ Esercizio 10.17 del qualeviene mantenuto tutto il corpo del programma e vengono effettuate solo due modifiche:

1. Definizione nel segmento Dati del vettore R, che con una matrice composta al massimo da 50 elementi,deve essere almeno 25 (questo per una matrice di dimensioni 2x25).

2. Sostituzione della routineSOMMARcon la routineCREAVe della relativa chiamata.

La routineCREAVinizializzaSI al contatore per del numero di righe, ovvero gli elementi di R,BXalla prima posizione della matrice M, infineDI alla prima posizione di R. Sfruttando la memorizzazionedi M, come in Figura 10.1, si puo notare che la creazione del vettore R, consiste nell’eseguire la sommaogni J elementi (con J numero di colonne) e salvarne il risultato in R per I volte (con I numero di righe).

Alla fine si stampa a video il vettoreR.

; *************************************;INIZIO ROUTINE CREAZIONE VETTORE R(n)

CREAV PROC NEAR

MOV SI,0 ;inizializza SI come contatore delle righeMOV BX,OFFSET MMOV DI,OFFSET R

INIZ: MOV CX,J ;CX e il numero di colonneMOV AX,0 ;AX l’accumulatore della somma

SOMM1: MOV DX,[BX]INC BXADD AX,DXLOOP SOMM1 ;si somma tutta la riga

MOV [DI],AX ; si trasferisce il risultato in RINC DIINC SICMP SI,I ;si controlla SI, se e uguale al numero di righe si esce

108

JE EXITJNE INIZ

EXIT: RET

CREAV ENDP

;FINE ROUTINE CREAZIONE VETTORE R(n); *************************************

Esercizio 10.19

Rispetto alla soluzione dell’esercizio 10.17 cambia la modalita di accesso agli elementi della matrice inquanto si tratta di sommare colonne con colonne, invece di righe con righe.In conseguenza della rappresentazione in memoria di M, Figura 10.1, risulta variato solo il punto 7 deipassi della routineSOMMAR. Si riportano i passi della routineSOMMACche effettua l’operazione richiesta.La matrice ha dimensioni M(r,c).

1. Si calcola la posizione assoluta suMdella colonna j e si assegna aSI2. Si deposita il valore puntato daSI in DX3. Si calcola la posizione assoluta suMdella colonna i e si assegna aSI4. Si deposita il valore puntato daSI in AX5. Si esegue la somma diAXeDX6. Si deposita il risultato nella locazione diMpuntata daSI .7. Si itera in base alle dimensioni della matrice, sommando il numero di righe r, agli indici delle colonne.

Il controllo di questo cicloe affidato ad un contatore, il registroCX, che interrompe il ciclo quandoe uguale a c, ovvero al numero delle colonne.

Rispetto all’ Esercizio 10.17 veniva richiesto che la somma fosse depositata nella seconda colonna,e per fare cio e stato invertito l’ordine di estrazione dei valori. L’aggiornamento, come si puo notare,procede per righe (r), non di una unita, in quanto il valore successivo di una colonna, si trova r-locazionipiu avanti.

; ***********************************************;INIZIO ROUTINE RICHIESTA E SOMMA DI DUE COLONNE

SOMMAC PROC NEARWRITELN TESTO6CALL INPUTMOV AH,0MOV X,AX ;X e la prima colonna

WRITELN TESTO7CALL INPUTMOV AH,0MOV Y,AX ;Y e al seconda colonna da sommare

SOMMMA_COLONNE:MOV SI,1MOV DI,XLOCATE SI,DI ;carica la posizione assoluta della prima colonnaMOV X_ASS,AX

MOV SI,1MOV DI,YLOCATE SI,DI ;carica la posizione assoluta della seconda colonnaMOV Y_ASS,AX

MOV DI,0MOV SI,J

Somma: MOV BX,OFFSET MADD BX,X_ASS ;somma a BX lo scostamento assoluto della prima colonnaMOV DH,0MOV DL,[BX] ;mette il valore della prima colonna in DX

MOV BX,OFFSET MATRIXADD BX,Y_ASSMOV AH,0

109

MOV AL,[BX] ;mette il valore della seconda colonna in AX

ADD AL,DL ;esegue la somma tra i due valori

MOV [BX],AL ;sostituisce il precedente valore nella seconda colonna

ADD X_ASS,SI ;incrementa il valore assoluto su MATRIX della primaADD Y_ASS,SI ;e della seconda colonna del valore SI, che e il numeroINC DI ;colonne della matriceCMP DI,IJNE SOMMA

WRITELN TESTO5

RET

SOMMAC ENDP

;FINE ROUTINE RICHIESTA E SOMMA DI DUE COLONNE; ***********************************************

Esercizio 10.20

L’algoritmo e molto semplice. Per ogni carattere della stringa inserita dall’utente, viene eseguita unaricerca suΓ, per determinarne la posizionep. Questo valore viene quindi sommato alla chiavek e vienescritto nella stringa di uscita il valore alla posizionep + k in Ω. Il valorep + k e da intendersi modulo27. In uscita viene presentata la stringa criptata.

;Definizioni di macro

Include Macro.mac

;Segmento Dati e Stack;----------------------------------------------------------------STACK SEGMENT STACK

DB 10 DUP(0)

STACK ENDS;-------------------------------------------------------------

DATA SEGMENTCR EQU 0DHLF EQU 0AHTESTO DB ’Immetti il testo da criptare > ’,’$’GAMMA DB ’ abcdefghijklmnopqrstuvwxyz’,CR,LF,LF,’$’OMEGA DB ’gthe quickbsownfxjmpdvrlazy’,CR,LF,LF,’$’K EQU 1Buffer EQU MaxMax DB FINE_MESS-MESSAGGIOn DB ?MESSAGGIO DB 80 DUP(?)FINE_MESS EQU $DATA ENDS;-------------------------------------------------------------

CODESec SEGMENT ASSUME CS:CODESec,DS:Data,SS:Stack

Main PROC FAR


WRITELN TESTO ;Stampa a video di MessREADLN Buffer ;Lettura stringa


MOV SI,OFFSET Buffer+1 ;muove SI all’inizio della stringa inseritaMOV DI,OFFSET MESSAGGIO ;muove DI all’inizio della stringa di arrivoMOV AL,LF ;Sposta LF in ALMOV [DI],AL ;Scrive in cima all’arrivo il valore LFINC DI ;punta al successivo carattere

110

MOV AL,CR ;idem a prima ---MOV [DI],AL ;---con CR---INC DI ;-----

CALL CriptMe ;chiama la funzione di ordinamento

WRITELN MESSAGGIO ;Stampa il messaggio criptato a video


Main ENDP

CriptMe PROC NEAR; In ingresso a CriptME:; SI: offset della posizione del primo carattere introdotto;; DI: offset della prima posizione libera di MESSAGGIO; CX: numero di caratteri introdotti

Crip: SUB BX,BX ;azzera il registro BX, che sar aINC BX ;l’indice di riferimento posizione (p)INC SIMOV DL,[SI] ;carica in DL il valore puntato da SI

Comp: CMP DL,GAMMA[BX] ;compara il valore della stringa;messa dall’utente con il;primo carattere dell’ alfabeto

JE Prin ;se viene trovato il carattere viene memorizzatoINC BXJMP Comp ; non esiste ciclo di uscita xche la lettera deve essere

;in tutti i modi trovata dentro l’alfabeto

Print: ADD BX,K ;Somma la chiava di criptatura a p.CMP BX,27 ;Esegue un controllo sulla posizioneJNBE Sottrai ;in quanto dobbiamo simulare una codaJNAE Stampa ;circolare

Sottrai: SUB BX,27 ;riparte il conteggio dall’inizio,in quanto;la somma p+k e un numero maggiore a 27

Stampa: MOV AL,OMEGA[BX]MOV [DI],AL ;mette in coda al messaggio di uscita il carattere criptatoINC DI ;passa in uscita al carattere successivoLOOP Crip

Exit: MOV AL,’$’ ;Aggiunta del ’$’MOV [DI],AL ;- a fine stringaMOV AL,0 ; OK!RETRET

CriptMe ENDP

CODESec ENDSEND Main

Esercizio 10.21

Di seguito si mostra la routine che calcola la successione (si veda l’Esercizio 10.22 per il programmachiamante). Il test della parita del termine contenuto in AX viene effettuato con una divisione per 2; seil resto (contenuto in DX)e diverso da zero il numeroe dispari. La routine si ferma quando si raggiungeil numero 1. A tale scopo viene controllato che il quoziente della divisione sia pari a 0; se risulta essere0 allora la routine esce rendendo il controllo al programma chiamante.

; In ingresso: ; AX: contiene il numero ’k’ ; BX: e l’offsetdi memoria dell’area dove costruire la successione ; CX:contiene il numero di iterazioni compiute dalla routine

SubSEG SEGMENT PUBLICASSUME CS:SubSEG

PUBLIC SUCC

111

SUCC PROC FAR

MOV CX, 0 ; azzera il contatore delle iterazioni

START: MOV DX, 0 ; azzera il registro DXINC CX ; CX conta le iterazioni eseguite

PUSH AX ; salvataggio di AX

MOV [BX], AX ; primo termine della successione in memoria

ADD BX, 2 ; aumenta di 2 l’indice BXPUSH BX ; salva BX, dopo serve alla divisioneMOV BX, 2 ; carica il divisoreDIV BX ; procede alla divisionePOP BX ; ripristina BX

CMP AX, 0 ; verifica se la successioneJE FINE ; e arrivata alla fine

CMP DX, 0 ; verifica se il termineJE PARI ; corrente e pariJNE DISP ; o dispari

PARI: POP DX ; svuota lo stack dal valore obsoleto di AXJMP START ; torna su START

DISP: POP AX ; ripristino del valore di AXPUSH BX ; salvataggio di BX per la divisioneMOV BX, 3 ; se e dispari si moltiplica per 3MUL BXPOP BX ; ripristino del valore di BXINC AX ; aggiunge 1, poi si torna a START perJMP START ; la memorizzazione

FINE: POP DX ; svuota lo stack dal valore obsoleto di AXRET ; rende il controllo al chiamante

SUCC ENDPSubSEG ENDSEND

Esercizio 10.22

Di seguito il programma chiamante la routineSUCCche chiede il numerok da tastiera e stampa a videola successione dei numeri trovati.

INCLUDE MACRO.MAC


STACK ENDS


LF EQU 0AHCR EQU 0DHOFLOW DB LF,CR,’Overflow’,LF,CR,’$’M_RIS DB LF,CR,’Termine della successione: ’VIDEO DB 5 DUP(?)RISULT DW 500 DUP(?)

DATA ENDS


EXTRN BIN2ASC:FAREXTRN INPUT: FAREXTRN SUCC: FAR

MAIN LABEL FARMOV AX, DATA ; mette l’indirizzo del segmentoMOV DS, AX ; DATA in DS

112

CALL INPUT ; in AX c’ e il carattere da; tastiera ’k’

MOV BX,OFFSET RISULT ; mette in BX l’offset dell’area di memoriaCALL SUCC ; chiama la routine della successione

MOV SI, 0 ; inizializza i registriMOV DX, 0 ; per la stampa a video

LOOP: MOV AX, WORD PTR RISULT[SI] ; carica il numero da stampare in AX

PUSH SI ; salva i registriPUSH CX ; prima della stampaPUSH DX

MOV BX, OFFSET VIDEO ; codifica ASCIICALL BIN2ASC ; del risultato eWRITELN M_RIS ; stampa a video

POP DX ; ripristino dei registriPOP CXPOP SI

ADD SI, 2 ; incremento dell’indiceINC DX ; incremento del contatore della stampaCMP DX, CX ; test di fine iterazione: si devono stampare

; tanti elementi quanti sono quelli calcolatiJE EXITJNE LOOP


OFLOWR: WRITELN OFLOW ; stampa il messaggio diJMP EXIT ; errore e esce

MainSEG ENDSEND MAIN

Esercizio 10.23

Per la soluzione di questo esercizioe stato utilizzato come compilatore il Microsoft Visual C++, quindil’assembler utilizzatoe obbligatoriamente IA32. Le differenze, in questo preciso caso, si limitano a:

• il nome dei registri, es:BX->EBX;• alcune istruzioni come laIMUL (vedi Esercizio 9.2) hanno una diversa modalita d’uso, mantenendo

invariato l’effetto.

Riportiamo di seguito il listato C della routine e del programma chiamante, secondo le specifichedell’Esercizio, dove pero la funzionesucc restituisce un intero al posto di void; questo per permettereal chiamante una piu semplice gestione della stampa a video dei valori.

//file main.c

#include <stdio.h>

int succint x, int v[];

void main(void)

int k;int i;int numero_elementi;int v[100];

printf("Battere il numero k : ");scanf("%d", &k );

numero_elementi = succ(k, v);

113

for(i=0; i<numero_elementi; i++)printf("\nEcco il risultato : %d", v[i]);

printf("\nFatti %d cicli.\n",i);

////////////////////////////////////////////////////////////

//file succ.c

int succ(int k, int v[])

int temp;int i;i=0;

v[0] = k;

while (k!=1)temp= k%2; //resto divisione intera (modulo 2)

if(temp==0)

k=k/2;v[i]=k;

else

k= (3 * k) +1;v[i]=k;

i++;

return i;

Viene ora presentata la routine in assembler IA32 che corrisponde al codice in formato C del filesucc.c . Semplicemente basta sostituire tutto il contenuto del filesucc.c con il seguente codice eprocedere con la compilazione. Si noti l’uso dello stack come nell’Esercizio 9.14. Le variabili internedella funzione vengono salvate nel verso degli indirizzi decrescenti rispetto alla posizione puntata daEBP, mentre l’indirizzo di ritorno e i parametri si trovano nel verso degli indirizzi crescenti. Da cioderivano i seguenti scostamenti rispetto a EBP (in esadecimale):

C = *v (indirizzo di v)8 = k4 = Ind. ritorno0 = EBP0

-4 = temp-8 = i

L’header della funzionee rimasto uguale a quello che si sarebbe usato in caso di puro codice C,in quanto il Visual Studio non consente la chiamata diretta a funzioni scritte in assembler. Richiedeinvece che il codice assembler sia scritto internamente alla funzione C, ma la chiamata della stessa

114

Figura 10.2 Memorizzazione delle variabili dell’Esercizio 10.23 sullo stack all’atto della chiamata dellaroutine succ .

debba essere gestita dal linker come di consueto. Il codice assembler si inserisce nel modo seguente:__asm... codice ASM ... .

Per ulteriori chiarimenti si invita a visionare le direttive della Microsoft riguardo a questo problemaall’indirizzo:http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vclang/html/

_core_writing_functions_with_inline_assembly.asp

Infine, per semplicita di lettura,e stato inserito prima delle istruzioni assembler il codice C corri-spondente.

//FILE succ.c (con codice interno in assembler)

int succ(int k, int v[])__asm

;INIZIO del codice assembler

;5: int temp;;6: int i;;7: i=0;

mov dword ptr [ebp-8],0 ;i e in posizione -8

;8:;9: v[0] = k;

mov eax,dword ptr [ebp+0Ch]mov ecx,dword ptr [ebp+8]mov dword ptr [eax],ecx ;k e in posizione +8

;11: while (k!=1)ciclo: cmp dword ptr [ebp+8],1

je esci

;12: ;13: temp= k%2;

mov edx,dword ptr [ebp+8]and edx,80000001hjns modulodec edxor edx,0FEhinc edx

modulo: mov dword ptr [ebp-4],edx ;temp e in posizione -4

;15: if(temp==0)cmp dword ptr [ebp-4],0jne dispari

115

;16: ;17: k=k/2;

mov eax,dword ptr [ebp+8]cdqsub eax,edxsar eax,1mov dword ptr [ebp+8],eax

;18: v[i]=k;mov eax,dword ptr [ebp-8]mov ecx,dword ptr [ebp+0Ch]mov edx,dword ptr [ebp+8]mov dword ptr [ecx+eax * 4],edx

;19: ;20: else

jmp aggiorna

;21: ;22: k= (3 * k) +1;

dispari: mov eax,dword ptr [ebp+8]imul eax,eax,3add eax,1mov dword ptr [ebp+8],eax

;23: v[i]=k;mov ecx,dword ptr [ebp-8]mov edx,dword ptr [ebp+0Ch]mov eax,dword ptr [ebp+8]mov dword ptr [edx+ecx * 4],eax

;24: ;25: i++;

aggiorna: mov ecx,dword ptr [ebp-8]add ecx,1mov dword ptr [ebp-8],ecx

;26: jmp ciclo

;28: return i;esci: mov eax,dword ptr [ebp-8]

;29: pop edipop esipop ebxmov esp,ebppop ebpret

//chiusura codice assembler

//ritorno al programma chiamante

Si noti che con la traduzione data dallo statement 29 (“”), il ritorno viene effettuato direttamentedal codice assembler e che quindi il controllo non passa mai dal ritorno del C al programma chiamante(ultimo “”), per il quale il compilatore genera il suo codice.

Esercizio 10.24Mostriamo prima il caso del passaggio del parametro tramite stack. Il programma principalee quellosotto riportato. Esso non merita particolari commenti, se non l’affermazione che esso impiega la routineINPUT, tradotta all’Esercizio 10.14, per la lettura del valore di cui di vuole il fattoriale.

INCLUDE MACRO.MAC

STACK SEGMENT STACKDB 500 DUP(0)

STACK ENDS

DATA SEGMENT PUBLIC ’DATA’LF EQU 0AHCR EQU 0DH

116

M_RIS DB LF,CR,’Ecco il fattoriale : ’RISULT DB 5 DUP(?)DATA ENDS


EXTRN BIN2ASC: FAREXTRN INPUT: FAREXTRN FATT: FAR

FATTO LABEL FARMOV AX, DATA ; mette l’indirizzo del segmentoMOV DS, AX ; DATA in DS

CALL INPUT ; chiede un carattere da tastiera; in AX il carattere inserito

PUSH AXCALL FATT ; lancia la routine del fattorialeADD SP,2 ; ripristina SP alla posizione precedente alla chiamata

MOV BX, OFFSET RISULT ; stampa del risultatoCALL BIN2ASCWRITELN M_RIS


MainSEG ENDSEND FATTO

La routineFATT sotto riportata fa uso dello stack per trattare la ricorsivita. Per verificare la fine delladiscesa ricorsiva si effettua un controllo sul valore del parametro. Quando quest’ultimoe arrivato ad 1 sipuo risalire moltiplicando la successione di termini precedentemente memorizzati sullo stack.

; In ingresso:; AX: numero per cui si richiede il fattoriale; In uscita:; AX: risultato


PUBLIC FATT

FATT PROC FARMOV BP, SP ; recupero del valore diADD BP, 4 ; AX nello stackMOV AX, [BP]CMP AX, 1 ; fine della discesa ricorsiva?JG RECURS ; noJMP FINE ; si

RECURS: DEC AX ; diminuzione del valorePUSH AXCALL FATT ; chiamata ricorsiva

MOV BP, SP ; recupero del precedente valoreADD BP, 6 ; la moltiplicazione avvieneMOV BX, [BP] ; sulla risalitaIMUL BX ; moltiplicazione dei terminiADD SP, 2 ; aggiornamento di SP

FINE: RET

FATT ENDPSubSEG ENDS

END

Per quanto si riferisce al passaggio del parametro tramite AX, si puo ancora usare il precedenteprogramma chiamante, anche se lo statementPUSH AXe il corrispondenteADD SP,2 sono del tuttosuperflui.

; In ingresso:; AX: numero per cui si richiede il fattoriale

117

; In uscita:; AX: risultato


PUBLIC FATT

FATT PROC FARCMP AX, 1 ; verifica se AX eJNE RECURS ; alla fine della discesaRET ; ricorsiva

RECURS: PUSH AX ; se non alla fine:DEC AX ; mette AX nello stackCALL FATT ; decrementa AX e chiama FATT

MOV BP, SP ; copia dallo stack il termineMOV BX, [BP] ; da moltiplicareIMUL BX ; moltiplicazione dei terminiADD SP, 2 ; aggiorna SP prima del RETRET ; rende il controllo al chiamante

FATT ENDPSubSEG ENDS

END

118

Soluzioni - italy-s3-mhe-prod.s3-website-eu-west...

Documents

Transcript of Soluzioni - italy-s3-mhe-prod.s3-website-eu-west...