Algorithms and parallel programming Page 1/76

Course objectives

The objectives pursued in the context of this course on Algorithmics and Parallel Programming
are presented as follows:
1. Allow students to acquire basic concepts in parallel and distributed computing.
2. Study and analyze parallel algorithms
3. Design and deploy parallel programs for workstation networks, clusters and
global computing

Prerequisites

In order to ensure a good understanding of this course, students are expected to have
solid knowledge in the following fields and languages:
Linux operating system
2. Language C (C++, Fortran, Java)
3. Notions of complexity
4. Management of Competition

Course summary

1. Generalities on parallelism
2. Parallel Programming Models
3. Parallel programming with MPI
4. Parallel scientific libraries
5. Grid computing

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithms and parallel programming Page 2/76

Chapter 1

Generalities on parallelism
1.1. Motivation and definition of a distributed system

1.1.1. Motivation

Computer Science of 1946 with the construction of the ENIAC (Electronic Numerical Integrator And
Computer) composed of 19000 tubes, weighing 30 tons, with a clock speed of 100 KHz, does not
nothing to do with current Computing where micro-computers reach speeds
above 3 GHz for less than ten kilograms. The use of a computer has become
almost indispensable in everyday life. However, despite the omnipresence, see
Despite the omnipotence of computers, there are still and always needs for computing power.
superior to the capabilities of current machines.

The needs for computing power (and even storage) are increasing in a
a multitude of domains (simulation and modeling, signal processing, image processing, data mining,
drug design, molecular biology, web page ranking etc.) and the
Parallelism is an attempt at an answer that is still relevant today. This is the purpose for which they were designed.

supercomputers, machines composed of several hundred, even thousands, of interconnected processors

by a high-speed interconnection network. This type of machine experienced its heyday until
1990s. That’s when clusters of stations (or clusters) appeared, much less expensive,
but offering performances that can be comparable to those of supercomputers. These
clusters consist of a set of inexpensive commercial stations, connected by a network
more or less fast. This revolution was only possible thanks to constant efforts in terms of
software design and development.

Currently, these different types of machines coexist and the fleet of universities and
companies are often very heterogeneous, comprising supercomputers, clusters (groups of
computers) and personal workstations. However, these different machines are not sufficient.
always to solve increasingly complex problems. Networks are becoming increasingly
Rapidly, the current trend in parallel and distributed computing is to seek to federate a
set of these machines, distributed across a continent, or even the entire planet, in order to

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithms and parallel programming Page 3/76

aggregate computing power. This is the famous computing grid (Grid computing) (figure 1.1).
The new type of computing platform is very heterogeneous, whether at the level of
computing resources (processors) or at the level of communication capabilities (network). The consideration of
Accounting for this heterogeneity is therefore a major challenge for the effective use of platforms.
of today and tomorrow.

Figure 1.1: Example of Grid computing

1.1.2. Definition of a distributed system

A distributed system is a set of independent computers that appears to the user

as a unique and coherent system.
Note that parallel computation can be done on a parallel machine or on a system.
distributed, which can be made up of 2 or more homogeneous or heterogeneous machines.

1.2. What is parallelism?

Intuitively, a task can be completed much more quickly if it is shared among

several people or on several machines. This concept is called parallelism which can be
to define as the state of what develops in the same direction or at the same time.
Parallelism has been successfully applied in several human activities such as
harvests, the distribution of mail, or even assembly lines in factories. The increase in
the number of workers allows for faster completion. A limit can, of course, be reached.

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 4/76

increasing the number of workers no longer brings any time gain. In fact,
Some tasks are purely sequential and can only be performed by one person.
Par exemple, deux marathoniens ne peuvent se partager la distance à parcourir et réclamer la médaille
of gold.
It is naturally that the concept of parallelism has been applied to computers. As a result, it
it has been possible to meet the power needs required for the realization of projects
consumers in terms of calculations and memory size. In fact, parallelism can be defined
as a technique for enhancing the performance of a computer system based on
the simultaneous use of multiple resources (processor, memory, hard disk, ...). This means
that will require breaking down the problem to be solved into several sub-problems that can be
resolved concurrently by several processors.

1.3. Definition of an algorithm

An algorithm is a problem-solving procedure stated in the form of a series

operations to be carried out in order to obtain the desired result. The Webster's Ninth New College Dictionary
defines an algorithm as 'a procedure solving a mathematical problem in a finite number'
of steps that often involves the repetition of an operation; or more broadly: a procedure
solving a problem step by step and arriving at an end. It's a game of rules or of
well-defined procedures that must be followed to obtain the solution to a problem in a finite number
steps.
An algorithm can understand algebraic and arithmetic procedures and instructions,
logical, and others. An algorithm can be simple or complicated. However, an algorithm must
obtain a solution in a finite number of steps.

Algorithms are fundamental in the search for a solution through computer means.
because one must give a computer a series of clear instructions to lead to a solution
in a reasonable time. Programming a computer requires more than just a simple translation
well known instructions in a language understandable by the computer.

Combined parallelism with efficient algorithms allows for saving time in order to
best respond to important needs. It breaks with the classic approach that involves winning
the speed by performing each operation more quickly, is bounded by the laws of physics.

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 5/76

1.4. Importance of parallelism

Currently, the use of parallelism is primarily justified by performance needs.

to satisfy on one hand, the time constraints that are due to the real-time nature of the problems
such as weather forecasts, the interpretation of satellite photographs of critical regions, etc...
and on the other hand by the size of the problems.

Let us also mention the intrinsically parallel nature of certain problems that will gain clarity.
to be programmed according to a parallel model providing the appropriate constructions. Finally, let us note the

need for power as an economic phenomenon: a fast machine will be faster

made profitable because it will do more work.

1.5. Parallel programming models

Let us consider the following sequential program that calculates a vector of polynomials.

pouri = 0àn-1making
vv[i] = a + b.v[i]² + c.v[i]3+ d.v[i]4+ e.v[i]5+ f.v[i]6+ g.v[i]7
end for (VP)

Generally, two types of parallelism are distinguished:

a. Data parallelism: A program follows a programming model of parallelism
data if it involves a single process that acts on a set of data concurrently.

The instances of the body of the loop of the problem (VP) can execute independently.
one another:

pour = 0 to do in parallel
vv[i] = a + b.v[i]² + c.v[i]3+ d.v[i]4+ e.v[i]5+ f.v[i]6+ g.v[i]7
end for

Each vv[i] can be calculated on a processor P.i(i=0, ..., n-1)

P0 P1 ... Pn-2 Pn-1

vv[0]=.. vv[1]=... ... vv[n-2]=... vv[n-1]=...

Note that in data parallelism, the data is often more numerous than the
number of processors. This raises the issue of load distribution between the processors. For this
Data distribution can be done in three different ways: by block, cyclically, or by blocks.
cyclic

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 6/76

Figure 1.2: Data distribution

b. Control parallelism: A program follows a programming model with parallelism

checks if it includes several processes that run concurrently and communicate
to carry out the overall action of the program. Each process has its own private data.

We evaluate the polynomial of the program (VP) in parallel.

vv[i] = a + b.v[i]² + c.v[i]3+ d.v[i]4+ e.v[i]5+ f.v[i]6+ g.v[i]7

(a + b.v[i]² + c.v[i]3) + v[i]4(d + e.v[i] + f.v[i]2+ g.v[i]3)

We obtain three sub-expressions of comparable complexity.

Each sub-expression will be evaluated by a different processor.

The problem to solve becomes

pouri = 0àn-1faire
parallel_tasks
x = a + b.v[i]² + c.v[i]3
y = d + e.v[i] + f.v[i]2+ g.v[i]3
z = v[i]4
end parallel_tasks
vv[i]= x + y* z
end for

Figure 1.3: graph of (a+1)*(b-2)

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 7/76

Here, parallelism is limited to three processes. The processors must synchronize at the end.
of a calculation.

Control parallelism requires:

1. breaking down the problem into tasks
2. study of tasks to determine which can be executed in parallel and which must
execute sequentially.

These categories of parallelism can be achieved through programming models.

following:
the data-parallel programming model
the lightweight process programming model1
the message passing programming model

In the data parallel programming model, the flow of control is unique and each
instruction is executed on a dataset arranged on a virtual geometry. This
Geometry is defined by an abstract description of a virtual processor grid. The complexity
The calculation and communication of a data-parallel algorithm varies depending on the strategy of the
data distribution. The choice of data distribution is related to the choice of the
geometry used. As a result, the choice of geometry becomes an important parameter to consider
taken into account in this type of programming model. HPF and CM Fortran are two typical examples
parallel data programming languages. This programming model is well suited for
SIMD machines like CM-2 or CM-200.

The paradigm of programming with lightweight processes is based on data sharing in

the same memory space. In this programming model, communications are implicit. The
Information is transmitted when writing in a shared memory area and then retrieved.
when another process comes to read this area. The synchronization must be explicit using
basic instructions for managing mutual exclusion and waiting on condition. Both
The most widespread tools for programming with lightweight processes are OpenMP and Posix Thread.
First is based on a compiler that analyzes the specific directives present in the program.
and generates calls to the available thread library. The second involves exploiting

1
multithread programming model

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 8/76

directly the thread library defined in the Posix standard. This programming model is well
adapted to MIMD machines of the shared memory type such as IBM SP3 or IBM SP4.

In the message-passing programming model, each process has its own

private memory. The processes must then communicate to transfer information across a
network2Thus, communication is explicit while synchronization can be explicit or
implicit (it is produced by communication). It is the dual of the shared memory model. This
The programming model is well suited for MIMD machines that have a memory architecture.
shared, distributed and hierarchical memory like IBM SP3, IBM SP4, CRAY T3E, NOW or the
IBM SP3 or SP4 cluster. This programming model is the most portable, therefore the most used.
The difficulty of this model comes from the network characteristic. There are several types of
communications depending on whether the emission and reception are blocking or not. We speak of
synchronous communications when the transfer of information is only possible after a
global synchronization of the transmitting and receiving processes. In this case, the transmission and reception

can be blocking. The emission can be non-blocking if the network interface can move it
even the data, or whether the processor can be interrupted later to move the data.
Finally, if the emission is non-blocking with a network that cannot retain messages, we obtain
an unstable communication.

In the message passing programming model, processors can

communicate with each other in the following four ways:
one to one
one to many
many to one
many to many

According to Dekeyser and Marquet, any language that can be called a data-parallel language
in which an instruction involves several identical processes on the data of a set.
Data parallelism offers the programmer defined primitives on sets (vectors
and matrices most commonly), which translates into duplicating the processing as many times as there
of data in the specified structure.

2
The ways to transfer private data between processors vary according to the architecture of the parallel machine.

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 9/76

While different ways to program a sequential machine can be found, the uniqueness of
however limits the models that could be associated with it. Thus, the 'optimal' model
is quickly found. The parallelism, on the contrary, has greatly multiplied the possibilities:
Number of processors,
Arrangement,
Communication network
•Shared or distributed memory,
Centralized or distributed control,
etc

The quest for the optimal model in parallelism is still a subject of research. In fact,
the analyses agree that a single model is an illusion, given the diversity of problems and
the machines (or models) to solve them is large.
The notion of parallelism has greatly contributed to the multiplication of computational models.

1.6. Key concepts of parallelism

1.6.1. User time (wallclock time) and computation time (cpu time)

Let P=4 be the number of processors. Let's imagine that the execution time of a program is
4 minutes if it is handled by only one processor.
If we use the 4 processors to perform the same task, each processor should in
principle work 1 minute to do your share of the work.
If no communication is necessary, all processors have effectively completed their task.
after 1 minute. This is the ideal case: the wall clock time is 4 times smaller than that of the serial execution.
The CPU time is however the same (4 processors worked for 1 minute: in total, there are 4)
work minutes.
Unfortunately, some communications are still necessary. These communications
extending the time necessary for each processor to complete its share of the work.
Each processor will therefore work for more than a minute (let's say 1 min 15 sec). Even if we
using 4 processors, we do not get the final result in 4 times less time. The wallclock time is
greater than a quarter of that of serial execution. Moreover, the CPU time has increased (4
Processors worked for 1 min 15 sec: in total there is now 5 minutes of work.

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 10/76

Figure 1.4: Wallclock time and CPU time

1.6.2. Load balancing

Let's suppose that in the previous example one of the four processors is twice as slow as
the other three. It will take him 2 minutes and 15 seconds to complete his part of the work. The other three processors
will have worked for 1 minute 15 seconds and then will have remained 1 minute doing nothing (CPU is idle). The user
Wait 2 minutes 15 seconds to get your result. The wall clock time is therefore more than half of that.
of a serial execution.
The situation is worse than if we had only worked with the other three processors. In
Indeed, the wall clock time would have been 4 min / 3 + 15 sec = 1 min 35 sec. To use it exactly the
the slowest processor actually needs to be given half the work of the other three. We
this touches on the issue of workload distribution (load balancing).

Figure 1.5: Load balancing

1.6.3. At what level to parallelize?

A program can consist of several independent parts. These can include

themselves independent sub-parts, which contain other independent sub-sub-parts.

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 11/76

Where should we parallelize? At the highest level (processing the parts in parallel)? Or at the level
plus bas (traiter en parallèle les sous-sous-parties)?
Parallelizing at the highest level reduces communication times, but the work is at risk.
to be poorly distributed if the parts do not all have the same execution time.
Parallelizing at the lowest level increases communication times, but the work is
better distributed among the processors.
We recommend letting the compiler handle the lowest levels and
parallelize your program at the highest level.

Figure 1.6: Granularity of a program

1.7. The dangers of parallelization

Parallelism has not only advantages. Thus, we can note the following dangers related to
in parallelism:
1. Rounding errors can depend on how the work is distributed. The results of a code
Parallelized ones are not always identical to those of a sequential program.
2. If multiple processors access the same data, undesirable effects can occur if these
data is modified by a processor and if others continue to work with an old one
version of these.
The process by which each processor has at each
instant of the same shared data copy. This update operation is resource-intensive
communications and reduce the effectiveness of parallelization.

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 12/76

In practice, it is better for each processor to work with private versions of

each data (private variables are not visible to other processors and therefore it is not
necessary to inform them of a possible modification of these.

3. Opening files by several processors at the same time can also cause problems.
(notably during parallelization with OpenMP or MPI). It is then necessary to keep up to date a
shared variable that indicates at every moment whether a file is being manipulated or not. A
The processor is only allowed to open a file if it is the only one doing so.

Before opening a file, a processor must therefore check the status of this variable and
to wait for it to take a value indicating that no other processor is handling the file. It
then change the state of this variable, manipulate the file, and restore the variable to its initial state.
allowing other processors to manipulate files.
4. When the work of one processor requires that of another to be completed, it is again
necessary to keep him waiting.

1.8. The top500

Every year, a list of the 500 largest computers is published on[Link]

Excerpt from the list of November 8, 2006:

Rank Name / Manufacturer Country / Year Processors

1 BlueGene /IBM USA/2005 131072
2 Red Storm/Cray Inc. USA/2006 26544
3 BGW/IBM USA/2005 40960
4 ASC Purple/IBM USA/2006 12208
5 MareNostrum/IBM Spain/2006 10240
6 Thunderbird/Dell USA/2006 9024
7 Tera-10/Bull SA France/2006 9968
8 Columbia/SGI USA/2004 10160
9 TSUBAME Grid Cluster/Nec Sun Japan/2006 11088
…
+ PC House Everywhere/2007 1

Figure 1.7: Top500 of parallel machines

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 13/76

Chapter 2

Parallel programming models

2.1. Introduction

Parallel computing ('parallel processing' or 'high-performance computing') encompasses

both the design of time-efficient algorithms, the architecture of the computer, the implementation of
Work on programs and performance analysis, with a view to improving the computer tool.

The problems related to parallelism can be approached from both a software and
material:
1. Determination of competition (parallel algorithm or 'software') through evaluation of the
granularity (refers to the number of calculations, instructions, or elementary operations), implementation in

mechanism for control ensuring the execution of programs (synchronization) and the
data management (geometry of communications).
2. Projection ('mapping') of parallel algorithms on specific machines (architectures
parallels or "hardware": complexity of the elementary computing entity, operating mode,
memory distribution and interconnection network.

2.2. Models of parallel machines

2.2.1. Principles of parallel machines

A parallel machine is made up of a set of processors capable of cooperating in order to

solve a problem.
This definition includes parallel supercomputers with hundreds or thousands of
processors, clusters, that is to say a set of machines (workstations
or PC) connected by an interconnection network (IN), or even multiprocessor workstations.

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 14/76

Parallel machines essentially have two types of memory:

[Link] Memory Machines (SMP3): the processors are connected via
from an RI to the same memory that they share. In SMP architectures, the memory is
accessible and shared by all processors of the machine symmetrically. These
architectures allow for quick access to data but limit the number of
system processors. In this type of architecture, at least one level of cache memory
is specifically associated with each processor. The cache memory prevents that
processors access the shared memory when the data is in the cache.
However, several copies of the same data can exist in different caches.
That is why consistency between the different copies of the data must be ensured in order to
that a piece of data read by a processor has a correct value. Sun E10000, IBM SP3 and
SP4 are examples of machines that exhibit this type of architecture.
[Link] à mémoire distribuée (MPP4). In distributed memory architectures
chaque processeur ne peut accéder qu'à sa propre mémoire. Afin d'accéder au reste de la
memory, each processor must communicate with the others. The processors can
communicate with each other only by sending messages through an interconnection network.
Fujitsu AP3000, CRAY T3E are examples of machines that have this type.
of architecture. NOW (Network Of Workstation), another representative example of this type
of architecture, consists of a set of heterogeneous and/or homogeneous machines, connected
through an interconnection network of the Ethernet type, HiPP, SCI, Myrinet, etc.

3
Symmetrical Multi Processors also known as shared memory multi processors systems

4
also called shared nothing

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 15/76

Figure 2.1: Different memory and CPU organizations

There are also non-uniform memory access (NUMA) architectures. 5) and architectures
hierarchical.
Unlike SMP architecture, non-uniform memory architectures do not offer a
uniform cost of memory access. This type of architecture allows for global addressing for the
distributed memories (the local memory of each processor). This global addressing can be located
either at the hardware level or at the software level. Each processor has its own memory
The local accesses other memories via an interconnection network. This network can be made up of a
hierarchical bus structure. In this case, the access time to memory depends on the number of buses
crossed. Generally speaking, the bandwidth of this type of network increases depending on the
number of processors, allowing for better scalability of the NUMA architecture (some
hundreds of processors) compared to the SMP architecture. The SGI Origin 2000 machines,
Onyx 3000, Compaq GS Series Alpha Server are representative examples of NUMA architecture.

A hierarchical architecture is a combination of shared memory architecture.

and distributed memory architecture. The idea here is to build a machine with distributed memory
each node adopts a shared memory parallel architecture. The type architecture
hierarchical allows for the extensibility of a distributed memory architecture while maintaining a

5
Non Uniform Memory Access

Prof. Dr. Saint-Jean DJUNGU

Phone: +243 897232200; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 16/76

part of the flexibility provided by shared memory. It allows the interconnection of a large
number of shared memory nodes, which can themselves be powerful multiprocessors. In
Each node's communications between the processors are efficiently done thanks to the memory.
shared.

Routing determines the path to take in the network to go from a source processor to a
destination processor. The communication mode indicates how the messages are
transported.
We distinguish the following modes:
Circuit switching: before sending its message, the source sends a request.
to the destination in order to build an end-to-end physical circuit. Once the
circuit established, the message is then transmitted directly to the destination,
Packet switching: each router has memory buffers, each of which can
store a packet. Upon receiving a packet, the router stores it in one of
buffers before forwarding it to the next router on the packet's route. Each packet
contains information allowing the router to calculate the path to follow,
"Whormhole": the message is divided into small entities called "flits" that are
stored in the memory buffers of routers. Only the first 'flit' contains
information that allows the router to calculate the path to follow, while the others
"flits" contain only data. They must therefore proceed one after the other.
others in the network.

Communication can be:

global: each processor communicates with all other processors,
A processor communicates with a limited set of processors,
- point-to-point: a sending processor sends a message to a receiving processor.

His mode of operation can be:

-Synchronous: all processors work synchronously under the control of a
common clock
-Asynchronous: each processor works under a specific clock. In such a mode,
the programmer has the responsibility to set synchronization points (called
synchronization barriers) as needed.

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 17/76

2.2.2. Classification of parallel machines

Historically, the first parallel machines are networks of computers, and

vector machines and weakly parallel (1970s - IBM 360-90 vector, IRIS 80
triprocessors, CRAY 1 vector...

There are several types of classifications of parallel machines. The classical classification
Flynn's classification is based on the notions of control flow and data flow.
Flynn's taxonomy presents four types of parallel machines: SISD, SIMD, MISD, and MIMD.

1. SISD machine. A SISD (Single Instruction stream Single Data) machine is what we
usually calls a sequential machine, or Von Neumann machine. A single
instruction is executed at a given time and a single piece of data (simple, unstructured) is
treated at every moment.
2. MISD machine. A MISD (Multiple Instruction stream Single Data) machine can execute
several instructions at the same time on the same data. This may seem paradoxical but
this actually covers a very ordinary type of micro parallelism in microprocessors
modern: vector processors and pipeline architectures.
3. Machine SIMD. In a SIMD (Single Instruction stream Multiple Data) machine, each
the instruction of a program is executed identically on each processor, but on some
different and private data to each processor. In other words, in this type of machine,
The parallel execution of the same instruction occurs simultaneously on processors.
different. In general, it has a large number of processors. The CM-200 computers,
CM5, Hitachi S3600, CPP DAP Gamma II, and Alenia Quadrics were among the first
examples of parts of SIMD machines.
Systolic machines are special SIMD machines in which the
calcul moves across a topology of processors, like a wave front, and acquires
local data changes with each wave front movement (comprising several
processors, but not all in general).
In both cases, the parallel execution of the same instruction is done at the same time on
different processors (synchronous data parallelism).
4. MIMD machines. The case of MIMD (Multiple Instruction stream Multiple Data) machines is
the most intuitive. Here, each processor can execute a different program on data
different. We have several possible types of architecture:

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 18/76

Shared memory
Local memory + communication network (Transputer, Connection Machine) - System
distributed.

Because it is generally not necessary to use different programs for each

processor, the same code is often executed on all the nodes of a MIMD machine but they
are not necessarily synchronized. We then refer to the SPMD model (Single Program Multiple Data).

A shared memory MIMD machine is primarily made up of processors with

independent clocks, thus evolving asynchronously, and communicating by writing and reading
values in a single shared memory (shared memory). An additional difficulty that
We will not describe further here, is that each processor generally has at least one data cache, all
these caches must have consistent information at crucial moments.

Figure 2.2: Possible paradigm of parallel architectures

Notons SPMD is a special case of the more general MPMD model (Multiple Program,
Multiple Data), which it can also emulate .

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 19/76

Parallel algorithms are an approach that has allowed the development of models enabling
to solve a large number of problems. These models can be classified into two main families
what are: fine-grained models and coarse-grained models.

Regarding the design of high-performance parallel machines, the main focus of

the difficulty lies in defining the most suitable 'mapping' that most often results
a compromise between the needs required by an application and the constraints imposed by the
technology

2.2.3. Fine-grained models

Fine-grained models were the first parallel models to appear. The notion of grain
comes from the fact that, for these models, it is assumed that the number of processors is essentially
equal to the number of input data.
The two main families of fine-grained models are: memory machine models
shared and distributed memory machine models.

a. Shared memory models

The PRAM (Parallel Random Access Machine) is undoubtedly the most

popular in parallel computing. As described in figure 2.3, the model consists of a number of
processors sharing a common memory. The processors can solve a problem
calculable in parallel by the simultaneous execution of the different steps of an algorithm. The memory
shared contains the data and the results, and also serves as a means of communication between
processors. An interconnection unit (IU) allocates access to the processors for the locations of the
memory for reading and writing.

Figure 2.3: The PRAM

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithms and parallel programming Page 20/76

This model is further specified by defining the access mode to memory. Four variants
are the most often used:
- Exclusive-Read Exclusive-Write (EREW) PRAM: in this variant, two processors do not
can access the same memory location simultaneously whether to read or
good for writing,
Concurrent-Read Exclusive-Write (CREW) PRAM: this variant allocates more than one
processor for reading but not for writing in the same memory location at the same time
weather
Concurrent-Read Concurrent-Write (CRCW) PRAM: for this variant, it is possible
for multiple processors to access the same memory location to read or to
to write
- Exclusive-Read Concurrent-Write (ERCW) PRAM: this variant has a very
restricted applications.

The advantage of this model is its simplicity. Moreover, it is very useful for highlighting parallelism.
studied problems. It is often a first step towards parallelization.

Given its high level of abstraction, it allows us to know to what extent a problem
may be parallelized or not. However, it is greatly removed from real machines. Furthermore, the
technological constraints do not allow a large number of processors to access a
common memory in constant time. That is why there is no PRAM machine today; to
memory is distributed among the processors.

b. Distributed memory models

In this model, each processor has its own constant-size local memory and there is no
no shared memory. The processors can only communicate through an RI. Like in
In PRAM, the processors work synchronously. At each step, each processor can
simultaneously send a data word to one of its neighbors, receive a data word from one of its
neighbors and perform a local operation on its data.

Each distributed memory model explicitly takes into account the topology of the network.
interconnection represented by different characteristics:

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 21/76

the degree, which is the maximum number of neighbors for a processor. It corresponds to a
sort of architectural limitation given by the maximum number of physical links
associated with each processor,
the diameter, which is the maximum distance between two processors (the distance being the most
short path in the interconnection network between these two processors). It provides a
lower bound on the complexity of algorithms in which two processors
arbitrariness must communicate,
the bisection, which is the minimum number of links to remove in order to disconnect the network
two networks of the same size (give or take one processor). It represents a
lower bound on the execution time of algorithms where there is a phase that does
communicate half of the processors with the other half.

Among these distributed memory models, the two-dimensional grid and the hypercube have been
widely used. More recently, other interconnection networks have emerged such as the
honeycombet its extension called star-honeycomb, or also leXmesh.

Figure 2.4: Grid and Hypercube

The specificity of the algorithms developed on distributed memory models (if possible
effective or even optimal) is a major drawback. Thus, these algorithms are not portable because
They are heavily dependent on the chosen topology.

c. Systolic model

By definition, a systolic array is a network of processors that compute and exchange

data regularly. The analogy is made with the regularity of the heart's contraction that propagates
the blood in the body's circulatory system. Each processor of a systolic network can be seen

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 22/76

like a heart playing the role of a pump on several crossing streams. The regular rhythm of these
processors maintain a constant flow of data throughout the network.

This model appears when VLSI and WSI technologies have emerged and its success relies on
large part of its adaptation between the demand for extremely fast low-cost calculators and the
possibility of significantly reducing the execution time of several sequential algorithms
At the simple price of an increase in the complexity of the material through the replication of structures.

simple and regular elementary.

Since then, significant efforts have been made to design parallel architectures based
on the regularity of the data rhythm ('dataflow architectures'), to pipeline the
processors or vectorize them, or on the regularity of the execution flow ('wavefront architectures'). The
The main problem of developing such computers lies in the organization of intensive flows.
control and data ensuring high performance. The pipelined architectures and
"wavefront" are systolic variants that are among the most effective. They have thus largely
contributed to the dissemination of the systolic model and to its familiarization.

The dominant characteristics of a systolic network can be summarized by a

massive and decentralized parallelism, through local and regular communications and by a mode
synchronous operation. To describe a systolic network, it is therefore necessary, just like with a
language such as VHDL (standardized specification language for the realization of integrated circuits), of
specify:
the interconnection graph of the processors (network topology),
the architecture of a processor (description of registers and channels: name, type, semantics
…),
the program of a processor (reading values from input channels, combination
of arithmetic and logical operators, storing results in registers and
writings on the output channels,
the flow of data consumed by the network to produce a solution.

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithms and parallel programming Page 23/76

Figure 2.5: Most commonly used systolic network architectures

2.2.4. Coarse-grained models

Most of the machines currently used are large data grain, which means that the
the size of each local memory is much larger than the size of a data item. Thus, from
Numerous studies have described models that take into account the real characteristics of
machines. These models recognize, for example, the existence of communication costs,
unlike the PRAM model, without specifying the topology of the support of
communications, unlike fine-grained models of distributed memory.
The BSP model ('Bulk Synchronous Parallel'), the first model of its kind proposed by Valiant,
formalize the architectural characteristics of existing machines through four parameters.
The LogP model described by Culler et al. specifies more parameters than BSP, while CGM
"Coarse Grained Multicomputers" proposed by Dehne et al. is a simplification of BSP.

2.3. Steps for parallelizing a task

The parallelization of a problem depends on the nature of the problem as well as the architecture.
Material considered. However, the general philosophy is represented in figure 2.5.

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithms and parallel programming Page 24/76

Figure 2.6: Steps of parallelization

Note that the thread or process is somewhat a copy of the program.

Example
1. S=f(A[1])+ ... + f(A[n])
2. Decomposition
Calculation of each f(A[j])
Parallelization of n elements, where n can >>> p
Calculation of the sum S
3. Assignment
•Sum of the thread Sk= f(A[k*n/p]) + … + f(A[(k+1)*n/p-1])

Thread 1 sum S = S1+ … + Sp

Thread 1 communicates S to the other threads
4. Orchestration
Starting threads
•Communication, synchronization with thread 1
5. Mapping
Processor j executes thread j
In this section, we present in order of increasing complexity, the different ways
to parallelize his problem.

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 25/76

2.3.1. Help the compiler to parallelize

The compiler itself performs a number of parallelizations.6Just help him.

in his task by programming in a clear manner.

Here are some tips that can help the compiler:

1. Use global instructions instead of sums over the indices. For example, write:
s=a+b;
rather than
for (i = 1; i <= n; i++)
{
s(i) = a(i) + b(i);
}
Think about using the instructions sum, product, etc. when possible. For example, write
sum = sum(a)
rather than
sum = 0 ;
for (i = 1 ; i <= n ; i++)
{
sum = sum + a(i);
}

2. Avoid cluttering your loops with instructions that may lead the compiler to think that
iterations are not independent. For example, avoid this:

for (i = 1; i <= n; i++)

{
num = num + 1 ; /*depends here on previous iterations*/
.
.
.
int subpr(int num); We do not know how souspr affects num
or other variables. In case of doubt, the

6
A condition to use autoparallelization options at compile time

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 26/76

compiler prefers not to parallelize.

*/
}

Note that libraries like LAPACK are already parallelized.

2.3.2. Distribute the data to be processed

If your IT infrastructure allows you to run multiple executables at the same time, you
you can parallelize your problem by assigning each machine the calculations corresponding to a part
of this problem. The idea here is to parallelize the task to be done rather than the program itself. This
last indeed must not undergo any modification.
Note that the assignment of tasks to processors poses a scheduling problem.
Example:
You have 20 machines and you need to compute a function on a grid of 100 points.
Just assign the calculation of 5 points to each machine. Rather than parallelizing your program,
The idea here is to plan 20 tasks that will execute the same sequential program on inputs.
different. Once the 20 tasks are completed, you just need to collect
the partial results.
What to do if all machines are identical? We must avoid entrusting the machines with
too slow too much work under the penalty of having to eventually wait for them. The idea is to entrust each
machine the right amount of work, so that they all finish at the same time.

Thus, we can consider the following scheduling models:

a. Continuous distribution model

To set things straight, let's assume we have 10 additional machines, 3 times slower.
that the first 20. We have 100 calculations to complete, which take one minute each on the
the fastest machines and therefore 3 minutes on the slowest.

Let N=100 be the number of calculations to be performed, N1the number of fast computers, N2=10 the number
slow computers. Let's call v1=3 the speed of fast machines and v2the speed of machines
glasses. We are looking for the number n1calculations to assign to each fast machine and the number n2of
calculations to be entrusted to each slow machine.

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 27/76

One must then satisfy:

n1.N1+ n2*N2=N
n1/v1= n2/v2

We find:

v1.N 3.100
n1= = 4.2857...
v1.N1+v2.N23.20 + 10
v2.N 1.100
n2= = 1.4285...
v1.N1+v2.N23.20 + 10

All the machines will finish their task at the same time if we assign each of them this
number of calculations. As these numbers are fractional, some of the slow machines will receive in
reality 1 calculation to be made, others 2. The latter therefore receive too much work and will be delayed.
the end of the process. They will indeed need 2 * 3 = 6 minutes to complete their task, whereas 5
minutes were sufficient by only working with the fastest machines. We see that this model
give an approximation of the number of calculations to assign to each processor, but do not give the
optimal name.

b. Discrete distribution model

In the previous example, only one task should have been assigned to the most...
lenses2and leave what remains to the fastest computers. The new idea is not to entrust
a task to a slow processor only after all the fast processors have already received 3
tasks. Only then do slow processors become useful and stop making us wait.
end of the procedure.

The initial distribution of tasks is then done gradually (see figure 2.6). The v1.N1=60
the first calculations are entrusted to the 20 fast processors. The v2.N2The following 10 calculations are then
entrusted to the 10 slow computers. And we start again like this: the v1.N1=60 calculations that follow are entrusted to
fast computers. A second calculation is only entrusted to slow computers if each computer
Rapide has already received 6 tasks (these will be tasks 131-140).

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 28/76

Figure 2.6: Discrete distribution model

The algorithm is therefore:

1. Rank the processors in descending order of speed

2. Distribute the tasks one by one:

o starting from the left

o by shifting one square to the right if ni/vi(ni+1+1)/vi+1

o returning to the first box if this condition is not met or if we arrive at all
right

2.3.3. Parallelizing your program with OpenMP

If the processors we want to use have access to a shared memory area

memory), we can parallelize our program with OpenMP. The OpenMP library allows us to provide
to the compiler of directives on how to parallelize its program. For example, one can
indicate that such a loop is parallelizable, that such a variable is shared or private, etc. The
The compiler handles all the management of this information.
The OpenMP standards date back to 1997, with OpenMP-2 standards established in 2000. The developers of

compilers (Fortran, C, and C++) implement them.

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithms and parallel programming Page 29/76

Figure 2.7: OpenMP execution model

Beware of conflicts.
Very little overhead from parallelization.
Most often, the number of processors < 32.
Expensive architecture.

2.3.4. Parallelizing your program with MPI

The latest model is one where the processors do not have access to a common memory area.
but have only a private memory, visible only to them (distributed memory). The
processors must communicate explicitly with each other to transmit information.
The MPI (Message Passing Interface) library allows for controlling all these communications. We
We will explore it further in chapter 3.

Figure 2.8: Communication model with MPI

It is necessary to manage the message exchange (overhead)

Cheap architecture.

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 30/76

A high-performance communication network needs to be added.

Almost unlimited number of processors.
The specifications of the MPI standard were established in March 1994.

Structurally, parallelization can be done at various levels:

a. Langages:
Compositional C++ (CC++)
Fortran M
High performance Fortran (HPF)
* etc...
b. Libraries:
Message Passing Interface (MPI)
Parallel Virtual Machine (PVM): ~ obsolete.
c. Compilation directives:
OpenMP
Specific manufacturer instructions.
d. Compilers: very low efficiency.
* Intel Fortran/C compiler: free.

2.4. Modeling Cost

2.4.1. Calculation of parallel complexity

To study parallel complexity, we consider classes of very parallel architectures.

simple systems that can be characterized by a single parameter, P the number of processors. The
parallel complexity depends on two variables: the size N of the problem and the number of
used processors.
We define:
a) Gain in performance (speedup) as the ratio between the execution time in mode
sequential and the execution time in parallel on P processors.
b) Efficiency as the ratio between the gain and the number of processors used.
The work of a parallel algorithm is defined as the product of the time complexity of a
processor by the number P of processors.

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 31/76

If the problem is 'completely parallelizable' then the execution time on P

processors are P times faster than on a single one. In this case, the gain is equal to P and the efficiency
the maximum is therefore 1.

In parallel complexity, we have two parameters to manage: N and P. Two cases can be
produce:
a) If N is greater than P, we place several elements on the same processor and process them.
in sequence (also called concurrently). In this method known as virtual processors, the
Processor switching can take time: if this time is a constant that does not depend on
If it is not P, then it does not affect the asymptotic complexity. Conversely, the loss of
performance can be important.
b) If N is smaller than P, we cannot use all the processors; in this case, only
effectiveness is affected.
In practice, the size of the problem is generally much greater than the number of processors: N >> P.

2.4.2. Amdahl's Law

Regardless of the problems dealt with so far, the effectiveness of a parallelization is

limited by the fact that a program does not consist solely of parallelizable parts.

Demonstration:

Let f be the fraction of the code that is parallelizable and P be the number of processors.

Serial execution time: T(1) = f * T + (1−f) * T = T

Parallel execution time: T(P) = f * [ T/P] + (1-f) * T

Speed-up : S(P) = [ T(1)/T(P)] = [ 1/( f/P + 1−f )]

Efficiency: E(P) = [ S(P)/P]

Interpretation:

Ideal case: f = 1 S(P) = P, E(P) = 1

Most unfavorable case: f = 0 S(P) = 1, E(P) = 1/P

Intermediate cases:

• In any case: S(P) < P, E(P) < 1

(we talk about 'scalability' to describe how S(P) compares to P).

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 32/76

• If we do not take communication times into account: S(P) [( P ) || ( )] [ 1/(1-f)]

(saturation), E(P) [( P ) || ( )] 0.

• If we take into account communication times: S(P), E(P) [( P there exists a P

optimal).

{"Conclusions":"Conclusions"}

• S(P) eventually reaches saturation (the later it happens, the closer f is to 1).

• When S(P) saturates, increasing P is no longer justified and becomes dangerous.

• If one obtains S(P) We achieved the best possible parallelization.

• This ideal case is more easily approached by parallelizing at the highest level and where the
program spends the most time.

Figure 2.9: Amdahl's Law

2.5. Summary of Parallelism Models

Performing a parallel computation means having several processors cooperate to carry out a calculation.

Prof. Dr. Saint-Jean DJUNGU

Phone: +243 897232200; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 33/76

Advantages:
Speed:
For N processors, computation time divided by N, in theory.
2. Memory size:
For N processors, we generally have N times more memory.

Difficulties:
One must manage the division of tasks.
It is necessary to manage the exchange of information (non-independent tasks)

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 34/76

Chapter 3
Parallel programming with MPI
3.1 Introduction

The model of parallelism considered in this chapter is one where the processors have
only a private memory, visible only to them (distributed memory). There is no memory here
shared and all information exchange between processors is done via messages that must be
explicitly programmed. The MPI (Message Passing Interface) library provides the instructions that
allow to schedule these information exchanges.

Figure 3.1: Distributed memory model

3.2. Some concepts

3.2.1. Message exchange

A message is made up of data packets (variables, scalars, arrays, etc.) passing through
from the sender process to the receiver process(es). In this environment, if a message is sent to
a process, it must then receive it (see figure 3.2). The receiving process must be able to
classify and interpret the messages that have been addressed to him.

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithms and parallel programming Page 35/76

Figure 3.2: The exchange of messages

3.2.2. The Master and the Slaves

In certain programming models, a particular thread (the Master) is sometimes entrusted with
who has the number 0) the task of distributing/collecting the data. The other threads (the Slaves)
they do the work.

3.2.3. Synchronous or asynchronous messages, blocking or non-blocking

We distinguish the following types of messages:

[Link] messages: Communication ends when the message is fully transmitted.

The sender is informed of the success of the operation.

Asynchronous messages: Communication ends as soon as the message is sent. The sender
just know when the message has been sent.

[Link] messages: The sender cannot do anything during the message sending.

[Link]-blocking messages: The sender can perform other tasks while sending the message.

3.2.4. Individual and collective communications

We distinguish the following types of communications:

Individual communications: from one processor to another

2. Collective communications: between one processor and several other processors

Operations:

• Barrier: wait for all processors to reach the same point in the program

• Broadcast: a processor sends the same message to all other processors

• Reduction: we take data from each processor, we reduce them to a single data point.
which is then made available to all processors

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 36/76

3.2.5. Risk of deadlock

When using blocking messages without caution, it can happen that all threads get
find themselves in a state of perpetual waiting (deadlock).

Example: If all the threads send a blocking message at the same time: they all end up at
await a confirmation of receipt of their message while none of them are able to
to intercept it.

3.3. Basic example

# include<stdio.h>

# include<mpi.h> /* mpi library*/

int main(int argc, char *argv[])

{
int myid, numprocs;

/*MPI Initialization*/

MPI_Init (&argc,&argv);

Know which processor I am

MPI_Comm_Rank (MPI_COMM_WORLD,&myid);

Know the total number of processors

MPI_Comm_Size (MPI_COMM_WORLD, numprocs);

if (myid == 0)

printf(" The number of processors is: %d", numprocs);

printf(" My number is %d ", myid) ;

Quit mpi

MPI_Finalize ();

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 37/76

Result:

My number is 1

Number of processors is: 4

My number is 0

Mon numéro est 3

My number is 2

3.4. Sending messages between two threads (point-to-point communication)

A so-called point-to-point communication takes place between two processes, one called process
emitter and the other process receiver (or recipient).

Figure 3.3: Point-to-point communication

The sender and the receiver are identified by their rank in the communicator.
The part we call the envelope of a message is made up of:
1. the rank of the emitting process;
the rank of the receiving process;
3. of the message tag;
4. the name of the communicator who will define the communication context of
the operation.
The exchanged data is typed (integers, reals, etc. or personal derived types).
There are several transfer modes in each case, using different protocols.

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 38/76

3.4.1 Basic Syntax

int size, source, destination, tag;

MPI_STATUS_SIZE status;

...

MPI_SEND(data, size, type, destination, tag, MPI_COMM_WORLD);

MPI_RECV(data, size, type, source, tag, MPI_COMM_WORLD, status);

where is the information to be transferred, size its size and type its type. source and destination are the numbers

from the transmitter and the receiver. Tag the message number or label. The status table
(MPI_STATUS_SIZE) allows to know afterwards if the communication is finished.

3.4.2. Types of messages

Here are the different possibilities for type:

3.4.3. Sending modes

• Standard sending (blocking asynchronous):

MPI_SEND(data, size, type, destination, tag, MPI_COMM_WORLD)

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 39/76

• Blocking synchronous sending:

MPI_SSEND(data, size, type, destination, tag, MPI_COMM_WORLD)

• Non-blocking asynchronous send:

MPI_ISEND(data, size, type, destination, tag, MPI_COMM_WORLD, request)

oùrequestest un entier qui permet de savoir par la suite si la communication est terminée.

• Non-blocking synchronous send:

MPI_ISSEND(data, size, type, destination, tag, MPI_COMM_WORLD, request)

Blocking buffered send: the message is stored in a buffer before being sent.

MPI_BUFFER_ATTACH(buffer, size)
MPI_BSEND(data, size, type, destination, tag, MPI_COMM_WORLD)
MPI_BUFFER_DETACH(buffer,size)
where buffer is the buffer variable in which data is transferred before communication.

Non-blocking buffer send

MPI_IBSEND(data, size, type, destination, tag, MPI_COMM_WORLD)

3.4.4. Modes of reception

• Blocking reception:

MPI_RECV(data, size, type, source, tag, MPI_COMM_WORLD, status)

wheresourceis the transmitter number (or MPI_ANY_SOURCE) andtagis the message number
(ouMPI_ANY_TAG).

• Non-blocking reception:

MPI_IRECV(data, size, type, source, tag, MPI_COMM_WORLD, request)

where request is an integer that allows to know later if the communication is finished.

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 40/76

3.4.5. Wait or test for the end of a communication

In general, in the case of a send (MPI_IxSEND) or a receive (MPI_IRECV)

non-blocking, there is a whole range of sub-programs that allow for synchronization of a
process (MPI_WAIT) or to check the completion of a request (MPI_TEST).

To wait for the end of a communication:

MPI_WAIT(request,status)

To test if a communication is finished:

MPI_TEST(request, flag, status)

where the logical variable flag = .true. if the communication is finished.

3.4.6. Example of sending and receiving

# include<studio>

# include<mpi.h>
int main(int argc, char *argv[])
{
int rank, size;
MPI_Status status;
Hello from processor 0
char RecvMsg[23];
int root;
int tag;
int rankdest;
int i;
/* initialization */
MPI_Init(&argc,&argv);
MPI_Comm_rank(MPI_COMM_WORLD,&rank);
MPI_Comm_size(MPI_COMM_WORLD,&size);
sending the message
root = 0;
if (rank==root)
for(i=1;i<size;i++)
{
tag=i;

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithms and parallel programming Page 41/76

rankdest=i;
MPI_Send(SendMsg, 23, MPI_CHAR, rankdest, tag, MPI_COMM_WORLD);
}
/* receipt of the message */
RecvMsg=SendMsg;
if(rank!=root) {
tag = rank;
MPI_Recv(RecvMsg, 23, MPI_CHAR, root, tag, MPI_COMM_WORLD, &status);
printf("I am processor %d, I received the message: %s \n", rank, RecvMsg);
}
MPI_Finalize();
}

3.4.7. Wait or test multiple communications

To wait for the end of all communications:

MPI_WAITALL(count, array_of_requests, array_of_statuses)

To test if all communications are completed:

MPI_TESTALL(count,array_of_requests,flag,array_of_statuses)

To wait for the end of at least one communication:

MPI_WAITANY(count, array_of_requests, index, status)

To test if at least one communication is completed:

MPI_TESTANY(count, array_of_requests, index, flag, status)

3.5. Sending messages between multiple threads (collective communication)

3.5.1. Thread Synchronization (barrier)

To wait for all threads to arrive at a given point in the program:

MPI_BARRIER(MPI_COMM_WORLD)

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 42/76

3.5.2. General diffusion (broadcast)

To distribute information from the thread source to all other threads, one can use:

MPI_BCAST (data, size, type, source, MPI_COMM_WORLD)

This instruction must be executed by all threads (i.e., it is used to send-receive).

Figure 3.4: General diffusion: MPI_BCAST

Example :

# include<stdio.h>

# include<mpi.h>
int main(int argc, char *argv[])

{
int range, value;
/* initialization */
MPI_Init(&argc,&argv);
MPI_Comm_rank(MPI_COMM_WORLD,&rank);

send the message

if (rank==2)
{
valeur=rang+1000;

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 43/76

MPI_BCAST(value, 1, MPI_INT, 2, MPI_COMM_WORLD);

}
printf(" Hello, processor %d, I received %d from processor 2 \n", rank, value);

MPI_Finalize();
}

Execution:

mpirun -np 4 bcast

Hi, processor 2, I received 1002 from processor 2

Hi, processor 0, I received 1002 from processor 2
Hi, processor 1, I received 1002 from processor 2
Hi, processor 3, I received 1002 from processor 2

3.5.3. Selective diffusion (scatter)

To split information held by the thread source and distribute its parts to others
threads, we can use:

MPI_scatter(data_to_send, size_to_send, type_to_send, data_to_recv, size_to_recv, &

type_to_recv, source, MPI_COMM_WORLD

where data_to_send is the information to be distributed and size_to_send is the size of the chunks to be sent to each

threads. These pieces are placed by each thread in data_to_recv, which has a size of size_to_recv.
type_to_send and type_to_recv describe the types of messages. If type_to_send = type_to_recv, then size_to_send

= size_to_recv.

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 44/76

Figure 3.5: Selective diffusion: MPI_SCATTER()

3.5.4. Gather the fragments of information

The opposite operation consists of gathering the fragments held by each thread to
give the thread the complete information:

MPI_gather(data_to_send, size_to_send, type_to_send, data_to_recv, size_to_recv, &

type_to_recv, source, MPI_COMM_WORLD

where data_to_send is the piece of information contained by each thread, size_to_send is its size,
data_to_recvla variable qui contiendra tous les morceaux,size_to_recvla taille des morceaux reçus.
If type_to_send = type_to_recv, then size_to_send = size_to_recv.

Figure 3.6: Collection: MPI_GATHER()

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 45/76

3.5.5. Gather information fragments at each thread (allgather)

To gather the fragments of information in each thread, one can use:

MPI_ALLGATHER(data_to_send, size_to_send, type_to_send, data_to_recv, &

size_to_recv, type_to_recv, MPI_COMM_WORLD

Figure 3.7: General Collection: MPI-ALLGATHER()

3.5.6. Redistributing information fragments among threads (all_to_all)

To give each thread i the i-th part of each fragment, we can use this sub-
routine

MPI_all_to_all(data_to_send, size_to_send, type_to_send, &

data_to_recv, size_to_recv, type_to_recv, &

MPI_COMM_WORLD)

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithms and parallel programming Page 46/76

Figure 3.8: Cross exchanges: MPI_ALLTOALL()

3.6. Reduction Operations

A reduction is an operation applied to a set of elements to obtain a single one.
value. Typical examples are the sum of the elements of a vector SUM(A(:)) or the search
of the maximum value element in a vector MAX(V( :)).

3.6.1. Reduction operations with results communicated to a single thread (reduce)

It is possible to perform certain operations on variables distributed among the different

threads. In order for the result of this operation to be communicated to the thread source, this can be used
subroutine:

MPI_REDUCE ( data_to_send, data_to_recv, size, type, &

operation, source, MPI_COMM_WORLD

where data_to_send is the information contained by each thread on which the operation must be
executed. The result appears in the variable data_to_recv from the source thread.
The main predefined reduction operations (there are also other logical operations)
are summarized in the table below.

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 47/76

Figure 3.9 presents the example of a sum of the elements.

Figure 2.9: Distributed reduction (sum)

3.6.2. Reduction operations with results communicated to all threads (allreduce)

To ensure that each thread receives the result of the operation, we can use:

MPI_allreduce ( data_to_send, data_to_recv, size, type, operation, MPI_COMM_WORLD)

3.6.3 Reduction operations with partial results communicated to the various threads (scan)

With the subroutine scan, each thread receives the result of the operation performed on its
element and that of the threads that precede it.

MPI_scan ( data_to_send, data_to_recv, size, type, operation, MPI_COMM_WORLD)

3.6.4. Example: calculation of the trace of a matrix

Calculation of the trace of a square matrix A

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 48/76

Reminder: the trace of a matrix is the sum of the elements of its diagonal (matrix
necessarily square)

Immediately, it is easy to see that the problem can be parallelized by calculating the sum
diagonal elements on multiple processors then using a reduction to calculate
the global trace

#include <stdio.h>

#include <mpi.h>

void main(int argc, char ** argv) {

int me, np, root=0;

int N; /* It is assumed that N = m*np */

double A[N][N];

double buffer[N], diag[N];

double traceA, trace_loc;

MPI_Init(&argc, &argv);

MPI_Comm_rank(MPI_COMM_WORLD, &me);

MPI_Comm_size(MPI_COMM_WORLD, &np);

tranche = N/np;

/* Initialization of A done on 0 */

/* … */

/* We buffer the diagonal elements from the master process */

if (me == 0) {

for (i=root; i<N; i++)

buffer[i] = A[i][i];

The scatter operation allows distributing the buffered diagonal among the processes.

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 49/76

MPI_Scatter(buffer, chunk, MPI_DOUBLE, diag, chunk, MPI_DOUBLE, MPI_COMM_WORLD);

/* We calculate the local trace on each processor */

trace_loc = 0;

for (i = 0; i < tranche; i++)

trace_loc += diag[i];

We can then calculate the global sum.

MPI_Reduce(&trace_loc, &traceA, 1, MPI_DOUBLE, MPI_SUM, root, MPI_COMM_WORLD);

if (me == root)

The trace of A is: %f

MPI_Finalize();

3.7. MPI-2 Extensions

The MPI-2 standard introduces some new features to address certain gaps observed.
allows among other things, the dynamic management of the number of processors.

For the use of MPI under Windows, it is recommended to use MPICH. This
installation requires including certain things in PATH and copying certain files into the
compiler's lib directory used.

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 50/76

Chapter 4

Scientific libraries for parallel computing

4.1. Introduction

If it is long and difficult to write generic subprograms for numerical analysis, which
the more efficient they are, the difficulty is multiplied if it concerns doing it for machines with memory
repartition. Here too, we have every interest in checking beforehand if it does not exist in a library or
library.
The major benefit of using libraries (aside from the saved work!) comes from this
that allow for combining portability and performance - except in the particular case of non
portability of certain parts of the manufacturers' libraries.
They indeed account for a wide range of factors, almost outside
of reaching by non-specialists:
• independence regarding the type of data (simple or double precision real?, real or
complexes ?)
•independence regarding data representation (symmetric matrices, bands,
hollows ?) ;
the choice of the best numerical algorithm;
the verification of the numerical stability of the algorithm;
optimization based on the architecture of the target machine;
Optimization based on the case to be handled (a matrix product is programmed differently)
according to the ratio between the number of rows and columns of these.

We can use the following simple classification:

1. the 'portable' libraries:
"portables" means here "available on most platforms";
•from the public domain: BLAS, LAPACK, ScaLAPACK, ARPACK, FFTW, PETSc, etc.;
•commercial: IMSL and NAG (but of course, they need to be purchased...).
2. the libraries provided by the manufacturers:
All manufacturers of scientific computers have developed their own

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 51/76

library ((P)ESSL at IBM, SSL2VP(P) at Fujitsu, ASL and MathKeisan at NEC, SciLib
at Cray, etc.) ;
their advantage is that they have (in principle!) optimal performance for the
machines concerned;
However, they are not portable.

Note that several of the libraries presented in this chapter are not accessible, or
mostly accessible, whether in C or Fortran. It will therefore be necessary for some
programmers to develop the expertise to mix compiled objects in C and others
compiled in Fortran.

4.2. PBLAS

4.2.1. BLAS

Started in 1978, BLAS (Basic Linear Algebra Subroutines) is a library for performing
elementary operations of linear algebra but in a relatively optimized way. Several others
libraries and font references. The BLAS_LEVEL_1, BLAS_LEVEL_2, and BLAS_LEVEL_3 perform
respectively of vector-vector, vector-matrix, and matrix-matrix operations.

4.2.2. PBLAS

PBLAS (Parallel BLAS) (Parallel Basic Linear Algebra Subprograms) defined and implemented in the
framework of the ScaLAPACK project (during the second major modification of this library, but which has
gave rise to the first public version), in analogy with what was done for LAPACK, which did
a wide use of BLAS.
Provides on distributed memory machines everything (or almost everything) that BLAS provides
1, 2 and 3 on shared memory machines.
Interface as close as possible to that of BLAS. PBLAS uses BLACS for the
communications.

4.3. ScaLAPACK

4.3.1. BLACS

BLACS (Basic Linear Algebra Communication Subroutines) is a library of

communication allowing, on a predefined grid of processes, to exchange blocks of matrices
between these processes, to disseminate them globally and to calculate reductions on them.

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithms and parallel programming Page 52/76

Written in C, BLACS is often based on MPI, but not necessarily (on IBM, LAPI, which
is the native communication layer on these machines). The call syntax for BLACS remains
identical from one system to another (hence its relevance).

4.3.2. LAPACK

LAPACK (Linear Algebra PACKage) allows solving problems involving

full or band matrices (linear equations, least squares minimization, minimization by
generalized least squares, standard eigenvalue problems, eigenvalue decompositions
singular, generalized singular value problems). Therefore, it does not apply to matrices
drains.

4.3.3. ScaLAPACK

Project started in 1989 under the responsibility of Jack Dongarra (University of Tennessee and
Oak Ridge Laboratory.
The ScaLAPACK project (Scalable Linear Algebra PACKage) itself is actually divided
today in four components:
1. the ScaLAPACK library: linear algebra for dense matrices;
2. the PARPACK library (Parallel ARPACK): searching for certain eigenvalues on very
large matrices
3. the CAPSS library (CArtesian Parallel Sparse Solver): solving linear systems on
symmetric positive definite sparse matrices, by direct method;
4. the PARPRE library (PARallel PREconditioners): a set of preconditioners for the
handling of any sparse matrices.
Since version 1.0 from February 95, which was the first public version, it is based on the
PBLAS and BLACS libraries.
The main areas addressed are:
1. resolution of linear systems and factorization (LU, Cholesky, QR, etc.);
2. matrix inversion;
3. systems with eigenvalues.
Project launched in late 2004 (through new funding granted by the NSF in the United States), for
develop a new version of ScaLAPACK (and LAPACK), integrating the advancements
algorithmic in recent years

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithms and parallel programming Page 53/76

4.4. Super_LU_DIST

4.4.1. Super_LU

Direct resolution (multi-frontal elimination) of a system of linear equations.

4.4.2. Super_LU_DIST

Direct resolution (multi-front Gaussian elimination) of systems of linear equations on

distributed memory machines.

4.5. PETSc

Developed by the Argonne National Laboratory, PETSc (Portable, Extensible Toolkit for
Scientific Computation) is a library made up of a set of procedures that allows
solve both sequentially and in parallel partial differential equations and problems
linear algebra (linear and nonlinear equations) using iterative numerical methods based on
on Krylov subspaces. PETSc uses MPI for inter-process communications.
Portable across various environments including those of Cray, HP, IBM, NEC, SGI, Sun, etc. It can be
used directly by Fortran, C or C++ programs.

4.6. P_ARPACK

4.6.1. ARPACK

ARPACK (ARnoldi PACKage) is a library that allows solving problems in

eigenvalues by the Arnoldi method. Unlike Lanczos, this method supports
non-symmetric matrices or non-Hermitian in the case of complex numbers.

4.6.2. P_ARPACK

P_ARPACK (Parallel ARnoldi PACKage) does the same thing as ARPACK but in execution
parallel.

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithms and parallel programming Page 54/76

Figure 4.1: Some libraries

4.7. Practical implementation of PETSc

4.7.1. Structure of PETSc

Figure 7.2: Structure of PETSc

•Vectors (Vec): initialization and basic operations on vectors (addition, scalar product,
etc.)
Matrices (Mat): initialization and basic operations on sparse or dense matrices
(factorizations, transposition, etc.)
Simplified linear equation solvers (SLES), an overlay of iterative methods

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 55/76

in the Krylov space and preconditioners

Krylov solvers (KSP): iterative methods in the Krylov space, with or without
preconditioner
•The preconditioners (PC): useful for iterative methods,
Nonlinear Equation Solvers (SNES)
•The rest (Index Set, Distributed Array, Draw, Grid, ...).

The compilation will be preprocessed to substitute the generic types of PETSc (Scalar,
Vec, Mat, ...) by the appropriate structures and descriptors.

4.7.2. Example of matrix initialization

#include "mat.h"

int main(int argc, char **argv)

{
Mat C;
int i, n = 5, midx[3], nidx[2], ierr, flg;
Scalar v[6];

PetscInitialize(&argc,&argv,(char *)0,PETSC_NULL);
ierr = OptionsGetInt(PETSC_NULL,"-n",&n,&flg);
Creation of a general sparse matrix
ierr = MatCreate(PETSC_COMM_WORLD, n, n, &C);

ierr = OptionsHasName(PETSC_NULL,"-column_oriented",&flg);
if (flg) {ierr = MatSetOption(C,MAT_COLUMN_ORIENTED);
for ( i=0; i<6; i++ ) v[i] = (double) i;
midx[0] = 0; midx[1] = 2; midx[2] = 3;
nidx[0] = 1; nidx[1] = 3;
ierr = MatSetValues(C, 3, midx, 2, nidx, v, ADD_VALUES);
ierr = MatAssemblyBegin(C, MAT_FINAL_ASSEMBLY);
ierr = MatAssemblyEnd(C, MAT_FINAL_ASSEMBLY);

ierr = MatView(C, VIEWER_STDOUT_WORLD);

ierr = MatDestroy(C);
PetscFinalize();

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithms and parallel programming Page 56/76

return 0;
}

Figure 4.3: Example of initialization

Some explanations about the role of certain lines:

OptionsGetInt: allows extracting the size of the matrix from the command line.
OptionsHasName / MatSetOption: change the default behavior of the filling of the
matrix
MatSetValues :
i. C : matrix to be initialized
ii. 3: number of row indices to initialize
iii. midx: row indices [0,2,3]
iv. 2: number of column index to initialize
v. nidx: column indices [1,3]
vi. v : vector of values corresponding to the indices above
MatView: display of the matrix C, line by line in the form (column number value)

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithm and parallel programming Page 57/76

Chapter 5

Grid computing
5.1. Introduction

For several years, Distributed Computing and the associated technologies have been in a
constant technological and economic evolution. Technologies are becoming increasingly mature and
sophisticated. Computing and storage servers see their quality ratio
price constantly increasing by incorporating new technological and manufacturing innovations.
The same observation can be applied to network technologies and bandwidth.
offer that is becoming unlimited from an applicative point of view.
The response to these changes is to move to a distributed computing model allowing
to fully exploit the resources and capabilities offered. This environment will provide a service and
uniform and economically viable access to infrastructure resources.
This evolution is known as 'Grid Computing' or 'grid computing'.
The term 'The Grid' or 'computing grid' was first introduced in the United States.
during the 1990s to describe a distributed computing infrastructure used in projects of
scientific and industrial research.
In one of the earliest documents dealing with grid computing concepts, researchers attempt
to provide a detailed definition of the objectives, structure, and architecture of the computing grids.
Six fundamental questions are established that anyone involved in design must consider.
development or the use of calculation grids may arise:
Why do we need calculation grids?
What types of applications will benefit from computing grids?
Who will use the calculation grids?
How will the calculation grids be used?
What are the components involved in the design of calculation grids?
What are the obstacles to overcome for the calculation grids to become
omnipresent?

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 58/76

The concept of a calculation grid is greatly inspired by the power grid.

by the early 1900s, electricity generation was already technologically possible and
new equipment using electrical power had appeared. However, the fact
that each user operates their own electricity generator was a major obstacle to adoption
this technology. Thus the real revolution was the construction of the electrical grid and networks of
transmission and associated distribution. Electricity has thus become universally available.
It is this universal and economically viable (inexpensive) availability that has allowed the
industries to adopt this technology and to evolve and develop through it.
By analogy to this electricity grid, the notion of computational grid is
defined as: a material and software infrastructure providing reliable access
(dependable), consistent, pervasive and cheap
(inexpensive) has processing and computing capabilities.
We are talking about infrastructure because a grid will have to provide resources (compute, storage...) to.
large scale. This requires a significant amount of material that will constitute the resources and
ensure their interconnection and a significant amount of software to properly control and supervise this
hardware set.
The necessity of a reliable service is fundamental. Users of such an infrastructure
expect to receive a predictable, continuous, and efficient service. Otherwise, development and
The use of applications using this infrastructure will not occur.
Coherence suggests, just like in the electricity grid, the presence of standard services,
accessible via standard interfaces and operating according to standard parameters.
Un taux de pénétration élevé permet de garantir que les services seront facilement accessibles
by a large population.
Ultimately, the cheap aspect is very important from an economic viability standpoint.

In [The Grid, Blueprint], a computing grid is an environment of systems

of heterogeneous architectures and operating systems whose access is provided to the user in a form
unified, by a software called middleware.

The grids are currently the subject of numerous projects, implemented by various
architectures. There is no single definition that is unanimously recognized.

However, everyone agrees that all these architectures have a point

common: the sharing of resources. But, it is not because a system ensures sharing of
resources that it is a grid.

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 59/76

As for the features of these architectures, programming models

there is no consensus on what they produce, or even on how to define the models that validate them.

5.2. Reasons for Grid Computing

It is important to know what advantages a calculation grid can offer that the
infrastructures and current technologies are not able to ensure. We then expose
some of the reasons that may lead to deploying a calculation grid.

5.2.1. Exploit underutilized resources

Studies show that personal computers and workstations are inactive

most of the time. The usage rate varies between 30% (academic and industrial environments) and 5%
(consumer machines).
The calculation grids will allow the use of the processor cycles during which the
machines are inactive in order to run an application requiring computing power
important and that the machines dedicated to it are unable to ensure.
Processor cycles are not the only underutilized resource; often the capabilities of
stockages are too. Thus, it is possible for a grid to aggregate all these resources in order to
sharing between different users (we then talk about a 'data grid' or Data Grid). A
Another consequence of such use is the possibility of load sharing between the
different resources of a grid.

5.2.2. Provide significant parallel computing capacity

The ability to provide significant parallel processing capacity constitutes a

important characteristic of calculation grids.
In addition to the academic field, the industrial environment will greatly benefit from such a
capability: bioinformatics, oil exploration, film industry, etc. Indeed the
applications are written in a way to be able to parallel exploit resources (clusters,
multiprocessor machines ...).
Calculation grids can similarly provide resources whose use
can be done in parallel.

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 60/76

5.2.3. Better use of certain resources

By sharing resources, a grid can provide access to special resources such as

specific equipment (electron microscope, robotic arm ...) or software whose price
the license is high. Thus, these resources exposed to all users will be better utilized and
shared and thus we will avoid having to install new equipment or buy new ones.
licenses.

5.2.4. Reliability and availability of services

Due to the fact that the resources federated by a computing grid are geographically dispersed
and available in significant quantities ensures the continuity of service if certain resources
become inaccessible. The grid control and management software will be able to
submit the calculation request to other resources.

5.3. Application areas of Grid computing

The main applications of computing grids will be in the following areas:

5.3.1. Distributed Intensive Computing

A computing grid will be able to aggregate a significant amount of resources in order to provide the
computing power needed for many applications and that even supercomputers
more modern ones cannot provide.
Depending on the nature and extent of the grid, the aggregated resources may range from all the
workstations of a university to all the supercomputers of research organizations in a country.
As examples of applications, we can mention distributed simulation in the
meteorology, cosmology, and aeronautics...

5.3.2. High-speed calculation

A calculation grid will be used to schedule a large amount in parallel.

independent tasks from each other.
As examples of applications, we can mention the search for cryptographic keys, the
molecule simulations and genome analysis ...

5.3.3. Calculation on request

A calculation grid can provide the resources to meet short-term demands.

of an application and that local resources are not able to provide (processor cycles,
storage ...)

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 61/76

The main challenge for designers of such grids is the dynamic and random nature of
requests made by users that can constitute a large population.

5.3.4. Collaborative Calculation

This class of applications includes applications for interaction between humans in

real-time simulation environments (design and interaction with a new engine
of an airplane, design of an urban plan ...).

5.3.5. Intensive data processing

In such applications, a computing grid can absorb and store significant amounts.
generated information.
As an example of applications, we can mention the production of a map of
the universe, long-term weather forecasting, quantum simulations ...

5.4. General Architecture of Grid Computing

We present in this section a set of design principles and criteria.

common principles used in the definition and development of grid architectures.

5.4.1. The characteristics of Grid computing

The calculation grids have four main characteristics:

Existence of several administrative domains: resources are geographically
distributed and belong to different organizations, each having its own management policies
and security. Therefore, it is essential to adhere to the policies of each of these organizations.
•Heterogeneity of resources: the resources in a grid are heterogeneous in nature.
terms of hardware and software.
Scalability: a grid may consist of a few dozen resources.
to millions or even tens of millions. This poses new constraints on applications and
resource management algorithms.
•Dynamic nature of resources: in the grids this dynamic nature is the rule and not
not the exception. This imposes constraints on applications such as adapting to change
dynamique du nombre de ressources, la tolérance aux pannes et aux délais …

5.4.2. Distribution of resources in Grid computing

A grid is a collection of resources that the user can benefit from. The resources
are generally divided into several types:

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 62/76

1. Processor cycles: there are several ways to exploit unused processor cycles of
machines participating in the grid. The first is to run an application on a machine
remote instead of the local processor. The second is to use an application designed to run its
different parts in parallel on different processors. The third is to run multiple
occurrences of the same application on different machines in order to process different data more
quickly.
2. Storage capacity: the second type of resources available in a grid is capacity
storage. Indeed, the machines participating in the grid will be able to provide a part of the capacity of
storage necessary for the functioning of the grid. The storage capacities in a grid may
to be used in order to increase the offered capacity, performance, sharing efficiency, and reliability.
3. Special equipment and high-license software: some software whose license prices
will be present in only a few copies in the grid. This grid will allow
so by exposing them to many users, a better use of these software. It is a matter of
even for certain special equipment such as electron microscopes and devices
medical ...

5.4.3. Steps for building a Grid computing

Several steps make up the process of building a grid:

Integration of different hardware and software components into a global resource through
the network.
The implementation of middleware providing a transparent and consistent view of this resource.
The development of tools for controlling and managing the infrastructure and
applications.
The development of applications using this infrastructure.

5.4.4. Architecture of a Grid computing

Although each project has its own architecture, a general architecture is important for
explain some fundamental concepts of grids.

Figure 5.1 below illustrates such an architecture.

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithms and parallel programming Page 63/76

Figure 5.1: General architecture of a Grid computing

At the core of the layered architecture, we have the resources themselves.

interconnected through local and long-distance networks. This hardware infrastructure
(fabric) includes notably PCs, workstations, computing clusters,
storage equipment, databases, special equipment ...
The resources of a grid can vary from the simplest (machines of the same architecture, same
operating system, homogeneous interconnection network) to the most complicated (different
machine architectures, multiple operating systems, geographical extent, different
security policies, several administrators ...
The second layer provides the necessary security mechanisms for protection.
resources. In the calculation grids, security is a much greater concern than in the
traditional distributed computing environments. The significant number of resources and their
Geographical extent is an important factor. Thus, it is essential to clearly identify the
resources to protect and the levels of protection needed to apply.
Among the protective measures are those normally used in networks (firewalls,
intrusion detection ...) as well as those specific to distributed environments and grids
(authentication, authorization, single sign-on ...).
The third layer provides the middleware necessary for management of
resources, access coordination, task scheduling... This unifies access to
heterogeneous IT resources. It is positioned between the existing operating systems (no
perturbation of these systems) and the user. It masks the heterogeneity of the various installed systems.
and provides a set of routines (commands and programming libraries) independent of
system. These commands and functions allow, for example, to execute an application on a

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 64/76

machine with a resource description language (amount of memory required, CPU time, ...)
.) independent of the machine used.

There are many middleware or software components that can provide them.
features known as Unicore (German middleware), LEGION (American), JINI
our Middleware Sun, CORBA (one of the concepts of the OMG - Object Management Group), DCOM, SOAP or

.NET. But the one everyone is talking about today is Globus, the only complete, open middleware.
source and free.

We briefly explain below the main functions provided by these middleware:

•Scheduling: a scheduler will have to find the most suitable machine
suitable for running the tasks assigned to it. Schedulers can range from the most
simple (round-robin allocation) to more complex (priority-based scheduling ...).
Schedulers respond to the load of the grid. They determine the load rate of each
resource to properly schedule the upcoming tasks. They can be organized in a hierarchy with
some interacting directly with the resources, and others (meta-schedulers) interacting
with the intermediate schedulers. They can also oversee the progress of a task until
submit it again if it is abruptly interrupted and complete it
prematurely if it is in a loop finally of execution.
Reservation: it is possible in the calculation grids to reserve the resources in advance and
this in order to guarantee a certain quality of service and to meet certain deadlines. For this reason
the middleware must provide a reservation system allowing users to express their
resource needs and to make the reservation.
Information and Directory Services: a grid is a
environment where the number and the resource load are dynamic. An objective during the
The design of a grid is to make resources easily accessible to all processes. It is
therefore necessary to provide mechanisms for recording and discovering these resources and
to identify their state.
Naming Service: As in any distributed system, a grid must allow
to reference its resources in a standard and uniform way.
A calculation grid must operate with a wide range of hardware or software technologies.
Just as web users do not care whether web servers run on a
x86 or Sparc machine or whether the operating system is Unix or Windows, the users of a
grids do not want to worry about the material and software details of the infrastructure. A

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 65/76

The ideal grid environment will thus provide transparent access to resources by hiding all the
physical differences.
The fourth layer includes all the tools and paradigms that can assist developers.
to design and write applications that can run on the grid. It particularly includes
compilers, libraries, parallel application design tools as well as
programming interfaces or APIs (resource discovery and booking, security mechanisms,
storage ...) that application developers will be able to use.
The last layer groups the applications themselves, which are of a varied nature:
scientific, medical, financial, engineering projects ...

5.5. Different topologies of Grid computing

By their nature, grids can be viewed from two perspectives:

The services rendered

Shared resources

But we can also classify them according to other criteria:

Calculation grids, data grids

Scientific grids, business grids
Internet grids, Intranet, P2P

From a topological point of view, grids are of three types according to the increasing order of extent.
geographical and complexity: Intragrids, Extragrids and
Intergrilles (Intergrids).

5.5.1. Intragrille (by analogy with Intranet)

The simplest of the grids is the intragrid, composed of a relatively simple set of
resources and services belonging to a single organization.
The main features of such a grid are the presence of an interconnection network.
high-performance and high-speed, in a unique security domain controlled by the administrators of
the organization and a relatively static and homogeneous set of resources. A company can
to be led to build an intragrid to increase the computing power of its teams
research and development while maintaining a low level of investment in terms of
new infrastructures (for example, AMD during the design phase of its processors
K6 and K7 [2]).

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 66/76

5.5.2. Extragrille (by analogy with Extranet)

An extragrid extends the model by aggregating multiple intragrids. The main

Characteristics of such a grid include the presence of a high and low heterogeneous interconnection network.
bandwidth (LAN/WAN), from several distinct security domains, and a more or less
resource dynamics.
An example of use is during alliances and Business-to-Business (B2B) exchanges between
partner companies.

5.5.3. Intergrid (by analogy with the Internet)

An intergrid consists of aggregating the grids of multiple organizations into a single grid.
the main features of such a grid are the presence of a very interconnected network
heterogeneous high and low bandwidth (LAN / WAN), from several distinct security domains and sometimes
different and even contradictory security policies, and a very dynamic set of
resources.
Intergrids will often be implemented during large industrial projects (design
of an aircraft by an aeronautics consortium for example) or scientific (protein modeling)
where several organizations will be invited to participate.
With the birth of the concept of computing grid, the concept of virtual organization
Organization) appears. Users will be able to be grouped according to their different interests, in
such organizations, each with their own policy. Each virtual organization will implement the
providing these users with a set of resources in the form of a grid.

Figure 5.2: Different grid topologies

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithms and parallel programming Page 67/76

It should be noted that the notion of intergrid is today tending to be confused with that of Global

computing Internet computing.

5.6. Application design for Grid

Although grids offer several advantages, only certain types of applications will be able to benefit from them.

benefit. Applications designed to run on multiple processors in parallel

will benefit the most from the calculation grids.
The most important question is whether an application can be written in the form
algorithms executing in parallel. Indeed, some algorithms execute in a way
sequential and will not be able to benefit from the parallel computing power of grids.
The work of the application designer will therefore consist of determining what the parts are
of the application likely to run in parallel and implement the corresponding algorithms
to make the application ready to run on a grid.
For certain applications that are difficult to break down into parallel sub-applications, a grid
is useful when one wants to run multiple instances of the application in order to find a
optimal result, for example the ideal trajectory of a space shuttle.
Another way to make applications less sequential is to break them down into sub
applications and trying to eliminate the dependency between these sub-parts by performing calculations
redundant: if one part requires as input the results of the previous part and if the entire
the results of this last one are of reasonable size, we can run several instances of the
second part in parallel for each of the elements of the set and to eliminate the bad ones.
instances when the result of the first part is known. This form of speculative execution
(speculative execution) is well known to microprocessor architecture designers. Even
when the set of possible outcomes is large or infinite, it is possible to conceive of
heuristics for selecting a finite subset of the most probable results to process in
parallel. It may not produce an optimal final result, but according to the technical constraints and
The economic results of the application will be more or less acceptable.
Decisions will also need to be made during the design of the application regarding
concerning the data to be processed. Indeed, by decomposing an application, we must take into
considering the necessity of sending data through the network to a subpart of the application
remote turning. The volume of this data and its transfer time become parameters.
important for the overall performance of the application.
When the volume of this data is large, it becomes very inefficient to send it to
through the network. Thus, it becomes preferable to place the data as close as possible to the node.

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 68/76

performing the calculations. And when the same data is used by multiple nodes it becomes
it is necessary to replicate this data in several places on the grid. Therefore, one must arrange for
each node accesses the closest data. This illustrates the importance of the presence of a
service for locating this data.
Some data is static in nature, while others are dynamic. In the latter case, and if these
data is replicated in several places on the grid, the designer will have to consider the issue of the
update of the various replicas and the overall consistency of the data.
For certain types of data, it will be urgent to propagate any changes as quickly as possible.
possible for all replies. Sometimes it is not urgent and thus helps to improve the
global performance of the application in terms of execution time. The update and access
Simultaneous data raise issues of consistency of this data. For this, mechanisms
Appropriate locking and synchronization mechanisms must be used. It then becomes necessary
to avoid, to prevent, and to detect all well-known issues of deadlock and starvation in
distributed computing.
Finally, we mention that a single application can have several instances that
are executed in parallel in different places of the grid in order to minimize the effects of failures
that may occur. These different instances will need to coordinate in order not to modify the data.
in an incoherent manner and leave them in an erroneous state.

5.7. Applications Grid

5.7.1. The present of the Grid

Most current grid projects remain scientific projects. They are still the
needs for computing power or massive data processing that remain the motivations
first users. These arguments leave traditional companies completely indifferent.

Certain industrial sectors, such as energy (particularly the industry

nuclear) or pharmacy are the most receptive because numerical simulations have increased their
processing power or computing needs. Similar interest in biotechnology, the
chimie, l'aérospatial, le design micro-électronique, etc. Ou encore, dans le monde de la finance, la
The race for instantaneity also leads to the search for power (risk assessment or evaluation of
wallets).

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithms and parallel programming Page 69/76

5.7.2. Projects and applications

The pooling of computing resources has become accessible to the developer.

applications with the arrival of PVM (Parallel Virtual Machine), certain implementations of MPI
(Message Passing Interface) like MPICH, Condor (University of Wisconsin), Nemrod.

Several projects for creating calculation grids are underway and are benefiting from the support of
universities, research centers, and industrialists.
a) Europe
a.1) Community projects
Following the work of the pioneers from the United States of America and Europe, platforms of
Software development for distributed computing such as Globus, Condor, Unicore are available.
Europe has managed to set up a functional testing framework in which 20 participate.
European centers, in the context of the EDG (European DataGrid) project.

The goal of the EGEE project (Enabling Grids for eScience in Europe) is to integrate the grids
national, regional and current thematic priorities to create a European framework for research
European. This infrastructure will be connected with other grids globally, including between
other than that of the US NSF (National Science Foundation), thus contributing to the emergence
from a planetary grid.

This infrastructure will be built by carrying out two pilot projects, one in particle physics.
in high energies and the other in biomedical.

The first project is the Large Hadron Collider Computing Grid (LHCG), for which a grid
is necessary to process the 12 to 14 petabytes of annual data resulting either from experiments or
CERN simulations. The analysis will require the equivalent of 70,000 of the fastest processors.
Today... Its results are of interest to about 6000 scientists from universities and laboratories.
whole world.

The other project is Biomedical Grids, for which several communities collaborate to process
data from bioinformatics and the healthcare system.

a.2) French projects

GénoGRID: A grid for genomics

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 70/76

GenHomme aims to promote the enhancement of knowledge derived from

human genomics and to generate a project dynamic.
GLOP (Multidisciplinary Local Grid): a multidisciplinary local grid deployed between
the laboratories of the Cézeaux Campus in Clermont-Ferrand.
ACI GRID (Globalization of IT and Data Resources): the objective of ACI
(Coordinated Incentive Actions), is to energize and make operational, at a time
critique, the contribution of French research teams in the field of Grid
computing.
EDF: participates in a computing grid project called e-star that enables sharing.
of applications and software internally.
EADS: uses grid computing to carry out highly intensive simulations on one hand.
processing power consumers (design of an Airbus or an Ariane rocket) and
on the other hand to collaborate with the different entities of the group that are spread across
Europe
CGG: CGG (General Geophysics Company) is a French company specialized
in oil exploration. It uses Grid computing on a fleet of 16,000 PCs in
cluster to conduct seismic studies, utilizing data volumes of
l'ordre du téraoctet.
CEA: The CEA (French Atomic Energy Commission) develops computing projects
distributed for its research and development activities that require resources
important computer science.
OPEN PLAST: The OPEN PLAST project is a project for the industrial application of
simulation and computing grid technologies, focused on simulation needs of
plastic processing companies and focused in a first phase on the simulation of the process
injection of thermoplastic materials.
Decrypton: AFM, IBM, and CNRS have decided to collaborate to develop a platform
technological framework allowing for a duration of three years to carry out operations of
shared computing ("grid computing").

North America

b.1) United States

TeraGRID: is the result of many years of effort to deploy the largest architecture
worldwide distributed for scientific research. TeraGrid is expected to represent a power of

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 71/76

calculation of 20 teraflops, with the ability to manage and store nearly a petabyte of data, and
a high-resolution visualization environment.
Access Grid: This grid was developed by the Argonne National Laboratory.

Earth System Grid II: It is created for the purpose of being able to carry out climate simulations.
Search for ExtraTerrestrial Intelligence (SETI@home): SETI@home is certainly
the most popular grid application. It concerns the search for extraterrestrial intelligence.
This project uses computers connected to the Internet to analyze data from
of a radio telescope.
[Link]: LeGrid MP Global @ [Link] has served, among other things, for the Research project for
the Cancer sponsored by Intel and the University of Oxford and that of Anthrax Research
sponsored by Intel and Microsoft
•Grid Physics Network, Particle Physics Daa Grid, NASA Information Power Grid, …

b.2) Canada

Several grids are under construction, including:

WestGrid: Grid created to satisfy seven Canadian institutions.

c) Asia

c.1) Japan

•Naregi: The Japanese government, commercial entities, and universities have unveiled the
Naregi project (National Research Grid Initiative) which aims to create a supercomputer at
starting from computers spread throughout the country. This meta-computer is expected to reach a capability of
100 Tflops in 2007.
BioGrid: It is a project involving Japan and China, between Osaka University and the Institute
of Microbiology of the Academy of Sciences of China.

c.2) China

•CNGrid (China National Grid Project): It is a key project of the National High-Tech program.
R&D (863 projects).

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 72/76

China Education and Research Grid: The project began in 2003 with six universities. Once
I finished, the grid will serve over 200,000 students and university members spread over about a
hundred of sites.

Australia

Nimrod: The initiator of these projects is Rajkumar Buyya, who completed a thesis to obtain a PhD.
whose dissertation title is: "Economic-based Distributed Resource Management and
Scheduling for Grid Computing in April 2002.

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithms and parallel programming Page 73/76

Some references

Arnaud LEGRAND, "Heterogeneous Parallel Algorithmic and Scheduling Techniques:"

static and dynamic approaches", Thesis, December 2003
Thierry GARCIA, "Parallel Text Algorithmics: from the Systolic Model to the CGM Model"
Thesis, November 2003
[3] Alexandre Mayer, « Techniques de programmation parallèle », Mai 2004
Pierre Manneback, "Parallel and Distributed Computing", June 2005
The Anatomy of the Grid: Enabling Scalable Virtual
Organizations, International Journal of Supercomputer Applications, volume 15, number 3, 2001.

[6] François Colombier, "The Grid: State of Affairs", 2003

[7] X, "Calculation Grids: State of the Art", June 2003
Reference site for MPI [Link]
Jalel Chergui et al., "MPI-1", April 2004
MPI Reminder in C
[Link]
[11] Jalel Chergui et al., « Les bibliothèques scientifiques parallèles », Janvier 2005
[Link]
Zahir, 'Scientific Libraries'
[Link]
Reference site of PETSC,
[Link]
Introduction to ScaLAPACK
[Link]
Saint-Jean DJUNGU, "Semantic Grid: State of the Art", March 2005
[16] Eric Goubault, « Parallélisme et Distribution », Commissariat à l’énergie atomique, 2005
[17] Eric Garcia, « Initiation au parallélisme », Cours de DESS, LIFC, 2006
Benoît Semelin, "Parallel programming for scientific computing", Doctoral School
astrophysics of Île de France, 2005
M. J. Flynn. Some computer organization and their effectiveness. IEEE Transactions on Computers, C-
21, pages 948 -960, 1972.
A. J. Van der Steen and J. Dongarra. Overview of recent supercomputers.

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithms and parallel programming Page 74/76

Table of contents

Course objectives
Prerequisites....................................................................................................................................................1
Course Summary....................................................................................................................................1
Chapter 1
Generalities on parallelism..................................................................................................................2
1.1. Motivation and definition of a distributed system
1.1.1. Motivation
1.1.2. Definition of a distributed system...........................................................................................3
1.2. What is parallelism? ......................................................................................................3
1.3. Definition of an algorithm.............................................................................................................4
1.4. Importance of parallelism............................................................................................................5
1.5. Parallel programming models.............................................................................................5
1.6. Key concepts of parallelism........................................................................................................9
1.6.1. User time (wallclock time) and computation time (cpu time) ......................................9
1.6.2. Load balancing .............................................................................10
1.6.3. At what level to parallelize?...................................................................................................10
1.7. The dangers of parallelization ..........................................................................................11
1.8. The top500
Chapter 2................................................................................................................................................13
Parallel programming models......................................................................................................13
2.1. Introduction
2.2. Models of parallel machines .................................................................................................13
2.2.1. Principles of parallel machines
2.2.2. Classification of parallel machines..................................................................................17
2.2.3. Fine-grained models ...............................................................................................................19
2.2.4. Coarse grain models.............................................................................................................23
2.3. Steps for parallelizing a task...........................................................................................23
2.3.1. Helping the compiler to parallelize.......................................................................................25
2.3.2. Distributing the data to be processed.................................................................................................26
2.3.3. Parallelizing your program with OpenMP...........................................................................28
2.3.4. Parallelizing your program with MPI ..................................................................................29
2.4. Cost of modeling ...................................................................................................................30
2.4.1. Calculation of parallel complexity..........................................................................................30
2.4.2. Amdahl's Law....................................................................................................................31
2.5. Summary of Parallelism Models...........................................................................................32
Chapter 3................................................................................................................................................34
Parallel programming with MPI.........................................................................................................34
3.1 Introduction
3.2. Some concepts
3.2.1. Message exchange............................................................................................................34
3.2.2. The Master and the Slaves
3.2.3. Synchronous or asynchronous messages, blocking or non-blocking ...................................35
3.2.5. Risk of deadlock ..............................................................................................36
3.3. Basic example
3.4. Sending messages between two threads (point-to-point communication).....................................37
3.4.1 Basic Syntax.....................................................................................................................38

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 75/76

3.4.2. Types of messages

3.4.3. Sending modes ..........................................................................................38
3.4.4. Modes of reception..............................................................................................................39
3.4.5. Wait for or test the end of a communication
3.4.6. Example of sending and receiving.............................................................................................40
3.4.7. Wait or test multiple communications ......................................................................41
3.5. Sending messages between multiple threads (collective communication) ....................................41
3.5.1. Thread synchronization (barrier) ..................................................................................41
3.5.2. General broadcast.............................................................................................42
3.5.3. Selective diffusion (scatter) .................................................................................................43
3.5.4. Gather the fragments of information .......................................................... 44
3.5.5. Gather the fragments of information at each thread (allgather)......................45
3.5.6. Redistributing information fragments between threads (all_to_all) ..............................45
3.6.1. Reduction operations with results communicated to a single thread (reduce)....................46
3.6.2. Reduction operations with results communicated to all threads (allreduce) .............47
3.6.3 Reduction operations with partial results communicated to the different threads (scan)
.........................................................................................................................................................47
Scientific libraries for parallel computing ......................................................................................50
4.1. Introduction
4.2. PBLAS
4.2.1. BLAS
4.2.2. PBLAS ..................................................................................................................................51
4.3. ScaLAPACK
4.3.1. BLACS..................................................................................................................................51
4.3.2. LAPACK................................................................................................................................52
4.3.3. ScaLAPACK..........................................................................................................................52
4.4. Super_LU_DIST ..........................................................................................................................53
4.4.1. Super_LU
4.4.2. Super_LU_DIST
4.5. PETSc...........................................................................................................................................53
4.6. P_ARPACK
4.6.1. ARPACK ..............................................................................................................................53
4.6.2. P_ARPACK
4.7. Practical implementation of PETSc ............................................................................................... 54
4.7.1. Structure of PETSc
Figure 7.2: Structure of PETSc
4.7.2. Example of matrix initialization..................................................................................55
Grid computing
5.1. Introduction.................................................................................................................................57
5.2. Reasons for Grid Computing..........................................................................................................59
5.2.1. Exploit underutilized resources ..................................................................................59
5.2.2. Provide significant parallel computing capacity .............................................................59
5.2.3. Better use of certain resources ........................................................................60
5.2.4. Reliability and availability of services
5.3. Application areas of Grid computing .................................................................60
5.3.1. Distributed intensive computing .........................................................................60
5.3.2. High-speed computation.................................................................................................................60
5.3.3. Calculation on demand
5.3.4. Collaborative Calculation
5.3.5. Intensive data processing .............................................................................................61

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]
Algorithmics and parallel programming Page 76/76

5.4. General architecture of Grid computing

5.4.1. The characteristics of Grid computing ............................................................................61
5.4.2. Distribution of resources in a Grid computing ...................................................................61
5.4.3. Steps for building a Grid computing
5.4.4. Architecture of a Grid computing
5.5. Different topologies of Grid computing...................................................................................65
5.5.1. Intragrille (by analogy with Intranet)...................................................................................65
5.5.2. Extragrille (by analogy with Extranet).................................................................................66
5.5.3. Intergrid (by analogy with the Internet)...................................................................................66
5.6. Application Design for Grid...........................................................................................67
5.7. Applications Grid
5.7.1. The present of the Grid.................................................................................................................68
5.7.2. Projects and applications
Table of contents...................................................................................................................................74

Prof. Dr. Saint-Jean DJUNGU

Tél :+243 897232200 ; +243 818572245 email :sdjungu@[Link]