Okay, we're good to get started with one more MPI talk, but I think a very different one
compared to the others.
Hopefully.
Compiler-added MPI correctness check.
Yeah.
Thank you.
So my name is Alexander Hück, and today I'm going to talk about basically the dynamic
MPI correctness tool, which is called MUST.
And in particular, I'm going to talk about the compiler extension, which is called Type
Art, which is supposed to help with MPI type correctness checking.
And first of all, as we heard before, the message-passing interface is the defector
standard of distributed computations in the HPC world, right?
And it defines a large set of communication routines and other stuff, and it's also designed
for a heterogeneous cluster system where you have different platforms that communicate
and compute something.
However, in that sense, it's also very low-level interface where you have to specify a lot
of stuff manually, and you can expect only a little error checking in general from the
library itself.
So the user is required for the simple MPI send operation to specify the data, which
is transferred as a typeless void buffer.
The user has to specify its data length of the buffer and the user and the type manually,
and also the message envelope, so the destination of the message and the communicate and stuff
like that has to be specified manually.
So there's a lot of opportunity to commit a mistake, basically.
And this is quite a question to you guys, if you look at this small code, try to figure
out how many errors you can spot in this small example.
And just try to look at every corner, basically.
And while I'm talking, I can also spoiler you that I'm going to show you every issue
in this small example in a couple of seconds, so to speak.
When I first looked at it, my colleague Joachim showed me I couldn't find the most simple
one that was a bit crazy to me.
Sometimes you don't see the forest in front of the trees.
OK, so the most basic one, we don't call MPI in it, right?
That's usually in MPI applications.
That's the very first call you're supposed to do, where you initialize the MPI environment.
And then likewise, if you look at the end of the program, we do not call MPI finalize.
So those are two simple mistakes.
But then in total, we have eight issues.
I don't know how many you found.
And I'm also not going to talk about each one of them, but it's quite easy to, if you
look at each individual issue, to kind of guess that it can happen to you also.
And those are the pointers where they are.
And in particular, I want to talk about the receive-receive deadlock, where, for instance,
two process weights on each other without being able to continue.
You can argue that all those issues, except maybe the deadlock, could be found by the
MPI library itself.
But typically on HPC systems, the library does not do any checking for performance reasons.
That's why many of these issues will not be, will cause maybe crashes for unknown reasons
or just produce some strange results.
Well, that's why the dynamic MPI correctness tool must was developed in the past, which
is a tool that during runtime checks for issues and produces such reports where it finds some
issues.
And this is a report of the deadlock we have seen in the example code, where the message
itself just describes there's a deadlock.
In the bottom left, you can see a wait for graph, which just shows you which rank waits
for another rank causing the deadlock.
This helps you to kind of see where the deadlock occurs and why it occurs.
And also, must can produce so-called call stack information, where you can see, beginning
from main of the program to the basically origin of the deadlock, but this was omitted
now.
Okay.
So, to facilitate correctness checking for MPI, must uses a so-called distributed
agent-based analysis, which means that you have your normal MPI application with four
ranks, four processes that communicate as you would expect as the user wrote it.
But must will also create a analysis network, which helps you to do local analysis, it helps
you to do distributed analysis.
If you think about a deadlock, you need information for more than one process to figure out that
there occurred a deadlock in your program.
So must creates that completely transparent to the user, so you would use MPI comworld
and any other communicator as normal, must takes care of creating such a network.
And also, what's maybe the focus of the talk today is the local analysis, where we look
at process local checks.
If you think about MPI type correctness of a send operation, you can do a lot of stuff
locally, or I should do a lot of stuff locally, and this is the focus.
So, MPI type correctness, we focus basically on the buffer and the user-specified length
and the user-specified MPI data type today.
Must can already detect mismatches of, for instance, the send and receive communication
pair, where must basically creates a so-called type map, it looks at the user-specified
buffer size and the user-specified data type, and compares it to the corresponding receive
operation.
If there is a mismatch, obviously, there is going to be an issue, and must creates a report
about that.
This also, of course, works for collective communications, where you can make sure that
all ranks call, for instance, a broadcast operation with the same data type.
However, since must only intercepts MPI calls in general, it cannot look behind a
device, like it cannot look what happens in user space, you know.
So, we cannot reason about the type of the Void buffer data, and this is why we were
motivated to create the tool type art, which is something that helps with basically figuring
out what the memory allocation is that you put into your MPI calls.
So, if you look at this small example on the right side, completely processed locally,
there might be some memory allocation in that example, it's a double buffer that was allocated
by Melloc, let's say, and the question now becomes, how can we make sure that data, the
data buffer, which is a Void buffer, fits the user-specified buffer size, so is it of
length buffer size, and it also should be compatible with the MPI float type, and of
course, we can already see that double and MPI float, there's a type mismatch, but must
cannot answer such a question without further tooling, because it just intercepts MPI calls.
Okay, so to just show you that it's not an academic example, there's two well-known HPC
benchmark codes, which have some issues, so one was reported in the past by others, where
there's a broadcast operation, it uses a big end, which is an alias for a 64-bit data type,
however, the user-specified MPI end, which is a 32-bit data type for the broadcast operation,
so there's an obvious mismatch, that could be a problem, likely, and also for milk, there's
an all-reduced operation, where the user's passed in a struct with two float members,
and it's interpreted as a float array of size two, which is B9, to be honest, but that could
be a portability issue in the future, maybe, you know, depending on the platform, maybe
there's padding, or whatnot, and maybe it's an illegal operation, so this could also be
an issue in the future.
Well, from a high-level point of view, how it does must work, well, you have your MPI
application, and during runtime, it intercepts all the MPI calls, and collects all the states
that it's needed for deadlock detection, and so on, and we added type art, which looks
at all those allocations that are passed to MPI calls for those local analysis of buffers,
which is the compiler extension based on LLVM, so you compile your code with our extension,
and the extension instruments all allocations, be it stack, be it heap, which are related
to MPI calls, and we also provide a runtime, so during runtime, we get callbacks of the
target application, all allocations, all free operations, so we have a state of the allocation
of the memory, basically, in a target code.
We also, of course, look at the allocations and pass out their type, so simple case is
buffer, A is a double type, more complex cases would be structs or classes, we pass the serialized
type information to our runtime, which then enables, of course, must to make queries,
so for instance, for an MPI center operation, we give the type art runtime the buffer, the
typeless buffer, and the runtime would return all the necessary type information to ensure
type correctness of those buffer handles.
This is the whole high level process behind it.
And then if you take a look at an example of a memory allocation, C is a small heap
allocation of a float array, this all happens in LLVM IR, I'm just showing C like code to
make it easier to understand, we would add such a type art alloc callback, which where
we need the data pointer, of course, and then we need a so called type ID, it's just a representation
of what we allocated, that is later used for type checking, and of course we need the dynamic
length of the allocated array to reason about where we are in the memory space, so to speak.
Once we handle stack and global allocations, for stack allocations, of course, we have
to respect the automatic scope dependent lifetime properties, and for global we just register
once and then it exists at our runtime for the whole program duration.
And of course, for performance reasons, you can imagine that the less callbacks the better,
hence we try to filter out allocations where we can prove that they are never part of an
MPI call and just never instrument those.
This is basically possible on LLVM IR by data flow analysis, so in the function foo we have
two stack allocations and then we try to follow the data flow where we can see that A is passed
to bar, and inside bar there's never any MPI call, so we can just say, okay, we do not need
to instrument this, this is discarded.
Likewise for foo bar, we can see that B is passed, if it's in another translation unit
we would need to have a whole program view of the program, which we support, but other
tools have to create such a call graph with those required information.
Anyways, so also if we had this view, we can see foo bar also does not call MPI, so both
stack allocations don't need to be instrumented, which helps a lot with the performance.
Okay, so the type ID which is passed to the runtime for identification works as follows,
built-in types are obviously known a priori, so we know the type layout, float is 4 bytes,
double is 8 bytes, depending on platform of course, for user defined types, which means
structs, classes and so on, we basically serialize it to a YAML file and the corresponding type
ID of course, so we can match those during runtime, where we have the extent how many
members offsets, byte offsets basically from the beginning of the struct, and also the
subtypes are listed, which can then be used for making type queries about the layout and
stuff like that.
And then of course, must needs to have some API to figure out type correctness, and this
is provided by our runtime, which has quite a few API functions, the most basic one would
be this type out get type where you put in the MPI buffer handle, and what we put out
is the type ID and the error length, and then you can use the type ID subsequently, for
instance in this call where you put in the type ID and you get out the struct layout
I just mentioned earlier, and this way you kind of can assemble some iterative type checking
which is done in must.
And then putting it all together, if you want to use our tooling, you would need to first
of all compile your program with our provided compiler wrapper, which is a batch script and
does the bookkeeping require to introduce the instrumentation, the type out stuff, so
you exchange your compiler, that's the first step, it's optional, you don't have to do
it if you don't need this local type out checking, and then you would also need to replace your
MPI exec or MPI run depending on the system with the must run, which also does some bookkeeping
for must to execute the target code appropriately, spawn all the analysis agent based networking
and so on, and then the program runs as normal and must output file is generated with all
issues found during execution of your program, and as a side note maybe, as I said must does
this agent based network and in the most simple case for the distributed analysis, there's
an additional process needed for the deadlock detection and so on, so for SLAM or whatnot
you need to allocate an additional process, however you don't need to specify it in the
must run stuff, it happens automatically in the background, alright, so that's it, if
you look now at what the impact is of our tooling, well that's quite dependent as I
kind of alluded to, how many callbacks you have, how many memory allocations you actually
have to track, and how good we are at filtering them, so here's two examples, Lulech and
Tachyon, which are again quite well known HPC benchmarking codes, and Lulech is quite
favorable for our presentation because there's not many callbacks and hence our runtime impact
is like quite non-existent so to speak, where you can see that this is compared to vanilla
without any instrumentation without our tooling, type art almost has no impact, and then with
type art analysis enabled has almost no additional impact, for Tachyon the picture looks quite
different as you can see, there's an overhead factor of about three using when you introduce
type art, this is because there's a lot of stack allocations that cannot filter, so we
track a lot of stack allocations and the runtime impact is quite high, and this is reflected
by those runtime and static instrumentation numbers, so first of all the buff table here
shows you during compilation what we instrument, so you can see that there's some heap free
operations that we find an instrument, there's some stack allocations and globals that we
instrument, well of course those numbers do not represent the runtime numbers because
heap and free operations sometimes are written in a way that they are like centralized in
a program, that's why those numbers are not as high as you would expect, for stack allocations
we find 54 and out of those 54 we can filter for Lulish at least 21%, and globals are much
easier to follow along the data flow in LLVM IR so we can filter much more and much more
effectively, well going to the runtime numbers which means that those are basically the
number of callbacks that happen during our benchmarking, we can already see that the
high overhead of which we observed in Tachyon is to be explained by the almost 80 million
stack allocation callbacks basically that we have to track during runtime, which is
a lot of context switching and so on, which is not good for the runtime, alright so this
is already my conclusion, what we have done is basically with type art must can now check
all phases of the MPI communication with respect to type correctness, so the first phase that
must can already do is this one, which is basically the message transfer, this is checked
against, however there is also the phase of message assembly, right where you go kind
of from the user process into the MPI process and you have to check this, and of course
if you think about it you would also have to kind of check the message disassembly where
you go from the received data to your user program again, so type art enables these kind
of local checks to ensure type correctness, thank you very much.
Any questions?
Yeah so I really like to talk, I thought it was really interesting, so one thing I wanted
to ask was how does one get must, like how do they install it, is it available for distribution
package managers or is it more that you have to compile it yourself?
Good question, I think you have to compile it yourself, even on our HPC system so, but
it's not that tedious to compile I think, maybe I'm biased, but just go to the website
and there's a zip file, it includes every dependency that you need and I think the documentation
is quite straightforward, you need of course maybe open MPI installed, but not much more
to be honest and then you should be good to go, yeah, I think it's CMAC based, I don't
know if you have problems with that, but yeah, it should be straightforward to try it out.
Thank you, another question there on my way.
So on the type analysis that you do, I mean if you look at malloc and it has like a type
cast then you know what the type is, but if it doesn't have a type cast, if you malloc
into a void pointer and if the amount of bytes you are allocating comes from some constant
or macro or some argument, how far do you follow and if you can't see it, do you have
a warning, do you crash?
That's a good question and that's basically a fundamental problem, right, so we have to
have some expectations of the program, right, so our expectation is that the malloc calls
are typed, otherwise we would just track it as a chunk of bytes and I think our analysis
is quite forgiving, so we would just look at okay this is a chunk of bytes, it fits you
know the buffer and this is fine.
Yes, you kind of lose that, right, if you just know it's a chunk of bytes then you kind
of lose the alignment checks because you could, if you have like say you malloc is struct
and then you do some pointer magic for your MPI buffer and you point between members in
the padding area, only if type art knows about the malloc struct, it can of course warn that
you are doing some illegal memory operations, if we just see a void pointer due to the type
plus malloc then we have lost basically, anyone else, do you have any thoughts on using Rust
which is a way more memory safe language than C and C plus pluses, have you looked at it?
Not really, not yet, for now we have so much to do with the C and C plus words to support
typing better, to get more robustness and so on and not yet to be honest.
Maybe all that work becomes irrelevant if Rust gets popular enough.
I think in general maybe I'm completely like a newbie when it comes to Rust, I think the
MPI support itself is still in the works, I read some papers about like generating bindings
for MPI which are inherently type safe, not sure how that goes.
I think everyone will be happy if Rust or some other type safe language becomes more
used by people and this kind of work is irrelevant, but while people still use C plus pluses,
this is very relevant.
That pays my bills.
Thank you very much.
Thank you.