orga2-simd/informe/subBlur.tex

\subsection{Blur Gaussiano}
El filtro Blur Gaussiano consiste en, dado un radio \textbf{r} y un par\'ametro $\sigma$, \emph{generar} una matriz de convoluci\'on, la cual no depende de los valores de la imagen, por lo que puede ser calculada una sola vez. Luego con esa matriz se toma una \emph{sub-matriz} de radio \textbf{r} con centro en el p\'ixel que se quiere procesar y realizar una sumatoria de la multiplicaci\'on componente a componente de cada matriz. Esto resulta en una imagen m\'as "borrosa" (a lo que se debe el nombre del filtro).

\subsubsection{Implementaci\'on C}
\label{sec:blur_impc}
Para simplificar el c\'odigo en \textbf{C} y \textbf{ASM} se cre\'o  una funci\'on encargada de calcular la matriz de convoluci\'on. La matriz se almacena en el heap y se devuelve un puntero a la misma para realizar los c\'alculos. Queda a cargo del c\'odigo que utilice a dicha matriz llamar al \emph{free} para liberar la memoria.
Para generar la matriz primeramente se calcula el largo de la misma, el cual es $(2*r + 1)^2$, al momento de llamar a la funci\'on \textbf{malloc} se multiplica dicho valor por el tama\~no de un float. \\
Luego se realizan dos ciclos \textbf{\emph{for}} anidados, uno para recorrer las columnas y otro para recorrer las filas. Los valores van desde $-r$ a $r$. Para cada elemento realizo la ecuaci\'on gaussiana en dos dimensiones y lo almaceno en la matriz. \\
Al finalizar queda la matriz de convoluci\'on con \emph{float}, donde cada elemento de la matriz corresponder\'ia a un p\'ixel. \\
En el c\'odigo \ref{blurc_1} se puede ver el ejemplo del código que se ejecuta.
\cscript{blurc_1}{blur_c}{Blur C - Ciclo princip\'al de calculo de matriz de convoluci\'on}{24}{36}

Antes de iniciar el procesamiento se realiza un casteo de los punteros a im\'agenes recibidos para poder operar con los mismos como matrices. Tambi\'en se declaran las variables que se van a usar para recorrer la imagen y la sub-matriz. Se llama a la funci\'on para obtener la matriz de convoluci\'on y se almacena el puntero a la misma.\\
Se procede a recorrer la imagen con dos ciclos \textbf{\emph{for}} anidados, los mismos van desde \emph{Radio} hasta $Filas-Radio"$ y $Columnas-Radio$, esto produce que no se recorran ni procecen los bordes de la im\'agen.
Dentro del ciclo interno se reinicia (asigna $0$) al acumulador interno, se reinicia tambi\'en el contador de posici\'on de la matriz de convoluci\'on.

\emph{NOTA: Descubrimos que el puntero de destino tiene el mismo contenido que la imagen de origen, esa es la raz\'on por la que no leemos ni escribimos en los bordes. Si llegara a cambiar esto, deber\'ia añadirse un bloque peque\~no de c\'odigo que copie los bordesde de tama\~no $Radio$ de la im\'agen de origen sin procesarlos.}

Para cada ciclo interno, luego de reiniciars las variables se realizan otros dos ciclos \textbf{\emph{for}} anidados para calcular la sumatoria de la sub-matriz que le corresponde al p\'ixel actual. Dichos ciclos van, al igual que los ciclos que se usan para calcular la matriz de convoluci\'on, desde $-Radio$ hasta $Radio$.\\
Luego se multiplica cada componente del p\'ixel que se recorre por la matriz de convoluci\'on en la misma posici\'on, se almacena en el acumulador y antes de terminar el ciclo se aumenta la posici\'on de la matriz de convoluci\'on. Esta operaci\'on se realiza por cada elemento de la sub-matriz (por los ciclos \emph{for}).

Al finalizar la sumatoria de la sub-matriz se guardan los valores de la sumatoria en cada canal del pixel actual en la imagen de destino y se contin\'ua con el ciclo. En el c\'odigo \ref{blurc_2} puede verse la operaci\'on de almacenamiento de cada componente en la imagen de destino.
\cscript{blurc_2}{blur_c}{Blur C - Ciclo princip\'al de calculo de matriz de convoluci\'on}{61}{64}


\subsubsection{Implementaci\'on Ensamblador}
\label{sec:blur_impasm}
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