Ayer tuve mi último examen de Análisis de Algoritmos, el correspondiente a la tarea 3 de Análisis de Algoritmos (en negritas, porque tengo que escribir acerca de ella, del examen y de la materia en general).

Al terminar le hablé a Alejandro, que estaba recluido en su casa (creo que sin bañarse) desde el viernes, y él me dijo que prefería estar en su casa chambeando. Dado que él fue el head developer por defecto del proyecto, presumí que nuestro deber era ir a apoyar; así que agarré a Alexander y fuimos a casa de Alejandro, llamándole a Iván y diciéndole que su misión si decidía aceptarla era ir también.

Lo que siguió fueron las veinte horas más pesadas que he tenido en el IIMAS, y ciertamente están en el top five de mi vida.

Estuvimos en casa de Alejandro con la firme idea de no salir hasta que saliera el proyecto o hasta que tuviéramos que ir al IIMAS a entregarlo, lo que ocurriese primero.

Varios obstáculos se interpusieron en el camino: primero, la chingadera no cabía. La Xilinx Spartan-3E que teníamos era el modelo más chafa (bueno, el segundo más chafa) de esa compañía, y nuestro proyecto era muy complejo: entonces las compuertas no alcanzaban. Los inges (principalmente Alejandro) estuvieron haciendo maromas con el código VHDL para optimizar todo lo optimizable, y viendo qué podían quitar.

Después, la FPU ya estaba, jalaba en el ModelSim, pero no servía cuando la quemábamos en la tarjeta. Tenía que ver con la frecuencia a la que jalaba la tarjeta, que era como el doble de lo que aguantaba el FPU… o algo así.

Y por último, cada quemada de todo el CPU nos tomaba cerca de 20 minutos… lo cual nos mataba el ritmo, porque no podíamos hacer nada mientras estaba compilando y quemando el CPU a la tarjeta.

Cerca de las 3 de la mañana, un gran pesimismo comenzó a apoderarse de nosotros: la cosa no quería quedar, y comenzamos a pensar en un plan B. En el peor de los casos, teníamos smiley para presentar.

Y entonces, a las 7:30 de la mañana, cada quién haciendo lo que podía con su parte (yo estaba terminando la documentación), todos madreados y ya sin muchas esperanzas, Alejandro de repente nos dijo “¡miren!”.

Y miramos.

Haciendo uso de todos los trucos del universo, y optimizando todo lo optimizable, el CPU cupo y funcionó en la tarjeta. Literalmente ocupamos todo el espacio de la tarjeta: incluso usamos una opción que tiene el XST de Xilins para utilizar los Block RAMs no utilizados en el proyecto como compuertas lógicas extras.

Ya de ahí todo fue de bajada; terminamos todo lo que había que terminar, y nos tomamos la foto del triunfo:

Lo chido de esa foto, es que de verdad estábamos eufóricos: el pinche procesador nos había costado un huevo y la mitad del otro, y ya casi habíamos perdido la esperanza cuando por fin funcionó.

Terminamos todo el procesador. Sólo excluimos las instrucciones lógicas (and, or, xor, shl y shr), porque no cabían. Era trivial implementarlas (las operaciones están soportadas a nivel de VHDL, y Xilinx para variar sí implementó esa parte del estándar VHDL); pero no teníamos ya compuertas. Nos quedaban como dos ORs. Y un AND.

Después fue preparar la presentación (que ya fue sencillo teniendo todo), nos fuimos al IIMAS, y fuimos el primer equipo en presentar su proyecto. Fue una presentación muy padre: fuimos el único equipo que hizo ensamblador y simulador, y pudimos enseñarle a Savage dos fractales y nuestro smiley. Además, de verdad estábamos emocionados con nuestro micro, porque nos había costado un chingo. Savage incluso nos felicitó; yo ni podía creerlo.

Ya después, cada quién fue a dormir a su casa.

No sé qué calificación vaya a tener al final en esta materia; en los exámenes me fue mal. Pero creo que no importa; a este proyecto le echamos todas las ganas del universo, y la verdad nos quedó muy padre.

Aunque yo le pondría 10 a mi equipo.

El trabajo en nuestro procesador para Arquitectura sigue y sigue. Los inges trabajan día y noche para poder sintetizar (así se le dice) el código VHDL en lo que sea que se quema en la tarjeta Xilinx.

Nuestro micro (cuando esté) podrá hacer cosas bastante interesantes. Pero aunque sigue incompleto, los inges han ido implementando cada vez más instrucciones, hasta que por fin fue capaz de hacer esto:

En la imagen (que no tomé yo) también se alcanza a ver la tarjeta que estamos usando.

No parece mucho, pero el programa en ensamblador que genera eso ya no es trivial. Para poder dibujar toda la carita necesitamos saltos (para los fors), saltos condicionales (para ifs), y dado que sólo tenemos cuatro registros enteros, necesitamos apuntadores (poder escribir y leer datos teniendo sólo la dirección de memoria). No ha sido nada fácil.

Si les interesa, el código del smiley está aquí. Viendo la cantidad de números mágicos que estaban apareciendo en nuestros programas, también añadimos constantes. Son iguales que las variables, sólo que de hecho no generan código máquina (se convierten en literales antes de generarlo), y por supuesto no pueden aparecer del lado derecho de un mov.

Teniendo ya Mandelbrot, era trivial hacer Julia. Pero para hacerlo más interesante, el programa en ensamblador cambia la constante de Julia por una , y vuelve a dibujar el fractal. Esto resulta en una “animación” (entre comillas porque mi simulador tarda unos siete segundos en dibujar todo el “monitor”), que me dieron ganas de mostrar en el blog.

Para esto, utilicé la opción que tienen los GdkPixbufs de salvarse a archivos gráficos, y modifiqué el simulador para que lo haga si el usuario lo invoca con un parámetro en la línea de comando. En el camino, arreglé todas las broncas de sincronización que tenía el simulador (el ciclo del simulador es un hilo de ejecución (thread) independiente de gtk_main()), y de una vez limpié todo mi uso de Gdk. Quedó mucho más bonito.

Para generar automáticamente las 325 imágenes de la animación, hice un hack para que el simulador guarde una copia de la imagen cada vez que se ejecuta la instrucción shl (shift left), porque esa instrucción no se usa en el programa de Mandelbrot o Julia. El hack es necesario porque el simulador sólo guarda la imagen cuando entra en un ciclo infinito que no hace nada, que es como “oficialmente” acaban los programas correctos en nuestro micro. El programa de Julia no tiene ciclo infinito que no haga nada; tiene un ciclo infinito que dibuja Julia en cada iteración, y no iba a generar las 325 imágenes a pie.

La animación quedó bonita:

Los inges siguen avanzando con el micro. Or so they say.

Con Alejandro en nuestro proyecto de Arquitectura:

Yo: ¿Entonces VHDL no permite if‘s anidados ni elsif‘s?
Alejandro: No, la bronca es que cuando hacemos

if (pin = ‘0’) then
    do shit
else
    esto no quiere decir que pin es ‘1’, sólo no es ‘0’
end if;

Yo:Y es por eso que no estudié en Ingeniería.

De donde yo vengo, los bits valen cero o uno. Y ya.

Sólo he escrito entradas de Arquitectura de Computadoras últimamente, porque ha sido mi coco este semestre (no es que sea difícil; no lo es… es sólo que esta materia tiene todos los elementos por los cuales acabé en la Facultad de Ciencias y no en la de Ingeniería). Pero eso no quiere decir que no tenga un fin de semestre completito.

Mañana son las reposiciones de Lenguajes de Programación. La materia ha sido muy frustante, básicamente por el ayudante. Tengo un historial añejo de pelearme con ayudantes. El resultado es que no sé qué he sacado en mis exámenes; sé que no he reprobado ninguno, y que (creo) en ninguno tengo menos de ocho. Pero no sé exactamente qué calificaciones tengo, además de que el antes mencionado ayudante no ha entregado las calificaciones de los últimos dos exámenes que hicimos. Entonces no sé si tengo 10 de calificación… y quiero 10, así que ante la duda (si no nos entregan calificaciones antes), tendré que hacer reposiciones.

El lunes tengo examen de Análisis de Algoritmos. Ha sido sin duda mi mejor materia, incluido un 6 idiota que tuve en un examen, especialmente por la tarea 3, de la cual hablaré (espero) al fin del semestre. El punto es que no me preocupa demasiado el examen; creo que estoy en condiciones suficientemente buenas para pasarlo bien.

El martes es el día que entregamos nuestro micro en Arquitectura de Computadoras. Creo que sí acabamos a tiempo, y creo que va a quedar muy padre ese proyecto. Cómo carajo se va a ver reflejado eso en mi calificación, no tengo idea.

Y por último el miércoles tengo mi último examen de Autómatas y Lenguajes Formales. Exceptuando un 7.2 y un 8.5 en dos de las ocho tareas, tengo 10 o más de 9.5 en todo lo demás (incluido el primer y hasta ahora único examen). Pero este segundo examen es el 40% de la calificación, así que más vale que lo saque bien.

Independientemente de que es fin de semestre completito, el cansancio ya comienza a ser evidente. Es la primera vez que en diciembre no descansé nada (estuve yendo al IIMAS diario o trabajando desde mi casa en cosas de Arquitectura y Algoritmos), y además ya comienzo a hartarme. Pero falta menos de una semana para que este semestre acabe.

Y mañana sale el nuevo capítulo de Battlestar Galactica.

Hoy acabé la parte de software para nuestro proyecto de Arquitectura de Computadoras. Por supuesto no va a servir de mucho si los inges no acaban el micro, pero me he divertido al menos.

Nuestro micro es bastante sencillo; tiene instrucciones para manejo de memoria, una pilita (en la misma memoria), saltos, un ALU de enteros, y (el chiste), una unidad aritmética de complejos.

La idea era hacer algo nuevo.

La aplicación obvia para nuestro micro es un fractal; sobre todo porque tenemos salida VGA de nuestra tarjeta Spartan-3E, y entonces (mientras los inges se hacen bolas con el código VHDL), yo hice un ensamblador, un desensamblador, un convertidor de código máquina a VHDL, y un emulador. La idea es tener todo el software depurado para que al momento de correr la aplicación en la tarjeta, si algo sale mal, sepamos que de hecho es el código VHDL y no algún error bobo en el software.

El ensamblador lo hice con Yacc y Lex (y sé que no era necesario; sólo era muy sencillo hacerlo así), el desensamblador en Perl (aunque lo pasé a C porque cómo joden los inges con la eficiencia), el convertidor en C, y el emulador también en C, utilizando Gtk+ para emular el monitor. Ya entrados y en el vicio, hice también el programa en ensamblador que dibujara Mandelbrot en la pantalla.

Para que se den una idea, este es un programa en nuestro ensamblador que dibuja una línea vertical justo al centro del monitor (en VGA tenemos 640×480 de resolución):

1:	start:
2:		mov	0, %ebx
3:		mov	7, %ecx
4:		mov	320, %eax
5:	for:
6:		vput
7:		mov	1, %edx
8:		add	%ebx, %edx
9:		mov	480, %edx
10:		sub	%edx, %ebx
11:		jz	end
12:		jmp	for
13:	end:
14:		jmp	end

Les queda de tarea descifrarlo. Sólo quiero especificar que el ciclo infinito al final es idea de los inges: parece que la idea de que las cosas terminen les molesta.

Tenemos sólo cuatro registros enteros (%eax, %ebx, %ecx y %edx), y cuatro complejos (iguales, pero “c” en lugar de “e”). Cada complejo tiene una parte real y una imaginaria. No pongo el algoritmo de Mandelbrot porque está bastante más largo (108 líneas de ensamblador; pequeño para todo lo que hace), pero sí les pongo que para graficarlo uno calcula

donde , y recorre un área que será la que cubra la pantalla.

(Realmente no había razón para ponerles la fórmula; pero ya tengo rato buscando un pretexto para utilizar mi renderer).

Mi emulador ya pudo dibujar Mandelbrot, y sin más preámbulo se los presento:

Si les parece que los colores son demasiado “All the leaves are brown…”, tienen toda la razón. Sólo tenemos 3 bits para representar colores, así que sólo tenemos ocho: negro, azul, verde, rojo, magenta, cyan, amarillo y blanco. Así que la caballada estaba flaca para empezar.

El proyecto está bonito; si lo acabamos lo va a estar más.