From 2c9279323393cded909289eb5e2718a950798e62 Mon Sep 17 00:00:00 2001 From: Arnaud Giersch Date: Thu, 23 Oct 2014 22:15:38 +0200 Subject: [PATCH 1/1] Quick spell check. --- Heter_paper.tex | 86 ++++++++++++++++++++++++++++++++++++++----------- 1 file changed, 67 insertions(+), 19 deletions(-) diff --git a/Heter_paper.tex b/Heter_paper.tex index a569aaa..c5f885a 100644 --- a/Heter_paper.tex +++ b/Heter_paper.tex @@ -98,7 +98,14 @@ % paper in homogeneous clusters} \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 heterogeneous platforms. We define a heterogeneous platform as a collection of heterogeneous computing nodes interconnected via a high speed homogeneous network. Therefore, each node has different characteristics such as computing power (FLOPS), energy consumption, cpu's frequency range, ... but they all have the same network bandwidth and latency. + +In this paper, we are interested in reducing the energy consumption of message +passing distributed iterative synchronous applications running over +heterogeneous platforms. We define a heterogeneous platform as a collection of +heterogeneous computing nodes interconnected via a high speed homogeneous +network. Therefore, each node has different characteristics such as computing +power (FLOPS), energy consumption, CPU's frequency range, ... but they all have +the same network bandwidth and latency. \begin{figure}[t] @@ -294,8 +301,28 @@ form over the available frequency scaling factors as shown in~\cite{15,3,19}. \section{The heterogeneous scaling algorithm } \label{sec.optim} -In this section we proposed an heterogeneous scaling algorithm, (figure~\ref{HSA}), that selects the optimal set of scaling factors from each node. -The algorithm is numerates the suitable range of available scaling factors for each node in the heterogeneous cluster, returns a set of optimal frequency scaling factors for each node. Using heterogeneous cluster is produces different workloads for each node. Therefore, the fastest nodes waiting at the barrier for the slowest nodes to finish there work as in figure (\ref{fig:heter}). Our algorithm takes into account these imbalanced workloads when is starts to search for selecting the best scaling factors. So, the algorithm is selecting the initial frequencies values for each node proportional to the times of computations that gathered from the first iteration. As an example in figure (\ref{fig:st_freq}), the algorithm don't test the first frequencies of the fastest nodes until it converge their frequencies to the frequency of the slowest node. If the algorithm is starts test changing the frequency of the slowest nodes from beginning, we are loosing performance and then not selecting the best tradeoff (the distance). This case will be similar to the homogeneous cluster when all nodes scales their frequencies together from the beginning. In this case there is a small distance between energy and performance curves, for example see the figure(\ref{fig:r1}). Then the algorithm searching for optimal frequency scaling factor from the selected frequencies until the last available ones. + +In this section we proposed an heterogeneous scaling algorithm, +(figure~\ref{HSA}), that selects the optimal set of scaling factors from each +node. The algorithm is numerates the suitable range of available scaling +factors for each node in the heterogeneous cluster, returns a set of optimal +frequency scaling factors for each node. Using heterogeneous cluster is produces +different workloads for each node. Therefore, the fastest nodes waiting at the +barrier for the slowest nodes to finish there work as in figure +(\ref{fig:heter}). Our algorithm takes into account these imbalanced workloads +when is starts to search for selecting the best scaling factors. So, the +algorithm is selecting the initial frequencies values for each node proportional +to the times of computations that gathered from the first iteration. As an +example in figure (\ref{fig:st_freq}), the algorithm don't test the first +frequencies of the fastest nodes until it converge their frequencies to the +frequency of the slowest node. If the algorithm is starts test changing the +frequency of the slowest nodes from beginning, we are loosing performance and +then not selecting the best trade-off (the distance). This case will be similar +to the homogeneous cluster when all nodes scales their frequencies together from +the beginning. In this case there is a small distance between energy and +performance curves, for example see the figure(\ref{fig:r1}). Then the +algorithm searching for optimal frequency scaling factor from the selected +frequencies until the last available ones. \begin{figure}[t] \centering \includegraphics[scale=0.5]{fig/start_freq} @@ -359,16 +386,24 @@ maximum frequency of node $i$ and the computation scaling factor $Scp_i$ as fol \caption{Heterogeneous scaling algorithm} \label{HSA} \end{figure} -When the initial frequencies are computed the algorithm numerates all available scaling factors starting from these frequencies until all nodes reach their -minimum frequencies. At each iteration the algorithm remains the frequency of the slowest node without change and scaling the frequency of the other nodes. This is gives better performance and energy tradeoff. -The proposed algorithm works online during the execution time of the MPI -program. Its returns a set of optimal frequency scaling factors $Sopt_i$ depending on the objective function EQ(\ref{eq:max}). The program changes the new frequencies of the CPUs according to the computed scaling factors. This algorithm has a small execution time: -for an heterogeneous cluster composed of four different types of nodes having the characteristics presented in -table~(\ref{table:platform}), it takes \np[ms]{0.04} on average for 4 nodes and -\np[ms]{0.1} on average for 128 nodes. 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 on average from 12 to 20 iterations for all the NAS benchmark on class C to selects the best set of frequency scaling factors. Its called just once during the execution of the program. The DVFS figure~(\ref{dvfs}) shows where and when the algorithm is -called in the MPI program. +When the initial frequencies are computed the algorithm numerates all available +scaling factors starting from these frequencies until all nodes reach their +minimum frequencies. At each iteration the algorithm remains the frequency of +the slowest node without change and scaling the frequency of the other +nodes. This is gives better performance and energy trade-off. The proposed +algorithm works online during the execution time of the MPI program. Its +returns a set of optimal frequency scaling factors $Sopt_i$ depending on the +objective function EQ(\ref{eq:max}). The program changes the new frequencies of +the CPUs according to the computed scaling factors. This algorithm has a small +execution time: for an heterogeneous cluster composed of four different types of +nodes having the characteristics presented in table~(\ref{table:platform}), it +takes \np[ms]{0.04} on average for 4 nodes and \np[ms]{0.1} on average for 128 +nodes. 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 on average from 12 to 20 iterations for all the NAS benchmark on class C +to selects the best set of frequency scaling factors. Its called just once +during the execution of the program. The DVFS figure~(\ref{dvfs}) shows where +and when the algorithm is called in the MPI program. \begin{figure}[tp] \begin{algorithmic}[1] % \footnotesize @@ -392,7 +427,7 @@ called in the MPI program. \section{Experimental results} \label{sec.expe} -The experiments of this work are executed on the simulator Simgrid/SMPI +The experiments of this work are executed on the simulator SimGrid/SMPI v3.10~\cite{casanova+giersch+legrand+al.2014.versatile}. We configure the simulator to use a heterogeneous cluster with one core per node. The proposed heterogeneous cluster has four different types of nodes. Each node in cluster @@ -409,7 +444,7 @@ and static power values proportional to their performance/GFlops, for more details see the Intel data sheets in \cite{47}. Each node has a percentage of 80\% for dynamic power and 20\% for static power from the hole power consumption, the same assumption is made in \cite{45,3}. These nodes are -connected via an ethernet network with 1 Gbit/s bandwidth. +connected via an Ethernet network with 1 Gbit/s bandwidth. \begin{table}[htb] \caption{Heterogeneous nodes characteristics} % title of Table @@ -622,13 +657,24 @@ The results of applying the proposed scaling algorithm to NAS benchmarks is demo \subfloat[Imbalanced nodes type scenario]{% \includegraphics[width=.23185\textwidth]{fig/avg_neq}\label{fig:avg_neq}} \label{fig:avg} - \caption{The average of energy and performance for all Nas benchmarks running with difference number of nodes} + \caption{The average of energy and performance for all NAS benchmarks running with difference number of nodes} \end{figure} In the NAS benchmarks there are some programs executed on different number of nodes. The benchmarks CG, MG, LU and FT executed on 2 to a power of (1, 2, 4, 8, ...) of nodes. The other benchmarks such as BT and SP executed on 2 to a power of (1, 2, 4, 9, ...) of nodes. We are take the average of energy saving, performance degradation and distances for all results of NAS benchmarks. The average of these three objectives are plotted to the number of nodes as in plots (\ref{fig:avg_eq} and \ref{fig:avg_neq}). In CG, MG, LU, and FT benchmarks the average of energy saving is decreased when the number of nodes is increased due to the increasing in the communication times as mentioned before. Thus, the average of distances (our objective function) is decreased linearly with energy saving while keeping the average of performance degradation the same. In BT and SP benchmarks, the average of energy saving is not decreased significantly compare to other benchmarks when the number of nodes is increased. Nevertheless, the average of performance degradation approximately still the same ratio. This difference is depends on the characteristics of the benchmarks such as the computation to communication ratio that has. \subsection{The results for different powers scenarios} -The results of the previous section are obtained using a percentage of 80\% for dynamic power and 20\% for static power of total power consumption. In this section we are change these ratio by using two others scenarios. Because is interested to measure the ability of the proposed algorithm to changes it behaviour when these power ratios are changed. In fact, we are use two different scenarios for dynamic and static power ratios in addition to the previous scenario in section (\ref{sec.res}). Therefore, we have three different scenarios for three different dynamic and static power ratios refer to as: 70\%-20\%, 80\%-20\% and 90\%-10\% scenario. The results of these scenarios running NAS benchmarks class C on 8 or 9 nodes are place in the tables (\ref{table:res_s1} and \ref{table:res_s2}). + +The results of the previous section are obtained using a percentage of 80\% for +dynamic power and 20\% for static power of total power consumption. In this +section we are change these ratio by using two others scenarios. Because is +interested to measure the ability of the proposed algorithm to changes it +behavior when these power ratios are changed. In fact, we are use two different +scenarios for dynamic and static power ratios in addition to the previous +scenario in section (\ref{sec.res}). Therefore, we have three different +scenarios for three different dynamic and static power ratios refer to as: +70\%-20\%, 80\%-20\% and 90\%-10\% scenario. The results of these scenarios +running NAS benchmarks class C on 8 or 9 nodes are place in the tables +(\ref{table:res_s1} and \ref{table:res_s2}). \begin{table}[htb] \caption{The results of 70\%-30\% powers scenario} @@ -731,5 +777,7 @@ the real execution time by maximum normalized error 0.03 of all NAS benchmarks. %%% ispell-local-dictionary: "american" %%% End: -% LocalWords: Fanfakh Charr FIXME Tianhe DVFS HPC NAS NPB SMPI Rauber's Rauber -% LocalWords: CMOS EQ EPSA Franche Comté Tflop Rünger IUT Maréchal Juin cedex +% LocalWords: Fanfakh Charr FIXME Tianhe DVFS HPC NAS NPB SMPI Rauber's Rauber +% LocalWords: CMOS EQ EPSA Franche Comté Tflop Rünger IUT Maréchal Juin cedex +% LocalWords: de badri muslim MPI TcpOld TcmOld dNew dOld cp Sopt Tcp Tcm Ps +% LocalWords: Scp Fmax Fdiff SimGrid GFlops Xeon EP BT -- 2.39.5