\section{Técnicas algorítmicas de uso frecuente en las implementaciones}\label{tec_alg}
En esta sección se describen dos técnicas algorítmicas aplicadas con mucha frecuencia en los distintos algoritmos implementados: \emph{loop unrolling} y \emph{software pipelining}.

El \emph{loop unrolling} se aplica tanto en las versiones escalares de los algoritmos estudiados, como en las vectorizadas. El \emph{software pipelining}, en cambio, solo en estas últimas.

\subsection{\emph{Loop Unrolling}}
El \emph{loop unrolling}, o también \emph{loop unwinding}, que en español se suele traducir como \emph{desenrosado de ciclos}, o \emph{despliegue de ciclos}, es una técnica algorítmica que busca optimizar la velocidad de los ciclos basados en iteraciones (por ejemplo, el bucle \texttt{for}).

Consiste sencillamente en el despliegue secuencial del bloque de código correspondiente a cada iteración del ciclo. En términos más prácticos, si tenemos un ciclo como el siguiente:

{\setlength{\parskip}{0cm}
\begin{flushleft}
\hspace{24pt}\textbf{Para} $i=0$ hasta $4$, \textbf{hacer}\\
\vspace{5pt}
\hspace{36pt}$f(i)$ \\
\vspace{5pt}
\hspace{24pt}\textbf{Fin Para}\\
\end{flushleft}}

Donde $f$ es cualquier bloque de código que puede o no requerir al contador $i$, lo reemplazamos por esto otro:

{\setlength{\parskip}{0cm}
\begin{flushleft}
\hspace{24pt}$f(0)$ \\
\hspace{24pt}$f(1)$ \\
\hspace{24pt}$f(2)$ \\
\hspace{24pt}$f(3)$ \\
\hspace{24pt}$f(4)$ \\
\end{flushleft}}

Como resultado del despliegue, nos ahorramos todas las instrucciones relativas al control del ciclo, tales como el incremento de la variable que actúa como contador, como así también las instrucciones de comparación que evalúan la condición de finalización del ciclo.

Esta técnica, que a las claras es muy simple, suele mejorar considerablemente la performance de un ciclo, o incluso la aplicación entera. Esto es algo que comprobaremos en la primera experiencia del trabajo, que se describe en la sección \ref{tec_alg:experiencia} siguiente. Tiene la desventaja, sin embargo, de que puede incrementar significativamente el tamaño del ejecutable final. Pero en los casos donde el tamaño del programa no resulte un problema, o el incremento no sea significativo o, sobre todo, cuando la performance sea prioridad, como puede ser el caso del cómputo de un valor de hash, es altamente probable que el \emph{loop unrolling} resulte conveniente.

En general, este mecanismo suele implementarse mediante el uso de \emph{macros}; en particular, aquellas que admiten parámetros. Las macros simplifican y automatizan el proceso de despliegue al permitirnos definir el bloque de código a desplegar en un solo lugar, y en función de algún parámetro que represente el número de iteración. Con este valor, el ensamblador realiza el reemplazo correctamente en cada lugar. De otra forma, la tarea puede volverse demasiado tediosa y altamente susceptible a errores, dado que el proceso de despliegue para cada iteración habría que realizarlo de forma manual.

Veamos un ejemplo sencillo. Consideremos el caso de un ciclo de $20$ iteraciones en el cual se leen secuencialmente en el registro \texttt{RAX} 20 valores \texttt{QWORD} desde un área de memoria apuntada por \texttt{BUFFER\_PTR}. El código en ensamblador, sin \emph{loop unrolling}, podría ser algo como lo siguiente:

\newpage

\begin{verbatim}
      ...

   XOR RCX, RCX

loop:

   ;
   ; Actualización del puntero al buffer basado en el
   ; contador de la iteración.
   ;
   MOV RBX, RCX
   SHL RBX, 3	  ; Multiplicamos por 8.

   ;
   ; Leemos el QWORD utilizando a RBX como offset.
   ;
   MOV RAX, [BUFFER_PTR + RBX]

   ;
   ; Instrucciones de control del ciclo.
   ;
   INC RCX
   CMP RCX, 20
   JLE loop

      ...
\end{verbatim}

El mismo código, con \emph{loop unrolling} implementado a través de macros, se convierte en esto otro:

\begin{verbatim}
   ;
   ; Definición de la macro para el despliegue.
   ;
   ; Recibe dos parámetros:
   ;
   ; %1: dirección del buffer.
   ; %2: número de ronda.
   ;
   %macro UNROLLED_LOOP 2

      MOV RAX, [%1 + %2*8]

   %endmacro

       ...

   ;
   ; El ciclo se transformó en esto:
   ;
   UNROLLED_LOOP BUFFER_PTR, 0
   UNROLLED_LOOP BUFFER_PTR, 1
   UNROLLED_LOOP BUFFER_PTR, 2
   UNROLLED_LOOP BUFFER_PTR, 3

       ...

   UNROLLED_LOOP BUFFER_PTR, 19	
\end{verbatim}

\newpage
Como resultado, el ensamblador traduce el código anterior en lo siguiente antes del proceso de ensamblaje:

\begin{verbatim}
   MOV RAX, [BUFFER_PTR]
   MOV RAX, [BUFFER_PTR + 8]
   MOV RAX, [BUFFER_PTR + 16]
   MOV RAX, [BUFFER_PTR + 24]
  
      ...

   MOV RAX, [BUFFER_PTR + 152]
\end{verbatim}

Donde antes había 6 instrucciones, ahora hay una sola, y esto tendrá como resultado una mejora considerable en la velocidad de ejecución.

\subsubsection{Experiencia}\label{tec_alg:experiencia}
Con el objeto de verificar qué tanto puede mejorar el desempeño de un algoritmo al emplear la técnica del \emph{loop unrolling}, realizamos una experiencia muy sencilla: escribimos un programa en \emph{C} que implementa el primero de los algoritmos analizados en este trabajo: el algoritmo \emph{SHA-1}.

El programa puede ejecutar el algoritmo en una de dos versiones: la primera, sin \emph{loop unrolling}, y la segunda, con \emph{loop unrolling}. Recibe, por lo tanto, dos parámetros: el primero, con el tipo de versión a ejecutar, y el segundo, con la ruta absoluta al archivo con los datos para los que se pretende calcular el valor de hash SHA-1. Al finalizar, la aplicación devuelve, entre otras cosas, el valor del hash SHA-1 asociado al archivo, y el \emph{tiempo de CPU} que fue requerido por el cálculo. Estos datos también se guardan en un archivo de salida\footnote{La sección \ref{implementaciones} describe todos los detalles acerca del modo de uso, código fuente, generación y procesamiento de los datos, etc., de la aplicación implementada para esta experiencia.}.

Dado que el algoritmo SHA-1 es tema de la sección \ref{sha1}, donde se lo analiza en detalle, omitimos ahora cualquier descripción, y nos enfocamos en el resultado de la comparación entre las dos implementaciones con y sin \emph{loop unrolling}, respectivamente \footnote{Sin embargo, la lectura del código fuente del programa para esta primera experiencia debería resultar lo suficientemente claro para su comprensión.}.

La experiencia consistió en la ejecución de ambas versiones del algoritmo SHA-1 sobre un grupo de archivos cuyos tamaños varían en el rango $0.5$ \emph{GB} y $3.0$ \emph{GB}, en saltos de $0.5$ \emph{GB} (es decir, 6 archivos de tamaños $0.5$, $1$, $1.5$, $2$, $2.5$ y $3.0$ \emph{GB}, respectivamente). Cada ejecución se repitió media docena de veces, y de ahí se obtuvo el tiempo de CPU promedio para cada caso.

El esquema \ref{loop_unrolling} ilustra el resultado de la prueba.

\begin{figure}[!ht]
\centering
\includegraphics[scale=0.70]{img/sha1_c_vs_c_3gb.png}
\caption{implementaciones de SHA-1 con y sin \emph{loop unrolling}}\label{loop_unrolling}
\end{figure}

Del análisis de los datos, se desprende que la versión con \emph{loop unrolling} resultó ser casi un $50\%$ más rápida que la implementación sin \emph{loop unrolling}! ($47,1\%$, para ser precisos) La diferencia es muy notable.

A la luz de estos resultados, todos los algoritmos implementados en este trabajo, tanto en las versiones escalares como en las vectorizadas, incluirán esta optimización.

\newpage
\subsection{\emph{Software Pipelining}}
\emph{Software pipelining} es otra técnica algorítmica de optimización, que consiste básicamente en la ejecución de múltiples ductos o secuencias de instrucciones independientes entre sí. Tiene como resultado el aprovechamiento de la \emph{ejecución fuera de orden}, propiedad de los procesadores capaz de optimizar el número de operaciones que éstos realizan en paralelo durante los ciclos de instrucción \emph{fetch-decode-execute}. Veamos la idea con un ejemplo. Sea el siguiente ciclo:
{\setlength{\parskip}{0cm}
\begin{flushleft}
\hspace{24pt} \\
\hspace{24pt}\textbf{Para} $i=0$ hasta $N$, \textbf{hacer}\\
\vspace{5pt}
\hspace{36pt}$a = f(i)$ \\
\hspace{36pt}$b = g(a)$ \\
\hspace{36pt}$h(b)$ \\
\vspace{5pt}
\hspace{24pt}\textbf{Fin Para} \\
\end{flushleft}}

Es evidente la dependencia $h \rightarrow g \rightarrow f$, donde el nexo son, en este caso, las variables $a$ y $b$. Este código, por lo tanto, debe ejecutarse de forma secuencial, y la ejecución fuera de orden esencialmente no es posible. Notemos, sin embargo, que la secuencia de instrucciones en un ciclo $i$ es independiente a la del ciclo $i+1$.

El \emph{software pipelining} consiste en el reordenamiento de las sentencias de modo tal que las instrucciones de la secuencia resulten independientes entre sí. En nuestro caso, este reordenamiento podría ser algo como lo siguiente:

{\setlength{\parskip}{0cm}
\begin{flushleft}
\hspace{24pt} \\
\hspace{24pt}$a = f(0)$\\
\hspace{24pt}$b = g(a)$\\
\hspace{24pt}$a = f(1)$\\
\hspace{24pt} \\
\hspace{24pt}\textbf{Para} $i=2$ hasta $N$, \textbf{hacer} \\
\vspace{5pt}
\hspace{36pt}$h(b)$ \\
\hspace{36pt}$b = g(a)$ \\
\hspace{36pt}$a = f(i)$ \\
\vspace{5pt}
\hspace{24pt}\textbf{Fin Para} \\
\hspace{24pt} \\
\hspace{24pt}$b = g(a)$ \\
\hspace{24pt}$h(b)$ \\
\end{flushleft}}

Si observamos el cuerpo del ciclo, las instrucciones que lo componen ahora son independientes, puesto que son las mismas que en la secuencia original, pero en el orden inverso. Notemos también que este reordenamiento implicó la ejecución de ciertas instrucciones \emph{de arranque} antes del ciclo, y la ejecución de otras ciertas instrucciones que \emph{cierran} el cómputo al finalizar dicho ciclo; lo primero se denomina \emph{prólogo}, y lo segundo, \emph{epílogo}.

Depleguemos el ciclo algunas iteraciones para hacer otra observación:

{\setlength{\parskip}{0cm}
\begin{flushleft}
\hspace{24pt} \\
\hspace{24pt}\texttt{//} \\
\hspace{24pt}\texttt{// Prólogo} \\
\hspace{24pt}\texttt{//} \\
\hspace{24pt}$a = f(0)$  \hspace{10pt} \texttt{<- "Ducto"} \texttt{0} \\
\hspace{24pt}$b = g(a)$  \hspace{11pt} \texttt{<- "Ducto"} \texttt{0} \\
\hspace{24pt}$a = f(1)$  \hspace{10pt} \texttt{<- "Ducto"} \texttt{1} \\
\hspace{24pt} \\
\hspace{24pt}\texttt{//} \\
\hspace{24pt}\texttt{// Ciclo desplegado.} \\
\hspace{24pt}\texttt{//} \\
\hspace{24pt}$h(b)$      \hspace{28pt} \texttt{<- "Ducto"} \texttt{0 - Completado} \\
\hspace{24pt}$b = g(a)$  \hspace{10pt} \texttt{<- "Ducto"} \texttt{1} \\
\hspace{24pt}$a = f(2)$  \hspace{9pt} \texttt{<- "Ducto"} \texttt{2} \\
\hspace{24pt} \\
\hspace{24pt}$h(b)$      \hspace{28pt} \texttt{<- "Ducto"} \texttt{1 - Completado} \\
\hspace{24pt}$b = g(a)$  \hspace{10pt} \texttt{<- "Ducto"} \texttt{2} \\
\hspace{24pt}$a = f(3)$  \hspace{9pt} \texttt{<- "Ducto"} \texttt{3} \\
\hspace{24pt} \\
\hspace{24pt}$h(b)$      \hspace{28pt} \texttt{<- "Ducto"} \texttt{2 - Completado} \\
\hspace{24pt}$b = g(a)$  \hspace{10pt} \texttt{<- "Ducto"} \texttt{3} \\
\hspace{24pt}$a = f(4)$  \hspace{9pt} \texttt{<- "Ducto"} \texttt{4} \\
\hspace{24pt} \\
\hspace{48pt}$...$ \\
\hspace{24pt} \\
\hspace{24pt}\texttt{//} \\
\hspace{24pt}\texttt{// Epílogo} \\
\hspace{24pt}\texttt{//} \\
\hspace{24pt}$b = g(a)$  \hspace{10pt} \texttt{<- "Ducto"} \texttt{N} \\
\hspace{24pt}$h(b)$      \hspace{28pt} \texttt{<- "Ducto"} \texttt{N - Completado} \\
\end{flushleft}}


Las etiquetas marcan cada ducto o secuencia independiente de instrucciones que se generan como resultado de la aplicación de esta técnica: es como que los datos en cada iteración se desplazan a la siguiente etapa de procesamiento en cada ducto paralelo.

La desventaja del software pipelining radica fundamentalmente en la manera que dificulta la comprensión del código: el prólogo, el cuerpo del ciclo, y el epílogo pueden fácilmente dar la impresión de no tener ninguna relación entre sí.

El \emph{software pipelining} se suele combinar con el \emph{loop unrolling} precisamente para favorecer el procesamiento de los múltiples \emph{ductos}, a lo que se le suma las ventajas en el ahorro de las instrucciones de control del ciclo.

En el marco de este trabajo, el \emph{software pipelinig} se aplica únicamente a las implementaciones vectorizadas de los algoritmos analizados.

