\usepackage{subfig}
\usepackage{amsmath}
\usepackage{url}
+
\DeclareUrlCommand\email{\urlstyle{same}}
\usepackage[autolanguage,np]{numprint}
the 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
+ platforms (heterogeneous CPUs) 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 message passing iterative applications running on a heterogeneous
platform. The proposed algorithm is evaluated on the SimGrid simulator while
running the NAS parallel benchmarks. The experiments show that it reduces the
- energy consumption by up to \np[\%]{35} while limiting the performance
+ energy consumption by up to \np[\%]{34} while limiting the performance
degradation as much as possible. Finally, the algorithm is compared to an
- existing method, the comparison results showing that it outperforms the
- latter.
+ existing method, the comparison results show that it outperforms the
+ latter, on average it saves \np[\%]{4} more energy while keeping the same performance.
\end{abstract}
goal. Reducing the frequency of a processor lowers its number of FLOPS and may
degrade the performance of the application running on that processor, especially
if it is compute bound. Therefore selecting the appropriate frequency for a
-processor to satisfy some objectives while taking into account all the
+processor to satisfy some objectives, while taking into account all the
constraints, is not a trivial operation. Many researchers used different
strategies to tackle this problem. Some of them developed online methods that
compute the new frequency while executing the application, such
$\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 energy and execution time curves are not in the same
-direction. According to the equations~(\ref{eq:pnorm}) and (\ref{eq:enorm}), the
+time, the normalized energy and execution time curves do not evolve (increase/decrease) in the same way. According to the equations~(\ref{eq:pnorm}) and (\ref{eq:enorm}), the
vector of frequency scaling factors $S_1,S_2,\dots,S_N$ reduce both the energy
and the execution time simultaneously. But the main objective is to produce
maximum energy reduction with minimum execution time reduction.
This problem can be solved by making the optimization process for energy and
-execution time following the same direction. Therefore, the equation of the
+execution time follow the same evolution according to the vector of scaling factors. Therefore, the equation of the
normalized execution time is inverted which gives the normalized performance
equation, as follows:
\begin{multline}
\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[{$\Fdiff[i]$}] array of the differences between two successive frequencies for all nodes.
\end{description}
\Ensure $\Sopt[1],\Sopt[2] \dots, \Sopt[N]$ is a vector of optimal scaling factors
according to the computed initial frequency scaling factors. The resulting new
frequencies are highlighted in Figure~\ref{fig:st_freq}. This set of
frequencies can be considered as a higher bound for the search space of the
-optimal vector of frequencies because selecting frequency scaling factors higher
+optimal vector of frequencies because selecting scaling factors higher
than the higher bound will not improve the performance of the application and it
will increase its overall energy consumption. Therefore the algorithm that
selects the frequency scaling factors starts the search method from these
initial frequencies and takes a downward search direction toward lower
-frequencies. The algorithm iterates on all left frequencies, from the higher
+frequencies. The algorithm iterates on all remaining frequencies, from the higher
bound until all nodes reach their minimum frequencies, to compute their overall
energy consumption and performance, and select the optimal frequency scaling
factors vector. At each iteration the algorithm determines the slowest node
until they reach the higher bound. It can also be noticed that the higher the
difference between the faster nodes and the slower nodes is, the bigger the
maximum distance between the energy curve and the performance curve is while the
-scaling factors are varying which results in bigger energy savings.
+scaling factors are varying which results in bigger energy savings.
+Finally, in a homogeneous platform the energy consumption is increased when the scaling factor is very high.
+Indeed, the dynamic energy saved by reducing the frequency of the processor is compensated by the significant increase of the execution time and thus the increased of the static energy. On the other hand, in a heterogeneous platform this is not the case.
\subsection{The evaluation of the proposed algorithm}
\label{sec.verif.algo}
very precise, the maximum normalized difference between the predicted execution
time and the real execution time is equal to 0.03 for all the NAS benchmarks.
-Since the proposed algorithm is not an exact method it does not test all the
+Since the proposed algorithm is not an exact method, it does not test all the
possible solutions (vectors of scaling factors) in the search space. To prove
its efficiency, it was compared on small instances to a brute force search
algorithm that tests all the possible solutions. The brute force algorithm was
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)$, 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.
+maximum number of available frequencies, 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.
\begin{table}[!t]
\caption{Heterogeneous nodes characteristics}
\label{sec.expe}
To evaluate the efficiency and the overall energy consumption reduction of
-Algorithm~\ref{HSA}, it was applied to the NAS parallel benchmarks NPB v3.3. The
+Algorithm~\ref{HSA}, it was applied to the NAS parallel benchmarks NPB v3.3 which
+is composed of synchronous message passing applications. The
experiments were executed on the simulator SimGrid/SMPI which offers easy tools
to create a heterogeneous platform and run message passing applications over it.
The heterogeneous platform that was used in the experiments, had one core per
MG, FT, BT, LU and SP) and the benchmarks were executed with the three classes:
A, B and C. However, due to the lack of space in this paper, only the results of
the biggest class, C, are presented while being run on different number of
-nodes, ranging from 4 to 128 or 144 nodes depending on the benchmark being
+nodes, ranging from 8 to 128 or 144 nodes depending on the benchmark being
executed. Indeed, the benchmarks CG, MG, LU, EP and FT had to be executed on 1,
2, 4, 8, 16, 32, 64, or 128 nodes. The other benchmarks such as BT and SP had
to be executed on 1, 4, 9, 16, 36, 64, or 144 nodes.
\begin{table}[!t]
- \caption{Running NAS benchmarks on 4 nodes }
- % title of Table
- \centering
- \begin{tabular}{|*{7}{r|}}
- \hline
- \hspace{-2.2084pt}%
- Program & Execution & Energy & Energy & Performance & Distance \\
- name & time/s & consumption/J & saving\% & degradation\% & \\
- \hline
- CG & 64.64 & 3560.39 & 34.16 & 6.72 & 27.44 \\
- \hline
- MG & 18.89 & 1074.87 & 35.37 & 4.34 & 31.03 \\
- \hline
- EP & 79.73 & 5521.04 & 26.83 & 3.04 & 23.79 \\
- \hline
- LU & 308.65 & 21126.00 & 34.00 & 6.16 & 27.84 \\
- \hline
- BT & 360.12 & 21505.55 & 35.36 & 8.49 & 26.87 \\
- \hline
- SP & 234.24 & 13572.16 & 35.22 & 5.70 & 29.52 \\
- \hline
- FT & 81.58 & 4151.48 & 35.58 & 0.99 & 34.59 \\
- \hline
- \end{tabular}
- \label{table:res_4n}
+
% \end{table}
- \medskip
+
% \begin{table}[!t]
\caption{Running NAS benchmarks on 8 and 9 nodes }
% title of Table
energy consumption model (\ref{eq:energy}), with and without applying the
algorithm. The execution time was also measured for all these experiments. Then,
the energy saving and performance degradation percentages were computed for each
-instance. The results are presented in Tables~\ref{table:res_4n},
+instance. The results are presented in Tables
\ref{table:res_8n}, \ref{table:res_16n}, \ref{table:res_32n},
\ref{table:res_64n} and \ref{table:res_128n}. All these results are the average
values from many experiments for energy savings and performance degradation.
The tables show the experimental results for running the NAS parallel benchmarks
-on different number of nodes. The experiments show that the algorithm
-significantly reduces the energy consumption (up to \np[\%]{35}) and tries to
+on different numbers of nodes. The experiments show that the algorithm
+significantly reduces the energy consumption (up to \np[\%]{34}) and tries to
limit the performance degradation. They also show that the energy saving
percentage decreases when the number of computing nodes increases. This
reduction is due to the increase of the communication times compared to the
increase. While for the EP and SP benchmarks, the energy saving percentage is
not affected by the increase of the number of computing nodes, because in these
benchmarks there are little or no communications. Finally, the energy saving of
-the GC benchmark significantly decrease when the number of nodes increase
+the CG benchmark significantly decreases when the number of nodes increase
because this benchmark has more communications than the others. The second plot
shows that the performance degradation percentages of most of the benchmarks
decrease when they run on a big number of nodes because they spend more time
iterative applications running over heterogeneous platforms. To evaluate the
proposed method, it was applied on the NAS parallel benchmarks and executed over
a heterogeneous platform simulated by SimGrid. The results of the experiments
-showed that the algorithm reduces up to \np[\%]{35} the energy consumption of a
+showed that the algorithm reduces up to \np[\%]{34} the energy consumption of a
message passing iterative method while limiting the degradation of the
performance. The algorithm also selects different scaling factors according to
the percentage of the computing and communication times, and according to the
\section*{Acknowledgment}
-This work has been partially supported by the Labex
-ACTION project (contract ``ANR-11-LABX-01-01''). As a PhD student,
-Mr. Ahmed Fanfakh, would like to thank the University of
-Babylon (Iraq) for supporting his work.
-
+This work has been partially supported by the Labex ACTION project (contract
+``ANR-11-LABX-01-01''). Computations have been performed on the supercomputer
+facilities of the Mésocentre de calcul de Franche-Comté. As a PhD student,
+Mr. Ahmed Fanfakh, would like to thank the University of Babylon (Iraq) for
+supporting his work.
% trigger a \newpage just before the given reference
% number - used to balance the columns on the last page
