\newcommand{\MaxDist}{\mathit{Max}\Dist}
\newcommand{\MinTcm}{\mathit{Min}\Tcm}
\newcommand{\Ntrans}{\Xsub{N}{trans}}
+\newcommand{\Pd}{\Xsub{P}{d}}
\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{\TcpOld}{\Xsub{T}{cpOld}}
\newcommand{\Tnew}{\Xsub{T}{New}}
-%\newcommand{\Tnorm}{\Xsub{T}{Norm}}
\newcommand{\Told}{\Xsub{T}{Old}}
\begin{document}
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.
\If{(not the first frequency)}
\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 $\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)}
\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 $\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)$}
\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
