X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/mpi-energy2.git/blobdiff_plain/93836a322514b561c0e5f2c9a2fcdf584617852e..d9b19f4d196a6480adf6a68b1e39d6eca733b6b0:/Heter_paper.tex?ds=sidebyside

diff --git a/Heter_paper.tex b/Heter_paper.tex
index 5d28377..630c7fe 100644
--- a/Heter_paper.tex
+++ b/Heter_paper.tex
@@ -8,7 +8,6 @@
 \usepackage{algorithm}
 \usepackage{subfig}
 \usepackage{amsmath}
-\usepackage{multirow}
 \usepackage{url}
 \DeclareUrlCommand\email{\urlstyle{same}}
 
@@ -24,44 +23,53 @@
 \newcommand{\JC}[2][inline]{%
   \todo[color=red!10,#1]{\sffamily\textbf{JC:} #2}\xspace}
 
-\newcommand{\Xsub}[2]{\ensuremath{#1_\textit{#2}}}
+\newcommand{\Xsub}[2]{{\ensuremath{#1_\mathit{#2}}}}
 
-\newcommand{\Dist}{\textit{Dist}}
+%% 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{\Eind}{\Xsub{E}{ind}}
 \newcommand{\Enorm}{\Xsub{E}{Norm}}
 \newcommand{\Eoriginal}{\Xsub{E}{Original}}
 \newcommand{\Ereduced}{\Xsub{E}{Reduced}}
-\newcommand{\Fdiff}{\Xsub{F}{diff}}
-\newcommand{\Fmax}{\Xsub{F}{max}}
+\newcommand{\Es}{\Xsub{E}{S}}
+\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}{\textit{Max Dist}}
+\newcommand{\MaxDist}{\mathit{Max}\Dist}
+\newcommand{\MinTcm}{\mathit{Min}\Tcm}
 \newcommand{\Ntrans}{\Xsub{N}{trans}}
-\newcommand{\Pdyn}{\Xsub{P}{dyn}}
-\newcommand{\PnormInv}{\Xsub{P}{NormInv}}
+\newcommand{\Pd}[1][]{\Xsub{P}{d}_{\fxheight{#1}}}
+\newcommand{\PdNew}{\Xsub{P}{dNew}}
+\newcommand{\PdOld}{\Xsub{P}{dOld}}
 \newcommand{\Pnorm}{\Xsub{P}{Norm}}
-\newcommand{\Tnorm}{\Xsub{T}{Norm}}
-\newcommand{\Pstates}{\Xsub{P}{states}}
-\newcommand{\Pstatic}{\Xsub{P}{static}}
-\newcommand{\Sopt}{\Xsub{S}{opt}}
-\newcommand{\Tcomp}{\Xsub{T}{comp}}
-\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{\Told}{\Xsub{T}{Old}} 
-\begin{document} 
+\newcommand{\Told}{\Xsub{T}{Old}}
+
+\begin{document}
 
-\title{Energy Consumption Reduction for Message Passing Iterative  Applications in Heterogeneous Architecture Using DVFS}
- 
-\author{% 
+\title{Energy Consumption Reduction for \\
+  Message Passing Iterative Applications on \\
+  Heterogeneous Architectures Using DVFS}
+
+\author{%
   \IEEEauthorblockN{%
     Jean-Claude Charr,
     RaphaÃ«l Couturier,
     Ahmed Fanfakh and
     Arnaud Giersch
-  } 
+  }
   \IEEEauthorblockA{%
     FEMTO-ST Institute, University of Franche-Comte\\
     IUT de Belfort-MontbÃ©liard,
@@ -75,151 +83,174 @@
 \maketitle
 
 \begin{abstract}
-Computing platforms  are consuming  more and more  energy due to  the increasing
-number  of nodes  composing  them.  To  minimize  the operating  costs of  these
-platforms many techniques have been  used. Dynamic voltage and frequency scaling
-(DVFS) is  one of them. It  reduces the frequency of  a CPU to  lower its energy
-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
-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 35\% 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.
+  Computing platforms are consuming more and more energy due to the increasing
+  number of nodes composing them.  To minimize the operating costs of these
+  platforms many techniques have been used. Dynamic voltage and frequency
+  scaling (DVFS) is one of them. It reduces the frequency of a CPU to lower its
+  energy 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 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 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
+  degradation as much as possible.  Finally, the algorithm is compared to an
+  existing method, the comparison results showing that it outperforms the
+  latter.
 
 \end{abstract}
 
 \section{Introduction}
 \label{sec.intro}
-The  need for  more  computing  power is  continually  increasing. To  partially
-satisfy  this need,  most supercomputers  constructors just  put  more computing
-nodes in their  platform. The resulting platforms might  achieve higher floating
-point operations  per second  (FLOPS), but the  energy consumption and  the heat
-dissipation  are  also increased.   As  an  example,  the Chinese  supercomputer
-Tianhe-2 had  the highest FLOPS  in November 2014  according to the  Top500 list
-\cite{TOP500_Supercomputers_Sites}.  However, it was  also the most power hungry
-platform  with  its  over  3  million cores  consuming  around  17.8  megawatts.
-Moreover,    according   to    the    U.S.    annual    energy   outlook    2014
-\cite{U.S_Annual.Energy.Outlook.2014}, the  price of energy  for 1 megawatt-hour
+
+The need for more computing power is continually increasing. To partially
+satisfy this need, most supercomputers constructors just put more computing
+nodes in their platform. The resulting platforms might achieve higher floating
+point operations per second (FLOPS), but the energy consumption and the heat
+dissipation are also increased.  As an example, the Chinese supercomputer
+Tianhe-2 had the highest FLOPS in November 2014 according to the Top500 list
+\cite{TOP500_Supercomputers_Sites}.  However, it was also the most power hungry
+platform with its over 3 million cores consuming around 17.8 megawatts.
+Moreover, according to the U.S.  annual energy outlook 2014
+\cite{U.S_Annual.Energy.Outlook.2014}, the price of energy for 1 megawatt-hour
 was approximately equal to \$70.  Therefore, the price of the energy consumed by
-the Tianhe-2  platform is approximately more  than \$10 million  each year.  The
-computing platforms must  be more energy efficient and  offer the highest number
-of FLOPS  per watt  possible, such as  the L-CSC  from the GSI  Helmholtz Center
+the Tianhe-2 platform is approximately more than \$10 million each year.  The
+computing platforms must be more energy efficient and offer the highest number
+of FLOPS per watt possible, such as the L-CSC from the GSI Helmholtz Center
 which became the top of the Green500 list in November 2014 \cite{Green500_List}.
 This heterogeneous platform executes more than 5 GFLOPS per watt while consuming
 57.15 kilowatts.
 
-Besides platform  improvements, there are many software  and hardware techniques
-to lower  the energy consumption of  these platforms, such  as scheduling, DVFS,
-...   DVFS is  a  widely used  process to  reduce  the energy  consumption of  a
-processor            by             lowering            its            frequency
+Besides platform improvements, there are many software and hardware techniques
+to lower the energy consumption of these platforms, such as scheduling, DVFS,
+\dots{} DVFS is a widely used process to reduce the energy consumption of a
+processor by lowering its frequency
 \cite{Rizvandi_Some.Observations.on.Optimal.Frequency}. However, it also reduces
 the number of FLOPS executed by the processor which might increase the execution
 time of the application running over that processor.  Therefore, researchers use
-different optimization  strategies to select  the frequency that gives  the best
-trade-off  between the  energy reduction  and performance  degradation  ratio. In
-\cite{Our_first_paper}, a  frequency selecting algorithm was  proposed to reduce
-the energy  consumption of message  passing iterative applications  running over
-homogeneous platforms.  The results of  the experiments show  significant energy
-consumption  reductions. In  this  paper, a  new  frequency selecting  algorithm
-adapted  for heterogeneous  platform  is  presented. It  selects  the vector  of
-frequencies, for  a heterogeneous platform  running a message  passing iterative
+different optimization strategies to select the frequency that gives the best
+trade-off between the energy reduction and performance degradation ratio. In
+\cite{Our_first_paper}, a frequency selecting algorithm was proposed to reduce
+the energy consumption of message passing iterative applications running over
+homogeneous platforms.  The results of the experiments show significant energy
+consumption reductions. In this paper, a new frequency selecting algorithm
+adapted for heterogeneous platform is presented. It selects the vector of
+frequencies, for a heterogeneous platform running a message passing iterative
 application, that simultaneously tries to offer the maximum energy reduction and
-minimum performance degradation ratio. The  algorithm has a very small overhead,
+minimum performance degradation ratio. The algorithm has a very small overhead,
 works online and does not need any training or profiling.
 
 This paper is organized as follows: Section~\ref{sec.relwork} presents some
 related works from other authors.  Section~\ref{sec.exe} describes how the
-execution time of message passing programs can be predicted.  It also presents an energy
-model that predicts the energy consumption of an application running over a heterogeneous platform. Section~\ref{sec.compet} presents
-the energy-performance objective function that maximizes the reduction of energy
+execution time of message passing programs can be predicted.  It also presents
+an energy model that predicts the energy consumption of an application running
+over a heterogeneous platform. Section~\ref{sec.compet} presents the
+energy-performance objective function that maximizes the reduction of energy
 consumption while minimizing the degradation of the program's performance.
-Section~\ref{sec.optim} details the proposed frequency selecting algorithm then the precision of the proposed algorithm is verified. 
-Section~\ref{sec.expe} presents the results of applying the algorithm on  the NAS parallel benchmarks and executing them 
-on a heterogeneous platform. It shows the results of running three 
-different power scenarios and comparing them. Moreover, it also shows the comparison results
-between the proposed method and an existing method.
-Finally, in Section~\ref{sec.concl} the paper ends with a summary and some future works.
+Section~\ref{sec.optim} details the proposed frequency selecting algorithm then
+the precision of the proposed algorithm is verified.  Section~\ref{sec.expe}
+presents the results of applying the algorithm on the NAS parallel benchmarks
+and executing them on a heterogeneous platform. It shows the results of running
+three different power scenarios and comparing them. Moreover, it also shows the
+comparison results between the proposed method and an existing method.  Finally,
+in Section~\ref{sec.concl} the paper ends with a summary and some future works.
 
 \section{Related works}
 \label{sec.relwork}
+
 DVFS is a technique used in modern processors to scale down both the voltage and
-the  frequency  of the  CPU  while  computing, in  order  to  reduce the  energy
-consumption of  the processor. DVFS is also  allowed in  GPUs  to achieve the
-same goal. Reducing the frequency of  a processor lowers its number of FLOPS and
-might  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
-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  as
-~\cite{Hao_Learning.based.DVFS,Spiliopoulos_Green.governors.Adaptive.DVFS}. Others
-used  offline methods  that might  need to  run the  application and  profile it
-before       selecting       the        new       frequency,       such       as
-~\cite{Rountree_Bounding.energy.consumption.in.MPI,Cochran_Pack_and_Cap_Adaptive_DVFS}. The
-methods could  be heuristics, exact or  brute force methods  that satisfy varied
-objectives such as  energy reduction or performance. They  also could be adapted
-to  the  execution's  environment  and  the  type of  the  application  such  as
-sequential, parallel  or distributed architecture,  homogeneous or heterogeneous
-platform, synchronous or asynchronous application, ...
-
-In this paper, we are interested in reducing energy for message passing iterative synchronous applications running over heterogeneous platforms.
-Some works have already been done for such platforms and they can be classified into two types of heterogeneous platforms: 
+the frequency of the CPU while computing, in order to reduce the energy
+consumption of the processor. DVFS is also allowed in GPUs to achieve the same
+goal. Reducing the frequency of a processor lowers its number of FLOPS and might
+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
+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
+as~\cite{Hao_Learning.based.DVFS,Spiliopoulos_Green.governors.Adaptive.DVFS}.
+Others used offline methods that might need to run the application and profile
+it before selecting the new frequency, such
+as~\cite{Rountree_Bounding.energy.consumption.in.MPI,Cochran_Pack_and_Cap_Adaptive_DVFS}.
+The methods could be heuristics, exact or brute force methods that satisfy
+varied objectives such as energy reduction or performance. They also could be
+adapted to the execution's environment and the type of the application such as
+sequential, parallel or distributed architecture, homogeneous or heterogeneous
+platform, synchronous or asynchronous application, \dots{}
+
+In this paper, we are interested in reducing energy for message passing
+iterative synchronous applications running over heterogeneous platforms.  Some
+works have already been done for such platforms and they can be classified into
+two types of heterogeneous platforms:
 \begin{itemize}
-
 \item the platform is composed of homogeneous GPUs and homogeneous CPUs.
 \item the platform is only composed of heterogeneous CPUs.
-
 \end{itemize}
 
-For the first type of platform, the computing intensive parallel tasks are executed on the  GPUs and the rest are executed 
-on the CPUs.  Luley et al.
-~\cite{Luley_Energy.efficiency.evaluation.and.benchmarking}, proposed  a heterogeneous 
-cluster composed of Intel Xeon CPUs and NVIDIA GPUs. Their main goal was to maximize the 
-energy efficiency of the platform during computation by maximizing the number of FLOPS per watt generated. 
-In~\cite{KaiMa_Holistic.Approach.to.Energy.Efficiency.in.GPU-CPU}, Kai Ma et al. developed a scheduling 
-algorithm that distributes  workloads proportional to the computing power of the nodes which could be a GPU or a CPU. All the tasks must be completed at the same time.
-In~\cite{Rong_Effects.of.DVFS.on.K20.GPU}, Rong et al. showed that 
-a heterogeneous (GPUs and CPUs) cluster that enables DVFS gave better energy and performance 
-efficiency than other clusters only composed of  CPUs.
- 
-The work presented in this paper concerns the second type of platform, with 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 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.
-In~\cite{Shelepov_Scheduling.on.Heterogeneous.Multicore} and \cite{Li_Minimizing.Energy.Consumption.for.Frame.Based.Tasks}, 
- the best frequencies for a specified heterogeneous cluster are selected offline using some 
-heuristic. Chen et al.~\cite{Chen_DVFS.under.quality.of.service.requirements} used a greedy dynamic programming approach to  
-minimize the power consumption of heterogeneous servers  while respecting given time constraints. This approach 
-had considerable overhead.
-In contrast to the above described papers, this paper presents the following contributions :
+For the first type of platform, the computing intensive parallel tasks are
+executed on the GPUs and the rest are executed on the CPUs.  Luley et
+al.~\cite{Luley_Energy.efficiency.evaluation.and.benchmarking}, proposed a
+heterogeneous cluster composed of Intel Xeon CPUs and NVIDIA GPUs. Their main
+goal was to maximize the energy efficiency of the platform during computation by
+maximizing the number of FLOPS per watt generated.
+In~\cite{KaiMa_Holistic.Approach.to.Energy.Efficiency.in.GPU-CPU}, Kai Ma et
+al. developed a scheduling algorithm that distributes workloads proportional to
+the computing power of the nodes which could be a GPU or a CPU. All the tasks
+must be completed at the same time.  In~\cite{Rong_Effects.of.DVFS.on.K20.GPU},
+Rong et al. showed that a heterogeneous (GPUs and CPUs) cluster that enables
+DVFS gave better energy and performance efficiency than other clusters only
+composed of CPUs.
+
+The work presented in this paper concerns the second type of platform, with
+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 $\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 \np[\%]{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.
+In~\cite{Shelepov_Scheduling.on.Heterogeneous.Multicore} and
+\cite{Li_Minimizing.Energy.Consumption.for.Frame.Based.Tasks}, the best
+frequencies for a specified heterogeneous cluster are selected offline using
+some heuristic.  Chen et
+al.~\cite{Chen_DVFS.under.quality.of.service.requirements} used a greedy dynamic
+programming approach to minimize the power consumption of heterogeneous servers
+while respecting given time constraints.  This approach had considerable
+overhead.  In contrast to the above described papers, this paper presents the
+following contributions :
 \begin{enumerate}
-\item  two new energy and performance models for message passing iterative synchronous applications running over 
-       a heterogeneous platform. Both models take into account  communication and slack times. The models can predict the required energy and the execution time of the application.
-       
-\item a new online frequency selecting algorithm for heterogeneous platforms. The algorithm has a very small 
-      overhead and does not need any training or profiling. It uses a new optimization function which simultaneously maximizes the performance and minimizes the energy consumption of a message passing iterative synchronous application.
-      
+\item two new energy and performance models for message passing iterative
+  synchronous applications running over a heterogeneous platform. Both models
+  take into account communication and slack times. The models can predict the
+  required energy and the execution time of the application.
+
+\item a new online frequency selecting algorithm for heterogeneous
+  platforms. The algorithm has a very small overhead and does not need any
+  training or profiling. It uses a new optimization function which
+  simultaneously maximizes the performance and minimizes the energy consumption
+  of a message passing iterative synchronous application.
+
 \end{enumerate}
 
 \section{The performance and energy consumption measurements on heterogeneous architecture}
 \label{sec.exe}
 
-
-
-\subsection{The execution time of message passing distributed 
-                iterative applications on a heterogeneous platform}
+\subsection{The execution time of message passing distributed iterative
+  applications on a heterogeneous platform}
 
 In this paper, we are interested in reducing the energy consumption of message
 passing distributed iterative synchronous applications running over
@@ -229,44 +260,44 @@ network. Therefore, each node has different characteristics such as computing
 power (FLOPS), energy consumption, CPU's frequency range, \dots{} but they all
 have the same network bandwidth and latency.
 
-The overall execution time  of a distributed iterative synchronous application 
-over a heterogeneous platform  consists of the sum of the computation time and 
-the communication time for every iteration on a node. However, due to the 
-heterogeneous computation power of the computing nodes, slack times might occur 
-when fast nodes have to  wait, during synchronous communications, for  the slower 
-nodes to finish  their computations (see Figure~(\ref{fig:heter})). 
-Therefore,  the overall execution time  of the program is the execution time of the slowest
-task which has the highest computation time and no slack time.
-  
- \begin{figure}[!t]
+\begin{figure}[!t]
   \centering
-   \includegraphics[scale=0.6]{fig/commtasks}
+  \includegraphics[scale=0.6]{fig/commtasks}
   \caption{Parallel tasks on a heterogeneous platform}
   \label{fig:heter}
 \end{figure}
 
-Dynamic Voltage and Frequency Scaling (DVFS) is a process, implemented in 
-modern processors, that reduces the energy consumption of a CPU by scaling 
-down its voltage and frequency.  Since DVFS lowers the frequency of a CPU 
-and consequently its computing power, the execution time of a program running 
-over that scaled down processor might increase, especially if the program is 
-compute bound.  The frequency reduction process can be  expressed by the scaling 
-factor S which is the ratio between  the maximum and the new frequency of a CPU 
+The overall execution time of a distributed iterative synchronous application
+over a heterogeneous platform consists of the sum of the computation time and
+the communication time for every iteration on a node. However, due to the
+heterogeneous computation power of the computing nodes, slack times might occur
+when fast nodes have to wait, during synchronous communications, for the slower
+nodes to finish their computations (see Figure~\ref{fig:heter}).  Therefore, the
+overall execution time of the program is the execution time of the slowest task
+which has the highest computation time and no slack time.
+
+Dynamic Voltage and Frequency Scaling (DVFS) is a process, implemented in
+modern processors, that reduces the energy consumption of a CPU by scaling
+down its voltage and frequency.  Since DVFS lowers the frequency of a CPU
+and consequently its computing power, the execution time of a program running
+over that scaled down processor might increase, especially if the program is
+compute bound.  The frequency reduction process can be  expressed by the scaling
+factor S which is the ratio between  the maximum and the new frequency of a CPU
 as in (\ref{eq:s}).
 \begin{equation}
   \label{eq:s}
- S = \frac{F_\textit{max}}{F_\textit{new}}
+  S = \frac{\Fmax}{\Fnew}
 \end{equation}
- The execution time of a compute bound sequential program is linearly proportional 
- to the frequency scaling factor $S$.  On the other hand,  message passing 
- distributed applications consist of two parts: computation and communication. 
- The execution time of the computation part is linearly proportional to the 
- frequency scaling factor $S$ but  the communication time is not affected by the 
- scaling factor because  the processors involved remain idle during the  
- communications~\cite{Freeh_Exploring.the.Energy.Time.Tradeoff}. 
- The communication time for a task is the summation of  periods of 
- time that begin with an MPI call for sending or receiving   a message 
- until the message is synchronously sent or received.
+The execution time of a compute bound sequential program is linearly
+proportional to the frequency scaling factor $S$.  On the other hand, message
+passing distributed applications consist of two parts: computation and
+communication.  The execution time of the computation part is linearly
+proportional to the frequency scaling factor $S$ but the communication time is
+not affected by the scaling factor because the processors involved remain idle
+during the communications~\cite{Freeh_Exploring.the.Energy.Time.Tradeoff}.  The
+communication time for a task is the summation of periods of time that begin
+with an MPI call for sending or receiving a message until the message is
+synchronously sent or received.
 
 Since in a heterogeneous platform each node has different characteristics,
 especially different frequency gears, when applying DVFS operations on these
@@ -280,364 +311,288 @@ operation. Then the execution time for one iteration of the application with any
 vector of scaling factors can be predicted using (\ref{eq:perf}).
 \begin{equation}
   \label{eq:perf}
- \textit  T_\textit{new} = 
- \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)
+  \label{eq:perf2}
+  \MinTcm = \min_{i=1,2,\dots,N} (\Tcm[i])
 \end{equation}
-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
-node. It means only the communication  time without any slack time is taken into
+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
+node. It means only the communication time without any slack time is taken into
 account.  Therefore, the execution time of the iterative application is equal to
-the  execution time of  one iteration  as in  (\ref{eq:perf}) multiplied  by the
+the execution time of one iteration as in (\ref{eq:perf}) multiplied by the
 number of iterations of that application.
 
-This prediction model is developed from  the model to predict the execution time
-of     message    passing     distributed    applications     for    homogeneous
-architectures~\cite{Our_first_paper}.   The execution  time prediction  model is
-used in  the method  to optimize both the energy consumption and the performance of
-iterative methods, which is presented in the following sections.
-
+This prediction model is developed from the model to predict the execution time
+of message passing distributed applications for homogeneous
+architectures~\cite{Our_first_paper}.  The execution time prediction model is
+used in the method to optimize both the energy consumption and the performance
+of iterative methods, which is presented in the following sections.
 
 \subsection{Energy model for heterogeneous platform}
+
 Many researchers~\cite{Malkowski_energy.efficient.high.performance.computing,
-Rauber_Analytical.Modeling.for.Energy,Zhuo_Energy.efficient.Dynamic.Task.Scheduling,
-Rizvandi_Some.Observations.on.Optimal.Frequency} divide the power consumed by a processor into
-two power metrics: the static and the dynamic power.  While the first one is
-consumed as long as the computing unit is turned on, the latter is only consumed during
-computation times.  The dynamic power $Pd$ is related to the switching
-activity $\alpha$, load capacitance $C_L$, the supply voltage $V$ and
-operational frequency $F$, as shown in (\ref{eq:pd}).
+  Rauber_Analytical.Modeling.for.Energy,Zhuo_Energy.efficient.Dynamic.Task.Scheduling,
+  Rizvandi_Some.Observations.on.Optimal.Frequency} divide the power consumed by
+a processor into two power metrics: the static and the dynamic power.  While the
+first one is consumed as long as the computing unit is turned on, the latter is
+only consumed during computation times.  The dynamic power $\Pd$ is related to
+the switching activity $\alpha$, load capacitance $\CL$, the supply voltage $V$
+and operational frequency $F$, as shown in (\ref{eq:pd}).
 \begin{equation}
   \label{eq:pd}
-  Pd = \alpha \cdot C_L \cdot V^2 \cdot F
+  \Pd = \alpha \cdot \CL \cdot V^2 \cdot F
 \end{equation}
-The static power $Ps$ captures the leakage power as follows:
+The static power $\Ps$ captures the leakage power as follows:
 \begin{equation}
   \label{eq:ps}
-   Ps  = V \cdot N_{trans} \cdot K_{design} \cdot I_{leak}
+   \Ps  = V \cdot \Ntrans \cdot \Kdesign \cdot \Ileak
 \end{equation}
-where V is the supply voltage, $N_{trans}$ is the number of transistors,
-$K_{design}$ is a design dependent parameter and $I_{leak}$ is a
+where V is the supply voltage, $\Ntrans$ is the number of transistors,
+$\Kdesign$ is a design dependent parameter and $\Ileak$ is a
 technology dependent parameter.  The energy consumed by an individual processor
 to execute a given program can be computed as:
 \begin{equation}
   \label{eq:eind}
-   E_\textit{ind} =  Pd \cdot Tcp + Ps \cdot T
+  \Eind =  \Pd \cdot \Tcp + \Ps \cdot T
 \end{equation}
-where $T$ is the execution time of the program, $Tcp$ is the computation
-time and $Tcp \le T$.  $Tcp$ may be equal to $T$ if there is no
+where $T$ is the execution time of the program, $\Tcp$ is the computation
+time and $\Tcp \le T$.  $\Tcp$ may be equal to $T$ if there is no
 communication and no slack time.
 
-The main objective of DVFS operation is to reduce the overall energy consumption~\cite{Le_DVFS.Laws.of.Diminishing.Returns}.  
-The operational frequency $F$ depends linearly on the supply voltage $V$, i.e., $V = \beta \cdot F$ with some
-constant $\beta$.~This equation is used to study the change of the dynamic
-voltage with respect to various frequency values in~\cite{Rauber_Analytical.Modeling.for.Energy}.  The reduction
-process of the frequency can be expressed by the scaling factor $S$ which is the
-ratio between the maximum and the new frequency as in (\ref{eq:s}).
-The CPU governors are power schemes supplied by the operating
-system's kernel to lower a core's frequency. The new frequency 
-$F_{new}$ from (\ref{eq:s}) can be calculated as follows:
+The main objective of DVFS operation is to reduce the overall energy
+consumption~\cite{Le_DVFS.Laws.of.Diminishing.Returns}.  The operational
+frequency $F$ depends linearly on the supply voltage $V$, i.e., $V = \beta \cdot
+F$ with some constant $\beta$.~This equation is used to study the change of the
+dynamic voltage with respect to various frequency values
+in~\cite{Rauber_Analytical.Modeling.for.Energy}.  The reduction process of the
+frequency can be expressed by the scaling factor $S$ which is the ratio between
+the maximum and the new frequency as in (\ref{eq:s}).  The CPU governors are
+power schemes supplied by the operating system's kernel to lower a core's
+frequency. The new frequency $\Fnew$ from (\ref{eq:s}) can be calculated as
+follows:
 \begin{equation}
   \label{eq:fnew}
-   F_\textit{new} = S^{-1} \cdot F_\textit{max}
+   \Fnew = S^{-1} \cdot \Fmax
 \end{equation}
-Replacing $F_{new}$ in (\ref{eq:pd}) as in (\ref{eq:fnew}) gives the following 
+Replacing $\Fnew$ in (\ref{eq:pd}) as in (\ref{eq:fnew}) gives the following
 equation for dynamic power consumption:
 \begin{multline}
   \label{eq:pdnew}
-   {P}_\textit{dNew} = \alpha \cdot C_L \cdot V^2 \cdot F_{new} = \alpha \cdot C_L \cdot \beta^2 \cdot F_{new}^3 \\
-   {} = \alpha \cdot C_L \cdot V^2 \cdot F_{max} \cdot S^{-3} = P_{dOld} \cdot S^{-3}
+   \PdNew = \alpha \cdot \CL \cdot V^2 \cdot \Fnew = \alpha \cdot \CL \cdot \beta^2 \cdot \Fnew^3 \\
+   {} = \alpha \cdot \CL \cdot V^2 \cdot \Fmax \cdot S^{-3} = \PdOld \cdot S^{-3}
 \end{multline}
-where $ {P}_\textit{dNew}$  and $P_{dOld}$ are the  dynamic power consumed with the 
+where $\PdNew$  and $\PdOld$ are the  dynamic power consumed with the
 new frequency and the maximum frequency respectively.
 
-According to (\ref{eq:pdnew}) the dynamic power is reduced by a factor of $S^{-3}$ when 
-reducing the frequency by a factor of $S$~\cite{Rauber_Analytical.Modeling.for.Energy}. Since the FLOPS of a CPU is proportional 
-to the frequency of a CPU, the computation time is increased proportionally to $S$.  
-The new dynamic energy is the  dynamic power multiplied by the new time of computation 
-and is given by the following equation:
+According to (\ref{eq:pdnew}) the dynamic power is reduced by a factor of
+$S^{-3}$ when reducing the frequency by a factor of
+$S$~\cite{Rauber_Analytical.Modeling.for.Energy}. Since the FLOPS of a CPU is
+proportional to the frequency of a CPU, the computation time is increased
+proportionally to $S$.  The new dynamic energy is the dynamic power multiplied
+by the new time of computation and is given by the following equation:
 \begin{equation}
   \label{eq:Edyn}
-   E_\textit{dNew} = P_{dOld} \cdot S^{-3} \cdot (Tcp \cdot S)= S^{-2}\cdot P_{dOld} \cdot  Tcp 
+   \EdNew = \PdOld \cdot S^{-3} \cdot (\Tcp \cdot S)= S^{-2}\cdot \PdOld \cdot  \Tcp
 \end{equation}
-The static power is related to the power leakage of the CPU and is consumed during computation 
-and even when idle. As in~\cite{Rauber_Analytical.Modeling.for.Energy,Zhuo_Energy.efficient.Dynamic.Task.Scheduling}, 
- the static power of a processor is considered as constant 
-during idle and computation periods, and for all its available frequencies. 
-The static energy is the static power multiplied by the execution time of the program. 
-According to the execution time model in (\ref{eq:perf}), the execution time of the program 
-is the sum of the computation and the communication times. The computation time is linearly related  
-to the frequency scaling factor, while this scaling factor does not affect the communication time. 
-The static energy of a processor after scaling its frequency is computed as follows: 
+The static power is related to the power leakage of the CPU and is consumed
+during computation and even when idle. As
+in~\cite{Rauber_Analytical.Modeling.for.Energy,Zhuo_Energy.efficient.Dynamic.Task.Scheduling},
+the static power of a processor is considered as constant during idle and
+computation periods, and for all its available frequencies.  The static energy
+is the static power multiplied by the execution time of the program.  According
+to the execution time model in (\ref{eq:perf}), the execution time of the
+program is the sum of the computation and the communication times. The
+computation time is linearly related to the frequency scaling factor, while this
+scaling factor does not affect the communication time.  The static energy of a
+processor after scaling its frequency is computed as follows:
 \begin{equation}
   \label{eq:Estatic}
- E_\textit{s} = Ps \cdot (Tcp \cdot S  + Tcm)
+  \Es = \Ps \cdot (\Tcp \cdot S  + \Tcm)
 \end{equation}
 
-In  the  considered  heterogeneous  platform,  each  processor  $i$  might  have
-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
-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
-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
-(\ref{eq:Edyn}), the static energy is computed  as the sum of the execution time
-of  one iteration multiplied  by the static  power of  each processor.   The overall
-energy consumption of a message  passing distributed application executed over a
-heterogeneous platform during one iteration  is the summation of all dynamic and
+In the considered heterogeneous platform, each processor $i$ might have
+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
+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 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
+(\ref{eq:Edyn}), the static energy is computed as the sum of the execution time
+of one iteration multiplied by the static power of each processor.  The overall
+energy consumption of a message passing distributed application executed over a
+heterogeneous platform during one iteration is the summation of all dynamic and
 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}) +
-  {MinTcm))}
- \end{multline}
-
-Reducing the frequencies of the processors according to the vector of
-scaling factors $(S_1, S_2,\dots, S_N)$ may degrade the performance of the
-application and thus, increase the static energy because the execution time is
-increased~\cite{Kim_Leakage.Current.Moore.Law}. The overall energy consumption for the iterative 
-application can be measured by measuring  the energy consumption for one iteration as in (\ref{eq:energy}) 
-multiplied by the number of iterations of that application.
+ 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}
 
+Reducing the frequencies of the processors according to the vector of scaling
+factors $(S_1, S_2,\dots, S_N)$ may degrade the performance of the application
+and thus, increase the static energy because the execution time is
+increased~\cite{Kim_Leakage.Current.Moore.Law}. The overall energy consumption
+for the iterative application can be measured by measuring the energy
+consumption for one iteration as in (\ref{eq:energy}) multiplied by the number
+of iterations of that application.
 
 \section{Optimization of both energy consumption and performance}
 \label{sec.compet}
 
 Using the lowest frequency for each processor does not necessarily give the most
-energy efficient  execution of an  application. Indeed, even though  the dynamic
-power  is  reduced  while  scaling  down  the  frequency  of  a  processor,  its
-computation power  is proportionally decreased. Hence, the  execution time might
-be drastically  increased and  during that time,  dynamic and static  powers are
-being consumed.  Therefore,  it might cancel any gains  achieved by scaling down
-the frequency of all nodes to  the minimum and the overall energy consumption of
-the application might not  be the optimal one.  It is not  trivial to select the
-appropriate frequency  scaling factor for  each processor while  considering the
-characteristics  of each  processor  (computation power,  range of  frequencies,
-dynamic  and static  powers)  and the  task executed  (computation/communication
-ratio). The  aim being  to reduce  the overall energy  consumption and  to avoid
-increasing    significantly    the    execution    time.   In    our    previous
-work~\cite{Our_first_paper},  we  proposed a  method  that  selects the  optimal
-frequency scaling factor  for a homogeneous cluster executing  a message passing
-iterative synchronous  application while giving  the best trade-off  between the
-energy consumption and  the performance for such applications.   In this work we
-are  interested  in heterogeneous  clusters  as  described  above.  Due  to  the
-heterogeneity of the processors, a vector of scaling factors should
-be selected and  it must give the best trade-off  between energy consumption and
-performance.
-
-The  relation between  the  energy consumption  and  the execution  time for  an
-application  is complex  and nonlinear,  Thus, unlike  the relation  between the
-execution time and  the scaling factor, the relation between  the energy and the
-frequency   scaling    factors   is   nonlinear,   for    more   details   refer
-to~\cite{Freeh_Exploring.the.Energy.Time.Tradeoff}.   Moreover,  these relations
-are not  measured using the same  metric.  To solve this  problem, the execution
-time is normalized by computing the  ratio between the new execution time (after
-scaling  down the  frequencies of  some processors)  and the  initial  one (with
+energy efficient execution of an application. Indeed, even though the dynamic
+power is reduced while scaling down the frequency of a processor, its
+computation power is proportionally decreased. Hence, the execution time might
+be drastically increased and during that time, dynamic and static powers are
+being consumed.  Therefore, it might cancel any gains achieved by scaling down
+the frequency of all nodes to the minimum and the overall energy consumption of
+the application might not be the optimal one.  It is not trivial to select the
+appropriate frequency scaling factor for each processor while considering the
+characteristics of each processor (computation power, range of frequencies,
+dynamic and static powers) and the task executed (computation/communication
+ratio). The aim being to reduce the overall energy consumption and to avoid
+increasing significantly the execution time.  In our previous
+work~\cite{Our_first_paper}, we proposed a method that selects the optimal
+frequency scaling factor for a homogeneous cluster executing a message passing
+iterative synchronous application while giving the best trade-off between the
+energy consumption and the performance for such applications.  In this work we
+are interested in heterogeneous clusters as described above.  Due to the
+heterogeneity of the processors, a vector of scaling factors should be selected
+and it must give the best trade-off between energy consumption and performance.
+
+The relation between the energy consumption and the execution time for an
+application is complex and nonlinear, Thus, unlike the relation between the
+execution time and the scaling factor, the relation between the energy and the
+frequency scaling factors is nonlinear, for more details refer
+to~\cite{Freeh_Exploring.the.Energy.Time.Tradeoff}.  Moreover, these relations
+are not measured using the same metric.  To solve this problem, the execution
+time is normalized by computing the ratio between the new execution time (after
+scaling down the frequencies of some processors) and the initial one (with
 maximum frequency for all nodes) as follows:
 \begin{multline}
   \label{eq:pnorm}
-  P_\textit{Norm} = \frac{T_\textit{New}}{T_\textit{Old}}\\
-       {} = \frac{ \max_{i=1,2,\dots,N} (Tcp_{i} \cdot S_{i}) +MinTcm}
-           {\max_{i=1,2,\dots,N}{(Tcp_i+Tcm_i)}}
+  \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])}}
 \end{multline}
 
-
-In the same way, the energy is normalized by computing the ratio between the consumed energy 
-while scaling down the frequency and the consumed energy with maximum frequency for all nodes:
+In the same way, the energy is normalized by computing the ratio between the
+consumed energy while scaling down the frequency and the consumed energy with
+maximum frequency for all nodes:
 \begin{multline}
   \label{eq:enorm}
-  E_\textit{Norm} = \frac{E_\textit{Reduced}}{E_\textit{Original}} \\
-  {} = \frac{ \sum_{i=1}^{N}{(S_i^{-2} \cdot Pd_i \cdot  Tcp_i)} +
- \sum_{i=1}^{N} {(Ps_i \cdot T_{New})}}{\sum_{i=1}^{N}{( Pd_i \cdot  Tcp_i)} +
- \sum_{i=1}^{N} {(Ps_i \cdot T_{Old})}}
-\end{multline} 
-Where $E_\textit{Reduced}$ and $E_\textit{Original}$ are computed using (\ref{eq:energy}) and
-  $T_{New}$ and $T_{Old}$ 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 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 
-normalized execution time is inverted which gives the normalized performance equation, as follows:
+  \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)}}
+\end{multline}
+Where $\Ereduced$ and $\Eoriginal$ are computed using (\ref{eq:energy}) and
+$\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
+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
+normalized execution time is inverted which gives the normalized performance
+equation, as follows:
 \begin{multline}
   \label{eq:pnorm_inv}
-  P_\textit{Norm} = \frac{T_\textit{Old}}{T_\textit{New}}\\
-          = \frac{\max_{i=1,2,\dots,N}{(Tcp_i+Tcm_i)}}
-            { \max_{i=1,2,\dots,N} (Tcp_{i} \cdot S_{i}) + MinTcm} 
+  \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}
 \end{multline}
 
-
 \begin{figure}[!t]
   \centering
   \subfloat[Homogeneous platform]{%
     \includegraphics[width=.33\textwidth]{fig/homo}\label{fig:r1}}%
-  
-  
+
   \subfloat[Heterogeneous platform]{%
     \includegraphics[width=.33\textwidth]{fig/heter}\label{fig:r2}}
   \label{fig:rel}
   \caption{The energy and performance relation}
 \end{figure}
 
-Then, the objective function can be modeled in order to find the maximum distance
-between the energy curve (\ref{eq:enorm}) and the  performance
-curve (\ref{eq:pnorm_inv}) over all available sets of scaling factors.  This
-represents the minimum energy consumption with minimum execution time (maximum 
-performance) at the same time, see figure~(\ref{fig:r1}) or figure~(\ref{fig:r2}). Then the objective
-function has the following form:
+Then, the objective function can be modeled in order to find the maximum
+distance between the energy curve (\ref{eq:enorm}) and the performance curve
+(\ref{eq:pnorm_inv}) over all available sets of scaling factors.  This
+represents the minimum energy consumption with minimum execution time (maximum
+performance) at the same time, see Figure~\ref{fig:r1} or
+Figure~\ref{fig:r2}. Then the objective function has the following form:
 \begin{equation}
   \label{eq:max}
-  Max Dist = 
-  \max_{i=1,\dots F, j=1,\dots,N}
-      (\overbrace{P_\textit{Norm}(S_{ij})}^{\text{Maximize}} -
-       \overbrace{E_\textit{Norm}(S_{ij})}^{\text{Minimize}} )
+  \MaxDist =
+  \mathop{\max_{i=1,\dots F}}_{j=1,\dots,N}
+      (\overbrace{\Pnorm(S_{ij})}^{\text{Maximize}} -
+       \overbrace{\Enorm(S_{ij})}^{\text{Minimize}} )
 \end{equation}
-where $N$ is the number of nodes and $F$ is the  number of available frequencies for each node. 
-Then, the optimal set of scaling factors that satisfies (\ref{eq:max}) can be selected.  
-The objective function can work with any energy model or any power values for each node 
-(static and dynamic powers). However, the most important energy reduction gain can be achieved when 
-the energy curve has a convex form as shown in~\cite{Zhuo_Energy.efficient.Dynamic.Task.Scheduling,Rauber_Analytical.Modeling.for.Energy,Hao_Learning.based.DVFS}.
+where $N$ is the number of nodes and $F$ is the number of available frequencies
+for each node.  Then, the optimal set of scaling factors that satisfies
+(\ref{eq:max}) can be selected.  The objective function can work with any energy
+model or any power values for each node (static and dynamic powers). However,
+the most important energy reduction gain can be achieved when the energy curve
+has a convex form as shown
+in~\cite{Zhuo_Energy.efficient.Dynamic.Task.Scheduling,Rauber_Analytical.Modeling.for.Energy,Hao_Learning.based.DVFS}.
 
 \section{The scaling factors selection algorithm for heterogeneous platforms }
 \label{sec.optim}
 
-\subsection{The algorithm details}
-In this section, algorithm \ref{HSA} is presented. It selects the frequency scaling factors 
-vector that gives the best trade-off between minimizing the energy consumption  and maximizing 
-the performance of a message passing synchronous iterative application executed on a heterogeneous 
-platform. It works online during the execution time of the iterative message passing program.  
-It uses information gathered during the first iteration such as the computation time and the 
-communication time in one iteration for each node. The algorithm is executed  after the first 
-iteration and returns a vector of optimal frequency scaling factors   that satisfies the objective 
-function (\ref{eq:max}). The program applies DVFS operations to change the frequencies of the CPUs 
-according to the computed scaling factors.  This algorithm is called just once during the execution 
-of the program. Algorithm~(\ref{dvfs}) shows where and when the proposed scaling algorithm is called 
-in the iterative MPI program.
-
-The nodes in a heterogeneous platform have different computing powers, thus while executing message 
-passing iterative synchronous applications, fast nodes have to wait for the slower ones to finish their 
-computations before being able to synchronously communicate with them as in figure (\ref{fig:heter}). 
-These periods are called idle or slack times. 
-The algorithm takes into account this problem and tries to reduce these slack times when selecting the 
-frequency scaling factors vector. At first, it selects initial frequency scaling factors that increase 
-the execution times of fast nodes and  minimize the  differences between  the  computation times of 
-fast and slow nodes. The value of the initial frequency scaling factor  for each node is inversely 
-proportional to its computation time that was gathered from the first iteration. These initial frequency 
-scaling factors are computed as   a ratio between the computation time 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}
-\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:
-\begin{equation}
-  \label{eq:Fint}
- F_{i} = \frac{Fmax_i}{Scp_i},~{i=1,2,\cdots,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  figure
-(\ref{fig:st_freq}), the nodes are sorted by their computing power in ascending
-order and the  frequencies of the faster nodes are scaled  down according to the
-computed initial  frequency scaling factors.  The resulting new  frequencies are
-colored in  blue 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  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 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 according to
-the equation (\ref{eq:perf}) and keeps  its frequency unchanged, while it lowers
-the  frequency  of  all  other  nodes  by one  gear.   The  new  overall  energy
-consumption  and  execution time  are  computed  according  to the  new  scaling
-factors.  The optimal set of frequency scaling factors is the set that gives the
-highest distance according to the objective function (\ref{eq:max}).
-
-Figures~\ref{fig:r1} and \ref{fig:r2}  illustrate the normalized performance and
-consumed  energy for  an application  running on  a homogeneous  platform  and a
-heterogeneous platform respectively while increasing the scaling factors. It can
-be noticed  that in a  homogeneous platform the  search for the  optimal scaling
-factor should start  from the maximum frequency because  the performance and the
-consumed energy decrease from the beginning of the plot. On the other hand,
-in the heterogeneous platform the  performance is maintained at the beginning of
-the plot  even if the  frequencies of the  faster nodes decrease  until the
-computing power of scaled down  nodes are lower than the slowest  node. In other
-words, 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.
-\begin{figure}[!t]
-  \centering
-    \includegraphics[scale=0.5]{fig/start_freq}
-  \caption{Selecting the initial frequencies}
-  \label{fig:st_freq}
-\end{figure}
-
-
-
-
 \begin{algorithm}
   \begin{algorithmic}[1]
     % \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.$
-    \EndIf 
-    \State $T_\textit{Old} \gets max_{~i=1,\dots,N } (Tcp_i+Tcm_i)$
-    \State $E_\textit{Original} \gets \sum_{i=1}^{N}{( Pd_i \cdot  Tcp_i)} +\sum_{i=1}^{N} {(Ps_i \cdot T_{Old})}$
-    \State  $Sopt_{i} \gets 1,~i=1,\dots,N. $
-    \State $Dist \gets 0 $
+          \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 $\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 $T_{New} \gets max_\textit{~i=1,\dots,N} (Tcp_{i} \cdot S_{i}) + MinTcm $
-       \State $E_\textit{Reduced} \gets \sum_{i=1}^{N}{(S_i^{-2} \cdot Pd_i \cdot  Tcp_i)} + $  \hspace*{43 mm} 
-               $\sum_{i=1}^{N} {(Ps_i \cdot T_{New})} $
-       \State $ P_\textit{Norm} \gets \frac{T_\textit{Old}}{T_\textit{New}}$
-       \State $E_\textit{Norm}\gets \frac{E_\textit{Reduced}}{E_\textit{Original}}$
+       \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}
@@ -652,7 +607,7 @@ maximum distance  between the  energy curve and  the performance curve  is while
       \If {$(k=1)$}
         \State Gather all times of computation and\newline\hspace*{3em}%
                communication from each node.
-        \State Call algorithm \ref{HSA}.
+        \State Call Algorithm \ref{HSA}.
         \State Compute the new frequencies from the\newline\hspace*{3em}%
                returned optimal scaling factors.
         \State Set the new frequencies to nodes.
@@ -663,441 +618,551 @@ maximum distance  between the  energy curve and  the performance curve  is while
   \label{dvfs}
 \end{algorithm}
 
+\subsection{The algorithm details}
+
+In this section, Algorithm~\ref{HSA} is presented. It selects the frequency
+scaling factors vector that gives the best trade-off between minimizing the
+energy consumption and maximizing the performance of a message passing
+synchronous iterative application executed on a heterogeneous platform. It works
+online during the execution time of the iterative message passing program.  It
+uses information gathered during the first iteration such as the computation
+time and the communication time in one iteration for each node. The algorithm is
+executed after the first iteration and returns a vector of optimal frequency
+scaling factors that satisfies the objective function (\ref{eq:max}). The
+program applies DVFS operations to change the frequencies of the CPUs according
+to the computed scaling factors.  This algorithm is called just once during the
+execution of the program. Algorithm~\ref{dvfs} shows where and when the proposed
+scaling algorithm is called in the iterative MPI program.
+
+\begin{figure}[!t]
+  \centering
+  \includegraphics[scale=0.5]{fig/start_freq}
+  \caption{Selecting the initial frequencies}
+  \label{fig:st_freq}
+\end{figure}
+
+The nodes in a heterogeneous platform have different computing powers, thus
+while executing message passing iterative synchronous applications, fast nodes
+have to wait for the slower ones to finish their computations before being able
+to synchronously communicate with them as in Figure~\ref{fig:heter}.  These
+periods are called idle or slack times.  The algorithm takes into account this
+problem and tries to reduce these slack times when selecting the frequency
+scaling factors vector. At first, it selects initial frequency scaling factors
+that increase the execution times of fast nodes and minimize the differences
+between the computation times of fast and slow nodes. The value of the initial
+frequency scaling factor for each node is inversely proportional to its
+computation time that was gathered from the first iteration. These initial
+frequency scaling factors are computed as a ratio between the computation time
+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]}
+\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:
+\begin{equation}
+  \label{eq:Fint}
+  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
+Figure~\ref{fig:st_freq}, the nodes are sorted by their computing power in
+ascending order and the frequencies of the faster nodes are scaled down
+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
+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
+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
+according to the equation (\ref{eq:perf}) and keeps its frequency unchanged,
+while it lowers the frequency of all other nodes by one gear.  The new overall
+energy consumption and execution time are computed according to the new scaling
+factors.  The optimal set of frequency scaling factors is the set that gives the
+highest distance according to the objective function (\ref{eq:max}).
+
+Figures~\ref{fig:r1} and \ref{fig:r2} illustrate the normalized performance and
+consumed energy for an application running on a homogeneous platform and a
+heterogeneous platform respectively while increasing the scaling factors. It can
+be noticed that in a homogeneous platform the search for the optimal scaling
+factor should start from the maximum frequency because the performance and the
+consumed energy decrease from the beginning of the plot. On the other hand, in
+the heterogeneous platform the performance is maintained at the beginning of the
+plot even if the frequencies of the faster nodes decrease until the computing
+power of scaled down nodes are lower than the slowest node. In other words,
+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.
+
 \subsection{The evaluation of the proposed algorithm}
 \label{sec.verif.algo}
-The precision  of the  proposed algorithm mainly  depends on the  execution time
-prediction model  defined in  (\ref{eq:perf}) and the  energy model  computed by
-(\ref{eq:energy}).   The energy  model is  also significantly  dependent  on the
-execution  time model  because  the static  energy  is linearly  related to  the
-execution time  and the dynamic energy  is related to the  computation time. So,
-all the works presented  in this paper are based on the  execution time model. To
-verify  this  model, the  predicted  execution time  was  compared  to the  real
-execution          time           over          SimGrid/SMPI          simulator,
-v3.10~\cite{casanova+giersch+legrand+al.2014.versatile},   for   all   the   NAS
-parallel benchmarks NPB v3.3  \cite{NAS.Parallel.Benchmarks}, running class B on
-8 or  9 nodes. The comparison showed  that the proposed execution  time model is
-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 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 applied to different NAS benchmarks classes with 
-different number of nodes. The solutions returned by the brute force algorithm and the proposed algorithm were identical 
-and the proposed algorithm was on average 10 times faster than the brute force algorithm. It has a small execution time: 
-for a heterogeneous 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$ 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.
-
-\section{Experimental results}
-\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
-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
-node because just one process was executed per node.  The heterogeneous platform
-was  composed  of  four  types  of  nodes. Each  type  of  nodes  had  different
-characteristics  such as  the maximum  CPU  frequency, the  number of  available
-frequencies  and the  computational power,  see Table  \ref{table:platform}. The
-characteristics  of  these  different  types  of nodes  are  inspired  from  the
-specifications of real  Intel processors.  The heterogeneous platform  had up to
-144 nodes and had nodes from the four types in equal proportions, for example if
-a benchmark was executed on 8 nodes, 2 nodes from each type were used. Since the
-constructors of  CPUs do not specify the  dynamic and the static  power of their
-CPUs, for  each type of  node they were  chosen proportionally to  its computing
-power  (FLOPS).  In  the initial  heterogeneous platform,  while  computing with
-highest frequency,  each node  consumed an amount  of power proportional  to its
-computing  power  (which  corresponds to  80\%  of  its  dynamic power  and  the
-remaining  20\%  to  the  static   power),  the  same  assumption  was  made  in
-\cite{Our_first_paper,Rauber_Analytical.Modeling.for.Energy}.    Finally,  These
-nodes were connected via an Ethernet network with 1 Gbit/s bandwidth.
+The precision of the proposed algorithm mainly depends on the execution time
+prediction model defined in (\ref{eq:perf}) and the energy model computed by
+(\ref{eq:energy}).  The energy model is also significantly dependent on the
+execution time model because the static energy is linearly related to the
+execution time and the dynamic energy is related to the computation time. So,
+all the works presented in this paper are based on the execution time model. To
+verify this model, the predicted execution time was compared to the real
+execution time over SimGrid/SMPI simulator,
+v3.10~\cite{casanova+giersch+legrand+al.2014.versatile}, for all the NAS
+parallel benchmarks NPB v3.3 \cite{NAS.Parallel.Benchmarks}, running class B on
+8 or 9 nodes. The comparison showed that the proposed execution time model is
+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
+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
+applied to different NAS benchmarks classes with different number of nodes. The
+solutions returned by the brute force algorithm and the proposed algorithm were
+identical and the proposed algorithm was on average 10 times faster than the
+brute force algorithm. It has a small execution time: for a heterogeneous
+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)$, 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.
 
 \begin{table}[!t]
   \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             &              &       \\
+    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:platform}
 \end{table}
 
- 
-%\subsection{Performance prediction verification}
+\section{Experimental results}
+\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
+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
+node because just one process was executed per node.  The heterogeneous platform
+was composed of four types of nodes. Each type of nodes had different
+characteristics such as the maximum CPU frequency, the number of available
+frequencies and the computational power, see Table~\ref{table:platform}. The
+characteristics of these different types of nodes are inspired from the
+specifications of real Intel processors.  The heterogeneous platform had up to
+144 nodes and had nodes from the four types in equal proportions, for example if
+a benchmark was executed on 8 nodes, 2 nodes from each type were used. Since the
+constructors of CPUs do not specify the dynamic and the static power of their
+CPUs, for each type of node they were chosen proportionally to its computing
+power (FLOPS).  In the initial heterogeneous platform, while computing with
+highest frequency, each node consumed an amount of power proportional to its
+computing power (which corresponds to \np[\%]{80} of its dynamic power and the
+remaining \np[\%]{20} to the static power), the same assumption was made in
+\cite{Our_first_paper,Rauber_Analytical.Modeling.for.Energy}.  Finally, These
+nodes were connected via an Ethernet network with 1 Gbit/s bandwidth.
 
 
 \subsection{The experimental results of the scaling algorithm}
 \label{sec.res}
 
-
 The proposed algorithm was applied to the seven parallel NAS benchmarks (EP, CG,
-MG, FT, BT, LU and SP) and  the benchmarks were executed with the three classes:
+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
-executed. Indeed, the benchmarks CG, MG, LU, EP and FT had to be executed on $1,
-2, 4, 8, 16, 32, 64, 128$ nodes.   The other benchmarks such as BT and SP had to
-be executed on $1, 4, 9, 16, 36, 64, 144$ nodes.
-
- 
- 
+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
+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}{l|}}
+  \begin{tabular}{|*{7}{r|}}
     \hline
-    Program     & Execution     & Energy         & Energy      & Performance        & Distance      \\
-    name       & time/s        & consumption/J  & saving\%    & degradation\%      &               \\
+    \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      \\
+    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
-    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
+  \medskip
 % \begin{table}[!t]
   \caption{Running NAS benchmarks on 8 and 9 nodes }
   % title of Table
   \centering
-  \begin{tabular}{|*{7}{l|}}
+  \begin{tabular}{|*{7}{r|}}
     \hline
-    Program    & Execution     & Energy         & Energy      & Performance        & Distance      \\
-    name       & time/s        & consumption/J  & saving\%    & degradation\%      &               \\
+    \hspace{-2.2084pt}%
+    Program & Execution & Energy        & Energy   & Performance   & Distance \\
+    name    & time/s    & consumption/J & saving\% & degradation\% &          \\
     \hline
-    CG         &36.11    	   &3263.49	        &31.25	      &7.12	               &24.13     \\
-    \hline 
-    MG         &8.99 	       &953.39	        &33.78	      &6.41	               &27.37     \\
-   \hline
-    EP         &40.39	       &5652.81	        &27.04	      &0.49	               &26.55     \\
-   \hline
-    LU         &218.79  	   &36149.77	    &28.23        &0.01   	           &28.22      \\
+    CG      &  36.11    &  3263.49      & 31.25    & 7.12          & 24.13    \\
+    \hline
+    MG      &   8.99    &   953.39      & 33.78    & 6.41          & 27.37    \\
+    \hline
+    EP      &  40.39    &  5652.81      & 27.04    & 0.49          & 26.55    \\
+    \hline
+    LU      & 218.79    & 36149.77      & 28.23    & 0.01          & 28.22    \\
+    \hline
+    BT      & 166.89    & 23207.42      & 32.32    & 7.89          & 24.43    \\
+    \hline
+    SP      & 104.73    & 18414.62      & 24.73    & 2.78          & 21.95    \\
+    \hline
+    FT      &  51.10    &  4913.26      & 31.02    & 2.54          & 28.48    \\
     \hline
-    BT         &166.89 	       &23207.42	    &32.32	      &7.89	               &24.43      \\
-   \hline
-    SP         &104.73	       &18414.62	    &24.73	      &2.78	               &21.95      \\
-   \hline
-    FT         &51.10	       &4913.26	        &31.02	      &2.54	               &28.48      \\
-\hline 
   \end{tabular}
   \label{table:res_8n}
 % \end{table}
 
-\medskip
+  \medskip
 % \begin{table}[!t]
   \caption{Running NAS benchmarks on 16 nodes }
   % title of Table
   \centering
-  \begin{tabular}{|*{7}{l|}}
+  \begin{tabular}{|*{7}{r|}}
     \hline
-    Program     & Execution     & Energy         & Energy      & Performance        & Distance      \\
-    name       & time/s        & consumption/J  & saving\%    & degradation\%      &               \\
+    \hspace{-2.2084pt}%
+    Program & Execution & Energy        & Energy   & Performance   & Distance \\
+    name    & time/s    & consumption/J & saving\% & degradation\% &          \\
     \hline
-    CG         &31.74	       &4373.90	        &26.29	      &9.57	               &16.72          \\
-    \hline 
-    MG         &5.71	       &1076.19         &32.49	      &6.05	               &26.44         \\
-   \hline
-    EP         &20.11	       &5638.49	        &26.85	      &0.56	               &26.29         \\
-   \hline
-    LU         &144.13	       &42529.06	    &28.80	      &6.56	               &22.24         \\
+    CG      &  31.74    &  4373.90      & 26.29    & 9.57          & 16.72    \\
+    \hline
+    MG      &   5.71    &  1076.19      & 32.49    & 6.05          & 26.44    \\
+    \hline
+    EP      &  20.11    &  5638.49      & 26.85    & 0.56          & 26.29    \\
+    \hline
+    LU      & 144.13    & 42529.06      & 28.80    & 6.56          & 22.24    \\
+    \hline
+    BT      &  97.29    & 22813.86      & 34.95    & 5.80          & 29.15    \\
+    \hline
+    SP      &  66.49    & 20821.67      & 22.49    & 3.82          & 18.67    \\
+    \hline
+    FT      &  37.01    &  5505.60      & 31.59    & 6.48          & 25.11    \\
     \hline
-    BT         &97.29	       &22813.86	    &34.95   	  &5.80	               &29.15         \\
-   \hline
-    SP         &66.49	       &20821.67 	    &22.49	      &3.82	               &18.67         \\
-   \hline
-    FT     	   &37.01          &5505.60	        &31.59	      &6.48	               &25.11         \\
-\hline 
   \end{tabular}
   \label{table:res_16n}
 % \end{table}
 
-\medskip
+  \medskip
 % \begin{table}[!t]
   \caption{Running NAS benchmarks on 32 and 36 nodes }
   % title of Table
   \centering
-  \begin{tabular}{|*{7}{l|}}
+  \begin{tabular}{|*{7}{r|}}
     \hline
-    Program    & Execution     & Energy         & Energy      & Performance        & Distance      \\
-    name       & time/s        & consumption/J  & saving\%    & degradation\%      &               \\
+    \hspace{-2.2084pt}%
+    Program & Execution & Energy        & Energy   & Performance   & Distance \\
+    name    & time/s    & consumption/J & saving\% & degradation\% &          \\
     \hline
-    CG         &32.35	       &6704.21	        &16.15	      &5.30	               &10.85           \\
-    \hline 
-    MG         &4.30	       &1355.58	        &28.93	      &8.85	               &20.08          \\
-   \hline
-    EP         &9.96           &5519.68	        &26.98	      &0.02	               &26.96          \\
-   \hline
-    LU         &99.93	       &67463.43	    &23.60	      &2.45	               &21.15          \\
+    CG      & 32.35     &  6704.21      & 16.15    & 5.30          & 10.85    \\
+    \hline
+    MG      &  4.30     &  1355.58      & 28.93    & 8.85          & 20.08    \\
+    \hline
+    EP      &  9.96     &  5519.68      & 26.98    & 0.02          & 26.96    \\
+    \hline
+    LU      & 99.93     & 67463.43      & 23.60    & 2.45          & 21.15    \\
+    \hline
+    BT      & 48.61     & 23796.97      & 34.62    & 5.83          & 28.79    \\
+    \hline
+    SP      & 46.01     & 27007.43      & 22.72    & 3.45          & 19.27    \\
+    \hline
+    FT      & 28.06     &  7142.69      & 23.09    & 2.90          & 20.19    \\
     \hline
-    BT         &48.61	       &23796.97	    &34.62	      &5.83	               &28.79          \\
-   \hline
-    SP         &46.01	       &27007.43	    &22.72	      &3.45	               &19.27           \\
-   \hline
-    FT     	   &28.06     	   &7142.69	        &23.09	      &2.90	               &20.19           \\
-\hline 
   \end{tabular}
   \label{table:res_32n}
 % \end{table}
 
-\medskip
+  \medskip
 % \begin{table}[!t]
   \caption{Running NAS benchmarks on 64 nodes }
   % title of Table
   \centering
-  \begin{tabular}{|*{7}{l|}}
+  \begin{tabular}{|*{7}{r|}}
     \hline
-    Program    & Execution     & Energy         & Energy      & Performance        & Distance      \\
-    name       & time/s        & consumption/J  & saving\%    & degradation\%      &               \\
+    \hspace{-2.2084pt}%
+    Program & Execution & Energy        & Energy   & Performance   & Distance \\
+    name    & time/s    & consumption/J & saving\% & degradation\% &          \\
     \hline
-    CG         &46.65	       &17521.83	    &8.13	      &1.68	               &6.45           \\
-    \hline 
-    MG         &3.27	       &1534.70	        &29.27	      &14.35	           &14.92          \\
-   \hline
-    EP         &5.05           &5471.1084	    &27.12	      &3.11    	           &24.01         \\
-   \hline
-    LU         &73.92	       &101339.16	    &21.96	      &3.67	               &18.29         \\
+    CG      & 46.65     &  17521.83     &  8.13    &  1.68         &  6.45    \\
+    \hline
+    MG      &  3.27     &   1534.70     & 29.27    & 14.35         & 14.92    \\
+    \hline
+    EP      &  5.05     &   5471.11     & 27.12    &  3.11         & 24.01    \\
+    \hline
+    LU      & 73.92     & 101339.16     & 21.96    &  3.67         & 18.29    \\
+    \hline
+    BT      & 39.99     &  27166.71     & 32.02    & 12.28         & 19.74    \\
+    \hline
+    SP      & 52.00     &  49099.28     & 24.84    &  0.03         & 24.81    \\
+    \hline
+    FT      & 25.97     &  10416.82     & 20.15    &  4.87         & 15.28    \\
     \hline
-    BT         &39.99 	       &27166.71	    &32.02	      &12.28	           &19.74         \\
-   \hline
-    SP         &52.00	       &49099.28	    &24.84	      &0.03	               &24.81         \\
-   \hline
-    FT         &25.97	       &10416.82        &20.15	      &4.87	               &15.28         \\
-\hline 
   \end{tabular}
   \label{table:res_64n}
 % \end{table}
 
-\medskip
+  \medskip
 % \begin{table}[!t]
   \caption{Running NAS benchmarks on 128 and 144 nodes }
   % title of Table
   \centering
-  \begin{tabular}{|*{7}{l|}}
+  \begin{tabular}{|*{7}{r|}}
     \hline
-    Program    & Execution     & Energy         & Energy      & Performance        & Distance     \\
-    name       & time/s        & consumption/J  & saving\%    & degradation\%      &              \\
+    \hspace{-2.2084pt}%
+    Program & Execution & Energy        & Energy   & Performance   & Distance \\
+    name    & time/s    & consumption/J & saving\% & degradation\% &          \\
     \hline
-    CG         &56.92	       &41163.36        &4.00	      &1.10	               &2.90          \\
-    \hline 
-    MG         &3.55           &2843.33         &18.77	      &10.38	           &8.39          \\
-   \hline
-    EP         &2.67           &5669.66	        &27.09	      &0.03	               &27.06         \\
-   \hline
-    LU         &51.23	       &144471.90   	&16.67	      &2.36	               &14.31         \\
+    CG      & 56.92     &  41163.36     &  4.00    &  1.10         &  2.90    \\
+    \hline
+    MG      &  3.55     &   2843.33     & 18.77    & 10.38         &  8.39    \\
+    \hline
+    EP      &  2.67     &   5669.66     & 27.09    &  0.03         & 27.06    \\
+    \hline
+    LU      & 51.23     & 144471.90     & 16.67    &  2.36         & 14.31    \\
+    \hline
+    BT      & 37.96     &  44243.82     & 23.18    &  1.28         & 21.90    \\
+    \hline
+    SP      & 64.53     & 115409.71     & 26.72    &  0.05         & 26.67    \\
+    \hline
+    FT      & 25.51     &  18808.72     & 12.85    &  2.84         & 10.01    \\
     \hline
-    BT         &37.96          &44243.82	    &23.18	      &1.28	               &21.90         \\
-   \hline
-    SP         &64.53	       &115409.71 	    &26.72	      &0.05	               &26.67         \\
-   \hline
-    FT         &25.51	       &18808.72	    &12.85	      &2.84	               &10.01         \\
-\hline 
   \end{tabular}
   \label{table:res_128n}
 \end{table}
-The overall energy  consumption was computed for each  instance according to the
-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},
-\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 35\%) 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 execution times when
-the benchmarks are run over a high number of nodes.  Indeed, the benchmarks with
-the  same  class,  C,  are  executed  on different  numbers  of  nodes,  so  the
-computation required  for each iteration is  divided by the  number of computing
-nodes.  On the other hand,  more communications are required when increasing the
-number  of  nodes so  the  static energy  increases  linearly  according to  the
-communication time and the dynamic power  is less relevant in the overall energy
-consumption.   Therefore, reducing the  frequency with  algorithm~(\ref{HSA}) is
-less effective  in reducing the overall  energy savings. It can  also be noticed
-that for the benchmarks EP and  SP that contain little or no communications, the
-energy savings are  not significantly affected by the high  number of nodes.  No
-experiments were conducted  using bigger classes than D,  because they require a
-lot  of memory (more  than 64GB)  when being  executed by  the simulator  on one
-machine.   The maximum  distance between  the  normalized energy  curve and  the
-normalized performance for each instance is  also shown in the result tables. It
-decrease in the same way as  the energy saving percentage.  The tables also show
-that the performance degradation  percentage is not significantly increased when
-the number  of computing  nodes is increased  because the computation  times are
-small when compared to the communication times.
-
-
- 
+
 \begin{figure}[!t]
   \centering
-  \subfloat[Energy saving]{%
+  \subfloat[Energy saving (\%)]{%
     \includegraphics[width=.33\textwidth]{fig/energy}\label{fig:energy}}%
-  
-  \subfloat[Performance degradation ]{%
+
+  \subfloat[Performance degradation (\%)]{%
     \includegraphics[width=.33\textwidth]{fig/per_deg}\label{fig:per_deg}}
   \label{fig:avg}
   \caption{The energy and performance for all NAS benchmarks running with a different number of nodes}
 \end{figure}
 
-Figures  \ref{fig:energy} and  \ref{fig:per_deg} present  the energy  saving and
-performance  degradation respectively for  all the  benchmarks according  to the
-number of used nodes. As shown  in the first plot, the energy saving percentages
-of the benchmarks MG,  LU, BT and FT decrease linearly when  the number of nodes
-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
-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
-communicating than computing,  thus, scaling down the frequencies  of some nodes
+The overall energy consumption was computed for each instance according to the
+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},
+\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
+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
+execution times when the benchmarks are run over a higher number of nodes.
+Indeed, the benchmarks with the same class, C, are executed on different numbers
+of nodes, so the computation required for each iteration is divided by the
+number of computing nodes.  On the other hand, more communications are required
+when increasing the number of nodes so the static energy increases linearly
+according to the communication time and the dynamic power is less relevant in
+the overall energy consumption.  Therefore, reducing the frequency with
+Algorithm~\ref{HSA} is less effective in reducing the overall energy savings. It
+can also be noticed that for the benchmarks EP and SP that contain little or no
+communications, the energy savings are not significantly affected by the high
+number of nodes.  No experiments were conducted using bigger classes than D,
+because they require a lot of memory (more than 64GB) when being executed by the
+simulator on one machine.  The maximum distance between the normalized energy
+curve and the normalized performance for each instance is also shown in the
+result tables. It decrease in the same way as the energy saving percentage.  The
+tables also show that the performance degradation percentage is not
+significantly increased when the number of computing nodes is increased because
+the computation times are small when compared to the communication times.
+
+Figures~\ref{fig:energy} and \ref{fig:per_deg} present the energy saving and
+performance degradation respectively for all the benchmarks according to the
+number of used nodes. As shown in the first plot, the energy saving percentages
+of the benchmarks MG, LU, BT and FT decrease linearly when the number of nodes
+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
+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
+communicating than computing, thus, scaling down the frequencies of some nodes
 has less effect on the performance.
 
-
-
-
 \subsection{The results for different power consumption scenarios}
 \label{sec.compare}
-The results  of the previous section  were obtained while  using processors that
-consume during  computation an overall power  which is 80\%  composed of dynamic
-power and of 20\% of static power. In this section, these ratios are changed and
-two new  power scenarios are  considered in order  to evaluate how  the proposed
-algorithm adapts itself  according to the static and  dynamic power values.  The
-two new power scenarios are the following:
+
+The results of the previous section were obtained while using processors that
+consume during computation an overall power which is \np[\%]{80} composed of
+dynamic power and of \np[\%]{20} of static power. In this section, these ratios
+are changed and two new power scenarios are considered in order to evaluate how
+the proposed algorithm adapts itself according to the static and dynamic power
+values.  The two new power scenarios are the following:
 
 \begin{itemize}
-\item 70\% of dynamic power  and 30\% of static power
-\item 90\% of dynamic power  and 10\% of static power
+\item \np[\%]{70} of dynamic power and \np[\%]{30} of static power
+\item \np[\%]{90} of dynamic power and \np[\%]{10} of static power
 \end{itemize}
 
-The NAS parallel benchmarks were  executed again over processors that follow the
-new power scenarios.   The class C of each  benchmark was run over 8  or 9 nodes
-and   the    results   are   presented   in    Tables   \ref{table:res_s1}   and
-\ref{table:res_s2}. These tables  show that the energy saving  percentage of the
-70\%-30\% scenario is  smaller for all benchmarks compared  to the energy saving
-of the 90\%-10\% scenario. Indeed, in  the latter more dynamic power is consumed
-when  nodes are running  on their  maximum frequencies,  thus, scaling  down the
-frequency of  the nodes results in  higher energy savings than  in the 70\%-30\%
-scenario. On the  other hand, the performance degradation  percentage is smaller
-in the 70\%-30\% scenario compared to the 90\%-10\% scenario. This is due to the
-higher  static  power percentage  in  the first  scenario  which  makes it  more
-relevant in the  overall consumed energy.  Indeed, the  static energy is related
-to the execution time and if  the performance is degraded the amount of consumed
-static  energy directly  increases.  Therefore,  the proposed  algorithm  does not
-really significantly  scale down much the  frequencies of the nodes  in order to
-limit the  increase of the  execution time and  thus limiting the effect  of the
+The NAS parallel benchmarks were executed again over processors that follow the
+new power scenarios.  The class C of each benchmark was run over 8 or 9 nodes
+and the results are presented in Tables~\ref{table:res_s1} and
+\ref{table:res_s2}. These tables show that the energy saving percentage of the
+\np[\%]{70}-\np[\%]{30} scenario is smaller for all benchmarks compared to the
+energy saving of the \np[\%]{90}-\np[\%]{10} scenario.  Indeed, in the latter
+more dynamic power is consumed when nodes are running on their maximum
+frequencies, thus, scaling down the frequency of the nodes results in higher
+energy savings than in the \np[\%]{70}-\np[\%]{30} scenario. On the other hand,
+the performance degradation percentage is smaller in the \np[\%]{70}-\np[\%]{30}
+scenario compared to the \np[\%]{90}-\np[\%]{10} scenario. This is due to the
+higher static power percentage in the first scenario which makes it more
+relevant in the overall consumed energy.  Indeed, the static energy is related
+to the execution time and if the performance is degraded the amount of consumed
+static energy directly increases.  Therefore, the proposed algorithm does not
+really significantly scale down much the frequencies of the nodes in order to
+limit the increase of the execution time and thus limiting the effect of the
 consumed static energy.
 
-Both   new  power   scenarios   are  compared   to   the  old   one  in   figure
-(\ref{fig:sen_comp}). It  shows the average of the  performance degradation, the
-energy saving and the  distances for all NAS benchmarks of class  C running on 8
-or 9 nodes.   The comparison shows that the energy  saving ratio is proportional
-to the dynamic power ratio: it is increased when applying the 90\%-10\% scenario
-because at  maximum frequency  the dynamic  energy is the  most relevant  in the
-overall consumed  energy and can  be reduced by  lowering the frequency  of some
-processors. On  the other hand, the  energy saving decreases  when the 70\%-30\%
-scenario is  used because  the dynamic  energy is less  relevant in  the overall
-consumed energy and  lowering the frequency does not  return big energy savings.
-Moreover, the average  of the performance degradation is  decreased when using a
-higher  ratio   for  static  power  (e.g.   70\%-30\%   scenario  and  80\%-20\%
-scenario). Since  the proposed algorithm  optimizes the energy  consumption when
-using a  higher ratio for dynamic  power the algorithm  selects bigger frequency
-scaling  factors that result  in more  energy saving  but less  performance, for
-example see  Figure (\ref{fig:scales_comp}). The  opposite happens when  using a
-higher  ratio for  static power,  the algorithm  proportionally  selects smaller
-scaling  values which result  in less  energy saving  but also  less performance
+Both new power scenarios are compared to the old one in
+Figure~\ref{fig:sen_comp}. It shows the average of the performance degradation,
+the energy saving and the distances for all NAS benchmarks of class C running on
+8 or 9 nodes.  The comparison shows that the energy saving ratio is proportional
+to the dynamic power ratio: it is increased when applying the
+\np[\%]{90}-\np[\%]{10} scenario because at maximum frequency the dynamic energy
+is the most relevant in the overall consumed energy and can be reduced by
+lowering the frequency of some processors. On the other hand, the energy saving
+decreases when the \np[\%]{70}-\np[\%]{30} scenario is used because the dynamic
+energy is less relevant in the overall consumed energy and lowering the
+frequency does not return big energy savings.  Moreover, the average of the
+performance degradation is decreased when using a higher ratio for static power
+(e.g.  \np[\%]{70}-\np[\%]{30} scenario and \np[\%]{80}-\np[\%]{20}
+scenario). Since the proposed algorithm optimizes the energy consumption when
+using a higher ratio for dynamic power the algorithm selects bigger frequency
+scaling factors that result in more energy saving but less performance, for
+example see Figure~\ref{fig:scales_comp}. The opposite happens when using a
+higher ratio for static power, the algorithm proportionally selects smaller
+scaling values which result in less energy saving but also less performance
 degradation.
 
-
- \begin{table}[!t]
-  \caption{The results of the 70\%-30\% power scenario}
+\begin{table}[!t]
+  \caption{The results of the \np[\%]{70}-\np[\%]{30} power scenario}
   % title of Table
   \centering
-  \begin{tabular}{|*{6}{l|}}
+  \begin{tabular}{|*{6}{r|}}
+    \hline
+    Program & Energy        & Energy   & Performance   & Distance \\
+    name    & consumption/J & saving\% & degradation\% &          \\
     \hline
-    Program    & Energy          & Energy      & Performance        & Distance     \\
-    name       & consumption/J   & saving\%    & degradation\%      &              \\
+    CG      &  4144.21      & 22.42    & 7.72          & 14.70    \\
     \hline
-    CG         &4144.21          &22.42        &7.72                &14.70         \\
-    \hline 
-    MG         &1133.23          &24.50        &5.34                &19.16          \\
+    MG      &  1133.23      & 24.50    & 5.34          & 19.16    \\
    \hline
-    EP         &6170.30	        &16.19	       &0.02	            &16.17          \\
+    EP      &  6170.30      & 16.19    & 0.02          & 16.17    \\
    \hline
-    LU         &39477.28        &20.43	       &0.07	            &20.36          \\
+    LU      & 39477.28      & 20.43    & 0.07          & 20.36    \\
     \hline
-    BT         &26169.55	    &25.34	       &6.62	            &18.71          \\
+    BT      & 26169.55      & 25.34    & 6.62          & 18.71    \\
    \hline
-    SP         &19620.09	    &19.32	       &3.66	            &15.66          \\
+    SP      & 19620.09      & 19.32    & 3.66          & 15.66    \\
    \hline
-    FT         &6094.07	        &23.17	       &0.36	            &22.81          \\
-\hline 
+    FT      &  6094.07      & 23.17    & 0.36          & 22.81    \\
+    \hline
   \end{tabular}
   \label{table:res_s1}
 \end{table}
 
-
-
 \begin{table}[!t]
-  \caption{The results of the 90\%-10\% power scenario}
+  \caption{The results of the \np[\%]{90}-\np[\%]{10} power scenario}
   % title of Table
   \centering
-  \begin{tabular}{|*{6}{l|}}
+  \begin{tabular}{|*{6}{r|}}
     \hline
-    Program    & Energy          & Energy      & Performance        & Distance     \\
-    name       & consumption/J   & saving\%    & degradation\%      &              \\
+    Program & Energy          & Energy      & Performance   & Distance \\
+    name    & consumption/J   & saving\%    & degradation\% &          \\
     \hline
-    CG         &2812.38	         &36.36	       &6.80                &29.56         \\
-    \hline 
-    MG         &825.427	         &38.35	       &6.41	            &31.94         \\
-   \hline
-    EP         &5281.62	         &35.02	       &2.68	            &32.34         \\
-   \hline
-    LU         &31611.28	     &39.15        &3.51	            &35.64        \\
+    CG      &  2812.38        & 36.36       &  6.80         & 29.56    \\
+    \hline
+    MG      &   825.43        & 38.35       &  6.41         & 31.94    \\
+    \hline
+    EP      &  5281.62        & 35.02       &  2.68         & 32.34    \\
+    \hline
+    LU      & 31611.28        & 39.15       &  3.51         & 35.64    \\
+    \hline
+    BT      & 21296.46        & 36.70       &  6.60         & 30.10    \\
+    \hline
+    SP      & 15183.42        & 35.19       & 11.76         & 23.43    \\
+    \hline
+    FT      &  3856.54        & 40.80       &  5.67         & 35.13    \\
     \hline
-    BT         &21296.46	     &36.70	       &6.60	            &30.10       \\
-   \hline
-    SP         &15183.42	     &35.19	       &11.76	            &23.43        \\
-   \hline
-    FT         &3856.54	         &40.80	       &5.67	            &35.13        \\
-\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.00 & 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
@@ -1108,79 +1173,68 @@ degradation.
     \includegraphics[width=.33\textwidth]{fig/three_scenarios}\label{fig:scales_comp}}
   \label{fig:comp}
   \caption{The comparison of the three power scenarios}
-\end{figure}  
-
+\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.
-
-Both algorithms were applied to the parallel NAS benchmarks to compare their efficiency. Table \ref{table:compare_EDP}  presents the results of comparing the execution times and the energy consumption for both versions of the NAS benchmarks while running the class C of each benchmark over 8 or 9 heterogeneous nodes. The results show that our algorithm provides better energy savings than Spiliopoulos et al. algorithm, 
-on average it results in 29.76\% energy saving while their algorithm returns just 25.75\%. The average of performance degradation percentage is approximately the same for both algorithms, about 4\%. 
 
+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
+execution times and the energy consumption for both versions of the NAS
+benchmarks while running the class C of each benchmark over 8 or 9 heterogeneous
+nodes. The results show that our algorithm provides better energy savings than
+Spiliopoulos et al. algorithm, on average it results in \np[\%]{29.76} energy
+saving while their algorithm returns just \np[\%]{25.75}. The average of
+performance degradation percentage is approximately the same for both
+algorithms, about \np[\%]{4}.
 
 For all benchmarks,  our algorithm outperforms Spiliopoulos et  al. algorithm in
-terms of  energy and  performance trade-off, see  figure (\ref{fig:compare_EDP}),
+terms of  energy and  performance trade-off, see  Figure~\ref{fig:compare_EDP},
 because it maximizes the distance  between the energy saving and the performance
 degradation values while giving the same weight for both metrics.
 
-
-
-
-\begin{table}[!t]
- \caption{Comparing the proposed algorithm}
- \centering
-\begin{tabular}{|l|l|l|l|l|l|l|l|}
-\hline
-\multicolumn{2}{|l|}{\multirow{2}{*}{\begin{tabular}[c]{@{}l@{}}Program \\ name\end{tabular}}} & \multicolumn{2}{l|}{Energy saving \%} & \multicolumn{2}{l|}{Perf.  degradation \%} & \multicolumn{2}{l|}{Distance} \\ \cline{3-8} 
-\multicolumn{2}{|l|}{}                                                                         & EDP             & MaxDist          & EDP            & MaxDist           & EDP          & MaxDist        \\ \hline
-\multicolumn{2}{|l|}{CG}                                                                       & 27.58           & 31.25            & 5.82           & 7.12              & 21.76        & 24.13          \\ \hline
-\multicolumn{2}{|l|}{MG}                                                                       & 29.49           & 33.78            & 3.74           & 6.41              & 25.75        & 27.37          \\ \hline
-\multicolumn{2}{|l|}{LU}                                                                       & 19.55           & 28.33            & 0.0            & 0.01              & 19.55        & 28.22          \\ \hline
-\multicolumn{2}{|l|}{EP}                                                                       & 28.40           & 27.04            & 4.29           & 0.49              & 24.11        & 26.55          \\ \hline
-\multicolumn{2}{|l|}{BT}                                                                       & 27.68           & 32.32            & 6.45           & 7.87              & 21.23        & 24.43          \\ \hline
-\multicolumn{2}{|l|}{SP}                                                                       & 20.52           & 24.73            & 5.21           & 2.78              & 15.31         & 21.95         \\ \hline
-\multicolumn{2}{|l|}{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} 
+\label{sec.concl}
+
 In this paper, a new online frequency selecting algorithm has been presented. It
-selects the  best possible  vector of frequency  scaling factors that  gives the
-maximum  distance  (optimal  trade-off)  between  the predicted  energy  and  the
+selects the best possible vector of frequency scaling factors that gives the
+maximum distance (optimal trade-off) between the predicted energy and the
 predicted performance curves for a heterogeneous platform. This algorithm uses a
-new  energy  model  for  measuring  and predicting  the  energy  of  distributed
-iterative  applications running  over heterogeneous  platforms. To  evaluate the
+new energy model for measuring and predicting the energy of distributed
+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 35\% 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 values of the static
-and  dynamic  powers  of the  CPUs.   Finally,  the  algorithm was  compared  to
-Spiliopoulos et al.  algorithm and  the results showed that it outperforms their
-algorithm in terms of energy-time trade-off.
+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
+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
+values of the static and dynamic powers of the CPUs.  Finally, the algorithm was
+compared to Spiliopoulos et al.  algorithm and the results showed that it
+outperforms their algorithm in terms of energy-time trade-off.
 
 In the near future, this method  will be applied to real heterogeneous platforms
 to evaluate its  performance in a real study case. It  would also be interesting
@@ -1195,9 +1249,9 @@ the iterative system.
 \section*{Acknowledgment}
 
 This work has been partially supported by the Labex
-ACTION project (contract âANR-11-LABX-01-01â). As a PhD student, 
+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. 
+Babylon (Iraq) for supporting his work.
 
 
 % trigger a \newpage just before the given reference
@@ -1209,7 +1263,7 @@ Babylon (Iraq) for supporting his work.
 \bibliographystyle{IEEEtran}
 \bibliography{IEEEabrv,my_reference}
 \end{document}
-   
+
 %%% Local Variables:
 %%% mode: latex
 %%% TeX-master: t
@@ -1219,6 +1273,5 @@ Babylon (Iraq) for supporting his work.
 
 % LocalWords:  Fanfakh Charr FIXME Tianhe DVFS HPC NAS NPB SMPI Rauber's Rauber
 % LocalWords:  CMOS EPSA Franche ComtÃ© Tflop RÃ¼nger IUT MarÃ©chal Juin cedex GPU
-% LocalWords:  de badri muslim MPI TcpOld TcmOld dNew dOld cp Sopt Tcp Tcm Ps
-% LocalWords:  Scp Fmax Fdiff SimGrid GFlops Xeon EP BT GPUs CPUs AMD
+% LocalWords:  de badri muslim MPI SimGrid GFlops Xeon EP BT GPUs CPUs AMD
 %  LocalWords:  Spiliopoulos scalability
