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.

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

   .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

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<0

• G(i) = i---+ F(i-1) se i>0
• G(i) = 2 * F(i---+1) se i<0

Soluzione Esercizio A2

   .text
F:
   beqz $a0, casobaseF   # se i=0
   bgt $a0, $0, fPositiva   # se i>0
   blt $a0, $0, fNegativa   # se i<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<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<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<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

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)

   .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

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

   .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

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<0

Soluzione Esercizio B2

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

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

   .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

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

   .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

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<b

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

Soluzione Esercizio D2

   .text

F:
   beq $a0, $a1, casobaseF   # se a=b
   blt $a0, $a1, minoreF   # se a<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<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
   

-- AndreaSterbini - 19 Jun 2001