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.
+to describe the types of 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.
\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}.
+The process of the simultaneous application of the calculations is called the 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:
\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 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 as in the 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.
\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, 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 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 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 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 a 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.
+According to the Moore’s law \cite{ref9}, the 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 to satisfy this increased.
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.
\begin{figure}[h!]
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 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 has the maximum execution time (the slowest task) as follows:
\begin{equation}
\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
+\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 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.
+Vector and array processors 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.
\begin{figure}[h!]
\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 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 some interesting uses such as the systolic arrays and dataflow machines.
\begin{figure}[h!]
\centering
\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
+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 communication network model. The multi-core processors, local
+clusters and grid systems are an examples for the MIMD machine.
+Many of applications have conducted over this architecture
such as computer-aided design, computer-aided manufacturing, simulation, modeling, iterative applications and so on.
\begin{figure}[h!]
The work of this thesis is dedicated to MIMD machines 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, the 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:
\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}.
+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 GPU is the NVIDIA GeForce TITAN Z with 5700 cores in 2015 \cite{ref17}. While the general-purpose microprocessors (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
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.
-
+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 handles 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 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.
\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 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 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 the 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 applies 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 keeps all the messages from the lost.
\begin{figure}[h!]
\centering
\label{fig:ch1:12}
\end{figure}
+
\begin{figure}[h!]
\centering
\includegraphics[scale=1]{fig/ch1/grid5000.pdf}
\end{itemize}
-Grid'5000 \cite{ref21} can be considered as a good example for this distributed platform.
+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
+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
There are 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.
+which is the shared and the distributed models. Moreover, these two types are divided into two subcategories according to the support level to the number of computing units composing them.
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.
\begin{itemize}
\item \textbf{Local cluster programming models}
\begin{itemize}
- \item \textbf{MPI} \cite{ref23} is Message Passing Interface, is a standardization
+ \item \textbf{MPI} \cite{ref23} is the 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
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.
+ inside both 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
\cite{ref26}. While MPI has 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 linear algebra messages communication
- model which is applied effectively over distributed memory architectures.
+ 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
\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.
+ to discover the inherent parallelism. Many specification are used in Cilk
+ such as the load balancing, synchronization and communication protocols.
\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
+ It woks on the principle of dividing the computations 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
+ it easily ported to a 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
+ support to vector processing architecture and then it connected with OpenMP
and Cilk to support this platform.
\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 been increasing chip-level
+ parallelism. Current NVIDIA GPUs are many-core processor 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{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 platform composed
+ of CPUs and GPUs. The first release is 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.
+ This parallel programming language can support the homogeneous shared memory
+ platforms and the multi-core processors, by using one core for control
+ and the others for computing.
\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
+ provides a graphical pipeline parallelism.
+ The last version of HLSL is v5.0 for 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.
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)}$. This operation $F$ is applied sequentially many times until convergence condition is satisfy 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 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:
\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 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.
\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 the
+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
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.
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.
+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 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 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 is wasted 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.
+For this reason, this algorithm is effectively implemented over a local cluster where a high speed local network is exist to reduce these idle times.
\begin{figure}[h!]
\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
+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 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 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.
+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.
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.
+The asynchronous iterative algorithm uses asynchronous communications and called \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.
+ This 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.
\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.
+The global convergence of the parallel iterative method depend 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.
\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.
+ 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.
-\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
+\item The application of the 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 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
- the synchronous iterative methods for detecting the global convergence cannot be used for
+ synchronous iterative methods for detecting the global convergence cannot be used for
asynchronous ones. Therefore, in AIAC algorithm a process can performs 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
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 our works, we are interested to implement both of a synchronous and asynchronous
+iterative methods for solving different problems over local homogeneous cluster, local heterogeneous cluster and distributed grid. Then, the process of optimizing their energy consumptions and performance is the main objective of this work as shown in the coming chapters.
\section{The energy consumption model of the parallel applications }
\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 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:
{} =\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 power 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 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:
\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}$ is not changes when the frequency of the processors 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
\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 nodes, $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 of this energy model as follows:
\begin{itemize}
-\item The message passing iterative programs consist of the communication and computation times.
+\item The message passing iterative program consists of the communication and computation times.
This energy model is assumed that the dynamic power consumes during both these times.
While the processor during the communication times involved remain idle and only consumes the static
power, for more details see \cite{ref53}.
\label{ch1:5}
In this chapter, we have 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.
The two parallel systems are described, which are the shared and distributed platforms. Depending on these two types, we have categorized the parallel programming models. The parallel iterative methods are explained and their 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 are interested in this work. The energy consumption model for measuring the energy consumption of the parallel applications from the related 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.
+Consequently, running these two types of the parallel iterative methods over distributed platforms are interested in this work. The energy consumption model for measuring the energy consumption of the parallel applications from the related literature is described. This model cannot be used for all types of parallel architectures. It is assumed to measure the dynamic power during both 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 the heterogeneous architectures when there are different
+types of the processors, which are consumed 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.
