程序代写代做代考 python c/c++ flex compiler c++ Java Fortran Microsoft PowerPoint – MPI-1 [Compatibility Mode]

Microsoft PowerPoint – MPI-1 [Compatibility Mode]

1Computer Science, University of Warwick

Example of using Thread Class

public static void main(String[ ] args)
{

System.out.println(“Simple Thread Demonstration”);
System.out.println(” Extending Thread”);
for (int i = 0; i < 4; i++) { MyThread newThread = new MyThread( i ); newThread.start( ); } } } 2Computer Science, University of Warwick Synchronization of Java Threads  The previous examples shows independent, asynchronous threads (i.e., run at their own pace)  Independent threads can run asynchronously if they only use local (private) data  In many cases, threads i) share data, and/or ii) rely on the activities of other threads  They must synchronize to share data  Consider the following producer-consumer example 3Computer Science, University of Warwick Producer public class Producer extends Thread { private CubbyHole cubbyhole; public Producer (CubbyHole c) { cubbyhole = c; } public void run ( ) { for (int i = 0; i < 10; i++) { cubbyhole.put(i); try { sleep ((int) (Math.random( ) * 100)); } catch (InteruptedException e) { } } } }  Generates 0 <= i < 9  Stores it in a Cubbyhole  Sleeps for a while  Generates the next I public class CubbyHole { private int contents; public int get (int number) { … } public void put (int number, int value) { … } 4Computer Science, University of Warwick Consumer public class Consumer extends Thread { private CubbyHole cubbyhole; public Consumer (CubbyHole c) { cubbyhole = c; } public void run ( ) { int value = 0; for (int i = 0; i < 10; i++) { value = cubbyhole.get(); } } }  Consumes the integers from the Cubbyhole Object  As quickly as they become available 5Computer Science, University of Warwick Producer / Consumer Example  CubbyHole is the shared data  Ideally Consumer will get each value only once produced by Producer  If Producer runs faster than Consumer, Consumer #1 got: 3 Producer #1 put: 4 Producer #1 put: 5 Consumer #1 got: 5 Problem arises if Producer is quicker than Consumer Producer generates two numbers before Consumer consumes the first E.g. misses the number 4 6Computer Science, University of Warwick Producer / Consumer Example  If Producer is slower than Consumer we also have a problem  Consumer gets two same numbers before Producer generates a new number  E.g. gets the number 4 twice Producer #1 put: 4 Consumer #1 got: 4 Consumer #1 got: 4 Producer #1 put: 5  Example of a race condition – reading and writing shared data concurrently; success depends on timing  Example of critical section - Need synchronization 7Computer Science, University of Warwick Synchronization of Java Threads  The put and get in the CubbyHole code are the so called critical section (monitor region)  These should be marked as synchronized public class CubbyHole { private int contents; private boolean available = false; public synchronized int get () { … } public synchronized void put (int value) { … }  Running synchronized method locks class  Unlocked when method terminates 8Computer Science, University of Warwick Synchronization of Java Threads • So now we have mutual exclusion, but how do Producer and Consumer cooperate to address the race condition? • Consumer needs to wait until Producer has put new data, and Producer needs to notify Consumer after the data is put– and vice versa  put and get need to wait on and notify each other of their activities  available=false means the data has not been put  wait releases lock public synchronized int get { while (available == false) { try { // wait for producer to put value wait ( ); } catch (InterruptedException e) { } } available = false; // Notify Producer value has been retrieved notify ( ); return contents } 9Computer Science, University of Warwick Wait Releases Monitor 10Computer Science, University of Warwick Synchronization of Java Threads  So now we have mutual exclusion, but how do Producer and Consumer cooperate?  Consumer needs to wait until Producer has put something new, and Producer needs to notify Consumer after the data is put– and vice versa  i.e put and get need to wait on and notify each other of their activities  available=false means the data has not been put  wait releases lock  Loops until the new data is available  When consumer gets data, it does “notify” and Producer comes out of wait state and puts the next new data public synchronized int get { while (available == false) { try { // wait for producer to put value wait ( ); } catch (InterruptedException e) { } } available = false; // Notify Producer value has been retrieved notify ( ); return contents } 11Computer Science, University of Warwick Synchronization of Java Threads  So now we have locking, but how do Producer and Consumer cooperate?  Consumer needs to wait until Producer has put something, at which point Producer needs to notify Consumer – and vice versa  i.e put and get need to wait on and notify each other of their activities  available=true means the data has been put  Loops until Producer ready with new value  wait relinquishes lock  When Producer put the data, it does notify and consumer comes out of wait state and get() can collect value public synchronized void put(int value){ while (available == true) { try { // wait for consumer to get value wait ( ); } catch (InterruptedException e) { } } contents = values; available = true; // Notify Consumer that value has been sent notify ( ); } 12Computer Science, University of Warwick Synchronization of Java Threads  notify will allow one (rather than all) thread to be woken  notifyAll wakes up all threads waiting on the monitor in question  Awakened threads compete for lock (ownership of the monitor)  Those threads that don’t get the lock continue to wait 13Computer Science, University of Warwick Synchronization in Java (Monitor) • Java provide built-in thread synchronization ability (through monitors), which is part of the programming language • The compiler generate correct code to generate the monitor for each class/object and implement the monitor locks For more information, see: http://java.sun.com/docs/books/tutorial/essential/threads 14Computer Science, University of Warwick pthread_mutex_t my_mutex; /* declared in global area*/ void *Calc(void *); main(){ pthread_mutex_init(&my_mutex, NULL) /* before pthread_create*/ for(ith=0; ith MPI
specification > MPI implementation

19Computer Science, University of Warwick

OpenMP vs MPI

• MPI is used on distributed-memory systems

• OpenMP is used on shared-memory systems

• Both are explicit parallelism

• OpenMP is higher-level control
 Compiler can automatically parallelise the codes

when instructed

• MPI is lower-level control
 Data partition, allocation and communication are

conducted by programmers

20Computer Science, University of Warwick

A brief history of MPI

 Message-passing libraries developed for a number of
early distributed memory computers

 By 1993 there were many vendor specific
implementations

 By 1994 MPI-1 was proposed
 Emphasize message passing
 Has a static runtime environment

 By 1996 MPI-2 was finalized
 includes new features such as

o parallel I/O,
o dynamic process management
o remote memory operations

 2012 MPI-3 is formalized

21Computer Science, University of Warwick

The MPI programming model

 MPI standards –

 MPI-1, MPI-2, MPI-3

 Standard bindings – for C, C++ and Fortran.

 There are MPI bindings for Python, Java etc (non-

standard)

 We will stick to the C/C++ binding, for the lectures and

coursework.

22Computer Science, University of Warwick

MPI functions

• MPI is a complex system comprising of numerous
• functions with various parameters and variants

• Six of them are indispensable, but can write a large
number of useful programs already

• Other functions add other features, including flexibility

(datatype), robustness (non-blocking send/receive),

efficiency (ready-mode communication), modularity

(communicators, groups) or convenience (collective

operations, topology).

• In the lectures, we are going to cover most commonly

encountered functions

23Computer Science, University of Warwick

Intuitive Interfaces for sending
and receiving messages

• Send(data, destination), Receive(data_location, source)

 minimal interface

• Not enough in some situations, we also need

 Message matching – sender may send multiple messages to

the same receiver: add message_id at both send and receive

interfaces

 they become Send(data, destination, msg_id), receive(data,

source, msg_id)

 Message_id

 Is expressed using an integer, termed as message tag

 Can differentiate the messages from the same process

 Enable the messages to be processed in an ordered fashion

24Computer Science, University of Warwick

• Early stages:
 (address, length) for the send interface
 (address, max_length) for the receive interface

• They are not always good
 the data may not occupy contiguous memory locations
 Storing format for data may not be the same in

heterogeneous platform

• Enventually, a triple (address, count, datatype) is used to
express the data to be sent and (address, max_count,
datatype) for the data to be received
 Reflecting the fact that a message contains much more

structures than just a string of bits, For example, (vector_A,
300, MPI_REAL)

 Programmers can construct their own datatype

• Now, the interfaces become send(address, count,
datatype, destination, msg_tag) and receive(address,
max_count, datatype, source, msg_tag)

How to express the data in the
send/receive interfaces

25Computer Science, University of Warwick

 Message tag is necessary, but not sufficient

 So, communicator is introduced …

How to distinguish messages

26Computer Science, University of Warwick

Communicators

• Messages are put into communication contexts

 Contexts are allocated at run time by the MPI system

 Each generated context is unique

• The processes in a MPI system are divided into groups

• The notions of context and process group are combined in a

single object, which is called a communicator

 A communicator consists of a group of processes and a communication

context

 The MPI library defines a initial communicator, MPI_COMM_WORLD,

which contains all the processes running in the system

• Messages from different communicators can have the same tag

• So the send interface becomes send(address, count, datatype,

destination, tag, comm)

27Computer Science, University of Warwick

Status of the received messages

• The structure of the message status is added to the receive

interface

• Status holds the information about source, tag and actual

message size

 In the C language, source can be retrieved by accessing

status.MPI_SOURCE,

 tag can be retrieved by status.MPI_TAG and

 actual message size can be retrieved by calling the function

MPI_Get_count(&status, datatype, &count)

• The receive interface becomes receive(address, maxcount,

datatype, source, tag, communicator, status)

28Computer Science, University of Warwick

How to express source and destination

 The processes in a communicator (group) are
identified by ranks

 If a communicator contains n processes, process
ranks are integers from 0 to n-1

 Source and destination processes in the send/receive
interface are the ranks

29Computer Science, University of Warwick

Some other issues

In the receive interface, tag can be a wildcard
(MPI_ANY_TAG), which means any message will be
received

In the receive interface, source can also be a wildcard
(MPI_ANY_SOURCE), which match any source

30Computer Science, University of Warwick

MPI basics

First six functions (C bindings)

MPI_Send (buf, count, datatype, dest, tag, comm)

Send a message
buf address of send buffer
count no. of elements to send (>=0)

datatype of elements

dest process id of destination

tag message tag

comm communicator (handle)

31Computer Science, University of Warwick

MPI basics

First six functions (C bindings)

MPI_Send (buf, count, datatype, dest, tag, comm)

Send a message
buf address of send buffer
count no. of elements to send (>=0)

datatype of elements

dest process id of destination

tag message tag

comm communicator (handle)

32Computer Science, University of Warwick

MPI basics

First six functions (C bindings)

MPI_Send (buf, count, datatype, dest, tag, comm)

Send a message
buf address of send buffer
count no. of elements to send (>=0)

datatype of elements

dest process id of destination

tag message tag

comm communicator (handle)

33Computer Science, University of Warwick

MPI basics

First six functions (C bindings)

MPI_Send (buf, count, datatype, dest, tag, comm)

Calculating the size of the data to be send …

buf address of send buffer

count * sizeof(datatype) bytes of data

34Computer Science, University of Warwick

MPI basics

First six functions (C bindings)

MPI_Send (buf, count, datatype, dest, tag, comm)

Send a message

buf address of send buffer

count no. of elements to send (>=0)

datatype process id of destination

dest process id of destination

tag message tag

comm communicator (handle)

35Computer Science, University of Warwick

MPI basics

First six functions (C bindings)

MPI_Send (buf, count, datatype, dest, tag, comm)

Send a message

buf address of send buffer

count no. of elements to send (>=0)

datatype process id of destination

dest process id of destination

tag message tag

comm communicator (handle)

36Computer Science, University of Warwick

MPI basics

First six functions (C bindings)

MPI_Send (buf, count, datatype, dest, tag, comm)

Send a message

buf address of send buffer

count no. of elements to send (>=0)

datatype process id of destination

dest process id of destination

tag message tag

comm communicator (handle)

37Computer Science, University of Warwick

MPI basics

First six functions (C bindings)

MPI_Recv (buf, count, datatype, source, tag, comm, status)

Receive a message

buf address of receive buffer

count max no. of elements in receive buffer (>=0)

datatype of receive buffer elements

source process id of source process, or
MPI_ANY_SOURCE

tag message tag, or MPI_ANY_TAG

comm communicator

status status object

38Computer Science, University of Warwick

MPI basics

First six functions (C bindings)

MPI_Init (int *argc, char**argv)

Initiate a MPI computation

argc(number of arguments) and argv(argument vector) hold
main program’s arguments

Must be called first, and once per process

MPI_Finalize()

Shut down a computation

The last thing that happens

39Computer Science, University of Warwick

MPI basics

First six functions (C bindings)

MPI_Comm_size (MPI_Comm comm, int* size)

Determine number of processes in comm

comm is communicator handle,

MPI_COMM_WORLD is the default (including all MPI
processes)

size holds number of processes in group

MPI_Comm_rank (MPI_Comm comm, int* pid)

Determine id of current (or calling) process

pid holds id of current process

40Computer Science, University of Warwick

MPI basics – a basic example

mpirun –np 4 myprog

Hello, world. I am 1 of 4

Hello, world. I am 3 of 4

Hello, world. I am 0 of 4

Hello, world. I am 2 of 4

#include “mpi.h”

#include

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

int rank, nprocs;

MPI_Init(&argc,&argv);
MPI_Comm_size(MPI_COMM_WORLD,&nprocs);
MPI_Comm_rank(MPI_COMM_WORLD,&rank);

printf(“Hello, world. I am %d of %d\n”, rank, nprocs);

MPI_Finalize();

}

41Computer Science, University of Warwick

MPI basics – send and recv example (1)

#include “mpi.h”

#include

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

int rank, size, i;

int buffer[10];

MPI_Status status;

MPI_Init(&argc,&argv);

MPI_Comm_size(MPI_COMM_WORLD, &size);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);

if (size < 2) { printf("Please run with two processes.\n"); MPI_Finalize(); return 0; } if (rank == 0) { for (i=0; i<10; i++) buffer[i] = i; MPI_Send(buffer, 10, MPI_INT, 1, 123, MPI_COMM_WORLD); } 42Computer Science, University of Warwick MPI basics – send and recv example (2) if (rank == 1) { for (i=0; i<10; i++) buffer[i] = -1; MPI_Recv(buffer, 10, MPI_INT, 0, 123, MPI_COMM_WORLD, &status); for (i=0; i<10; i++) { if (buffer[i] != i) printf("Error: buffer[%d] = %d but is expected to be %d\n", i, buffer[i], i); } } MPI_Finalize(); } 43Computer Science, University of Warwick MPI language bindings  Standard (accepted) bindings for Fortran, C and C++  Two types of Java bindings (work in progress)  native MPI bindings: native MPI library is called by Java programs through Java wrappers JavaMPI mpiJava  pure Java implementations: the whole MPI library is rewritten in Java jmpi MPIJ  Java Grande Forum trying to sort it all out  We will use the C bindings