\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}}
\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}}
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
\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
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}
\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}
\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}).
\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}
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
% \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_{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}
