Transcript
No Orden
Apellido y nombre
L.U.
Cantidad de hojas
Organizaci´ on del Computador 2 Primer parcial – 29/09/16 (Resoluci´on) 1 (40)
2 (40)
3 (20)
Normas generales Numere las hojas entregadas. Complete en la primera hoja la cantidad total de hojas entregadas. Entregue esta hoja junto al examen, la misma no se incluye en la cantidad total de hojas entregadas. Est´ a permitido tener los manuales y los apuntes con las listas de instrucciones en el examen. Est´ a prohibido compartir manuales o apuntes entre alumnos durante el examen. Cada ejercicio debe realizarse en hojas separadas y numeradas. Debe identificarse cada hoja con nombre, apellido y LU. La devoluci´ on de los ex´ amenes corregidos es personal. Los pedidos de revisi´ on se realizar´ an por escrito, antes de retirar el examen corregido del aula. Los parciales tienen tres notas: I (Insuficiente): 0 a 59 pts, A- (Aprobado condicional): 60 a 64 pts y A (Aprobado): 65 a 100 pts. No se puede aprobar con A- ambos parciales. Los recuperatorios tienen dos notas: I: 0 a 64 pts y A: 65 a 100 pts.
Ej. 1.
(40 puntos)
Ej. 1.1.
Enunciado
Considerar un ´ arbol binario de b´ usqueda con la siguiente estructura. typedef struct node_t { int value; node *derecha; node *izquierda; } node; 1. (25p) Construir una funci´ on en ASM que determine si el ´arbol esta ordenado. La misma debe respetar la aridad void ordenado(node* arbol, node** desordenado), tomando como par´amentro el puntero al primer nodo del ´ arbol y un doble puntero a nodo donde ser´a almacenado el puntero al sub´ arbol m´ as peque˜ no que resulte estar desordenado. En el caso que el ´arbol este ordenado, se escribir´ a en desordenado un cero. Nota: se aclaro en el parcial que se debia retornar el primer sub-´ arbol que resulte desordenado realizando la busqueda in-order 2. (10p) Construir una funci´ on en ASM que dado un valor, obtenga el puntero al mismo valor en el arbol. De estar repetido, debe retornar el m´as cercano a la ra´ız del ´arbol. La aridad de la funci´ ´ on ser´ a void obtener(node* arbol, int valor, int** valorBuscado). 3. (5p) Modificar la funci´ on anterior para que retorne el puntero al nodo que contiene el valor. ¿fue necesario realizar alguna modificaci´ on? Nota: Tener en cuenta que para que un ´arbol binario este ordenado todos los valores del sub´arbol izquierdo tienen que ser menores al valor de la ra´ız y todos los elementos del sub´arbol derecho deben ser mayores o iguales. Soluci´ on de David Gonz´ alez M´ arquez. () 1. Una de las soluciones esperadas es la siguiente, primero se presenta una soluci´ on en C a fin de comprender mejor la soluci´ on ASM. #define MIN(X, Y) (((X) < (Y)) ? (X) : (Y)) #define MAX(X, Y) (((X) > (Y)) ? (X) : (Y)) node* ordenadoAux(struct node* actual, int* min, int* max) { int maxi, maxd, mini, mind;
1/9
2do cuatrimestre de 2016
Organizaci´on del Computador 2 - DC - UBA
if(actual==0) return 0; node* ni = ordenadoAux(actual->izq, &mini, &maxi); node* nd = ordenadoAux(actual->der, &mind, &maxd); *min = MIN(actual->valor,MIN(mind,mini)); *max = MAX(actual->valor,MAX(maxd,maxi)); if(ni) return ni; if(!(maxi < actual->valor && actual->valor < mind )) return actual; if(nd) return nd; return 0; } void ordenado(node* arbol, node** desordenado) { int max; int min; *desordenado = ordenadoAux(arbol, &min, &max); }
ordenadoAux: push push push push mov sub
r14 r13 r12 rbx rbx, rdi rsp, 24
test je
rdi, rdi .null
mov mov lea mov mov call mov
rdi, [rdi+16] r13, rsi rsi, [rsp+8] r12, rdx rdx, rsp ordenadoAux r14, rax
mov lea lea call mov
rdi, [rbx+8] rdx, [rsp+4] rsi, [rsp+12] ordenadoAux rdx, r14
mov mov mov cmp cmovle cmp cmovle
ecx, r8d, edi, ecx, r8d, r8d, edi,
mov cmp
esi, [rsp] [rsp+4], esi
[rsp+12] [rsp+8] [rbx] r8d ecx edi r8d
; actual null
; busco lado izquierdo
; busco lado derecho
; obtengo el menor
; obtengo el mayor
2/9
2do cuatrimestre de 2016
.null: .end:
Organizaci´on del Computador 2 - DC - UBA
mov cmovge mov mov cmp cmovge
r8d, esi r8d, [rsp+4] [r13+0], edi edi, [rbx] r8d, edi edi, r8d
test mov jne
r14, r14 [r12], edi .end
; comparo lado derecho
mov mov cmp jge
edi, [rbx] rdx, rbx esi, edi .end
; comparo valor actual
cmp cmovl jmp
edi, ecx rdx, rax .end
; comparo lado izquierdo
xor add mov
edx, edx rsp, 24 rax, rdx
pop pop pop pop ret
rbx r12 r13 r14
2. Posible soluci´ on no recursiva obtenerAux: .cont:
test rdi, rdi je .null
; actual null (esto no deberia pasar)
mov cmp jne mov ret
; ; ; ;
eax, [rdi] eax, esi .notfound rax, rdi
.notfound:
mov rdx, [rdi+16] cmp esi, eax cmovge rdx, [rdi+8] mov rdi, rdx jmp .cont
.null:
xor eax, eax ret
levanto valor actual comparo valor con valor actual si lo encontre sigo guardo resultado
; ; ; ;
levanto lado izquierdo comparo actual con valor si da mayor lo intercambio remplazo mi nuevo nodo
obtener: push rbx mov rbx, rdx call obtenerAux mov [rbx], rax pop rbx ret 3. No se debe modificar el c´ odigo, ya que la primera posici´ on de la estructura del nodo es justamente el valor.
3/9
2do cuatrimestre de 2016
Organizaci´on del Computador 2 - DC - UBA
Ej. 2.
(40 puntos)
Ej. 2.1.
Enunciado
Sea un vector de enteros sin signo de 12 bits ordenados de forma contigua como muestra la figura:
Notar que cada valor del vector ocupa un byte y la mitad del siguiente, o medio byte y el siguiente completo. 1. (20p) Construir una funci´ on en ASM usando SIMD que dado un arreglo determine si este esta ordenado de menor a mayor. 2. (20p) Construir una funci´ on en ASM usando SIMD que dado un arreglo y un n´ umero de 12 bits determine si el n´ umero pertence al arreglo. Nota: Considerar para la soluci´ on que el arreglo tiene exactamente 24 elementos. Soluci´ on de Gonzalo ciruelos. () Parte 1 Hay muchas formas de resolver este ejercicio, vamos a ver una. Esta soluci´ on divide al arreglo en 3 partes que se solapan. Cada parte entra en un registro xmm, con lo que vamos a chequear que cada parte est´e ordenada y, como se solapan, esto nos va a garantizar que el arreglo est´ a todo ordenado. Ahora bien, seg´ un la consigna, el arreglo tiene 24 elementos. Como c´ ada elemento ocupa 12 bits, entonces el arreglo ocupar´ a 24·12 = 36 bytes. 8 Representemos estos 36 bytes en memoria y veamos cuales son las 3 partes en las que vamos a partir al arreglo. 1
1
1
2
2
2|3
1
1 2|3
1 2|3
1
1 2|3
1 2|3
1
1|2
2|3
3
1|2 3
1|2 3
1|2 3
3
1|2 3
3
1|2
2
2
3
3
3
Donde cada n´ umero indica a que parte pertenece ese byte, o a que partes en caso de solapamiento. N´ otese que cada parte tiene 16 bytes. Entonces lo que tenemos que hacer es simplemente cargar estas partes a un registro. Luego, vamos a desempaquetar los n´ umeros de 12 bits y pasarlos a 16 bits. Vamos a pasar los de ´ındice par a un registro y los de ´ındice impar a otro. Esto lo vamos a hacer usando pshufb y pand para limpiar la eventual basura que pueda quedarnos. Luego vamos a comparar y listo. %define offset_parte1 0 %define offset_parte2 10 %define offset_parte3 20 ; rdi = puntero ordenado: push rbp mov rbp, rsp pcmpeq xmm12, xmm12 ; xmm12 = 1111...1 ; En los 16 bits mas bajos de este registro voy a ; acumular el resultado. 1s si esta ordenado, 0s si no.
4/9
2do cuatrimestre de 2016
Organizaci´on del Computador 2 - DC - UBA
movdqu xmm0, [rdi + offset_parte1] ; xmm0 = parte 1 que vimos arriba call aux ; despues de la llamada, los 16 bits mas bajos van a valer ; 1 si la lista esta ordenada y 0 si no. pand xmm12, xmm0
movdqu xmm0, [rdi + offset_parte2] ; xmm0 = parte 2 que vimos arriba call aux ; despues de la llamada, los 16 bits mas bajos van a valer ; 1 si la lista esta ordenada y 0 si no. pand xmm12, xmm0 movdqu xmm0, [rdi + offset_parte3] ; xmm0 = parte 3 que vimos arriba call aux ; despues de la llamada, los 16 bits mas bajos van a valer ; 1 si la lista esta ordenada y 0 si no. pand xmm12, xmm0 movd eax, xmm12 and eax, 0x0000ffff
; eax = 32 bits bajos de xmm2 ; limpio todo excepto los 16 bits bajos
pop rbp ret ; xmm0 = ; [ ? ? | 9 9 | 9 8 | 8 8 | 7 7 | 7 6 | 6 6 | 5 5 ; | 5 4 | 4 4 | 3 3 | 3 2 | 2 2 | 1 1 | 1 0 | 0 0] ; En cada nibble se indica a que numero corresponde ese nibble ; no voy a usar xmm12 mask_pares: db 00, 01, 03, 04, 06, 07, 09, 0a, 0c, 0d, ff, ff, ff, ff, ff, ff mask_impares: db 01, 02, 04, 05, 07, 08, 0a, 0b, 0d, 0e, ff, ff, ff, ff, ff, ff limpiar_pares: ddq 0000000000000fff0fff0fff0fff0fff aux: movdqu xmm1, xmm0 ; en xmm1 van a ir los pares, o sea [ 8 | 6 | 4 | 2 | 0 ] movdqu xmm2, xmm0 ; en xmm2 van a ir los impares, [ 9 | 7 | 5 | 3 | 1 ] pshufb xmm1, [mask_pares] ; xmm1 = [ ceros | 9 8 | 8 8 | 7 6 | 6 6 | 5 4 | 4 4 | 3 2 | 2 2 | 1 0 | 0 0 ] pand xmm1, [limpiar_pares] ; xmm1 = [ ceros | 8 | 6 | 4 | 2 | 0 ] todos en 16 bits pshufb xmm2, [maskim_pares] ; xmm2 = [ ceros | 9 9 | 9 8 | 7 7 | 7 6 | 5 5 | 5 4 | 3 3 | 3 2 | 1 1 | 1 0 ] psrlw xmm2, 4 ; xmm2 = [ ceros | 9 | 7 | 5 | 3 | 1 ] todos en 16 bits ; ahora tenemos que ver que 0 < 1 < 2 < 3 < ... < 9 ; primero vamos a ver que 0 < 1, 2 < 3, 4 < 5, 6 < 7, 8 < 9 movdqu xmm3, xmm2 ; xmm3 = [ ceros | 9 | 7 | 5 | 3 | 1 ] todos en 16 bits pcmpgtw xmm3, xmm1 ; xmm3 = [ 0 | 9 > 8 | 7 > 6 | 5 > 4 | 3 > 2 | 1 > 0 ] ; pcmpgtw compara enteros con signo pero no hay problema ; porque todos nuestros enteros de 16 bits tienen en 0 ; su nibble mas alto. ; segundo veamos que 1 < 2, 3 < 4, 5 < 6, 7 < 8 movdqu xmm4, xmm1 ; xmm4 = [ ceros | 8 | 6 | 4 | 2 | 0 ] todos en 16 bits psrldq xmm4, 2 ; xmm4 = [ ceros | 8 | 6 | 4 | 2 ] pcmpgtw xmm4, xmm2 ; xmm4 = [ ceros | 8 > 7 | 6 > 5 | 4 > 3 | 2 > 1 ] ; ahora falta hacer el and de todo y devolverlo por la parte baja de 16 bits ; de xmm0, hagamoslo a lo bruto pcmpeqb xmm0, xmm0 ; xmm0 = [ unos ] pand xmm0, xmm3 ; xmm0 = [ ? | 1 > 0 ] psrldq xmm3, 2
5/9
2do cuatrimestre de 2016
Organizaci´on del Computador 2 - DC - UBA
pand xmm0, xmm3 psrldq xmm3, 2 pand xmm0, xmm3 psrldq xmm3, 2 pand xmm0, xmm3 psrldq xmm3, 2 pand xmm0, xmm3
; xmm0 = [ ? | 1 > 0, 3 > 2 ]
pand xmm0, xmm4 psrldq xmm4, 2 pand xmm0, xmm4 psrldq xmm4, 2 pand xmm0, xmm4 psrldq xmm4, 2 pand xmm0, xmm4
; xmm0 = [ ? | 0 < 1 < 2 < 3, 5 > 4, 7 > 6, 9 > 8]
; xmm0 = [ ? | 1 > 0, 3 > 2, 5 > 4] ; xmm0 = [ ? | 1 > 0, 3 > 2, 5 > 4, 7 > 6 ] ; xmm0 = [ ? | 1 > 0, 3 > 2, 5 > 4, 7 > 6, 9 > 8 ]
; xmm0 = [ ? | 0 < 1 < 2 < 3 < 4 < 5, 7 > 6, 9 > 8] ; xmm0 = [ ? | 0 < 1 < 2 < 3 < 4 < 5 < 6 < 7, 9 > 8] ; xmm0 = [ ? | 0 < 1 < 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9]
ret
Parte 2 Este ejercicio es igual que el anterior, solo que un poco m´ as f´ acil. De nuevo, vamos a cubrir al arreglo con tres leidas de memoria que se van a solapar. En este caso, la funcion aux lo que va a hacer, luego de extraer los ´ındices pares y los impares, lo que va a hacer simplemente es chequear si alguno es igual a el valor pasado como par´ ametro. Voy a usar los define y las etiquetas del ejercicio anterior sin volver a definirlas. ; bool buscar(uint12_t* ptr, uint12_t x); ; rdi = ptr ; si = x, valor a buscar (nos llega en un registro de 16 bits, cuya parte alta esta potencialmente sucia) buscar: push rbp mov rbp, rsp and rsi, 0x0fff movd xmm1, rsi pshufw xmm1, xmm1, 0
; limpio la parte alta de rsi ; xmm1 = [ ? | x ] ; xmm1 = [ x | x | x | x | x | x | x | x ]
pxor xmm12, xmm12 ; xmm12 = 000..0 ; En los 16 bits mas bajos de este registro voy a ; acumular el resultado. 1s si x esta, 0s si no. movdqu xmm0, [rdi + offset_parte1] ; xmm0 = parte 1 que vimos arriba call aux ; despues de la llamada, los 16 bits mas bajos van a valer ; 1 si x esta en la lista y 0 si no. por xmm12, xmm0
movdqu xmm0, [rdi + offset_parte2] ; xmm0 = parte 2 que vimos arriba call aux ; despues de la llamada, los 16 bits mas bajos van a valer ; 1 si x esta en la lista y 0 si no. por xmm12, xmm0 movdqu xmm0, [rdi + offset_parte3] ; xmm0 = parte 3 que vimos arriba call aux ; despues de la llamada, los 16 bits mas bajos van a valer ; 1 si x sta en la lista y 0 si no. por xmm12, xmm0 movd eax, xmm12
; eax = 32 bits bajos de xmm2
6/9
2do cuatrimestre de 2016
Organizaci´on del Computador 2 - DC - UBA
and eax, 0x0000ffff
; limpio todo excepto los 16 bits bajos
pop rbp ret ; xmm0 = ; [ ? ? | 9 9 | 9 8 | 8 8 | 7 7 | 7 6 | 6 ; | 5 4 | 4 4 | 3 3 | 3 2 | 2 2 | 1 1 | 1 ; xmm1 = [ x | x | x | x | x | x | x | x ] aux: movdqu xmm6, xmm1 ; xmm6 = [ x | x | x | movdqu xmm1, xmm0 ; en xmm1 van a ir los movdqu xmm2, xmm0 ; en xmm2 van a ir los
6 | 5 5 0 | 0 0]
x | x | x | x | x] pares, o sea [ 8 | 6 | 4 | 2 | 0 ] impares, [ 9 | 7 | 5 | 3 | 1 ]
pshufb xmm1, [mask_pares] ; xmm1 = [ ceros | 9 8 | 8 8 | 7 6 | 6 6 | 5 4 | 4 4 | 3 2 | 2 2 | 1 0 | 0 0 ] pand xmm1, [limpiar_pares] ; xmm1 = [ ceros | 8 | 6 | 4 | 2 | 0 ] todos en 16 bits pshufb xmm2, [maskim_pares] ; xmm2 = [ ceros | 9 9 | 9 8 | 7 7 | 7 6 | 5 5 | 5 4 | 3 3 | 3 2 | 1 1 | 1 0 ] psrlw xmm2, 4 ; xmm2 = [ ceros | 9 | 7 | 5 | 3 | 1 ] todos en 16 bits ; ahora tenemos que ver si ; primero vamos a ver si x movdqu xmm0, xmm2 ; xmm3 pcmpeqw xmm0, xmm6 ; xmm6
x es alguno de los numeros estos. es alguno de {1, 3, 5, 7, 9} = [ ceros | 9 | 7 | 5 | 3 | 1 ] todos en 16 bits = [ ? | 9 = x | 7 = x | 5 = x | 3 = x | 1 = x]
; segundo vamos a ver si x es alguno de {1, 3, 5, 7, 9} movdqu xmm4, xmm1 ; xmm4 = [ ceros | 8 | 6 | 4 | 2 | 0 ] todos en 16 bits pcmpgeq xmm4, xmm6 ; xmm4 = [ ? | 8 = x | 6 = x | 4 = x | 2 = x | 0 = x ] por xmm0, xmm4 ; xmm0 = [ ? | x es 8 o 9 | x es 6 o 7 | x es 4 o 5 | x es 2 o 3 | x es 0 o 1 ] movdqu xmm4, xmm0 psrldq xmm4, 2 por xmm0, xmm4 psrldq xmm4, 2 por xmm0, xmm4 psrldq xmm4, 2 por xmm0, xmm4 psrldq xmm4, 2 por xmm0, xmm4
; xmm0 = [ ? | x es 0, 1, 2 o 3 ] ; xmm0 = [ ? | x es 0, 1, 2, 3, 4 o 5 ] ; xmm0 = [ ? | x es 0, 1, 2, 3, 4, 5, 6 o 7 ] ; xmm0 = [ ? | x es 0, 1, 2, 3, 4, 5, 6, 7, 8 o 9 ]
ret
Ej. 3.
(20 puntos)
Ej. 3.1.
Enunciado
Se desea modificar la convenci´ on C por una nueva denominada convenci´on Z. Esta implementa las siguientes modificaciones sobre la convenci´on C: 7/9
2do cuatrimestre de 2016
Organizaci´on del Computador 2 - DC - UBA
Una funci´ on se identifica por un nombre y un conjunto de par´ametros escritos con la sintaxis
(,...). No es parte de la aridad el tipo del valor de retorno. El valor de retorno para toda funci´ on es un uint64 que identifica la cantidad de bytes que se dejan en la pila a la funci´ on llamadora. Todos los par´ ametros de una funci´ on se pasan por la pila. Se pushean en orden inverso a como figuran en la aridad de la funci´ on. Por ejemplo si se llama a una funci´ on f que toma un solo par´ametro de 4bytes y retorna valores con un total de 24 bytes, la pila se ver´ a de la siguiente forma: Pila antes del llamado
Parámetros
Pila despues del retorno
Valores de retorno
RSP
RSP
1. (15p) Escribir el c´ odigo ASM de la funci´on sumar(int size, int a,...) respetando la convenci´ on Z. Esta funci´ on toma una cantidad variable de par´ametros enteros donde el primero indica la cantidad de par´ ametros que recibe la funci´on. La funci´on retorna una cantidad variable de enteros (int), siguiendo la siguiente f´ ormula: Pi ri = 0 ai 2. (5p) Escribir el c´ odigo ASM para llamar a la funci´on anterior con los par´ametros 4, 12, 44, 76. Nota: Considerar que fuera de las modificaciones nombradas, las funciones deben respetar la convenci´ on C. Soluci´ on de Lautaro Petaccio. () 1. Implementaci´ on de sumar en convenci´ on Z sumar: ; Consigo la direcci´ on de retorno pop r8 ; Consigo size y limpio la parte alta pop r9 and r9, 0x00000000FFFFFFFF; ; Dejo el tama~ no de los datos que voy a dejar en la pila ; son enteros, pero la pila la debo operar de a 8 bytes, es el size * 8 mov rax, r9 shl rax, 3 ; Dejo la direcci´ on de retorno en el tope de la pila ; para poder volver al hacer ret push r8 ; r11 va a ser mi acumulador de sumas parciales mov r11d, 0 ; RDI va a ser mi contador de iteraciones mov rdi, 0 .ciclo: cmp r9, rdi je .fin ; Acumulo los enteros y los escribo otra vez
8/9
2do cuatrimestre de 2016
Organizaci´on del Computador 2 - DC - UBA
; El + 8 en la cuenta es para saltear la direcci´ on de retorno add r11d, [rsp + rdi * 8 + 8] mov [rsp + rdi * 8 + 8], r11d inc rdi .fin: ret 2. Llamar a sumar en convenci´ on Z push push push push push call
76 44 12 4 4 sumar
9/9