Correct formulae and algorithm.

[mpi-energy.git] / paper.tex

diff --git a/paper.tex b/paper.tex
index 9d65cfbe56020e23416b929e1e1598585a635737..9c374ba8c8b4d56d6ca1346ca15f2942f2f41b28 100644 (file)
--- a/paper.tex
+++ b/paper.tex
@@ -285,8 +285,8 @@ function of the scaling factor $S$, as in EQ~\eqref{eq:energy}.
     \left( T_1 + \sum_{i=2}^{N} \frac{T_i^3}{T_1^2} \right) +
       \Pstatic \cdot T_1 \cdot S_1 \cdot N
 \end{equation}
     \left( T_1 + \sum_{i=2}^{N} \frac{T_i^3}{T_1^2} \right) +
       \Pstatic \cdot T_1 \cdot S_1 \cdot N
 \end{equation}

-where $N$ is the number of parallel nodes, $T_i$ for $i=1,\dots,N$ are
-the execution times and scaling factors of the sorted tasks.  Therefore, $T1$ is
+where $N$ is the number of parallel nodes, $T_i$ and $S_i$ for $i=1,\dots,N$ are
+the execution times and scaling factors of the sorted tasks.  Therefore, $T_1$ is

 the time of the slowest task, and $S_1$ its scaling factor which should be the
 highest because they are proportional to the time values $T_i$.  The scaling
 factors are computed as in EQ~\eqref{eq:si}.
 the time of the slowest task, and $S_1$ its scaling factor which should be the
 highest because they are proportional to the time values $T_i$.  The scaling
 factors are computed as in EQ~\eqref{eq:si}.


@@ -345,18 +345,18 @@ the consumed energy with scaled frequency and the consumed energy without scaled
 frequency:
 \begin{multline}
   \label{eq:enorm}
 frequency:
 \begin{multline}
   \label{eq:enorm}

-  \Enorm = \frac{ \Ereduced}{\Eoriginal} \\
-      {} = \frac{\Pdyn \cdot S_1^{-2} \cdot
+  \Enorm(S) = \frac{ \Ereduced}{\Eoriginal} \\
+         {} = \frac{\Pdyn \cdot S^{-2} \cdot

              \left( T_1 + \sum_{i=2}^{N}\frac{T_i^3}{T_1^2}\right) +
              \left( T_1 + \sum_{i=2}^{N}\frac{T_i^3}{T_1^2}\right) +

-               \Pstatic \cdot T_1 \cdot S_1 \cdot N}{
+               \Pstatic \cdot T_1 \cdot S \cdot N}{

              \Pdyn \cdot \left(T_1+\sum_{i=2}^{N}\frac{T_i^3}{T_1^2}\right) +
                \Pstatic \cdot T_1 \cdot N }
 \end{multline}
 In the same way we can normalize the performance as follows:
 \begin{equation}
   \label{eq:pnorm}
              \Pdyn \cdot \left(T_1+\sum_{i=2}^{N}\frac{T_i^3}{T_1^2}\right) +
                \Pstatic \cdot T_1 \cdot N }
 \end{multline}
 In the same way we can normalize the performance as follows:
 \begin{equation}
   \label{eq:pnorm}

-  \Pnorm = \frac{\Tnew}{\Told}
-         = \frac{\TmaxCompOld \cdot S + \TmaxCommOld}{
+  \Pnorm(S) = \frac{\Tnew}{\Told}
+            = \frac{\TmaxCompOld \cdot S + \TmaxCommOld}{

              \TmaxCompOld + \TmaxCommOld}
 \end{equation}
 The second problem is that the optimization operation for both energy and
              \TmaxCompOld + \TmaxCommOld}
 \end{equation}
 The second problem is that the optimization operation for both energy and


@@ -377,7 +377,7 @@ direction.  Therefore, we inverse the equation of the normalized performance as
 follows:
 \begin{equation}
   \label{eq:pnorm_en}
 follows:
 \begin{equation}
   \label{eq:pnorm_en}

-  \Pnorm^{-1} = \frac{ \Told}{ \Tnew}
+  \Pnorm^{-1}(S) = \frac{ \Told}{ \Tnew}

                = \frac{\TmaxCompOld +
                  \TmaxCommOld}{\TmaxCompOld \cdot S +
                  \TmaxCommOld}
                = \frac{\TmaxCompOld +
                  \TmaxCommOld}{\TmaxCompOld \cdot S +
                  \TmaxCommOld}


@@ -417,29 +417,33 @@ the objective function described above.
 \begin{figure}[tp]
   \begin{algorithmic}[1]
     % \footnotesize
 \begin{figure}[tp]
   \begin{algorithmic}[1]
     % \footnotesize

-    \State  Initialize the variable $\Dist=0$
-    \State Set dynamic and static power values.
-    \State Set $\Pstates$ to the number of available frequencies.
-    \State Set the variable $\Fnew$ to max. frequency,  $\Fnew = \Fmax $
-    \State Set the variable $\Fdiff$ to the difference between two successive
-           frequencies.
-    \For {$j := 1$ to $\Pstates $}
-      \State $\Fnew = \Fnew - \Fdiff $
-      \State $S = \frac{\Fmax}{\Fnew}$
-      \State $S_i = S \cdot \frac{T_1}{T_i}
-                  = \frac{\Fmax}{\Fnew} \cdot \frac{T_1}{T_i}$
-             for $i=1,\dots,N$
-      \State $\Enorm =
-          \frac{\Pdyn \cdot S_1^{-2} \cdot
+    \Require ~
+    \begin{description}
+    \item[$\Pstatic$] static power value
+    \item[$\Pdyn$] dynamic power value
+    \item[$\Pstates$] number of available frequencies
+    \item[$\Fmax$] maximum frequency
+    \item[$\Fdiff$] difference between two successive freq.
+    \end{description}
+    \Ensure $\Sopt$ is the optimal scaling factor
+
+    \State $\Sopt \gets 1$
+    \State $\Dist \gets 0$
+    \State $\Fnew \gets \Fmax$
+    \For {$j = 2$ to $\Pstates$}
+      \State $\Fnew \gets \Fnew - \Fdiff$
+      \State $S \gets \Fmax / \Fnew$
+      \State $\Enorm \gets
+          \frac{\Pdyn \cdot S^{-2} \cdot

                   \left( T_1 + \sum_{i=2}^{N}\frac{T_i^3}{T_1^2}\right) +
                   \left( T_1 + \sum_{i=2}^{N}\frac{T_i^3}{T_1^2}\right) +

-                  \Pstatic \cdot T_1 \cdot S_1 \cdot N }{
+                  \Pstatic \cdot T_1 \cdot S \cdot N }{

                 \Pdyn \cdot
                   \left(T_1+\sum_{i=2}^{N}\frac{T_i^3}{T_1^2}\right) +
                   \Pstatic \cdot T_1 \cdot N }$
                 \Pdyn \cdot
                   \left(T_1+\sum_{i=2}^{N}\frac{T_i^3}{T_1^2}\right) +
                   \Pstatic \cdot T_1 \cdot N }$

-      \State $\PnormInv = \Told / \Tnew$
+      \State $\PnormInv \gets \Told / \Tnew$

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

-        \State $\Sopt = S$
-        \State $\Dist = \PnormInv - \Enorm$
+        \State $\Sopt \gets S$
+        \State $\Dist \gets \PnormInv - \Enorm$

       \EndIf
     \EndFor
     \State  Return $\Sopt$
       \EndIf
     \EndFor
     \State  Return $\Sopt$


@@ -479,7 +483,7 @@ program.
 \begin{figure}[tp]
   \begin{algorithmic}[1]
     % \footnotesize
 \begin{figure}[tp]
   \begin{algorithmic}[1]
     % \footnotesize

-    \For {$k:=1$ to \textit{some iterations}}
+    \For {$k=1$ to \textit{some iterations}}

       \State Computations section.
       \State Communications section.
       \If {$(k=1)$}
       \State Computations section.
       \State Communications section.
       \If {$(k=1)$}