Remove constant factor in O(F·N·4).

[mpi-energy2.git] / Heter_paper.tex

diff --git a/Heter_paper.tex b/Heter_paper.tex
index 0b545e4ad4f0cc6b0ef10247275210007dc2a614..be509e747a69c1f500a17463bcac8495dd185a3f 100644 (file)
--- a/Heter_paper.tex
+++ b/Heter_paper.tex
@@ -25,6 +25,9 @@
 
 \newcommand{\Xsub}[2]{{\ensuremath{#1_\mathit{#2}}}}
 
 
 \newcommand{\Xsub}[2]{{\ensuremath{#1_\mathit{#2}}}}
 

+%% 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{\CL}{\Xsub{C}{L}}
 \newcommand{\Dist}{\mathit{Dist}}
 \newcommand{\EdNew}{\Xsub{E}{dNew}}


@@ -33,24 +36,24 @@
 \newcommand{\Eoriginal}{\Xsub{E}{Original}}
 \newcommand{\Ereduced}{\Xsub{E}{Reduced}}
 \newcommand{\Es}{\Xsub{E}{S}}
 \newcommand{\Eoriginal}{\Xsub{E}{Original}}
 \newcommand{\Ereduced}{\Xsub{E}{Reduced}}
 \newcommand{\Es}{\Xsub{E}{S}}

-\newcommand{\Fdiff}{\Xsub{F}{diff}}
-\newcommand{\Fmax}{\Xsub{F}{max}}
+\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{\MaxDist}{\mathit{Max}\Dist}
 \newcommand{\MinTcm}{\mathit{Min}\Tcm}
 \newcommand{\Ntrans}{\Xsub{N}{trans}}
 \newcommand{\Fnew}{\Xsub{F}{new}}
 \newcommand{\Ileak}{\Xsub{I}{leak}}
 \newcommand{\Kdesign}{\Xsub{K}{design}}
 \newcommand{\MaxDist}{\mathit{Max}\Dist}
 \newcommand{\MinTcm}{\mathit{Min}\Tcm}
 \newcommand{\Ntrans}{\Xsub{N}{trans}}

-\newcommand{\Pd}{\Xsub{P}{d}}
+\newcommand{\Pd}[1][]{\Xsub{P}{d}_{\fxheight{#1}}}

 \newcommand{\PdNew}{\Xsub{P}{dNew}}
 \newcommand{\PdOld}{\Xsub{P}{dOld}}
 \newcommand{\Pnorm}{\Xsub{P}{Norm}}
 \newcommand{\PdNew}{\Xsub{P}{dNew}}
 \newcommand{\PdOld}{\Xsub{P}{dOld}}
 \newcommand{\Pnorm}{\Xsub{P}{Norm}}

-\newcommand{\Ps}{\Xsub{P}{s}}
-\newcommand{\Scp}{\Xsub{S}{cp}}
-\newcommand{\Sopt}{\Xsub{S}{opt}}
-\newcommand{\Tcm}{\Xsub{T}{cm}}
-\newcommand{\Tcp}{\Xsub{T}{cp}}
-\newcommand{\TcpOld}{\Xsub{T}{cpOld}}
+\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}} 
 


@@ -297,14 +300,14 @@ 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}

-  \Tnew = \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
+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
 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


@@ -397,13 +400,13 @@ The static energy of a processor after scaling its frequency is computed as foll
 \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


@@ -414,8 +417,8 @@ 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}) +
+ 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}
 
   {\MinTcm))}
  \end{multline}
 


@@ -464,8 +467,8 @@ maximum frequency for all nodes) as follows:
 \begin{multline}
   \label{eq:pnorm}
   \Pnorm = \frac{\Tnew}{\Told}\\
 \begin{multline}
   \label{eq:pnorm}
   \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)}}
+       {} = \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}
 
 


@@ -474,9 +477,9 @@ while scaling down the frequency and the consumed energy with maximum frequency
 \begin{multline}
   \label{eq:enorm}
   \Enorm = \frac{\Ereduced}{\Eoriginal} \\
 \begin{multline}
   \label{eq:enorm}
   \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)}}
+  {} = \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} 
 Where $\Ereduced$ and $\Eoriginal$ are computed using (\ref{eq:energy}) and
   $\Tnew$ and $\Told$ are computed as in (\ref{eq:pnorm}).
 \end{multline} 
 Where $\Ereduced$ and $\Eoriginal$ are computed using (\ref{eq:energy}) and
   $\Tnew$ and $\Told$ are computed as in (\ref{eq:pnorm}).


@@ -495,8 +498,8 @@ normalized execution time is inverted which gives the normalized performance equ
 \begin{multline}
   \label{eq:pnorm_inv}
   \Pnorm = \frac{\Told}{\Tnew}\\
 \begin{multline}
   \label{eq:pnorm_inv}
   \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} 
+          = \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}
 
 


@@ -564,14 +567,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,\dots,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


@@ -623,42 +626,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 $\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 $\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)}
     \State $\Dist \gets 0 $
     \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 $\Tnew \gets max_\textit{~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 $\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)$}
        \State $\Pnorm \gets \frac{\Told}{\Tnew}$
        \State $\Enorm\gets \frac{\Ereduced}{\Eoriginal}$
       \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}


@@ -711,7 +714,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.