]> AND Private Git Repository - ThesisAhmed.git/blob - CHAPITRE_02.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
corrections
[ThesisAhmed.git] / CHAPITRE_02.tex
1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2 %%                          %%
3 %%       CHAPTER 04        %%
4 %%                          %%
5 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
6
7 \newcommand{\AG}[2][inline]{%
8   \todo[color=green!50,#1]{\sffamily\textbf{AG:} #2}\xspace}
9 \newcommand{\JC}[2][inline]{%
10   \todo[color=red!10,#1]{\sffamily\textbf{JC:} #2}\xspace}
11
12 \newcommand{\Xsub}[2]{{\ensuremath{#1_\mathit{#2}}}}
13
14 %% used to put some subscripts lower, and make them more legible
15 \newcommand{\fxheight}[1]{\ifx#1\relax\relax\else\rule{0pt}{1.52ex}#1\fi}
16
17 \newcommand{\Tcomp}[1][]{\Xsub{T}{comp}_{#1}}
18 \renewcommand*\npunitcommand[1]{\text{#1}}
19
20
21 \chapter{Energy optimization of homogeneous platform}
22 \label{ch2}
23
24 \section{Introduction}
25 \label{ch2:1}
26
27 Dynamic Voltage and Frequency Scaling (DVFS) can be applied to modern CPUs. This technique is 
28 usually used to reduce the energy consumed by a CPU while computing. Indeed,
29 power consumption by a processor  is exponentially related to its frequency. 
30 Thus, decreasing the frequency reduces the power consumed by the CPU. However, it can also 
31 significantly affect the performance of the executed program if it is compute bound. The performance degradation ratio can even be higher 
32 than the saved energy ratio. Therefore, the chosen frequency scaling factor must give the best possible
33 trade-off between energy reduction and performance. This chapter presents an algorithm 
34 that predicts the energy consumed with each frequency gear and selects the one that gives 
35 the best ratio between energy consumption reduction and performance. Furthermore, the main
36 objective of HPC systems is to execute as fast as possible the application. Therefore, our 
37 algorithm selects the scaling factor online with a very small overhead.  The proposed algorithm 
38 takes into account both the computation and communication times of the Message Passing 
39 Interface  (MPI) programs to choose the frequency scaling factor. 
40 This algorithm has the ability to predict both energy consumption and execution time over 
41 all available scaling factors.  The prediction achieved depends on some computing time information,
42 gathered at the beginning of the runtime.  We have applied this algorithm to the NAS parallel 
43 benchmarks (NPB v3.3) developed by the  NASA~\cite{ref65}.  Our experiments are executed using the simulator
44 SimGrid/SMPI v3.10~\cite{ref66} over an homogeneous
45 distributed memory architecture. 
46
47 This chapter is composed of two parts. In the first part, the proposed frequency scaling selection algorithm  uses the energy model of  Rauber and Rünger \cite{ref47} and  is compared to Rauber and Rünger's method.  The comparison results show that our algorithm gives better energy-time trade-off. In the second part,  a new energy model  that takes into account both the communication and computation times of the MPI programs running over a homogeneous cluster is developed.
48 It  also shows the new results obtained using the new energy model. The results are compared to the  ones given by Rauber and Rünger's energy model.  
49
50
51 This chapter is organized as follows:  Section~\ref{ch2:2} explains the execution
52 of parallel tasks and the sources of slack times.  It also presents an energy
53 model for homogeneous platforms from other researchers.  Section~\ref{ch2:3} describes how the
54 performance of MPI programs can be predicted.  Section~\ref{ch2:4} presents
55 the energy-performance objective function that maximizes the reduction of energy
56 consumption while minimizing the degradation of the program's performance.
57 Section~\ref{ch2:5} details the algorithm that returns the scaling factor that gives the best energy-performance 
58 trade-off for a parallel  application with iterations
59 Section~\ref{ch2:6} verifies the accuracy of the performance prediction model
60 and presents the results of the proposed algorithm.  It also shows the
61 comparison results between our method and other existing methods.  
62 Section~\ref{ch2:7} describes the new proposed energy consumption model for 
63 homogeneous platforms. Section~\ref{ch2:8} presents the experimental results 
64 of using the new energy model. Finally,  section~\ref{ch2:9} summarizes this chapter.
65
66
67 \section{Related works}
68 \label{sec.relwork}
69
70
71 In this section, some heuristics to compute the scaling factor are presented and
72 classified into two categories: offline and online methods.
73
74 \subsection{Offline scaling factor selection methods}
75
76 The offline scaling factor selection methods are executed before the runtime of
77 the program.  They return static scaling factor values to the processors
78 participating in the execution of the parallel program.  On the one hand, the
79 scaling factor values could be computed based on information retrieved by
80 analyzing the code of the program and the computing system that will execute it.
81 In~\cite{ref56}, Azevedo et al. detect during compilation the dependency points
82 between tasks in a multi-task program.  This information is then used to lower
83 the frequency of some processors in order to eliminate slack times.  A slack
84 time is the period of time during which a processor that has already finished
85 its computation, has to wait for a set of processors to finish their
86 computations and send their results to the waiting processor in order to
87 continue its task that is dependent on the results of computations being
88 executed on other processors.  Freeh et al. showed in~\cite{ref53} that the
89 communication times of MPI programs do not change when the frequency is scaled
90 down.  On the other hand, some offline scaling factor selection methods use the
91 information gathered from previous full or partial executions of the program. 
92 The whole program or a part of it  is usually executed over all the available frequency
93 gears and the execution time and the energy consumed with each frequency
94 gear are measured.  Then a heuristic or an exact method uses the retrieved
95 information to compute the values of the scaling factor for the processors.
96 In~\cite{ref57}, Xie et al. use an exact exponential breadth-first search algorithm
97 to compute the scaling factor values that give the optimal energy reduction
98 while respecting a deadline for a sequential program.  They also present a
99 linear heuristic that approximates the optimal solution.  In~\cite{ref58}, Rountree
100 et al. use a linear programming algorithm, while in~\cite{ref59,ref60}, Cochran et
101 al. use a multi-logistic regression algorithm for the same goal.  The main
102 drawback of these methods is that they all require executing the
103 whole program or, a part of it, on all frequency gears for each new instance of 
104 the same program.
105
106 \subsection{Online scaling factor selection methods}
107
108 The online scaling factor selection methods are executed during the runtime of
109 the program.  They are usually integrated into iterative programs where the same
110 block of instructions is executed many times.  During the first few iterations,
111 a lot of information are measured such as the execution time, the energy consumed
112 using a multimeter, the slack times, \dots{} Then a method will exploit these
113 measurements to compute the scaling factor values for each processor.  This
114 operation, measurements and computing new scaling factors, can be repeated as
115 much as needed if the iterations are not regular.  Kimura, Peraza, Yu-Liang et
116 al.~\cite{ref61,ref55,ref62} used many heuristics to select the appropriate scaling
117 factor values to eliminate the slack times during runtime.  However, as seen
118 in~\cite{ref63,ref64}, machine learning methods can take a lot of time to converge
119 when the number of available gears is big.  To reduce the impact of slack times,
120 in~\cite{ref54}, Lim et al. developed an algorithm that detects the communication
121 sections and changes the frequency during these sections only.  This approach
122 might change the frequency of each processor many times per iteration if an
123 iteration contains more than one communication section.  In~\cite{ref53}, Rauber and
124 Rünger used an analytical model that can predict the consumed energy and the
125 execution time for every frequency gear after measuring the consumed energy and
126 the execution time with the highest frequency gear.  These predictions may be
127 used to choose the optimal gear for each processor executing the parallel
128 program to reduce energy consumption.  To maintain the performance of the
129 parallel program , they set the processor with the biggest load to the highest
130 gear and then compute the scaling factor values for the rest of the processors.
131 Although this model was built for parallel architectures, it can be adapted to
132 distributed architectures by taking into account the communication times.  The
133 primary contribution of this chapter is to present a new online scaling factor
134 selection method which has the following characteristics:
135 \begin{enumerate}
136 \item It is based on both  Rauber and Rünger and the new  energy model to predict the energy consumption of the application with different frequency gears. 
137 \item It selects the frequency scaling factor for simultaneously optimizing
138   energy reduction and maintaining performance.
139 \item It is well adapted to distributed architectures because it takes into
140   account the communication time.
141 \item It is well adapted to distributed applications with imbalanced tasks.
142 \item It has a very small footprint when compared to other methods
143   (e.g.,~\cite{ref64}) and does not require profiling or training as
144   in~\cite{ref59,ref60}.
145 \end{enumerate}
146
147
148 \section{Execution time and energy consumption of parallel tasks running on a homogeneous platform}
149 \label{ch2:2}
150
151 \subsection{Parallel tasks execution on a homogeneous platform}
152 \label{ch2:2:1}
153 A homogeneous cluster consists in identical nodes in terms of hardware and
154 software.  Each node has its own memory and at least one processor which can be
155 a multi-core.  The nodes are connected via a high bandwidth network.  Tasks
156 executed on this model can be either synchronous or asynchronous.  In this chapter
157 we consider the execution of  synchronous tasks on distributed homogeneous
158 platform.  These tasks can synchronously exchange  data via message passing.
159
160
161
162 \begin{figure}[h!]
163 \centering
164 \centering
165 \includegraphics[scale=0.73]{fig/ch2/commtasks} 
166 \includegraphics[scale=0.73]{fig/ch2/compt}\\ ~ ~ ~ ~ ~  ~(a) ~ ~  ~ ~ ~  ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~(b)
167 \caption{Parallel tasks execution on a homogeneous platform (a) imbalanced communications and (b) imbalanced  
168 computations}
169 \label{fig:homo}
170 \end{figure}
171
172 The execution time of a task consists in the computation time and the
173 communication time.  Moreover, the synchronous communications between tasks can
174 lead to slack times while tasks wait at a synchronization barrier for other
175 tasks to finish their tasks (see figure~\ref{fig:homo}(a)).  The imbalanced
176 communications happen when nodes have to send/receive different amounts of data
177 or they communicate with different numbers of nodes.  Other sources of slack
178 times are imbalanced computations.  This happens when processing different
179 amounts of data on each processor (see figure~\ref{fig:homo}(b)).  In this case the
180 fastest tasks have to wait at the synchronization barrier for the slowest ones
181 to continue their computations.  In both cases the overall execution time of the program
182 is the execution time of the slowest task as in EQ~(\ref{eq:T1}).
183 \begin{equation}
184   \label{eq:T1}
185   \textit{Program Time} = \max_{i=1,2,\dots,N} T_i
186 \end{equation}
187 where $T_i$ is the execution time of task $i$ and all the tasks are executed
188 concurrently on different processors.
189
190 \subsection{Energy consumption model for a homogeneous platform}
191 \label{ch2:2:2}
192
193 The total energy  for a parallel homogeneous
194 platform, as presented by Rauber and Rünger~\cite{ref47}, can be written as a
195 function of the scaling factor $S$, as in EQ~\ref{eq:energy}.
196 Moreover, the scaling factor $S_1$ is the scaling factor which should be the
197 highest because they are proportional to the time values $T_i$.  Therefore, the scaling
198 factors of the others tasks $S_i$ are computed as in EQ~\ref{eq:si}.
199
200 \begin{equation}
201   \label{eq:si}
202   S_i = S \cdot \frac{T_1}{T_i}
203       = \frac{F_{max}}{F_{new}} \cdot \frac{T_1}{T_i},~{i=1,2,\dots,N}
204 \end{equation}
205
206 Rauber and Rünger's scaling factor selection
207 method  uses the same energy model.  In their method, the optimal scaling factor is
208 computed by minimizing the derivation of EQ~(\ref{eq:energy}) which produces
209 EQ~(\ref{eq:sopt}).
210
211 \begin{equation}
212   \label{eq:sopt}
213   S_\textit{opt} = \sqrt[3]{\frac{2}{N} \cdot \frac{P_\textit{dyn}}{P_\textit{static}} \cdot
214     \left( 1 + \sum_{i=2}^{N} \frac{T_i^3}{T_1^3} \right) }
215 \end{equation}
216
217 This model  computes the frequency scaling factor which minimizes the energy consumption of the parallel program.
218
219 \section{Performance evaluation of MPI programs}
220 \label{ch2:3}
221
222 The execution time of a parallel synchronous  application with iteration is equal
223 to the execution time of its slowest task as in figure~(\ref{fig:homo}).  
224 If there is no communication in the application and it is not data bounded, the execution time of this 
225 parallel application is linearly proportional to the operational frequency. Any 
226 DVFS operation for energy reduction increases the execution time of the parallel
227 program.  Therefore, the scaling factor $S$ is linearly proportional to the
228 execution time of the application.  However, in most MPI applications the processes exchange
229 data.  During these communications the processors involved remain idle during a synchronous communication.  For that reason, any change in the frequency has no
230 impact on the time of communication~\cite{ref53}.  The communication time for a
231 task is the summation of periods of time that begin with an MPI call for sending
232 or receiving a message until the message is synchronously sent or received.  To
233 be able to predict the execution time of MPI program, the communication time and
234 the computation time for the slowest task must be measured before scaling.  These
235 times are used to predict the execution time for any MPI program as a function
236 of the new scaling factor as in EQ~(\ref{eq:tnew}).
237 \begin{equation}
238   \label{eq:tnew}
239  \textit  T_\textit{new} = T_\textit{Max Comp Old} \cdot S + T_{\textit{Min Comm Old}}
240 \end{equation}
241 In this chapter, this prediction method is used to select the best scaling factor
242 for each processor as presented in the next section.
243
244
245
246 \section{Performance and energy reduction trade-off}
247 \label{ch2:4}
248 This section presents our method for choosing the  scaling factor that
249 gives the best tradeoff between energy reduction and performance. This method
250 takes into account the execution times for both computation and communication to
251 compute the scaling factor.  Since the energy consumption and the performance
252 are not measured using the same metric, a normalized value of both measurements
253 can be used to compare them.  The normalized energy is the ratio between the
254 consumed energy with scaled frequency and the consumed energy without scaled
255 frequency:
256
257 \begin{equation}
258   \label{eq:enorm}
259   E_\textit{Norm} = \frac{ E_\textit{Reduced}}{E_\textit{Original}} 
260          = \frac{P_\textit{dyn} \cdot S_1^{-2} \cdot
261                \left( T_1 + \sum_{i=2}^{N}\frac{T_i^3}{T_1^2}\right) +
262                P_\textit{static} \cdot T_1 \cdot S_1 \cdot N  }{
263               P_\textit{dyn} \cdot \left(T_1+\sum_{i=2}^{N}\frac{T_i^3}{T_1^2}\right) +
264               P_\textit{static} \cdot T_1 \cdot N }
265 \end{equation}
266 In the same way we can normalize the performance as follows:
267 \begin{equation}
268   \label{eq:pnorm}
269   T_\textit{Norm} = \frac{T_\textit{New}}{T_\textit{Old}}
270           = \frac{T_\textit{Max Comp Old} \cdot S +
271            T_\textit{Min Comm Old}}{T_\textit{Max Comp Old} +
272            T_\textit{Min Comm Old}}
273 \end{equation}
274
275 The relation between the execution time and the consumed energy of a program is nonlinear and complex. In consequences,  the relation between the consumed energy and the scaling factor is also nonlinear, for more details refer to~\cite{ref53}. The resulting normalized energy consumption curve and execution time curve, for different scaling factors, do not have the same direction see Figure~\ref{fig:rel}(b).  To tackle this problem and optimize both terms,  we inverse the equation of the normalized execution time which gives the normalized performance and is computed as follows:
276
277 \begin{equation}
278   \label{eq:pnorm_en}
279    P_\textit{Norm} = \frac{ T_\textit{old}}{ T_\textit{new}}
280                = \frac{T_\textit{max Comp Old} +
281                  T_\textit{min Comm Old}}{T_\textit{max Comp Old} \cdot S +
282                  T_\textit{min Comm Old}}
283 \end{equation}
284
285 \begin{figure}[h!]
286 \centering
287 \centering
288 \includegraphics[scale=1]{fig/ch2/file}\\~ ~ ~ ~ ~(a) \\
289 \includegraphics[scale=1]{fig/ch2/file3}\\~ ~ ~ ~ ~(b)
290 \caption{The energy and performance relation (a) Converted relation and (b) Real relation}
291 \label{fig:rel}
292 \end{figure}
293
294 Then, we can model our objective function as finding the maximum distance
295 between the energy curve EQ~\ref{eq:enorm} and the performance
296 curve EQ~\ref{eq:pnorm_en} over all available scaling factors.  This
297 represents the minimum energy consumption with minimum execution time (better
298 performance) at the same time, see Figure~\ref{fig:rel}(a).  Then
299 our objective function has the following form:
300
301 \begin{equation}
302   \label{eq:max1}
303    MaxDist = \max_{j=1,2,\dots,F}
304       (\overbrace{P_\textit{norm}(S_j)}^{\text{Maximize}} -
305        \overbrace{E_\textit{norm}(S_j)}^{\text{Minimize}} )
306 \end{equation}
307 where $F$ is the number of available frequencies. Then we can select the optimal
308 scaling factor that satisfies EQ~\ref{eq:max1}.  Our objective function can
309 work with any energy model or static power values stored in a data file.
310 Moreover, this function works in optimal way when the energy curve has a convex
311 form over the available frequency scaling factors as shown in~\cite{ref48,ref47,ref64}.
312
313 \section{Optimal scaling factor for performance and energy}
314 \label{ch2:5}
315
316
317 \begin{algorithm}[!t]
318   \caption{Scaling factor selection algorithm for a homogeneous cluster}
319   \label{EPSA}
320   \begin{algorithmic}[1]
321     \State  Initialize the variable $Dist=0$
322     \State Set dynamic and static power values.
323     \State Set $P_{states}$ to the number of available frequencies.
324     \State Set the variable $F_{new}$ to max. frequency,  $F_{new} = F_{max} $
325     \State Set the variable $F_{diff}$ to the difference between two successive
326            frequencies.
327     \For {$j:=1$   to   $P_{states} $}
328       \State $F_{new}=F_{new} - F_{diff} $
329       \State $S = \frac{F_\textit{max}}{F_\textit{new}}$
330       \State $S_i = S \cdot \frac{T_1}{T_i}
331                   = \frac{F_\textit{max}}{F_\textit{new}} \cdot \frac{T_1}{T_i}$
332              for $i=1,\dots,N$
333       \State $E_\textit{Norm} =
334           \frac{P_\textit{dyn} \cdot S_1^{-2} \cdot
335                   \left( T_1 + \sum_{i=2}^{N}\frac{T_i^3}{T_1^2}\right) +
336                   P_\textit{static} \cdot T_1 \cdot S_1 \cdot N }{
337                 P_\textit{dyn} \cdot
338                   \left(T_1+\sum_{i=2}^{N}\frac{T_i^3}{T_1^2}\right) +
339                   P_\textit{static} \cdot T_1 \cdot N }$
340       \State $P_{Norm}= \frac{T_{old}}{T_{new}}$
341       \If{$(P_{Norm}-E_{Norm} > Dist)$}
342         \State $S_{opt} = S$
343         \State $Dist = P_{Norm} - E_{Norm}$
344       \EndIf
345     \EndFor
346     \State  Return $S_{opt}$
347   \end{algorithmic}
348 \end{algorithm}
349
350
351 Algorithm~\ref{EPSA} computes the optimal scaling factor according to the
352 objective function described above.
353 The proposed algorithm works online during the execution time of the MPI
354 program.  It selects the optimal scaling factor after gathering the computation
355 and communication times from the program after one iteration.  Then the program
356 changes the new frequencies of the CPUs according to the computed scaling
357 factors. The  experiments conducted over a homogeneous cluster and described in
358 Section~\ref{ch2:6}, showed that this algorithm has a small execution time. It takes on average \np[$\mu$s]{1.52}  for 4 nodes and \np[$\mu$s]{6.65} for 32
359 nodes.  The algorithm complexity is $O(F\cdot N)$, where $F$ is the number of
360 available frequencies and $N$ is the number of computing nodes.  The algorithm
361 is called just once during the execution of the program.  The DVFS algorithm
362 ~\ref{dvfs} shows where and when the algorithm \ref{EPSA} is called in the MPI
363 program.
364
365
366
367 \begin{algorithm}[!t]
368   \caption{DVFS algorithm of homogeneous cluster}
369   \label{dvfs}
370   \begin{algorithmic}[1]
371     \For {$k:=1$ to \textit{some iterations}}
372       \State Computations section.
373       \State Communications section.
374       \If {$(k=1)$}
375         \State Gather all times of computation and  communication from each node.
376         \State Call algorithm~\ref{EPSA} with these times.
377         \State Compute the new frequency from the returned optimal scaling factor.
378         \State Set the new frequency to the CPU.
379       \EndIf
380     \EndFor
381   \end{algorithmic}
382 \end{algorithm}
383
384
385 After obtaining the optimal scaling factor, the program calculates the new
386 frequency $F_i$ for each task proportionally to its execution time, $T_i$.  By
387 substitution of EQ~(\ref{eq:s}) in EQ~(\ref{eq:si}), we can calculate the new
388 frequency $F_i$ as follows:
389 \begin{equation}
390   \label{eq:fi}
391   F_i = \frac{F_\textit{max} \cdot T_i}{S_\textit{opt} \cdot T_\textit{max}}
392 \end{equation}
393 According to this equation all the nodes may have the same frequency value if
394 they have balanced workloads, otherwise, they take different frequencies when
395 having imbalanced workloads.  Thus, EQ~(\ref{eq:fi}) adapts the frequency of the
396 CPU to the nodes' workloads to maintain the performance of the program.
397
398 \section{Experimental results}
399 \label{ch2:6}
400 Our experiments are executed on the simulator SimGrid/SMPI v3.10.  We configure
401 the simulator to use a homogeneous cluster with one core per node.  The detailed
402 characteristics of our platform file are shown in
403 table~(\ref{table:platform-homo}).  Each node in the cluster has 18 frequency values
404 from  2.5 GHz to 800 MHz with 100 MHz  difference between each
405 two successive frequencies.  The simulated network link is 1 GB Ethernet
406 (TCP/IP).  The backbone of the cluster simulates a high performance switch.
407
408 \begin{table}[!t]
409   \caption{Platform file parameters}
410   % title of Table
411   \centering
412   \begin{tabular}{|*{7}{l|}}
413     \hline
414     Max      & Min      & Backbone        & Backbone         & Link         & Link            & Sharing \\
415     Freq.    & Freq.    & Bandwidth       & Latency          & Bandwidth    & Latency         & Policy  \\
416     \hline
417     2.5      & 800       & 2.25  GBps     & 0.5  $\mu$s      & 1 GBps       &  50 $\mu$s      & Full    \\
418     GHz      & MHz      &                 &                  &              &                 & Duplex  \\
419     \hline
420   \end{tabular}
421   \label{table:platform-homo}
422 \end{table}
423
424
425 \subsection{Performance prediction verification}
426 \label{ch2:6:1}
427 In this section, the precision of the proposed performance prediction method 
428 based on EQ~(\ref{eq:tnew}) is evaluated by applying it to the NAS benchmarks.  
429 The NAS programs are executed with the class B option to compare the real execution 
430 time with the predicted execution time.  Each program runs offline with all available
431 scaling factors on 8 or 9 nodes (depending on the benchmark) to produce real
432 execution time values.  These scaling factors are computed by dividing the
433 maximum frequency by the new one see EQ~(\ref{eq:s}).
434 \begin{figure*}[h!]
435   \centering 
436   \centering 
437   \centering
438   \includegraphics[width=.49\textwidth]{fig/ch2/cg_per}
439   \includegraphics[width=.49\textwidth]{fig/ch2/mg_pre}
440   \includegraphics[width=.49\textwidth]{fig/ch2/bt_pre}
441   \includegraphics[width=.49\textwidth]{fig/ch2/lu_pre}
442   \caption{Comparing predicted to real execution time}
443   \label{fig:pred}
444 \end{figure*}
445 %see Figure~\ref{fig:pred}
446 In our cluster there are 18 available frequency states for each processor.  This
447 leads to 18 run states for each program.  Seven MPI programs of the NAS
448 parallel benchmarks were used: CG, MG, EP, FT, BT, LU and SP. Table \ref{table:NAS-dec} shows 
449 the description of these seven benchmarks. Some of these benchmarks are considered  MPI parallel applications with synchronous iterations  or iterative applications that repeat the same block of instructions until convergence. 
450 However,  the proposed method can be applied to any application that executes the same block
451 of instructions many times and it is not limited to iterative methods. 
452 Figure~(\ref{fig:pred}) presents plots of the real execution times compared to the simulated ones.  The maximum
453 normalized error between these two execution times varies between 0.0073 to
454 0.031 depending on the executed benchmark.  The smallest prediction error
455 was for CG and the worst one was for LU.
456
457 \begin{table}[!t]
458 \centering
459 \caption{NAS Benchmarks description}
460 \label{table:NAS-dec}
461 \begin{tabular}{|l|l|l|}
462 \hline
463 Benchmark & Full Name                                                                     & Description                                                                                                                                                                                                                                                                     \\ \hline
464 CG        & Conjugate Gradiant                                                            & \begin{tabular}[c]{@{}l@{}}
465 It solves a system of linear equations by estimating\\ the smallest eigenvalue of a large sparse  matrix \end{tabular}\\ \hline
466
467 MG        & MultiGrid                                                                     & \begin{tabular}[c]{@{}l@{}}It uses the multigrid method to approximate the solution \\of a three-dimensional discrete Poisson equation\end{tabular}                                                                                                                     
468  \\ \hline
469 EP       & Embarrassingly Parallel                                                       & \begin{tabular}[c]{@{}l@{}} It applies the Marsaglia polar method to randomly \\generates independent Gaussian variates
470 \end{tabular}                                                                                                                                                       \\ \hline
471 FT        & Fast Fourier Transform                                                        & \begin{tabular}[c]{@{}l@{}}It uses the fast Fourier transform to solve a \\ three-dimensional partial differential equation
472
473 \end{tabular}                                                                                                                               \\ \hline
474 BT        & Block Tridiagonal                                                             & \multirow{3}{*}{\begin{tabular}[c]{@{}l@{}} \\They solve nonlinear partial differential equations \end{tabular}} \\ \cline{1-2}
475 LU        & \begin{tabular}[c]{@{}l@{}}Lower-Upper symmetric \\ Gauss-Seidel\end{tabular} &                                                                                                                                                                                                                                                                                 \\ \cline{1-2}
476 SP        & \begin{tabular}[c]{@{}l@{}}Scalar Pentadiagonal\end{tabular}               &                                                                                                                                                                                                                                                                                 \\ \hline
477 \end{tabular}
478 \end{table}
479
480 \subsection{The experimental results for the scaling algorithm }
481 \label{ch2:6:2}
482 The proposed algorithm was applied to seven MPI programs of the NAS benchmarks
483 (EP, CG, MG, FT, BT, LU and SP) which were run with three classes (A, B and C).
484 For each instance, the benchmarks were executed on a number of processors
485 proportional to the size of the class.  Each class represents the problem size in 
486 ascending order from  class A to C.  The classes A, B and C were executed on 4, 8 or 9 and 16 nodes respectively.  The energy consumption for all the NAS MPI programs was measured while assuming that the dynamic power with
487 the highest frequency is equal to 20 W and the static power  is equal to
488 4 W for all the experiments.  These power values were also used by Rauber and
489 Rünger in~\cite{ref47}.  The results showed that the algorithm selected different
490 scaling factors for each program depending on the communication features of the
491 program as in the plots~(\ref{fig:nas}).  These plots illustrate that there are
492 different distances between the normalized energy and the normalized 
493 performance curves, because there are different communication features for each
494 benchmark.  When there are little or no communications, the 
495 performance curve is very close to the energy curve.  Then the distance between
496 the two curves is very small.  This leads to small energy savings.  The opposite
497 happens when there are a lot of communication, the distance between the two
498 curves is big.  This leads to more energy savings (e.g. CG and FT), see
499 table~(\ref{table:factors results}).  All the discovered frequency scaling factors
500 optimize both the energy and the performance simultaneously for all the NAS
501 benchmarks.  In table~(\ref{table:factors results}), the optimal
502 scaling factors results for each benchmark running class C are presented.  These scaling
503 factors give the maximum energy saving percentage and the minimum performance
504 degradation percentage at the same time from all available scaling factors.
505 \begin{figure*}[h!]
506   \centering
507   \includegraphics[width=.49\textwidth]{fig/ch2/ep}
508   \includegraphics[width=.49\textwidth]{fig/ch2/cg}
509   \includegraphics[width=.49\textwidth]{fig/ch2/sp}
510   \includegraphics[width=.49\textwidth]{fig/ch2/lu}
511   \includegraphics[width=.49\textwidth]{fig/ch2/bt}
512   \includegraphics[width=.49\textwidth]{fig/ch2/ft}
513   \caption{Optimal scaling factors for the predicted energy and performance of NAS benchmarks}
514   \label{fig:nas}
515 \end{figure*}
516 \begin{table}[htb]
517   \caption{The scaling factors results}
518   % title of Table
519   \centering
520   \begin{tabular}{|l|*{4}{r|}}
521     \hline
522     Program & Optimal        & Energy    & Performance    & Energy-Perf. \\
523     Name    & Scaling Factor & Saving \% & Degradation \% & Distance     \\
524     \hline
525     CG      & 1.56           & 39.23     & 14.88          & 24.35 \\
526     \hline
527     MG      & 1.47           & 34.97     & 21.70          & 13.27 \\
528     \hline
529     EP      & 1.04           & 22.14     & 20.73          &  1.41 \\
530     \hline
531     LU      & 1.38           & 35.83     & 22.49          & 13.34 \\
532     \hline
533     BT      & 1.31           & 29.60     & 21.28          &  8.32 \\
534     \hline
535     SP      & 1.38           & 33.48     & 21.36          & 12.12 \\
536     \hline
537     FT      & 1.47           & 34.72     & 19.00          & 15.72 \\
538     \hline
539   \end{tabular}
540   \label{table:factors results}
541   % is used to refer this table in the text
542 \end{table}
543
544 As shown in table~(\ref{table:factors results}), when the optimal scaling
545 factor has a big value we can gain more energy savings  as in CG and
546 FT benchmarks.  The opposite happens when the optimal scaling factor has a  small value as in BT and EP benchmarks.  Our algorithm selects a big scaling factor value when the
547 communication and  other slacks times are big.  In EP there are no communication inside the iterations, which leads our algorithm to select smaller scaling factors (inducing smaller energy savings).
548
549
550 \subsection{Results comparison}
551 \label{ch2:6:3}
552 In this section, we compare our scaling factor selection method with the Rauber and
553 Rünger's method~\cite{ref47}.  They had two scenarios, the first is to reduce energy
554 to the optimal level without considering the performance as in
555 EQ~(\ref{eq:sopt}).  We refer to this scenario as $R_{E}$.  The second scenario
556 is similar to the first except setting the slower task to the maximum frequency
557 (the scale $S=1$) to keep the performance from degradation as mush as
558 possible.  We refer to this scenario as $R_{E-P}$ and to our
559 algorithm as EPSA (Energy to Performance Scaling Algorithm).  The comparison is
560 made in table ~\ref{table:compareC}.  This table shows the results of our method and
561 the Rauber and Rünger's scenarios for all the NAS benchmarks programs for class C.
562
563 \begin{table}[h!]
564   \caption{Comparing results for the NAS class C}
565   % title of Table
566   \centering
567   \begin{tabular}{|l|l|*{4}{r|}}
568     \hline
569     Method    & Program & Factor & Energy    & Performance    & Energy-Perf. \\
570     Name      & Name    & Value  & Saving \% & Degradation \% & Distance     \\
571     \hline
572     % \rowcolor[gray]{0.85}
573     $EPSA$    & CG      & 1.56   & 39.23     & 14.88          &  24.35 \\ \hline
574     $R_{E-P}$ & CG      & 2.15   & 45.36     & 25.89          &  19.47 \\ \hline
575     $R_{E}$   & CG      & 2.15   & 45.36     & 26.70          &  18.66 \\ \hline
576
577     $EPSA$    & MG      & 1.47   & 34.97     & 21.69          &  13.27 \\ \hline
578     $R_{E-P}$ & MG      & 2.15   & 43.65     & 40.45          &   3.20 \\ \hline
579     $R_{E}$   & MG      & 2.15   & 43.64     & 41.38          &   2.26 \\ \hline
580
581     $EPSA$    & EP      & 1.04   & 22.14     & 20.73          &   1.41 \\ \hline
582     $R_{E-P}$ & EP      & 1.92   & 39.40     & 56.33          & -16.93 \\ \hline
583     $R_{E}$   & EP      & 1.92   & 38.10     & 56.35          & -18.25 \\ \hline
584
585     $EPSA$    & LU      & 1.38   & 35.83     & 22.49          &  13.34 \\ \hline
586     $R_{E-P}$ & LU      & 2.15   & 44.97     & 41.00          &   3.97 \\ \hline
587     $R_{E}$   & LU      & 2.15   & 44.97     & 41.80          &   3.17 \\ \hline
588
589     $EPSA$    & BT      & 1.31   & 29.60     & 21.28          &   8.32 \\ \hline
590     $R_{E-P}$ & BT      & 2.13   & 45.60     & 49.84          &  -4.24 \\ \hline
591     $R_{E}$   & BT      & 2.13   & 44.90     & 55.16          & -10.26 \\ \hline
592
593     $EPSA$    & SP      & 1.38   & 33.48     & 21.35          &  12.12 \\ \hline
594     $R_{E-P}$ & SP      & 2.10   & 45.69     & 43.60          &   2.09 \\ \hline
595     $R_{E}$   & SP      & 2.10   & 45.75     & 44.10          &   1.65 \\ \hline
596
597     $EPSA$    & FT      & 1.47   & 34.72     & 19.00          &  15.72 \\ \hline
598     $R_{E-P}$ & FT      & 2.04   & 39.40     & 37.10          &   2.30 \\ \hline
599     $R_{E}$   & FT      & 2.04   & 39.35     & 37.70          &   1.65 \\ \hline
600   \end{tabular}
601   \label{table:compareC}
602   % is used to refer this table in the text
603 \end{table}
604
605
606 \begin{figure*}[h!]
607   \centering
608  % \includegraphics[width=.6\textwidth]{fig/ch2/classA.eps}
609   % \includegraphics[width=.6\textwidth]{fig/ch2/classB.eps}
610   \includegraphics[width=.7\textwidth]{fig/ch2/classC.eps}
611   \caption{Comparing our method to Rauber and Rünger's methods}
612   \label{fig:compare}
613 \end{figure*}
614
615
616
617 As shown in the table~\ref{table:compareC}, the ($R_{E-P}$) method outperforms the ($R_{E}$)
618 method in terms of performance and energy reduction.  The ($R_{E-P}$) method
619 also gives better energy savings than our method.  However, although our scaling
620 factor is not optimal for energy reduction, the results in these tables prove
621 that our algorithm returns the best scaling factor that satisfy our objective
622 method: the largest distance between energy reduction and performance
623 degradation. Figure~\ref{fig:compare}  illustrates even better the distance between the energy reduction and performance degradation. The negative values mean that one of
624 the two objectives (energy or performance) has been degraded more than the 
625 other.  The positive trade-offs with the highest values lead to maximum energy
626 savings while keeping the performance degradation as low as possible.  Our
627 algorithm always gives the highest positive energy to performance trade-offs
628 while the Rauber and Rünger's method, ($R_{E-P}$), gives sometimes negative
629 trade-offs such as for BT and EP.
630
631
632 \section{The new energy model for a homogeneous cluster}
633 \label{ch2:7}
634 As mentioned in chapter \ref{ch1} section \ref{ch1:3}, the power consumed by a processor is divided 
635 into two power metrics: the static and the dynamic power. The  first power metric  is
636 consumed as long as the computing unit is on, while the other one is consumed when the processor is doing the computations. Consequentially, the energy consumed by an individual processor
637 to execute a given program can be computed as follows:
638
639
640 \begin{equation}
641   \label{eq:eind1}
642    E_\textit{ind} =  P_\textit{dyn} \cdot T_{Comp} + P_\textit{static} \cdot T
643 \end{equation}
644
645 where $T$ is the execution time of the program, $T_{Comp}$ is the computation
646 time and $T_{Comp} \leq T$.  $T_{Comp}$ may be equal to $T$ if there is no
647 communication, no slack time and no synchronization.
648
649 Applying a DVFS operation leads to a new frequency state which is represented by the frequency scaling factor $S$, computed as in the equation \ref{eq:s}. According to  Rauber and Rünger's energy model \ref{eq:energy}, the dynamic energy is consumed during the overall program's execution time. This assumption is not precise because the CPU  only consumes the dynamic power during computation time. Moreover, the CPU involved remains idle during the communication times and only consumes the static power, see \cite{ref53}. We have also conducted some experiments over a real homogeneous cluster where some MPI programs of the NAS  benchmarks were executed while varying the CPUs frequencies at each execution. The results prove that  changing the frequency does not effect on the communication times of these programs.  Therefore, the frequency scaling factor $S$ can increase the computation times  proportionally to its value,  and does not  effect the communication times. This assumption consort with the used performance prediction model \ref{eq:tnew}. This model is evaluated and its prediction accuracy is showed in section \ref{ch2:6:1}. Therefore, the new dynamic energy is the dynamic power multiplied by the new time of computation and is given by the following equation:
650
651 \begin{equation}
652   \label{eq:Edyn_new}
653    Ed_{New} = Pd_{Old} \cdot S^{-3} \cdot (T_{comp} \cdot S)= S^{-2} \cdot Pd_{Old} \cdot  T_{comp}
654 \end{equation}
655
656 The static power is related to the power leakage of the CPU and is consumed
657 during computation and even when idle. As in~\cite{ref47,ref46},
658 the static power of a processor is considered as constant during idle and
659 computation periods, and for all its available frequencies.  The static energy
660 is the static power multiplied by the execution time of the program.  According
661 to the execution time model in (\ref{eq:tnew}), the execution time of the
662 program is the sum of the computation and the communication times. The
663 computation time is linearly related to the frequency scaling factor, while this
664 scaling factor does not affect the communication time.  Then, the static energy of a
665 processor after scaling its frequency is computed as follows:
666 \begin{equation}
667   \label{eq:Estatic_new}
668   Es = P_{static} \cdot (T_{comp} \cdot S  + T_{comm})
669 \end{equation}
670
671 In particular, in a homogeneous cluster all the computing nodes have the same specification and thus their CPUs have similar frequencies gears. The execution time of the MPI application is the execution time of the slowest task as shown in section \ref{ch2:2:1}. Therefore, the frequency scaling factor $S$ of the slowest task can be used to modelize the  energy consumption of the parallel application.
672 The dynamic energy consumed by $N$  parallel tasks  is the summation of all the dynamic energies of  all tasks during the computation time $\Tcomp[i]$  of  each task. The static energy of each task is the static power consumed during the execution time of the slower task because all the tasks are synchronised and have the same execution time.
673 Therefore, the energy consumption model of $N$ parallel task executed  synchronously over a homogeneous platforms can be represented as in \ref{eq:e-new}. 
674
675 \begin{equation}
676   \label{eq:e-new}
677  E_{new} = \sum_{i=1}^{N} {(S^{-2} \cdot Pd \cdot  \Tcomp[i])}  + 
678   ( Ps \cdot  ( T_\textit{Max Comp Old} \cdot S + T_{\textit{Min Comm Old}} ) )  \cdot N
679 \end{equation}
680  
681 According to this model, the frequency scaling factor $S$ reduces the energy consumption of the homogeneous architecture by a factor of $S^{-2}$ and increases the execution time by a factor of  $S$.
682 This model can be used to predict the energy consumption of the message passing   applications with synchronous iterations after gathering the computation and communication times of the first iteration.
683 Furthermore, it can be used to measure the energy consumption of the parallel  application with iterations  by multiplying the energy consumed of all tasks in  one iteration  by the number of the iterations. 
684
685 This model is used by the algorithm \ref{EPSA}  to predict the energy consumption and to select the optimal frequency scaling factor. The new frequency $F_i$ can be computed as in \ref{eq:fi} while using the new selected frequency scaling factor.  
686 In the next section,  algorithm \ref{EPSA} is re-evaluated while using this new energy model and the new results are presented.
687
688 \section{The experimental results using the new energy model}
689 \label{ch2:8}
690
691 This section presents the results of applying the frequency selection algorithm \ref{EPSA} using the new proposed energy model \ref{eq:e-new} to NAS parallel benchmarks.
692 The class C of the benchmarks was executed on a homogeneous architecture composed of 16 nodes and simulated by SimGrid. The same  static and dynamic power values were used as in section \ref{ch2:6:2}. Figure \ref{fig:energy_con} presents the energy consumption of the NAS benchmarks class C using the new energy model and the Rauber and Rünger's model. The energy consumptions of both models are computed using similar parameters:  frequency scaling factors, dynamic and static powers values. As shown in this figure,  the majority  of the benchmarks  consumes less energy using the new model than when using the Rauber and Rünger's model.
693 Two reasons explain these differences in the energy consumptions: the first one is related to the dynamic power consumption, where the new energy model ensures that this power metric is only consumed  during the computation time, while  the other model assumes that the dynamic power is consumed during both computation and communication times and thus increasing the dynamic energy consumption.
694 The second reason is related to the execution time. In the new model only the computation times are increased when the frequency of a processor is scaled down, while
695 Rauber and Rünger's model indicates that both the computation and communication times 
696 are  increased according to the scaling factor and hence more static energy  is consumed.  Therefore, the MPI programs that have big communication times,  have bigger  energy consumption values using  Rauber and Rünger's model  when compared to the new model as for the CG, SP, LU and FT benchmarks. Whereas, if the MPI programs have very small communication times, their computed energy values have very small differences  using both models such as for the MG and BT benchmarks, or they are identical such as for the  EP benchmark where there is no communication and no idle times. 
697
698
699 \begin{figure*}[h!]
700   \centering
701   \includegraphics[width=.7\textwidth]{fig/ch2/energy_con.eps}
702   \caption{Comparing the energy consumptions estimated using Rauber energy  model and our own}
703   \label{fig:energy_con}
704 \end{figure*}
705 \begin{table}[h!]
706 \centering
707 \begin{tabular}{|l|l|l|l|l|l|l|}
708 \hline
709 \multicolumn{1}{|c|}{\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}Method\\ Name\end{tabular}}} & \multicolumn{3}{c|}{Rauber  Energy Model Results}                                                                                                                                            & \multicolumn{3}{c|}{New Energy Model Results}                                                                                                                                                \\ \cline{2-7} 
710 \multicolumn{1}{|c|}{}                                                                          & \begin{tabular}[c]{@{}l@{}}Scaling\\ Factors\end{tabular} & \begin{tabular}[c]{@{}l@{}}Energy \\ Saving\%\end{tabular} & \begin{tabular}[c]{@{}l@{}}Performance\\ Degradation\%\end{tabular} & \begin{tabular}[c]{@{}l@{}}Scaling\\ Factors\end{tabular} & \begin{tabular}[c]{@{}l@{}}Energy \\ Saving\%\end{tabular} & \begin{tabular}[c]{@{}l@{}}Performance\\ Degradation\%\end{tabular} \\ \hline
711
712 CG      & 1.56      & 39.23       & 14.88       & 1.47       & 30.20       & 13.56     \\ \hline
713 MG      & 1.47      & 34.97       & 21.69       & 1.38       & 30.04       & 16.48      \\ \hline
714 EP      & 1.04      & 22.14       & 20.73       & 1.04       & 22.14       & 20.73       \\ \hline
715 LU      & 1.38      & 35.83       & 22.49       & 1.31       & 29.15       & 18.03       \\ \hline
716 BT      & 1.31      & 29.60       & 21.53       & 1.31       & 28.75       & 21.55        \\ \hline
717 SP      & 1.38      & 33.48       & 21.35       & 1.31       & 28.93       & 14.83        \\ \hline
718 FT      & 1.47      & 34.72       & 19.00       & 1.38       & 29.94       & 17.43        \\ \hline
719 \end{tabular}
720 \caption{The Results of NAS Parallel Benchmarks running on 16 nodes}
721 \label{table:new-res}
722 \end{table}
723
724 Table \ref{table:new-res} shows  the energy saving and performance degradation percentages when applying the frequency selecting algorithm  using the new proposed  energy model. It also presents the new selected frequency scaling factors and compares them to the ones used by the Rauber and Rünger's model. It shows  that the new selected frequency scaling factors are smaller than  those selected using the other model because the predicted energies by the new energy model are smaller.
725 Consequently, less energy savings and performance degradation percentages are produced according to 
726 these smaller frequency scaling factors such as for the  CG, MG, LU, SP and FT benchmarks. While in the BT and EP benchmarks where there are very small or no communication times, similar scaling factors are selected because the predicted energies by the two models are approximately equivalent. 
727
728 Therefore, the new proposed energy model is more accurate than Rauber and Rünger's energy
729 model, because  it takes into consideration both the communication and idle times in addition to
730 the computation times of  message passing programs running over homogeneous clusters. 
731 The scaling factor selection algorithm can work with any energy model and  it selects  the scaling factor values according to the predicted energy values. 
732
733 \section{Conclusion}
734 \label{ch2:9}
735 In this chapter, a new online scaling factor selection method
736 that optimizes simultaneously the energy and performance of a distributed 
737 application running on a homogeneous cluster have been presented .  It uses the computation and
738 communication times measured at the first iteration to predict the energy
739 consumption and the performance of the parallel application at every available
740 frequency.  Then, it selects the scaling factor that gives the best trade-off
741 between energy reduction and performance which is the maximum distance between
742 the energy and the performance curves.  To evaluate this method, we
743 have applied it to the NAS benchmarks and it was compared to the Rauber and Rünger's 
744 method while being executed on the SimGrid simulator.  The results showed that
745 our method, outperforms the Rauber and Rünger's method in terms of energy-performance
746 ratio. Finally, this chapter presents a new energy consumption model for  parallel
747   applications with synchronous iterations running on homogeneous clusters. This model takes into consideration 
748 both  the computation and communication times and their relation with the frequency scaling 
749 factor. The results obtained using the new energy model have shown that different frequency scaling factors 
750 were  selected which gave new experimental results that are more accurate and realistic.