Création du dépôt pulications et ajout de PDSEC2010

[interreg4.git] / pdsec2010 / pdsec2010.tex

%% Version PDSEC
\documentclass[conference,compsoc,a4paper]{IEEEtran}

%% Pour Ingrid
%\documentclass[conference,compsoc,a4paper,onecolumn]{IEEEtran}
%\documentclass[compsoc,a4paper,oneside]{IEEEtran}

\usepackage[T1]{fontenc}
\usepackage{ucs}
\usepackage[utf8x]{inputenc}
\usepackage{lmodern}
\usepackage{color}
%% Jolis entetes %%
%\usepackage[Glenn]{fncychap}
\usepackage{amsmath}
%\usepackage{amsthm}
\usepackage{amsfonts}
%\usepackage{graphicx}
%\usepackage{xspace}
% Definition des marges
\usepackage{vmargin}
\setpapersize[portrait]{A4}

\usepackage[english]{babel}
% Extension pour les graphiques EPS
%\usepackage[dvips]{graphicx}
\usepackage[pdftex,final]{graphicx}
% Extension pour les liens intra-documents (tagged PDF)
% et l'affichage correct des URL (commande \url{http://example.com})
\usepackage{hyperref}
% Extension pour que plus de titres apparaissent dans la table des matieres
% (table des matieres, bibliographie, index).
%\usepackage{tocbibind}
%\newcommand{\tabledesmatieres}{
%  \setlength{\parskip}{0ex} % suppression de l'espace entre les paragraphes
%  \tableofcontents
%  \espacementnormal
%}
%\NoAutoSpaceBeforeFDP
%\author{Sébastien Miquée}

\usepackage[ruled,vlined]{algorithm2e}
\usepackage{cite}

\newcommand{\myitemize}[1]
{
\begin{itemize}
\itemsep=#1pt
}

%
\ifCLASSINFOpdf
   \usepackage[pdftex]{graphicx}
   \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
\else
\fi

% *** PDF, URL AND HYPERLINK PACKAGES ***
%
\usepackage{url}


\title{Mapping Asynchronous Iterative Applications on Heterogeneous
  Distributed Architectures}

\author{
\IEEEauthorblockN{Raphaël Couturier \hspace{10pt} David Laiymani
  \hspace{10pt} Sébastien Miquée}

\IEEEauthorblockA{Laboratoire d'Informatique de Franche-Comté
  (LIFC)\\
  University of Franche-Comté\\
  IUT de Belfort-Montbéliard,2 Rue Engel Gros, BP 27, 90016 Belfort,
  France\\
 % Tel.: +33-3-84587782 \hspace{20pt} Fax: +33-3-84587781\\
Email:
\{raphael.couturier,david.laiymani,sebastien.miquee\}@univ-fcomte.fr}

%\thanks{This work was supported by the European Interreg IV From-P2P project.}
}

%% Permet de réactiver le \thanks
\IEEEoverridecommandlockouts

\date{}
\begin{document}

%% left, top, right, bottom
\setmargrb{20mm}{15mm}{20mm}{15mm}

\IEEEcompsoctitleabstractindextext

\maketitle


\begin{abstract}
  To design parallel numerical algorithms on large scale distributed
  and heterogeneous platforms, the asynchronous iteration model (AIAC)
  may be an efficient solution. This class of algorithm is very
  suitable since it enables communication/computation overlapping and
  it suppresses all synchronizations between computation nodes. Since
  target architectures are composed of more than one thousand
  heterogeneous nodes connected through heterogeneous networks, the
  need for mapping algorithms is crucial. In this paper, we propose a
  new mapping algorithm dedicated to the AIAC model. To evaluate our
  mapping algorithm we first implemented it in the JaceP2P programming
  and executing environment dedicated to AIAC applications. Then we
  conducted a set of experiments on the Grid'5000 testbed with more
  than 700 computing cores and with a real and typical AIAC
  application based on the NAS parallel benchmarks. Results are very
  encouraging and show that the use of our algorithm brings an
  important gain in term of execution time (about $40\%$).\\

%  To design parallel and distributed applications on heterogeneous
%  distributed architectures, the asynchronous iteration model may be
%  an efficient solution. Such architectures contain various computing
%  nodes connected by heterogeneous links. Nowadays, these
%  architectures offer users too many computing nodes as they need, so
%  a choice should be done, which is called ``tasks mapping''. In this
%  paper we propose a comparison between different mapping algorithms,
%  in order to evaluate mapping needs of the asynchronous iteration
%  model on this kind of architectures. To do our experiments we used a
%  middleware, JaceP2P-V2, which allows users to design asynchronous
%  iterative applications and execute them on distributed
%  architectures, in which we added a mapping library.\\
  
  \textup{\small \textbf{Keywords:} Mapping algorithms, Distributed
    clusters, Parallel iterative asynchronous algorithms, Heterogeneous
    architectures.}
\end{abstract}


\IEEEpeerreviewmaketitle

%\begin{keywords}
%  Mapping algorithms, Distributed clusters, Parallel iterative
%  asynchronous algorithms, Heterogeneous architectures.
%\end{keywords}

\section{Introduction}
\label{sec:intro}

Nowadays scientists of many domains, like climatic simulation or
biological research, need great and powerful architectures to compute
their large applications. Distributed clusters architectures, which
are part of the grid architecture, are one of the best architectures
used to solve such applications with an acceptable execution
time. These architectures provide a lot of heterogeneous computing
nodes interconnected by a high performance network, but even with the
greatest efforts of their maintainers, there are latency and
computation capacity differences between clusters of each site.

In order to efficiently use this massive
distributed computation power, numerous numerical algorithms have been
elaborated. These algorithms can be broadly classified into two
categories:

\myitemize{5}
\item \textbf{Direct methods}, which give the exact solution of the
  problem using a finite number of operations
  (e.g. Cholesky\cite{cholesky-cg}, LU\cite{lu},etc). However, these
  methods cannot be applied to all kinds of numerical problems. In
  general, they are not well adapted to very large problems.
\item \textbf{Iterative methods}, that repeat the same instructions
  until a desired approximation of the solution is reached -- we say
  that the algorithm has converged. Iterative algorithms constitute
  the only known approach to solving some kinds of problems and they
  are easier to parallelize than direct methods. The Jacobi or
  Conjugate Gradient\cite{cg} algorithms are examples of such
  iterative methods.
\end{itemize}


In the rest of this paper we only focus on iterative methods. Now to
parallelize this kind of algorithm, two classes of parallel iterative
models can be described:

\myitemize{5}

\begin{figure}[h!]
  \vspace{0.1cm}
  \centering
  \includegraphics[width=7.4cm]{images/ISCA}
  \caption{Two processors computing in the Synchronous Iteration - Asynchronous Communication (SIAC) model}
  \label{fig:SIAC}
\end{figure}

\item \textbf{The synchronous iteration model}. In this model, as can
  be seen on Figure \ref{fig:SIAC}, after each iteration (represented
  by a filled rectangle), a node sends its results to its neighbors
  and waits for the reception of all dependency messages from its
  neighbors to start the next iteration. This results in large idle
  times (represented by spaces between each iteration) and is
  equivalent to a global synchronization of nodes after each
  iteration. These synchronizations can strongly penalize the overall
  performances of the application particularly in case of large scale
  platforms with high latency network. Furthermore, if a message is
  lost, its receiver will wait forever for this message and the
  application will be blocked. In the same way, if a machine falls
  down, all the computation will be blocked.

\begin{figure}[h!]
  \vspace{0.1cm}
  \centering
  \includegraphics[width=7.4cm]{images/IACA}
  \caption{Two processors computing in the Asynchronous Iteration - Asynchronous Communication (AIAC) model}
  \label{fig:AIAC}
\end{figure}


\item \textbf{The asynchronous iteration model}. In this
  model\cite{book_raph}, as can be seen on Figure \ref{fig:AIAC}, after
  each iteration, a node sends its results to its neighbors and starts
  immediately the next iteration with the last received data. These
  data could be data from previous iterations, because last data are
  not arrived in time or neighbors have not finish their current
  iteration. The receiving and sending mechanisms are asynchronous and
  nodes do not have to wait for the reception of dependency messages
  from their neighbors. Consequently, there is no more idle time
  between two iterations. Furthermore, this model is tolerant to
  messages loss and even if a node dies, the remaining nodes continue
  the computation, with the last data the failed node
  sent. Unfortunately, the asynchronous iteration model generally
  requires more iterations than the synchronous one to converge to the
  solution.

  This class of algorithms is very suitable in a distributed clusters
  computing context because it suppresses all synchronizations between
  computation nodes, tolerates messages loss and enables the
  overlapping of communications by computations. Interested readers
  might consult \cite{bcvc06:ij} for a precise classification and
  comparison of parallel iterative algorithms. In this way, several
  experiments \cite{bcvc06:ij} show the relevance of the AIAC
  algorithms in the context of distributed clusters with high latency
  between clusters. These works underline the good adaptability of
  AIAC algorithms to network and processor heterogeneity.
\end{itemize}

As we aim to solve very large problems on heterogeneous distributed
architectures, in the rest of this study we only focus on the
asynchronous iteration model. In order to efficiently use such
algorithms on distributed clusters architectures, it is essential to
map the tasks of the application to the best sub-sets of nodes of the
target architecture. This mapping procedure must take into account
parameters such as network heterogeneity, computing nodes
heterogeneity and tasks heterogeneity in order to minimize the overall
execution time of the application.
%we have to select
%sets of computing nodes, which can improve applications execution
%time. Indeed, as there are more available nodes as we need on such
%architectures, it is important to select appropriate computing nodes,
%due to their heterogeneity at computation power as well as relying
%network. 
To the best of our knowledge, there exits no algorithm which
specifically addresses the mapping of AIAC applications on distributed
architectures. The aim of this paper is to propose a new mapping
algorithm dedicated to AIAC applications and to implement it into a
real large scale computing platform, JaceP2P-V2. Experiments conducted
on the Grid'5000 testbed with more than 400 computing cores show that
this new algorithm allows to enhance the performances of JaceP2P-V2 of
about $40\%$ for a real and typical AIAC application.

%this mapping problem. Our aim is to evaluate the
%more common approaches to solve this problem, by using several mapping
%algorithms implemented in a real large scale computing platform,
%JaceP2P-V2, on a true distributed clusters architecture.\\

The rest of this paper is organized as follows. Section
\ref{sec:jacep2p} presents the JaceP2P-V2 middleware. We focus here on
one of the main drawbacks of this platform: its lack of an efficient
mapping strategy. Section \ref{sec:pb} presents our mapping problem
and quotes existing issues to address it. Section
\ref{sec:aiacmapping} describes the specificities of the AIAC model
and details the main solution we propose to address the AIAC mapping
problem. In section \ref{sec:expe} we describe the experiments we have
conducted, with their different components and results. These results
were conducted on the Grid'5000 testbed with more than 400 computing
cores and show an important gain (about $40\%$) of the overall
execution time for a typical AIAC application, i.e. based on the NAS
Parallel Benchmark. Finally, we give some concluding remarks and plan
our future work in section \ref{sec:conclu}.


\section{JaceP2P-V2}
\label{sec:jacep2p}

JaceP2P-V2\cite{jaceP2P-v2} is a distributed platform implemented
using the Java programming language and dedicated to developing and
executing parallel iterative asynchronous applications. JaceP2P-V2
executes parallel iterative asynchronous applications with
dependencies between computing nodes. In addition, JaceP2P is fault
tolerant which allows it to execute parallel applications over
volatile environments and even for stable environments like local
clusters, it offers a safer and crash free platform. To our knowledge
this is the only platform dedicated to designing and executing AIAC
algorithms.

\subsection{Architecture}
\label{sec:archijaceP2P}

In this section we describe the JaceP2P-V2 environment. As can be seen
on Figure \ref{fig:jaceP2P-v2}, which shows its architecture, this
platform is composed of three main entities:

\begin{figure}[h!]
  \vspace{0.1cm}
  \centering
  \includegraphics[width=7.4cm]{images/JACEP2P-V2}
  \caption{The JaceP2P-V2 architecture}
  \label{fig:jaceP2P-v2}
\end{figure}

\myitemize{5}
\item The first entity is the ``super-node'' (represented by a big
  circle in figure \ref{fig:jaceP2P-v2}).  Super-nodes form a circular
  network and store, in registers, the identifiers of all the
  computing nodes that are connected to the platform and that are not
  executing any application.
%  Each super-node has a status table containing the
%  number of connected computing nodes to each super-node and all the
%  super-nodes share a ``token'' that is passed successively from a
%  super-node to the next one. Once a super-node has the token, it
%  computes the average number of computing nodes connected to a
%  super-node ($avg$) using the status table. If $avg$ is lower than
%  the number of computing nodes connected to it, then it sends the
%  identifiers of the extra computing nodes to the super-nodes that
%  have the number of computing nodes connected to them less than
%  $avg$. If the number of computing nodes connected to it has changed,
%  it broadcasts the information to all the super-nodes in the
%  platform. Finally, it passes the token to the next super node. This
%  distribution reduces the load of the super-nodes. 
  A super-node regularly receives heartbeat messages (represented by
  doted lines in figure \ref{fig:jaceP2P-v2}) from the computing nodes
  connected to it. If a super-node does not receive a heartbeat
  message from a computing node for a given period of time, it
  declares that this computing node is dead and deletes its identifier
  from the register.

\item The second entity is the ``spawner'' (represented by a square in
  figure \ref{fig:jaceP2P-v2}).  When a user wants to execute a
  parallel application that requires $N$ computing nodes, he or she
  launches a spawner. The spawner contacts a super-node to reserve the
  $N$ computing nodes plus some extra nodes. When the spawner receives
  the list of nodes from the super-node, it transforms the extra
  nodes into spawners (for fault tolerance and scalability reasons)
  and stores the identifiers of the rest of the nodes in its own
  register. Once the extra nodes are transformed into spawners, they
  form a circular network and they receive the register containing the
  identifiers of the computing nodes. Then each spawner becomes
  responsible for a subgroup of computing nodes, starts the tasks on
  the computing nodes under its command and sends a specific register
  to them.
%  So each
%  computing node receives a specific register that only contains the
%  identifiers of the daemons it interacts with and that depends on the
%  application being executed. These specific registers reduce the
%  number of messages sent by the spawners to update the register of
%  the daemons after a daemon crashes because usually a small number of
%  daemons is affected by this crash. 
  If the spawner receives a message from a computing node informing
  that one of its neighbors is fallen, it fetches a new one from the
  super-node in order to replace the dead one. The spawner initializes
  the new daemon, which retrieves the last backup (see next paragraph)
  of the dead node and continues the computing task from that
  checkpoint.

\item The third entity is the ``daemon'', or the computing node,
  (represented in figure \ref{fig:jaceP2P-v2} by a hashed small circle
  if it is idle and by a white small circle if it is executing an
  application). Once launched, it connects to a super-node and waits
  for a task to execute. Once they begin executing an application they
  form a circular network which is only used in the failure detection
  mechanism. Each daemon can communicate directly with the daemons
  whose identifiers are in its register. At the end of a task, the
  daemons reconnect to a super-node.
\end{itemize}

To be able to execute asynchronous iterative applications, JaceP2P-V2
has an asynchronous messaging mechanism and to resist daemons'
failures, it implements a distributed backup mechanism called the
uncoordinated distributed checkpointing. This method allows daemons to
save their data on neighboring daemons without any user
intervention. The asynchronous nature of the application allows two
daemons to execute two different iterations, thus each daemon saves
its status without synchronizing with other daemons. This
decentralized procedure allows the platform to be very scalable, with
no weak points and does not require a secure and stable station for
backups. Moreover, since the AIAC model is tolerant to messages loss,
if a daemon dies, the other computing nodes continue their tasks and
are not affected by this failure. 
% The application convergence detection is done by daemons, using the
% decentralized global convergence detection algorithm presented in
% \cite{conv_dec}. It consists of two phases: the detection phase and
% the verification phase. This algorithm aims to detect efficiently
% the global convergence of asynchronous iterative parallel algorithms
% on distributed architectures.
For more details on the JaceP2P-V2 platform, readers can refer to
\cite{jaceP2P-v2}.

\subsection{Benefits of mapping}
\label{sec:benef}

In the JaceP2P-V2 environment, presented in the previous section,
there is no effective mapping solution. Indeed, when a user wants to
launch an application, the spawner emits a request to the super-node,
which is in charge of available daemons. Basically, the super-node
returns the amount of requested computing nodes by choosing in its own
list.
%,
%if there are sufficient daemons connected on it, or in other
%super-nodes lists, in addition of its one. 
In this method, the super-node only cares about the amount of
requested nodes, it returns in general nodes in the order of their
connection to the platform -- there is no specific selection.
Distributed architectures such as distributed clusters, as can be seen
on Figure \ref{fig:pbdistclust}, are often composed of heterogeneous
clusters linked via heterogeneous networks with high latencies and
bandwidths. As an example the Grid'5000\cite{g5k} testbed is composed
of 23 clusters spread over 9 sites. Those clusters are heterogeneous,
with computing powers starting from bi-cores at 2GHz to
bi-quadri-cores at 2.83GHz with 2Go of memory for the first one to 8Go
for the second. Links relying clusters are 10Gb/s capable, but as many
researchers use this platform, high latencies appear in links between
sites.
%In the targeted architectures, which are distributed clusters, each
%cluster provides a fixed number of homogeneous computing nodes --
%computing nodes are heterogeneous from a cluster to another. Figure
%\ref{fig:pbdistclust} represents such an architecture, in which we can
%see different sites containing several heterogeneous clusters. Each
%cluster is relied by high speed network with clusters in the same site
%and in others. We note that the architecture may not be represented by
%a full connected graph, as some sites are not directly connected to
%some others. The Grid'5000 testbed, described in section
%\ref{sec:g5k}, is an example of such a distributed clusters
%architecture.  Though there are efficient links relying each site, a
%residual latency continues to exist, at local clusters (in the same
%site) as well as distant clusters (from two distinct sites), and can
%penalize performances.

\begin{figure}[ht!]
  \centering
  \includegraphics[width=7.8cm]{images/dist_clust}
  \caption{A distributed clusters architecture}
  \label{fig:pbdistclust}
\end{figure}


With such an architecture, it could be
efficient to assign tasks communicating with each other on the same
cluster, in order to improve communications. But, as we use very large
problems, it is quite impossible to find clusters containing as many
computing nodes as requested. So we have to dispatch tasks over
several clusters. That implies to deal with heterogeneity in clusters
computing power and heterogeneity in network. We should make a
trade-off between both components in order to take the best part
of each one to improve the overall performances.
%The
%literature in high performance computing has broadly demonstrated the
%benefits of mapping solutions on the applications execution time.

In order to check if a tasks mapping algorithm would provide
performances improvement in JaceP2P-V2 environment, we have evaluated
the contributions of a simple mapping algorithm, which is described in
section \ref{sec:sma}. These experiments used the NPB Kernel CG
application described in section \ref{sec:cg}, with two problem sizes
(the given problem sizes are the sides sizes of square matrices used)
and using a distributed clusters architecture composed of 102
computing nodes, representing 320 computing cores, spread over 5
clusters in 5 sites. The results of these experiments are given in
Table \ref{tab:benef}.

\renewcommand{\arraystretch}{1.5}

\begin{table}[h!]
  \centering
  \begin{tabular}{|c|c|c|}
    \hline
    Problem size&$550,000$&$5,000,000$\\
    \hline
    Execution Time (without mapping)&141s&129s\\
    Execution Time (with mapping)&97s&81s\\
    \hline
    Gains&$31\%$&$37\%$\\
    \hline
  \end{tabular}
  \caption{Effects of a simple tasks
    mapping algorithm on application's execution time}
  \label{tab:benef}
\end{table}

As can be seen in Table \ref{tab:benef}, the effects of a
simple tasks mapping algorithm are significant. 
%Moreover, we can see
%that are scalable with the application's size, which demonstrates the
%real needs of the platform for a such algorithm. 
This encouraged us to look further for better task mapping
algorithms. In the next section, we describe the specificities of our
model and issues which can be exploited.

\section{Problem description}
\label{sec:pb}

In this section we describe the AIAC mapping problem. We first
formalize the different elements we should take into consideration:
the application, the targeted architecture and the objectives
functions of the mapping. We also give a state of the art about
considered kinds of mapping algorithms.

\subsection{Model formalization}
\label{sec:pbmodel}

In this section the models of the applications and architectures we
used are given, with the objectives functions of the mapping
algorithms.

\subsubsection{Application modeling}
\label{sec:pbmodelapp}

In high performance computing, when we want to improve the global
execution time of parallel applications we have to make an efficient
assignation of tasks to computing nodes. Usually, to assign tasks of
parallel applications to computing nodes, scheduling algorithms are
used. These algorithms often represent the application by a graph,
called DAG \cite{dag1,dag2,dag3,dag4} (Directed Acyclic Graph). In
this graph, each task is represented by a vertex which is relied to
others by edges, which represent dependencies and communications
between tasks. This means that some tasks could not start before other
ones finish their computation and send their results. As exposed in
the introduction, in the AIAC model, there is no precedence between
tasks.

Indeed, with the AIAC model, all tasks compute in parallel at the same
time. As communications are asynchronous, there is no synchronization
and no precedence. During an iteration, each task does its job and
sends results to its neighbors and continues with the next
iteration. If a task receives new data from its dependencies, it
includes them and the computation continues with these new data. If
not all dependencies data, or none, are received before starting the
computation of the next iteration, old data are used instead. Tasks
are not blocked on dependencies. Nevertheless regularly receiving new
data allows tasks to converge more quickly. So, it appears that DAG
are not appropriate to modeling AIAC applications. TIG\cite{tig1,
  tig2} (Task Interaction Graph) are more appropriate.
%That is why we use the
%TIG\cite{tig1, tig2} (Task Interaction Graph) model instead of DAG,
%which allows to modeling application using tasks and their
%communication dependencies. Figure \ref{fig:tig} gives an example of a
%TIG.

\begin{figure}[h!]
  \centering
  \includegraphics[width=5cm]{images/tig}
  \caption{An example of a TIG of a nine tasks application}
  \label{fig:tig}
\end{figure}

In the TIG model, a parallel program is represented by a graph
%, as can
%be seen in Figure \ref{fig:tig}. This graph 
$GT(V,E)$, where $V = \{V_1,V_2,\dots V_v\}$ is the set of $|V|$
vertices and $E \subset V \times V$ is the set of undirectional edges
(see Figure \ref{fig:tig}). The vertices represent tasks and the edges
represent the mutual communication among tasks. A function $ET : V
\rightarrow R^+$ gives the computation cost of tasks and $CT : E
\rightarrow R^+$ gives the communication cost for message passing on
edges. We define $v = |V|$, $ET(V_i) = e_i$ and $CT(V_i,V_j) =
c_{ij}$. For example, in Figure \ref{fig:tig}, \mbox{$e_0$ = 10} and $c_{01}
= 2$, $c_{03} = 2$ and $c_{04} = 2$. Tasks in TIG exchange information
during their execution and there is no precedence relationship among
tasks; each task cooperates with its neighbors. This model is used to
represent applications, where tasks are considered to be executed
simultaneously. Temporal dependencies in the execution of tasks are
not explicitly addressed: all the tasks are considered simultaneously
executable and communications can take place at any time during the
computation. That is why vertices and edges are labeled with weights
describing computational and communication costs.\\
 

\subsubsection{Architecture modeling}
\label{sec:pbmodelarchi}

As TIG models the application, we have to model the targeted
architecture. A distributed clusters architecture can be modeled by a
three-level-graph. The levels are \textit{architecture} (a), in our
study it is the Grid'5000 grid, \textit{cluster} (c) and computing
node (n) levels. Figure \ref{fig:pbdistclust} in section
\ref{sec:benef} shows such a model. Let $GG(N,L)$ be a graph
representing a distributed clusters architecture, where $N =
\{N_1,N_2,\dots N_n\}$ is the set of $|N|$ vertices and $L$ is the set
of undirectional edges. The vertices represent the computing nodes and
the edges represent the links between them. An edge $L_i \in L$ is an
unordered pair $(N_x,N_y) \in N$, representing a communication link
between nodes $x$ and $y$. Let be $|C|$ the number of clusters in the
architecture containing computing nodes. A function $WN : N
\rightarrow R^+$ gives the computational power of nodes and $WL : L
\rightarrow R^+$ gives the communication latency of links. We define
$WN(N_i) = wn_i$ and $WL(L_i,L_j) = wl_{ij}$.

An architecture with a three-level-graph is specified according as
follows. All computing nodes are in the same node level. When
computing nodes can communicate to one another with the same
communication latency, they can be grouped into the same cluster. In
addition, like in the Grid'5000 testbed, if computing nodes seemly
have the same computational power with a low communication latency, a
cluster of these nodes can be defined. All participating clusters,
including computing nodes, are in the same architecture level and
communicate through the architecture network.\\


\subsubsection{Mapping functions}
\label{sec:pbmodelmapping}

After having described the two graphs used to model the application
and the architecture, this section defines our objectives.

When a parallel application $App$, represented by a graph $GT$, is
mapped on a distributed clusters architecture, represented by a graph
$GG$, the execution time of the application, $ET(App)$, can be defined
as the execution time of the slowest task.
%In the AIAC model, tasks
%have, in general, seemly the same work and communication loads; so the
%difference on execution time depends on the executing machines. 
Indeed an application ends when all the tasks have detected
convergence and have reached the desired approximation of the
solution, that is why the execution time of the application depends on
the slowest task.
%, this converges last. 
We define
\begin{equation}
  \label{eq:et}
  ET(App) = \max_{i=1 \dots v} ( ET(V_i) )
\end{equation}

where the 
%$ET(V_s)$ is the execution time of the slowest task $V_s$. The
execution time of each task $i$ \mbox{($i=1 \dots v$)}, $ET(V_i)$ is
given by
\begin{equation}
  \label{eq:ettask}
  ET(V_i) = \frac{e_i}{wn_i} + \sum_{j \in J} c_{ij} \cdot wl_{ij}
\end{equation}

where $e_i$ is the computational cost of $V_i$, $wn_i$ is the
computational power of the node $N_i$ on which $V_i$ is mapped, $J$
represents the neighbors set of $V_i$, $c_{ij}$ is the amount of
communications between $V_i$ and $V_j$, and $wn_{ij}$ is the link
latency between the computing nodes on which are mapped $V_i$ and
$V_j$. 
%Note that in the AIAC model, we only consider for $e_i$ the
%cost of an only one iteration, as we cannot determine in advance the
%amount of iterations a task should complete to converge.
We underline here that in the AIAC model, it is impossible to predict
the number of iterations of a task. So it is difficult to evaluate a
priori the cost $e_i$ of a task. In the remainder, we approximate
$e_i$ by the cost of one iteration.

The mapping problem is similar to the classical graph partitioning and
task assignment problem \cite{npcomp}, and is thus NP-complete. 
%The
%generalization of this problem by considering both heterogeneous tasks
%graph and architecture graph makes the problem more complex.
%The JaceP2P-V2 platform is design to execute parallel asynchronous
%iterative application on heterogeneous distributed architectures, so
%it has to launch applications on a variety of computing nodes relying
%by non-uniform links. As demonstrates in the previous section, it does
%not map efficiently tasks on nodes and the overall performances can be
%strongly penalize by this lack of mapping. Indeed, if the
%heterogeneity degree of the architecture used is high, it can be
%possible to have two neighbors tasks executing on two foreign
%computing nodes, that penalizes communications between these tasks,
%that increase the execution time. With the same mining, it is
%interesting to have similar computing nodes, in order to have seemly
%the same iteration execution time that allows to converge more
%quickly. We can conclude that JaceP2P-V2 needs an algorithm to
%efficiently map tasks on computing nodes.
%
%%As we use parallel distributed algorithms on distributed
%%architectures, we have to efficiently map tasks on computing nodes, in
%%order to obtain best performances and the slowest execution time of
%%the application. 
%There exist many scheduling and mapping algorithms in the literature,
%and the research is active in this domain. A first approach is to use
%one the numerous scheduling algorithms, but our model does not fit
%with them. Indeed, a scheduling implies that we have tasks which are
%depending on others, more precisely that some tasks cannot start
%computation before having received data from other tasks, which are
%called precedences, or ``strong dependencies''. This class of
%algorithms uses a well known application's representation: the DAG
%(Direct Acyclic Graph). This model cannot be used with our
%problematic. Indeed, in asynchronous iterative applications, all the
%tasks are executed in the same time, in parallel; there is no
%precedence. So we have to look at another way, which is the ``tasks
%mapping''.
%
%The second approach is to use a tasks mapping algorithm, which only
%aims to map tasks on nodes, following a metric, to minimize the
%application's execution time. To determine which class of tasks
%mapping algorithms we should consider, it is important to draw up a
%list of which information we have in hands. When an application using
%the asynchronous iteration model is run, the number of iterations to
%converge to the solution is unpredictable and change from a run to
%another. So, we cannot give a good approximation of the execution time
%of a task, but we can retrieve an estimation of the computational
%amount of a task (plus de détails ?). In addition, as the asynchronous
%iteration model based algorithms are able to provide to applications
%the message lost tolerance, we cannot exactly quantify the amount of
%communications in an application; some algorithms can converge with
%receiving only few dependencies messages. One application's
%representation which fit perfectly with our model is the TIG (Task
%Interaction Graph), which only considers relations between tasks --
%the only thing which is predictable in our model. The figure
%\ref{fig:tig} presents an example of a TIG.
%
%
%
%On figure \ref{fig:tig} we can see an application with 6 tasks, in
%which each task is in relation with tasks of previous and next rank,
%with two exceptions, the first and the last tasks, which can
%eventually be in relation, depending of the application. This is a
%commonly scheme in asynchronous iteration model; in general, tasks are
%in relation with some others which previous and next ranks, but in
%some cases, dependencies are more complex.

\subsection{Related work}
\label{sec:pbrw}

%In the previous section we have determined that we need to use TIG
%model based mapping algorithms to address our problem. 
In the literature of the TIG mapping, we can find many algorithms,
which can be divided into two categories:

\myitemize{5}
\item \textbf{Edge-cuts optimization}. The aim of this class of
  algorithms is to minimize the use of the penalizing links between
  clusters. As tasks are depending on neighbors, which are called here
  dependencies, the goal is to choose nodes which distance, in term of
  network, is small, to improve communications between tasks. Here we
  can cite Metis\cite{metis}, Chaco\cite{chaco} and
  PaGrid\cite{pagrid} which are libraries containing such kind of
  algorithms. The main drawback of edge-cuts algorithms is that they
  do not tackle the computing nodes heterogeneity issues. They only
  focus on communication overheads.
%  The figure \ref{fig:edge} shows
%  that the optimization is on edges of communications, which are
%  circled in red.
%
%  \begin{figure}[h!]
%    \centering
%    \includegraphics[width=3.5cm]{images/edgecut}
%    \caption{The edge-cuts optimization}
%    \label{fig:edge}
%  \end{figure}
\item \textbf{Execution time optimization}. The aim of these
  algorithms is to minimize the whole execution time of the
  application. They look for nodes which can provide the small
  execution time of tasks using their computational power. Here we can
  cite FastMap\cite{fastmap} and MiniMax\cite{minimax} as such kind of
  algorithms. QM\cite{qm_these} is also an algorithm of this category,
  but it aims to find for each task the node which can provide the
  best execution time. QM works at the task level,
  whereas others work at the application level.\\
%  The figure
%  \ref{fig:et} shows that the optimization is on tasks, which are
%  circled in red.\\
%
%  \begin{figure}[h!]
%    \centering
%    \includegraphics[width=3.5cm]{images/exectime}
%    \caption{The execution time optimization}
%    \label{fig:et}
%  \end{figure}
\end{itemize}

The two classes of algorithms may fit with our goals, because in our
model we have both the computational power of nodes and communication
costs may influence the applications performances.

Nevertheless, to the best of our knowledge, none of the existing
algorithms take into consideration the specificities of the AIAC model
(see next section).
%specifically address the AIAC mapping problem.
%As the existing mapping algorithms are not designed to fit
%with the AIAC mapping problem.

\section{AIAC mapping}
\label{sec:aiacmapping}

In this section we present the specificities of the AIAC model, which
are interesting in the mapping problem, and the solution we propose:
the AIAC QM algorithm, which is an extended version of the QM
algorithm.

\subsection{Specificities of the AIAC mapping problem}
\label{sec:specAIACmapping}

An important point to take into consideration in the AIAC model is
that we do not allow the execution of multiple tasks on the same
computing node. This comes from the fact that the targeted
architectures are volatile distributed environments. Assigning
multiple tasks to a node provides a fall of performances when this
node fails. Indeed we should redeploy all of the tasks from this node
to another one, using last saves, which implies to search a new
available computing node, transfer saves to it and restart the
computation from this point (which could be far from this just before
the failure). 

Nevertheless, in order to benefit of multi-cores architectures, we use
a task level parallelism by running multi-threaded sequential solver
for example.   
%In addition, it is more simple and efficient to parallelize at the
%task level using, as an example with the CG application, a
%multi-threaded linear solver, which benefits of the multi-cores
%architecture of computing nodes.

Another important point in the AIAC model is that we should take into
account precisely the locality issue. This comes from the fact that in
this model, the faster and more frequently a task receives its
dependencies, the faster it converges. Moreover, as the JaceP2P-V2
environment is fault tolerant and tasks save checkpoints on their
neighbors, it is more efficient to save on near nodes than on far
ones.


%As our problem is on task mapping, only considering the dependency
%relations between tasks, with a part of consideration on task weight,
%we should use TIG (\textit{task interaction graph}) mapping model. 

%\section{Mapping algorithms}
%\label{sec:mapalgo}

\subsection{AIAC Quick-quality Map}
\label{sec:qmmodif}

%After having describe the different kinds of mapping algorithms which
%can be found in the literature, we now present the three algorithms we
%use to do mapping in the JaceP2P-V2 environment.

We present here the solution we propose, called \textit{AIAC QM
  algorithm}, to address the AIAC mapping problem. We decided to
improve the \textit{Quick-quality Map} (QM) algorithm since it is one
of the most accurate to address the TIG mapping problem.
%
%\subsection{Modified Quick-quality Map}
%\label{sec:modifiedqm}
%
%As the previous algorithm describe in section \ref{sec:sma} showed
%that mapping provides a significant increase of applications
%performances (which can be seen in the section \ref{sec:experiments}),
%we decide to try another mapping algorithm, which is a modified
%version of the \textit{Quick-quality Map} (QM) algorithm.
%
%
%As explained in section \ref{sec:pb}, the asynchronous iteration model
%is specific, as it is not a good solution to map many tasks on the
%same node. This is why QM has been modified to take into account these
%characteristics.
% Indeed, originally QM tries to map many tasks on the
%same node to improve the execution time of tasks by decreasing
%communications costs. This solution can be good if communications
%between tasks are heavy and if we consider that computing nodes are
%stable and are not volatile. As 

%, we have modified some parts
%of it to fit with our constraints. This was an opportunity to be taken
%to insert a little part of ``edge-cuts'' optimization, as in our model
%communications have to be taken into account. 
In its original version, this algorithm aims at privileging the
computational power of nodes. Indeed, its aim is to find the more
powerful node to map a task on. Moreover, a part of this algorithm is
designed to map multiple tasks on the same node, in order to improve
local communications. This solution can be efficient if communications
between tasks are heavy and if we consider that computing nodes are
stable and not volatile. This last point is in contradiction with
our model, as we authorize only the execution of one task on a single
node -- this allows to lose only the work of a single task in case of
node's fault, with a low cost on restarting mechanism. Instead
assigning multiple tasks on the same computing node, our mapping
algorithm tries to keep tasks locality, to improve communications, by
trying to assign tasks to computing nodes in the neighborhood
of which their neighbors are mapped on. 

The pseudo-code of AIAC QM is given in Algorithm \ref{alg:qmmodified}.

\SetAlgoSkip{}
\begin{algorithm}
  \SetLine
  \dontprintsemicolon
  
  \KwIn{Sets of tasks and computing nodes}
  \KwOut{Mapping of tasks to nodes}
  
  \BlankLine
  
  sort nodes by descending power\;
  map tasks in order on nodes\;
  set all tasks \textit{moveable}\;
  $r \leftarrow 1$\;
  
  \BlankLine
  
  \While{one task is moveable}{
    \For{each task $t_{i}$ $\&\&$ $t_{i}$ is moveable }{
      $n_{c} \leftarrow$ current node of $t_{i}$\; 
      $n_{n} \leftarrow t_{i}$\;
      
      \BlankLine
      
      \For{$k = 0 ; k < \frac{f \cdot n}{r} ; k++$}{
        select random node $n_{r}$ in $[0,\frac{n}{r}]$\;
        \If{ET($t_{i}$,$n_{r}$) $<$ ET($t_{i}$,$n_{n}$)}{
          $n_{n} \leftarrow n_{r} $\;
        }
      }
      
      \BlankLine
      
      \For{each node $n_{v}$ near $dep(t_{i})$}{
        \If{ET($t_{i}$,$n_{v}$) $<$ ET($t_{i}$,$n_{n}$)}{
          $n_{n} \leftarrow n_{v} $\;
        }
      }
      
      \BlankLine
      
      \If{$n_{n} \neq n_{c}$}{
        map $t_{i}$ on $n_{n}$\;
        update ET of $t_{i}$ and dep($t_{i}$)\;
      }
    }
    
    \BlankLine
    
    set $t_i$ not moveable\;
    $r \leftarrow r+1$ if all tasks have been considered\;
  }
  
  \caption{The AIAC QM}
  \label{alg:qmmodified}
\end{algorithm}
%\vspace{-0.5cm}

All nodes are first sorted in descending order according to their
computation power, and all tasks are mapped on these nodes according
to their identifier (they are also marked as ``moveable'', that means
that each task can be moved from a node to another). As in the
original QM algorithm, AIAC QM keeps track of the \textit{number of
  rounds} $r$ ($r > 0$), that all tasks have been searched for a
better node. This allows to reduce at each round the number of
considered nodes. While there is at least one moveable task, it
performs for each moveable task the search for a better node. It
chooses a set of nodes, $\frac{f \cdot n}{r}$, where $f$ is defined as
the search factor and $n$ is the number of nodes. $r$ and $f
\in ]0,1]$ control the portion of nodes that will be considered where
more numerous the rounds are, the less the considered nodes will
be. Then the algorithm estimates the execution time $ET(v)$ of the
task on each node. If it is smaller than the current node on which the
task is mapped on, this node becomes the new potential node for
task $t_i$.

After having randomly searched for a new node, the AIAC QM tries to
map the task on nodes that are neighbors of nodes of which the
dependencies of $t_i$ are mapped on. This is one of the major
modification to the original QM algorithm. It introduces a little part
of ``edge-cuts'' optimization. In the original version, it tries to
map the task $t_i$ on the same node of one as its dependencies. As
explain in \ref{sec:specAIACmapping}, this is not an acceptable
solution in our case. Instead, the algorithm now searches to map task
$t_i$ on nodes which are near the ones its dependencies are mapped
on. This search requires a parameter which indicates the maximum
distance at which nodes should be from the node of dependencies of
$t_i$.

At the end of the algorithm, if a new node is found, $t_i$ is mapped
on and its execution time is updated and $t_i$ is set to ``not
moveable''. The execution time of each of its dependencies is also
updated, and if this new execution time is higher than the previous,
the task is set to ``moveable''. And finally, if all tasks have been
considered in this round, $r$ is incremented.

The complexity of the AIAC QM algorithm is about $O(n^2 \cdot
t \cdot ln(r))$. This complexity is the same as the original
(details are given in \cite{qm_these}, with a an increase of a factor
$n$, corresponding to the edge-cuts part.

\section{Experimentation}
\label{sec:expe}

We now describe the experiments we have conducted and their
components, to evaluate the effects of the AIAC QM algorithm on
application execution time.

\subsection{The NAS Parallel Benchmark Kernel CG}
\label{sec:cg}

We used the ``Kernel CG'' of the NAS Parallel Benchmarks (NPB)
\cite{nas} to evaluate the performances of the mapping
algorithm. This benchmark is designed to be used on large
architectures, because it tests communications over latency networks,
by processing unstructured matrix vector multiplication. In this
benchmark, a Conjugate Gradient is used to compute an approximation of
the smallest eigenvalue of a large, sparse and symmetric positive
definite matrix, by the inverse power method. In our tests, the whole
matrix contains nonzero values, in order to stress more
communications. As the Conjugate Gradient method cannot be executed
with the asynchronous iteration model we have replaced it by another
method called the multisplitting method. This latter supports the
asynchronous iterative model.


With the multisplitting algorithm, the $A$ matrix is split into
horizontal rectangle parts, as Figure \ref{fig:multisplit} shows. Each
of these parts is affected to a processor -- so the size of data
depends on the matrix size but also on the number of participating
nodes. In this way, a processor is in charge of computing its $X Sub$
part by solving the following subsystem: $ASub \times XSub = BSub -
DepLeft \times XLeft - DepRight \times XRight$

After solving $XSub$, the result must be sent to other
processors which depend on it.

\begin{figure}[h!]
  \centering
  \includegraphics[width=7.4cm]{images/multisplit}
  \caption{Data decomposition for the multisplitting method
    implementation}
  \label{fig:multisplit}
\end{figure}

The multisplitting method can be decomposed into four phases:
\begin{enumerate}
\itemsep=5pt
\item \textbf{Data decomposition}. In this phase, data are allocated
  to each processor assuming the decomposition exposed on figure
  \ref{fig:multisplit}. Then, each processor iterates until converge
  on the following.
\item \textbf{Computation}. At the beginning of the computation, each
  processor computes 
    $BLoc = BSub - DepLeft \times XLeft - DepRight \times XRight$. Then,
  it solves $ASub \times XSub = BLoc$ by using a
  multi-threaded sequential version of the Conjugate Gradient method.
\item \textbf{Data exchange}. Each processor sends its $XSub$
  part to its neighbors. Here, the neighborhood is closely related
  to the density of the $A$ matrix. Clearly, a dense matrix implies an
  \textit{all-to-all} communication scheme while a matrix with a low
  bandwidth reduces the density of the communication scheme.
\item \textbf{Convergence detection} Each processor computes its local
  convergence and sends it to a server node. When this one detects
  that each processor has converged, it stops the whole computation
  process.
\end{enumerate}

%It can be pointed out here that it is possible to modify the data
%decomposition in order to obtain non disjoint rectangle matrices. This
%property of multisplitting methods, called \textit{overlapping}, can
%bring significant improvements to convergence speed, but it is not the
%aim of this paper. 
For more details about this method, interested readers are invited to
see \cite{book_raph}. In our benchmark, the sequential solver part of
the multisplitting method is the Conjugate Gradient, using the
MTJ\cite{mtj} library. Its implementation is multi-threaded, so it
benefits from multi-core processors.

We point out here that this benchmark is a typical AIAC
application. The general form of the TIG for this application is given
by Figure \ref{fig:tigcg}.

\begin{figure}[h!]
  \centering
  \includegraphics[width=8cm]{images/tigcg2}
  \caption{Part of the form of the TIG representing an instance of the
    NAS Kernel CG application}
  \label{fig:tigcg}
\end{figure}

This figure shows 6 tasks, which are represented by a circle in which
the identifier of the task is given. In our study, we consider that
the computational costs of tasks are approximately the same and that the
communications costs also the same (this comes from the difficulty to
evaluate real costs in the AIAC model).
% The computational cost of a task is given by the number on the top
% left-hand side of each circle (for example the cost of task 31 is
% 1000). Communications between tasks are represented by edges on
% which the amount of communication is given (for example, the
% communication cost between tasks 29 and 30 is about 30).
Doted lines represent communications with tasks which are not
represented on the figure. We can see here that each task has four
neighbors (the two previous and the two next). This amount of
neighbors is directly related to the bandwidth of the matrix (in this
example the bandwidth is very small). For more details about the
influence of the bandwidth on the amount of neighbors, interested
readers are invited to see \cite{largescale}.

For our experiments the bandwidth of matrices has been reduced in
order to limit the dependencies and we fixed it to $35,000$. This
bandwidth size generates, according to the problem's size, between 10
and 25 neighbors per tasks.

\subsection{The Grid'5000 platform}
\label{sec:g5k}

The platform used for our tests, called Grid’5000\cite{g5k}, is a
French nationwide experimental set of clusters which provides a
configurable and controllable instrument. We can find many clusters
with different kinds of computers with various specifications and
software.

\begin{figure}[h!]
  \centering
  \includegraphics[height=6.5cm]{images/g5k-noms}
  \caption{The Grid'5000 sites map}
  \label{fig:g5ksite}
\end{figure}

Clusters are spread over 9 sites, as can be seen on Figure
\ref{fig:g5ksite}, and the computing power represents more than 5000
computing cores interconnected by the ``Renater'' network. This
network is the national network for research and education; it
provides a large bandwidth with high latency. Intra-clusters networks
present small bandwidth and low latencies.


\subsection{Other mapping algorithms}
\label{sec:othermaping}

In this section we present the two other mapping algorithms we used
in our experiments to compare the performances of the AIAC QM
algorithm. The first one was used to evaluate the benefits of a
mapping solution in section \ref{sec:benef}. The second one was used
to show the differences between the two mapping class, the ``execution
time'' and the ``edge-cuts'' optimizations, as it is a fully edge-cut
optimization based mapping algorithm.

\subsubsection{A Simple Mapping algorithm}
\label{sec:sma}

%As mentioned in section \ref{sec:pb}, the asynchronous iteration model
%has some specificities which distinguishes it from other classical model
%for the mapping.
%
%The first thing we have done was to be sure that a mapping algorithm
%would enhance applications performances. 
The \textit{Simple Mapping algorithm} (SMa) was designed to
show the benefits of a mapping algorithm in the JaceP2P-V2 platform.
%The text of the \textit{Simple Mapping} if given by
Algorithm \ref{alg:sma} gives the pseudo-code of the \textit{Simple
  Mapping algorithm}.
%, in which we can see that it is very simple, with a complexity in $O(n^
%2)$ resulting from sort methods.


\SetAlgoSkip{}
\begin{algorithm}
  \SetLine
  \dontprintsemicolon
  \KwIn{Sets of tasks and computing nodes}
  \KwOut{Mapping of tasks to nodes}
  
  \BlankLine
  
  sort computing nodes by cluster\;
  sort clusters by size, from higher to lower\;
  map tasks in order on sorted clusters\;
  \caption{The Simple Mapping algorithm}
  \label{alg:sma}  
\end{algorithm}


%The aim of this algorithm is to do similarly to a very simple
%edge-cuts optimization algorithm. To do that 
The algorithm puts each node in a cluster entity.
%, which is given for now by the convention name of nodes
%on Grid'5000 (for example azur-3.sophia.grid500.fr is the node 3 of
%the azur cluster in the sophia site). 
Then it sorts clusters by their size, from the higher to the lower.
%; this operation is the part which
%is inspired by edge-cuts optimization based algorithms. 
Finally, all tasks are mapped in order on the sorted clusters; each
task is assigned to a particular computing node of the chosen cluster.

%Though this algorithm is trivial, it allows AIAC applications to run faster
%on distributed clusters architectures, with a gain over $30\%$ on
%execution, as experiments described in section \ref{sec:benef}.

\subsubsection{Edge-cuts optimization}
\label{sec:edgcutalgo}

As explained in section \ref{sec:pb}, the asynchronous iteration model
is so specific and unpredictable that we would like to evaluate the
second kind of mapping algorithm, which aims to optimize the
``edge-cuts''. 
%Multilevel partitioning algorithms such as Metis and
%Chaco fail to address the limitations imposed by heterogeneity in the
%underlying targeted system. They assume that computing nodes and
%network relying them are homogeneous. This is not corresponding to our
%execution environment, which is fully heterogeneous. These methods are
%based on ``graph growing'' (GGP) and/or ``greedy graph growing''
%(GGGP) algorithms which aim to divide tasks into two, or for some
%algorithm a power of two, partitions. In our case, we do not know in
%advance the number of partitions we need. Indeed, it depends on the
%amount of nodes in each cluster and on the number of tasks.
%
%As GGP and GGGP algorithms seems to be efficient in specific cases, it
%could be interesting to adapt one to our model, in order to evaluate a
%real edge-cuts optimization algorithm. 
We choose the Farhat's algorithm\cite{farhat}, which has the ability
to divide the graph into any number of partitions, thereby avoiding
recursive bisection. 
%Therefore its running execution time is
%independent of the desired number of subsections.

The adapted version of this algorithm, Farhat's Edge-Cut (F-EC),
evaluated in the JaceP2P-V2 environment is described in Algorithm
\ref{alg:edgecuts}.

\SetAlgoSkip{}
\begin{algorithm}
  \SetLine
  \dontprintsemicolon
  
  \KwIn{Sets of tasks and computing nodes}
  \KwOut{Mapping of tasks to nodes}
  
  \BlankLine
  
  
  sort nodes by cluster\;
  $lTasks \leftarrow$ sort tasks by dep degree\;
  $changeCluster \leftarrow$ true\;
  $cTasks \leftarrow$ empty;

  \BlankLine
  
  \While{one task is not mapped}{
    \If{$changeCluster$}{
      $curCluster \leftarrow$ nextCluster()\;
      $places \leftarrow$ size($curCluster$)\;
      $changeCluster \leftarrow$ false\;
      $mTasks \leftarrow$ empty\;
    }
    
    \BlankLine

    \If{no task in cTasks}{
      $cTasks \leftarrow$ first task from $lTasks$\;
    }

    \BlankLine

    $curTask \leftarrow$ first task in $cTasks$\;

    \BlankLine

    \eIf{$( 1 + $dep(curTask)~$\cdot~\delta) <= places)$}{
      remove $curTask$ from $cTasks$\;
      add $curTask$ in $mTasks$\;
      $places \leftarrow places - 1$\;
      add dep(curTask) in cTasks\;
    }{
      $changeCluster$ $\leftarrow$ true\;
      associate $mTasks$ with $curCluster$\;
    }
  }
  
  \caption{The Fahrat's Edge-Cut algorithm}
  \label{alg:edgecuts}  
\end{algorithm}

This algorithm aims to do a ``clusterization'' of the tasks. First, it
groups computing nodes in clusters, which are sorted according to
their number of nodes, from the higher to the lower. Tasks are ordered
following their dependency degree, starting from the higher to the
lower. Tasks in the top of the list have a higher priority to be
mapped. Next, the algorithm tries to map on each cluster the maximum
number of tasks. To map a task on a cluster, the algorithm evaluates
if there is enough place to map the task and some of its
dependencies. This amount of dependencies is fixed by a factor
$\delta$, which is a parameter of the algorithm. In the positive case,
the task is mapped on the current cluster and its dependencies become
priority tasks to be mapped. This allows to keep the focus on the
communicating tasks locality.
%All computing nodes are first grouped in clusters.
%%, using their full
%%qualified name -- for now, no criteria is used to sort clusters, such
%%are their power or size. 
%Next, tasks are inserted in a list $lTasks$, sorted in descending
%according to their dependency degree. This allows to map tasks with
%their dependencies to improve communications. Next begins the main
%mapping loop.
%
%While not all tasks have been mapped the algorithm do the
%following. First, at the beginning, it chooses the first available
%cluster to be the current cluster to map tasks on, and sets the
%variable $places$ to its size, in number of computing nodes, and
%create a new tasks' list $mTasks$. During the execution of the
%algorithm, passing in this block means that there is no more node
%available in the current cluster, so it has to choose the next
%cluster. Next, it looks in $cTasks$, which is a tasks list containing
%tasks which are in instance to be mapped. If $cTasks$ is empty it
%takes the first available task in $lTasks$ -- at the beginning it
%takes the first one, which has the higher dependency degree.
%
%Next, it takes the first task in $cTasks$ to try to map it on the
%current cluster. The task is mapped on if there is enough available
%computing nodes on the current cluster. This amount of node
%corresponds to $1 + dep( curTask ) \cdot \delta$, which represents the
%task plus the amount of its dependencies multiplied by a ``local
%dependency factor'' $\delta$, which indicates how many dependencies
%must be a least with $curTask$ on the same cluster. If the task could
%be mapped on this cluster, $curTask$ is added in $mTasks$, which is a
%tasks' list containing tasks which are currently mapped on current
%cluster, and removed it from $cTasks$. The number of available nodes,
%$places$, is decremented, and the dependencies of $curTask$ are added
%to $cTasks$. This list is sorted in the same way as $lTasks$, indeed
%tasks are added according to their dependency degree, from the higher
%to the lower. Otherwise, if there is not enough or no more nodes
%available in the cluster, it has to change the current cluster, so it
%associates the current cluster and list of tasks mapped on, $mTasks$.


\subsection{Experiments}
\label{sec:experiments}

After having described the different components of the experiments, we
now present the impacts of the AIAC QM mapping on applications running
with JaceP2P-V2 on a heterogeneous distributed clusters
architecture. In the following, we note ``heterogeneity degree'' the
degree of heterogeneity of distributed clusters; it is the ratio
between the average and the standard deviation of the computing nodes
power. This heterogeneity degree may vary from 0, nodes are
homogeneous, to 10, nodes are totally heterogeneous. In these
experiments, we consider that there is no computing nodes fault during
applications execution.

The application used to realize these experiments is the KernelCG of
the NAS parallel benchmark, in the multi-splitting version. Two
problem sizes were used: one using a matrix of size $550,000$ (named
``class E'') using 64 computing nodes and the other using a matrix of
size $5,000,000$ (named ``class F'') using 128 nodes.
%
%Figure
%\ref{fig:tigcg} shows a part of a TIG of this application.
%
%\begin{figure}[h!]
%  \centering
%  
%  \label{fig:tigcg}
%\end{figure}



\subsubsection{About heterogeneity}
\label{sec:xphetero}

The first experiments concern the study of the impact of the
heterogeneity of the computing nodes on the mapping
results. Heterogeneity takes an important place in the high
performance computing on grid, all the more so when using the
asynchronous iteration model.

As mapping algorithms take in parameter a factor of research (for AIAC
QM) and the amount of local dependencies (for F-EC), we fixed both to
$50\%$. That means for AIAC QM that at each round the amount of
considering nodes would be divided by two, and for F-EC that each task
requires half of its dependencies on the same local cluster.

Four experiments were done using four architectures having different
heterogeneity degrees -- in two architectures computing nodes are more
heterogeneous than in the others. In these experiments, we did not
affect the networks heterogeneity, because of the difficulty to
disturb and control network on Grid'5000; by default, networks are
already quite heterogeneous. We needed more than 200 computing nodes
to execute our application because of the small capacity of some
clusters to execute the largest problems (there is not enough memory).

The first architecture, Arc1.1, was composed of 113 computing nodes
representing 440 computing cores, spread over 5 clusters in 4
sites. In Arc1.1 we used bi-cores (2 clusters), quadri-cores (2
clusters) and bi-quadri-cores (1 cluster) machines. Its heterogeneity
degree value is 6.43. This architecture was used to run class E of the CG
application using 64 computing nodes. The second architecture, Arc1.2,
used to execute class F of the CG application, using 128 computing
nodes, was composed of 213 computing nodes representing 840 computing
cores, with a heterogeneity degree of 6.49. This architecture was
spread on the same clusters and sites as Arc1.1. The results of the
experiments on Arc1.1 and Arc1.2 are given in Table \ref{tab:exph1E}
and Table \ref{tab:exph1F}, which give the gains in execution time obtained
in comparison to the version without mapping.

%\vspace{0.2cm}

\renewcommand{\arraystretch}{1.5}

\begin{table}[h!]
  \centering
  \begin{tabular}[h!]{|c||c|c|c|c|}
    \hline
    Algorithm& None&SMa & AIAC QM & F-EC \\
    \hline
    \hline
    Execution time&150s&110s&101s&90s\\
    \hline
%    Gains&--&$27\%$&$33\%$&\textcolor{blue}{$40\%$}\\
    Gains&--&$27\%$&$33\%$&$40\%$\\
    \hline
  \end{tabular}
  \caption{Gains in time of the execution of the class E of the CG 
    application on Arc1.1 using 64 computing nodes, with mapping 
    algorithms}
  \label{tab:exph1E}
  \vspace*{-0.3cm}
\end{table}

%\vspace{-0.5cm}

\renewcommand{\arraystretch}{1.5}

\begin{table}[h!]
  \centering
  \begin{tabular}[h!]{|c||c|c|c|c|}
    \hline
    Algorithm& None &SMa & AIAC QM & F-EC \\
    \hline
    \hline
    Execution time&403s&265s&250s&218s\\
    \hline
%    Gains&--&$34\%$&$38\%$&\textcolor{blue}{$46\%$}\\
    Gains&--&$34\%$&$38\%$&$46\%$\\
    \hline
  \end{tabular}
  \caption{Gains in time of the execution of the class F of the CG
    application on Arc1.2 using 128 computing nodes, with mapping 
    algorithms}
  \label{tab:exph1F}
  \vspace*{-0.3cm}
\end{table}

At first, we can see that the Simple Mapping algorithm, though it is
simple, provides a significant improvement of application execution
time. This highlights that JaceP2P-V2 really needs a mapping algorithm
in order to be more efficient. Then, we can see that the F-EC and the
AIAC QM algorithms provide a better mapping than the Simple Mapping
algorithms, we can see a significant difference between both
algorithms. This comes from the homogeneity of clusters. In this case,
the F-EC algorithm is more efficient since the minimization of the
communications becomes more important than the tackle of the
computational power heterogeneity problem.
%Indeed, it is more benefic for ta becomes more important than the
%tacklebecomes more important than the
%tackle sks to have locally their
%dependencies, which allows to improve communications, in case of
%computing nodes are more homogeneous -- communications are more
%important than computing power (that is why the F-EC algorithm is more
%efficient). 
The effect is that tasks do less iterations as they
receive more frequently updated data from their neighbors. In
addition, as tasks and their dependencies are on the same cluster,
communications are improved, but also as computations take
approximately the same time, the amount of iterations is reduce and
the algorithm can converge more quickly.

Another important positive point is that gains are scalable, which allows
to foresee big improvements for very large applications.\\

The third architecture, Arc2.1, was composed of 112 computing nodes,
representing 394 computing cores, spread over 5 clusters in 5
sites. In this architecture we used bi-cores (3 clusters),
quadri-cores (1 cluster) and bi-quadri-cores (1 cluster) machines. Its
heterogeneity degree's value is 8.41. This architecture was used to run
class E of the CG application, using 64 computing nodes. The fourth
architecture, Arc2.2, used to execute class F of the CG
application, using 128 computing nodes, was composed of 212 computing
nodes representing 754 computing cores, with a degree of heterogeneity
of 8.44. This architecture was spread on the same clusters and sites
as Arc2.1. The results of the experiments on Arc2.1 and Arc2.2 are
given in Table \ref{tab:exph2E} and Table \ref{tab:exph2F}, which give the
gains in execution time obtained in comparison to the version without
mapping.

%\vspace{0.2cm}

\renewcommand{\arraystretch}{1.5}

\begin{table}[h!]
  \centering
  \begin{tabular}[h!]{|c||c|c|c|c|}
    \hline
    Algorithm&None& SMa & AIAC QM & F-EC \\
    \hline
    \hline
    Execution time&498s&341s&273s&385s\\
    \hline
%    Gains&$32\%$&\textcolor{blue}{$45\%$}&\textcolor{red}{$23\%$}\\
    Gains&--&$32\%$&$45\%$&$23\%$\\
    \hline
  \end{tabular}
  \caption{Gains in time of the execution of the class E of the CG
    application on Arc2.1 using 64 computing nodes, with mapping 
    algorithms}
  \label{tab:exph2E}
  \vspace*{-0.3cm}
\end{table}

\renewcommand{\arraystretch}{1.5}

\begin{table}[h!]
  \centering
  \begin{tabular}[h!]{|c||c|c|c|c|}
    \hline
    Algorithm& None&SMa & AIAC QM & F-EC \\
    \hline
    \hline
    Execution time&943s&594s&453s&660s\\
    \hline
%    Gains&$37\%$&\textcolor{blue}{$52\%$}&\textcolor{red}{$30\%$}\\
    Gains&--&$37\%$&$52\%$&$30\%$\\
    \hline
  \end{tabular}
  \caption{Gains in time of the execution of the class F of the CG
    application on Arc2.2 using 128 computing nodes, with mapping 
    algorithms}
  \label{tab:exph2F}
  \vspace*{-0.3cm}
\end{table}

To begin with, these experiments confirm that a mapping algorithm is
needed and that improvements are always scalable. Then, we can see
that the F-EC algorithm falls in performances and AIAC QM is
improved. What is surprising is that the Simple Mapping algorithm is
better than F-EC. This can be explained by the fact that as computing
nodes are quite heterogeneous, computations are not the same, so it is
not significant to map dependencies close to tasks. In this case, the
most important is the power of computing nodes. So, in this kind of
architecture, it is more efficient to choose the best computing nodes
to compute iterations more quickly and to improve the convergence
detection.

Here, it is important to note that the AIAC QM algorithm offers a gain
of about $50\%$ on the execution time, that is to say that the
application takes half of the execution time than without mapping.

\subsubsection{Parameters variation}
\label{sec:xpvariation}

After having evaluated mapping algorithms on the heterogeneity of
distributed clusters, we now propose to change the parameters of AIAC
QM and F-EC algorithms, in order to determine which values are the
most accurate.

To do these experiments, we used an architecture composed of 122
computing nodes representing 506 computing cores, spread over 5
clusters in 5 sites. In this architecture we used bi-cores (2
clusters), quadri-cores (2 clusters) and bi-quadri-cores (1 cluster)
machines. Its heterogeneity degree value is 4.98.
%, which means that
%computing nodes power is very heterogeneous.

The parameters of each algorithm, $f$ (the search factor) for
AIAC QM and $\delta$ (the amount of local dependencies) for F-EC,
varied both with values $10\%$, $50\%$ and $90\%$. We used the CG
multi-splitting application on 64 computing nodes. The results of
these experiments are given in Table \ref{tab:expparams}. Results
exposed in this table represent the gains in execution time provided
by each algorithm with different parameters values.

%\vspace{0.2cm}
\renewcommand{\arraystretch}{1.5}

\begin{table}[h!]
  \centering
  \begin{tabular}[h!]{|c||c|c|c|}
    \hline
    Parameters& $10\%$ & $50\%$ & $90\%$ \\
    \hline
    \hline
%    Simple & \multicolumn{3}{c|}{\textcolor{blue}{$39\%$}}\\
    SMa & \multicolumn{3}{c|}{$30\%$}\\
    \hline
%    AIAC QM & $35\%$ & \textcolor{blue}{$41\%$} & $35\%$ \\
    AIAC QM & $30\%$ & $32\%$ & $30\%$ \\
    \hline
%    F-EC & $39\%$ & $35\%$ & \textcolor{blue}{$45\%$} \\
    F-EC & $40\%$ & $37\%$ & $45\%$ \\
    \hline
  \end{tabular}
%  \caption{Parameters variations using a $500'000$ problem size on an
%    architecture of 5.37 heterogeneity degree}
  \caption{Gains in execution time with mapping algorithms parameters
    variations using the class E of the CG application using 64
    computing nodes}
%  \vspace*{-0.4cm}
  \label{tab:expparams}
%  \vspace*{-0.9cm}
\end{table}

%First of all, we can see that the Simple mapping provides the same
%order of performances, as shown in the precedent section, so it is
%not affected by the heterogeneity degree. Secondly, 
For the AIAC QM algorithm, we can note that the best value for its
parameter $f$ is about $50\%$, but its impact is not big enough to
indicate a specific configuration.
% With a low heterogeneity degree, this mapping algorithm provides a
% good performances improvement.
Finally, and this is not surprising, the F-EC algorithm is more
efficient with a factor $\delta$ near $100\%$, which directly comes
from its aim. But we can see that it is more efficient to have a
factor around $10\%$ than having one around $50\%$.

We can note here, with a lower heterogeneity degree than in previous
experiments, gains are lower and the difference between AIAC QM and
F-EC (with parameters at $50\%$) is lower. It can be explained as the
fact that more the heterogeneity degree tends to 0 more computing
nodes are the same, so a mapping solution will not be efficient,
except one only optimizing network latency.
%These experiments show that the impact of parameters values does not
%well influence the AIAC QM, whereas it is very important for the F-EC
%algorithm.

%\section{Discussion}
%\label{sec:discussion}
%
%In this paper three algorithms for mapping asynchronous iterative
%applications on heterogeneous distributed architectures are described.
%This approach is relatively new, so we had to study related works. We
%assume in our model that the amount of computation, the computational
%cost of each task, cannot be known in advance, and it is the same
%about communications. Two mains class of algorithms are mainly used,
%the ``execution time'' and the ``edge-cuts'' optimizations, with a
%newer preference fort the first one. Indeed, the efficiency of second
%one is criticized for its objectives, invoking the fact that these
%algorithms do not optimize the right metric. It is true in a broad
%spectrum of mapping domains, but we have shown that in our case, it
%could be an efficient solution, depending on the architecture
%heterogeneity.
%
%As each experiment takes a lot of time and the Grid'5000 platform is
%shared by many researchers, we could not conducted as many experiments
%as we wanted and as we need to purpose an exhaustive view of this part
%of the mapping domain. We cannot design a more general state of the
%mapping of asynchronous iterative applications on distributed
%architectures, but we can draw the main lines of future works.
%%, by
%%giving the first stones at the building of this specific part of the
%%mapping domain.
%
%We have shown that the heterogeneity in computing nodes power takes an
%important part in an efficient mapping algorithm. This parameter and
%probably the heterogeneity in network should really be more taken into
%consideration. Maybe a good solution consists in designing of mapping
%algorithms giving more important priority to one or to the other
%optimization objectives. This leads to design a novel algorithm, which
%takes into account the different points discussed in this paper, which
%would probably be an hybrid algorithm, efficient with our model on the
%targeted architectures.

\section{Conclusion and future works}
\label{sec:conclu}

In this paper we have presented 
%three algorithms to address the
%mapping problem for asynchronous iterative applications in
%heterogeneous distributed architectures. As the asynchronous iteration
%model is very specific, it was not clear of which kind of mapping
%algorithm should be efficient on such a problem. The two main
%approaches given in the literature, the ``execution time'' and the
%``edge-cuts'' optimization algorithms, have been evaluated on
%different architectures, with different heterogeneity degrees.
%% These architectures varied in their
%%heterogeneity, to evaluate the algorithms.
%
%%We proposed three mapping algorithms for the JaceP2P-V2
%%environment. The first is a simple way mapping, the Simple Mapping
%%algorithm, which always provides a good and stable improvement of
%%performances on all kinds of architectures. 
%We propose 
a specific mapping algorithm for the AIAC model, called AIAC QM. This
algorithm is based on the execution time optimization but it also
includes a small degree of edge-cuts optimization. Experiments on a
real large scale architecture of a typical AIAC application show that
the AIAC QM mapping algorithm is efficient on architectures with a
high heterogeneity degree. This can be explained by the fact that all
iteration computations are quite different, for our example, and the
convergence is more quickly detected as the more powerful computing
nodes progress in the computation. The F-EC algorithm, which is based
on the ``edge-cuts'' optimization, is meanwhile efficient on
architectures with a low heterogeneity degree. This can be explained
by the fact that in such an environment, it is more accurate for a
task to have its dependencies locally on the same cluster in order to
have efficient communications and to allow iterations to be computed
together, which improves the convergence detection speed.
Experiments we conducted have shown gains in execution time up to
$50\%$, which denotes a division by 2 of this execution time, for a
typical AIAC application on more than 700 computing cores.
%Experiments have shown that
%the importance of the parameter of both algorithms, AIAC QM and F-EC,
%is not so essential for the first one, instead it is very critical for
%the second one, but we cannot be sure that it is true all the time on
%all kinds of architectures; it maybe depends on the heterogeneity
%degree of the network. 
As we did not influence the network's heterogeneity,
% as we did for the computational power of nodes, 
the evaluation of the network impact on the
application execution time would be one of our next work.

%For now, these three mapping algorithms are implemented in an
%additional library for the JaceP2P-V2 environment. The results
%presented in this paper show that a mapping algorithm allows to
%improve applications performances, but as the executing architectures
%should have a variety of heterogeneity degree, we have to find a
%compromise between the two approaches in order to have an efficient
%mapping algorithm on all kinds of architectures. In the future, we
%would like to design an efficient mapping algorithm to improve the
%execution of asynchronous iteration applications on heterogeneous
%distributed architectures. As the algorithm should be integrated in
%the JaceP2P-V2 environment, which is fully decentralized and fault
%tolerant, the new mapping algorithm should have also these
%characteristics, in order to retrieve a fully decentralized and fault
%tolerant environment. 
Our future works concern the amelioration of the AIAC QM algorithm, in
order to improve it on homogeneous distributed architectures. As the
F-EC mapping algorithm is efficient on such architectures, we will
give a more important consideration to the edge-cuts part of AIAC
QM. Another important point is to take into consideration the fault
tolerance problem. In this study we have realized our experiments
without computing node fault, which is not the real case. We have to
take into account the AIAC QM algorithm about this important
parameter. First we have to efficiently choose new nodes to replace
failed ones. Secondly, as we do checkpointing to save tasks' states,
we have to efficiently choose backup nodes not to fall in case
a whole cluster fails, as we save on neighbors (which are
in general on the same cluster for communication efficiency reasons),
an important part of the application is lost and we cannot restart
this part; so the whole application fails. A trade-off should be done
by having some saving nodes in external clusters.

\section*{Acknowledgements}

\label{sec:merci}

This work was supported by the European Interreg IV From-P2P project
and the region of Franche-Comté.

Experiments presented in this paper were carried out using the
Grid'5000\cite{g5k} experimental testbed, being developed under the
INRIA ALADDIN development action with support from CNRS, RENATER and
several Universities as well as other funding bodies.


\bibliographystyle{unsrt}
%\nocite{*}
\bibliography{biblio}


\end{document}

%% %%