Università degli Studi di Udine
Corsi di laurea in Ingegneria Elettronica
Architettura dei calcolatori / Fondamenti di Informatica II 9 febbraio 2012 - Prova scritta
Matricola __________________
Nome _____________________
Cognome __________________
ISTRUZIONI (da leggere attentamente)
1) Lo studente è tenuto a scrivere, correggere, compilare ed eseguire su computer (a casa o in laboratorio) gli esercizi di programmazione prima della prova orale. Alla prova orale lo studente deve portare una memory pen USB contenente i sorgenti dei programmi corretti e le stampe dei relativi file.
2) Non è consentito l’uso di libri, appunti, calcolatrici, telefoni cellulari.
3) Rispondere sinteticamente negli spazi di fianco o seguenti le domande, oppure sul retro del foglio.
1. (4 punti) Una variabile reale con rappresentazione in floating point, singola precisione, eccesso 127, contiene il valore BF000000. Quanto vale il numero reale da essa rappresentato? Illustrare tutti i passaggi effettuati.
-0.5. Infatti:
B F 0 0 0 0 0 0 1011 1111 0000 0000 0000 0000 0000 0000
Il primo bit, di segno, vale 1 e quindi il valore rappresentato è negativo.
L’esponente vale 01111110, cioè 126. Nella rappresentazione in eccesso 127 significa -1, quindi la mantissa va moltiplicata per 2-1.
La mantissa è tutta a zero, quindi resta solo il valore 1 sottinteso (per via della normalizzazione).
Quindi: - 1 x 2-1 = -0.5.
2. (2 punti) Indicare le affermazioni vere.
Il program counter:
[ ] in nessun caso può contenere l’indirizzo di un dato
[ ] viene salvato nello stack quando viene eseguita una istruzione CALL [ ] viene salvato nello stack quando viene eseguita una istruzione di salto
[ ] all’inizio della fase di instruction fetch contiene l’indirizzo della prossima istruzione da eseguire [ ] viene sempre incrementato dello stesso numero di unità, pari al numero di byte di una word
[ ] in nessun caso può contenere l’indirizzo di un dato
[X] viene salvato nello stack quando viene eseguita una istruzione CALL [ ] viene salvato nello stack quando viene eseguita una istruzione di salto
[X] all’inizio della fase di instruction fetch contiene l’indirizzo della prossima istruzione da eseguire [ ] viene sempre incrementato dello stesso numero di unità, pari al numero di byte di una word
3. (2 punti) X16+X15+X2+1 rappresenta:
[ ] uno schema di memorizzazione dei bit ridondanti nella codifica di Hamming [ ] una funzione di compressione senza perdita
[ ] una funzione di compressione con perdita [ ] un polinomio generatore per il CRC
[ ] uno schema di memorizzazione dei bit ridondanti nella codifica di Hamming [ ] una funzione di compressione senza perdita
[ ] una funzione di compressione con perdita [X] un polinomio generatore per il CRC
Si consideri la libreria in linguaggio C per manipolare file bitmap vista a lezione, così definita:
typedef unsigned char byte;
typedef unsigned short int word;
typedef unsigned long int dword;
#define BMPFILETYPE 0x4D42
typedef struct tagCOLORTRIPLE {
byte blue;
byte green;
byte red;
} COLORTRIPLE;
typedef struct tagFILEHEADER {
word ImageFileType;
dword FileSize;
word Reserved1;
word Reserved2;
dword ImageDataOffset;
} FILEHEADER;
typedef struct tagBMPHEADER {
dword HeaderSize;
dword ImageWidth;
dword ImageHeight;
word NumberOfImagePlanes;
word BitsPerPixel;
dword CompressionMethod;
dword SizeOfBitmap;
dword HorizonalResolution;
dword VerticalResolution;
dword NumberOfColorsUsed;
dword
NumberOfSignificantColors;
} BMPHEADER;
typedef struct tagBITMAP {
dword width;
dword height;
COLORTRIPLE *pixel;
FILEHEADER fileheader;
BMPHEADER bmpheader;
} BITMAP;
#define PIXEL(image, row, column) \ image.pixel [(row( * image.width +
(column)]
BITMAP ReadBitmap (FILE *fp);
void WriteBitmap (BITMAP bitmap, FILE *fp);
BITMAP CreateEmptyBitmap
(dword height, dword width);
void ReleaseBitmapData (BITMAP *bitmap);
4. (10 punti) Si vogliono realizzare delle immagini quadrate del tipo di quelle riportate in figura. Si tratta di colorare ciascun pixel di un livello di grigio pari al valore della funzione seno il cui argomento sia proporzionale alla distanza del pixel dal centro dell’immagine.
Le due immagini in figura sono di
dimensioni 200 x 200 pixel e il periodo del seno utilizzato per il disegno è pari a 10 pixel nell’immagine di sinistra e 40 pixel in quella di destra (NOTA: la distanza espressa in numero di pixel si intende misurata sugli
assi x e y). Si osservi che, in generale, se p è il periodo espresso in numero di pixel, quando la distanza è pari a kp (k intero), l’argomento del seno deve valere 2kπ.
Si scriva un programma in linguaggio C che riceva sulla riga di comando il nome del file bitmap di uscita, la dimensione N e il periodo p, entrambi espressi in numero di pixel. Il programma deve scrivere nel file bitmap un’immagine N x N come sopra descritta.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "bmp.h"
void disegna_onde (BITMAP bmpout, int p);
int main (int argc, char *argv[]) {
FILE *fpout;
BITMAP bmpout;
int n;
if (argc != 4) {
printf ("Errore negli argomenti: onde <file> <dimensione> <periodo (in pixel)>\n");
exit (EXIT_FAILURE);
}
if ((fpout = fopen (argv[1], "wb")) == NULL) {
printf ("Errore di apertura del file\n");
exit (EXIT_FAILURE);
}
n = atoi (argv[2]);
bmpout = CreateEmptyBitmap (n, n);
disegna_onde (bmpout, atoi (argv[3]));
WriteBitmap (bmpout, fpout);
ReleaseBitmapData (&bmpout);
fclose (fpout);
return EXIT_SUCCESS;
}
void disegna_onde (BITMAP bmpout, int p) {
int i, j, xy_centro;
double r, lum, freq;
freq = 1.0 / p;
xy_centro = (int) bmpout.height / 2.0;
for (i = 0; i < bmpout.height; i++) for (j = 0; j < bmpout.width; j++) {
r = sqrt ((i - xy_centro) * (i - xy_centro) + (j - xy_centro) * (j - xy_centro));
lum = 127 * (1 + sin (2 * M_PI * freq * r));
PIXEL(bmpout, i, j).red = PIXEL(bmpout, i, j).green = PIXEL(bmpout, i, j).blue = lum;
}
return;
}
Un elaboratore (il modello didattico SimCPU visto a lezione) dispone di CPU (a 16 bit) con 16 registri di uso generale (R0, R1, ..., R15) più il Program Counter, l’Instruction Register, lo Stack Pointer e 4 flag Z (zero), N (negative), C (carry) e V (overflow). Si ricorda che il linguaggio assembler di tale elaboratore dispone delle seguenti istruzioni:
5. (7 punti) Si completi la funzione INVERTI_E_FILTRA in linguaggio assembler, riportata nel seguito, che riceve in R1 l’indirizzo di un vettore di numeri interi scritti su 16 bit e in R2 la dimensione di tale vettore, e che inverte il contenuto del vettore eliminando i valori nulli. In R0 è restituita la nuova dimensione del vettore.
Per esempio, se il vettore contiene i valori 45 129 0 5 221 0 86, viene modificato in 86 221 5 129 45 e in R0 viene restituito il valore 5.
La soluzione scelta fa uso dello stack per memorizzare i valori non nulli del vettore e prelevarli in ordine inverso.
assembly inst. name machine code action
LDWI d X load word 00010000dddd0000 DATA(16) d <- X LDWA d A load word 00100000dddd0000 ADDR(16) d <- mem[A]
LDWR d a load word 00110000ddddaaaa d <- mem[a]
LDBI d X load byte 00010001dddd0000 DATA(8) d <- X LDBA d A load byte 00100001dddd0000 ADDR(16) d <- mem[A]
LDBR d a load byte 00110001ddddaaaa d <- mem[a]
STWA s A store word 00100010ssss0000 ADDR(16) mem[A] <- s STWR s a store word 00110010ssssaaaa mem[a] <- s STBA s A store byte 00100011ssss0000 ADDR(16) mem[A] <- s STBR s a store byte 00110011ssssaaaa mem[a] <- s MV s d move 00000100ssssdddd d <- s PUSH s push 00001000ssss0000 push (s) POP d pop 00001001dddd0000 d <- pop () SPRD d read SP 00001101ssss0000 d <- SP SPWR s write SP 00001110ssss0000 SP <- s
ADD s d add 01000000ssssdddd d <- d + s SUB s d subtract 01000001ssssdddd d <- d - s NOT r bitwise NOT 01000010rrrr0000 r <- ~r AND s d bitwise AND 01000011ssssdddd d <- d & s OR s d bitwise OR 01000100ssssdddd d <- d | s XOR s d bitwise XOR 01000101ssssdddd d <- d ^ s INC r increment 01001000rrrr0000 r <- r + 1 DEC r decrement 01001001rrrr0000 r <- r + 1 LSH r left shift 01001010rrrr0000 r <- r << 1 RSH r right shift 01001011rrrr0000 r <- r >> 1
assembly inst. name machine code action
INW d A input word 10000000dddd0000 IN_ADDR(16) d <- read[A]
INB d A input byte 10000001dddd0000 IN_ADDR(16) d <- read[A]
OUTW s A out word 10000010ssss0000 OUT_ADDR(16) out[A] <- s OUTB s A out byte 10000011ssss0000 OUT_ADDR(16) out[A] <- s
TSTI A test input 1000010000000000 IN_ADDR(16) if completed then Z <- 1 else Z <- 0
TSTO A test output 1000010100000000 OUT_ADDR(16) if completed then Z <- 1 else Z <- 0
BR A branch 1100000000000000 ADDR(16) PC <- A JMP F jump 11000001FFFFFFFF PC <- PC + F
JMPZ F jump if zero 11000010FFFFFFFF if (z == 1) PC <- PC + F JMPNZ F jump if not zero 11000011FFFFFFFF if (z == 0) PC <- PC + F JMPN F jump if negative 11000100FFFFFFFF if (N == 1) PC <- PC + F JMPNN F jump if not neg. 11000101FFFFFFFF if (N == 0) PC <- PC + F JMPC F jump if carry 11000110FFFFFFFF if (C == 1) PC <- PC + F JMPV F jump if overflow 11000111FFFFFFFF if (V == 1) PC <- PC + F CALL A subroutine call 1100100000000000 ADDR(16) push (PC); PC <- A RET return from sub. 1100100100000000 PC <- pop() HLT halt 1100111100000000 halt
LEGENDA:
- lettere minuscole = registri; lettere maiuscole = dati numerici - ‘r’ = registro letto e modificato
- ‘s’ = registro soltanto letto - ‘d’ = registro modificato
- ‘a’ = registro il cui contenuto è usato come indirizzo - FFFFFFFF = offset (in complemento a 2)
INVERTI_E_FILTRA: MV R1 R11 ; usa R11 come puntatore
MV R2 R12 ; usa R12 come contatore all'indietro
LDWI R13 0 ; usa R13 come contatore dei valori filtrati (non nulli) LOOP1: ____________ ; carica l'elemento del vettore puntato da R11
____________ ; salta l'operazione di push se e` zero PUSH R10
INC R13 ; incrementa il contatore dei valori inseriti nello stack DOPOPUSH: INC R11 ; aggiorna il puntatore (R11 e` incrementato di due INC R11 ; per puntare alla word successiva)
DEC R12 ; decrementa il contatore
_____________
MV R1 R11 ; riporta il puntatore all'inizio del vettore MV R13 R12 ; usa R12 come contatore all'indietro
JMPZ FINE ; salta alla fine nel caso il vettore ora sia vuoto LOOP2: _____________ ; recupera il valore dallo stack
_____________ ; scrivi il valore in memoria all'indirizzo contenuto in R11 INC R11 ; aggiorna il puntatore (R11 e` incrementato di due
INC R11 ; per puntare alla word successiva) DEC R12 ; decrementa il contatore
_____________
FINE: _____________ ; scrivi in R0 la nuova lunghezza del vettore RET
INVERTI_E_FILTRA: MV R1 R11 ; usa R11 come puntatore
MV R2 R12 ; usa R12 come contatore all'indietro
LDWI R13 0 ; usa R13 come contatore dei valori filtrati (non nulli) LOOP1: LDWR R10 R11 ; carica l'elemento del vettore puntato da R11
JMPZ DOPOPUSH ; salta l'operazione di push se e` zero PUSH R10
INC R13 ; incrementa il contatore dei valori inseriti nello stack DOPOPUSH: INC R11 ; aggiorna il puntatore (R11 e` incrementato di due INC R11 ; per puntare alla word successiva)
DEC R12 ; decrementa il contatore JMPNZ LOOP1
MV R1 R11 ; riporta il puntatore all'inizio del vettore MV R13 R12 ; usa R12 come contatore all'indietro
JMPZ FINE ; salta alla fine nel caso il vettore ora sia vuoto LOOP2: POP R10 ; recupera il valore dallo stack
STWR R10 R11 ; scrivi il valore in memoria all'indirizzo contenuto in R11 INC R11 ; aggiorna il puntatore (R11 e` incrementato di due
INC R11 ; per puntare alla word successiva) DEC R12 ; decrementa il contatore
JMPNZ LOOP2
FINE: MV R13 R0 ; scrivi in R0 la nuova lunghezza del vettore RET
6. (3 punti) Tradurre in linguaggio macchina l’istruzione JMPZ FINE del frammento di codice sotto riportato, scrivendo i valori in esadecimale. Illustrare i passaggi effettuati.
____ LOOP: JMPZ FINE ____ DEC R0 JMPNZ LOOP FINE: RET
04 LOOP: JMPZ FINE C2
XX DEC R0 <-- qui punta il PC al momento dell’esecuzione dell’istruzione JMPZ XX
XX JMPNZ LOOP XX
XX FINE: RET <-- questa e` la destinazione del salto: 4 byte in avanti XX
7. (1 punto) Cosa significa MMU? MEMORY MANAGEMENT UNIT
8. (1 punto) A cosa serve la MMU?
[ ] gestire il vettore di interrupt [ ] gestire la memoria virtuale
[ ] gestire l’interruzione di un processo dovuta all’esaurimento della time slice
[ ] gestire il vettore di interrupt [X] gestire la memoria virtuale
[ ] gestire l’interruzione di un processo dovuta all’esaurimento della time slice
