Tags:
create new tag
view all tags




Esercitazioni di Architetture 2
Docente: Novella Bartolini, canali A-D e E-O

Orario di ricevimento:
Mercoledì 12:00 - 14:00
Stanza 309, Dipartimento di Informatica,
Via Salaria 113 - Roma

AVVISO

La prova di assembler prevista per l'esame degli studenti del canale del Prof. Tronci si terrà nel laboratorio Colossus, in Via Salaria 113.
Per la suddetta prova, si raccomanda di esercitarsi ad usare il simulatore SPIM da linea di comando, secondo le istruzioni fornite nell'allegato: SPIM_command-line.pdf: Spim Command Line Options.
Sebbene sia consentito l'uso di altri simulatori, gli studenti tengano presente che gli elaborati devono funzionare correttamente quando invocati secondo la sintassi spim nomefile.s .

HOMEWORK

Homework 1.
Si scrivano le seguenti funzioni che operano su matrici, le quali prendono in $a0 l'indirizzo del primo elemento in memoria di una matrice quadrata, il cui numero di righe e colonne sia dato in $a1.
1) trovaelementominimo: restituisce in $v0 e $v1 rispettivamente l'indice di riga e di colonna dell'elemento minimo
2) trovaelementomassimo: restituisce in $v0 e $v1 rispettivamente l'indice di riga e di colonna dell'elemento massimo
3) permutarighe: la funzione prende nei registri $a2 e $a3 gli indici k e j rispettivamente, e sostituisce in memoria la matrice A con la matrice A' ottenuta a partire da A permutandone le righe k e j.
Esempio:

A =| 1, 0, 1|
| 2, 1, 2|
| 3, 3, 2|
mentre, con k=0 e j=2, A'= | 3, 3, 2|
| 2, 1, 2|
| 1, 0, 1|

Homework 2.
Si scriva una funzione cercasottostringa che prenda in $a0 e $a1 gli indirizzi iniziali delle stringhe s e z rispettivamente.
La funzione restituisca in $v0 il valore 1 se la stringa z è contenuta in s, e 0 altrimenti.
Esempio:
s="La città di Roma è molto calda d'estate". Se z="calda", la funzione restituisce 1. Se z = "fredda" la funzione restituisce 0.

Homework 3.
Scrivere la funzione che restituisca in $v0 il valore del prodotto scalare tra due vettori v e z, i cui indirizzi in memoria siano dati in $a0 e $a1 rispettivamente, e la cui lunghezza sia data in $a2. Si ricorda che il prodotto scalare tra due vettori v e z, con v=<v1, v2, ..., vk> e z=<z1, z2, ..., zk>
vale p= v1*z1+ v2*z2+ ...+ vk*zk.
Esempio:
v=<2,3,4> e z=<1,2,1>. Il valore di p è 2*1+3*2+4*1=12.


Testi per le esercitazioni

1) Appendice A, del seguente libro:
David A. Patterson, John L. Hennessy, "Struttura e Progetto dei Calcolatori", ed. Zanichelli

2) Manuale di istruzioni del simulatore SPIM .


Entrambi questi testi e molti altri, sono disponibili online alla
pagina relativa alla documentazione sul simulatore SPIM .





Comunicazioni

Esercizi consigliati per esercitarsi per la prova scritta di assembler

1. Si scriva un programma in assembler MIPS che chieda all'utente di scrivere un elenco di numeri interi terminante con lo zero, memorizzi tali elementi in un vettore. Il programma deve scrivere su console l'elenco degli elementi di posizione pari e la loro somma.
Soluzione: elem_pari.s

2. Si scriva un programma in assembler MIPS che, data una stringa A di caratteri in memoria, copi in una stringa B solo le parole di posizione pari. Il programma deve scrivere su console la stringa B e il numero di parole copiate.
Esempio:
Stringa A: "Questo non è un esercizio facile devo fare molta attenzione altrimenti posso sbagliare"
Stringa B: "non un facile fare attenzione posso"
Soluzione: parole_pari.s

3. Si scriva un programma in assembler MIPS che, data una matrice A di interi in memoria, stampi sulla console l'elenco degli elementi A(i,j) per i quali i==j-1. Esempio:

A =| 0, 1, 2, 3, 4|
| 5, 6, 7, 8, 9|,
| 1, 1, 2, 3, 4|
deve stampare 1, 7, 3.
Soluzione: matrice_stamp_el.s

4. Si scriva un programma in assembler MIPS che, data una stringa A di caratteri in memoria, stampi sulla console una stringa B ottenuta dalla precedente sostituendo ogni occorrenza di vocale con il carattere "1" e ogni consonante con il carattere "0". Per semplicità considerare come consonante anche i caratteri numerici o speciali. Esempio:
Stringa A: "Esercizio"
Stringa B: "101001011"

5. Si scriva un programma in assembler MIPS che, data una stringa A di caratteri in memoria, scriva se è palindroma a meno di spazi. Esempio:
Stringa1: "ailatiditalia" è palindroma
Stringa2: "aabbccdc c b b aa" è palindroma
Stringa3: "acetone" non è palindroma

6. Si scriva un programma in assembler MIPS che, data una stringa A, conti il numero di caratteri che la compongono e le occorrenze del carattere "a". Il programma deve inoltre scrivere in memoria una stringa B ottenuta dalla stringa A letta al contrario. Esempio:
Stringa A: "enoteca" contiene 7 caratteri di cui 1 occorrenza del carattere "a"
Stringa B: "acetone"

7. Si scriva un programma in assembler MIPS che, data in memoria una matrice A di 3 righe e 5 colonne, scriva in memoria e sulla console una matrice B corrispondente alla trasposizione di A. Esempio:

A =| 0, 1, 2, 3, 4|
| 5, 6, 7, 8, 9|,
| 1, 1, 2, 3, 4|
deve stampare | 0, 5, 1|
| 1, 6, 1|
| 2, 7, 2|
| 3, 8, 3|
| 4, 9, 4|

8. Si scriva un programma in assembler MIPS che calcoli, attraverso una doppia chiamata ricorsiva, la funzione f(n) così definita:

f(n) =f(n-1) + f(n-2), se n>1
1, se n=1
0, se n=0

Soluzione: fibonacci_complessitesponenziale.s

9. Si scriva un programma in assembler MIPS che calcoli, attraverso una sola chiamata ricorsiva, la funzione f(n) a due valori così definita:

f(n) = (f(n);f(n-1)), se n>1
(1;0), se n=1
(0;0), se n=0

Soluzione: Fibonacci_complessitlineare.s

10. Si scriva un programma in assembler MIPS che calcoli, attraverso chiamate mutuamente ricorsive delle funzioni f() e g(), il valore della funzione f(n).

f(n) = 5, se x<=0
3*g(x-1)+1, altrimenti
g(n)= 2, se x<3
2+f(x-1), altrimenti
Soluzione: mutuaricorsione.s

11. Scrivere in assembler MIPS un programma che calcoli ricorsivamente il valore di f(10), dove f(x) è definita come segue:

f(x) = f(x-1) + x*g(x-1), se x>=5
2, se x<5
g(x)= f(x-2) +1, se x >= 3
7, altrimenti


Soluzione: es11.s

12. Scrivere in assembler MIPS un programma che, data una stringa Z di caratteri, ne ordini i caratteri in ordine alfabetico decrescente, utilizzando la funzione ricorsiva bubble(x) che prende in ingresso l'indirizzo (x) del carattere iniziale della stringa da ordinare e restituisce una stringa ordinata, allo stesso indirizzo della stringa di partenza (ovvero la funzione bubble(x) rimpiazza la stringa di partenza con la stringa ordinata).

Soluzione: sort.s

13. Scrivere un programma in assembler MIPS che determini se una stringa Z è palindroma utilizzando una funzione ricorsiva f(x,y) che prende in ingresso l?indirizzo del carattere iniziale (x) e l?indirizzo dell?ultimo carattere utile (y) e restituisce in uscita il valore 1 se la stringa è palindroma e zero altrimenti.

Soluzione: palindrom.s

14. Scrivere un programma in assembler MIPS che calcoli la somma dei primi 5 elementi di un vettore di interi facendo uso di una funzione iterativa somma_primi_cinque che prende in ingresso nel registro $a0 l'indirizzo del vettore, e restituisce in uscita, nel registro $v0, la somma degli elementi letti.

Soluzione: scritto3-6.s

15. Scrivere un programma in assembler MIPS che calcoli la funzione ricorsiva McCarthy91(n) di un qualsiasi numero n letto in ingresso.
Si veda il file: McCharty91.pdf per una definizione formale della funzione McCarthy91.

Soluzione: McCarthy.s

16. Esercizio sul fattoriale in due versioni del caso base, per risolvere il dubbio di qualcuno....
fattoriale_giusto1.s: fattoriale_giusto1.s
fattoriale_giusto2.s: fattoriale_giusto2.s

17. Scrivere un programma che decida se una matrice in ingresso è simmetrica o no. Il programma deve invocare una funzione f che prende in ingresso due parametri: l'indirizzo della matrice in memoria e la sua dimensione (n=numero di righe e di colonne). La funzione f deve restituire il valore 1 se la matrice è simmetrica e 0 altrimenti. La funzione f deve prevedere un confronto tra la prima riga e la prima colonna e poi chiamare sè stessa ricorsivamente sulla sottomatrice ottenuta eliminando la prima riga e la prima colonna.

Soluzione: matrice_simmetrica_ricorsivo1.s

18. Scrivere un programma che data una word in memoria decida se la sua rappresentazione binaria è palindroma. Si prevedano due metodi risolutivi, ovvero: A) si confronti il bit i-esimo con il bit 32-(i-1)-esimo per 1<=i<=16. B) si crei una word ottenuta da quella iniziale rovesciandone la rappresentazione binaria e si confronti tale parola con quella di partenza.

Soluzione:
word_palindroma_metodoA.s
word_palindroma_metodoB.s


19. (Esercizio di sbarramento dell'esame del 25 Giugno 2007)

Si scriva un programma in assembler MIPS che carichi un numero x presente in memoria e calcoli il numero y ottenuto a partire da x prendendo della sua rappresentazione binaria solo la cifra più significativa (la prima cifra non nulla a partire da sinistra). Si stampi la rappresentazione di y in base 10. Non è consentito l’uso di istruzioni aritmetiche (addizione, sottrazione, divisione, moltiplicazione).

Esempio: x=1410=11102 ---> y=10002=810
Il programma deve stampare il numero 8.

Soluzione: sbarramento_25_06_2007.s

20. Scrivere un programma che dato un intero in memoria, usi le operazioni logiche per calcolare il suo complemento a due. Stampare il risultato ottenuto con il servizio di sistema operativo per la stampa di numeri interi. Stamparne inoltre la rappresentazione binaria.

Soluzione:
complemento_a_2.s

21. Si scriva un programma che legga due valori in ingresso: i e b, con i compreso tra 1 e 32, e b tra 0 e 1.
Sia data una word W in memoria contenente una stringa di bit. Il programma deve configurare il bit i-esimo di W con il valore di b. Soluzione:
stampabit.s

Questa pagina è stata visitata: volte.

-- NovellaBartolini - 14 Apr 2011

Edit | Attach | Watch | Print version | History: r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r2 - 2011-06-02 - NovellaBartolini






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2021 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback