EsercitazioniAA2010-2011 < Architetture2/MZ

Tags: view all tags
<html>
<body>
<center>
<font size=+1>
</font></center>
<hr>
<hr>


<table width=100% bgcolor="GOLD"><tr><th class="topicTitleCell" align="left">
<span class="topicTitle" >
<font size=+2>Esercitazioni di Architetture 2 </font><font size=+1><br>Docente: 
<a href="http://twiki.dsi.uniroma1.it/twiki/view/Users/NovellaBartolini"><font color="white">Novella Bartolini</font></a>, canali A-D e E-O</font>
<br>
<strong>Orario di ricevimento: </strong><br>Mercoledì 12:00 - 14:00<br>Stanza 309, Dipartimento di Informatica, <br> Via Salaria 113 - Roma<br><br></span>
</th></tr>
<br><br>
<tr><td class="topicItemCell" align="left"><font size=+1><b>AVVISO</b></font><br>
<font color="red"></font>
<br>
La prova di assembler prevista per l'esame degli studenti del canale del Prof. Tronci si terrà nel laboratorio Colossus, in Via Salaria 113.<br>
Per la suddetta prova, si raccomanda di esercitarsi ad usare il simulatore SPIM da linea di comando, secondo le istruzioni fornite nell'allegato:
 [[%ATTACHURL%/SPIM_command-line.pdf][SPIM_command-line.pdf]]: Spim Command Line Options.<br>
Sebbene sia consentito l'uso di altri simulatori, gli studenti tengano presente che gli elaborati devono funzionare correttamente quando
invocati secondo la sintassi <b>spim nomefile.s </b>. 
<br><BR>
<font size=+1><b>HOMEWORK</b></font><br>

<b>Homework 1.</b><br>
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. <br>
1) <b>trovaelementominimo</b>: restituisce in $v0 e $v1 rispettivamente l'indice di riga e di colonna dell'elemento minimo<br>
2) <b>trovaelementomassimo</b>: restituisce in $v0 e $v1 rispettivamente l'indice di riga e di colonna dell'elemento massimo<br>
3) <b>permutarighe</b>: 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.<br>
Esempio:  
<br>
<table><tr><td>A  =</td><td>| 1, 0, 1|<br>
  | 2, 1, 2|  <br>
      | 3, 3, 2|<br></td><td>mentre, con k=0 e j=2,  A'= </td><td>
| 3, 3, 2|<br>
  | 2, 1, 2|  <br>
      | 1, 0, 1|<br>
</td></tr></table>


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

<b>Homework 3.</b><br>
Scrivere la funzione che restituisca in $v0 il valore del prodotto scalare tra due vettori <b>v</b> e <b>z</b>, 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 <b>v</b> e <b>z</b>, con <b>v</b>=<v<small><sub>1</sub></small>, v<small><sub>2</sub></small>, ..., v<small><sub>k</sub></small>> e  <b>z</b>=<z<small><sub>1</sub></small>, z<small><sub>2</sub></small>, ..., z<small><sub>k</sub></small>> <br>vale p= v<small><sub>1</sub></small>*z<small><sub>1</sub></small>+ v<small><sub>2</sub></small>*z<small><sub>2</sub></small>+
...+ v<small><sub>k</sub></small>*z<small><sub>k</sub></small>.
<br>Esempio: <br>
v=<2,3,4> e z=<1,2,1>. 
Il valore di p è 2*1+3*2+4*1=12.



<tr><td class="topicItemCell" align="left"><br>
<font size=+1><b>Testi per le esercitazioni</b></font><br>

1) [[http://twiki.di.uniroma1.it/pub/Architetture2/MZ/EsercitazioniAA2003-2004/cod-appa.pdf][Appendice A]], del seguente libro:  <br>
David A. Patterson, John L. Hennessy, "Struttura e Progetto dei Calcolatori", ed. Zanichelli<br><br>
2) [[http://twiki.di.uniroma1.it/pub/Architetture2/MZ/EsercitazioniAA2003-2004/spiminst.pdf][Manuale di istruzioni del simulatore SPIM]]  . <br>
<br><br>
Entrambi questi testi e molti altri, sono disponibili online alla <br> 
pagina relativa alla <a href="http://twiki.dsi.uniroma1.it/twiki/view/Architetture2/SimulatoreSpim"> documentazione sul simulatore SPIM </a>.
<br><br></td></tr>
<tr><td class="topicItemCell" align="left">
<br>

<br><br>
</td></tr>

<tr><td class="topicItemCell" align="left">
<br>
<font size=+1><b>Comunicazioni</b><br>
</font>
</td></tr>




<tr><td class="topicItemCell" align="left">
<br>
<font size=+1><b>Esercizi consigliati per esercitarsi per la prova scritta di assembler</b></font><br><br>
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. <br>
Soluzione: [[http://twiki.di.uniroma1.it/pub/Architetture2/MZ/EsercitazioniAA2003-2004/elem_pari.s][elem_pari.s]] 
<br><br>
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.<br>
Esempio: 
<br>
Stringa A: "Questo non è un esercizio facile devo fare molta attenzione altrimenti posso sbagliare"<br>
Stringa B: "non un facile fare attenzione posso" <br>
Soluzione: [[http://twiki.di.uniroma1.it/pub/Architetture2/MZ/EsercitazioniAA2003-2004/parole_pari.s][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:<br>
<table><tr><td>A  =</td><td>| 0, 1, 2, 3, 4|<br>
  | 5, 6, 7, 8, 9|,  <br>
      | 1, 1, 2, 3, 4|<br></td><td>deve stampare 1, 7, 3.</td></tr></table>
Soluzione: [[http://twiki.di.uniroma1.it/pub/Architetture2/MZ/EsercitazioniAA2003-2004/matrice_stamp_el.s][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: <br>
Stringa A: "Esercizio"<br>
Stringa B: "101001011"<br>

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: <br>
Stringa1: "ailatiditalia" è palindroma <br>
Stringa2: "aabbccdc c b   b aa" è palindroma <br>
Stringa3: "acetone" non è palindroma <br>

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: <br>
Stringa A: "enoteca" contiene 7 caratteri di cui 1 occorrenza del carattere "a" <br>
Stringa B: "acetone" <br>

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:<br>
<table><tr><td>A  =</td><td>| 0, 1, 2, 3, 4|<br>
  | 5, 6, 7, 8, 9|,  <br>
      | 1, 1, 2, 3, 4|<br></td><td>deve stampare </td><td>
| 0, 5, 1|<br>
  | 1, 6, 1|  <br>
      | 2, 7, 2|<br>
  | 3, 8, 3|  <br>
      | 4, 9, 4|<br>
</td></tr></table>


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

<table><tr><td>f(n)  =</td><td>f(n-1) + f(n-2), se n>1<br>
  1, se n=1 <br>
0, se n=0 </td></tr></table>


Soluzione:  [[http://twiki.di.uniroma1.it/pub/Architetture2/MZ/EsercitazioniAA2003-2004/fibonacci_complessitesponenziale.s][fibonacci_complessitesponenziale.s]]
<br>


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

<table><tr><td>f(n)  =</td><td> (f(n);f(n-1)), se n>1 <br>
                      (1;0), se n=1 <br>
(0;0), se n=0 </td></tr></table>


Soluzione: [[http://twiki.di.uniroma1.it/pub/Architetture2/MZ/EsercitazioniAA2003-2004/Fibonacci_complessitlineare.s][Fibonacci_complessitlineare.s]]<br>
<br>

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).<br>

<table><tr><td>f(n)  =</td><td> 5, se x<=0 
                     <br>
                      3*g(x-1)+1,  altrimenti </td>
</tr>
<tr>
<td>
g(n)=
</td>
<td>
2, se x<3 
<br>
2+f(x-1), altrimenti
</td>
</tr>
</table>
Soluzione: [[http://twiki.di.uniroma1.it/pub/Architetture2/MZ/EsercitazioniAA2003-2004/mutuaricorsione.s][mutuaricorsione.s]]<br>


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

<table><tr><td>f(x)  =</td><td> f(x-1) + x*g(x-1), se x>=5 
                     <br>
                      2, se x<5 
</td>
</tr>
<tr>
<td>
g(x)=
</td>
<td>
f(x-2) +1, se x >= 3 
<br>
7, altrimenti
</td>
</tr>
</table><br><br>
Soluzione: [[http://twiki.di.uniroma1.it/pub/Architetture2/MZ/EsercitazioniAA2003-2004/es11.s][es11.s]]<br>




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). <br><br>
Soluzione: [[http://twiki.di.uniroma1.it/pub/Architetture2/MZ/EsercitazioniAA2003-2004/sort.s][sort.s]] <br>

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. <br><br>
Soluzione: [[http://twiki.di.uniroma1.it/pub/Architetture2/MZ/EsercitazioniAA2003-2004/palindrom.s][palindrom.s]]<br>
<br>

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 <em>somma_primi_cinque</em> che prende in ingresso nel registro $a0 l'indirizzo del vettore, e restituisce in uscita, nel registro $v0, la somma degli elementi letti.
<br><br>
Soluzione: 
[[http://twiki.di.uniroma1.it/pub/Architetture2/MZ/EsercitazioniAA2003-2004/scritto3-6.s][scritto3-6.s]]
<br><br>
15. Scrivere un programma in assembler MIPS che calcoli la funzione ricorsiva <nop>McCarthy91(n) </nop>di un qualsiasi numero n letto in ingresso.<br> Si veda il file:   [[http://twiki.di.uniroma1.it/pub/Architetture2/MZ/EsercitazioniAA2003-2004/McCharty91.pdf][McCharty91.pdf]] per una definizione formale della funzione <nop>McCarthy91</nop>.
<br><br>
Soluzione:
[[http://twiki.di.uniroma1.it/pub/Architetture2/MZ/EsercitazioniAA2003-2004/McCarthy.s][McCarthy.s]]
<br><br>

16. Esercizio sul fattoriale in due versioni del caso base, per risolvere il dubbio di qualcuno....
<br> [[http://twiki.di.uniroma1.it/pub/Architetture2/MZ/EsercitazioniAA2003-2004/fattoriale_giusto1.s][fattoriale_giusto1.s]]: fattoriale_giusto1.s
<br> [[http://twiki.di.uniroma1.it/pub/Architetture2/MZ/EsercitazioniAA2003-2004/fattoriale_giusto2.s][fattoriale_giusto2.s]]: fattoriale_giusto2.s
<br><br>

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.
<br><br>
Soluzione:  [[http://twiki.di.uniroma1.it/pub/Architetture2/MZ/EsercitazioniAA2003-2004/matrice_simmetrica_ricorsivo1.s][matrice_simmetrica_ricorsivo1.s]]
<br>


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: <br>
[[http://twiki.di.uniroma1.it/pub/Architetture2/MZ/EsercitazioniAA2003-2004/word_palindroma_metodoA.s][word_palindroma_metodoA.s]]<br>
[[http://twiki.di.uniroma1.it/pub/Architetture2/MZ/EsercitazioniAA2003-2004/word_palindroma_metodoB.s][word_palindroma_metodoB.s]]


<br>
19. (<b>Esercizio di sbarramento dell'esame del 25 Giugno 2007</b>)<br><br>
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&#8217;uso di istruzioni aritmetiche (addizione, sottrazione, divisione, moltiplicazione).

Esempio:
x=14<small><sub>10</sub></small>=1110<small><sub>2</sub></small>  --->   y=1000<small><sub>2</sub></small>=8<small><sub>10</sub></small><br>
Il programma deve stampare il numero 8.
<br><br>
Soluzione:  [[http://twiki.di.uniroma1.it/pub/Architetture2/MZ/EsercitazioniAA2003-2004/sbarramento_25_06_2007.s][sbarramento_25_06_2007.s]]
 <br>

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: <br>
[[http://twiki.di.uniroma1.it/pub/Architetture2/MZ/EsercitazioniAA2003-2004/complemento_a_2.s][complemento_a_2.s]]<br>


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.<br>
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: <br>
[[http://twiki.di.uniroma1.it/pub/Architetture2/MZ/EsercitazioniAA2003-2004/stampabit.s][stampabit.s]]<br>




</tr>
</table>
<center> Questa pagina è stata visitata: 
<!-- Start of StatCounter Code -->
<script type="text/javascript" language="javascript">
var sc_project=266655; 
</script>
<script type="text/javascript" language="javascript" src="http://www.statcounter.com/counter/counter.js"></script>
<noscript><a href="http://www.statcounter.com" target="_blank"><img  src="http://c1.statcounter.com/counter.php?sc_project=266655&amp;java=0" alt="web counter" border="0"></a> </noscript>
<!-- End of StatCounter Code -->
volte.

</body>
</html>


   



-- Users.NovellaBartolini - 14 Apr 2011