ProvaAsmFebbraio2002 < Architetture2/MZ

---+++ Prova scritta di Assembler - 7/2/2002

Vedi RisultatiProvaAsmFebbraio2002.

Si implementi l'algoritmo di *mergesort* per ordinare un array di 2<sup>N</sup> word (con N&lt;32).

Si ricorda il funzionamento dell'algoritmo di *mergesort*, basato sulla operazione di fusione (*merge*) di due vettori ordinati:

*merge*: dati due vettori X ed Y *ordinati*, per ottenere il vettore *ordinato* Z=X unione Y:
	* si scorrono contemporaneamente i due vettori X ed Y
	* se tutti gli elementi di X sono stati consumati: si aggiungono a Z i rimanenti elementi di Y
	* se tutti gli elementi di Y sono stati consumati: si aggiungono a Z i rimanenti elementi di X
	* se nè X nè Y sono stati completamente consumati:
		* siano *x* ed *y* i valori degli elementi correnti di X ed Y
			* se *x&lt;y*	  si copia *x* nel vettore Z, si incrementa l'indice di X e quello di Z
			* *altrimenti*	 si copia *y* nel vettore Z, si incrementa l'indice di Y e quello di Z

*mergesort*: per ordinare un vettore generico di 2<sup>N</sup> word si procede come segue:
	* se il vettore è formato da un solo elemento è già ordinato
	* altrimenti:
		* lo si divide in due metà
		* le si ordina separatamente usando l'algoritmo di *mergesort*
		* si usa l'operazione di *merge* per fondere le due metà (ordinate) ed ottenere il vettore ordinato

*Svolgimento*:
	* Si implementino separatamente le due subroutine *merge* e *mergesort*
	* si noti che *mergesort* è una subroutine ricorsiva
	* per la routine *merge* si usino 3 registri per contenere gli indici necessari a scorrere gli elementi dei vettori X, Y, Z

*Suggerimenti*:
	* si passino a *merge* i seguenti 4 argomenti:
		* i 3 indirizzi di inizio dei vettori X, Y e Z (zona di memoria in cui costruire il vettore risultato)
		* il valore *n*: numero di elementi del vettore X (e anche di Y)
	* si passino a *mergesort* i seguenti 3 argomenti:
		* i 2 indirizzi di inizio dei vettori X e Z (area di memoria di appoggio)
		* il valore *n*: numero di elementi del vettore X (e anche di Z)

---+++ Soluzione

La routine *merge* può essere implementata come segue:
<pre>
merge:	# $a0=n  $a1=Z	$a2=X	$a3=Y
	li $t0, 0					 # contatore degli elementi di X
	li $t1, 0					 # contatore degli elementi di Y
	li $t2, 0					 # contatore degli elementi di Z
loop:
	beq $t0, $a0, copiaY	  # se gli X sono finiti si copiano in Z i rimanenti di Y
	beq $t1, $a0, copiaX	  # se gli Y sono finiti si copiano in Z i rimanenti di X
	lw  $s0, ($a2)			  # x (elemento corrente di X)
	lw  $s1, ($a3)			  # y (elemento corrente di Y)
	blt $s0, $s1, minore	  # se x&lt;y
	sw $s1, ($a1)				# z = y
	addi $a3, $a3, 4			# prossimo elemento di Y
	addi $t1, $t1, 1			# numero di elementi consumati di Y
	b avanti
minore:
	sw $s0, ($a1)				# z = x
	addi $a2, $a2, 4			# prossimo elemento di X
	addi $t0, $t0, 1			# numero di elementi consumati di X
avanti:	
	addi $a1, $a1, 4			# prossimo elemento di Z
	b loop
copiaX:
	move $t1, $t0				# uso copiaY per copiare i rimanenti elementi in Z
	move $a3, $a2
copiaY:
	beq $t1, $a0, finemerge
	lw $s0, ($a3)				# elemento corrente di Y
	sw $s0, ($a1)				# z = y
	addi $a3, $a3, 4			# prossimo elemento di Y
	addi $a1, $a1, 4			# prossimo elemento di Z
	addi $t1, $t1, 1			# conteggio degli elementi
	b copiaY
finemerge:
	jr $ra
</pre>

La routine *mergesort* può essere implementata come segue:
<pre>
mergesort:						# $a0=n, $a1=Z (area temporanea), $a2=X (sorgente e destinazione)
	beq $a0, 1, esci			# un vettore di dimensione n=1 è già ordinato
	subu $sp, $sp, 16		  # si alloca lo spazio su stack per 4 words (3 argomenti e $ra)
	sw $a0, 0($sp)			  # n
	sw $a1, 4($sp)			  # Z
	sw $a2, 8($sp)			  # X
	sw $ra,12($sp)			  # $ra
	div $a0, $a0, 2			 # n' = n/2
	jal mergesort				# prima chiamata ricorsiva per ordinare la prima metà
	mul $s0, $a0, 4			 # offset per arrivare all'inizio della seconda metà
	add $a1, $a1, $s0		  # Z' = Z---+ (n/2)*4
	add $a2, $a2, $s0		  # X' = X---+ (n/2)*4
	jal mergesort				# seconda chiamata ricorsiva per ordinare la seconda metà
# ora in Z si trovano le due metà ordinate, le fondiamo mettendo il risultato in X
									 # il numero di elementi n'' = n/2 è già in $a0
	move $a2, $a1				# una delle due sorgenti e' X'' = Z' (la seconda metà ordinata)
	lw $a1, 8($sp)			  # la destinazione e' Z'' = X
	lw $a3, 4($sp)			  # l'altra sorgente e' Y'' = Z (la prima metà ordinata)
	jal merge					 # si fondono i due vettori e si ottiene in X il vettore ordinato
# si ripristinano i registri
	lw $a0, 0($sp)			  # n
	lw $a1, 4($sp)			  # Z
	lw $a2, 8($sp)			  # X
	lw $ra,12($sp)			  # $ra
	addi $sp, $sp, 16		  # si rilascia lo spazio su stack 
esci:
	jr $ra
</pre>


-- Users.AndreaSterbini - 07 Feb 2002 <br>
<!--
	* Set ALLOWTOPICCHANGE = Users.DocentiArcGroup
-->
This topic: Architetture2/MZ > ProvaAsmFebbraio2002
Topic revision: r2 - 2002-02-15 - AndreaSterbini