Reword first 3 lines of the second paragraph of the abstract.

[mpi-energy2.git] / Heter_paper.tex

diff --git a/Heter_paper.tex b/Heter_paper.tex
index 014ad6056d683f34728df911fd8e56cf749ef190..af3d66087651d7dc6e5cc3fa2f42af3d3dc0442a 100644 (file)
--- a/Heter_paper.tex
+++ b/Heter_paper.tex
@@ -23,33 +23,40 @@
 \newcommand{\JC}[2][inline]{%
   \todo[color=red!10,#1]{\sffamily\textbf{JC:} #2}\xspace}
 
 \newcommand{\JC}[2][inline]{%
   \todo[color=red!10,#1]{\sffamily\textbf{JC:} #2}\xspace}
 

-\newcommand{\Xsub}[2]{\ensuremath{#1_\textit{#2}}}
+\newcommand{\Xsub}[2]{{\ensuremath{#1_\mathit{#2}}}}

 
 

-\newcommand{\Dist}{\textit{Dist}}
+%% used to put some subscripts lower, and make them more legible
+\newcommand{\fxheight}[1]{\ifx#1\relax\relax\else\rule{0pt}{1.52ex}#1\fi}
+
+\newcommand{\CL}{\Xsub{C}{L}}
+\newcommand{\Dist}{\mathit{Dist}}
+\newcommand{\EdNew}{\Xsub{E}{dNew}}

 \newcommand{\Eind}{\Xsub{E}{ind}}
 \newcommand{\Enorm}{\Xsub{E}{Norm}}
 \newcommand{\Eoriginal}{\Xsub{E}{Original}}
 \newcommand{\Ereduced}{\Xsub{E}{Reduced}}
 \newcommand{\Eind}{\Xsub{E}{ind}}
 \newcommand{\Enorm}{\Xsub{E}{Norm}}
 \newcommand{\Eoriginal}{\Xsub{E}{Original}}
 \newcommand{\Ereduced}{\Xsub{E}{Reduced}}

-\newcommand{\Fdiff}{\Xsub{F}{diff}}
-\newcommand{\Fmax}{\Xsub{F}{max}}
+\newcommand{\Es}{\Xsub{E}{S}}
+\newcommand{\Fdiff}[1][]{\Xsub{F}{diff}_{\!#1}}
+\newcommand{\Fmax}[1][]{\Xsub{F}{max}_{\fxheight{#1}}}

 \newcommand{\Fnew}{\Xsub{F}{new}}
 \newcommand{\Ileak}{\Xsub{I}{leak}}
 \newcommand{\Kdesign}{\Xsub{K}{design}}
 \newcommand{\Fnew}{\Xsub{F}{new}}
 \newcommand{\Ileak}{\Xsub{I}{leak}}
 \newcommand{\Kdesign}{\Xsub{K}{design}}

-\newcommand{\MaxDist}{\textit{Max Dist}}
+\newcommand{\MaxDist}{\mathit{Max}\Dist}
+\newcommand{\MinTcm}{\mathit{Min}\Tcm}

 \newcommand{\Ntrans}{\Xsub{N}{trans}}
 \newcommand{\Ntrans}{\Xsub{N}{trans}}

-\newcommand{\Pdyn}{\Xsub{P}{dyn}}
-\newcommand{\PnormInv}{\Xsub{P}{NormInv}}
+\newcommand{\Pd}[1][]{\Xsub{P}{d}_{\fxheight{#1}}}
+\newcommand{\PdNew}{\Xsub{P}{dNew}}
+\newcommand{\PdOld}{\Xsub{P}{dOld}}

 \newcommand{\Pnorm}{\Xsub{P}{Norm}}
 \newcommand{\Pnorm}{\Xsub{P}{Norm}}

-\newcommand{\Tnorm}{\Xsub{T}{Norm}}
-\newcommand{\Pstates}{\Xsub{P}{states}}
-\newcommand{\Pstatic}{\Xsub{P}{static}}
-\newcommand{\Sopt}{\Xsub{S}{opt}}
-\newcommand{\Tcomp}{\Xsub{T}{comp}}
-\newcommand{\TmaxCommOld}{\Xsub{T}{Max Comm Old}}
-\newcommand{\TmaxCompOld}{\Xsub{T}{Max Comp Old}}
-\newcommand{\Tmax}{\Xsub{T}{max}}
+\newcommand{\Ps}[1][]{\Xsub{P}{s}_{\fxheight{#1}}}
+\newcommand{\Scp}[1][]{\Xsub{S}{cp}_{#1}}
+\newcommand{\Sopt}[1][]{\Xsub{S}{opt}_{#1}}
+\newcommand{\Tcm}[1][]{\Xsub{T}{cm}_{\fxheight{#1}}}
+\newcommand{\Tcp}[1][]{\Xsub{T}{cp}_{#1}}
+\newcommand{\TcpOld}[1][]{\Xsub{T}{cpOld}_{#1}}

 \newcommand{\Tnew}{\Xsub{T}{New}}
 \newcommand{\Told}{\Xsub{T}{Old}} 
 \newcommand{\Tnew}{\Xsub{T}{New}}
 \newcommand{\Told}{\Xsub{T}{Old}} 

+

 \begin{document} 
 
 \title{Energy Consumption Reduction for Message Passing Iterative  Applications in Heterogeneous Architecture Using DVFS}
 \begin{document} 
 
 \title{Energy Consumption Reduction for Message Passing Iterative  Applications in Heterogeneous Architecture Using DVFS}


@@ -81,9 +88,10 @@ platforms many techniques have been  used. Dynamic voltage and frequency scaling
 consumption.  However,  lowering the  frequency  of  a  CPU might  increase  the
 execution  time of  an application  running on  that processor.   Therefore, the
 frequency that  gives the best trade-off  between the energy  consumption and the
 consumption.  However,  lowering the  frequency  of  a  CPU might  increase  the
 execution  time of  an application  running on  that processor.   Therefore, the
 frequency that  gives the best trade-off  between the energy  consumption and the

-performance of an application must be selected.\\
-In this  paper, a new  online frequencies selecting algorithm  for heterogeneous
-platforms is presented.   It selects the frequency which tries  to give the best
+performance of an application must be selected.
+
+In this  paper, a new  online frequency selecting algorithm  for heterogeneous
+platforms is presented.   It selects the frequencies and tries  to give the best

 trade-off  between  energy saving  and  performance  degradation,  for each  node
 computing the message  passing iterative application. The algorithm  has a small
 overhead and works without training or profiling. It uses a new energy model for
 trade-off  between  energy saving  and  performance  degradation,  for each  node
 computing the message  passing iterative application. The algorithm  has a small
 overhead and works without training or profiling. It uses a new energy model for


@@ -197,14 +205,14 @@ The work presented in this paper concerns the second type of platform, with
 heterogeneous CPUs.  Many methods were conceived to reduce the energy
 consumption of this type of platform.  Naveen et
 al.~\cite{Naveen_Power.Efficient.Resource.Scaling} developed a method that
 heterogeneous CPUs.  Many methods were conceived to reduce the energy
 consumption of this type of platform.  Naveen et
 al.~\cite{Naveen_Power.Efficient.Resource.Scaling} developed a method that

-minimizes the value of $energy\cdot delay^2$ (the delay is the sum of slack
-times that happen during synchronous communications) by dynamically assigning
-new frequencies to the CPUs of the heterogeneous cluster. Lizhe et
-al.~\cite{Lizhe_Energy.aware.parallel.task.scheduling} proposed an algorithm
-that divides the executed tasks into two types: the critical and non critical
-tasks. The algorithm scales down the frequency of non critical tasks
-proportionally to their slack and communication times while limiting the
-performance degradation percentage to less than
+minimizes the value of $\mathit{energy}\times \mathit{delay}^2$ (the delay is
+the sum of slack times that happen during synchronous communications) by
+dynamically assigning new frequencies to the CPUs of the heterogeneous
+cluster. Lizhe et al.~\cite{Lizhe_Energy.aware.parallel.task.scheduling}
+proposed an algorithm that divides the executed tasks into two types: the
+critical and non critical tasks. The algorithm scales down the frequency of non
+critical tasks proportionally to their slack and communication times while
+limiting the performance degradation percentage to less than

 10\%. In~\cite{Joshi_Blackbox.prediction.of.impact.of.DVFS}, they developed a
 heterogeneous cluster composed of two types of Intel and AMD processors. They
 use a gradient method to predict the impact of DVFS operations on performance.
 10\%. In~\cite{Joshi_Blackbox.prediction.of.impact.of.DVFS}, they developed a
 heterogeneous cluster composed of two types of Intel and AMD processors. They
 use a gradient method to predict the impact of DVFS operations on performance.


@@ -268,7 +276,7 @@ factor S which is the ratio between  the maximum and the new frequency of a CPU
 as in (\ref{eq:s}).
 \begin{equation}
   \label{eq:s}
 as in (\ref{eq:s}).
 \begin{equation}
   \label{eq:s}

- S = \frac{F_\textit{max}}{F_\textit{new}}
+ S = \frac{\Fmax}{\Fnew}

 \end{equation}
  The execution time of a compute bound sequential program is linearly proportional 
  to the frequency scaling factor $S$.  On the other hand,  message passing 
 \end{equation}
  The execution time of a compute bound sequential program is linearly proportional 
  to the frequency scaling factor $S$.  On the other hand,  message passing 


@@ -293,16 +301,15 @@ operation. Then the execution time for one iteration of the application with any
 vector of scaling factors can be predicted using (\ref{eq:perf}).
 \begin{equation}
   \label{eq:perf}
 vector of scaling factors can be predicted using (\ref{eq:perf}).
 \begin{equation}
   \label{eq:perf}

- \textit  T_\textit{new} = 
- \max_{i=1,2,\dots,N} ({TcpOld_{i}} \cdot S_{i}) +  MinTcm 
+  \Tnew = \max_{i=1,2,\dots,N} ({\TcpOld[i]} \cdot S_{i}) +  \MinTcm

 \end{equation}
 Where:
 \begin{equation}
 \label{eq:perf2}
 \end{equation}
 Where:
 \begin{equation}
 \label{eq:perf2}

- MinTcm = \min_{i=1,2,\dots,N} (Tcm_i)
+ \MinTcm = \min_{i=1,2,\dots,N} (\Tcm[i])

 \end{equation}
 \end{equation}

-where  $TcpOld_i$ is  the computation  time of  processor $i$  during  the first
-iteration and $MinTcm$  is the communication time of  the slowest processor from
+where  $\TcpOld[i]$ is  the computation  time of  processor $i$  during  the first
+iteration and $\MinTcm$  is the communication time of  the slowest processor from

 the  first iteration.   The model  computes  the maximum  computation time  with
 scaling factor  from each node  added to the  communication time of  the slowest
 node. It means only the communication  time without any slack time is taken into
 the  first iteration.   The model  computes  the maximum  computation time  with
 scaling factor  from each node  added to the  communication time of  the slowest
 node. It means only the communication  time without any slack time is taken into


@@ -323,28 +330,28 @@ Rauber_Analytical.Modeling.for.Energy,Zhuo_Energy.efficient.Dynamic.Task.Schedul
 Rizvandi_Some.Observations.on.Optimal.Frequency} divide the power consumed by a processor into
 two power metrics: the static and the dynamic power.  While the first one is
 consumed as long as the computing unit is turned on, the latter is only consumed during
 Rizvandi_Some.Observations.on.Optimal.Frequency} divide the power consumed by a processor into
 two power metrics: the static and the dynamic power.  While the first one is
 consumed as long as the computing unit is turned on, the latter is only consumed during

-computation times.  The dynamic power $Pd$ is related to the switching
-activity $\alpha$, load capacitance $C_L$, the supply voltage $V$ and
+computation times.  The dynamic power $\Pd$ is related to the switching
+activity $\alpha$, load capacitance $\CL$, the supply voltage $V$ and

 operational frequency $F$, as shown in (\ref{eq:pd}).
 \begin{equation}
   \label{eq:pd}
 operational frequency $F$, as shown in (\ref{eq:pd}).
 \begin{equation}
   \label{eq:pd}

-  Pd = \alpha \cdot C_L \cdot V^2 \cdot F
+  \Pd = \alpha \cdot \CL \cdot V^2 \cdot F

 \end{equation}
 \end{equation}

-The static power $Ps$ captures the leakage power as follows:
+The static power $\Ps$ captures the leakage power as follows:

 \begin{equation}
   \label{eq:ps}
 \begin{equation}
   \label{eq:ps}

-   Ps  = V \cdot N_{trans} \cdot K_{design} \cdot I_{leak}
+   \Ps  = V \cdot \Ntrans \cdot \Kdesign \cdot \Ileak

 \end{equation}
 \end{equation}

-where V is the supply voltage, $N_{trans}$ is the number of transistors,
-$K_{design}$ is a design dependent parameter and $I_{leak}$ is a
+where V is the supply voltage, $\Ntrans$ is the number of transistors,
+$\Kdesign$ is a design dependent parameter and $\Ileak$ is a

 technology dependent parameter.  The energy consumed by an individual processor
 to execute a given program can be computed as:
 \begin{equation}
   \label{eq:eind}
 technology dependent parameter.  The energy consumed by an individual processor
 to execute a given program can be computed as:
 \begin{equation}
   \label{eq:eind}

-   E_\textit{ind} =  Pd \cdot Tcp + Ps \cdot T
+  \Eind =  \Pd \cdot \Tcp + \Ps \cdot T

 \end{equation}
 \end{equation}

-where $T$ is the execution time of the program, $Tcp$ is the computation
-time and $Tcp \le T$.  $Tcp$ may be equal to $T$ if there is no
+where $T$ is the execution time of the program, $\Tcp$ is the computation
+time and $\Tcp \le T$.  $\Tcp$ may be equal to $T$ if there is no

 communication and no slack time.
 
 The main objective of DVFS operation is to reduce the overall energy consumption~\cite{Le_DVFS.Laws.of.Diminishing.Returns}.  
 communication and no slack time.
 
 The main objective of DVFS operation is to reduce the overall energy consumption~\cite{Le_DVFS.Laws.of.Diminishing.Returns}.  


@@ -355,19 +362,19 @@ process of the frequency can be expressed by the scaling factor $S$ which is the
 ratio between the maximum and the new frequency as in (\ref{eq:s}).
 The CPU governors are power schemes supplied by the operating
 system's kernel to lower a core's frequency. The new frequency 
 ratio between the maximum and the new frequency as in (\ref{eq:s}).
 The CPU governors are power schemes supplied by the operating
 system's kernel to lower a core's frequency. The new frequency 

-$F_{new}$ from (\ref{eq:s}) can be calculated as follows:
+$\Fnew$ from (\ref{eq:s}) can be calculated as follows:

 \begin{equation}
   \label{eq:fnew}
 \begin{equation}
   \label{eq:fnew}

-   F_\textit{new} = S^{-1} \cdot F_\textit{max}
+   \Fnew = S^{-1} \cdot \Fmax

 \end{equation}
 \end{equation}

-Replacing $F_{new}$ in (\ref{eq:pd}) as in (\ref{eq:fnew}) gives the following 
+Replacing $\Fnew$ in (\ref{eq:pd}) as in (\ref{eq:fnew}) gives the following 

 equation for dynamic power consumption:
 \begin{multline}
   \label{eq:pdnew}
 equation for dynamic power consumption:
 \begin{multline}
   \label{eq:pdnew}

-   {P}_\textit{dNew} = \alpha \cdot C_L \cdot V^2 \cdot F_{new} = \alpha \cdot C_L \cdot \beta^2 \cdot F_{new}^3 \\
-   {} = \alpha \cdot C_L \cdot V^2 \cdot F_{max} \cdot S^{-3} = P_{dOld} \cdot S^{-3}
+   \PdNew = \alpha \cdot \CL \cdot V^2 \cdot \Fnew = \alpha \cdot \CL \cdot \beta^2 \cdot \Fnew^3 \\
+   {} = \alpha \cdot \CL \cdot V^2 \cdot \Fmax \cdot S^{-3} = \PdOld \cdot S^{-3}

 \end{multline}
 \end{multline}

-where $ {P}_\textit{dNew}$  and $P_{dOld}$ are the  dynamic power consumed with the 
+where $\PdNew$  and $\PdOld$ are the  dynamic power consumed with the 

 new frequency and the maximum frequency respectively.
 
 According to (\ref{eq:pdnew}) the dynamic power is reduced by a factor of $S^{-3}$ when 
 new frequency and the maximum frequency respectively.
 
 According to (\ref{eq:pdnew}) the dynamic power is reduced by a factor of $S^{-3}$ when 


@@ -377,7 +384,7 @@ The new dynamic energy is the  dynamic power multiplied by the new time of compu
 and is given by the following equation:
 \begin{equation}
   \label{eq:Edyn}
 and is given by the following equation:
 \begin{equation}
   \label{eq:Edyn}

-   E_\textit{dNew} = P_{dOld} \cdot S^{-3} \cdot (Tcp \cdot S)= S^{-2}\cdot P_{dOld} \cdot  Tcp 
+   \EdNew = \PdOld \cdot S^{-3} \cdot (\Tcp \cdot S)= S^{-2}\cdot \PdOld \cdot  \Tcp 

 \end{equation}
 The static power is related to the power leakage of the CPU and is consumed during computation 
 and even when idle. As in~\cite{Rauber_Analytical.Modeling.for.Energy,Zhuo_Energy.efficient.Dynamic.Task.Scheduling}, 
 \end{equation}
 The static power is related to the power leakage of the CPU and is consumed during computation 
 and even when idle. As in~\cite{Rauber_Analytical.Modeling.for.Energy,Zhuo_Energy.efficient.Dynamic.Task.Scheduling}, 


@@ -390,17 +397,17 @@ to the frequency scaling factor, while this scaling factor does not affect the c
 The static energy of a processor after scaling its frequency is computed as follows: 
 \begin{equation}
   \label{eq:Estatic}
 The static energy of a processor after scaling its frequency is computed as follows: 
 \begin{equation}
   \label{eq:Estatic}

- E_\textit{s} = Ps \cdot (Tcp \cdot S  + Tcm)
+  \Es = \Ps \cdot (\Tcp \cdot S  + \Tcm)

 \end{equation}
 
 In  the  considered  heterogeneous  platform,  each  processor  $i$  might  have
 \end{equation}
 
 In  the  considered  heterogeneous  platform,  each  processor  $i$  might  have

-different   dynamic  and  static   powers,  noted   as  $Pd_{i}$   and  $Ps_{i}$
+different   dynamic  and  static   powers,  noted   as  $\Pd[i]$   and  $\Ps[i]$

 respectively.  Therefore,  even if  the  distributed  message passing  iterative
 application  is  load balanced,  the  computation time  of  each  CPU $i$  noted
 respectively.  Therefore,  even if  the  distributed  message passing  iterative
 application  is  load balanced,  the  computation time  of  each  CPU $i$  noted

-$Tcp_{i}$ might  be different and  different frequency scaling factors  might be
+$\Tcp[i]$ might  be different and  different frequency scaling factors  might be

 computed in order to decrease  the overall energy consumption of the application
 and reduce slack  times.  The communication time of a processor  $i$ is noted as
 computed in order to decrease  the overall energy consumption of the application
 and reduce slack  times.  The communication time of a processor  $i$ is noted as

-$Tcm_{i}$  and could  contain slack  times when  communicating  with slower
+$\Tcm[i]$  and could  contain slack  times when  communicating  with slower

 nodes,  see Figure~\ref{fig:heter}.  Therefore,  all nodes  do  not have  equal
 communication  times. While  the dynamic  energy  is computed  according to  the
 frequency  scaling   factor  and   the  dynamic  power   of  each  node   as  in
 nodes,  see Figure~\ref{fig:heter}.  Therefore,  all nodes  do  not have  equal
 communication  times. While  the dynamic  energy  is computed  according to  the
 frequency  scaling   factor  and   the  dynamic  power   of  each  node   as  in


@@ -411,9 +418,9 @@ heterogeneous platform during one iteration  is the summation of all dynamic and
 static energies for each processor.  It is computed as follows:
 \begin{multline}
   \label{eq:energy}
 static energies for each processor.  It is computed as follows:
 \begin{multline}
   \label{eq:energy}

- E = \sum_{i=1}^{N} {(S_i^{-2} \cdot Pd_{i} \cdot  Tcp_i)} + {} \\
- \sum_{i=1}^{N} (Ps_{i} \cdot (\max_{i=1,2,\dots,N} (Tcp_i \cdot S_{i}) +
-  {MinTcm))}
+ E = \sum_{i=1}^{N} {(S_i^{-2} \cdot \Pd[i] \cdot  \Tcp[i])} + {} \\
+ \sum_{i=1}^{N} (\Ps[i] \cdot (\max_{i=1,2,\dots,N} (\Tcp[i] \cdot S_{i}) +
+  {\MinTcm))}

  \end{multline}
 
 Reducing the frequencies of the processors according to the vector of
  \end{multline}
 
 Reducing the frequencies of the processors according to the vector of


@@ -460,9 +467,9 @@ scaling  down the  frequencies of  some processors)  and the  initial  one (with
 maximum frequency for all nodes) as follows:
 \begin{multline}
   \label{eq:pnorm}
 maximum frequency for all nodes) as follows:
 \begin{multline}
   \label{eq:pnorm}

-  P_\textit{Norm} = \frac{T_\textit{New}}{T_\textit{Old}}\\
-       {} = \frac{ \max_{i=1,2,\dots,N} (Tcp_{i} \cdot S_{i}) +MinTcm}
-           {\max_{i=1,2,\dots,N}{(Tcp_i+Tcm_i)}}
+  \Pnorm = \frac{\Tnew}{\Told}\\
+       {} = \frac{ \max_{i=1,2,\dots,N} (\Tcp[i] \cdot S_{i}) +\MinTcm}
+           {\max_{i=1,2,\dots,N}{(\Tcp[i]+\Tcm[i])}}

 \end{multline}
 
 
 \end{multline}
 
 


@@ -470,13 +477,13 @@ In the same way, the energy is normalized by computing the ratio between the con
 while scaling down the frequency and the consumed energy with maximum frequency for all nodes:
 \begin{multline}
   \label{eq:enorm}
 while scaling down the frequency and the consumed energy with maximum frequency for all nodes:
 \begin{multline}
   \label{eq:enorm}

-  E_\textit{Norm} = \frac{E_\textit{Reduced}}{E_\textit{Original}} \\
-  {} = \frac{ \sum_{i=1}^{N}{(S_i^{-2} \cdot Pd_i \cdot  Tcp_i)} +
- \sum_{i=1}^{N} {(Ps_i \cdot T_{New})}}{\sum_{i=1}^{N}{( Pd_i \cdot  Tcp_i)} +
- \sum_{i=1}^{N} {(Ps_i \cdot T_{Old})}}
+  \Enorm = \frac{\Ereduced}{\Eoriginal} \\
+  {} = \frac{ \sum_{i=1}^{N}{(S_i^{-2} \cdot \Pd[i] \cdot  \Tcp[i])} +
+ \sum_{i=1}^{N} {(\Ps[i] \cdot \Tnew)}}{\sum_{i=1}^{N}{( \Pd[i] \cdot  \Tcp[i])} +
+ \sum_{i=1}^{N} {(\Ps[i] \cdot \Told)}}

 \end{multline} 
 \end{multline} 

-Where $E_\textit{Reduced}$ and $E_\textit{Original}$ are computed using (\ref{eq:energy}) and
-  $T_{New}$ and $T_{Old}$ are computed as in (\ref{eq:pnorm}).
+Where $\Ereduced$ and $\Eoriginal$ are computed using (\ref{eq:energy}) and
+  $\Tnew$ and $\Told$ are computed as in (\ref{eq:pnorm}).

 
 While the main 
 goal is to optimize the energy and execution time at the same time, the normalized 
 
 While the main 
 goal is to optimize the energy and execution time at the same time, the normalized 


@@ -491,9 +498,9 @@ execution time following the same direction.  Therefore, the equation of the
 normalized execution time is inverted which gives the normalized performance equation, as follows:
 \begin{multline}
   \label{eq:pnorm_inv}
 normalized execution time is inverted which gives the normalized performance equation, as follows:
 \begin{multline}
   \label{eq:pnorm_inv}

-  P_\textit{Norm} = \frac{T_\textit{Old}}{T_\textit{New}}\\
-          = \frac{\max_{i=1,2,\dots,N}{(Tcp_i+Tcm_i)}}
-            { \max_{i=1,2,\dots,N} (Tcp_{i} \cdot S_{i}) + MinTcm} 
+  \Pnorm = \frac{\Told}{\Tnew}\\
+          = \frac{\max_{i=1,2,\dots,N}{(\Tcp[i]+\Tcm[i])}}
+            { \max_{i=1,2,\dots,N} (\Tcp[i] \cdot S_{i}) + \MinTcm} 

 \end{multline}
 
 
 \end{multline}
 
 


@@ -517,10 +524,10 @@ performance) at the same time, see Figure~\ref{fig:r1} or
 Figure~\ref{fig:r2}. Then the objective function has the following form:
 \begin{equation}
   \label{eq:max}
 Figure~\ref{fig:r2}. Then the objective function has the following form:
 \begin{equation}
   \label{eq:max}

-  Max Dist = 
-  \max_{i=1,\dots F, j=1,\dots,N}
-      (\overbrace{P_\textit{Norm}(S_{ij})}^{\text{Maximize}} -
-       \overbrace{E_\textit{Norm}(S_{ij})}^{\text{Minimize}} )
+  \MaxDist = 
+  \mathop{\max_{i=1,\dots F}}_{j=1,\dots,N}
+      (\overbrace{\Pnorm(S_{ij})}^{\text{Maximize}} -
+       \overbrace{\Enorm(S_{ij})}^{\text{Minimize}} )

 \end{equation}
 where $N$ is the number of nodes and $F$ is the  number of available frequencies for each node. 
 Then, the optimal set of scaling factors that satisfies (\ref{eq:max}) can be selected.  
 \end{equation}
 where $N$ is the number of nodes and $F$ is the  number of available frequencies for each node. 
 Then, the optimal set of scaling factors that satisfies (\ref{eq:max}) can be selected.  


@@ -561,14 +568,14 @@ frequency scaling factors are computed as a ratio between the computation time
 of the slowest node and the computation time of the node $i$ as follows:
 \begin{equation}
   \label{eq:Scp}
 of the slowest node and the computation time of the node $i$ as follows:
 \begin{equation}
   \label{eq:Scp}

- Scp_{i} = \frac{\max_{i=1,2,\dots,N}(Tcp_i)}{Tcp_i}
+ \Scp[i] = \frac{\max_{i=1,2,\dots,N}(\Tcp[i])}{\Tcp[i]}

 \end{equation}
 Using the initial  frequency scaling factors computed in (\ref{eq:Scp}), the algorithm computes 
 the initial frequencies for all nodes as a ratio between the maximum frequency of node $i$  
 \end{equation}
 Using the initial  frequency scaling factors computed in (\ref{eq:Scp}), the algorithm computes 
 the initial frequencies for all nodes as a ratio between the maximum frequency of node $i$  

-and the computation scaling factor $Scp_i$ as follows:
+and the computation scaling factor $\Scp[i]$ as follows:

 \begin{equation}
   \label{eq:Fint}
 \begin{equation}
   \label{eq:Fint}

- F_{i} = \frac{Fmax_i}{Scp_i},~{i=1,2,\cdots,N}
+ F_{i} = \frac{\Fmax[i]}{\Scp[i]},~{i=1,2,\dots,N}

 \end{equation}
 If the computed initial frequency for a node is not available in the gears of
 that node, it is replaced by the nearest available frequency.  In
 \end{equation}
 If the computed initial frequency for a node is not available in the gears of
 that node, it is replaced by the nearest available frequency.  In


@@ -620,41 +627,42 @@ maximum distance  between the  energy curve and  the performance curve  is while
     % \footnotesize
     \Require ~
     \begin{description}
     % \footnotesize
     \Require ~
     \begin{description}

-    \item[$Tcp_i$] array of all computation times for all nodes during one iteration and with highest frequency.
-    \item[$Tcm_i$] array of all communication times for all nodes during one iteration and with highest frequency.
-    \item[$Fmax_i$] array of the maximum frequencies for all nodes.
-    \item[$Pd_i$] array of the dynamic powers for all nodes.
-    \item[$Ps_i$] array of the static powers for all nodes.
-    \item[$Fdiff_i$] array of the difference between two successive frequencies for all nodes.
+    \item[{$\Tcp[i]$}] array of all computation times for all nodes during one iteration and with highest frequency.
+    \item[{$\Tcm[i]$}] array of all communication times for all nodes during one iteration and with highest frequency.
+    \item[{$\Fmax[i]$}] array of the maximum frequencies for all nodes.
+    \item[{$\Pd[i]$}] array of the dynamic powers for all nodes.
+    \item[{$\Ps[i]$}] array of the static powers for all nodes.
+    \item[{$\Fdiff[i]$}] array of the difference between two successive frequencies for all nodes.

     \end{description}
     \end{description}

-    \Ensure $Sopt_1,Sopt_2 \dots, Sopt_N$ is a vector of optimal scaling factors
+    \Ensure $\Sopt[1],\Sopt[2] \dots, \Sopt[N]$ is a vector of optimal scaling factors

 
 

-    \State $ Scp_i \gets \frac{\max_{i=1,2,\dots,N}(Tcp_i)}{Tcp_i} $
-    \State $F_{i} \gets  \frac{Fmax_i}{Scp_i},~{i=1,2,\cdots,N}$
+    \State $\Scp[i] \gets \frac{\max_{i=1,2,\dots,N}(\Tcp[i])}{\Tcp[i]} $
+    \State $F_{i} \gets  \frac{\Fmax[i]}{\Scp[i]},~{i=1,2,\cdots,N}$

     \State Round the computed initial frequencies $F_i$ to the closest one available in each node.
     \If{(not the first frequency)}
     \State Round the computed initial frequencies $F_i$ to the closest one available in each node.
     \If{(not the first frequency)}

-          \State $F_i \gets F_i+Fdiff_i,~i=1,\dots,N.$
+          \State $F_i \gets F_i+\Fdiff[i],~i=1,\dots,N.$

     \EndIf 
     \EndIf 

-    \State $T_\textit{Old} \gets max_{~i=1,\dots,N } (Tcp_i+Tcm_i)$
-    \State $E_\textit{Original} \gets \sum_{i=1}^{N}{( Pd_i \cdot  Tcp_i)} +\sum_{i=1}^{N} {(Ps_i \cdot T_{Old})}$
-    \State  $Sopt_{i} \gets 1,~i=1,\dots,N. $
-    \State $Dist \gets 0 $
+    \State $\Told \gets \max_{i=1,\dots,N} (\Tcp[i]+\Tcm[i])$
+    % \State $\Eoriginal \gets \sum_{i=1}^{N}{( \Pd[i] \cdot  \Tcp[i])} +\sum_{i=1}^{N} {(\Ps[i] \cdot \Told)}$
+    \State $\Eoriginal \gets \sum_{i=1}^{N}{( \Pd[i] \cdot  \Tcp[i] + \Ps[i] \cdot \Told)}$
+    \State $\Sopt[i] \gets 1,~i=1,\dots,N. $
+    \State $\Dist \gets 0 $

     \While {(all nodes not reach their  minimum  frequency)}
         \If{(not the last freq. \textbf{and} not the slowest node)}
     \While {(all nodes not reach their  minimum  frequency)}
         \If{(not the last freq. \textbf{and} not the slowest node)}

-        \State $F_i \gets F_i - Fdiff_i,~i=1,\dots,N.$
-        \State $S_i \gets \frac{Fmax_i}{F_i},~i=1,\dots,N.$
+        \State $F_i \gets F_i - \Fdiff[i],~i=1,\dots,N.$
+        \State $S_i \gets \frac{\Fmax[i]}{F_i},~i=1,\dots,N.$

         \EndIf
         \EndIf

-       \State $T_{New} \gets max_\textit{~i=1,\dots,N} (Tcp_{i} \cdot S_{i}) + MinTcm $
-       \State $E_\textit{Reduced} \gets \sum_{i=1}^{N}{(S_i^{-2} \cdot Pd_i \cdot  Tcp_i)} + $  \hspace*{43 mm} 
-               $\sum_{i=1}^{N} {(Ps_i \cdot T_{New})} $
-       \State $ P_\textit{Norm} \gets \frac{T_\textit{Old}}{T_\textit{New}}$
-       \State $E_\textit{Norm}\gets \frac{E_\textit{Reduced}}{E_\textit{Original}}$
+       \State $\Tnew \gets \max_{i=1,\dots,N} (\Tcp[i] \cdot S_{i}) + \MinTcm $
+%       \State $\Ereduced \gets \sum_{i=1}^{N}{(S_i^{-2} \cdot \Pd[i] \cdot  \Tcp[i])} + \sum_{i=1}^{N} {(\Ps[i] \cdot \rlap{\Tnew)}} $
+       \State $\Ereduced \gets \sum_{i=1}^{N}{(S_i^{-2} \cdot \Pd[i] \cdot  \Tcp[i] + \Ps[i] \cdot \rlap{\Tnew)}} $
+       \State $\Pnorm \gets \frac{\Told}{\Tnew}$
+       \State $\Enorm\gets \frac{\Ereduced}{\Eoriginal}$

       \If{$(\Pnorm - \Enorm > \Dist)$}
       \If{$(\Pnorm - \Enorm > \Dist)$}

-        \State $Sopt_{i} \gets S_{i},~i=1,\dots,N. $
+        \State $\Sopt[i] \gets S_{i},~i=1,\dots,N. $

         \State $\Dist \gets \Pnorm - \Enorm$
       \EndIf
     \EndWhile
         \State $\Dist \gets \Pnorm - \Enorm$
       \EndIf
     \EndWhile

-    \State  Return $Sopt_1,Sopt_2,\dots,Sopt_N$
+    \State  Return $\Sopt[1],\Sopt[2],\dots,\Sopt[N]$

   \end{algorithmic}
   \caption{frequency scaling factors selection algorithm}
   \label{HSA}
   \end{algorithmic}
   \caption{frequency scaling factors selection algorithm}
   \label{HSA}


@@ -707,7 +715,7 @@ brute force algorithm. It has a small execution time: for a heterogeneous
 cluster composed of four different types of nodes having the characteristics
 presented in Table~\ref{table:platform}, it takes on average \np[ms]{0.04} for 4
 nodes and \np[ms]{0.15} on average for 144 nodes to compute the best scaling
 cluster composed of four different types of nodes having the characteristics
 presented in Table~\ref{table:platform}, it takes on average \np[ms]{0.04} for 4
 nodes and \np[ms]{0.15} on average for 144 nodes to compute the best scaling

-factors vector.  The algorithm complexity is $O(F\cdot (N \cdot4) )$, where $F$
+factors vector.  The algorithm complexity is $O(F\cdot N)$, where $F$

 is the number of iterations and $N$ is the number of computing nodes. The
 algorithm needs from 12 to 20 iterations to select the best vector of frequency
 scaling factors that gives the results of the next sections.
 is the number of iterations and $N$ is the number of computing nodes. The
 algorithm needs from 12 to 20 iterations to select the best vector of frequency
 scaling factors that gives the results of the next sections.


@@ -741,22 +749,22 @@ nodes were connected via an Ethernet network with 1 Gbit/s bandwidth.
   \caption{Heterogeneous nodes characteristics}
   % title of Table
   \centering
   \caption{Heterogeneous nodes characteristics}
   % title of Table
   \centering

-  \begin{tabular}{|*{7}{l|}}
+  \begin{tabular}{|*{7}{r|}}

     \hline
     Node          &Simulated  & Max      & Min          & Diff.          & Dynamic      & Static \\
     type          &GFLOPS     & Freq.    & Freq.        & Freq.          & power        & power \\
                   &           & GHz      & GHz          &GHz             &              &       \\
     \hline
     \hline
     Node          &Simulated  & Max      & Min          & Diff.          & Dynamic      & Static \\
     type          &GFLOPS     & Freq.    & Freq.        & Freq.          & power        & power \\
                   &           & GHz      & GHz          &GHz             &              &       \\
     \hline

-    1             &40         & 2.5      & 1.2          & 0.1            & 20~W         &4~W    \\
+    1             &40         & 2.50     & 1.20         & 0.100          & \np[W]{20}   &\np[W]{4} \\

          
     \hline
          
     \hline

-    2             &50         & 2.66     & 1.6          & 0.133          & 25~W         &5~W    \\
+    2             &50         & 2.66     & 1.60         & 0.133          & \np[W]{25}   &\np[W]{5} \\

                   
     \hline
                   
     \hline

-    3             &60         & 2.9      & 1.2          & 0.1            & 30~W         &6~W    \\
+    3             &60         & 2.90     & 1.20         & 0.100          & \np[W]{30}   &\np[W]{6} \\

                   
     \hline
                   
     \hline

-    4             &70         & 3.4      & 1.6          & 0.133          & 35~W         &7~W    \\
+    4             &70         & 3.40     & 1.60         & 0.133          & \np[W]{35}   &\np[W]{7} \\

                   
     \hline
   \end{tabular}
                   
     \hline
   \end{tabular}


@@ -1126,6 +1134,24 @@ degradation.
   \label{table:res_s2}
 \end{table}
 
   \label{table:res_s2}
 \end{table}
 

+\begin{table}[!t]
+ \caption{Comparing the proposed algorithm}
+ \centering
+\begin{tabular}{|*{7}{r|}}
+\hline
+Program & \multicolumn{2}{c|}{Energy saving \%} & \multicolumn{2}{c|}{Perf.  degradation \%} & \multicolumn{2}{c|}{Distance} \\ \cline{2-7} 
+name    & EDP             & MaxDist          & EDP            & MaxDist           & EDP          & MaxDist        \\ \hline
+CG      & 27.58           & 31.25            & 5.82           & 7.12              & 21.76        & 24.13          \\ \hline
+MG      & 29.49           & 33.78            & 3.74           & 6.41              & 25.75        & 27.37          \\ \hline
+LU      & 19.55           & 28.33            & 0.0            & 0.01              & 19.55        & 28.22          \\ \hline
+EP      & 28.40           & 27.04            & 4.29           & 0.49              & 24.11        & 26.55          \\ \hline
+BT      & 27.68           & 32.32            & 6.45           & 7.87              & 21.23        & 24.43          \\ \hline
+SP      & 20.52           & 24.73            & 5.21           & 2.78              & 15.31         & 21.95         \\ \hline
+FT      & 27.03           & 31.02            & 2.75           & 2.54              & 24.28        & 28.48           \\ \hline
+
+\end{tabular}
+\label{table:compare_EDP}
+\end{table}

 
 \begin{figure}[!t]
   \centering
 
 \begin{figure}[!t]
   \centering


@@ -1138,16 +1164,31 @@ degradation.
   \caption{The comparison of the three power scenarios}
 \end{figure}  
 
   \caption{The comparison of the three power scenarios}
 \end{figure}  
 

-
+\begin{figure}[!t]
+  \centering
+   \includegraphics[scale=0.5]{fig/compare_EDP.pdf}
+  \caption{Trade-off comparison for NAS benchmarks class C}
+  \label{fig:compare_EDP}
+\end{figure}

 
 
 \subsection{The comparison of the proposed scaling algorithm }
 \label{sec.compare_EDP}
 
 
 \subsection{The comparison of the proposed scaling algorithm }
 \label{sec.compare_EDP}

-In this section, the scaling  factors selection algorithm, called MaxDist,
-is compared to Spiliopoulos et al. algorithm \cite{Spiliopoulos_Green.governors.Adaptive.DVFS}, called EDP. 
-They developed a green governor that regularly applies an online frequency selecting algorithm to reduce the energy consumed by a multicore architecture without degrading much its performance. The algorithm selects the frequencies that minimize the energy and delay products, $EDP=Energy\cdot Delay$ using the predicted overall energy consumption and execution time delay for each frequency.
-To fairly compare both algorithms, the same energy and execution time models, equations (\ref{eq:energy}) and  (\ref{eq:fnew}), were used for both algorithms to predict the energy consumption and the execution times. Also Spiliopoulos et al. algorithm was adapted to  start the search from the 
-initial frequencies computed using the equation (\ref{eq:Fint}). The resulting algorithm is an exhaustive search algorithm that minimizes the EDP and has the initial frequencies values as an upper bound.
+In this section, the scaling factors selection algorithm, called MaxDist, is
+compared to Spiliopoulos et al. algorithm
+\cite{Spiliopoulos_Green.governors.Adaptive.DVFS}, called EDP.  They developed a
+green governor that regularly applies an online frequency selecting algorithm to
+reduce the energy consumed by a multicore architecture without degrading much
+its performance. The algorithm selects the frequencies that minimize the energy
+and delay products, $\mathit{EDP}=\mathit{energy}\times \mathit{delay}$ using
+the predicted overall energy consumption and execution time delay for each
+frequency.  To fairly compare both algorithms, the same energy and execution
+time models, equations (\ref{eq:energy}) and (\ref{eq:fnew}), were used for both
+algorithms to predict the energy consumption and the execution times. Also
+Spiliopoulos et al. algorithm was adapted to start the search from the initial
+frequencies computed using the equation (\ref{eq:Fint}). The resulting algorithm
+is an exhaustive search algorithm that minimizes the EDP and has the initial
+frequencies values as an upper bound.

 
 Both algorithms were applied to the parallel NAS benchmarks to compare their
 efficiency. Table~\ref{table:compare_EDP} presents the results of comparing the
 
 Both algorithms were applied to the parallel NAS benchmarks to compare their
 efficiency. Table~\ref{table:compare_EDP} presents the results of comparing the


@@ -1165,39 +1206,6 @@ because it maximizes the distance  between the energy saving and the performance
 degradation values while giving the same weight for both metrics.
 
 
 degradation values while giving the same weight for both metrics.
 
 

-
-
-\begin{table}[!t]
- \caption{Comparing the proposed algorithm}
- \centering
-\begin{tabular}{|*{7}{r|}}
-\hline
-Program & \multicolumn{2}{c|}{Energy saving \%} & \multicolumn{2}{c|}{Perf.  degradation \%} & \multicolumn{2}{c|}{Distance} \\ \cline{2-7} 
-name    & EDP             & MaxDist          & EDP            & MaxDist           & EDP          & MaxDist        \\ \hline
-CG      & 27.58           & 31.25            & 5.82           & 7.12              & 21.76        & 24.13          \\ \hline
-MG      & 29.49           & 33.78            & 3.74           & 6.41              & 25.75        & 27.37          \\ \hline
-LU      & 19.55           & 28.33            & 0.0            & 0.01              & 19.55        & 28.22          \\ \hline
-EP      & 28.40           & 27.04            & 4.29           & 0.49              & 24.11        & 26.55          \\ \hline
-BT      & 27.68           & 32.32            & 6.45           & 7.87              & 21.23        & 24.43          \\ \hline
-SP      & 20.52           & 24.73            & 5.21           & 2.78              & 15.31         & 21.95         \\ \hline
-FT      & 27.03           & 31.02            & 2.75           & 2.54              & 24.28        & 28.48           \\ \hline
-
-\end{tabular}
-\label{table:compare_EDP}
-\end{table}
-
-
-
-
-
-\begin{figure}[!t]
-  \centering
-   \includegraphics[scale=0.5]{fig/compare_EDP.pdf}
-  \caption{Trade-off comparison for NAS benchmarks class C}
-  \label{fig:compare_EDP}
-\end{figure}
-
-

 \section{Conclusion}
 \label{sec.concl} 
 In this paper, a new online frequency selecting algorithm has been presented. It
 \section{Conclusion}
 \label{sec.concl} 
 In this paper, a new online frequency selecting algorithm has been presented. It


@@ -1253,6 +1261,5 @@ Babylon (Iraq) for supporting his work.
 
 % LocalWords:  Fanfakh Charr FIXME Tianhe DVFS HPC NAS NPB SMPI Rauber's Rauber
 % LocalWords:  CMOS EPSA Franche Comté Tflop Rünger IUT Maréchal Juin cedex GPU
 
 % LocalWords:  Fanfakh Charr FIXME Tianhe DVFS HPC NAS NPB SMPI Rauber's Rauber
 % LocalWords:  CMOS EPSA Franche Comté Tflop Rünger IUT Maréchal Juin cedex GPU

-% LocalWords:  de badri muslim MPI TcpOld TcmOld dNew dOld cp Sopt Tcp Tcm Ps
-% LocalWords:  Scp Fmax Fdiff SimGrid GFlops Xeon EP BT GPUs CPUs AMD
+% LocalWords:  de badri muslim MPI SimGrid GFlops Xeon EP BT GPUs CPUs AMD

 %  LocalWords:  Spiliopoulos scalability
 %  LocalWords:  Spiliopoulos scalability