orga2-simd/informe/subBlur.tex

\subsection{Blur Gaussiano}
\par El filtro Blur consiste en asignarle a cada pixel (excepto a los p\'ixeles del borde, que no se modifican) el promedio del valor (A, R, G y B) de sus vecinos (sus 8 vecinos inmediatos 
y el mismo pixel). Esto resulta en una imagen m\'as "borrosa" (a lo que se debe el nombre del filtro).
\subsubsection{Implementaci\'on 1}
\label{sec:blur_imp1}
\textbf{NOTA: Actualmente hay un error de lectura inv\'alida en la implementaci\'on, causada por leer 1 p\'ixel de m\'as al momento de procesar el \'ultimo p\'ixel, la implementaci\'on funciona, pero \emph{valgrind} tira error. }

Al comenzar la funci\'on se guardan en el stack los registros \emph{R13,R14 y R15}, para guardar el ancho, alto y puntero de la imagen, para no perderlos al momento de llamar a \emph{malloc}. Se copian en dichos registros los valores recibidos por parametros y se procede a calcular el tama\~no total de la imagen en \emph{Bytes}, se carga el valor en \emph{RDI} y se llama a la funci\'on \textbf{\emph{malloc}}. 
Ya que el valor de cada pixel depende de el valor de sus vecinos, no es posible sobreescribir cada pixel en la imagen tras procesarlo, ya que de esta forma se alterar\'ia el resultado
de todos sus vecinos que a\'un no fueron procesados. Para poder operar sobre cada pixel manteniendo una copia de su valor original, se utiliza una imagen "buffer" donde se escriben los resultados 
de cada iteraci\'on, manteniendo intacta la imagen original. Al finalizar todo el procedimiento, se sobreescribe la imagen original con la nueva, y se libera la memoria utilizada por la imagen 
"buffer" (llamando a la funci\'on \textbf{\emph{free}}).
Se recuperan los valores guardados y se genera un registro con el tama\~no correspondiente al ancho de la imagen. Al puntero a memoria de la imagen original se le suma dicho registro, para no realizar el procesamiento de la primera fila, luego se le suma 4 (1 p\'ixel) para evitar el procesamiento del primer p\'ixel. \\
De los indcadores del alto y ancho se restan 2 p\'ixeles en cada uno, correspondientes a los bordes de la imagen. \\
Antes de iniciar el ciclo, se carga un valor \textbf{constante} en un registro \emph{XMM}, el cual contiene 4  n\'umeros de punto \emph{flotante simples} con el valor 9 cada uno. Lo cual sirve para realizar la divisi\'on empaquetada de la suma de p\'ixeles en el procesamiento.

Ya dentro del ciclo principal del programa se realiza una copia del puntero a la imagen. De dicha copia se resta el ancho de la imagen para retroceder una fila, y liego se resta 1 p\'ixel (4 bytes) para leer el p\'ixel anterior al actual. \\
Se reinician los registros auxiliares para el procesamiento, se carga con el valor 3 un registro auxiliar para la carga de memoria. Luego se leen de memoria 16 \emph{Bytes}, lo que corresponde a 4 p\'ixeles. Se realiza un \emph{shift} de \emph{Double Word} a izquierda de 4 \emph{Bytes}, esto sirve para destruir el 4\textsuperscript{to} p\'ixel, que no es necesario para el c\'alculo del blur. \\
Se desempaqueta dicho registro de \emph{Byte} a \emph{Word} y se suman ambos registros desempaquetados en un nuevo registro, de la forma: 
$$ XMM0 = |0x0|P1|, XMM1 = |P2|P3|, XMM2 = 0x0 $$
$$ XMM2 = |P2+ 0x0| P1 + P3| $$ \\
Se suma en la copia del registro puntero el ancho de la imagen, para indicar que se quiere procesar la fila del medio, o \emph{la actual}. Se decrementa el valor del registro auxiliar y se compara con 0, si es distinto se vuelve a saltar a la secci\'on de lectura de imagen y vuelve a repetirse para la fila siguiente. Eso mismo deja en el registro \emph{XMM2} la suma de todos los p\'ixeles. En el c\'odigo \ref{blur1_1} se puede la lectura de las 3 filas de p\'ixeles.
%\asmscript{blur1_1}{Blur1 - Lectura de fila de p\'ixeles a procesar}

Al finalizar la lectura de los p\'ixeles se realiza una copia del registro con la suma. Se realiza un \emph{shift} de \emph{Double Word} a la derecha, con 8 \emph{Bytes}, lo que deja al registro con la parte alta con ceros. Se suma el registro con el original para finalizar la suma empaquetada de todos los p\'ixeles. \\
Como el registro cargado para la divisi\'on se encuentra en punto \emph{flotante simple}, y la instrucci\'on de divisi\'on debe operarse con ese mismo tipo de dato, se desempaqueta la parte baja del registro con la suma de \emph{Word} a \emph{Double Word} y luego se convierte a punto flotante con la instrucci\'on \textbf{cvtdq2ps}. \\
Se divide el registro con la suma como \emph{packed single precision} por el registro con los valores de \emph{9}.

Finalizada la división se convierte nuevamente el registro a entero \emph{Double Word} con truncado y se empaqueta a \emph{Word} con saturaci\'on sin signo.

Se escribe al registro de la imagen temporal el valor obtenido como \emph{Double Word} y se aumentan los iteradores de p\'ixel en 1 (4 \emph{Bytes}). Se compara el contador auxiliar de columna con el tama\~no. Si es igual se termina de recorrer la fila, sino se decrementa el contador auxiliar y luego se salta al inicio de del procesamiento de la fila y vuelven a leerse los siguientes p\'ixeles. Si no son iguales se considera que se termin\'o de procesar la fila y se salta a la secci\'on de final de fila.

En la secci\'on de final de fila se decrementa el contador de filas y se compara con 0. Si es igual, se termin\'o de procesar la imagen y se salta a la secci\'on de final. En caso contrario, se est\'a en el final de una fila y se avanzan los bordes de la imagen, leyendo el valor del registro y escribiendo el nuevo valor en la imagen temporal, luego se aumentan los registros contadores de fila y se salta al inicio de una nueva fila. En el c\'odigo~\ref{blur1_2} puede ver el manejo que se hace al llegar al final de una fila.
%\asmscript{blur1_2}{Blur1 - L\'ogica de fin de fila}

En la secci\'on final se recupera en \emph{RCX} el alto y ancho de la imagen en \emph{Bytes}, se quita del total el ancho de la imagen 2 veces, para indicar que se procesan 2 filas menos y 2 p\'ixeles, correspondientes a la columna.  \\
Se setea luego el flag de direcci\'on y se cargan las posiciones de memoria de la imagen destino y la temporal en \emph{RDI} y \emph{RSI}.\\
Se usa la instrucci\'on \textbf{rep movsb} para copiar la memoria.

Finalizada la copia se carga el puntero a la imagen temporal en \emph{RSI} y se llama a \textbf{free}. Se devuelven a su valor original los registros del stck, desarma el stack frame y se sale de la funci\'on.


\subsubsection{Implementaci\'on 2}
\label{sec:blur_imp2}
Al iniciar el filtro, se \emph{pushean} los registros \emph{RBX, R12, R13 y R14}, y se copian en ellos el puntero a la imagen original, el ancho y el alto. \\
Se carga un n\'umero entero constante pre-cargado de tama\~no \emph{Double Word} en toda la parte baja y alta del registro, lo que permite realizar las divisiones del blur con n\'umeros enteros, el valor se configura previamente al momento de compilar y sale de la formula: 
$$ Valor = \frac{2^{16}}{9}+1 $$ \\
Por cuestiones de precisi\'on, el n\'umero debe ser mayor a $2^8$, lo que implica que los enteros van a tener que ser como m\'inimo de tamaño \emph{Double Word} y no van a poder procesarse m\'as de dos p\'ixeles por instrucci\'on.

Luego se calcula el ancho de la imagen \emph{en Bytes} y se multiplica por el ancho para obtener el tama\~no total, luego se copia el dato al registro \emph{R12}. Se carga en \emph{RDI}, el tama\~no de la imagen calculado anteriormente y se llama a la funci\'on \emph{malloc}, por la misma raz\'on que en el filtro 1. \\
Al retornar la funci\'on copio los valores guardados en los registros, para realizar operaciones con ellos m\'as adelante. Se calcula el ancho en Bytes nuevamente y esta vez se almacena para recorrer la imagen. Al registro que contiene el tama\~no total de la imagen se le resta el ancho, para marcar que la \'ultima fila no debe procesarse. Al registro que se utiliza de contador de columnas se le asigna el tamaño de un p\'ixel y al registro que cuenta las filas se le suma el ancho, para indicar que se saltea la primera fila.

Finalizados los calculos se procede a leer los primeros 4 p\'ixeles de la imagen (sin contar la primera fila y la primera columna). Al registro que apunta al p\'ixel actual se le resta el ancho de la imagen, esto permite poder leer la fila anterior. Se lee empaquetado 16 Bytes de memoria de la posición del registro puntero \textbf{menos} 1 p\'ixel (4 bytes) y se almacena en un registro \emph{XMM}. Luego se lee de la posici\'on actual \textbf{mas} 4, lo que permite leer el p\'ixel siguente al \'ultimo que quiero procesar. Quedar\'ian los registros de la siguiente manera:
$$ XMM0 = |p0|p1|p2|p3| $$
$$ XMM1 = |p2|p3|p4|p5| $$ \\
Donde \emph{p\textbf{X}}, con \emph{X} natural referencia a cada pixel la fila de p\'ixeles central (la actual) que se encuentra almacenado en dicho registro. \emph{\textbf{U}p\textbf{X}} (U de \emph{Upper}) referencia a cada pixel de la fila superior (siguiente y misma columna) y \emph{\textbf{L}p\textbf{X}} (L de \emph{Lower}) referencia a la fila inferior. Esto permite simplificar los comentarios en el c\'odigo. Por ejemplo \textbf{Up0} referencia al pixel de la fila superior que se encuentra en la primera posici\'on del registro, lo que ser\'ia el pixel superior izquiero al pixel que se quiere procesar. 

Puede observarse que se leen 2 p\'ixeles repetidos, pero los mismos luego ser\'an descartados. \\
Luego al registro puntero se le suma el ancho de la imagen para poder cargar los p\'ixeles correspondientes a la fila \textbf{actual} y se realizan las mismas operaciones de lectura en dos registros.\\
Nuevamente se suma el ancho de la imagen al registro contador, esta vez para leer los p\'ixeles correspondientes a la fila de arriba de los actuales a procesar.
En el c\'odigo~\ref{blur2_1} puede observarse el c\'odigo encargado de la lectura de las 3 filas.
%\asmscript{blur2_1}{Blur2 - Lectura de fila de p\'ixeles a procesar}

Se desempaquetan los 6 registros de \emph{Byte} a \emph{Word} y se almacenan, en caso de los p\'ixeles repetidos, se descartan al desempaquetar. De este modo quedan 3 parejas de 3 registros, cada uno con 2 p\'ixeles donde cada pareja representa a una fila.
%\asmscript{blur2_2}{Blur2 - Secci\'on de desempaquetado de p\'ixeles}

Seguidamente se suman los registros "verticalmente", esto quiere decir que de las 3 parejas de p\'ixeles se suman empaquetados los correspondientes a los primeros dos p\'ixeles de la fila anterior, de la fila actual y de la fila siguiente. \\
Por ejemplo: \\
$$ xmm0 = |Up0|Up1|, xmm3 = |p0|p1|, xmm6 = |Dp0|Dp1| $$
$$ xmm3 = xmm0 + xmm3 + xmm6 $$
$$ xmm3 = |Up0 + p0 + Dp0|Up1 + p1 + Dp1| $$ \\
Y de similar manera los otros pares.

Finalizadas las sumas, quedan solamente 3 registros con 2 sumas verticales de p\'ixeles. Para poder continuar debe sumarse horizontalmente en grupos de a 3 los p\'ixeles que se encuentran a los lados de \emph{p1, p2, p3 y p4}. \\
Para lograr ello se suman de manera intercalada los registros, Por ejemplo: \\
$$ xmm3 = |SUM(p0)|SUM(p1)|, xmm4 = |SUM(p2)+SUM(p3)| $$
$$ xmm3 + xmm4 = |SUM(p0)+SUM(p2)|SUM(p1)+SUM(p3)| $$ \\
En este caso a la parte alta $(p0 + p2)$ requiere la suma de \emph{p1}, en la parte baja \emph{p2}. Y as\'i los otros dos registros. \\
En los ejemplos \emph{SUM(pX)} referencia a la suma de los p\'ixeles inmediatos superior e inferior de la columna a procesar y el mismo pixel central. Por ejemplo \emph{SUM(p3)} indica que se contiene la suma de los p\'ixeles \emph{Up3, p3 y Lp3}.

Para poder realizar la suma en ambos conjuntos de p\'ixeles se copia el registro que contiene a la suma de los p\'ixeles 0 y 1. A la copia se le realiza un \emph{shift} \emph{Double Word} a izquiera de 8 bytes, lo que deja en la parte alta al p\'ixel 1, luego vuelve a copiar el registro original y se hace otro \emph{shift} a la derecha. Ambos registros se suman, lo que deja un nuevo registro:
$$ xmm9 = |SUM(p1)|SUM(p2)| $$
Luego vuelve a repetirse los pasos para el registro que tiene los p\'ixeles 3 y 4, dejando un nuevo registro:
$$ xmm10 = |SUM(p3)|SUM(p4)| $$ \\
Una vez creados los registros se procede a sumarlos el grupos. En el c\'odigo~\ref{blur2_3} puede observarse el código que realiza la suma y shifteos, junto con los comentarios que explican el estado de los registros.
%\asmscript{blur2_3}{Blur2 - Suma por fila}

Deben volver a desempaquetarse los registros de \emph{Word} a \emph{Double Word} para poder realizar las multiplicaciones por el n\'umero previamente cargado, se desempaquetan los registros \emph{XMM3} y \emph{XMM5} a registros temporales. \\
Se realiza, luego, una multiplicaci\'on empaquetada de los 4 registros desempaquetados por dicho n\'umero. Luego se realiza un \emph{shifteo} de \emph{Double Word} a derecha por 16 bytes, que ser\'ia como realizar una divisi\'on.

Terminado el \emph{shifteo} deben volverse a empaquetar los datos hasta \emph{Byte}, una vez hecho esto, se escriben los datos en la posici\'on correspondiente, seg\'un la copia de los registros contadores, pero \textbf{en el puntero de la imagen temporal}.

Luego se procede a hacer avanzar para procesar los siguientes 4 p\'ixeles, se suma 16 al registro contador de columna y se compara al ancho de la imagen sin la última columna. Si el valor del contador supera al ancho, salta a la secci\'on~ de finalizaci\'on de columna. \\
Sino, al contador de columna se le resta el ancho de la imagen, si el resultado es mayor que 16 (4 p\'ixeles) se salta nuevamente a la secci\'on de lectura de memoria y se vuelve a ejecutar. De lo contrario se resta al contador de columna el resultado de la resta y se salta a la secci\'on de lectura de memoria. \\
Esto implica que en caso de que el siguiente procesamiento se pase del ancho de la imagen, se resta el \emph{offset} al contador y se vuelven a procesar  algunos de los p\'ixeles anteriores, pero esta vez el procesamiento va a terminar j\'usto en el borde de la imagen.

En la secci\'on de finalizaci\'on de columna se reinicia el contador de columna (y se le suma 4) y se aumenta el ancho de la imagen al contador de fila, para indicar que se est\'a en la fila siguiente. Si el contador de fila supera a $ TamañoImagen - AnchoImagen $, se finaliza el procesamiento de la imagen y se incia la copia de la imagen temporal al resultado, sino se salta nuevamente a la secci\'on de lectura de memoria.

En el proceso de copia de la imagen temporal al resultado final se evita copiar los bordes de la im\'agen, ya que los mismos no se procesan y esto ahorra tener que copiarlos a la imagen temporal para luego volver a copiarlos a la imagen final sin ser procesados. Por lo que solo se reemplazan los p\'ixeles internos que se procesaron.\\
Para esto se utilizan los registros copiados al inicio con el tama\~no de la imagen, otros dos registros punteros, uno con la imagen destino, y otro con la imagen temporal y un \'ultimo registro contador. Antes de comenzar la copia, a los registros punteros se le suma el ancho de la imagen, as\'i se evita copiar la primera fila. \\
Para facilitar la lectura se utiliza la instrucci\'on \textbf{movsd}, se carga en el registro \emph{RCX} el ancho de la imagen menos 8 (2 p\'ixeles), en el registro \emph{RDI}, donde se encuentra el puntero de la imagen temporal, se suma el tama\~no de un p\'ixel, lo mismo en el registro \emph{RSI} de destino. Se setea el flag de direcci\'on y se ejecuta \textbf{rep movsd}. \\
Luego se aumenta el contador de proceso de fila y se aumenta 1 p\'ixel en los punteros a las im\'agenes, lo que implica que no se copia el \'ultimo p\'ixel de la fila. Cuando el contador de la imagen llega al alto, se llama a la funci\'on \textbf{free} con la direcci\'on de la imagen temporal. Se desarma el stack frame y se sale de la funci\'on. En el c\'odigo~\ref{blur2_4} se puede ver un extracto de como se realiza la copia.
%\asmscript{blur2_4}{Blur2 - Copia de imagen temporal a resultado final}

\subsubsection{Hip\'otesis de funcionamiento para los experimentos}
Comparando la implementaci\'on 1 con C puede esperarse, un aumento en la velocidad de ejecución, ya que se realizan menos lecturas y escrituras a memoria. Adem\'as se realizan las operaciones de forma empaquetada y no de forma secuencial.\\
Al comparar la implementaci\'on 2 con la 1 se asume una reducci\'on en tiempo de ejecuci\'on de al menos \textbf{3} veces en casos de lectura. Debido que se realizan menos lecturas de memoria para procesar los mismos 4 p\'ixeles y se opera de a 2 p\'ixeles a la vez de forma empaquetada. Tambi\'en puede haber mejora en cuanto a instrucciones de prefetch, por que se realizan menos saltos condicionales a bloques diferentes.\\

\pagebreak