But before, before we do that, I wanted to talk about programming and a competitor to
using shared memory for programming. So, so far, we have looked at a shared memory
architecture to communicate from one core to another core. So, what does that means
is one core does a store to some memory address. And sometime in the future,
another core goes to read that memory address and gets the data. What's
interesting about that paradigm is the sender of the data, the core which is
writing the data or doing the store does not need to know which core is going to
read the data in the future. Or it's very possible that no one will go read that
data in the future. And in shared memory architectures, that doesn't, that doesn't
affect anything. We can actually have one core writes a piece of data in the memory
and some address and given this implicit name, we effectively have some associative
match where you can look up based on the address, the piece of data and go find the
piece of data sometime in the future. Now, you probably need to use locking and to,
to guaranteed causality between one processor writing the data and another
processor reading the data in shared memory but you don't need to know the
destination. In contrast, we're going to talk about explicit message passing as a
programming model. Now, there are lots of hardware implementations, you can go
implement this. But let's start off by talking about exclusive messaging as a
program model to communicate between different threads, processes, or cores.
And what we're going to have here is we're going to add, we're going to, we're going
to have an API or a, a programming interface here of send, where it names the
destination, and passes into it, a pointer to some data. And in our messaging API,
this is going to take this data and somehow get it to the receiver or the
destination. On the receive side, the most basic thing they can do is you can receive
data. Note this receive here does not denote who it's receiving data from. So, a
common of thing you can do is just receive in order, receive the next piece of data
that it gets in. Now, that may not be super useful so you may want to extend
this to having the receive actually take a, a source also. But it's not required.
There are the reason I'm, I'm talking about this in this abstract fashion here
is there's many different explicit message passing programming interfaces because
it's just software that people have implemented over, over the years. but at
the, at the fundamental level, there's a send and a receive. And you could think
about having the send, or the send requires a destination and receive can
just receive of, of, basically the input queue or it would try to receive from a
pre-recorded source, or another way to do this is what they do in, in MPI, which is
called the public message passing interface, which is a probably the most
common programming interface for messaging, is it won't take a source, but
instead, it will take a tag, which is effectively a number which says, what
message type is the or not message type, sorry, what, what traffic flow is it, you
sort of name the flow. This is kind of a tag is, is sort of a more generalized form
of, in TCP/IP, they have ports, for instance, right? And UDP has ports. Okay.
So, questions so far about this basic program model and why is it different than
loads and stores through shared addresses. Very different. They are jewels of each
other. I'm going to tell you right now that you, if you can implement one thing
of shared memory, you can implement messaging and vice versa, and there have
been lots of fights over this, and at some point or, or, the whole community realized
that you can do either with either. You can do any programming model, you can do
one and the other. Okay. So, the default message type we're going to talk about is
unicast. So, that's one-to-one. If you ascend to a destination, the destination
is one other node or one other process, or one other thread. The reason that I say,
process, thread, and node is depending on how API is structured. You might have, you
could use a, a messaging, exclusive message passing system on something like a
uniprocessor. We have different threads or different processes running and you are
only messaging for one process to another process even though it is one core. But
there's a pretty natural extension of that. You can take those two processes and
put them on different cores, and have them communicate using the same interface. We
could also do this between two threads, but that's less common. Okay. So, that, so
unicast is one-to-one. Some messaging networks and some messaging primitives
will actually program models will have a couple of other choices here. We can have
multicast. So,- this is communication from one node, but instead of having a
destination here which denotes one other location, it can denote a set of other
people to communicate with. It is still messaging except for destination, we've
expanded our notion of destination here so it can be a set, not just a single thing.
We can also have broadcast, where you can have one node, instead of having
destination here, you can have some magical flags which says, communicate this
with every other node in the system or every other process in the system or every
other threat in the system or every other process in that process group or thread
group there is. There's ways to sort of say that in these software protocols. just
for a quick question here. Has anyone here programmed an MPI? Okay. And once in a
while, perform a programming. Good. So, we'll talk briefly. I'm going to show a
brief code example here of one process communicating with another process via a
very common messaging library called the message passing interface or MPI for
short. So, let's look at this piece of code. It's a C code and what's happening
here is, okay we start our program, we have my ID. So, the, the program model of
MPI is that it will actually start the same process on multiple cores or multiple
processes or multiple not, not, it's not threads but multiple processes or multiple
cores will sta rt up the exact same program. So, this is sometimes called SPMD
or single program multiple data program model. SPMD. So, the SPMD model here, what
you're going to notice is that actually we're going to execute this program twice.
One on the one core, and one on the second core. Now, you're going to ,, well, if
you're executing exact same program, are they going to do the exact same thing?
Well, let's take a look. Okay. So, we have this thing called my ID. This is what
tells us in what core we are. And there's something here called numprocs, which is
going to tell us how many processors there are in the computer. And we fill these in.
So, you see here, we start off by calling MPI INT MPI INT sets up the message
passing system from a software perspective. Then we call MPI
communication size with some magic parameters. And it's going to fill in this
field, which tells us how many processors there are in this, in this MPI program.
When you launch an MPI program, there's a special MPI Start command that you will
have to run, which will actually, is, it takes a parameter of how many it takes
parameter of programmer trying to run and multiple processors that you are trying to
run, and the number of processes that you are trying to run it on. So, our program
now can dynamically detect how many processors were running on. It can also
detect what's called our rank, which is our ID. So now, we can actually detect
before the first process or the second process launched in a two-process system
or which one we are, and will fill in my ID with a rank. And this is a library
which will figure this out for us. In this, this MPI implementation. Okay. So,
we are assert now. We say the number of procs equals two. this is just to make
sure we're not running on three processors or ten processors or something like that.
We want strictly two and, And not one, and not so that will, that will fail if we get
a problem there. Okay. So now, this is, this is where we can do different things.
So, single program multiple data. The reason it's c alled this is we can
actually make decisions based on our processor ID or my ID here. So, we'll do
something which says is my ID zero? Do this else, do this other piece of code,
okay? So, is everyone want to wage your guess here what this program does so far?
So, the one, one processor is going to be executing this, the other processor is
going to be executing that. First processor executes a send. Let's, let's
look at this first line here and see what happens. This is the data we're trying to
send so we're sending x, which is an integer, which we load with the number
475, which is our class, or course number. And we send that with a particular tag.
So, MPI is structured around this notion of tags, which is how you can effectively
connect up a sender and a receiver. Oh, sorry. That's how you can connect up
multi, multiple pieces of traffic between senders and receivers. The other way that
you figure out is by looking at, there's a, a number of who you're sending and
receiving to, so this is the core number. So, what this says here is send x to rank
number one with tag, tag, we're going to say tag is 475 also, and this MPI rest of
this stuff here, don't worry about. And this is, this is a length. So, this is
going to say, send one word of size integer to processor one with a particular
tag. And this MPI COMM WORLD basically is extra flags you can pass there which says,
do I want to send to ev, all other MPI sub processes or you can make subgroups?
There's this notion of groups that MPI has but it's kind of, more complicated. Okay.
So, at the same time, this other program is executing here. The first thing it goes
to do is it receives. So, if it gets here first, it's just going to block and wait
in this receive. Conveniently, this first processor did ascend, and has a matched
receive here. So, it's going to receive with tag 475 length one of an MPI integer
from zero, and return as a status code. So, it's going to fill in y with the data
that got sent on this message. That's pretty fun. We just communicate inform
ation between two processes. Okay. So, let's, let's look through what's happening
here. Process zero as you do the send. So, it's going to send 475 to processor one.
Processor one could have gotten here early, at this receive. And processor one
does not execute any of this code. And it has different address base, x's and y's
are different, we have no shared memory here. It gets here, and it's going to do
receive. And at some point, the send shows up and the, the message shows up to the
receiver. It gets received and put into y. So, it just fills it in which is why we
pass the address of y. Now, we're going to increment y by 105, so we did some
computation on this node. At the, at the same time while were, we're doing this
receive, and we're doing this increment, and we're doing this send, process zero is
basically just sitting here waiting, trying to receive. So, we're doing, we're
having process zero. Sends some data to process one. Process one is going to do
some math on it that's going to increment the number, and it's going to send that
number back. So, it does the send back here which have y again. And we're going
to send y to process zero of length one, and when the message shows up, we're going
to receive in the process zero, and process zero is going to print out a
message. okay. What, what does it say? Received number 580. Yes, it should go 580
A, not 580 not 580 without an A. Because 580 without an A is not the parallel
programming class, that's the security class next to it. But 580 A, you should go
to it. So, it prints out the number. So, it can communicate from the one process to
the other process and back with messaging. So, one of the things we should note here
is, we are both moving data and we are synchronizing at the same time in this
message. So, it's, it's doing two different operations here. So, this is a
great question. So, this is a programming model right now. We're not going, you
know, there's many different ways to implement MPI and people to implement MPI.
The interface of these MPI send, MPI receive, are many different ways. So,
people have implement this, implement this over a message, hardware message passing
network, which does not have to go into the OS, for instance. You send and it
actually, there's, effectively hardware there which implements MPI send and
receive, sends it out over the networks and receives it on the receive side and
there's some interconnection network in the middle. That's one way. Another kind
of way is that you actually run MPI over a shared memory machine. At which point, MPI
send. This is going to sound kind of funny. It basically takes the data, copies
it into RAM somewhere and then when the receiver goes to receive it, it looks to
open in the hash table, finds the location in RAM and doesn't reach from that pointer
and that's, that's an option. And actually, that is one of the most common
ways that people run MPI today is, that doesn't have to go in to the OS because
it's just shared memory. on small machines, people run MPI that way. And it
actually has good, has typically had a better performance than sort of the
equivalent thing of writing the short memory program. And the reason for that is
you've effectively, explicitly made the communication or you've made the
communication explicit. So, that coherence protocol, you're basically going to be
build to optimize for producer-consumer. You have a right to some location. And
then, someone else is going to read it, your not going to have random false
sharing problems, your not going to lots other problems. So, that's pretty common.
where MPI has the biggest use today is in massively peril computations. So, this is
sort of the supercomputers of the world. sort of the, all the supercomputers minus
the vector of supercomputers who typically don't use MPI, but the massively parallel
computers. So, like the biggest computers in the world right now, the I don't know,
the Roadrunner computer at Los Alamos, for instance, and the similar sorts of
computers like that. They will have special network cards that implemen t MPI
effectively and they do it in user space. Now, another way to do it is that you can
actually implement MPI over TCP/IP going through the operating system. And that's
pretty common when people just run small clusters of computers is MPI send and
receive will trap into the operating system. It will go into the library first
and then up, the library will watch you read and write to the sockets. At some
point, that will go out over the network card. All of those are possible and all of
those have very optimized MPI implementations because this is the most
widely used parallel messaging library for high performance application and has the
largest . So, people have optimized this quite a bit. Okay. So, this, this brings
us to the question of, a lot of words in this slide, but I do want to sort of talk
about this, of message passing versus shared memory. So, we have two different
parallel programming models. Message passing, where you have to explicitly name
your destinations. And shared memory, where you went to some random location at
some point in the future, someone goes and reads from it and you don't know who the
reader is. It could be any of the processors in the system. If, you, you
could just read around them it could be random. It could be literally random like
you read some random number and it tells you whose going to do a reading of that
location. But if you think about it, because you have any, you can write two
locations someone else can go read it in shared memory. You are effectively having
a one to all communication versus message passing allows your microarchitecture and
your system to do the optimize around point-to-point communication. Okay. So,
let's compare these two things. we have message passing here. In message passing,
typically, memory is private per node or per process or per core. So, memory is not
shared. Shared memory by definition, memory is shared. Message passing of
explicit send and receives in our software code. So, we're actually going to put a
MPI send and MPI receive. We' re actually going to have sends and receives.
Conversely, shared memory, we have these implicit communication via loads and
stores. And the load and the store names an address but it does not name a core
number or a process number or a thread number. Message passing moves data. We do
a send and we put some data in there. Also by definition of receiving a message on
the receive side, there's some synchronization there. There's a
producer-consumer relationship from the sender to the receiver. In shared memory,
you have to explicitly have synchronization. sorry, I should say
explicit. You need to add explicit synchronization via fences, locks, and
flags. So, you need to add something in there to do synchronization. And if you
don't, you don't, if you don't have synchronization, you could have race
conditions. You can get the wrong data. You can pick up the incorrect data, which
is a, a pretty common programming error in shared memory programming. So you don't
need to know the destination, you don't need to know the destination up here. From
a, from a programming perspective, what I wanted to point out here is message
passing is very natural for producer-consumer style computations. So,
if you have one node producing some value and another node reading the value, it's
very, very natural. You set up, you set up a you send, you're sending from one node
to the other node and receive it at the other node and you have a channel between
them and you can communicate. And you can sort of send data in there, it's all in
order, we'll say, and you can just send down the channel stuff comes out the other
side. Very natural for producer-consumer. Shared memory, you have to implement
producer-consumer like we did on last lecture, where you have, like a Python
memory, and locks on that structure. But what is easy on shared memory, which is
hard to view in message passing, is if you have a large shared data structure. Let's
take, for example, you have a big table. And you're trying to process this table in
parallel and you have, I don't know, a big you have lots of little files. And you
give each of these files to a different processor. The processor reads the file
and what we're trying to do here is we're trying to build a histogram. So, it's
going to read some number out of a file and based on that number, it's going to
look at a shared data structure and increment that location by one. Now,
because it's shared memory, you want to make sure the two processes or two
processors or two threads or two processes or two processors is not trying to
increment the number at the same time, so you probably want to lock that location in
the table or lock the whole table, increment it, and then unlock it so you
don't have two people trying to increment it at the same time. But it's very natural
to build a shared table in shared memory and have locks on that shared table and
have different people operating on that shared piece of data at the same time. So,
the interesting thing here is that you can actually tunnel shared memory over
messaging. And you can tunnel messaging over shared memory. So, let's look at the
first example here of how to implement shared memory on top of messaging. You
could do this in software. And in software, we, how we do this is
effectively try and turn all of our loads and stores into sends and receives. Maybe
from, and there's maybe like one centralized node which has a big notion of
memory. That's one way to do this or you distribute it somehow. It's going to be
pretty painful to do. But people have implemented systems like this, where you
actually implement loads and stores or your compiler will go and pick out loads
and stores and turn them into messages. A more common thing to have happen is to
actually have hardware that automatically turns communications into messaging. So,
we are going to take this motion of a programming model and instead, we are
going to turn into a broader motion of entities trying to communicate via
explicit communications that are sent and then sort of interconnect. And this is
actually the mo st common way these days that people go about implementing these
large shared memory machines. This is actually, the memory traffic will get
packetized. And we'll talk about packetization in a second. And it will get
sent over a network and then received and then some receiver will do something with
it. So, an example here, let's say, we have this core here and this core wants to
do a load. And the, the, the, the data is in main memory. On our bus here, the core
could just shout, I need address five. And the memory will shout back, got it,
address five has the value six. If we have a switch interconnect, we put switches in
here. We can have the core actually packetize the memory request. So, we'll
take this load and it will make a message, send it over the network, and it will show
up at the memory. The memory will read the message, make a response, and, And it can
send it back over the network also. So effectively, what we have here is we can
actually tunnel shared memory over a message network. And this is actually, for
large cache coherence systems. The most common thing that happens. We'll be
talking about this in greater depth in two classes when we have our directory based
protocols, which are effectively implementing shared memory over these
switched interconnection networks. You could also implement messaging over shared
memory and this is pretty common in small systems that have shared memory. They have
no other way to communicate. And this is exactly what we talked about last lecture.
We had a FIFO, we had head and tail pointers, producer can effectively enqueue
onto this queue in main, main memory. Consumer can go read from it and you could
implement messaging this way. So, I guess, what I'm trying to get at here is
messaging and shared memory are duals of each other. They may be more natural for
one thing or another, but you can implement any algorithm, you can implement
one in the other. And that's been shown at this point.