Slide 1Generic Parallel Machine ArchitectureParallel programming languagesSome models of parallel computationTriton node architectureTriton overall architectureMessage-passing programming modelHello, world in MPIMPI in nine routines (all you really need)Ten more MPI routines (sometimes useful)Example: Send an integer x from proc 0 to proc 1Some MPI ConceptsSome MPI ConceptsSome MPI ConceptsParameters of blocking sendParameters of blocking receiveExample: Send an integer x from proc 0 to proc 1CS 240A:Models of parallel programming:Distributed memory and MPIGeneric Parallel Machine Architecture•Key architecture question: Where and how fast are the interconnects?•Key algorithm question: Where is the data?ProcCacheL2 CacheL3 CacheMemory Storage HierarchyProcCacheL2 CacheL3 CacheMemoryProcCacheL2 CacheL3 CacheMemorypotentialinterconnectsParallel programming languages•Many have been invented – *much* less consensus on what are the best languages than in the sequential world.•Could have a whole course on them; we’ll look just a few.Languages you’ll use in homework:•C with MPI (very widely used, very old-fashioned)•Cilk++ (a newer upstart)•Use any language you like for the final project!Some models of parallel computationComputational model•Shared memory•SPMD / Message passing•SIMD / Data parallel •Partitioned global address space (PGAS)•Hybrids …Languages•Cilk, OpenMP, Pthreads …•MPI•Cuda, Matlab, OpenCL, …•UPC, CAF, Titanium•???Triton node architectureNode MemoryProcCacheL2 CacheL3 CacheProcCacheL2 CacheProcCacheL2 CacheProcCacheL2 CacheProcCacheL2 CacheL3 CacheProcCacheL2 CacheProcCacheL2 CacheProcCacheL2 CacheChipChipNode<- Myrinet Interconnect to Other Nodes ->Triton overall architectureMessage-passing programming model•Architecture: Each processor has its own memory and cache but cannot directly access another processor’s memory.•Language: MPI (“Message-Passing Interface”)•A least common denominator based on 1980s technology•Links to documentation on course home page•SPMD = “Single Program, Multiple Data”interconnectP0memoryNI. . .P1memoryNIPnmemoryNIHello, world in MPI#include <stdio.h>#include "mpi.h"int main( int argc, char *argv[]){ int rank, size; MPI_Init( &argc, &argv ); MPI_Comm_size( MPI_COMM_WORLD, &size ); MPI_Comm_rank( MPI_COMM_WORLD, &rank ); printf( "Hello world from process %d of %d\n", rank, size ); MPI_Finalize(); return 0;}MPI in nine routines (all you really need)MPI_Init InitializeMPI_Finalize FinalizeMPI_Comm_size How many processes? MPI_Comm_rank Which process am I?MPI_Wtime TimerMPI_Send Send data to one procMPI_Recv Receive data from one procMPI_Bcast Broadcast data to all procsMPI_Reduce Combine data from all procsTen more MPI routines (sometimes useful)More collective ops (like Bcast and Reduce):MPI_Alltoall, MPI_AlltoallvMPI_Scatter, MPI_GatherNon-blocking send and receive:MPI_Isend, MPI_IrecvMPI_Wait, MPI_Test, MPI_Probe, MPI_IprobeSynchronization:MPI_BarrierExample: Send an integer x from proc 0 to proc 1MPI_Comm_rank(MPI_COMM_WORLD,&myrank); /* get rank */ int msgtag = 1;if (myrank == 0) {int x = 17;MPI_Send(&x, 1, MPI_INT, 1, msgtag, MPI_COMM_WORLD);} else if (myrank == 1) {int x;MPI_Recv(&x, 1, MPI_INT,0,msgtag,MPI_COMM_WORLD,&status);}Some MPI Concepts•Communicator•A set of processes that are allowed to communicate among themselves.•Kind of like a “radio channel”.•Default communicator: MPI_COMM_WORLD•A library can use its own communicator, separated from that of a user program.Some MPI Concepts•Data Type•What kind of data is being sent/recvd?•Mostly just names for C data types•MPI_INT, MPI_CHAR, MPI_DOUBLE, etc.Some MPI Concepts•Message Tag•Arbitrary (integer) label for a message•Tag of Send must match tag of Recv•Useful for error checking & debuggingParameters of blocking sendMPI_Send(buf, count, datatype, dest, tag, comm)Address ofNumber of itemsDatatype ofRank of destinationMessage tagCommunicatorsend bufferto sendeach itemprocessParameters of blocking receiveMPI_Recv(buf, count, datatype, src, tag, comm, status)Address ofMaximum numberMessage tagCommunicatorreceive bufferof items to receiveDatatype ofeach itemRank of sourceprocessStatusafter operationExample: Send an integer x from proc 0 to proc 1MPI_Comm_rank(MPI_COMM_WORLD,&myrank); /* get rank */ int msgtag = 1;if (myrank == 0) {int x = 17;MPI_Send(&x, 1, MPI_INT, 1, msgtag, MPI_COMM_WORLD);} else if (myrank == 1) {int x;MPI_Recv(&x, 1,