SoluzioniProva19Giugno2001 < Architetture2/MZ

---++ Prova di Assembler SPIM del 19-6-2001 - entrambi i canali

Ecco i testi e le (prime) soluzioni delle prova di recupero del 19 Giugno 2001.

Il resto delle soluzioni seguira' appena possibile.

I risultati sono su RisultatiProva19Giugno2001.

----
%TOC%
----
---++ Compito A
---+++ Esercizio A1 (15 punti)

Si scriva una procedura che serve a calcolare la matrice trasposta *Trasp* di una data matrice *Matr*.

Per far questo:
   * si presupponga che il numero di righe e di colonne siano stati gia' chiesti in input tramite syscall e che siano compresi tra 1 e 20 inclusi.
   * si allochi lo spazio necessario per le matrici *Matr* e *Trasp*
   * si scriva una routine che riceve come argomenti:
      * $a0 = numero di righe
      * $a1 = numero di colonne
   * e che calcola *Trasp*

Si ricorda la relazione tra gli elementi delle due matrici:
   * Trasp(i,j) = Matr(j,i)

---+++ Soluzione Esercizio A1
<pre>
   .data
Matr: .word 0:400   # matrice di nrig * ncol elementi
Trasp: .word 0:400   # matrice di ncol * nrig elementi

   .text
faiTrasposta:      # ho $a0=nrig e $a1=ncol
   li $t0, 0   # indice nella matrice Matr
   li $t1, 0   # i=0   (e' piu' comodo usare indici da 0 a nrig-1
   li $t2, 0   # j=0   per i conti seguenti)
   sub $t3, $a0, 1   # in $t3 metto nrig-1
   sub $t4, $a1, 1   # in $t4 metto ncol-1
   
ciclo:
   lw $t3, Matr($t0)   # carico in $t3 l'elemento corrente Matr(i,j)
   mul $t4, $t1, $a0   # calcolo la posizione dell'elemento Trasp(j,i)
# nella trasposta le righe sono lunghe nrig elementi (come una colonna di Matr)
   add $t4, $t2, $t4   # pos = 4*(i*nrig---+ j)
   sll $t4, $t4, 2      # la moltiplicazione per 4 di cui sopra
   sw $t3, Trasp($t4)
   addi $t0, 4      # passo all'elemento seguente
   addi $t1, 1      # i=i---+1
   blt $t1, $t3, ciclo   # se non e' ancora finita la riga
   li $t1, 0      # i=0
   addi $t2, 1      # j=j---+1
   blt $t2, $t4, ciclo   # se non e' ancora finita la matrice
   jr $ra
</pre>

---+++ Esercizio A2 (15 punti)

Si scrivano le due procedure mutuamente ricorsive *F* e *G* definite come segue:
   * F(0) = 0
   * F(i) = i - G(i-1) se i>0 
   * F(i) = 3---+ G(i+i) se i&lt;0

   * G(i) = i---+ F(i-1) se i>0 
   * G(i) = 2 * F(i---+1) se i&lt;0 

---+++ Soluzione Esercizio A2
<pre>
   .text
F:
   beqz $a0, casobaseF   # se i=0
   bgt $a0, $0, fPositiva   # se i>0
   blt $a0, $0, fNegativa   # se i&lt;0

#   F(0) = 0
casobaseF:
   li $v0, 0      # F=0
   jr $ra

#   F(i) = i - G(i-1) se i>0 
fPositiva:   # devo calcolare F(i) = i - G(i-1)
   subu $sp, $sp, 8   # alloco due words su stack
   sw $ra, 0($sp)      # salvo su stack il return address perche' F e G sono mutuamente ricorsive
   sw $a0, 4($sp)      # salvo su stack $a0 (cioe' i) che modifico
   sub $a0, $a0, 1      # i = i-1
   jal G         # G(i-1)
   lw $a0, 4($sp)      # ripristino $a0 cioe' i
   sub $v0, $a0, $v0   # F=i-G(i-1)
   lw $ra, 0($sp)      # ripristino $ra
   add $sp, $sp, 8   # libero le 2 words allocate prima
   jr $ra         # torno dalla subroutine

#   F(i) = 3---+ G(i+i) se i&lt;0
fNegativa:   # devo calcolare F(i) = 3---+ G(i+i)
   subu $sp, $sp, 8   # alloco due words su stack
   sw $ra, 0($sp)      # salvo su stack il return address perche' F e G sono mutuamente ricorsive
   sw $a0, 4($sp)      # salvo su stack $a0 (cioe' i) che modifico
   add $a0, $a0, $a0   # i = i---+i
   jal G         # G(i---+i)
   addi $v0, $v0, 3   # F(i) = 3---+ G(i+i)
   lw $a0, 4($sp)      # ripristino $a0 cioe' i
   lw $ra, 0($sp)      # ripristino $ra
   add $sp, $sp, 8   # libero le 2 words allocate prima
   jr $ra         # torno dalla subroutine

G:
   bgt $a0, $0, gPositiva   # se i>0
   blt $a0, $0, gNegativa   # se i&lt;0

#   G(i) = i---+ F(i-1) se i>0 
gPositiva:   # devo calcolare G(i) = i---+ F(i-1)
   subu $sp, $sp, 8   # alloco due words su stack
   sw $ra, 0($sp)      # salvo su stack il return address perche' F e G sono mutuamente ricorsive
   sw $a0, 4($sp)      # salvo su stack $a0 (cioe' i) che modifico
   sub $a0, $a0, 1      # i = i-1
   jal F         # F(i-1)
   lw $a0, 4($sp)      # ripristino $a0 cioe' i
   add $v0, $a0, $v0   # G=i---+F(i-1)
   lw $ra, 0($sp)      # ripristino $ra
   addu $sp, $sp, 8   # libero le 2 words allocate prima
   jr $ra         # torno dalla subroutine
   
#   G(i) = 2 * F(i---+1) se i&lt;0    
gNegativa:   # devo calcolare G(i) = 2 * F(i---+1) ... praticamente lo stesso di prima :-)
   subu $sp, $sp, 8   # alloco due words su stack
   sw $ra, 0($sp)      # salvo su stack il return address perche' F e G sono mutuamente ricorsive
   sw $a0, 4($sp)      # salvo su stack $a0 (cioe' i) che modifico
   add $a0, $a0, 1      # i = i---+1
   jal F         # F(i---+1)
   li $a0, 2      # mi serve la costante 2, la metto in $a0 che poi ripristinero'
   mul $v0, $v0, $a0   # G(i) = 2 * F(i---+i)
   lw $a0, 4($sp)      # ripristino $a0 cioe' i
   lw $ra, 0($sp)      # ripristino $ra
   addu $sp, $sp, 8   # libero le 2 words allocate prima
   jr $ra         # torno dalla subroutine
</pre>

----
---++ Compito B
---+++ Esercizio B1 (15 punti)

Si scriva una procedura che serve a calcolare la somma degli elementi che si trovano sulla diagonale della matrice cubica (a 3 dimensioni) che si chiama *Cubo*.

Per far questo:
   * si presupponga che il lato del cubo sia stato gia' chiesto in input tramite syscall e che sia compreso tra 1 e 30 inclusi.
   * si allochi lo spazio necessario per la matrice *Cubo*
   * si scriva una routine che riceve come argomenti:
      * $a0 = numero di righe
   * e che calcola la somma degli elementi sulla diagonale

Si ricorda che la diagonale di un cubo e' l'insieme degli elementi con indici uguali *i=j=k*

---+++ Soluzione Esercizio B1 (lenta)
<pre>
   .data
Cubo: .word 0:27000   # un cubo di lato 30 e' formato da 30*30*30=27000 elementi

   .text
# come sommare gli elementi della diagonale senza pensarci troppo su :-)
sommaDiagonaleCuboLenta:   
   li $t0, 0   # indice in memoria
   li $t1, 1   # i=1
   li $t2, 1   # j=1
   li $t3, 1   # k=1
   li $v0, 0   # il risultato all'inizio e' 0
ciclo:
   bne $t1, $t2, next   # se i!=j vado avanti
   bne $t2, $t3, next   # i=j ma j!=k, vado avanti
   lw $t4, Cubo($t0)
   add $v0, $v0, $t4   # i=j=k, sommo l'elemento corrente
next:
   addi $t0, $t0, 4   # prossima word in memoria
   addi $t1, $t1, 1   # i=i---+1
   blt  $t1, $a0, ciclo   # non e' ancora finita la riga?
   li $t1, 1      # i=1 (prima casella della prossima riga)
   addi $t2, $t2, 1   # j=j---+1
   blt  $t2, $a0, ciclo   # non e' ancora finita la fetta?
   li $t1, 1      # i=1 (prima casella della riga)
   li $t2, 1      # j=1 (prima riga del prossimo strato)
   addi $t3, $t3, 1   # k=k---+1
   blt  $t3, $a0, ciclo   # non e' ancora finito il cubo?
   jr $ra         # ritorno al chiamante
</pre>

---+++ Soluzione Esercizio B1 (veloce)

Notate che per passare da un elemento al successivo della diagonale
basta sommare 4*(lato*lato---+ lato + 1) = 4*(lato*(lato+1)+1)
infatti si deve passare al *prossimo strato, prossima riga, prossimo elemento*
<pre>
   .data
Cubo: .word 0:27000   # un cubo di lato 30 e' formato da 30*30*30=27000 elementi

   .text
sommaDiagonaleCuboVeloce:   
   li $t0, 0      # indice in memoria
   addi $t1, $a0, 1   # calcoliamo (lato---+1)
   mul $t1, $t1, $a0   # lato*(lato---+1)
   addi $t1, $t1, 1   # lato*(lato---+1)+1
   sll $t1, $t1, 2   # moltiplico per 4
   li $t2, 1      # i=1 (numero di elementi sommati)
   li $v0, 0      # il risultato all'inizio e' 0
ciclo:
   lw $t3, Cubo($t0)
   add $v0, $v0, $t3   # sommo l'elemento corrente
   add $t0, $t0, $t1   # passo al prossimo elemento della diagonale   
   addi $t2, $t2, 1   # i=i---+1
   blt  $t2, $a0, ciclo   # non e' ancora finita la riga?
   jr $ra      # ritorno al chiamante
</pre>

---+++ Esercizio B2 (15 punti)

Si scrivano le due procedure mutuamente ricorsive *F* e *G* definite come segue:
   * F(0) = 1 
   * F(i) = i * G((i-1) mod 9) 

   * G(i) = F(i-3)---+ 4 se i>0 
   * G(i) = F(i---+2) * i se i&lt;0 

---+++ Soluzione Esercizio B2
<pre>
   .text
F:
   beqz $a0, casobaseF   # se i=0

#   F(i) = i * G((i-1) mod 9) 
   subu $sp, $sp, 12   # alloco tre words su stack
   sw $ra, 0($sp)      # salvo su stack il return address perche' F e G sono mutuamente ricorsive
   sw $a0, 4($sp)      # salvo su stack $a0 (cioe' i) che modifico
   sw $t0, 8($sp)   # salvo su stack $t0 che modifico
   sub $a0, $a0, 1      # i = i-1
   li $t0, 9      # mi serve la costante 9
   rem $a0, $a0, $t0   # i = (i-1 mod 9)
   jal G         # G((i-1)mod 9)
   lw $t0, 8($sp)      # ripristino $t0
   lw $a0, 4($sp)      # ripristino $a0 cioe' i
   mul $v0, $a0, $v0   # F=i * G((i-1) mod 9) 
   lw $ra, 0($sp)      # ripristino $ra
   add $sp, $sp, 12   # libero le 3 words allocate prima
   jr $ra         # torno dalla subroutine

#    F(0) = 1 
casobaseF:
   li $v0, 1      # F=1
   jr $ra

G:
   bgt $a0, $0, gPositiva   # se i>0
   blt $a0, $0, gNegativa   # se i&lt;0

#   G(i) = F(i-3)---+ 4 se i>0 
gPositiva:   # devo calcolare G(i) = F(i-3)---+ 4
   subu $sp, $sp, 8   # alloco due words su stack
   sw $ra, 0($sp)      # salvo su stack il return address perche' F e G sono mutuamente ricorsive
   sw $a0, 4($sp)      # salvo su stack $a0 (cioe' i) che modifico
   sub $a0, $a0, 3    # i = i-3
   jal F         # F(i-3)
   add $v0, $v0, 4   # G(i) = F(i-3)---+ 4
   lw $a0, 4($sp)      # ripristino $a0 cioe' i
   lw $ra, 0($sp)      # ripristino $ra
   add $sp, $sp, 8   # libero le 2 words allocate prima
   jr $ra         # torno dalla subroutine
   
#   G(i) = F(i---+2) * i se i&lt;0 
gNegativa:   # devo calcolare G(i) = F(i---+2) * i 
   subu $sp, $sp, 8   # alloco due words su stack
   sw $ra, 0($sp)      # salvo su stack il return address perche' F e G sono mutuamente ricorsive
   sw $a0, 4($sp)      # salvo su stack $a0 (cioe' i) che modifico
   addi $a0, $a0, 2      # i = i---+2
   jal F         # F(i---+2)
   lw $a0, 4($sp)      # ripristino $a0 cioe' i
   mul $v0, $v0, $a0   # G(i) =  F(i---+2) * i 
   lw $ra, 0($sp)      # ripristino $ra
   addu $sp, $sp, 8   # libero le 2 words allocate prima
   jr $ra         # torno dalla subroutine
</pre>

----
---++ Compito C
---+++ Esercizio C1 (15 punti)

Si scriva una procedura che serve a ruotare gli elementi di una matrice *Matr* di una colonna a sinistra (cioe' spostare ciascuna riga di un elemento a sinistra con il primo elemento che va all'ultimo posto).

Per far questo:
   * si presupponga che il numero di righe e di colonne siano stati gia' chiesti in input tramite syscall e che siano compresi tra 1 e 20 inclusi.
   * si allochi lo spazio necessario per la matrice *Matr*
   * si scriva una routine che riceve come argomenti:
      * $a0 = numero di righe
      * $a1 = numero di colonne
   * e che ruota ogni riga di un elemento a sinistra

---+++ Soluzione Esercizio C1

Questo esercizio poteva essere risoloto in vari modi:
   * per ogni riga scambiare successivamente due elementi
      * 1 con 2, 2 con 3, 3 con 4, ......, n-1 con n
   * spostare gli elementi della prima colonna di una riga in giu' e poi spostare tutti gli elementi della matrice di un elemento a sinistra
   * per ogni riga:
      * mettere da parte il rpimo elemento
      * spostare gli altri di un elemento a sinistra
      * salvare l'elemento nell'ultima posizione della riga

*... devo finire di scrivere la soluzione ...*

---+++ Esercizio C2 (15 punti)

Si scrivano le due procedure mutuamente ricorsive *F* e *G* definite come segue:
   * F(0,j) = j * 3
   * F(i,j) = G(j,i-2)---+ 2

   * G(0,j) = j * j
   * G(i,j) = F(j---+1,i) * 3

---+++ Soluzione Esercizio C2
<pre>
   .text
F:
   beqz $a0, casobaseF   # se i=0

#   F(i,j) = G(j,i-2)---+ 2
   subu $sp, $sp, 12   # alloco due words su stack
   sw $ra, 0($sp)      # salvo su stack il return address perche' F e G sono mutuamente ricorsive
   sw $a0, 4($sp)      # salvo su stack $a0 (cioe' i) che modifico
   sw $a1, 8($sp)      # salvo su stack $a0 (cioe' i) che modifico
   sub $a1, $a0, 2     # j' = i-2
   lw $a0, 8($sp)      # i = j
   jal G               # G(j',i-2)
   lw $a1, 4($sp)      # ripristino $a1 cioe' j
   lw $a0, 4($sp)      # ripristino $a0 cioe' i
   lw $ra, 0($sp)      # ripristino $ra
   add $sp, $sp, 12    # libero le 2 words allocate prima
   addi $v0, $v0, 2    # F=G(j,i-2)---+ 2
   jr $ra              # torno dalla subroutine

#   F(0,j) = j * 3
casobaseF:
   mul $v0, $a1, 3      # F=j*3
   jr $ra

G:
   beqz $a0, gBase  # se i=0

#  G(i,j) = F(j---+1,i) * 3
   subu $sp, $sp, 12   # alloco due words su stack
   sw $ra, 0($sp)      # salvo su stack il return address perche' F e G sono mutuamente ricorsive
   sw $a0, 4($sp)      # salvo su stack $a0 (cioe' i) che modifico
   sw $a1, 8($sp)      # salvo su stack $a0 (cioe' i) che modifico
   addi $a0, $a1, 1    # i' = j---+1
   lw $a1, 4($sp)      # j = i
   jal F               # F(j---+1,i)
   lw $a1, 4($sp)      # ripristino $a1 cioe' j
   lw $a0, 4($sp)      # ripristino $a0 cioe' i
   lw $ra, 0($sp)      # ripristino $ra
   add $sp, $sp, 12    # libero le 2 words allocate prima
   mul $v0, $v0, 3     # F(j---+1,i) * 3
   jr $ra              # torno dalla subroutine
   
#   G(0,j) = j * j
casobaseF:
   mul $v0, $a1, $a1      # G=j*j
   jr $ra

</pre>

----
---++ Compito D
---+++ Esercizio D1 (15 punti)

Si scriva una procedura che serve a calcolare la somma degli elementi che si trovano sulla superficie della matrice cubica (a 3 dimensioni) che si chiama *Cubo*.

Per far questo:
   * si presupponga che il lato del cubo sia stato chiesto gia' in input tramite syscall e che sia compreso tra 1 e 30 inclusi.
   * si allochi lo spazio necessario per la matrice *Cubo*
   * si scriva una routine che riceve come argomenti:
      * $a0 = lato del cubo
   * e che calcola la somma degli elementi presenti sulla superficie

Si ricorda che la superficie di un cubo e' l'insieme degli elementi che hanno almeno un indice 
   * uguale a 1 
   * oppure uguale al lato

---+++ Soluzione Esercizio D1
<pre>
   .data
Cubo: .word 0:27000   # un cubo di lato 30 e' formato da 30*30*30=27000 elementi

   .text
sommaSuperficieCubo:   
   li $t0, 0   # indice in memoria
   li $t1, 1   # i=1
   li $t2, 1   # j=1
   li $t3, 1   # k=1
   li $t4, 1   # costante per i confronti
   li $v0, 0   # il risultato all'inizio e' 0
ciclo:
   beq $t1, $t4, somma  # se i=1 sommo
   beq $t1, $a0, somma  # se i=lato sommo
   beq $t2, $t4, somma  # se j=1 sommo
   beq $t2, $a0, somma  # se j=lato sommo
   beq $t3, $t4, somma  # se k=1 sommo
   beq $t3, $a0, somma  # se k=lato sommo
   b next
somma:
   lw $t4, Cubo($t0)
   add $v0, $v0, $t4   # i=j=k, sommo l'elemento corrente
next:
   addi $t0, $t0, 4   # prossima word in memoria
   addi $t1, $t1, 1   # i=i---+1
   blt  $t1, $a0, ciclo   # non e' ancora finita la riga?
   li $t1, 1      # i=1 (prima casella della prossima riga)
   addi $t2, $t2, 1   # j=j---+1
   blt  $t2, $a0, ciclo   # non e' ancora finita la fetta?
   li $t1, 1      # i=1 (prima casella della riga)
   li $t2, 1      # j=1 (prima riga del prossimo strato)
   addi $t3, $t3, 1   # k=k---+1
   blt  $t3, $a0, ciclo   # non e' ancora finito il cubo?
   jr $ra         # ritorno al chiamante
</pre>

---+++ Esercizio D2 (15 punti)

Si scrivano le due procedure mutuamente ricorsive *F* e *G* definite come segue:
   * F(a,b) = a  se a=b
   * F(a,b) = 2---+ G(a, a-b) se a>b
   * F(a,b) = G(a, b-a) se a&lt;b

   * G(a,b) = a * F(b, a)

---+++ Soluzione Esercizio D2
<pre>
   .text

F:
   beq $a0, $a1, casobaseF   # se a=b
   blt $a0, $a1, minoreF   # se a&lt;b
   bgt $a0, $a1, maggioreF   # se a>b

# F(a,b) = a  se a=b
casobaseF:
   move $v0, $a0      # F=a
   jr $ra

# F(a,b) = 2---+ G(a, a-b) se a>b
maggioreF:
   subu $sp, $sp, 8  # alloco due words su stack
   sw $ra, 0($sp)    # salvo su stack il return address perche' F e G sono mutuamente ricorsive
   sw $a1, 4($sp)    # salvo su stack $a1 (cioe' a) che modifico
   sub $a1, $a0, $a1 # b=a-b
   jal G             # 
   lw $a1, 4($sp)    # ripristino $a1 cioe' b
   lw $ra, 0($sp)    # ripristino $ra
   add $sp, $sp, 8   # libero le 2 words allocate prima
   add $v0, $v0, 2   # 2---+ G(a, a-b)
   jr $ra            # torno dalla subroutine

# F(a,b) = G(a, b-a) se a&lt;b
minoreF:
   subu $sp, $sp, 8  # alloco due words su stack
   sw $ra, 0($sp)    # salvo su stack il return address perche' F e G sono mutuamente ricorsive
   sw $a1, 4($sp)    # salvo su stack $a1 (cioe' a) che modifico
   sub $a1, $a1, $a0 # b=b-a
   jal G             # 
   lw $a1, 4($sp)    # ripristino $a1 cioe' b
   lw $ra, 0($sp)    # ripristino $ra
   add $sp, $sp, 8   # libero le 2 words allocate prima
   jr $ra            # torno dalla subroutine

# G(a,b) = a * F(b, a)
G:
   subu $sp, $sp, 12   # alloco tre words su stack
   sw $ra, 0($sp)      # salvo su stack il return address perche' F e G sono mutuamente ricorsive
   sw $a0, 4($sp)      # salvo su stack $a0 (cioe' a) che modifico
   sw $a1, 8($sp)      # salvo su stack $a1 (cioe' b) che modifico
   move $a0, $a1       # scambio gli argomenti
   lw   $a1, 4($sp)
   jal F               # F(b,a)
   lw $a1, 8($sp)      # ripristino $a1 cioe' b
   lw $a0, 4($sp)      # ripristino $a0 cioe' a
   lw $ra, 0($sp)      # ripristino $ra
   add $sp, $sp, 12    # libero le 3 words allocate prima
   add $v0, $v0, $a0   # a * F(b, a)
   jr $ra              # torno dalla subroutine
   
</pre>

----

-- Users.AndreaSterbini - 19 Jun 2001 <br>

<!--
   * Set ALLOWTOPICCHANGE = Users.DocentiArcGroup
-->
This topic: Architetture2/MZ > SoluzioniProva19Giugno2001
Topic revision: r8 - 2002-06-04 - AndreaSterbini