From c9066e476a4a5b2bdba5c2eb18ad0aa2ad1d2bb3 Mon Sep 17 00:00:00 2001 From: raphael couturier Date: Sun, 27 Apr 2014 16:33:51 +0200 Subject: [PATCH 1/1] modif dans partie 2 --- hpcc.tex | 94 +++++++++++++++++++++++++++++++++----------------------- 1 file changed, 56 insertions(+), 38 deletions(-) diff --git a/hpcc.tex b/hpcc.tex index 29d00a1..e043c78 100644 --- a/hpcc.tex +++ b/hpcc.tex @@ -170,25 +170,31 @@ out will be presented before some concluding remarks and future works. \section{Motivations and scientific context} -As exposed in the introduction, parallel iterative methods are now widely used in many scientific domains. They can be -classified in three main classes depending on how iterations and communications are managed (for more details readers -can refer to~\cite{bcvc06:ij}). In the \textit{Synchronous Iterations~-- Synchronous Communications (SISC)} model data -are exchanged at the end of each iteration. All the processors must begin the same iteration at the same time and -important idle times on processors are generated. The \textit{Synchronous Iterations~-- Asynchronous Communications -(SIAC)} model can be compared to the previous one except that data required on another processor are sent asynchronously -i.e. without stopping current computations. This technique allows to partially overlap communications by computations -but unfortunately, the overlapping is only partial and important idle times remain. It is clear that, in a grid -computing context, where the number of computational nodes is large, heterogeneous and widely distributed, the idle -times generated by synchronizations are very penalizing. One way to overcome this problem is to use the -\textit{Asynchronous Iterations~-- Asynchronous Communications (AIAC)} model. Here, local computations do not need to -wait for required data. Processors can then perform their iterations with the data present at that time. Figure~\ref{fig:aiac} -illustrates this model where the gray blocks represent the computation phases, the white spaces the idle -times and the arrows the communications. -\AG{There are no ``white spaces'' on the figure.} -With this algorithmic model, the number of iterations required before the -convergence is generally greater than for the two former classes. But, and as detailed in~\cite{bcvc06:ij}, AIAC -algorithms can significantly reduce overall execution times by suppressing idle times due to synchronizations especially -in a grid computing context.\LZK{Répétition par rapport à l'intro} +As exposed in the introduction, parallel iterative methods are now widely used +in many scientific domains. They can be classified in three main classes +depending on how iterations and communications are managed (for more details +readers can refer to~\cite{bcvc06:ij}). In the \textit{Synchronous Iterations~-- + Synchronous Communications (SISC)} model data are exchanged at the end of each +iteration. All the processors must begin the same iteration at the same time and +important idle times on processors are generated. The \textit{Synchronous + Iterations~-- Asynchronous Communications (SIAC)} model can be compared to the +previous one except that data required on another processor are sent +asynchronously i.e. without stopping current computations. This technique +allows to partially overlap communications by computations but unfortunately, +the overlapping is only partial and important idle times remain. It is clear +that, in a grid computing context, where the number of computational nodes is +large, heterogeneous and widely distributed, the idle times generated by +synchronizations are very penalizing. One way to overcome this problem is to use +the \textit{Asynchronous Iterations~-- Asynchronous Communications (AIAC)} +model. Here, local computations do not need to wait for required +data. Processors can then perform their iterations with the data present at that +time. Figure~\ref{fig:aiac} illustrates this model where the gray blocks +represent the computation phases. With this algorithmic model, the number of +iterations required before the convergence is generally greater than for the two +former classes. But, and as detailed in~\cite{bcvc06:ij}, AIAC algorithms can +significantly reduce overall execution times by suppressing idle times due to +synchronizations especially in a grid computing context. +%\LZK{Répétition par rapport à l'intro} \begin{figure}[!t] \centering @@ -197,26 +203,38 @@ in a grid computing context.\LZK{Répétition par rapport à l'intro} \label{fig:aiac} \end{figure} +\RC{Je serais partant de virer AIAC et laisser asynchronous algorithms... à voir} + +%% It is very challenging to develop efficient applications for large scale, +%% heterogeneous and distributed platforms such as computing grids. Researchers and +%% engineers have to develop techniques for maximizing application performance of +%% these multi-cluster platforms, by redesigning the applications and/or by using +%% novel algorithms that can account for the composite and heterogeneous nature of +%% the platform. Unfortunately, the deployment of such applications on these very +%% large scale systems is very costly, labor intensive and time consuming. In this +%% context, it appears that the use of simulation tools to explore various platform +%% scenarios at will and to run enormous numbers of experiments quickly can be very +%% promising. Several works\dots{} + +%% \AG{Several works\dots{} what?\\ +% Le paragraphe suivant se trouve déjà dans l'intro ?} +In the context of asynchronous algorithms, the number of iterations to reach the +convergence depends on the delay of messages. With synchronous iterations, the +number of iterations is exactly the same than in the sequential mode (if the +parallelization process does not change the algorithm). So the difficulty with +asynchronous algorithms comes from the fact it is necessary to run the algorithm +with real data. In fact, from an execution to another the order of messages will +change and the number of iterations to reach the convergence will also change. +According to all the parameters of the platform (number of nodes, power of +nodes, inter and intra clusrters bandwith and latency, ....) and of the +algorithm (number of splitting with the multisplitting algorithm), the +multisplitting code will obtain the solution more or less quickly. Or course, +the GMRES method also depends of the same parameters. As it is difficult to have +access to many clusters, grids or supercomputers with many different network +parameters, it is interesting to be able to simulate the behaviors of +asynchronous iterative algoritms before being able to runs real experiments. + -It is very challenging to develop efficient applications for large scale, -heterogeneous and distributed platforms such as computing grids. Researchers and -engineers have to develop techniques for maximizing application performance of -these multi-cluster platforms, by redesigning the applications and/or by using -novel algorithms that can account for the composite and heterogeneous nature of -the platform. Unfortunately, the deployment of such applications on these very -large scale systems is very costly, labor intensive and time consuming. In this -context, it appears that the use of simulation tools to explore various platform -scenarios at will and to run enormous numbers of experiments quickly can be very -promising. Several works\dots{} - -\AG{Several works\dots{} what?\\ - Le paragraphe suivant se trouve déjà dans l'intro ?} -In the context of AIAC algorithms, the use of simulation tools is even more -relevant. Indeed, this class of applications is very sensible to the execution -environment context. For instance, variations in the network bandwidth (intra -and inter-clusters), in the number and the power of nodes, in the number of -clusters\dots{} can lead to very different number of iterations and so to very -different execution times. -- 2.39.5