Merge branch 'master' of ssh://bilbo.iut-bm.univ-fcomte.fr/ThesisAhmed

[ThesisAhmed.git] / CHAPITRE_01.tex

diff --git a/CHAPITRE_01.tex b/CHAPITRE_01.tex
index 8c68324a2308d867a1567dd91081375b487ba80b..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


@@ -12,37 +21,35 @@
 \section{Introduction}
 \label{ch1:1}
 
 \section{Introduction}
 \label{ch1:1}
 

-Referred to the state of the art, specifically Von Neumann report in 1993 \cite{ref50}, most of the software applications are structured as sequential programs.
-The structure of the program code is understandable by the human brain as a series of instructions that
+Most of the software applications are structured as sequential programs.
+The structure of the program code is  a series of instructions that

 are executed successively one after the other. For many years until a short time,
 are executed successively one after the other. For many years until a short time,

-with each new generation of microprocessors,  users of  sequential applications have believed that these applications must run faster over them than previous ones.
+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.
 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.

-In this context,  the aim of improving the performance  of parallel applications is executed simultaneously over all available  computing units. 
- Furthermore, the concurrency revolution has been referred to the drastic improvement in the performance of new applications side by side to  new parallel architectures \cite{ref51}. Therefore, parallel applications and parallel architectures are closely tied together. 
-Moreover, thinking about parallel applications is directly related to think about  parallel  hardware that  must support them. 
-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. 
-
+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. 
+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
-are used to run them in parallel, which is considered as ultimate goal to optimize their energy consumptions.   

 
 

+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. 
 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}
 
 
 \section{Parallel Computing  Architectures} 
 \label{ch1:2}

-The process of executing the calculations simultaneously is called  parallel computing.
-Its main principle refers to the ability of dividing a large problem into a smaller sub-problems that can be solved at the same time \cite{ref2}. 
-Mainly, solving  sub-problems of one main problem in  parallel computing is carried out on multiple parallel processors.
-Indeed, parallel processor architecture can be defined as a computer system that is composed of many processing elements,
-which are connected via network model in addition to  software tools that are required to make the processing units work together  \cite{ref1}.
-In other words, the parallel computing architecture consists of a software and hardware resources. 
-Hardware resources are: (1) the processing units, (2) the memory model and (3) the network system that is used to connect 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. In this context, five types of parallelism levels have been defined as follows:
+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  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}
 
 \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, recent x86-64 architecture becomes the most familiar architecture. Noting that, the biggest word size is  the more parallelism level. Thus, it reflects to less instructions to be executed by a 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


@@ -51,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 different 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


@@ -61,7 +68,7 @@ Hardware resources are: (1) the processing units, (2) the memory model and (3) t
 \end{figure}
 
 
 \end{figure}
 
 

-\item \textbf{Instruction-level parallelism (ILP)}: Generally, a sequential program is composed of many instructions. These instructions can be executed in  parallel at the same time, if each of them is independent from  others. In particular, the parallelism can be achieved in  instruction level by using a pipeline. It means all independent instructions of a program are overlapped the execution of each others. For example, if we have two instructions: $I_1$ and $I_2$, they are independent if there is no control and no data dependency between them.
+\item \textbf{Instruction-level parallelism (ILP)}: Generally, a sequential program is composed of many instructions. These instructions can be executed in  parallel at the same time, if each one of them is independent from the others. In particular, the parallelism can be achieved in  instruction level by using a pipeline. It means the input and output times of each instruction is overlapped by computations from other instructions. For example, if we have two instructions: $I_1$ and $I_2$, they are independent if there is no control and no data dependency between them.

 In pipeline stages, the execution of each instruction is divided into multiple steps. Then, they can be overlapped with the steps of other instructions by a pipeline hardware unit.
 Figure~\ref{fig:ch1:3} demonstrates four instructions, where each one has four steps denoted as: (1) fetch, (2) decode, (3) execute and  (4) write. Thus, they are implemented in hardware units by pipeline. 
 
 In pipeline stages, the execution of each instruction is divided into multiple steps. Then, they can be overlapped with the steps of other instructions by a pipeline hardware unit.
 Figure~\ref{fig:ch1:3} demonstrates four instructions, where each one has four steps denoted as: (1) fetch, (2) decode, (3) execute and  (4) write. Thus, they are implemented in hardware units by pipeline. 
 


@@ -75,10 +82,9 @@ 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.
 
 
 \item \textbf{Thread-level parallelism (TLP)}: It is also known as  task-level parallelism.

-According to  Moore’s law \cite{ref9}, the processor can have a number of transistors
-that must doubled each two years to increase the frequency of processor, and consequently its improving 
-performance. Besides, cache and main memory sizes  must be increased together to response to this new change. 
-However, this provides 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. For that reasons,  programmers subdivided their programs into multiple tasks which can be then executed in parallel over distributed processors or shared multi-cores processors 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. 
+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 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


@@ -94,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}


@@ -102,10 +108,9 @@ Whereas, if tasks are executed synchronously over multiple processing units in p
 \end{equation}
 
 \item \textbf{Loop-level parallelism (LLP)}:
 \end{equation}
 
 \item \textbf{Loop-level parallelism (LLP)}:

-The numerical algorithms and many other algorithms are executed iteratively the same program portion,  computations, using different forms of the loop statements that are allowed in the programming languages. At each iteration, the program needs to scan a large data structure such as  array structure to perform the arithmetic calculations. Inside the loop structure, there are many instructions that are  dependent or independent. In a sequential loop execution,  the $i$ iteration must be executed after the completion of 
-$(i-1)$ iteration. 
-Whereas, if each iteration is independent from  others, then  all  iterations' instructions are distributed over many  processors to be executed in  parallel 
-for example, see figure\ref{fig:ch1:5}. In the parallel programming languages, this type of loop is  called $parallel~loop$.
+Many  algorithms  execute iteratively the same program portion,  computations, many times using different forms of loop statements. At each iteration, the program needs to scan a large data structure such as  an array structure to perform the arithmetic calculations. Inside the loop structure, there are many instructions that are  dependent or independent. In a sequential loop execution,  the $i$ iteration must be executed after the completion of the $(i-1)$ iteration. 
+If each iteration is independent from the others, then  all  iterations' instructions can be distributed over many  processors to be executed in  parallel,  
+for example, see figure\ref{fig:ch1:5}. In the parallel programming languages, this type of loop is  called the  $parallel~loop$.

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


@@ -129,15 +134,15 @@ For more details about the levels of parallelism see \cite{ref3,ref4,ref6,ref7}.
 
 \subsection{Types of Parallel platforms} 
 \label{ch1:2:1}
 
 \subsection{Types of Parallel platforms} 
 \label{ch1:2:1}

-The main goal behind using parallel computer is to solve the bigger problem faster.
-A collection of processing elements must  work together to perform the final solution of the main problem. However, many different architectures have been proposed  
+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
 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 produce four types of computer systems 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}
  
 \item \textbf{Single instruction, single data (SISD) stream}: A single processor that executes a single instruction stream (i.e executing one data stream stored in an individual memory model, see figure \ref{fig:ch1:6}). 
 
 \begin{itemize}
  
 \item \textbf{Single instruction, single data (SISD) stream}: A single processor that executes a single instruction stream (i.e executing one data stream stored in an individual memory model, see figure \ref{fig:ch1:6}). 

-The conventional sequential computer, according to Von Neumann model, also called the Uniprocessors can de viewed as an example of this type.
+The conventional sequential computer, according to Von Neumann model \cite{ref50}, also called the Uniprocessors can be viewed as an example of this type of architecture.

 \begin{figure}[h!]
 \centering
 \includegraphics[scale=1]{fig/ch1/sisd.pdf}
 \begin{figure}[h!]
 \centering
 \includegraphics[scale=1]{fig/ch1/sisd.pdf}


@@ -146,7 +151,7 @@ The conventional sequential computer, according to Von Neumann model, also calle
 \end{figure}
  
 \item \textbf{Single instruction, multiple data (SIMD) stream}: All  processors execute the same instructions on different data. 
 \end{figure}
  
 \item \textbf{Single instruction, multiple data (SIMD) stream}: All  processors execute the same instructions on different data. 

-Each processor stores the data in its local memory. Then, it communicates with each others typically via a simple communication model, see figure \ref{fig:ch1:7}. Many scientific and engineering
+Each processor stores the data in its local memory. Then, they communicate with each others typically via a simple communication model, see figure \ref{fig:ch1:7}. Many scientific and engineering

 applications are referred to this type of parallel scheme.
 Vector and array processors are well known  examples of this type. 
 Examples about the applications executed over this architecture: (1) graphics processing, (2) video compression and (3) medical image analysis applications.
 applications are referred to this type of parallel scheme.
 Vector and array processors are well known  examples of this type. 
 Examples about the applications executed over this architecture: (1) graphics processing, (2) video compression and (3) medical image analysis applications.


@@ -170,8 +175,8 @@ Examples about the applications executed over this architecture: (1) graphics pr
 
 \item \textbf{Multiple instruction, Multiple data (MIMD) stream}: There are multiple processing elements, each one has a separate instruction  and  local data memories.
 At any time, different processing elements may be used to execute different instructions on  different data fragment, see figure \ref{fig:ch1:9}. There are two types of MIMD machines: the shared memory and the message passing MIMD machines. 
 
 \item \textbf{Multiple instruction, Multiple data (MIMD) stream}: There are multiple processing elements, each one has a separate instruction  and  local data memories.
 At any time, different processing elements may be used to execute different instructions on  different data fragment, see figure \ref{fig:ch1:9}. There are two types of MIMD machines: the shared memory and the message passing MIMD machines. 

-In the former, processors are communicated via a shared memory model, while in the latter, each processor has its own local memory and all processors communicate with each other via a communication network model. The  multi-core processors, local clusters and grid systems are  some examples for  MIMD machine.
-Many applications have been provided based on this architecture 
+In the former, processors  communicate via a shared memory model, while in the latter, each processor has its own local memory and all processors communicate with each others via a communication network model. The  multi-core processors, local clusters and grid systems are  some examples for  MIMD machine.
+Many applications have been developed based on this architecture 

 such as computer-aided design, computer-aided manufacturing, simulation, modeling, iterative applications and so on.
 
  \begin{figure}[h!]
 such as computer-aided design, computer-aided manufacturing, simulation, modeling, iterative applications and so on.
 
  \begin{figure}[h!]


@@ -190,8 +195,8 @@ how MIMD processors access the memory model. The shared MIMD machine communicati
 
 \begin{itemize}
 \item \textbf{Multi-core processors}:
 
 \begin{itemize}
 \item \textbf{Multi-core processors}:

-The multi-core processor is a single chip component with two or more processing units. These processing units are called cores, which are connected to each other via a main memory model as in the figure \ref{fig:ch1:10}. Each individual core has its cache memory to store its data to execute different data or instruction streams in parallel. Moreover, each core may have  one or more threads to execute a specific programming task as shown in the thread-level parallelism. Historically, the multi-cores of the CPU began as a two-core processors, with an increase in the number of cores approximately by double with each semiconductor process generation \cite{ref12}. The very quick improvements in the performance and  the increase in the number of cores  are devoted in the graphics processing unit (GPU). A current exemplar of the GPU  is the NVIDIA  GeForce TITAN Z with 5700 cores in the year of 2015 \cite{ref17}. While, in the same year the general-purpose microprocessor (CPU) has been appeared with less number of the cores, for example the TILE-MX processor from Tilera has 100 cores  \cite{ref16}.
-For more details about the multi-core processors see \cite{ref15}.
+The multi-core processor is a single chip component with two or more processing units. These processing units are called cores, which are connected to each other via a main memory model as in the figure \ref{fig:ch1:10}. Each individual core has its own cache memory to store  data. Moreover, each core may have  one or more threads to execute a specific programming task as shown in the thread-level parallelism. Historically, the multi-cores of the CPU began as two-core processors, then the number of cores  doubled with each semiconductor process generation \cite{ref12}. The graphic processing units (GPU) use extensively the multi-core architecture, 
+the NVIDIA  GeForce TITAN Z has 5700 cores in the year of 2015 \cite{ref17}. While, in the same year a general-purpose microprocessor (CPU) has a lot less cores, for example the TILE-MX processor from Tilera has 100 cores  \cite{ref16}. For more details about the multi-core processors see \cite{ref15}.

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


@@ -203,8 +208,8 @@ For more details about the multi-core processors see \cite{ref15}.
 
 \item \textbf{Local Cluster}:
  is a collection of independent  computers that are connected
 
 \item \textbf{Local Cluster}:
  is a collection of independent  computers that are connected

-to each other  via standard network switches and cables, which is a high speed  
-local area network (LAN) with low latency and big bandwidth. Moreover, each node is distributed from each other and communicates with other nodes  using distributed message passing model. All the nodes in the cluster must be controlled by one node called the master node, which is a specific node used to handle the scheduling and the management of the other nodes as shown in the figure \ref{fig:ch1:11}. Usually, the hardware specifications of all nodes are homogeneous in term of  computing power and memory. Thus, it is called tightly-coupled fashion. Also, each computing node in the cluster has the same copy of the operating system. See \cite{ref18, ref19} for more information about the cluster and its applications.
+to each other  via  a high speed  
+local area network (LAN) with low latency and big bandwidth. Moreover, each node communicates with other nodes  using messages. All the nodes in the cluster must be controlled by one node called the master node, which is a specific node used to handle the scheduling and the management of the other nodes as shown in the figure \ref{fig:ch1:11}. Usually, all the nodes are homogeneous, they have the same specifications in term of  computing power and memory.  Also, all the computing nodes in the cluster run the same  operating system. See \cite{ref18, ref19} for more information about the cluster and its applications.

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


@@ -215,8 +220,9 @@ local area network (LAN) with low latency and big bandwidth. Moreover, each node
 
 
 \item \textbf{Grid (Distributed clusters)}:
 
 
 \item \textbf{Grid (Distributed clusters)}:

-Grid is a collection of local computing clusters from different sites that are connected via a wide area network (WAN), which can be appeared virtually to the benefit of users  to form a complete computing system  \cite{ref20}. 
-In particular, different local clusters compose the grid are geographically located far away from each others. Usually, each local cluster is composed of homogeneous nodes, which are different from  nodes of the other clusters located in different sites. These nodes can be different in its hardware and software specifications (i.e its computing power, its memory size, its operating system and its local network latency and bandwidth. Figure \ref{fig:ch1:12} presents an example of a grid that is composed of three heterogeneous local clusters that are located in  different sites and  connected via a wide area network.  Furthermore, the grid can be referred to an infrastructure  that applies the integration and the collaboration by using  a collection  of different computers, networks, database servers  and scientific devices, which are belong to  many companies and universities. Therefore, wide heterogeneous computing resources are available to be used simultaneously by different user. Let's indicates that, the only bottleneck of the grid is the high latency communications between the nodes from different sites. The grid is also called the loosely-coupled fashion platform. However, the fault tolerance  is required to guarantee the process of sending and receiving  of messages between the computing nodes. Thus, it safely protects  all  messages against loss.
+Grid is a collection of  computing clusters from different sites that are connected via a wide area network (WAN). 
+In particular, different local clusters compose the grid are geographically located far away from each others. Usually, each  cluster is composed of homogeneous nodes, which are different from  nodes of the other clusters located in different sites. These nodes can be different in their hardware and software specifications (i.e their computing power, their memory size, their operating system and their network: latency and bandwidth). Figure \ref{fig:ch1:12} presents an example of a grid that is composed of three heterogeneous clusters that are located in  different sites and  connected via a wide area network.  Furthermore, the grid can  refer to an infrastructure  that applies the integration and the collaboration by using  a collection  of different computers, networks, database servers  and scientific devices, which  belong to  many companies and universities. Therefore, wide heterogeneous computing resources are available to be used simultaneously by different users. Note that, the main bottleneck of the grid is the high latency communications between the nodes from different sites. 
+See \cite{ref20} for more information about the grid and its applications.

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


@@ -225,38 +231,16 @@ In particular, different local clusters compose the grid are geographically loca
 \label{fig:ch1:12}
 \end{figure}
 
 \label{fig:ch1:12}
 \end{figure}
 

-
-\begin{figure}[h!]
-\centering
-\includegraphics[scale=1]{fig/ch1/grid5000.pdf}
-\caption{Grid5000's sites distribution in France and Luxembourg}
-\label{fig:ch1:13}
-\end{figure}

 \end{itemize}
 
 
 \end{itemize}
 
 

-Grid'5000 \cite{ref21} can be considered as a good example of this distributed platform. 
-It is a large-scale testbed that consists of ten sites distributed
-all over metropolitan France and Luxembourg. These sites are: Grenoble, Lille, Luxembourg, Lyon, Nancy, Reims, Rennes , Sophia, Toulouse, Bordeaux. Figure \ref{fig:ch1:13} shows the geographical distribution of grid'5000 sites over France and Luxembourg. All the sites are connected together via a  special long distance network called RENATER, which is abbreviation of the French
-National Telecommunication Network for Technology. Each site in the grid is
-composed of a few heterogeneous computing clusters and each cluster contains
-many homogeneous nodes. In total, Grid'5000 has about one thousand heterogeneous nodes and eight thousand cores. In each site, the clusters and their nodes
-are connected via high speed local area networks. Two types of local networks
-are used, Ethernet or Infiniband networks, which have different characteristics
-in terms of bandwidth and latency.
-Grid'5000 is dedicated as a test-bed for grid computing and thus users can book the required nodes from different sites. 
-It also gives the opportunity to the users to deploy their configured image of the operating system over the reserved nodes.
-Indeed, many software tools are available for  users in order to control and manage the reservation and deployment processes from their local machines. For example, OAR \cite{ref22} is a  batch scheduler that is used to manage the heterogeneous resources of the grid'5000.
-
-

 \subsection{Parallel programming Models} 
 \label{ch1:2:2}
 \subsection{Parallel programming Models} 
 \label{ch1:2:2}

-There are many parallel programming languages and libraries that have been developed 
+Many parallel programming languages and libraries  have been developed 

 to explore the computing power of the parallel architectures. In this section,
 two types of parallel programming languages are investigated: (1) shared and (2) distributed programming models. Moreover, each  type is divided  into two subcategories according to their supporting level for the number of computing units from which  the parallel platform is composed.
 Figure \ref{fig:ch1:14} presents this classification hierarchy of the parallel programming 
 to explore the computing power of the parallel architectures. In this section,
 two types of parallel programming languages are investigated: (1) shared and (2) distributed programming models. Moreover, each  type is divided  into two subcategories according to their supporting level for the number of computing units from which  the parallel platform is composed.
 Figure \ref{fig:ch1:14} presents this classification hierarchy of the parallel programming 

-models. Three parallel language examples for each subcategory are shown.
-
+models. 

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


@@ -273,77 +257,26 @@ some examples for each type of the parallel programming models are discussed:
 \begin{itemize}
 \item \textbf{Local cluster programming models}
   \begin{itemize}
 \begin{itemize}
 \item \textbf{Local cluster programming models}
   \begin{itemize}

-    \item \textbf{MPI} \cite{ref23} is the Message Passing Interface and it id considered as a 
+    \item \textbf{MPI} \cite{ref23} is the Message Passing Interface and it is considered as a 

                       standardization 
                       dedicated to message passing in a distributed memory environment.
                       The first version of MPI was designed by a group of researchers in
                       standardization 
                       dedicated to message passing in a distributed memory environment.
                       The first version of MPI was designed by a group of researchers in

-                      1991. It consist of a library,  not a language and its subroutines 
-                      can be called from many programming languages such as C, Fortran and 
-                      Java. Programmes that write in these languages and 
-                      compile their codes with ordinary compilers are directly  linked to MPI library.  
-                      library functions are not only limited to  peer to peer operations for 
-                      sending and receiving messages, also it is related to many others collective 
-                      operations such as gathering and reduction operations. MPI user, feels
-                      free from the network topology, synchronization and communication
-                      functionality between a group of processes. Furthermore, it has an
-                      asynchronous point to point operations, which make the computations 
-                      to overlap with communications. While MPI is not devoted to grid,
-                       \textbf{MPICH}  is one of the most 
-                      popular implementations of MPI dedicated for grid computing. It has been used
-                      as an extended version of MPI, which has been implemented for fault tolerance  
-                      \cite{ref52}. In this work, both  MPI and MPICH programming libraries 
-                      are used in programming of our algorithms and applications which are included
-                      inside both Fortran and C programming languages.  
-                      
-   \item \textbf{PVM} \cite{ref25} is included Parallel Virtual Machine,  composed of a collection 
-                      of software tools and libraries that allow users to work over a   
-                      heterogeneous set of machines to perform a single high performance 
-                      parallel platform. It is dedicated to a group of machines that are 
-                      distributed  heterogeneously the operating system environments. 
-                      The PVM system is elementary for parallel programming to be used with 
-                       C, C++, and Fortran  languages. 
-                      It supports more robustness in term of fault tolerance tan MPI. 
-                      Also, it is not complicated in term of adding or deleting the crashed
-                      nodes in the host pool  \cite{ref26}.
-                      On the other side, MPI supports more more communication messages and asynchronous 
-                      operations which are not allowed in PVM. 
-                       
+                      1991. It  is a specification and have been implemented in many programming 
+                      languages such as C, Fortran and 
+                      Java.   
+                      The MPI functions are not only limited to  point to point operations for 
+                      sending and receiving messages, there are many others collective 
+                      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.  

                       
                       

-                      
-   \item \textbf{BLACS} \cite{ref27} is for Basic Linear Algebra Communication Subprograms.                 
-                 It consist of  a collection of libraries that are used to build a linear algebra message 
-                 communication model. Thus, it is effectively applied  over distributed memory architectures.
-                 The primary goal of using BLACS is mapping a linear set or processors or any distributed 
-                 machines into two dimensional arrays or grid. Indeed, it offers an easy tool to build the
-                 linear algebra based applications. 

                  
   \end{itemize} 
   
                  
   \end{itemize} 
   

-\item \textbf{Grid programming models}
-  \begin{itemize}
-   \item \textbf{Gridsolve} \cite{ref28}  is the first middleware for  grid  and the
-                high performance computing. It  supports  a good tool to solve complex
-                scientific applications using distinct distributed machines. Also, it satisfies the
-                fault tolerance and achieves the load balancing features to ensure the reliability of the
-                applications  when running over a geographically distributed resources. 
-                It can be integrated with different programming languages such as C, C++, Java and Fortran. 
-                
-   \item \textbf{GLOBAS} \cite{ref29,ref30} is the most widely standardization toolkit
-                for grid computing. It permits the users to share their computing resources securely. 
-               Since, the GLOBAS toolkit has the opportunity to work with grid, then it offers a fault 
-                detection mechanism to ensure the delivery of  messages. 
-                The first version of Globus toolkit has been appeared
-                in 1998. Recently, the sixth version of this toolkit is available now \cite{ref31}. 
-                       
-
-  \item \textbf{Legion} \cite{ref32,ref33} is an object-based, meta-systems software project,
-                invented by the University of Virginia on November 1997. 
-                It ensures many features such as security, portability and fault tolerance.
-                Moreover, it has been created to support a wide degree of parallelism under the use of  
-                an easy programming tool to build  parallel applications.
-              
-        
-  \end{itemize}
+

  
 \item \textbf{Multi-core CPU programming models} 
   \begin{itemize}
  
 \item \textbf{Multi-core CPU programming models} 
   \begin{itemize}


@@ -353,77 +286,45 @@ some examples for each type of the parallel programming models are discussed:
                 shared memory parallel programs. It can be used with many  programming languages such 
                 as C, C++ and Fortran in order to support different types of shared memory platforms 
                 such as multi-core processors.
                 shared memory parallel programs. It can be used with many  programming languages such 
                 as C, C++ and Fortran in order to support different types of shared memory platforms 
                 such as multi-core processors.

-                OpenMP uses multi-threading, which is a method of parallel programming 
+                OpenMP uses multi-threading, which is a model in parallel programming 

                 that uses a master thread to control a set of slave threads. Each
                 that uses a master thread to control a set of slave threads. Each

-                thread can be executed in parallel by allocating it to one processor.  
+                thread can be executed in parallel by assigning it to a processor.  

                 Moreover, OpenMP can be  used with MPI to support hybrid platforms which have 
                 shared and distributed memory models at the same time.
                 
                 Moreover, OpenMP can be  used with MPI to support hybrid platforms which have 
                 shared and distributed memory models at the same time.
                 

-  \item \textbf{Cilk} \cite{ref13,ref35} is a linguistic and runtime technology for algorithmic 
-                multi-threaded programming originally developed by MIT. 
-                It allows the programmer to focus on building the program in a structured way 
-                in order to discover the inherent parallelism. Many specifications are used in Cilk 
-                such as  load balancing, synchronization and communication protocols. 
-                
-                
-                
-            
-                
-   \item \textbf{TBB} \cite{ref36} Abbreviation of Threading Building Blocks. It is a software library 
-                used with 
-                C++ programming language for multi-core parallel programming that has been developed by Intel.
-                It works on the principle of dividing the computations into many tasks and
-                executing them in parallel. 
-                Also, It  has a management library to schedule the parallel task execution. 
-                The only difference between OpenMP and TBB, is that TBB uses a task-based scheduling 
-                mechanism. For that reason, TBB is more popular with C++ programming language than 
-                other languages. Additionally, it has the ability to work with any compiler environments.
-                Hence, it can be easily supported by any new platform. Therefore, TBB has been supported by 
-                different types of operating systems and processors. 
-                Noting that, it is still has some limitations to support vector processing architecture. 
-                For this reason, it is connected with with OpenMP and Cilk to overcome this limitations.
-               
-  \end{itemize}
-  

   
   

+    \end{itemize}
+

   
 \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  consisted of many-cores processor that have 
-                       thousands of cores. According to this massively core parallelism, in 2007 the NVIDIA 
-                       has  developed CUDA as parallel programming  language, which is Compute Unified Device  
-                       Architecture.  A CUDA program has two parts: hosts and kernels.  The host  is a
-                       set of threads that are sequentially executed  over the CPU. 
-                       While, the kernel is a set of threads that can be executed in parallel over the GPUs.
+                       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 
+                       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 
  
    \item \textbf{OpenCL}\cite{ref38} is for Open Computing Language. It is a parallel 

-                       programming language dedicated for heterogeneous platform 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, 
-                       which can be portable execute on any computing hardware such as CPU or GPU cores. 
-                       This parallel programming language supports the homogeneous shared memory 
-                       platforms and the multi-core processors by using one core for control 
-                       and the others for computing.
+                       programming language dedicated for heterogeneous platforms composed 
+                       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. 
+                     

                          
                          

-   \item \textbf{HLSL} \cite{ref39} is named as the  High Level Shading Language and defined as the shader 
-                       programming language for Direct3D, which is a part of
-                       Microsoft’s DirectX API. It supports the shader design with 
-                       C language syntax, types, expressions, statements, and functions and it 
-                       provides a graphical pipeline parallelism.
-                       The last version of HLSL is the version 5.0 of DirectX 11, which has added a new 
-                       general-purpose GPU functions like CUDA. Recently, the new OpenCL 
-                       version has started to replace CUDA as a multi-platform GPU language.

                                    
   \end{itemize}
                                    
   \end{itemize}

+  

  
 \end{itemize}
 
 
 \section{Iterative Methods} 
 \label{ch1:3}
  
 \end{itemize}
 
 
 \section{Iterative Methods} 
 \label{ch1:3}

-Numerical methods are defined as a scientific computation methods to solve linear and non-linear problems.
-Most of the numerical problems can be represented by a mathematical equation form with relations between its components. For example, solving linear equations which are well known in the scientific  area 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}


@@ -431,16 +332,14 @@ Most of the numerical problems can be represented by a mathematical equation for
 \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 method 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, the iterative methods are faster than direct methods and can be 
-effectively applied in parallel. Moreover, iterative methods can be used to solve both  linear and non-linear equations.
-In our work, we are interested to paralleize the iterative methods because they are more popular and more efficient than  direct ones.
+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}


@@ -465,17 +364,18 @@ Where $F$ is one or set of operations applied to the data vector $X^k$ to produc
    
 \end{algorithm}
 
    
 \end{algorithm}
 

-The sequential iterative algorithm at each iteration computes the value of the relative error, which is called the residual and denoted as $R$. This error value is the maximum difference  between the  data components of the vectors of the last two successive iterations as follows:
+The sequential iterative algorithm at each iteration computes the value of the relative error, which is called the residual and denoted as $R$. This error value can be computed as the maximum difference  between the  data components of the vectors of the last two successive iterations as follows:

 
  \begin{equation}
   \label{eq:res}
    R = \max_{i=1, \dots, N}  \abs{X_i^{(k+1)} - X_i^k}
 \end{equation}  
 
  \begin{equation}
   \label{eq:res}
    R = \max_{i=1, \dots, N}  \abs{X_i^{(k+1)} - X_i^k}
 \end{equation}  

-Where $N$ is the size of the vector $X$. Then, the iterative sequential algorithm stops its iterations if the maximum error between the last two successive solution vectors, as in \ref{eq:res}, is less than or equal to  some threshold values. Otherwise, it replaces the new vector $X^{(k+1)}$ with the old vector $X^k$ and computes the new iteration.
+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}
 
 \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)$. 
+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)$. 

 Each sub-vector can be solved  independently on one computing unit as follows:
 
 \begin{equation}
 Each sub-vector can be solved  independently on one computing unit as follows:
 
 \begin{equation}


@@ -488,11 +388,11 @@ Where $X_i^k$ is the sub-vector executed over the $i^{th}$ computing unit at the
 \begin{algorithm}[h!]
 \begin{algorithmic}[1]
   
 \begin{algorithm}[h!]
 \begin{algorithmic}[1]
   

-  \State Initialize the sub-vectors $(X_1^0,\dots,X_M^0)$ randomly  
+  \State Initialize the sub-vectors $(X_1^0,\dots,X_M^0)$   

     \For {$k:=1$  step $1$ to \textit{convergence}}
     \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  
 
    


@@ -502,67 +402,54 @@ Where $X_i^k$ is the sub-vector executed over the $i^{th}$ computing unit at the
 \end{algorithm}
 
 
 \end{algorithm}
 
 

-The algorithm \ref{spia}, represents the synchronous parallel iterative algorithm. Similarly to 
-the sequential iterative algorithm \ref{spia}, this algorithm stops its iterations when the convergence condition  is satisfied and it computes the residual value $R$ as follows: 
+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.

 
 

-\begin{equation}
- \label{eq:res_syn}
-   R = \max_{i=1, \dots, M}  (\max_{j=1, \dots, m}\abs{X_{ij}^{(k+1)} - X_{ij}^k})
-\end{equation}
-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
-at each iteration the local residual and store it in the local variable at the computing unit $i$. 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, which represents the global maximum errors overall maximum local errors from $M$ computing units. Where $m$ is the size of the $i$  sub-vector.
-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 variables computed by the computing units.
+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.

 
 
 \begin{figure}[h!]
 \centering
 \includegraphics[scale=0.75]{fig/ch1/sisc.pdf}
 
 
 \begin{figure}[h!]
 \centering
 \includegraphics[scale=0.75]{fig/ch1/sisc.pdf}

-\caption{The SICS Model}
+\caption{The SISC Model}

 \label{fig:ch1:15}
 \end{figure}
 
 
 \label{fig:ch1:15}
 \end{figure}
 
 

-In the synchronous iterative algorithm, computing processors need to communicate with each others to 
-exchange data at each iteration. Algorithm \ref{spia} can used synchronous iterations and synchronous communications  denoted as \textbf{SISC} model.  At each iteration, the computing processor waits until 
-it  receives all the  computed data at the previous iteration from other processors to perform the next iteration. This type of communication model uses if there is a dependency between the parallel tasks. Figure \ref{fig:ch1:15}, shows that using SICS model in a heterogeneous platform may result in a big period  of the idle times represented by the white dashed spaces between two successive iterations. Indeed, this happens when the faster computing processor waits for the slower ones to finish their iterations to be able to synchronously send its data to them. 
-Using this operation, faster processors wast a big amount of their computing power and thus their energy consumption.
-The increase in the heterogeneity level between  computing powers of the computing processors may increase propositionally these idle times.
-Accordingly, this algorithm is effectively implemented over a local cluster, where a high speed local network is used to reduce these idle times.  
+In a synchronous parallel iterative algorithm, computing processors need to communicate with each others to 
+exchange data at each iteration if there is a dependency between the parallel tasks. Algorithm \ref{spia}  use synchronous iterations and synchronous communications  denoted as \textbf{SISC} model.  At each iteration, the computing processor waits until 
+it  receives all the  computed data at the previous iteration from other processors to perform the next iteration. Figure \ref{fig:ch1:15}, shows that using SISC model in a heterogeneous platform may result in  big periods  of the idle times represented by the white dashed spaces between two successive iterations. Indeed, this happens when the fast computing processors wait for the slower ones to finish their iterations to be able to synchronously send their data to them. 
+Using this operation, faster processors waste a big amount of their computing power and thus consume uselessly energy.
+The increase in the heterogeneity in the computing powers between the  processors may increase proportionally these idle times.
+Accordingly, this algorithm can be  effectively run over a local cluster, where a high speed local network is used to reduce these idle times.  

 
 
 \begin{figure}[h!]
 \centering
 \includegraphics[scale=0.75]{fig/ch1/siac.pdf}
 
 
 \begin{figure}[h!]
 \centering
 \includegraphics[scale=0.75]{fig/ch1/siac.pdf}

-\caption{The SIAS Model}
+\caption{The SIAC Model}

 \label{fig:ch1:16}
 \end{figure}
 
 \label{fig:ch1:16}
 \end{figure}
 

-Furthermore, the communications of the synchronous iterative algorithm can be implemented asynchronously. Therefore, this 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
 fast computing nodes must  wait for slow ones to send their 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
 fast computing nodes must  wait for slow ones to send their data messages. 

-SISC and SIAC algorithms are not tolerated to the loss of data messages. Consequently, if one node is crashed,  all the other computing nodes are blocked together and all the system is crashed.
+SISC and SIAC algorithms are not tolerant to the loss of data messages. Consequently, if one node crashes, all the other computing nodes are blocked.

 
 
  
 \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 depending on its own data received at a specific time. While all processors don't have  to wait 
-for data delivery from each other, there are not existence of the 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  others at the same time. 
-Hence, 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. 
-However, there are two mechanisms to update  data vectors in AIAC algorithm which are:
- \begin{itemize}
- \item  The local vectors can be updated randomly on the order of $M$ computing units.
-        Indeed,  some of these local vectors may be not able to update at a certain time. 
- \item  According to the time period $t$, each computing unit checks if one of its 
-        dependencies components has been updated. If the computing node detects any update, 
-        then it updates its own local vector data using the last received data messages.
-        Otherwise, nothing is occurred at the time $t$.
- \end{itemize}
+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. 

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


@@ -572,72 +459,64 @@ However, there are two mechanisms to update  data vectors in AIAC algorithm whic
 \label{fig:ch1:17}
 \end{figure}
 
 \label{fig:ch1:17}
 \end{figure}
 

-The global convergence of the parallel iterative method depends on the scientific application.
+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. 
 
 

-The implementation of the AIAC method is not easy, but it gives many advantages over the traditional synchronous iterative method. These features can be summarized as follows:
+The implementation of the AIAC method is not easy, but it gives many advantages over the traditional synchronous iterative method:

 
 \begin{itemize}
 
 \begin{itemize}

-\item It prevents the existence of the  idle times, since each processor doesn't have to wait 
-      for  others to receive the data messages. Then, there are no idle times between each two  
-      successive iterations.
+\item It prevents the existence of idle times, since each processor does not have to wait 
+      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 
       
 \item Less sensitive for the heterogeneous communications and nodes' computing powers. In heterogeneous 

-      platform, the faster nodes don't need to wait for the slow ones, so it 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 together. 
+      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. 

 
 

-\item The loss of the data messages is totally tolerant because each computing unit can not to be 
-      blocked by others. If the message is lost, the destination node doesn't have to wait  
+\item The loss of data messages is totally tolerant because each computing unit is not  
+      blocked waiting for the message. If the message is lost, the destination node does not have to wait  

       for this data message and it uses the last received data to perform its iteration  
       independently.
       
       for this data message and it uses the last received data to perform its iteration  
       independently.
       

-\item In the distributed grid architecture, the local clusters from different sites are 
-      connected via slow network with a high latency. On the other hand, the use of the AIAC model 
+\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 
       reduces the delay of sending the data message over such slow network link and thus the performance 

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

 \end{itemize}
 
 
 \end{itemize}
 
 

-In addition to the difficulty of applying the asynchronous iterative method, it has some 
+In addition to the difficulty of applying the asynchronous iterative model, it has some 

 disadvantages that can be summarized by these points:
 
 \begin{itemize}
 \item It is not compatible with all types of the iterative applications because some of these 
 disadvantages that can be summarized by these points:
 
 \begin{itemize}
 \item It is not compatible with all types of the iterative applications because some of these 

-      applications need to receive  data messages from its neighbours at each iteration.   
-      Therefore, they required a fix number of iterations to converge. Otherwise, the 
-      application performs  an infinity number of iterations which provides a system crash.
+      applications need to receive  data messages  at each iteration or they would not converge. 

  
  

-\item The application of an asynchronous iterative method requires more iterations compared 
-      to the synchronous ones to converge  when it is executed over the local cluster. 
-      The increase in the number of iterations may increase proportionally 
-      the execution time of the application. 
-      Especially, the local computing cluster uses a high speed network, then running the 
-      synchronous version over such platform is quicker to converge.
+\item An asynchronous iterative method requires more iterations compared 
+      to the synchronous one to converge. The increase in the number of iterations may increase proportionally 
+      the execution time of the application if it is being executed on a fast homogeneous cluster.

     
     

-\item While the process  doesn't receive the new data messages at each iteration, the mechanism of 
-       synchronous iterative methods for detecting the global convergence cannot be used for 
-      asynchronous ones. Therefore, in AIAC algorithm a process can perform many iterations    
+\item Since each node does not receive  new data messages at each iteration,  detecting the global convergence 
+      is harder than for the synchronous model. 
+      Therefore, in AIAC algorithm a process can perform many iterations    

       without receiving any data messages from its neighbours. The absence of receiving new 
       data messages makes the data component invariant at the computing units and thus it provides 
       without receiving any data messages from its neighbours. The absence of receiving new 
       data messages makes the data component invariant at the computing units and thus it provides 

-      a false local convergence. This means that the local residual value is less than the   
-      required threshold. This fake convergence is conflicted at the reception of the first data message 
-      because the local subsystem will locally diverge after computing the next iteration. 
+      a false local convergence.  At the reception of the first data message,
+       the local subsystem will  diverge after computing the next iteration. 

       Therefore, special mechanisms are required for detecting the global convergence of a parallel 
       iterative algorithm implemented according to the asynchronous iteration model.
 
 
 \end{itemize}
 
       Therefore, special mechanisms are required for detecting the global convergence of a parallel 
       iterative algorithm implemented according to the asynchronous iteration model.
 
 
 \end{itemize}
 

-Generally, the interested readers can find more details about both of synchronous and asynchronous 
-iterative methods in \cite{ref44,ref45}.

 
 

-In our works, we are interested to implement both synchronous and asynchronous 
-iterative methods to solve different problems over local homogeneous cluster, local heterogeneous cluster and distributed grid. Accordingly, the process of optimizing their energy consumptions and their performance is the main objective of this work as will be discussed in the next chapters. 
+In work of this thesis, we are interested in optimizing the energy consumption of parallel iterative 
+methods running over clusters or grids. 
+

 
 
 
 

-\section{The energy consumption model of the parallel applications } 
+\section{The energy consumption model of a parallel application} 

 \label{ch1:4}
 
 Many researchers~\cite{ref46,ref47,ref48,ref49} divide the power consumed by a processor into
 \label{ch1:4}
 
 Many researchers~\cite{ref46,ref47,ref48,ref49} divide the power consumed by a processor into


@@ -661,7 +540,7 @@ technology-dependent parameter.
 
 
 The dynamic voltage and frequency scaling technique (\textbf{DVFS}) is a process that is allowed in modern processors to reduce the dynamic
 
 
 The dynamic voltage and frequency scaling technique (\textbf{DVFS}) is a process that is allowed in modern processors to reduce the dynamic

-power by scaling down the voltage and frequency.  Its main objective is to
+power by scaling down the voltage and frequency of the CPU.  Its main objective is to

 reduce the overall energy consumption of the CPU~\cite{ref77}.  The operational frequency $F$
 depends linearly on the supply voltage $V$ as follows:
 \begin{equation} 
 reduce the overall energy consumption of the CPU~\cite{ref77}.  The operational frequency $F$
 depends linearly on the supply voltage $V$ as follows:
 \begin{equation} 


@@ -682,7 +561,7 @@ frequency of the CPU to any new frequency value~(\emph{P-state}) in the
 governor.  The CPU governor is an interface driver supplied by the operating
 system's kernel to lower a core's frequency \cite{ref8}.  
 
 governor.  The CPU governor is an interface driver supplied by the operating
 system's kernel to lower a core's frequency \cite{ref8}.  
 

-Depending on the equation \ref{eq:s}, the new frequency $F_{new}$ can be calculates as follows:
+Depending on the equation \ref{eq:s}, the new frequency $F_{new}$ can be calculated as follows:

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


@@ -708,7 +587,7 @@ Replacing $F_{new}$ in \ref{eq:pd-beta} as in \ref{eq:fnew} gives the following
    {} =\alpha \cdot C_L \cdot V^2 \cdot F_{max} \cdot S^{-3} = P_{dyn} \cdot S^{-3}
 \end{multline}
 
    {} =\alpha \cdot C_L \cdot V^2 \cdot F_{max} \cdot S^{-3} = P_{dyn} \cdot S^{-3}
 \end{multline}
 

-Where $P_{dynNew}$  and $P_{dyn}$ are the  dynamic power consumed with the
+Where $P_{dynNew}$  and $P_{dyn}$ are the  dynamic powers consumed with the

 new frequency and the maximum frequency respectively.
 
 According to (\ref{eq:pdnew}) the dynamic power is reduced by a factor of
 new frequency and the maximum frequency respectively.
 
 According to (\ref{eq:pdnew}) the dynamic power is reduced by a factor of


@@ -721,7 +600,7 @@ multiplying the power consumption, measured in watts, by the  execution time of
   Energy = Power \cdot T
 \end{equation}
 
   Energy = Power \cdot T
 \end{equation}
 

-According to the equation \ref{eq:E}, the dynamic energy consumption of the program executed in the time $T$ over one processor is the dynamic power multiply by the execution time. Moreover, the frequency scaling factor $S$ increases the execution time of the processor linearly, then the new dynamic energy consumption can be computed as follows:
+According to the equation \ref{eq:E}, the dynamic energy consumption of the program executed in the time $T$ over one processor is the dynamic power multiplied by the execution time. Moreover, the frequency scaling factor $S$ increases the execution time of the processor linearly, then the new dynamic energy consumption can be computed as follows:

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


@@ -729,14 +608,14 @@ According to the equation \ref{eq:E}, the dynamic energy consumption of the prog
 \end{equation}
 
 
 \end{equation}
 
 

-According to \cite{ref46,ref47}, the static power consumption $P_{static}$  does not changed when the frequency of the processors is scaled down. Therefore, the static energy consumption can be computed as follows:
+According to \cite{ref46,ref47}, the static power consumption $P_{static}$  does not changed when the frequency of the processor is scaled down. Therefore, the static energy consumption can be computed as follows:

 \begin{equation}
   \label{eq:Estatic}
    E_{static} = S \cdot  P_{static}  \cdot T
 \end{equation}
 
 
 \begin{equation}
   \label{eq:Estatic}
    E_{static} = S \cdot  P_{static}  \cdot T
 \end{equation}
 
 

-Therefore, the energy consumption of the individual task running over one processor 
+Therefore, the energy consumption of an individual task running over one processor 

 is the sum of both static and dynamic energies that  can be computed as follows:
 \begin{equation}
  \label{eq:Eind}
 is the sum of both static and dynamic energies that  can be computed as follows:
 \begin{equation}
  \label{eq:Eind}


@@ -744,8 +623,8 @@ is the sum of both static and dynamic energies that  can be computed as follows:
 \end{equation}
 
  
 \end{equation}
 
  

-Depending on \ref{eq:Eind}, the total energy consumption of $N$  parallel task  running on $N$ processors is the summation  of the individual energies consumed by all processors. This model is developed and used by  Rauber and Rünger~\cite{ref47}. They modeled 
-the total energy consumption for parallel tasks running on a homogeneous platform by sorting the execution time of the all parallel tasks in a descending order, then their model can be  written as a function of the scaling factor $S$, as in EQ~(\ref{eq:energy}).
+The total energy consumption of $N$  parallel task  running on $N$ processors is the summation  of the individual energies consumed by all processors. This model is developed and used by  Rauber and Rünger~\cite{ref47}. 
+The total energy consumed by the parallel tasks running on a homogeneous platform is computed by sorting the execution time of the all parallel tasks in a descending order, then using EQ~(\ref{eq:energy}).

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


@@ -761,30 +640,27 @@ the time of the slowest task, and $S_1$ its scaling factor which should be the
 highest because they are proportional to the time values $T_i$. 
 Finally, model \ref{eq:energy}  can be used to measure the energy consumed by any parallel application such as the iterative parallel applications with respect to the new scaled frequency value. 
 
 highest because they are proportional to the time values $T_i$. 
 Finally, model \ref{eq:energy}  can be used to measure the energy consumed by any parallel application such as the iterative parallel applications with respect to the new scaled frequency value. 
 

-There are two drawbacks of this energy model as follows:
+There are two drawbacks in this energy model as follows:

 \begin{itemize}
 \begin{itemize}

-\item The message passing iterative program consists of the communication and computation times.
-      This energy model is assumed that the dynamic power consumes during both these times.
-      While the processor during the communication times involved remain idle and only consumes the static 
+\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}. 
 
 
       power, for more details see \cite{ref53}. 
 
 

-\item It is not well adapted to a heterogeneous architectures when there are different 
-      types of the processors, which are consumed different dynamic and static powers. Then, this model is 
-      not able to measure the energy consumption of all the parallel systems  because it depends on 
-      one value for the static and dynamic powers.
+\item It is not well adapted to a heterogeneous architecture when there are different 
+      types of  processors, which  consume different dynamic and static powers. 

 \end{itemize}
 
 Therefore, one of the more important goals of this work is to develop a new energy models that 
 \end{itemize}
 
 Therefore, one of the more important goals of this work is to develop a new energy models that 

-must be taken into consideration the communication times in addition to the  computation times in order to modelize and measure the energy consumptions of the parallel iterative methods. These models must be suitable to efficiently integrate with all parallel architectures such as the homogeneous and heterogeneous platforms, with its  local or distributed computing clusters.  
+ take into consideration the communication times in addition to the  computation times in order to modelize and measure the energy consumptions of the parallel iterative methods. These models must be suitable to  homogeneous or heterogeneous parallel architectures.  

 
 \section{Conclusion}
 \label{ch1:5}
 
 \section{Conclusion}
 \label{ch1:5}

-In this chapter, three sections have been presented to describe the parallel hardware architectures, parallel iterative applications and the energy consumption model used to measure the energies of these applications. 
-The different types of parallelism levels that can be implemented in  software and hardware techniques have been explained in the first section. Furthermore, different types of  parallel architectures have been discussed and classified according to the connection between the computation units and the memory model.  
-Both  shared and distributed platforms as well as its depending parallel programming models have been categorized.
-In the second section, the two types of parallel iterative methods: synchronous and asynchronous ones are investigated.
-The synchronous iterative methods are well implemented over local homogeneous cluster with a high speed network link, while the asynchronous iterative methods are more conventional to implement over 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 is explained. This model  cannot be used for all types of parallel architectures. Since, it assumes  to measure the dynamic power 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 the processors, that consume different dynamic and static powers at the same time.
-
-For these reasons, in the next chapters of this thesis a new energy consumption models are developed to effectively integrate in modeling and measuring the energy consumptions by parallel iterative methods running on both homogeneous and heterogeneous architectures.  Additionally, these energy models are used in a method to optimize  both  energy consumption and performance of the iterative message passing applications. 
\ No newline at end of file
+In this chapter, three sections have been presented to describe the parallel hardware architectures, the parallel iterative applications and the energy consumption model used to measure the energy consumption of these applications. 
+The different types of parallelism levels that can be implemented in  software and hardware techniques have been explained in the first section. Afterwards,  different types of  parallel architectures have been discussed and classified according to the connection between the computation units and the memory model.  
+Both  shared and distributed platforms as well as their depending parallel programming models have been categorized.
+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 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