\section{Introduction}
\label{ch1:1}
-Traditionally, most of the software applications are structured as 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 executed one after the other. From many years until a short time,
+Traditionally, most of the software applications are structured as 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 executed one after the other. For many years until a short time,
with each new generation of microprocessors the users of the sequential applications have believed that these applications run faster over them.
-Nowadays, this idea is no longer valid 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, traditional applications have not 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 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 new applications side by side to new parallel architectures \cite{ref51}. Therefore, parallel applications and parallel architectures are closely tied together. It is hard to think about any of parallel applications without thinking of the parallel hardware executed them.
-For example, the energy consumption of the parallel system mainly depends on both of the parallel application and the parallel architecture executes this application. Indeed, an energy consumption model or any measurement system depends on many specifications, some of them are concerning parallel hardware features such as the frequency of the processor, the power consumption of the processor and the communication model. The others are concerning the parallel application such as the computation and communication times of the application.
+Nowadays, this idea is no longer valid because the recent releases of the microprocessors have many computing units embedded in one chip and these programs are only run over one computing unit sequentially.
+Consequently, traditional applications have not 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 available computing units at the same time to improve its performance. 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. It is hard to think about any of parallel applications without thinking of the parallel hardware executed them.
+For example, the energy consumption of a parallel system mainly depends on both of the parallel applications and the parallel architectures execute these applications. Indeed, an energy consumption model or any measurement system depends on many specifications, some of them are concerning parallel hardware features such as the frequency of the processor, the power consumption of the processor and the communication model. The others are concerned the parallel application such as the computation and communication times of the application.
In this work, the iterative parallel applications are interested and running them over different parallel architectures to optimize their energy consumptions is the main goal.
As a result, this chapter is aimed to give a brief overview of parallel hardware architectures, parallel iterative applications and an energy model from the other authors used to measure the energy consumption of these applications.
\section{Parallel Computing Architectures}
\label{ch1:2}
The process of the simultaneous execution of calculations is called the parallel computing.
-Its 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}.
+Its main principle refers to the ability of dividing the large problem into smaller sub-problems that can be solved at the same time \cite{ref2}.
Mainly, solving 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 of many processing elements connected via network model in addition to software tools required to make the processing units work together \cite{ref1}.
-Consequently, the parallel computing architecture consist of a software and hardware resources.
+Indeed, the parallel processor architecture is a computer system composed of many processing elements connected via network model in addition to software tools required to make the processing units work together \cite{ref1}.
+Consequently, the parallel computing architecture consists of a software and hardware resources.
Hardware resources are processing units and the memory model in addition to the network system connecting them. Software resources include the specific operating system, the programming language and the compiler, or the runtime libraries. Furthermore, the parallel computing can have different levels of parallelism that can be performed in a software or a hardware level. There are five types of parallelism as follows:
\begin{itemize}
-\item \textbf{Bit-level parallelism (BLP)}: The appearance of the very-large-scale integration (VLSI) in 1970s has been considered the first step towards the parallel computing. It is used to increase the number of bits in the word size being processed by a processor as in the figure~\ref{fig:ch1:1}. For many successive years, the number of bits have 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 gives more parallelism level and thus less instructions to be executed by a processor at the same time.
+\item \textbf{Bit-level parallelism (BLP)}: The appearance of the very-large-scale integration (VLSI) in 1970s has been considered the first step towards the parallel computing. It is used to increase the number of bits in the word size being processed by a processor as in the figure~\ref{fig:ch1:1}. For many successive years, the number of bits have 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 gives more parallelism level and thus less instructions to be executed by a processor at the same time.
\begin{figure}[h!]
\centering
\label{fig:ch1:1}
\end{figure}
-\item \textbf{Data-level parallelism (DLP)}: Data parallelism is a process of distributing the data vector between different parallel processors and each one performs 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 from the area of scientific computing. Usually, data-parallel operations are only provided for arrays operations, for example see figure \ref{fig:ch1:2}. As an example about the applications use this type of parallelism are vectors multiplication, image and signal processing.
+\item \textbf{Data-level parallelism (DLP)}: Data parallelism is a process of distributing the data vector between different parallel processors and 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 from the area of scientific computing. Usually, data-parallel operations are only provided for arrays operations, for example, see figure \ref{fig:ch1:2}. As an example about the applications use this type of parallelism are vector multiplication, image and signal processing.
\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, the parallelism can be achieved in the instruction level by using pipeline. It means all the independent instructions of the 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 data dependency between them.
+\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, the parallelism can be achieved in the instruction level by using a pipeline. It means all the independent instructions of the 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 data dependency between them.
In pipeline stages, the execution of each instruction is divided into multiple steps that can be overlapped with the steps of other instructions 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, which are implemented in hardware units by pipeline.
\item \textbf{Thread-level parallelism (TLP)}: It is also known as a task-level parallelism.
According to the Moore’s law \cite{ref9}, the processor can have number of transistors by a double
-each two years to increase the frequency of the processor and thus its performance. Besides, cache and main memories sizes are must increased together to satisfy this increased.
-But, 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 that can be increased significantly the heat dissipation. As a result, programmers subdivided 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 has a multiple or an individual thread dedicated for each task. A thread can be defined as a part of the parallel program which shares processor resources with other threads.
+each two years to increase the frequency of the processor and thus its performance. Besides, cache and main memory sizes are must increased together to satisfy this increased.
+But, 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 that can be increased significantly the heat dissipation. As a result, programmers subdivided 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 an individual thread dedicated for each task. A thread can be defined as a part of the parallel program which 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 sum of the execution times of all tasks as follows:
+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:
\begin{equation}
\label{ch1:eq1}
\end{equation}
\item \textbf{Loop-level parallelism (LLP)}:
-The numerical algorithms and many other algorithms are executed iteratively the same program portion, computation, 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
+The numerical algorithms and many other algorithms are executed iteratively the same program portion, computation, 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 that are independent or dependent. 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 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}. In the parallel programming languages this type of a loop is called $parallel~loop$.
+Whereas, 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}. In the parallel programming languages this type of a loop is called $parallel~loop$.
\begin{figure}[h!]
\centering
\subsection{Types of Parallel platforms}
\label{ch1:2:1}
-The main goal behind using a parallel computers is to solve bigger problem faster.
+The main goal behind using a parallel computer is to solve the 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 these data to produce four types of computer systems as follows:
+streams. In 1966, Michel Flynn has been proposed a simple model of categorizing all computers that still useful until now \cite{ref10}. His taxonomy considered the data and the operations performed on these data to produce four types of computer systems as follows:
\begin{itemize}
\item \textbf{Single instruction, multiple data (SIMD) stream}: All the processors execute the same instructions on different data.
Each processor stores the data in its local memory, the processor communicates with each others typically via a 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 processors are well know examples of this type.
+Vector and array processors are well known examples of this type.
As an example about the applications executed over this architecture are graphics processing, video compression and medical image analysis applications.
\begin{figure}[h!]
\end{figure}
-\item \textbf{Multiple instruction, Multiple data (MIMD) stream}: There are multiple processing elements each of which has a separate instructions and local data 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 MIMD machines: the share memory and the massage passing MIMD machines.
-In the share memory architectures, a processors are communicated via a share memory model, while in the message passing architecture each processor has its own local memory and all processors communicate via a communication network model. The multi-core processors, local
+\item \textbf{Multiple instruction, Multiple data (MIMD) stream}: There are multiple processing elements, each of which has a separate instruction and local data memories.
+At any time, different processing elements may be executing different instructions on the 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 shared memory architectures, processors are communicated via a shared memory model, while in the message passing architecture each processor has its own local memory and all processors communicate via a communication network model. The multi-core processors, local
clusters and grid systems are an examples for MIMD machine.
Many applications have been conducted over this architecture
such as computer-aided design, computer-aided manufacturing, simulation, modeling, iterative applications and so on.
\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 communication topology 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:
+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 are some well known MIMD parallel computing platforms:
\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 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 increase in the number of cores approximately by double 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 the graphical processing unit (GPU). A current exemplar of GPU is the NVIDIA GeForce TITAN Z with 5700 cores in year of 2015 \cite{ref17}. While the general-purpose microprocessors (CPU) has less number of the cores, for example the TILE-MX processor from Tilera had 100 cores in the same year \cite{ref16}.
+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 instruction stream in 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 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 thus the increase in the number of cores is 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 the general-purpose microprocessor (CPU) has less 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}.
\begin{figure}[h!]
\item \textbf{Local Cluster}:
- is generally collection of independent computers that are connected
+ 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 networks (LAN) with low latency and big bandwidth. Moreover, each node is distributed from each other and it communicates 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 uses to handle the scheduling and 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 the computing power and memory and 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.
+local area network (LAN) with low latency and big bandwidth. Moreover, each node is distributed from each other and it 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 uses to handle the scheduling and 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 the computing power and memory and 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.
\begin{figure}[h!]
\centering
\item \textbf{Grid (Distributed clusters)}:
Grid is a collection of local computing clusters from different sites connected via 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 faraway 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 the hardware and software specifications such as the computing power, memory size, operating system, local network latency and bandwidth. Figure \ref{fig:ch1:12} presents an example of the grid composed of three heterogeneous local clusters located in different sites which are connected throw a wide area network. Furthermore, the grid can be referred to an infrastructure applies the integration and the collaboration by using 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 keeps all the messages from the lost.
+In particular, different local clusters composing the grid are geographically far away from each others. Usually, each local cluster composed of homogeneous nodes, which are different from the nodes of the others cluster located in different sites. These nodes can be different in the hardware and software specifications such as the computing power, memory size, operating system, local network latency and bandwidth. Figure \ref{fig:ch1:12} presents an example of the grid composed of three heterogeneous local clusters located in different sites which are connected throw a wide area network. Furthermore, the grid can be referred to an infrastructure applies the integration and the collaboration by using a collection of different computers, networks, database 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 keeps all the messages from loss.
\begin{figure}[h!]
\centering
the parallel programming languages are divided into two main types,
which is the shared and the distributed programming models. Moreover, each type is divided into two subcategories according to its support level for the number of computing units composing the parallel platform.
Figure \ref{fig:ch1:14} presents this classification hierarchy of the parallel programming
-models. It is also showed three parallel languages examples for each subcategory.
+models. It also shows three parallel language examples for each subcategory.
\begin{figure}[h!]
\begin{itemize}
\item \textbf{MPI} \cite{ref23} is the Message Passing Interface and it considers a
standardization
- dedicated for message passing in distributed memory environment.
+ dedicated for message passing in a 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
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 an
+ operations such as gathering and reduction operations. MPI user, feel
+ 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 a grid,
\textbf{MPICH} is one of the most
popular implementations of MPI dedicated for grid computing. It uses
- as an extended version for MPI, which implements a fault tolerance
+ as an extended version of MPI, which implements a fault tolerance
\cite{ref52}. In this work, both of MPI and MPICH programming libraries
have used for programming our algorithms and applications which called
inside both of 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 allow 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
+ parallel platform. It is dedicated to 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
+ The PVM system is elementary 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
+ \cite{ref26}. While MPI has, the more communication messages support and asynchronous
operations which are not allowed in PVM.
\item \textbf{BLACS} \cite{ref27} is for Basic Linear Algebra Communication Subprograms.
- It has a collection of libraries that used to built a linear algebra messages
+ It has a collection of libraries that used to build a linear algebra message
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 two dimensional array or grid, which offers an easy tool for building a
scientific applications using distinct distributed machines. It applies 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.
+ 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 a grid computing. It permits the users to share their computing resources securely.
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.
+ programming tool to build the parallel applications.
\end{itemize}
as C, C++ and Fortran to support different types of shared memory platforms
such as multi-core processors.
OpenMP uses multi-threading, which is a method of parallel programming
- that uses a master thread to control set of slave threads. Each
+ that uses a master thread to control a set of slave threads. Each
thread can be executed in a 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 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 computations into many tasks that can be
+ It works on the principle of dividing the computations into many tasks that can be
executed in a 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
+ other languages. It is designed to work with any compiler environments, and thus
it is easily ported to a new platform. Hence, TBB has been ported to
- different types of operating systems and processors. While, it has limited
+ different types of operating systems and processors. It has limited
support to vector processing architecture and then it is connected with OpenMP
and Cilk to support this platform.
\end{itemize}
\begin{itemize}
\item \textbf{CUDA} \cite{ref37} Modern graphical processing units (GPUs) have increased its chip-level
parallelism. Current NVIDIA GPUs are many-cores processor having thousands
- of core. According to this massively cores parallelism, the NVIDIA in 2007 developed
+ of cores. According to this massively core 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
\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 initially developed by Apple
- 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.
+ in 2008. Functions executed on an OpenCL device 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.
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 version 5.0 for DirectX 11, which adds a new
+ The last version of HLSL is version 5.0 of DirectX 11, which adds a new
general-purpose GPU functions like CUDA. Recently, the new OpenCL
- version starts to replace CUDA as a multi-platform GPU language.
+ version has started to replace CUDA as a multi-platform GPU language.
\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:
+Numerical methods are a scientific computation for solving linear and non-linear problems.
+Almost 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:
\begin{equation}
\label{eq:linear}
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
+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 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
\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 its iterations if the maximum error between the last two successive solution 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.
\subsection{Synchronous Parallel Iterative method}
\label{ch1:3:1}
\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
+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.
\end{figure}
-In synchronous iterative algorithm, computing processors needs to communicate with each others to
+In the synchronous iterative algorithm, computing processors need to communicate with each others to
exchange data at each iteration. Algorithm \ref{spia} can be used synchronous iterations and synchronous communications and denoted as \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 uses 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 happens when the fast computing processor waits for the slow ones to finish their iterations to be able to synchronously send its data to them. This operation wastes a big amount of the computing power of the faster processors and thus their energy consumptions. The increased in the level of the heterogeneity between the computing powers of the computing processors may increased propositionally these idle times.
+it has received all the data computed at the previous iteration from the 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 fast computing processor waits for the slow ones to finish their iterations to be able to synchronously send its data to them. This operation wastes a big amount of the computing power of the faster processors and thus their energy consumptions. The increase in the level of the heterogeneity between the 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.
Furthermore, the communications of the synchronous iterative algorithm can be implemented asynchronously. Therefore, this algorithm is called the synchronous iteration and asynchronous
communication algorithm 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 not has 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 programmed in MPI by replacing the synchronous send of the messages by asynchronous ones and keeps
+Moreover, each computing unit doesn't 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 with SISC algorithm programmed in MPI by replacing the synchronous send of the messages by asynchronous ones and keeps
the synchronous receive of the data messages. The only advantage of this technique is to reduce the idle times between the iterations by making 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 still have to wait for slow ones to send their data messages.
-Both of the SISC and SIAC algorithms are not tolerate 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.
+Both of the 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 crashing.
\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 as in figure \ref{fig:ch1:17}. This figure indicates that the fast processors can perform more iterations than the others at the same time.
-Hence, the asynchronous iterative algorithm uses asynchronous communications is called \textbf{AIAC} algorithm. Likewise the 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.
+The asynchronous iterations mean that all processors perform their iterations without considering the works of the other processors. Each processor doesn't have to wait for receiving
+the data messages from the other processors and continue computing 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 the fast processors can perform more iterations than the others at the same time.
+Hence, the asynchronous iterative algorithm uses an asynchronous communications is called \textbf{AIAC} algorithm. Likewise 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 of the iterations and communications are asynchronous.
However, there are two mechanisms to update the data vectors in AIAC algorithm as follows:
\begin{itemize}
\item The local vectors can be updated randomly on the order of $M$ computing units.
\label{fig:ch1:17}
\end{figure}
-The global convergence of the parallel iterative method depend on the scientific application.
+The global convergence of the parallel iterative method depends on the scientific application.
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 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, there is no idle times between each two
+\item It prevents the existence of the idle times because each processor doesn't have to wait
+ for the others to receive the data messages. Then, there are no idle times between each two
successive iterations.
-\item Less sensitive for the heterogeneous communications and nodes' computing powers. In
- 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 Less sensitive for the heterogeneous communications and nodes' computing powers. In heterogeneous
+ platform, the faster nodes don't 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
+ blocked by the others. If the message is lost, the destination node doesn't have to wait
for this data message and it uses the last received data to perform its iteration
independently.
disadvantages as follows:
\begin{itemize}
-\item It is not compatible to all types of the iterative applications because some of these
+\item It is not compatible with all types of the iterative applications because some of these
applications need to receive the data messages 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.
+ application performs an infinity number of iterations and then all of the system
+ is crashing.
\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 the iterations may increases proportionally
+ The increase in the number of the 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 While the process not receive the new data messages at each iteration, the mechanism of
+\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 performs many iterations
+ asynchronous ones. 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
+ 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 diverges after computing the next iteration.
+ because the local subsystem will locally 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.
\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
+ not able to measure the energy consumption of all the parallel systems because it depends on
one value for each of the static and dynamic powers.
\end{itemize}
-Therefore, one of the more important goals of this work is to develop an energy models that
+Therefore, one of the more important goals of this work is to develop energy models that
has be taken into consideration 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 may be local or distributed computing clusters.
\section{Conclusion}
In the first section, different types of parallelism levels that can be implemented in a software and hardware techniques have explained. Furthermore, the types of the parallel architectures are demonstrated and classified according to how their computing units are connected to a memory model.
Both of the shared and distributed platforms are demonstrated and depending on them the parallel programming models have categorized.
In the second section, the two types of parallel iterative methods are described as synchronous and asynchronous iterative methods. 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 used for measuring the energy consumption of the parallel applications from the related literature has described. This model cannot be used for all types of parallel architectures. Indeed, it assumes measuring 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, which are consumed different dynamic and static powers at the same time.
+Finally, in the third section, an energy consumption model used for measuring the energy consumption of the parallel applications from the related literature has described. This model cannot be used for all types of parallel architectures. Indeed, it assumes measuring 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, which are consumed different dynamic and static powers at the same time.
However, in the next chapters of this thesis a new energy consumption models are developed, and how these
-energy models are used for modeling and measuring the energy consumptions by parallel iterative methods running on both homogeneous and heterogeneous architectures. Furthermore, these energy models use in a methods for optimizing both of the energy consumption and the performance of the iterative message passing applications.
\ No newline at end of file
+energy models are used for modeling and measuring the energy consumptions by parallel iterative methods running on both homogeneous and heterogeneous architectures. Furthermore, these energy models use in a method for optimizing both of the energy consumption and the performance of the iterative message passing applications.
\ No newline at end of file
