Let's continue. Up next, we have himadry Chia Shailesh, I hope that's reasonably close.
Who has done a PhD recently, has recently graduated and has been looking into the
fun topic of parallelization in context of virtualized environments, high level description
I guess. In particular, then here in the GCC OpenMP implementation and
Libcom, the corresponding run time library. All right.
Can you hear me?
Yes.
Okay. Perfect. So, hello. I'm himadry. And I recently defended a PhD, my supervisor is
very Sean P. Allazi and Shulia LaWal. By the way, Shulia is present in the room. And
the previous speaker has put me in a challenging spot to show as much excitement about
this work in front of my supervisors. Thank you for that.
Right. So, I right now work with the Krakow esteem, in general, ENP as a postdoc. So, this is
something that I did at Visper, in real Paris.
Okay. So, first I'm going to give a little bit of context of this work. Then a quick
background to introduce the thesis. And finally, I will iterate over what are the contributions
of the thesis. And we will focus on the parts that touch LibQMP, which is run time library
provided by GCC. Okay. So, the context of this work is at the three out of parallelization,
scheduling and virtualization. And to be more specific, I am addressing parallelization,
achieve through LibQMP. So, the OpenMP implementation of GCC, scheduling in terms of lean
internal. So, right now, we have EEVDF scheduler. And for virtualization, I am using KMU,
KVM, hypervisor stack. Okay. Maybe most of you would be familiar with what is OpenMP,
but in case someone needs the definition. It's basically an API that lets you conveniently
convert your code into run your code using parallelization. So, it provides your compiler
directors, library routines, and you have environment variables. And you can do one
stuff with it, and the compiler in the library does a lot of heavy lifting for you. It
also gives the programmer a lot of control about how to achieve the parallelization.
Okay. The very basic idea is suppose you have a loop, and if you are going to do the works
sequentially, then you are going to do the same work in every iteration. And then if you are
using OpenMP, then you will write something like Pratma or MP4, and then that is going
to help you parallelize the loop. So, the application programmer just needs to write the
Pratma directive behind the scene. OpenMP does a lot of heavy lifting by it. We start
with how many threads to use, then you have to fork this threads, and then you have to
distribute the work to this threads, then you have to start the work, then you have to
synchronize the end of the work. And once you are done, you need to terminate the threads.
So, this is done by the library. And as I mentioned that you create threads. And for
this, OpenMP uses fork showing model. So, there is a master thread, and then that takes
care of creating a team of worker distributing the work, and the worker synchronized.
The master also makes a decision about how many threads to use. And once that decision
is made, you have to create those threads, and then synchronize and terminate them. You
also, so if your parallel application have multiple parallel regions, then you can also
reuse some existing threads. So, you don't necessarily create new threads every time.
The thread pull is around, and we are most of the times just reusing the threads.
And for synchronization, OpenMP heavily relies on using barriers. In simple jumps,
barrier is a point in execution, where all threads must arrive before anybody can proceed
further. And for various reasons to just give examples of two, all these threads do not
reach the barrier at the same time. Sometimes the work distribution is not perfectly
even, that can slow some threads down. If you are running your application on a DVFS system,
then you are different threads are running at different frequencies. So, your speed of
finishing computation is different on different core, and that could also slow some threads
down. So, there are some early arrivals at the barrier, and then there are some late
arrivals. So, how do we achieve weighting for the late comeers? And we have basically two choices.
We can either spin or we can block, and then there are some euristic-based decisions
currently in LibFUMP, and then there are also some environment variables that lets you
change this behavior. But I would like to point out that there are two barriers that we
care about, or like LibFUMP implementation cares about. So, one kind of barrier is called the
threads dock barrier. That synchronizes the start of any new parallel work. And then there is
another kind of barrier that is team barrier, which synchronizes in team work. So, you would have
a parallel region, and within the region you could be doing different chunks of parallel
works, and you might need to share interim results, et cetera. So, the barrier that gets used
are different, one that marks the regions, and another one that marks the chunks of the
work that is being done. Okay. So, here is like somewhat realistic example. Again, it is
taken from a micro benchmark suit, but I am showing two parallel, sorry, five parallel regions,
and inside each of these regions, there are two loops that we are trying to parallelize.
So, the first pragma OMB parallel that decides how many parallel regions are going to
be there in this application, and then hash pragma OMB before, that marks a loop that, okay,
this loop is inside a parallel region, and it should be executed with multiple threads.
So, what does it look like? And I would like to make a note that I can produce all this
visualizations. Thanks to the schedule of tools, they were presented in fostering 23,
in the kernel developer room. And they work on top of the F-trace infrastructure in
Linux kernel. So, you can generate a scheduler trace that is going to give you a lot of
events that happen in terms of scheduling, and then you can visualize it in terms of like
which thread was running on which core, which thread blocked a lot of things about scheduling
you can learn from this tool. What's going on when we are running an open MPE application.
And then we are talking about threads. So, the impact of scheduling also comes into the
picture, if you want good performance, you want good decisions by the scheduler.
So, very quickly scheduling 101. Inside the Linux kernel, we have a task struct that contains
important information that is related to a task. We treat threads as also like task is a
generic term inside the kernel. From the kernel view, everything is just a task.
So, there is no process thread differentiation that generally we read about in the
textbooks. The CPUs are represented with another kind of data structure called
runcuse. And two terms that I would be using very frequently are preemption.
So, it's just to define it that you stop a task from running on a CPU. That is a preemption.
And you switch between two tasks. That's the context switch.
And we are talking about running open MPE workloads inside virtual machines.
So, then you have dual level of task scheduling. So, your application is working
some threads. Two threads are trying to run on VCPUs. Then there is a guest scheduler
that is facing your threads on VCPUs. Then you have host scheduler that is
placing VCPUs on VCPUs and then the actual execution is spending out.
And we care about what happens to VCPUs because we are running our threads on that.
And the thing that troubles most is that from the host scheduler's point of view,
VCPUs are no special citizens. They can be preempted anytime.
And they can be preempted at that time. And that could have performance impacts on
MPE applications. So, we care about these preemptions.
Okay. So, now we have enough background to, we know the context and we know all the
important terms. So, I can then quickly touch on the motivation for this thesis before
presenting the thesis. Running open MPE applications in cloud, it's commonplace.
Over subscription is also cost-cutting technique that is widely used.
And if you want good performance for applications for your open MPE applications,
you want good scheduling decisions and you want good value synchronization performance.
And current implementation of LIMP is virtualization oblivious.
And most of these choices that impact the scheduling performance
or the better synchronization performance are static.
So, here is where we define whatever thesis is.
Is that we want to combine the scheduling insights at both levels.
And then we want to use this insights to guide the decisions made by LIMP.
And we are particularly targeting two decisions.
How many threads do you use in each parallel region and how to synchronize these threads?
And goal is to improve performance of open MPE applications,
running inside over subscribe virtual machines.
So, the work could be broadly categorized into three major contributions.
The first is phantom tracker.
It is an algorithm that tracks what is happening to your VCP use.
It is most implemented inside the LIMP scanner currently.
It would be much nicer to provide the same algorithm as BFF programs set.
And that is something I would like to do.
And I talked about this earlier in kernel conferences.
So, this information already exist and my thesis would also be soon available.
So, if someone wants to look at the details of this part of the contribution,
that would be available.
I wouldn't be going into detail of it right now.
The second one is the barriers synchronization mechanism.
We call it PV barriers think because we are introducing this par virtualized.
VCP is something that is not a phantom VCP.
Okay.
So, we track phantoms.
We enable communication between the schedulers.
We register our tasks with the guest.
We register the VMs VCP use with the host.
And finally, we compute phantom average.
We compute this metric at the granularity of the scheduler tick.
And that tells the impact of host overload conditions on the execution of our application.
So, we care about the overload impact on us and not the global load average.
And that's why we just don't take what leaves you MP does now.
Because there is an OMP dynamic implementation that takes global load average into account,
but that is not sufficient.
Okay.
The second contribution is motivated by two important academic works.
The first work show that spinning in overloaded scenario is very bad for performance.
And blocking is not great either.
Second work shows that if you are synchronizing threads in an over subscript scenario,
then you should be removing over subscriptions.
So, it's been as many threads as there are CPUs and then blocked remaining ones.
So, we built on top of it.
We introduce par virtualized insights.
So, we know how many VCPs can run.
So, we only want to run as many threads.
Sorry, we only want to use spinning for as many threads and blocked remaining ones.
So, essentially, we are making a decision on part thread basis at each barrier should I block at this barrier.
And that is entirely determined by the runtime conditions.
You don't need to read this, but it's a style for reference if someone wants to look up the slides later.
But this is, we change the do spin behavior in lips you MP.
Okay, and the final contribution which works in three parts.
So, first is that we adapt the DOP based on the information that we are getting from Phantom Tracker.
In addition to Phantom average, we also provide idle average.
And then we are using the PV barrier sync mechanism for team barrier as well as for the threads barrier.
And finally, we have a lightweight task affinity mechanism that we use to guide the guest scheduler.
Okay.
It is more complicated than this, but this is the just.
If you have Phantom's, don't use more threads.
If you are reduce your DOP.
If you see idle course, then you want to, that means you can increase your DOP.
And if you see that okay, we are in a stable situation, don't change anything.
We want to be more conservative when we increase the DOP so that we don't create more Phantom's and create instability.
So, there is like a stability requirement.
We only scale up by the minimum idle PCPUs seen in two takes and then we also scale that window.
And for affinity, we start with putting our application threads on the first NVCPUs because if the DOP is N.
And then later, if we need to shrink the CPU set, we do it once to better guide the PV sync barrier mechanism.
So, there are some scheduling related nitty gritties about why we do this.
And there is a lot of fighting that I had to do with Linux load balancer, but that what is the scope, you know, that you can improve on.
And then quantify your performance on it.
Then we also want to test whether we do well in varying load conditions as well as whether we do well if we scale smaller virtual machine bigger virtual machine as a pro.
Okay, for evaluation, I am using NAS per eventurizing open implementation of it.
And as you can see, it is quite diverse.
Like some applications have lots of decision points to change your DOP and some have lots of barriers and some good mix of boot things.
And for the competing workload, I am using random sequence.
Again, like this graph is generated using the same schedule of tools.
The green line show how many threads are running in the competing VM.
And then we also change like how frequently number of threads change in the competing VM.
So, the load condition like first one is load is changing once in one second.
Another one, I have the step size of 100 milliseconds, so every 100 milliseconds we have different load condition to balance against.
For baseline, of course, using spinning is not using spinning is common sense.
So we are testing again blocking, like block all threads at all values.
And then we are using a fixed number of threads for each parallel region.
And then for our algorithm, I have patches in the host scheduler, guest scheduler and lips you MP.
All right, so on the, yeah, on the right, it's a larger machine, it has 96 VCPs.
And we managed to win from, I think we are going from yet 30 seconds to 10 seconds or 25 seconds to 10 seconds on that machine.
And on the smaller machine, also we are going from 35 seconds to maybe 15 seconds.
So we win a lot on this benchmark.
But the important thing to note is that there are like lots of parallel regions and lots of barriers.
So there is good opportunity for us to apply corrections.
And then we have this where we don't exactly win, because very less opportunity for changing the number of threads and too many barriers.
That our current PV barriers think struggles to do well with.
Okay, so I want to test this more.
I want to fix it in the scenarios where it doesn't work.
Or at least it should not be with BPF as of now.
But we do use this is it when it comes to be there.
And the next question is, is making you the PPF back and for this is it.
Okay, please use this is it.
Okay, I think I can safely say we try to.
Okay.
I'm not sure it's I think.
How do you want to figure out another purchase use is changing more or.
Right, so the question is, how do we figure out the number of this number of runnable VCPUs is is changing and that is by.
Observing the decisions of the host scheduler for the VCPUs and then also enabling hints from the guest scheduler telling that.
Open MP thread is running on this VCPU and then I'm monitoring on the host scheduler what is happening to that VCPUs.
So essentially I'm monitoring the context which is and wake up events.
And I'm measuring that when a VCPU was thrown off from a PCP and when it got back again.
So those are state transitions I take samples and I compute average from the transitions.
And it's a simple pull out don't know or don't understand.
Let's let's say you're in the middle of one of schedule and decision both of you.
I'm in your library.
What happens if you get a schedule at that moment.
So the two scenarios.
The one is that you are.
A worker that is trying to do the work or you are a worker who is trying to wait for the others to arrive at the barrier.
And in both the cases.
There is a standard VCPU preemption parts that the context gets saved and you will be.
You will start from that context when you are scheduled back again.
So that is already happening.
And it does not change anything about the approach.
So preemption.
Yes.
Preemption are inefficiency for other words that is true.
Okay.
Time is up.
Thank you.