%% %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+% 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
\section{Introduction}
\label{ch1:1}
-Almost of the software applications are traditionally programmed as a sequential programs according to the Von Neumann report in 1993 \cite{ref50}. The structure of the
-program code is understandable by the human brain as a series of instructions that execute one after the other. From many years until a short time, the users of the sequential applications are moving their thinking towards that these applications must run faster with each new generation of microprocessors. This idea is no longer valid nowadays, because the recent release of the microprocessors have many computing units embedded in one chip and these programs are only run over one computing unit sequentially.
-Consequently, the traditional applications not have improved their performance a lot over the new architectures, whereas the new applications run faster over them in a parallel. The parallel application is executed over all the available computing units at the same time to improve its performance. Furthermore, the concurrency revolution has been referred to the drastically improvement in the performance of the new applications side by side to the new parallel architectures \cite{ref51}. Therefore, parallel applications and parallel architectures are closely tied together. It is hard to think about any of a parallel applications without thinking of the parallel hardware that executing them.
-
-In this work, the iterative parallel applications, which is the most popular type of the parallel applications, are interested and running them over different parallel architectures to optimize their energy consumptions is the goal.
-As a result, this chapter is aimed to give a brief overview for a parallel hardware architectures, parallel iterative applications and the energy model from the other authors used to measure the energy consumption of these applications.
-The reminder of this chapter is organized as follows: section \ref{ch1:2} is devoted
-to parallel computing architectures for describing the types of the parallelism and the types of the parallel platforms. It is also gives some information about the parallel programming models. Section \ref{ch1:3} explains both the synchronous and asynchronous parallel iterative methods and comparing them. Section \ref{ch1:4}, presents the well accepted energy model from the state of the art that can be used to measure the energy consumption of the parallel iterative applications when changing the frequency of the processor. Finally, section \ref{ch1:5} summaries this chapter.
+
+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,
+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 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 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.
+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 type of computation that makes the computing process applied simultaneously is called parallel computing. It has main principle refer to the ability of dividing the large problem into smaller sub-problems that can be solved at the same time \cite{ref2}.
-Mainly, solving the sub-problems of the main problem in a parallel computing are carried out on multiple parallel processors.
-Indeed, the parallel processors architecture is a computer system composed from many processing elements connected via network model in addition to the software tools required to make the processing units work together \cite{ref1}.
-Consequently, parallel computing architecture consist of software and hardware resources.
-The hardware resources are the processing units and the memory model in addition to the network system connecting them. The software resources include the specific operating system, the programming language and the compiler, or the runtime libraries. Furthermore, parallel computing can have different levels of parallelism, which can perform in software or hardware. There are five types of parallelism 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}
-\item \textbf{Bit-level parallelism (BLP)}: The appearance of very-large-scale integration (VLSI) in 1970s has been
- considered the first approach towards the parallel computing. It is used to increase the number of bits in word size being processed by a processor see figure~\ref{fig:ch1:1}. Year after year, the number of bits is increased starting from 4-bit microprocessors reaching until 64 bit microprocessors . For example, the recent x86-64 architecture becomes the most familiar architecture nowadays. Therefore, the biggest word size is given more parallelism level and thus less instructions to be executed by the processor at the same time.
-
+\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
\label{fig:ch1:1}
\end{figure}
-\item \textbf{Data-level parallelism (DLP)}:Data parallelism is the process of distributing the data vector between different parallel processors and each one performs the same operation 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 from the area of scientific computing. Usually, data-parallel operations are only provided for arrays operations, see figure \ref{fig:ch1:2}. As an example about the applications of this type of parallelism are the vectors multiplication, image and signal processing.
+\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
\label{fig:ch1:2}
\end{figure}
-\item \textbf{Instruction-level parallelism (ILP)}: Generally, the sequential program composed of many instructions. These instructions can be executed in a parallel at the same time, if each of them is independent from the others. In particular, parallelism can be achieved in the instruction level using the pipeline. It means all the independent instructions of the program are overlapped the execution of each others. For example, if we have two instruction $I_1$ and $I_2$, they are independent if there is no control and data dependency between them.
- In pipeline stages, the execution of each instruction is divided into multiple steps that can be overlapped with each others by the pipeline hardware unit.
-Figure~\ref{fig:ch1:3} demonstrates four instructions each one has four steps denoted as fetch, decode, execute and write are implemented in a hardware units by pipeline.
+
+\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.
\begin{figure}[h!]
\centering
-\item \textbf{Thread-level parallelism (TLP)}: It is also known as a task-level parallelism.
-According to the Moore’s law \cite{ref9}, processor can have a number of transistors by a double
-each two years to increase the frequency of the processor and thus its performance. Beside that, cache and main memories sizes are must increased together.
-This leads to some limits come from two main reasons, the first one is when the cache size is drastically increased leading to a larger access time. The second is related to the big increase in the number of the transistors per CPU can be increased significantly the heat dissipation. As a result, the programmers sub divided their programs into multiple tasks which can be executed in parallel over distributed processors or shared multi-cores processors to improve the performance of the program, see figure~\ref{fig:ch1:4}. Each processor can have a multiple or individual thread dedicated for each task. A thread can be defined as a part of a parallel program which shares processor resources with other threads.
+\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 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
\label{fig:ch1:4}
\end{figure}
-Therefore, we can consider the execution time of a sequential program composed of
-$N$ tasks as the sum of the execution times of all tasks as follows:
+Therefore, the execution time of a sequential program that is composed of $N$ tasks, is the sum of the execution times of all tasks. Thus, it is expressed as follows:
\begin{equation}
\label{ch1:eq1}
Sequential~execution~time = \sum_{i=1}^{N} T_i
\end{equation}
-Whereas, if the tasks are executed synchronously over multiple processing units in a parallel, the execution time of the program is the execution time of the task that have the 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}
Parallel~execution~time = \max_{i=1,\dots,N} T_i
\end{equation}
-
\item \textbf{Loop-level parallelism (LLP)}:
-The numerical algorithms and many other algorithms are executed iteratively the same program portion, the computations, using different forms of the loop statements allowed in the programming languages. At each iteration, the program need to scan a large data structure such as an array structure to make the arithmetic calculations. Inside the loop structure, there are many instructions, which are independent or dependent. In a sequential loop execution the $i$ iteration must be executed after the completion of $(i-1)$ iteration.
-While, if each iteration is independent from the others, then all the iterations are distributed over many processors to be executed in a parallel,
-for example see figure\ref{fig:ch1:5}. Thus, this type of a 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
-\includegraphics[scale=0.8]{fig/ch1/loop-para.pdf}
+\includegraphics[scale=0.85]{fig/ch1/loop-para.pdf}
\caption{Loop-level parallelism}
\label{fig:ch1:5}
\end{figure}
{N_{processors}}
\end{equation}
-For more detail about the levels of parallelism see \cite{ref3,ref4,ref6,ref7}.
+For more details about the levels of parallelism see \cite{ref3,ref4,ref6,ref7}.
\end{itemize}
\subsection{Types of Parallel platforms}
\label{ch1:2:1}
-The main goal behind using a parallel computers is to solve bigger problem faster.
-A collection of processing elements composing them must to work together to perform the final solution of the main problem. However, many different architectures have been proposed
-and classified according to the parallelism in the instruction and data
-streams. In 1966, Michel Flynn has been proposed a simple model of categorizing all computers that still useful until know \cite{ref10}. His taxonomy considered the data and the operations performed on this data to produce four types of computer systems as follows:
+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 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 executes a single instruction stream executing one data stream stored in an individual memory model, see figure \ref{fig:ch1:6}. As an example of this type is the conventional sequential computer according to the Von Neumann model, it is also called the Uniprocessors.
+\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 \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}
\label{fig:ch1:6}
\end{figure}
-\item \textbf{Single instruction, multiple data (SIMD) stream}: All the processors execute the same instruction on different data.
-Each processor stores the data in its local memory, the processors communicates with each others typically via simple communication model, see figure \ref{fig:ch1:7}. Many scientific and engineering
-applications are suitable to this type of parallel scheme.
-Vector and array processor are a well know examples of this type.
-As an example about the applications executed over this architecture are the graphics processing, video compression and medical image analysis applications.
+\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, 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.
\begin{figure}[h!]
\centering
\label{fig:ch1:7}
\end{figure}
-\item \textbf{Multiple instruction, single data (MISD) stream}: Many operations from multiple processing elements are executed over the same data stream. Each processing element has its local memory to store the private multiple program instructions applied to unique global memory data stream as in figure \ref{fig:ch1:8}. While the MISD machine is not commonly used, there are interesting uses such as the systolic arrays and dataflow machines.
+\item \textbf{Multiple instruction, single data (MISD) stream}: Many operations from multiple processing elements are executed over the same data stream. Each processing element has its local memory to store the private program instructions. Then, these instructions are applied to unique global memory data stream as in figure \ref{fig:ch1:8}. While the MISD machine is not commonly used, there are some interesting uses such as the systolic arrays and dataflow machines.
\begin{figure}[h!]
\centering
\end{figure}
-\item \textbf{Multiple instruction, Multiple data (MIMD) stream}: There are multiple processing elements each of which has a separate instruction and data local memories.
-At any time, different processing elements may be executing different instructions on different data fragment, see figure \ref{fig:ch1:9}. There are two types of the MIMD machines: the share memory and massage passing MIMD machines.
-In the share memory architectures, a processors are communicating via a share memory model, while in the message passing architecture each processor has its own local memory and they communicate via communication network model. The multi-core processors, local
-clusters and grid systems are an examples for the MIMD machine model.
-Many of applications are conducted over this architecture
+\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 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!]
\end{itemize}
For more details about this architectural taxonomy see \cite{ref11,ref5,ref13,ref14}.
-The work of this thesis is dedicated to MIMD machines architecture. Therefore, we discuss in
+The work of this thesis is dedicated to MIMD machine's architecture. Therefore, we discuss in
this chapter some of the commonly used parallel architectures that belong to MIMD machines.
-As explained before, MIMD architectures can be classified into two types, the shared memory and the distributed message passing ones. Furthermore, these classifications are based on
-how MIMD processors access the memory model. The shared MIMD machines can be bus-based, extended or
-hierarchical type. Whereas, the distributed memory MIMD machines may have hypercube or mesh inter connected networks. In the following are some well known MIMD parallel computing platforms:
+As explained before, MIMD architectures can be classified into two types, the shared memory and the distributed message passing ones. Furthermore, these classifications are based on
+how MIMD processors access the memory model. The shared MIMD machine communication topology can be bus-based, extended or hierarchical type. Whereas, the distributed memory MIMD machine may have hypercube or mesh interconnected networks. In the following some well known MIMD parallel computing platforms are explained:
\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 connected with each other via main memory model as in the figure \ref{fig:ch1:10}. Each individual core has its cache memory to store its data and execute different data or instructions stream in a parallel. Moreover, each core can 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, with the number of cores approximately doubling with each semiconductor process generation \cite{ref12}. The very quick improvements in the performance and thus the increase in the number of cores is devoted in a graphical processing unit (GPU). A current exemplar of GPUs is the NVIDIA GeForce TITAN Z with 5700 cores in 2015 \cite{ref17}. While the performance improvement of general-purpose microprocessors (CPU) has slowed increase in term of the number of the cores, for example the TILE-MX processor from Tilera has 100 cores in the same year \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
\item \textbf{Local Cluster}:
- is generally collection of independent computers that are connected
-to each other via standard network switches and cables, which is a high speed
-local area networks (LAN) with low latency and big bandwidth. Moreover, each node is distributed from each other and it is communicated with other nodes using distributed massage passing model. All the nodes in the cluster must be controlled by one node called the master node, which is a specific node handling the scheduling and management of the other nodes as in the figure \ref{fig:ch1:11}. Usually, the hardware specifications of all nodes are homogeneous in term of the computing power and memory and it is also 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.
-
+ is a collection of independent computers that are connected
+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
\end{figure}
-
-
\item \textbf{Grid (Distributed clusters)}:
-
-Grid is a collection of local computing clusters from different sites connected by wide area network (WAN), which can be appeared virtually to the benefit users as a complete computing system \cite{ref20}.
-In particular, different local clusters composing the grid are geographically far away from each others. Usually, each local cluster composed from homogeneous nodes, which are different from the nodes of the others cluster located in different sites. These nodes can be different in a hardware and software specifications such as the computing power, memory, operating system, local network latency and bandwidth. Figure \ref{fig:ch1:12} presents an example of the grid composed from three heterogeneous local clusters located in a different sites which are connected throw wide area network. Furthermore, the grid can be referred to an infrastructure that apply the integration and the collaboration by using a collection of different computers, networks, databases servers , and scientific devices belong to many companies and universities. Therefore, wide heterogeneous computing resources are allowed to many users simultaneously. While 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 the messages between the computing nodes and thus all the messages are recovered from the lost.
+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
\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}
-Grid'5000 \cite{ref21} can be considered as a good example for 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 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 allows the user to deploy his configured image of the operating system over the reserved nodes. Therefore, many software tools are available to the user to control and manage the reservation and deployment processes from his local machine. For example, OAR \cite{ref22} is a batch scheduler used to manage the heterogeneous resources of the grid'5000.
-
-
-
\subsection{Parallel programming Models}
-\label{ch1:2:2}.
-There are many parallel programming languages and libraries have been developed
+\label{ch1:2:2}
+Many parallel programming languages and libraries have been developed
to explore the computing power of the parallel architectures. In this section,
-the parallel computing programming languages are divided into two main types,
-which is the shared and the distributed models. Moreover, these two types are sub-divided into two sub-categories according to the support level to the number of computing units composing them.
+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
-paradigm. It is also show three parallel languages examples for each sub-category.
-
+models.
\begin{figure}[h!]
\centering
Many programming interfaces and libraries have been developed to compile and run the
-parallel applications over the parallel architectures. In the following are
-some examples for each type of the parallel programming models:
+parallel applications over the parallel architectures. In the following,
+some examples for each type of the parallel programming models are discussed:
\begin{itemize}
\item \textbf{Local cluster programming models}
\begin{itemize}
- \item \textbf{MPI} \cite{ref23} is Message Passing Interface, is a standardization
- dedicated for message passing in distributed memory environment.
- The first version of MPI designated by a group of researchers in
- 1991. It is a library, not a language and its subroutines
- can be called from many programming languages such as C, Fortran and
- Java. The programmes that users write in these languages are
- compiled with ordinary compilers and linked with the MPI library.
- Its library functions are not only for peer to peer operations throw
- send and receive messages, but it allowed many others collective
- operations such as gathering and reduction operations. MPI user feel
- free form the network topology, synchronization, and communication
- functionality between group of processes. Furthermore, it has
- asynchronous point to point operations, which make the computations
- to overlap with communications. While MPI is not devoted to a grid,
- \textbf{MPICH} is one of the most
- popular implementations of MPI dedicated for grid computing. It is used
- as an extended version for MPI, which implements a fault tolerance
- \cite{ref52}. In this work, both of MPI and MPICH programming libraries
- are used for programming our algorithms and applications which called
- inside Fortran and C programming languages.
-
- \item \textbf{PVM} \cite{ref25} is for Parallel Virtual Machine, which is a collection
- of software tools and libraries to allows users working over a
- heterogeneous set of machines to operate as a single high performance
- parallel platform. It is dedicated for a group of machine that are
- distributed and heterogeneous in the operating system environments.
- The PVM system is elementarily for parallel programming to be used with
- C, C++, and Fortran languages.
- It is considered more robust in fault tolerance
- than MPI, easier to add or delete the crashed nodes in the host pool
- \cite{ref26}. While MPI has more communication messages support and asynchronous
- operations which are not allowed in PVM.
+ \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
+ 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 has a collection of libraries that used to built linear algebra messages communication
- model which is applied effectively over distributed memory architectures.
- The primary goal of using
- BLACS is mapping a liner set or processors or any distributed machines into
- a two dimensional array or grid, which is offer an easy tool for building a
- linear algebra applications.
\end{itemize}
-\item \textbf{Grid programming models}
- \begin{itemize}
- \item \textbf{Gridsolve} \cite{ref28} is the first middleware for grid and
- high performance computing that offers a good tool to solve a complex
- scientific applications using distinct distributed machines. It applied the
- fault tolerance and load balancing features to ensure the reliability of the
- applications when running over a geographically distributed resources.
- It works with different programming languages such as C,C++, Java and Fortran.
-
- \item \textbf{GLOBAS} \cite{ref29,ref30} is the most widely standardization tool kit
- for grid computing. It permits the users to share their computing resources securely.
- While the GLOBAS toolkit is allowed to work with grid, it offers a fault
- detection mechanism to ensure the delivery of the messages.
- The first version of Globus toolkit appeared
- in 1998 and now the sixth version is available \cite{ref31}.
-
-
- \item \textbf{Legion} \cite{ref32,ref33} is an object-based and meta-systems software project
- at the University of Virginia on November 1997.
- It implements many features such as security, portability and fault tolerance.
- Moreover, it is created to support a wide degree of parallelism throw an easy
- programming tools to built the parallel applications.
-
-
- \end{itemize}
+
\item \textbf{Multi-core CPU programming models}
\begin{itemize}
- \item \textbf{OpenMP} \cite{ref34} is parallel programming tool for shared memory
+ \item \textbf{OpenMP} \cite{ref34} is a parallel programming tool dedicated to shared memory
architectures. The main goal of using this programming model is to provide
- a standard and portable API (application programming interface) for writing
- shared memory parallel programs. It can be used with programming languages such
- as C, C++ and Fortran to support different types of shared memory platforms
+ a standard and portable API (application programming interface) to write
+ 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 implements multi-threading, which is a method of parallel programming
- that organized by using master thread to control a set of slave threads. Each
- thread can be executed in parallel by allocating it to a processor.
- Moreover, OpenMP can be used with MPI to support hybrid platforms that have
- shared and distributed memory models in the same time.
-
- \item \textbf{Cilk} \cite{ref13,ref35} is a linguistic and runtime technology for algorithmic
- multi-threaded programming originally developed at MIT.
- It is allowed the programmer to focus on building the program in a structural way
- to discover the inherent parallelism. Many specification are used in Cilk
- such as the load balancing, synchronization, and communication protocols.
-
+ OpenMP uses multi-threading, which is a model in parallel programming
+ that uses a master thread to control a set of slave threads. Each
+ 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.
-
-
-
- \item \textbf{TBB} \cite{ref36} is for Threading Building Blocks, is a software library used with
- C++ programming language for multi-core parallel programming developed by Intel.
- It woks on the principle of dividing the computation into many tasks that can be executed in
- parallel. It also has a management library to schedule the parallel task execution.
- The difference between OpenMP and TBB, is the latter uses a task-based scheduling
- mechanism. Furthermore, TBB is more popular with C++ programming language than
- others languages. It is designed to work with any compiler environments, and thus
- be easily ported to new platform. Consequently, TBB has been ported to a
- different types of operating systems and processors. While, it has limited
- support to vector processing and then it connected with OpenMP
- and Cilk to support this platform.
- \end{itemize}
-
+ \end{itemize}
+
\item \textbf{GPU programming models}
\begin{itemize}
- \item \textbf{CUDA} \cite{ref37} Modern graphics processing units (GPUs) have been increasing chip-level parallelism. Current NVIDIA GPUs are many-core processor chips having thousands of core. According to this massively cores parallelism, the NVIDIA in 2007 developed a parallel programming language called CUDA , which is for Compute Unified Device Architecture.
- A CUDA program has two parts, the first one is called a host which is a set of threads that executed sequentially over the CPU. The second part is called the kernels, which are a set of a threads that can be executed in a parallel over the GPU.
+ \item \textbf{CUDA} \cite{ref37} Modern graphical processing units (GPUs) have increased its chip-level
+ 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
- programming language dedicated for heterogeneous platform composed
- of CPUs and GPUs. The first release is initially developed by Apple Inc
- in 2008. Functions executed on an OpenCL device is called kernel,
- which can be portably executes on any computing hardware such as CPU or GPU cores.
- This parallel programming language can support the homogeneous shared memory
- platforms, 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 for High Level Shading Language, is the shader
- programming language for Direct3D, which is a part of
- Microsoft’s DirectX API. It supports the shader construction with
- C-like syntax, types, expressions, statements, and functions. It
- provides a graphics pipeline parallelism.
- The last version of HLSL is v5.0 for DirectX 11, which adds a new GPGPU
- functions like CUDA. Recently, the new OpenCL version starts to replace CUDA
- as a multi-platform GPU language.
\end{itemize}
+
\end{itemize}
\section{Iterative Methods}
\label{ch1:3}
-Numerical methods are a scientific computations for solving linear and non-linear problems.
-Almost of the numerical problems can be represented by mathematical equation form with relations between its components. For example, solving linear equations which is 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}
\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 for solving this linear system.
-The first method is called \textbf{Direct methods}, which is 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 this methods are expensive or their
-solutions are impossible in some cases. The second type is called \textbf{Iterative methods}, which is computed
-many times the same block of the operations starting from the initial vector until reaching to the acceptable
-approximation of the exact solution. However, the iterative methods are faster than direct methods and can be
-applied in parallel. Moreover, iterative methods can be used to solve both of the linear and non-linear equations.
-In our work, we are interested in parallelizing the iterative methods because they are more popular and effective 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}
X^{(k+1)} \longleftarrow F(X^k)
\end{equation}
-Where $F$ is the one or set of operations applied to the data vector $X^k$ to produce the new data vector $X^{(k+1)}$. This operation $F$ is applied sequentially many times until convergence condition is satisfy, see algorithm \ref{sia}.
+Where $F$ is one or set of operations applied to the data vector $X^k$ to produce the new data vector $X^{(k+1)}$. The operation $F$ is applied sequentially many times until satisfying the convergence condition as in the algorithm \ref{sia}.
\end{algorithm}
-The sequential iterative algorithm at each iteration computes the value of the retaliative error, which is called the residual that denoted as $R$. This error value is the maximum difference between the data components of 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}
-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 solutions vectors, as in \ref{eq:res}, is less than or equal to the some threshold value. 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}
-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 one computing units as follows:
+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}
\label{eq:subvector}
\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 {$i:=1$ to \textit{M}}
+ \ParFor {$i:=1$ to \textit{M}}
\State $X^{(k+1)} = F(X^k)$
- \EndFor
+ \EndParFor
\EndFor
\end{algorithm}
+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.
-
-
-The algorithm \ref{spia}, represents the synchronous parallel iterative algorithm. In contrast to
-sequential iterative algorithm, algorithm \ref{spia}, stops its iterations when the convergence condition is satisfied. It computes the residual value $R$ as follows:
-
-\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 need 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 the
-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 reduce to one maximum value represented by the global residual, which is represent 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}
-\caption{The SICS Model}
+\caption{The SISC Model}
\label{fig:ch1:15}
\end{figure}
-In synchronous iterative algorithm, computing processors needs to communicate with each other to
-exchange data at each iteration. Algorithm \ref{spia} can be used synchronous iteration and synchronous communications (\textbf{SISC}) model. At each iteration the computing processor waits until
-it has receive all the data computed at the previous iteration from the other processors to perform the next iteration. This type of communication model used if there are a dependencies between the parallel tasks. Figure \ref{fig:ch1:15}, shows that using SICS model in a heterogeneous platform may results in a big periods of the idle times represented by the white dashed spaces
-between two successive iterations. Indeed, this happen when the fast computing processors waits for the slow ones to finish their iterations to be able to synchronously send its data to them. This operation is wasted a big amount of the computing power of the faster processors and thus its energy consumption. The increased in the level of the heterogeneity between the computing power of the computing processors may increased propositionally this idle times.
-For this reason, this algorithm is effectively implemented over a local cluster where a high speed local network exist 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}
-\caption{The SIAS Model}
+\caption{The SIAC Model}
\label{fig:ch1:16}
\end{figure}
-Furthermore, the communications of the synchronous iterative algorithm can be implemented asynchronously. Therefore, this algorithm is called the synchronous iteration and asynchronous
-communication algorithm (\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 not have to wait for its neighbours to receive the data messages
-that its has sent while it only waits for receiving the data from them. This can be implemented in SISC algorithm by replacing the synchronous send of the messages by asynchronous one and keeps
-the a synchronous receive of the data messages. The only advantage of this technique is to reduce the idle time between the iterations by making the communications to overlap partially
+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 have to wait for slow ones to send their data messages.
-Both of the SISC and SIAC algorithms are not tolerates to the loss of data messages. Consequently, if one node is crashed makes all the other computing nodes are blocked together and all the system is crashed.
+fast computing nodes must wait for slow ones to send their data messages.
+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}
-The asynchronous iterations mean that all processors perform their iterations without considering the works of the other processors. Each processor not has to wait for receiving
-the data messages from the others processors and continue computing the next iteration depending on its own data received at a specific time. While all processors not have to wait
-for data delivery from each other, there are not existence for the idle times at all between the iterations, see figure \ref{fig:ch1:17}. As shown in this figure, the fast processors can perform more iterations than the others at the same time.
-The asynchronous iterative algorithm uses asynchronous communications and called the \textbf{AIAC} algorithm. As same as in SISC algorithm, the AIAC algorithm subdivides the global Vectors $X$ into $M$ sub-vectors between the computing units. The main different between the two algorithm is that these $M$ sub-vectors are not updated at each iteration in the AIAC algorithm because both of the iterations and communications are asynchronous.
-However, there are two mechanisms to update the data vectors in AIAC algorithm:
- \begin{itemize}
- \item The local vectors can be updated randomly on the order of $M$ computing units.
- This is leads to some of these local vectors to not update at a certain time.
- \item According to the time period $t$, each computing unit checks if one of the its
- dependencies components have been updated. If the computing node detects any update
- case, it updates its own local vector data using the last received data messages.
- Otherwise, it does nothing 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!]
\label{fig:ch1:17}
\end{figure}
-The global convergence of the parallel iterative method depend on the scientific application
-and is ensured if the certain conditions are satisfied with respect to the data of the problem.
-For more information about the convergence detection techniques of the asynchronous iterative methods,
-we refer to \cite{ref40,ref41,ref42,ref43} for more details.
+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.
The implementation of the AIAC method is not easy, but it gives many advantages over the traditional synchronous iterative method:
\begin{itemize}
-\item It prevents the existence of the idle times because each processor not has to wait
- for the others to receive the data messages. Then, 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 a
- heterogeneous platform, the fast nodes not have to wait for the slow ones and so it
- performs more iterations than 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.
-
-\item The loss of the data messages is totally tolerant because each computing unit is not
- blocked with the others. If the message is lost, the destination node not has to wait
+\item Less sensitive for the heterogeneous communications and nodes' computing powers. In heterogeneous
+ 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 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.
-\item In the distributed grid architecture, the local clusters from different sites are
- connected via 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 improved.
+\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 affected.
\end{itemize}
-In addition to the difficulty of applying the asynchronous iterative method, it has some
-disadvantages as follows:
+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 to all types of the iterative applications because some of these
- applications need to receive data message from its neighbours at each iteration.
- Therefore, they required a fix number of iterations to converge. Otherwise, the
- application is perform infinity number of iterations and then all of the system
- is crash.
+\item It is not compatible with all types of the iterative applications because some of these
+ applications need to receive data messages at each iteration or they would not converge.
-\item The application of the asynchronous iterative methods required more iterations compared
- to the synchronous ones to converge to the problem solution when it is executed over
- the local cluster. The increase in the number of
- the iterations may increases proportionally the execution time of the application.
- Especially, the local computing cluster uses a high speed networks, then 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 not receive the new data messages at each iteration, the mechanism of
- the synchronous iterative methods for detecting the global convergence cannot be used for
- asynchronous ones. Therefore, in AIAC algorithm a process can performs 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 not vary at the computing units and thus it detect
- a false local convergence. This mean 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 diverges after computing the next iteration.
+ data messages makes the data component invariant at the computing units and thus it provides
+ 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}
-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 execute both of a synchronous and asynchronous
-iterative methods for solving different problems over local homogeneous cluster, local heterogeneous cluster and distributed grids and optimizing their energy consumptions and performance is the main goal of this work as in the coming 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
-two power metrics: the static and the dynamic power. While the first one is
+two power metrics: static power and dynamic power. The first one is
consumed as long as the computing unit is on, the latter is only consumed during
computation times. The dynamic power $P_{dyn}$ is related to the switching
activity $\alpha$, load capacitance $C_L$, the supply voltage $V$ and
\label{eq:ps}
P_\textit{static} = V \cdot N_{trans} \cdot K_{design} \cdot I_{leak}
\end{equation}
-where V is the supply voltage, $N_{trans}$ is the number of transistors,
+Where V is the supply voltage, $N_{trans}$ is the number of transistors,
$K_{design}$ is a design dependent parameter and $I_{leak}$ is a
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
-power by scaling down the voltage and frequency. Its main objective is to
-reduce the overall energy consumption~\cite{ref77}. The operational frequency $F$
+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}
\label{eq:v}
The value of the scaling factor $S$ is greater than 1 when changing the
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.
+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}
{} =\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
Energy = Power \cdot T
\end{equation}
-According to the equation \ref{eq:energy}, 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}
\end{equation}
-According to \cite{ref46,ref47}, the static power consumption $P_{static}$ is still without change when the frequency of the processors is scale 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}
-Therefore, the energy consumption of the individual task running over one processor can be computed as follows:
+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}
E_{ind} = E_{dynNew} + E_{static} = S^{-2} \cdot P_{dyn} \cdot T + S \cdot P_{static} \cdot T
\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 a 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}
\hfill
\end{equation}
-where $N$ is the number of parallel nodes, $T_i$ for $i=1,\dots,N$ are
+Where $N$ is the number of parallel tasks, $T_i$ for $i=1,\dots,N$ are
the execution times of the sorted tasks. Therefore, $T1$ is
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.
+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:
+There are two drawbacks in this energy model as follows:
\begin{itemize}
-\item The message passing iterative programs consist 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
- power, for more details we refer to \cite{ref53}.
+\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}.
-\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 measured the energy consumption of all the parallel system because it depends on
- one value of 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 an energy models that
-taking into account the communication times in addition to computation times to modelize and measure the energy consumptions of the parallel iterative methods. These models are dedicated to all parallel architectures such as the homogeneous and heterogeneous platforms, which are local or distributed computing clusters.
+Therefore, one of the most important goals of this work is to develop a new energy models that
+ 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}
-In this chapter, we are presented in general different types of parallelism levels that can be implemented in a software and hardware techniques. Furthermore, the types of the parallel architectures are demonstrated and classified according to how the computing units are connected to a memory model. Two parallel systems are classified to the shared and distributed platforms. Depending on these two types, we are categorized the parallel programming models. The parallel iterative methods are explained and its two types, the synchronous and asynchronous iterative methods, are described. 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.
-Consequently, running these two types of the parallel iterative methods over distributed platforms is interested in this work. The energy consumption model for measuring the energy consumption of the parallel applications from the literature is described. This model cannot be used for all types of parallel architectures. The energy model is assumed to measure the dynamic power during both communication and computation times, while the processor involved remains idle during the communications time and only consumes static power. Moreover, it is not well adapted to the heterogeneous architectures.
+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.
-However, in the coming chapters of this thesis a new energy consumption models are developed, use for modeling and measuring the energies consumed by a parallel iterative methods running on both homogeneous and heterogeneous architectures.
+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
