\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{\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{\Pd}[1][]{\Xsub{P}{d}_{\fxheight{#1}}}
\newcommand{\PdNew}{\Xsub{P}{dNew}}
\newcommand{\PdOld}{\Xsub{P}{dOld}}
-%\newcommand{\Pdyn}{\Xsub{P}{dyn}}
-\newcommand{\Pd}{\Xsub{P}{d}}
-%\newcommand{\PnormInv}{\Xsub{P}{NormInv}}
\newcommand{\Pnorm}{\Xsub{P}{Norm}}
-%\newcommand{\Pstates}{\Xsub{P}{states}}
-%\newcommand{\Pstatic}{\Xsub{P}{static}}
-\newcommand{\Ps}{\Xsub{P}{s}}
-\newcommand{\Scp}{\Xsub{S}{cp}}
-\newcommand{\Sopt}{\Xsub{S}{opt}}
-\newcommand{\Tcm}{\Xsub{T}{cm}}
-%\newcommand{\Tcomp}{\Xsub{T}{comp}}
-\newcommand{\TcpOld}{\Xsub{T}{cpOld}}
-\newcommand{\Tcp}{\Xsub{T}{cp}}
-%\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{\Tnorm}{\Xsub{T}{Norm}}
\newcommand{\Told}{\Xsub{T}{Old}}
\begin{document}
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
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.
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}
- \MinTcm = \min_{i=1,2,\dots,N} (\Tcm_i)
+ \MinTcm = \min_{i=1,2,\dots,N} (\Tcm[i])
\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
\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
-$\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
-$\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
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}
\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}
\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}).
\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}
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$
-and the computation scaling factor $\Scp_i$ as follows:
+and the computation scaling factor $\Scp[i]$ as follows:
\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
% \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}
- \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 $F_i \gets F_i+\Fdiff_i,~i=1,\dots,N.$
+ \State $F_i \gets F_i+\Fdiff[i],~i=1,\dots,N.$
\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 $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
- \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 $\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 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}
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.
\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
- 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
- 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
- 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
- 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}
\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
\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}
-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
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
