Tags:
create new tag
view all tags

Prova scritta di Assembler - 7/2/2002

Vedi RisultatiProvaAsmFebbraio2002.

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

Edit | Attach | Watch | Print version | History: r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r2 - 2002-02-15 - AndreaSterbini






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2022 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback