X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/mpi-energy2.git/blobdiff_plain/cdc55cc9fb92c0969e7c5773567fad0348c8a6dc..1cea7b40511f60228c23a644b707615cd1559471:/Heter_paper.tex?ds=inline diff --git a/Heter_paper.tex b/Heter_paper.tex index 0b545e4..a604b96 100644 --- a/Heter_paper.tex +++ b/Heter_paper.tex @@ -25,6 +25,9 @@ \newcommand{\Xsub}[2]{{\ensuremath{#1_\mathit{#2}}}} +%% 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}} @@ -33,24 +36,24 @@ \newcommand{\Eoriginal}{\Xsub{E}{Original}} \newcommand{\Ereduced}{\Xsub{E}{Reduced}} \newcommand{\Es}{\Xsub{E}{S}} -\newcommand{\Fdiff}{\Xsub{F}{diff}} -\newcommand{\Fmax}{\Xsub{F}{max}} +\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}{\mathit{Max}\Dist} \newcommand{\MinTcm}{\mathit{Min}\Tcm} \newcommand{\Ntrans}{\Xsub{N}{trans}} -\newcommand{\Pd}{\Xsub{P}{d}} +\newcommand{\Pd}[1][]{\Xsub{P}{d}_{\fxheight{#1}}} \newcommand{\PdNew}{\Xsub{P}{dNew}} \newcommand{\PdOld}{\Xsub{P}{dOld}} \newcommand{\Pnorm}{\Xsub{P}{Norm}} -\newcommand{\Ps}{\Xsub{P}{s}} -\newcommand{\Scp}{\Xsub{S}{cp}} -\newcommand{\Sopt}{\Xsub{S}{opt}} -\newcommand{\Tcm}{\Xsub{T}{cm}} -\newcommand{\Tcp}{\Xsub{T}{cp}} -\newcommand{\TcpOld}{\Xsub{T}{cpOld}} +\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}} @@ -85,9 +88,10 @@ platforms many techniques have been used. Dynamic voltage and frequency scaling 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 +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 @@ -297,14 +301,14 @@ 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} - \Tnew = \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) + \MinTcm = \min_{i=1,2,\dots,N} (\Tcm[i]) \end{equation} -where $\TcpOld_i$ is the computation time of processor $i$ during the first +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 @@ -397,13 +401,13 @@ The static energy of a processor after scaling its frequency is computed as foll \end{equation} In the considered heterogeneous platform, each processor $i$ might have -different dynamic and static powers, noted as $\Pd_{i}$ and $\Ps_{i}$ +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 +$\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 +$\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 @@ -414,8 +418,8 @@ 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}) + + 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} @@ -464,8 +468,8 @@ maximum frequency for all nodes) as follows: \begin{multline} \label{eq:pnorm} \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)}} + {} = \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} @@ -474,9 +478,9 @@ while scaling down the frequency and the consumed energy with maximum frequency \begin{multline} \label{eq:enorm} \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)}} + {} = \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}). @@ -495,8 +499,8 @@ normalized execution time is inverted which gives the normalized performance equ \begin{multline} \label{eq:pnorm_inv} \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} + = \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} @@ -564,21 +568,21 @@ 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} + \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: +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} + 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 colored in blue in Figure~\ref{fig:st_freq}. This set of +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 @@ -623,42 +627,42 @@ maximum distance between the energy curve and the performance curve is while % \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.$ + \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 $\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 $\Tnew \gets max_\textit{~i=1,\dots,N} (\Tcp_{i} \cdot S_{i}) + \MinTcm $ -% \State $\Ereduced \gets \sum_{i=1}^{N}{(S_i^{-2} \cdot \Pd_i \cdot \Tcp_i)} + \sum_{i=1}^{N} {(\Ps_i \cdot \rlap{\Tnew)}} $ - \State $\Ereduced \gets \sum_{i=1}^{N}{(S_i^{-2} \cdot \Pd_i \cdot \Tcp_i + \Ps_i \cdot \rlap{\Tnew)}} $ + \State $\Tnew \gets \max_{i=1,\dots,N} (\Tcp[i] \cdot S_{i}) + \MinTcm $ +% \State $\Ereduced \gets \sum_{i=1}^{N}{(S_i^{-2} \cdot \Pd[i] \cdot \Tcp[i])} + \sum_{i=1}^{N} {(\Ps[i] \cdot \rlap{\Tnew)}} $ + \State $\Ereduced \gets \sum_{i=1}^{N}{(S_i^{-2} \cdot \Pd[i] \cdot \Tcp[i] + \Ps[i] \cdot \rlap{\Tnew)}} $ \State $\Pnorm \gets \frac{\Told}{\Tnew}$ \State $\Enorm\gets \frac{\Ereduced}{\Eoriginal}$ \If{$(\Pnorm - \Enorm > \Dist)$} - \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} @@ -711,7 +715,7 @@ 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$ +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. @@ -745,22 +749,22 @@ nodes were connected via an Ethernet network with 1 Gbit/s bandwidth. \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 & & \\ \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}