\usepackage{listings}
\usepackage{colortbl}
\usepackage{amsmath}
-% \usepackage{sectsty}
-% \usepackage{titlesec}
-% \usepackage{secdot}
-%\usepackage[font={footnotesize,bt}]{caption}
-%\usepackage[font=scriptsize,labelfont=bf]{caption}
+
+\usepackage[autolanguage,np]{numprint}
+\renewcommand*\npunitcommand[1]{\text{#1}}
+
\usepackage{xspace}
\usepackage[textsize=footnotesize]{todonotes}
\newcommand{\AG}[2][inline]{\todo[color=green!50,#1]{\sffamily\textbf{AG:} #2}\xspace}
Complete affiliation, add an email address, etc.}
\begin{abstract}
-The important technique for energy reduction of parallel systems is CPU frequency
-scaling. This operation used by many researchers to reduce energy consumption in many
-ways. Frequency scaling operation also has big impact on the performance. In some cases,
-the performance degradation ratio is bigger than energy saving ratio when the frequency scaled
-to down level. Therefore, the trade offs between the energy and performance becomes more
-important topic when using this technique. In this paper we developed an algorithm that
-select the frequency scaling factor for both energy and performance simultaneously.
-This algorithm takes into account the communication times when selecting the frequency scaling
-factor. It is works online without training or profiling to have very small overhead.
-The algorithm has better energy-performance trade offs compared to other methods.
+ The important technique for energy reduction of parallel systems is CPU
+ frequency scaling. This operation is used by many researchers to reduce energy
+ consumption in many ways. Frequency scaling operation also has a big impact on
+ the performances. In some cases, the performance degradation ratio is bigger
+ than energy saving ratio when the frequency is scaled to low level. Therefore,
+ the trade offs between the energy and performance becomes more important topic
+ when using this technique. In this paper we developed an algorithm that select
+ the frequency scaling factor for both energy and performance simultaneously.
+ This algorithm takes into account the communication times when selecting the
+ frequency scaling factor. It works online without training or profiling to
+ have a very small overhead. The algorithm has better energy-performance trade
+ offs compared to other methods.
\end{abstract}
\section{Introduction}
benchmarks (NPB v3.3) developed by NASA~\cite{44}. Our experiments are executed
using the simulator SimGrid/SMPI v3.10~\cite{Casanova:2008:SGF:1397760.1398183}
over an homogeneous distributed memory architecture. Furthermore, we compare the
-proposed algorithm with Rauber and R\"{u}nger methods~\cite{3}.
+proposed algorithm with Rauber and Rünger methods~\cite{3}.
The comparison's results show that our
algorithm gives better energy-time trade off.
-This paper is organized as follows: Section~\ref{sec.relwork} presents the works from other authors.
-Section~\ref{sec.ptasks} shows the execution of parallel tasks and sources of idle times. Section~\ref{sec.energy} resumes the
-energy model of homogenous platform. Section~\ref{sec.mpip} evaluates the performance of MPI program.
-Section~\ref{sec.verif} verifies the performance prediction model. Section~\ref{sec.compet} presents
-the energy-performance trade offs objective function. Section~\ref{sec.optim} demonstrates the proposed
-energy-performance algorithm. Section~\ref{sec.expe} presents the results of our experiments.
-Section~\ref{sec.compare} shows the comparison results. Finally, we conclude in Section~\ref{sec.concl}.
+This paper is organized as follows: Section~\ref{sec.relwork} presents the works
+from other authors. Section~\ref{sec.ptasks} shows the execution of parallel
+tasks and sources of idle times. Section~\ref{sec.energy} resumes the energy
+model of homogeneous platform. Section~\ref{sec.mpip} evaluates the performance
+of MPI program. Section~\ref{sec.verif} verifies the performance prediction
+model. Section~\ref{sec.compet} presents the energy-performance trade offs
+objective function. Section~\ref{sec.optim} demonstrates the proposed
+energy-performance algorithm. Section~\ref{sec.expe} presents the results of our
+experiments. Section~\ref{sec.compare} shows the comparison results. Finally,
+we conclude in Section~\ref{sec.concl}.
\section{Related Works}
\label{sec.relwork}
The DVFS offline methods are static and are not executed during the runtime of
the program. Some approaches used heuristics to select the best DVFS state
-during the compilation phases as for example in Azevedo et al.~\cite{40}. They use
-dynamic voltage scaling (DVS) algorithm to choose the DVS setting when there are dependency points
-between tasks. While in~\cite{29}, Xie et al. used breadth-first search
-algorithm to do that. Their goal is to save energy with time limits. Another
-approach gathers and stores the runtime information for each DVFS state, then
-selects the suitable DVFS offline to optimize energy-time
-trade offs. As an example Rountree et al.~\cite{8}, use liner programming
+during the compilation phases as for example in Azevedo et al.~\cite{40}. They
+use dynamic voltage scaling (DVS) algorithm to choose the DVS setting when there
+are dependency points between tasks. While in~\cite{29}, Xie et al. used
+breadth-first search algorithm to do that. Their goal is to save energy with
+time limits. Another approach gathers and stores the runtime information for
+each DVFS state, then selects the suitable DVFS offline to optimize energy-time
+trade offs. As an example, Rountree et al.~\cite{8} use liner programming
algorithm, while in~\cite{38,34}, Cochran et al. use multi logistic regression
algorithm for the same goal. The offline study that shows the DVFS impact on the
-communication time of the MPI program is~\cite{17}, where Freeh et al. show that these
-times do not change when the frequency is scaled down.
+communication time of the MPI program is~\cite{17}, where Freeh et al. show that
+these times do not change when the frequency is scaled down.
\subsection{The online DVFS orientations}
-The objective of online DVFS orientations works is to dynamically compute and set the frequency of
-the CPU during the runtime of the program for saving energy. Estimating and
-predicting approaches for the energy-time trade offs are developed by Kimura, Peraza, Yu-Liang et al.
-~\cite{11,2,31}. These works select the best DVFS setting depending on the slack
-times. These times happen when the processors have to wait for data from other
-processors to compute their task. For example, during the synchronous
-communications that take place in MPI programs, some processors are
-idle. The optimal DVFS can be selected using learning methods. Therefore, in Dhiman, Hao Shen et al.
-~\cite{39,19} used machine learning to converge to the suitable DVFS
-configuration. Their learning algorithms take big time to converge when the
-number of available frequencies is high. Also, the communication sections of the MPI
-program can be used to save energy. In~\cite{1}, Lim et al. developed an
-algorithm that detects the communication sections and changes the frequency
-during these sections only. This approach changes the frequency many times
-because an iteration may contain more than one communication section. The domain
-of analytical modeling used for choosing the optimal frequency as inRauber and R\"{u}nger~\cite{3}. they
-developed an analytical mathematical model to determine the
-optimal frequency scaling factor for any number of concurrent tasks. They set the slowest task to maximum frequency for maintaining performance. In this paper we compare our algorithm with
-Rauber and R\"{u}nger model~\cite{3}, because their model can be used for any number of
-concurrent tasks for homogeneous platforms. The primary contributions of this paper are:
+The objective of the online DVFS orientations is to dynamically compute and set
+the frequency of the CPU for saving energy during the runtime of the
+programs. Estimating and predicting approaches for the energy-time trade offs
+are developed by Kimura, Peraza, Yu-Liang et al. ~\cite{11,2,31}. These works
+select the best DVFS setting depending on the slack times. These times happen
+when the processors have to wait for data from other processors to compute their
+task. For example, during the synchronous communications that take place in MPI
+programs, some processors are idle. The optimal DVFS can be selected using
+learning methods. Therefore, in Dhiman, Hao Shen et al. ~\cite{39,19} used
+machine learning to converge to the suitable DVFS configuration. Their learning
+algorithms take big time to converge when the number of available frequencies is
+high. Also, the communication sections of the MPI program can be used to save
+energy. In~\cite{1}, Lim et al. developed an algorithm that detects the
+communication sections and changes the frequency during these sections
+only. This approach changes the frequency many times because an iteration may
+contain more than one communication section. The domain of analytical modeling
+can also be used for choosing the optimal frequency as in Rauber and
+Rünger~\cite{3}. They developed an analytical mathematical model to determine
+the optimal frequency scaling factor for any number of concurrent tasks. They
+set the slowest task to maximum frequency for maintaining performance. In this
+paper we compare our algorithm with Rauber and Rünger model~\cite{3}, because
+their model can be used for any number of concurrent tasks for homogeneous
+platforms. The primary contributions of this paper are:
\begin{enumerate}
\item Selecting the frequency scaling factor for simultaneously optimizing energy and performance,
while taking into account the communication time.
\label{eq:s}
S = \frac{F_\textit{max}}{F_\textit{new}}
\end{equation}
-The value of the scale $S$ is greater than 1 when changing the frequency to
-any new frequency value~(\emph {P-state}) in governor, the CPU governor is an interface
-driver supplied by the operating system kernel (e.g. Linux) to lowering core's frequency.
-The scaling factor is equal to 1 when the frequency set is to the maximum frequency.
-The energy consumption model for parallel homogeneous platform depends on the scaling factor \emph S. This factor reduces quadratically the dynamic power. Also, this factor increases the
-static energy linearly because the execution time is increased~\cite{36}. The
-energy model depending on the frequency scaling factor for homogeneous platform
-for any number of concurrent tasks was developed by Rauber and R\"{u}nger~\cite{3}. This model
-considers the two power metrics for measuring the energy of the parallel tasks as
-in EQ~(\ref{eq:energy}):
+The value of the scale $S$ is greater than 1 when changing the frequency to any
+new frequency value~(\emph {P-state}) in governor, the CPU governor is an
+interface driver supplied by the operating system kernel (e.g. Linux) to
+lowering core's frequency. The scaling factor is equal to 1 when the frequency
+set is to the maximum frequency. The energy consumption model for parallel
+homogeneous platform depends on the scaling factor \emph S. This factor reduces
+quadratically the dynamic power. Also, this factor increases the static energy
+linearly because the execution time is increased~\cite{36}. The energy model
+depending on the frequency scaling factor for homogeneous platform for any
+number of concurrent tasks was developed by Rauber and Rünger~\cite{3}. This
+model considers the two power metrics for measuring the energy of the parallel
+tasks as in EQ~(\ref{eq:energy}):
\begin{equation}
\label{eq:energy}
= \frac{F_\textit{max}}{F_\textit{new}} \cdot \frac{T_1}{T_i}
\end{equation}
where $F$ is the number of available frequencies. In this paper we depend on
-Rauber and R\"{u}nger energy model EQ~(\ref{eq:energy}) for two reasons: (1)-this model is used
-for homogeneous platform that we work on in this paper. 2-we compare our
-algorithm with Rauber and R\"{u}nger scaling model. Rauber and R\"{u}nger scaling factor that reduce
- energy consumption derived from the EQ~(\ref{eq:energy}). They take the
-derivation for this equation (to be minimized) and set it to zero to produce the
-scaling factor as in EQ~(\ref{eq:sopt}).
+Rauber and Rünger energy model EQ~(\ref{eq:energy}) for two reasons: (1) this
+model is used for homogeneous platform that we work on in this paper, and (2) we
+compare our algorithm with Rauber and Rünger scaling model. Rauber and Rünger
+scaling factor that reduce energy consumption derived from the
+EQ~(\ref{eq:energy}). They take the derivation for this equation (to be
+minimized) and set it to zero to produce the scaling factor as in
+EQ~(\ref{eq:sopt}).
\begin{equation}
\label{eq:sopt}
S_\textit{opt} = \sqrt[3]{\frac{2}{n} \cdot \frac{P_\textit{dyn}}{P_\textit{static}} \cdot
sending or receiving till the message is synchronously sent or received. In this
paper we predict the execution time of the program for any new scaling factor
value. Depending on this prediction we can produce our energy-performance scaling
-method as we will show in the coming sections. In the next section we make an
+method as we will show in the coming sections. In the next section we make to finishan
investigation study for the EQ~(\ref{eq:tnew}).
\section{Performance Prediction Verification}
static power values stored in a data file. Moreover, this function works in
optimal way when the energy function has a convex form with frequency scaling
factor as shown in~\cite{15,3,19}. Energy measurement model is not the
-objective of this paper and we choose Rauber and R\"{u}nger model as an example with two
+objective of this paper and we choose Rauber and Rünger model as an example with two
reasons that mentioned before.
\section{Optimal Scaling Factor for Performance and Energy}
\caption{Platform File Parameters}
% title of Table
\centering
- \begin{tabular}{ | l | l | l |l | l |l |l | p{2cm} |}
+ \begin{tabular}{|*{7}{l|}}
\hline
Max & Min & Backbone & Backbone&Link &Link& Sharing \\
Freq. & Freq. & Bandwidth & Latency & Bandwidth& Latency&Policy \\ \hline
- 2.5 &800 & 2.25 GBps &$5\times 10^{-7} s$& 1 GBps & $5\times 10^{-5} s$ &Full \\
+ \np{2.5} & \np{800} & \np[GBps]{2.25} &\np[$\mu$s]{0.5}& \np[GBps]{1} & \np[$\mu$s]{50} &Full \\
GHz& MHz& & & & &Duplex \\\hline
\end{tabular}
\label{table:platform}
for each MPI program. When there are little or not communications, the inversed
performance curve is very close to the energy curve. Then the distance between
the two curves is very small. This lead to small energy savings. The opposite
-happens when there are a lot of communication, the distance between the two
+happens when there are a lot of communication, theto finish distance between the two
curves is big. This lead to more energy savings (e.g. CG and FT), see
table~(\ref{table:factors results}). All discovered frequency scaling factors
optimize both the energy and the performance simultaneously for all the NAS
\label{fig:nas}
\end{figure*}
\begin{table}[htb]
- \caption{Optimal Scaling Factors Results}
+ \caption{The EPSA Scaling Factors Results}
% title of Table
\centering
- \AG{Use the same number of decimals for all numbers in a column,
- and vertically align the numbers along the decimal points.
- The same for all the following tables.}
- \begin{tabular}{ | l | l | l |l | r |}
+ \begin{tabular}{|l|*{4}{r|}}
\hline
Program & Optimal & Energy & Performance&Energy-Perf.\\
Name & Scaling Factor& Saving \%&Degradation \% &Distance \\ \hline
\section{Comparing Results}
\label{sec.compare}
-In this section, we compare our EPSA algorithm results with Rauber and R\"{u}nger
+In this section, we compare our EPSA algorithm results with Rauber and Rünger
methods~\cite{3}. He had two scenarios, the first is to reduce energy to optimal
level without considering the performance as in EQ~(\ref{eq:sopt}). We refer to
this scenario as $R_{E}$. The second scenario is similar to the first
to keep the performance from degradation as mush as possible. We refer to this
scenario as $R_{E-P}$. The comparison is made in tables~(\ref{table:compare
Class A},\ref{table:compare Class B},\ref{table:compare Class C}). These
-tables show the results of our EPSA and Rauber and R\"{u}nger scenarios for all the NAS
+tables show the results of our EPSA and Rauber and Rünger scenarios for all the NAS
benchmarks programs for classes A,B and C.
\begin{table}[p]
\caption{Comparing Results for The NAS Class A}
% title of Table
\centering
- \begin{tabular}{ | l | l | l |l | l | r| }
+ \begin{tabular}{|l|l|*{4}{r|}}
\hline
Method&Program&Factor& Energy& Performance &Energy-Perf.\\
Name &Name&Value& Saving \%&Degradation \% &Distance
\caption{Comparing Results for The NAS Class B}
% title of Table
\centering
- \begin{tabular}{ | l | l | l |l | l |r| }
+ \begin{tabular}{|l|l|*{4}{r|}}
\hline
Method&Program&Factor& Energy& Performance &Energy-Perf.\\
Name &Name&Value& Saving \%&Degradation \% &Distance
\caption{Comparing Results for The NAS Class C}
% title of Table
\centering
- \begin{tabular}{ | l | l | l |l | l |r| }
+ \begin{tabular}{|l|l|*{4}{r|}}
\hline
Method&Program&Factor& Energy& Performance &Energy-Perf.\\
Name &Name&Value& Saving \%&Degradation \% &Distance
such as Rauber's scaling factor EQ~(\ref{eq:sopt}), but it is optimal for both
the energy and the performance simultaneously. Our $EPSA$ optimal scaling factors
has better simultaneous optimization for both the energy and the performance
-compared to Rauber and R\"{u}nger energy-performance method ($R_{E-P}$). Also, in
+compared to Rauber and Rünger energy-performance method ($R_{E-P}$). Also, in
($R_{E-P}$) method when setting the frequency to maximum value for the
slower task lead to a small improvement of the performance. Also the results
show that this method keep or improve energy saving. Because of the energy
Figure~(\ref{fig:compare}) shows the maximum distance between the energy saving
percent and the performance degradation percent. Therefore, this means it is the
same resultant of our objective function EQ~(\ref{eq:max}). Our algorithm always
-gives positive energy to performance trade offs while Rauber and R\"{u}nger method
+gives positive energy to performance trade offs while Rauber and Rünger method
($R_{E-P}$) gives in some time negative trade offs such as in BT and
EP. The positive trade offs with highest values lead to maximum energy savings
concatenating with less performance degradation and this the objective of this
\includegraphics[width=.33\textwidth]{compare_class_A.pdf}
\includegraphics[width=.33\textwidth]{compare_class_B.pdf}
\includegraphics[width=.33\textwidth]{compare_class_c.pdf}
- \caption{Comparing Our EPSA with Rauber and R\"{u}nger Methods}
+ \caption{Comparing Our EPSA with Rauber and Rünger Methods}
\label{fig:compare}
\end{figure}
-
\section{Conclusion}
\label{sec.concl}
-
-\AG{the conclusion needs to be written\dots{} one day}
+In this paper we develop the simultaneous energy-performance algorithm. It is works based on the trade off relation between the energy and performance. The results showed that when the scaling factor is big value leads to more energy saving. Also, it show that when the the scaling factor is small value leads to the fact that the scaling factor has bigger impact on performance than energy. Then the algorithm optimize the energy saving and performance in the same time to have positive trade off. The optimal trade off refer to maximum distance between the energy and the inversed performance curves. Also, the results explained when setting the slowest task to maximum frequency usually not have a big improvement on performance.
\section*{Acknowledgment}
\AG{Right?}
Computations have been performed on the supercomputer facilities of the
Mésocentre de calcul de Franche-Comté.
+As a PhD student, M. Ahmed Fanfakh, would like to thank the University of
+Babylon (Iraq) for supporting his scholarship program that allows him to work on
+this paper.
+\AG{What about simply: ``[...] for supporting his work.''}
% trigger a \newpage just before the given reference
% number - used to balance the columns on the last page
%%% ispell-local-dictionary: "american"
%%% End:
-% LocalWords: Badri Charr FIXME Tianhe DVFS HPC NAS NPB SMPI Rauber's Rauber
-% LocalWords: CMOS EQ $$EPSA$$ Franche Comté Tflop
+% LocalWords: Fanfakh Charr FIXME Tianhe DVFS HPC NAS NPB SMPI Rauber's Rauber
+% LocalWords: CMOS EQ EPSA Franche Comté Tflop Rünger
