\subsection{Medidas de eficiencia}

%- Introducci�n a la secci�n  OK
%- Definiciones b�sicas de rendimiento. OK
%- desglose del tiempo OK
%- Rendimiento de CPU
%	- MIPS �?
%	- MFLOPS �?
%	- Ejecuci�n de programas para evaluar el rendimiento �?
%- Comparaci�n de rendimientos
%	- Speed Up OK
% - Coste

En esta secci�n introduciremos los tipos de medidas de tiempo,
las dependencias que afectan a los resultados obtenidos con estas medidas,
los motivos por los cuales elegimos los ciclos como medida de tiempo para nuestro proyecto y,
finalmente, c�mo podemos comparar dos ejecuciones para observar la variaci�n de rendimiento del sistema evaluado.


\subsubsection{Medidas de c�lculo del tiempo}

La eficiencia (o rendimiento) de una ejecuci�n se asocia a dos factores.
Hablaremos de {\it throughput} o {\it ancho de banda} cuando el rendimiento se centre en medir la cantidad de trabajo realizado en un tiempo determinado
En cambio, nos referiremos a {\it latencia} cuando el rendimiento sea el tiempo transcurrido entre el comienzo y el final del evento.
Como el inter�s de este proyecto es estimar el tiempo de ejecuci�n de los procesos,
nuestra medida de eficiencia se basa en la latencia.

{\it John L.Hennessy}, en su libro de Arquitectura de computadores \cite{Arquitectura},
desglosa el tiempo de ejecuci�n tal y como se muestra en Fig. \ref{fig:DesgloseTiempo}


\begin{figure}[!ht] 
	\centering
	\fbox{\pdfimage width 6in {Imagenes/DesgloseTiempo.pdf}}
	\caption{Desglose del tiempo de ejecuci�n} 
	\label{fig:DesgloseTiempo}
\end{figure} 


\begin{enumerate}
\item {\bf Tiempo real:   }
Tambi�n conocido como \textit{Wall Clock} (reloj de pared), tiempo de respuesta o tiempo transcurrido ({\it elapsed time}).
Indica la latencia para completar una tarea.
La latencia depende de una serie de factores
como accesos a disco, accesos a memoria, actividades E/S,
gastos del sistema operativo o tiempo utilizado para la ejecuci�n de otros programas.
Estas dependencias implican que el resultado obtenido sea impreciso.
Por este motivo, el tiempo real se desglosa para obtener el tiempo de CPU. 

\item {\bf Tiempo de CPU:   }
El tiempo de CPU es la parte del tiempo real que la CPU dedica a nuestro proceso
sin incluir el tiempo de espera para las E/S o para ejecutar otros programas.
De esta forma obviamos el tiempo de ejecuci�n del resto de los programas que haya funcionando en paralelo al nuestro.
Este tiempo es la combinaci�n del tiempo de usuario y tiempo de sistema.

\item {\bf Tiempo de Usuario:   }
El tiempo de usuario es el tiempo de CPU que gasta un proceso sin contar las llamadas al sistema operativo.

\item {\bf Tiempo de Sistema:   }
Es el Tiempo de CPU que el proceso dedica a llamadas al sistema operativo, por ejemplo, para el acceso a dispositivos.
\end{enumerate}

Aunque el tiempo de CPU nos abstraiga de la ejecuci�n concurrente de otras tareas, 
dos ejecuciones no son comparables si se hacen en m�quinas distintas.
Una de las razones es que el tiempo de CPU es inversamente proporcional a la frecuencia del procesador.
Si ejecutamos un mismo proceso en dos procesadores con la misma arquitectura pero con frecuencias diferentes, el tiempo de CPU ser� distinto.

Para independizarnos de la velocidad del procesador,
a menudo, el tiempo se mide en ciclos.
Un ciclo se obtiene a partir del tiempo de ejecuci�n y la frecuencia del procesador.

\begin{center}
$
Ciclos_{CPU}=Tiempo_{CPU}*Frecuencia
$
\end{center}

Aunque el resultado ser� independiente de la velocidad del procesador,
el valor de los ciclos depende de aspectos arquit�ctonicos
(qu� arquitecturas que soporta,
c�mo se consideran las instrucciones vectoriales,
el tipo de cache,...)
y plataforma
(qu� valor tiene cada instrucci�n,
c�mo se contabilizan los {\it jumps} y las {\it pipelines},
qu� excepciones se tienen en cuenta,...).

% MIPS y MFLOPS
% En la b�squeda de una medida est�ndar de rendimiento se ha generalizado el uso de algunas m�tricas como alternativa al tiempo de ejecuci�n.
% Los m�s comunes son los {\it MIPS} y los {\it MFLOPS}.
% 
% 
% Los {\it MIPS} indican los millones de instrucciones que se realizan en un segundo.
% La f�rmula es la siguiente:
% 
% \begin{center}
% $
% MIPS=\frac{Instrucciones}{T_{ejecucion}*10^6}=\frac{Frecuencia}{CPI*10^6}
% $
% \end{center}
% 
% Y el tiempo de ejecuci�n podr�a obtenerse de la siguiente manera:
% 
% \begin{center}
% $
% T_{ejecucion}=\frac{Instrucciones}{MIPS*10^6}
% $
% \end{center}
% 
% La raz�n por la cual los {\it MIPS} no son �tiles para el c�lculo de eficiencia que deseamos
% es que el resultado no s�lo depende del repertorio de instrucciones,
% si no que tambi�n var�a entre programas de la misma m�quina,
% con lo cual, no es posible comparar resultados entre s�, que es nuestra finalidad.
% De hecho, los {\it MIPS} pueden variar inversamente al rendimiento.
% Un ejemplo es una m�quina con hardware opcional de punto flotante.
% Una instrucci�n de punto flotante suele requerir m�s ciclos de reloj que una instrucci�n entera,
% sin embargo, si se usa el hardware opcional en vez de rutinas de software,
% el tiempo utilizado para la ejecuci�n de la instrucci�n ser� menor pero esta disminuci�n de tiempo no implicar� un aumento proporcional de la frecuencia de {\it MIPS},
% con lo cual, el resultado obtenido a partir de los {\it MIPS} ser� contraproducente para realizar un progreso de la eficiencia. 
% 
% Los MFLOPS son los millones de instrucciones de punto flotante por segundo:
% 
% \begin{center}
% $
% MFLOPS=\frac{OperacionesPuntoFlotante}{T_{ejecucion}*10^6}
% $
% \end{center}
% 
% La estimaci�n de {\it MFLOPS}, al igual que suced�a con los {\it MIPS}, depeden de la m�quina y del programa que lo ejecute.
% Si consideraban que esta m�trica pod�a ser �til era porque,
% aunque cada m�quina ejecutase un n�mero diferentes de instrucciones,
% supon�an que las instrucciones de punto flotante ser�an las mismas.
% Sin embargo, es completamente falso ya que cada m�quina tiene un conjunto de operaciones de punto flotante diferente y,
% mientras hay m�quinas que tienen instrucciones de divisi�n, ra�ces cuadradas y cosenos ({\it Motorola 68882}), hay otras que ni tan siquiera tienen instrucciones de divisi�n ({\it CRAY-2}).
% 
% El motivo por el cual las m�tricas no son �tiles para medir la eficiencia de nuestro proyecto
% es porque el objetivo de nuestro proyecto es evaluar la evoluci�n del rendimiento del software en el tiempo,
% de manera que las diferentes evaluaciones de eficiencia puedan ser comparadas independientemente de la m�quina en la que se realiz� la ejecuci�n.
% El objetivo de los {\it MIPS} y los {\it MFLOPS}, es poder comparar el rendmiento de hardware
% ejecutando un mismo programa en m�quinas diferentes y comparando los resultados.
% Por lo tanto, el uso de m�tricas no sirve como soluci�n para el c�lculo de tests de eficiencia de software.

\subsubsection{Rendimiento y Speed Up}

Una vez elegida la medida de control del tiempo, falta comparar los ciclos de diferentes ejecuciones para valorar si la mejora de eficiencia.
Seg�n la {\it ley de Amdahl} extra�da del libro de {\it Hennessy} \cite{Arquitectura},
% \begin{citation}
{\it La mejora obtenida en el rendimiento al utilizar alg�n modo de ejecuci�n m�s r�pido, est� limitada por la fracci�n de tiempo que se pueda utilizar ese modo m�s r�pido}.
% \end{citation}
Esta ley define la ganancia de rendimiento o {\it speed up} que puede lograrse al utilizar una caracter�stica particular

\begin{center}
$
SpeedUp =
\frac{Rendimiento_x}{Rendimiento_R}
$
\end{center}

Donde $Rendimiento_x$ es el rendimiento de la tarea completa utilizando la mejora cuando sea posible
y $Rendimiento_R$ es el rendimiento de la tarea completa sin utilizar la mejora o, como en nuestro caso, el valor de referencia a partir del cual realizaremos la variaci�n de eficiencia.

Con esta f�rmula, el {\it Speed Up} ser� 1 cuando no haya ninguna variaci�n,
menor que uno cuando empeore el rendimiento
y mayor que uno cuando mejore.

Como nuestro inter�s es mostrar la variaci�n de eficiencia a partir del porcentaje de variaci�n,
primero modificaremos la f�rmula de tal manera que si no hay variaci�n el {\it Speed Up} sea 0, si empeora el rendimiento, sea menor que 0 y si mejora sea mayor que 0:
\begin{center}
$
SpeedUp=\frac{Rendimiento_x}{Rendimiento_R}-1
$

$
SpeedUp=\frac{Rendimiento_X - Rendimiento_R}{Renidimiento_R}
$
\end{center}

Esta f�rmula calcula el speedUp a partir del rendimiento, sin embargo, nosotros debemos calcular el speedUp a partir de los ciclos. Como el n�mero de ciclos es inversamente proporcional al rendimiento, la f�rmula quedar�a de la siguiente manera:

$
SpeedUp=\frac{\frac{1}{Ciclos_X} - \frac{1}{Ciclos_R}}{\frac{1}{Ciclos_R}}
$

$
SpeedUp=\frac{Ciclos_R}{Ciclos_X} - \frac{Ciclos_R}{Ciclos_R}
$

$
SpeedUp=\frac{Ciclos_R}{Ciclos_X} - 1
$

$
SpeedUp=\frac{Ciclos_R}{Ciclos_X} - 1
$

$
SpeedUp=\frac{Ciclos_R - Ciclos_X}{Ciclos_X}
$
Y, finalmente, cambiaremos el rango del resultado para que sea mostrado en porcentaje
\begin{center}
$
SpeedUp=100*\frac\frac{Ciclos_R - Ciclos_X}{Ciclos_X}
$
\end{center}

Esta f�rmula de {\it Speed up} ser� la utilizada para evaluar la progresi�n de rendimiento de cada uno de los tests de eficiencia que se hayan creado.

