Prova scritta di Assembler - 7/2/2002

Vedi RisultatiProvaAsmFebbraio2002.

Si implementi l'algoritmo di mergesort per ordinare un array di 2^N word (con N<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<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^N 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:

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

La routine mergesort può essere implementata come segue:

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

-- AndreaSterbini - 07 Feb 2002