correction

[ThesisAhmed.git] / CHAPITRE_01.tex

diff --git a/CHAPITRE_01.tex b/CHAPITRE_01.tex
index dd97ab94921297505141f2328f2d13a4a3e9ef36..cc23717765e321288e5562d3bb956f3715e9a591 100644 (file)
--- a/CHAPITRE_01.tex
+++ b/CHAPITRE_01.tex
@@ -4,6 +4,15 @@
 %%                          %%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 %%                          %%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 

+
+% declaration of the new block
+\algblock{ParFor}{EndParFor}
+% customising the new block
+\algnewcommand\algorithmicparfor{\textbf{parfor}}
+\algnewcommand\algorithmicpardo{\textbf{do}}
+\algnewcommand\algorithmicendparfor{\textbf{end\ parfor}}
+\algrenewtext{ParFor}[1]{\algorithmicparfor\ #1\ \algorithmicpardo}
+\algrenewtext{EndParFor}{\algorithmicendparfor}

 \chapter{Parallel Architectures and  Iterative Applications}
 \label{ch1}
 %% Introduction
 \chapter{Parallel Architectures and  Iterative Applications}
 \label{ch1}
 %% Introduction


@@ -18,30 +27,29 @@ are executed successively one after the other. For many years until a short time
 with each new generation of microprocessors,  users of  sequential applications expected that these applications should run faster over them than over the previous ones.
 Nowadays, this idea is no longer valid  since  recent releases of  microprocessors have many computing units that are embedded in one chip and  programs are  running  only over one computing unit sequentially.
 Indeed, new applications have significantly improved  their performance over  new architectures in parallel compared to traditional applications.
 with each new generation of microprocessors,  users of  sequential applications expected that these applications should run faster over them than over the previous ones.
 Nowadays, this idea is no longer valid  since  recent releases of  microprocessors have many computing units that are embedded in one chip and  programs are  running  only over one computing unit sequentially.
 Indeed, new applications have significantly improved  their performance over  new architectures in parallel compared to traditional applications.

-To improve the performance  of  applications, they should parallelized  and executed simultaneously over all available  computing units. 
-Furthermore, the concurrency revolution has been referred  primarily to software revolution, that all applications are amenable to parallelization over the  new parallel architectures \cite{ref51}. 
-Moreover,  parallel applications should be optimized to the  parallel  hardware that  must execute them. 
+To improve the performance  of  applications, they should be parallelized  and executed simultaneously over all available computing units. 
+Moreover, parallel applications should be optimized to the  parallel  hardwares that  will execute them. 

 Therefore, parallel applications and parallel architectures are closely tied together. 
 Therefore, parallel applications and parallel architectures are closely tied together. 

-For example, the energy consumption of one parallel system mainly depends on both: (1) parallel applications and (2) parallel architectures. Indeed, an energy consumption model or any measurement system depends on many specifications, some of them are related to the  parallel hardware features such as: (1) the frequency of  processor, (2) the  power consumption of processor and (3) the communication model.  Others are relied to  the parallel application such as: (1) the computation time and (2) the communication time of the application. 
+For example, the energy consumption of one parallel system mainly depends on both: (1) parallel applications and (2) parallel architectures. Indeed, an energy consumption model or any measurement system depends on many specifications, some of them are related to the  parallel hardware features such as: (1) the frequency of  processor, (2) the  power consumption of processor and (3) the communication model.  Others rely to the parallel application such as: (1) the computation time and (2) the communication time of the application. 

 
 
 
 

-This work is focused on studying the iterative parallel  applications, where different parallel architectures
+This work of this thesis is focused on studying the iterative parallel  applications, where different parallel architectures

 are used to execute them in parallel, while optimizing their energy consumptions.   
 In this context, this chapter gives a brief overview about parallel hardware architectures and  parallel iterative applications. Also, it discusses an energy model proposed by other authors used to measure the energy consumption of these applications. 
 are used to execute them in parallel, while optimizing their energy consumptions.   
 In this context, this chapter gives a brief overview about parallel hardware architectures and  parallel iterative applications. Also, it discusses an energy model proposed by other authors used to measure the energy consumption of these applications. 

-The reminder of this chapter is organized as follows: section \ref{ch1:2} describes different types of  parallelism and different types of  parallel platforms. It also explains some models of parallel programming.  Section \ref{ch1:3} discusses both types of parallel iterative methods, synchronous and asynchronous one and comparing them. Section \ref{ch1:4}, presents a well accepted energy model from the state of the art that can be used to measure the energy consumption of parallel iterative applications when  the frequency of  processor is changed. Finally, section \ref{ch1:5} summarizes this chapter.
+The reminder of this chapter is organized as follows: section \ref{ch1:2} describes different types of  parallelism and different types of  parallel platforms. It also explains some models of parallel programming.  Section \ref{ch1:3} discusses both types of parallel iterative methods, synchronous and asynchronous ones and comparing them. Section \ref{ch1:4}, presents a well accepted energy model from the state of the art that can be used to measure the energy consumption of parallel iterative applications when  the frequency of  processor is changed. Finally, section \ref{ch1:5} summarizes this chapter.

 
 
 \section{Parallel Computing  Architectures} 
 \label{ch1:2}
 The process of executing the calculations simultaneously over many computing units is called  parallel computing.
 Its main principle refers to the ability of dividing a large problem into  smaller sub-problems that can be solved at the same time \cite{ref2}. 
 
 
 \section{Parallel Computing  Architectures} 
 \label{ch1:2}
 The process of executing the calculations simultaneously over many computing units is called  parallel computing.
 Its main principle refers to the ability of dividing a large problem into  smaller sub-problems that can be solved at the same time \cite{ref2}. 

-Solving the sub-problems of one main problem in  parallel computing is carried out in parallel  on multiple  processors.
+Solving the sub-problems of one main problem in  parallel  is carried out in parallel  on multiple  processors.

 Indeed, a parallel  architecture can be defined as a computing system that is composed of many processing elements, which are connected via a network model and some tools that are used to make the processing units work together  \cite{ref1}.
 In other words, the parallel computing architecture consists of  software and hardware resources. 
 Hardware resources are: (1) the processing units, (2) the memory model and (3) the network system that connects them. Software resources include (1) the specific operating system, (2) the programming language and (3) the compile or the runtime libraries. Besides,  parallel computing may have different levels of parallelism that can be performed in a software or a hardware level. Five types of parallelism levels have been defined as follows:
 \begin{itemize}
 
 Indeed, a parallel  architecture can be defined as a computing system that is composed of many processing elements, which are connected via a network model and some tools that are used to make the processing units work together  \cite{ref1}.
 In other words, the parallel computing architecture consists of  software and hardware resources. 
 Hardware resources are: (1) the processing units, (2) the memory model and (3) the network system that connects them. Software resources include (1) the specific operating system, (2) the programming language and (3) the compile or the runtime libraries. Besides,  parallel computing may have different levels of parallelism that can be performed in a software or a hardware level. Five types of parallelism levels have been defined as follows:
 \begin{itemize}
 

-\item \textbf{Bit-level parallelism (BLP)}: The appearance of  very-large-scale integration (VLSI) in 1970s has been viewed as the first step towards  parallel computing. It is used to increase the number of bits  in the word size which is processed by a processor as illustrated in the figure~\ref{fig:ch1:1}. For many successive years, the number of bits have been increased starting from 4 bit to 64 bit microprocessors. For example nowadays, the recent x86-64 architecture is the most common architecture. For a given application, the biggest the word size is the lesser in instructions to be executed by the processor.
+\item \textbf{Bit-level parallelism (BLP)}: The appearance of  very-large-scale integration (VLSI) in 1970s has been viewed as the first step towards  parallel computing. It is used to increase the number of bits  in the word size which is processed by a processor as illustrated in the figure~\ref{fig:ch1:1}. For many successive years, the number of bits have been increased starting from 4 bit to 64 bit microprocessors. For example nowadays, the recent x86-64 architecture is the most common architecture. For a given application, the biggest the word size is the lesser  instructions to be executed by the processor.

  
 \begin{figure}[h!]
 \centering
  
 \begin{figure}[h!]
 \centering


@@ -50,7 +58,7 @@ Hardware resources are: (1) the processing units, (2) the memory model and (3) t
 \label{fig:ch1:1}
 \end{figure}
 
 \label{fig:ch1:1}
 \end{figure}
 

-\item \textbf{Data-level parallelism (DLP)}: Data parallelism is the process of distributing  data vector between   parallel processors, where each one performs the same operations on its data sub-vector. Therefore, many arithmetic operations can be performed on the same data vector in a simultaneous manner. This type of parallelism can be used in many programs, especially in the area of scientific computing. Usually, data-parallel operations are only provided to arrays operations, for example, as shown in figure \ref{fig:ch1:2}.  Vector multiplication, image and signal processing can be considered as an example of applications that use this type of parallelism. 
+\item \textbf{Data-level parallelism (DLP)}: Data parallelism is the process of distributing  data vector between  processors, where each one performs the same operations on its data sub-vector. Therefore, many arithmetic operations can be performed on the same data vector in a simultaneous manner. This type of parallelism can be used in many programs, especially in the area of scientific computing. Usually, data-parallel operations are only provided to arrays operations, for example, as shown in figure \ref{fig:ch1:2}.  Vector multiplication, image and signal processing can be considered as an example of applications that use this type of parallelism. 

 
 \begin{figure}[h!]
 \centering
 
 \begin{figure}[h!]
 \centering


@@ -76,7 +84,7 @@ Figure~\ref{fig:ch1:3} demonstrates four instructions, where each one has four s
 \item \textbf{Thread-level parallelism (TLP)}: It is also known as  task-level parallelism.
 According to  Moore’s law \cite{ref9}, the number of transistors in a processor doubles each two years to increase its performance. Cache and main memory sizes  must also be increased in order to avoid data bottlenecks.
 However,  increasing the number of transistors may generate some issues: (1) the first issue is related to drastically  increase in  cache size, which leads to a large access time. (2) the second issue is related to the huge increase in the number of the transistors per CPU, which  can increase significantly the heat dissipation.
 \item \textbf{Thread-level parallelism (TLP)}: It is also known as  task-level parallelism.
 According to  Moore’s law \cite{ref9}, the number of transistors in a processor doubles each two years to increase its performance. Cache and main memory sizes  must also be increased in order to avoid data bottlenecks.
 However,  increasing the number of transistors may generate some issues: (1) the first issue is related to drastically  increase in  cache size, which leads to a large access time. (2) the second issue is related to the huge increase in the number of the transistors per CPU, which  can increase significantly the heat dissipation.

-Thus, CPUs constructors couldn't increase the frequency of the processor any more due to these reasons. Therefore, they created multi-core processor that  programmers subdivided their programs into multiple tasks which can be then executed in parallel over them to improve the performance, see figure~\ref{fig:ch1:4}. Each processor can have individual threads or multiple threads dedicated to each task. A thread can be defined as a part of the parallel program that shares processor resources with other threads. 
+Thus, CPUs constructors couldn't increase the frequency of the processor anymore due to these reasons. Therefore, they created multi-core processors. With multi-core processors, programmers subdivide their programs into multiple tasks which can be then executed in parallel over them to improve the performance, see figure~\ref{fig:ch1:4}. Each processor can have individual threads or multiple threads dedicated to each task. A thread can be defined as a part of the parallel program that shares processor resources with other threads. 

 
 \begin{figure}[h!]
 \centering
 
 \begin{figure}[h!]
 \centering


@@ -92,7 +100,7 @@ Therefore, the execution time of a sequential program that is composed of $N$ ta
     Sequential~execution~time = \sum_{i=1}^{N} T_i
 \end{equation}
 
     Sequential~execution~time = \sum_{i=1}^{N} T_i
 \end{equation}
 

-Whereas, if tasks are executed synchronously over multiple processing units in parallel, the execution time of the program is defined as the execution time of the task that has maximum execution time (the slowest task) as follows:
+Whereas, if tasks are executed synchronously over multiple processing units in parallel, the execution time of the program is defined as the execution time of the task that has maximum the execution time (the slowest task) as follows:

 
 \begin{equation}
 \label{ch1:eq2}
 
 \begin{equation}
 \label{ch1:eq2}


@@ -129,7 +137,7 @@ For more details about the levels of parallelism see \cite{ref3,ref4,ref6,ref7}.
 The main goal behind using a parallel architecture is to solve a big problem faster.
 A collection of processing elements must  work together to compute the final solution of the main problem. Many different architectures have been proposed  
 and classified according to  parallelism in  instruction and data
 The main goal behind using a parallel architecture is to solve a big problem faster.
 A collection of processing elements must  work together to compute the final solution of the main problem. Many different architectures have been proposed  
 and classified according to  parallelism in  instruction and data

-streams. In 1966, Michel Flynn has proposed a simple model to categorize all computers  models that still useful until now \cite{ref10}. His taxonomy is based on considering the data and the operations performed on this data to classify the computing system into four types as follows:
+streams. In 1966, Michel Flynn has proposed a simple model to categorize all computers  models that is still useful until now \cite{ref10}. His taxonomy is based on considering the data and the operations performed on this data to classify the computing systems into four types as follows:

 
 \begin{itemize}
  
 
 \begin{itemize}
  


@@ -255,16 +263,15 @@ some examples for each type of the parallel programming models are discussed:
                       The first version of MPI was designed by a group of researchers in
                       1991. It  is a specification and have been implemented in many programming 
                       languages such as C, Fortran and 
                       The first version of MPI was designed by a group of researchers in
                       1991. It  is a specification and have been implemented in many programming 
                       languages such as C, Fortran and 

-                      Java. Programmes  written in these languages are compiled MPI with ordinary compilers.  
-                      The functions are not only limited to  peer to peer operations for 
+                      Java.   
+                      The MPI functions are not only limited to  point to point operations for 

                       sending and receiving messages, there are many others collective 
                       sending and receiving messages, there are many others collective 

-                      operations such as gathering and reduction operations. Furthermore, it has an
-                      asynchronous point to point operations, which make the computations 
-                      to overlap with communications. While MPI is not designed for grid,
-                       \textbf{MPICH}  is widely used as the communication interface for grid  applications 
-                       \cite{ref52}. 
-                      In this work,   MPI was used  in programming  our algorithms and applications which are
-                      implemented in both Fortran and C programming languages.  
+                      operations such as gathering and reduction operations. 
+                      While MPI is not designed for grid,
+                      it  is widely used as the communication interface for grid  applications 
+                      \cite{ref52}. 
+                    In this work,   MPI was used  in programming  our algorithms and applications which are
+                    implemented in both Fortran and C programming languages.  

                       
                  
   \end{itemize} 
                       
                  
   \end{itemize} 


@@ -292,18 +299,19 @@ some examples for each type of the parallel programming models are discussed:
 \item \textbf{GPU programming models} 
   \begin{itemize}
    \item \textbf{CUDA} \cite{ref37} Modern graphical processing units (GPUs) have increased its chip-level  
 \item \textbf{GPU programming models} 
   \begin{itemize}
    \item \textbf{CUDA} \cite{ref37} Modern graphical processing units (GPUs) have increased its chip-level  

-                       parallelism.  Current  NVIDIA  GPUs  consist of many-cores processor that have 
+                       parallelism.  Current  NVIDIA  GPUs  consist of many-cores processors that have 

                        thousands of cores. To make their GPUs a general purpose computing processor in 2007 
                        thousands of cores. To make their GPUs a general purpose computing processor in 2007 

-                       the NVIDIA has  developed CUDA as parallel programming  language.
+                       the NVIDIA has  developed CUDA a parallel programming  language.

                        A CUDA program has two parts: host and kernels.  The host  code is  sequentially 
                        executed over the CPU. 
                        While, the kernels are executed in parallel over the GPUs.
  
    \item \textbf{OpenCL}\cite{ref38} is for Open Computing Language. It is a parallel 
                        programming language dedicated for heterogeneous platforms composed 
                        A CUDA program has two parts: host and kernels.  The host  code is  sequentially 
                        executed over the CPU. 
                        While, the kernels are executed in parallel over the GPUs.
  
    \item \textbf{OpenCL}\cite{ref38} is for Open Computing Language. It is a parallel 
                        programming language dedicated for heterogeneous platforms composed 

-                       of CPUs and GPUs. The first release of this language has initially developed by Apple  
-                       in 2008. Functions that are executed over OpenCL devices are called kernels. 
-                       They are portable and can be execute on any computing hardware such as CPU or GPU cores. 
+                       of CPUs and GPUs. The first release of this language has initially been developed 
+                       by Apple in 2008. Functions that are executed over OpenCL devices are called kernels. 
+                       They are portable and can be executed on any computing hardware such as CPU or GPU
+                       cores. 

                      
                          
                                    
                      
                          
                                    


@@ -315,8 +323,8 @@ some examples for each type of the parallel programming models are discussed:
 
 \section{Iterative Methods} 
 \label{ch1:3}
 
 \section{Iterative Methods} 
 \label{ch1:3}

-In this work, we are interesting in solving linear equations which are well known in the scientific  area.
-It is generally expressed in the following form:
+In this work, we are interested in solving system of linear equations which are very common in the scientific field. A system of linear equations can be expressed as follows:
+

 
 \begin{equation}
   \label{eq:linear}
 
 \begin{equation}
   \label{eq:linear}


@@ -324,14 +332,14 @@ It is generally expressed in the following form:
 \end{equation}
 
 Where $A$ is a two dimensional matrix of size $N \times N$, $x$ is the unknown vector,
 \end{equation}
 
 Where $A$ is a two dimensional matrix of size $N \times N$, $x$ is the unknown vector,

-and $b$ is a vector of constant, each of size $N$. There are two types of solution methods to solve this linear system.
-The first type of methods is called \textbf{Direct methods}, which consist of a finite number of steps depending on the 
-size  of the linear system to give the exact solution. If the problem size is very big, these methods are expensive or their
-solutions are impossible in some cases.  The second type is called \textbf{Iterative methods}, which computes 
-the same block of  operations  several times, starting from the initial vector until reaching  the acceptable 
-approximation  of the exact solution. However, it can be effectively applied in parallel. Moreover, iterative methods can be used to solve both  linear and non-linear equations.
+and $b$ is a vector of constant, each of size $N$. There are two types of solution methods to solve this linear system: the \textbf{direct} and the \textbf{iterative methods}.
+A direct method executes a finite number of steps, depending on the 
+size  of the linear system and gives the exact solution of the system. If the problem  is very big, this method is expensive or its
+solution is impossible in some cases.  On the other hand, methods with iterations execute the same block of instructions many times. The number of iterations can be predefined or the application iterates until a criterion is satisfied. Iterative methods are methods with iterations that start from an initial guess and 
+improve successively the solution until reaching an acceptable approximation of the exact solution. 
+These methods are well adapted for large systems and can be easily parallelized. 

 
 

-The sequential iterative algorithm is typically organized as a series of steps essentially  of the form:
+A sequential iterative algorithm is typically organized as a series of steps essentially  of the form:

 
 \begin{equation}
   \label{eq:iter}
 
 \begin{equation}
   \label{eq:iter}


@@ -364,6 +372,7 @@ The sequential iterative algorithm at each iteration computes the value of the r
 \end{equation}  
 Where $N$ is the size of the vector $X$. Then, the iterative sequential algorithm stops  iterating if the maximum error between the last two successive solution vectors, as in \ref{eq:res}, is less than or equal to a threshold value. Otherwise, it replaces the new vector $X^{(k+1)}$ with the old vector $X^k$ and computes a new iteration.
 
 \end{equation}  
 Where $N$ is the size of the vector $X$. Then, the iterative sequential algorithm stops  iterating if the maximum error between the last two successive solution vectors, as in \ref{eq:res}, is less than or equal to a threshold value. Otherwise, it replaces the new vector $X^{(k+1)}$ with the old vector $X^k$ and computes a new iteration.
 

+

 \subsection{Synchronous Parallel Iterative method} 
 \label{ch1:3:1}
 The sequential iterative algorithm \ref{sia} can be parallelized by executing it on many computing units. To solve this algorithm on $M$ computing units, first the elements of the problem vector $X$ must be subdivided into $M$ sub-vectors, $X^k=(X_1^k,\dots,X_M^k)$. 
 \subsection{Synchronous Parallel Iterative method} 
 \label{ch1:3:1}
 The sequential iterative algorithm \ref{sia} can be parallelized by executing it on many computing units. To solve this algorithm on $M$ computing units, first the elements of the problem vector $X$ must be subdivided into $M$ sub-vectors, $X^k=(X_1^k,\dots,X_M^k)$. 


@@ -381,9 +390,9 @@ Where $X_i^k$ is the sub-vector executed over the $i^{th}$ computing unit at the
   
   \State Initialize the sub-vectors $(X_1^0,\dots,X_M^0)$   
     \For {$k:=1$  step $1$ to \textit{convergence}}
   
   \State Initialize the sub-vectors $(X_1^0,\dots,X_M^0)$   
     \For {$k:=1$  step $1$ to \textit{convergence}}

-       \For {$i:=1$   to \textit{M}}
+       \ParFor {$i:=1$   to \textit{M}}

         \State $X^{(k+1)} = F(X^k)$
         \State $X^{(k+1)} = F(X^k)$

-      \EndFor
+      \EndParFor

     \EndFor  
 
    
     \EndFor  
 
    


@@ -395,8 +404,9 @@ Where $X_i^k$ is the sub-vector executed over the $i^{th}$ computing unit at the
 
 The algorithm \ref{spia} represents the synchronous parallel iterative algorithm. Similarly to 
 the sequential iterative algorithm \ref{spia}, this algorithm stops iterating when the convergence condition  is satisfied.
 
 The algorithm \ref{spia} represents the synchronous parallel iterative algorithm. Similarly to 
 the sequential iterative algorithm \ref{spia}, this algorithm stops iterating when the convergence condition  is satisfied.

+We consider that the keyword \textbf{parfor} is used to make a for loop in parallel.

 
 

-This algorithm needs to satisfy some convergence condition which  is called the  global convergence condition. In order to detect the global convergence overall computing units, first we need to compute
+This algorithm needs to satisfy a convergence condition which  is called the  global convergence condition. In order to detect the global convergence overall computing units, first we need to compute

 at each iteration the local residual. Then at the end of each iteration, all the local residuals  from $M$ computing units must be reduced to one maximum  value represented by the  global residual.
 For example, in MPI this operation is directly applied using a high level communication procedure  called \textit{AllReduce}. The goal of this communication procedure is to apply the reduction operation on all local residuals computed by the computing units.
 
 at each iteration the local residual. Then at the end of each iteration, all the local residuals  from $M$ computing units must be reduced to one maximum  value represented by the  global residual.
 For example, in MPI this operation is directly applied using a high level communication procedure  called \textit{AllReduce}. The goal of this communication procedure is to apply the reduction operation on all local residuals computed by the computing units.
 


@@ -424,9 +434,9 @@ Accordingly, this algorithm can be  effectively run over a local cluster, where
 \label{fig:ch1:16}
 \end{figure}
 
 \label{fig:ch1:16}
 \end{figure}
 

-Furthermore, the communications of the synchronous iterative algorithm can be replaced by asynchronous ones. The resulting algorithm is called  Synchronous Iteration and Asynchronous 
-Communication  and denoted as \textbf{SIAC} algorithm. The main principle of this algorithm is to use a synchronized iterations while exchanging the data between the computing units asynchronously.
-Moreover, each computing unit doesn't need to wait for its neighbours to receive the data messages 
+Furthermore, the communications of the synchronous iterative algorithm can be replaced by asynchronous ones. The resulting algorithm is called  Synchronous Iterations with Asynchronous 
+Communications  and denoted as \textbf{SIAC} algorithm. The main principle of this algorithm is to use  synchronize iterations while exchanging the data between the computing units asynchronously.
+Moreover, each computing unit does not need to wait for its neighbours to receive the data messages 

 that it has sent, while it only waits to receive  data from them. This can be implemented with SISC algorithm that is programmed in MPI by replacing the synchronous send of the messages by asynchronous ones, while keeping  
 the synchronous receive. The only advantage of this technique is to reduce the idle times between iterations by allowing the communications to overlap partially
 with computations, see figure \ref{fig:ch1:16}. The idle times are not totally eliminated  because the
 that it has sent, while it only waits to receive  data from them. This can be implemented with SISC algorithm that is programmed in MPI by replacing the synchronous send of the messages by asynchronous ones, while keeping  
 the synchronous receive. The only advantage of this technique is to reduce the idle times between iterations by allowing the communications to overlap partially
 with computations, see figure \ref{fig:ch1:16}. The idle times are not totally eliminated  because the


@@ -437,8 +447,8 @@ SISC and SIAC algorithms are not tolerant to the loss of data messages. Conseque
  
 \subsection{Asynchronous Parallel Iterative method} 
 \label{ch1:3:2}
  
 \subsection{Asynchronous Parallel Iterative method} 
 \label{ch1:3:2}

-The asynchronous iterations mean that all processors perform their iterations without considering the works of  other processors. Each processor doesn't have to wait to receive 
-data messages from  other processors and continues to compute the next iteration using the last data received from neighbours. Therefore, there  are no  idle times at all between the iterations as in figure \ref{fig:ch1:17}.  This figure indicates that  fast processors can perform more iterations than  the slower ones at the same time. 
+The asynchronous iterations mean that all processors perform their iterations without considering the works of  other processors. Each processor does not have to wait to receive 
+data messages from  other processors and continues to compute the next iteration using the last data received from neighbours. Therefore, there  are no  idle times at all between the iterations as in Figure \ref{fig:ch1:17}.  This figure indicates that  fast processors can perform more iterations than  the slower ones at the same time. 

 The asynchronous iterative algorithm that uses an asynchronous communications  is called  \textbf{AIAC} algorithm. Similarly to the SISC algorithm, the AIAC algorithm subdivides the global vectors $X$ into $M$ sub-vectors between the computing units. The main difference between the two algorithms is that these $M$ sub-vectors are not updated at each iteration in the AIAC algorithm because both  iterations and communications are asynchronous. 
 
 
 The asynchronous iterative algorithm that uses an asynchronous communications  is called  \textbf{AIAC} algorithm. Similarly to the SISC algorithm, the AIAC algorithm subdivides the global vectors $X$ into $M$ sub-vectors between the computing units. The main difference between the two algorithms is that these $M$ sub-vectors are not updated at each iteration in the AIAC algorithm because both  iterations and communications are asynchronous. 
 
 


@@ -449,7 +459,7 @@ The asynchronous iterative algorithm that uses an asynchronous communications  i
 \label{fig:ch1:17}
 \end{figure}
 
 \label{fig:ch1:17}
 \end{figure}
 

-The global convergence detection of the asynchronous parallel iterative is problem dependent process.
+The global convergence detection of the asynchronous parallel iterative is not trivial.

 For more information about the convergence detection techniques of the asynchronous iterative methods, refer to \cite{ref40,ref41,ref42,ref43} for more details. 
 
 
 For more information about the convergence detection techniques of the asynchronous iterative methods, refer to \cite{ref40,ref41,ref42,ref43} for more details. 
 
 


@@ -460,7 +470,7 @@ The implementation of the AIAC method is not easy, but it gives many advantages
       to receive the data messages from its neighbours to compute the next iteration.
       
 \item Less sensitive for the heterogeneous communications and nodes' computing powers. In heterogeneous 
       to receive the data messages from its neighbours to compute the next iteration.
       
 \item Less sensitive for the heterogeneous communications and nodes' computing powers. In heterogeneous 

-      platform, the fast nodes don't need to wait for the slow ones, and they can  perform more iterations
+      platform, the fast nodes do not need to wait for the slow ones, and they can  perform more iterations

       compared to them. While in the traditional synchronous iterative methods, the fast computing nodes perform
       the same number of iterations as the slow ones because they are blocked. 
 
       compared to them. While in the traditional synchronous iterative methods, the fast computing nodes perform
       the same number of iterations as the slow ones because they are blocked. 
 


@@ -472,7 +482,7 @@ The implementation of the AIAC method is not easy, but it gives many advantages
 \item In the grid architecture, the local clusters from different sites are 
       connected via a slow network with a high latency. The use of the AIAC model 
       reduces the delay of sending the data message over such slow network link and thus the performance 
 \item In the grid architecture, the local clusters from different sites are 
       connected via a slow network with a high latency. The use of the AIAC model 
       reduces the delay of sending the data message over such slow network link and thus the performance 

-      of the applications is not effected.
+      of the applications is not affected.

 \end{itemize}
 
 
 \end{itemize}
 
 


@@ -501,8 +511,8 @@ disadvantages that can be summarized by these points:
 \end{itemize}
 
 
 \end{itemize}
 
 

-In our works, we are interested in optimizing the energy consumption of parallel iterative methods running over 
-clusters or grids. 
+In work of this thesis, we are interested in optimizing the energy consumption of parallel iterative 
+methods running over clusters or grids. 

 
 
 
 
 
 


@@ -632,7 +642,7 @@ Finally, model \ref{eq:energy}  can be used to measure the energy consumed by an
 
 There are two drawbacks in this energy model as follows:
 \begin{itemize}
 
 There are two drawbacks in this energy model as follows:
 \begin{itemize}

-\item The message passing iterative program consists of the communication and computation times.
+\item The message passing iterative program consists of  communication and computation times.

       This energy model assumes that the dynamic power is consumed during both these times.
       While the processor during the communication times remains idle and only consumes the static 
       power, for more details see \cite{ref53}. 
       This energy model assumes that the dynamic power is consumed during both these times.
       While the processor during the communication times remains idle and only consumes the static 
       power, for more details see \cite{ref53}. 


@@ -653,4 +663,4 @@ Both  shared and distributed platforms as well as their depending parallel progr
 In the second section, the two types of parallel iterative methods: synchronous and asynchronous ones were presented. The synchronous iterative methods are well adapted to local homogeneous clusters with a high speed network link, while the asynchronous iterative methods are more suited to the distributed heterogeneous clusters. 
 Finally, in the third section, an energy consumption model proposed in the state of the art to  measure the energy consumption of parallel applications was explained. This model  cannot be used for all types of parallel architectures. Since, it assumes  that the dynamic power is consumed during both of the communication and computation times, while the processor involved remains idle during the communication times and  only consumes the static power. Moreover, it is not well adapted to  heterogeneous architectures when there are different types of processors, that consume different dynamic and static powers.
 
 In the second section, the two types of parallel iterative methods: synchronous and asynchronous ones were presented. The synchronous iterative methods are well adapted to local homogeneous clusters with a high speed network link, while the asynchronous iterative methods are more suited to the distributed heterogeneous clusters. 
 Finally, in the third section, an energy consumption model proposed in the state of the art to  measure the energy consumption of parallel applications was explained. This model  cannot be used for all types of parallel architectures. Since, it assumes  that the dynamic power is consumed during both of the communication and computation times, while the processor involved remains idle during the communication times and  only consumes the static power. Moreover, it is not well adapted to  heterogeneous architectures when there are different types of processors, that consume different dynamic and static powers.
 

-For these reasons, in the next chapters of this thesis  new energy consumption models are developed to effectively predict the energy consumed by parallel iterative methods running on both homogeneous and heterogeneous architectures.  Additionally, these energy models are used in a method  optimizes  both  energy consumption and performance of an iterative message passing application. 
\ No newline at end of file
+For these reasons, in the next chapters of this thesis  new energy consumption models are developed to efficiently predict the energy consumed by parallel iterative methods running on both homogeneous and heterogeneous architectures.  Additionally, these energy models are used in a method  that optimizes  both  energy consumption and performance of an iterative message passing application. 
\ No newline at end of file