So thanks for this opportunity to talk about some research
. Uh Dr Morelli said my name is uh 25th
year here. I heard from somebody that five years
I get free parking that I'm pretty excited about that
. But there's a nice opportunity to talk about some
of the values have been working on recently in the
Centers for Computing, a part of the check center
here in the computer science department. And I found
what I would do actually in some ways, a
fairly high level talks. I want to take almost
a third of the time to do some introductory stuff
, context settings for those of you that are experts
tonight performance computing and computational science, which is the
area that I've worked in for a long time.
Some of this is going to be very familiar to
you, but for those of you that maybe don't
work so much in this area, I think it's
useful to kind of step back A few minutes to
talk about context, talk about where, you know
, history has brought us. And this is what
led me to really focus on on time systems as
the defining characteristic of a lot of the research work
right now in high end systems. So that's sort
of the angle to talk. So after spending 10
or 15 minutes, I'm historical context setting stuff,
then I'm gonna give you two examples of projects that
we've worked down in the last couple of years uh
checks, both of which are examples of runtime systems
, both of which are examples of systems that were
designed to trying to deal with the complexities uh and
the enormous potential of high end computing systems today.
So let's start with some very high level sort of
background stuff as I look back over the work I've
done for the last few decades or whatever. You
know, if I had to simplify it down the
kind of things I've been interested in. I like
things that run fast. I like to like high
performance. I like to think about algorithms and software
and models and implementations and systems that help people solve
important problems. And that's the exciting thing about working
in computational science is that the motivating problems, you
know, the reality of here, that we're interested
in thinking about our, you know, famous problems
that we all care a lot about. The motivation
for designing systems that we try to build at least
an important motivation and historically probably the most important motivation
for the has done things like physical systems. Were
trying to model and understand right kind of modeling uh
interaction of molecules and drugs. Uh Physical engineering systems
, bridges, you know, engines, reactors and
so on and so forth. So it's very easy
to motivate, you know, why we care about
solving these problems. Uh, and most of,
you know, computational science, computational science and engineering
, uh this phrase that's that's become very common over
the last 15 or 20 years, at least kind
of refer to this. Many would say third way
of doing science. And if it's not a third
way, it's certainly a complementary way that complements the
traditional ways that we do science, theoretical ways of
doing science, experimental ways of doing science. Right
? So we build theories way build mathematical models to
try to understand and explain what's going on in a
physical system or some engineering systems. Uh you experiment
well, great things, measure things and way things
and watch things and so on. So, so
computational science uses computing. Uh the fundamentals are a
tool primarily in the guise of simulation uh to understand
science and engineering design better engineers. Right? So
it relies on the theory because we need the mathematical
models, we need a theoretical underpinnings to understand and
describe what's going on, and we need our codes
or simulations to reflect that theory. But it's also
very much like experimental in the sense that sort of
virtual experiments. Right? So instead of going out
and measuring the wind speed in the middle of the
hurricane by holding up your hand or whatever, we
computed and simulated the computer and computer. Okay,
so most of you all know this, and if
you think about how computational science works, you know
, there's there's very little levels of abstraction that people
have to work at. Uh There's different components,
you need different kinds of expertise, uh and one
of their own challenges in doing good computational science and
then applying high end systems, high performance computing systems
to these sorts of problems Is to avoid the kind
of natural, understandable tendency to just be an expert
in one little corner to only think about one of
these boxes. One of the challenges to try to
build expertise and bring groups together and train students that
can work their way up and down this sort of
, you know, seven abstractions here, nobody is
going to be an expert in all these things.
But one of the things we're trying to do checks
is to is to train people and work with people
that can be experts in building hbc sis but understand
enough about the issues up here to do it well
to do it better. Right. So I had
to provide some feedback because obviously there has to be
feedback and all this stuff. Okay, so just
very quickly, right, we're interested in some kind
of reality that were trying to model we have to
, we have to somehow abstracted or representative Michael math
models generically distraction typically involving mathematics to describe what's going
on. That reality that has to be turned into
out somehow that can solve or deal with or represent
these models, which has to be turned into actual
codes. That particular machine, right. Which has
to run on resources which generate results. And then
obviously this is all right. As we get feedback
. Um, so I've enjoyed working in this area
. As I say, motivated problems are really interesting
and important, but you get to play a lot
of systems that run really fast and that's, that's
an interesting combination. So, uh, our senator
part of checks the center for high end computing systems
and kind of the core reason for checks to exist
down here to think about high end systems, broadly
defined architecture, storage systems, networking software, etcetera
, etcetera, etcetera. But high performance systems motivated
by and in the service you will be arrested this
stuff So insects. We bring together people not only
that I think all day about high performance systems,
but we try to bring together people that have expertise
that they stay up and down. You know,
cascade of a different kind of, that's kind of
the vision of checks. But it's not easy because
not only is there a lot to try to understand
and keep track of people literally use different vocabularies.
People that live in this area as opposed to people
that live here, learn how to talk to each
other. But it's also difficult because the world has
changed, right? So what do you think about
that? We want to think about the challenge of
working productively in this sort of space. Um,
they even ask the question, well, you know
, what do you care about? How do you
build something? If you do what you do an
experiment to build some software, you design a system
. How do you evaluate? How do you say
I did a good job but I did a better
job than you write the obvious question and or said
another way, you know, what's the goal of
the science is done in the lower right hand corner
of the previous diet? So there's lots of different
possible answers to that question. Right? You just
sort of fly through these if all you want to
do is sort of design, you know that shit
or a piece of the processor or a piece of
the system. You might focus on just how fast
can you make this thing Look that's a legitimate answer
to the question is a very narrow answer to the
question, but it's a legitimate answers to the questions
. Or you might run some classic benchmark, right
? Some computational rate, floating point operations per second
and eventually this is a classic impact benchmark that many
of you have heard. That's one example. That's
the one that's used to rank the so called top
500 machines that are done every six months or so
. So that's a possible answer the question. Or
you might say, well I don't care about the
impact. You know, nobody gets paid too little
impact. Typically what I really care about is some
other set of applications, some sweet benchmark for some
sweet of real applications and real data. Let's see
how well this system runs on that. And so
in our field, people spend a lot of time
designing good sets of applications that the Department of Energy
cares about, that. Homeland Security cares about that
other sorts of applications that take care. You might
have a completely different view of the world. You
might think more in terms of I have this resource
, I have this data center. Big question.
I have the grid, whatever this cloud resource.
And what I care about is keeping it busy.
Maybe that's that's why I care about it from the
manager of that data centre and I'm making money as
a function of how much work I do. Right
. So utilization might be a reasonable metric or some
measure of the rate at which I finished. All
right. So what kind of jobs per day or
whatever? So perfectly reasonable thing to do might lead
you to a different view of how you design that
system, right? Than some of the other,
some of the other better. Uh or you might
care about human beings, right. This is a
really important this is a really important conditions. So
you spend a lot of time thinking about how can
we help people build systems that are even your use
right? Or build software that's easier to use and
debug into and re factor and extend and expand.
Right? So lots of important issues that come from
the software engineering community to help us get worked on
more quickly. Uh or if you set a theoretical
point of view, especially the algorithm section, we
still absolutely need to do, you know, traditional
complexity announced at the end of the day, that
algorithm, you know, and then square that was
Well, again, I know that's what I'm betting
that. Right. That's still a hugely important distinction
that we have to keep in mind when you think
about doing computational science. Uh or is that uh
would like to talk about time to discover a lot
of people do actually. And at the end of
the day, if you think about the upper left
corner of my previous diagram, what I really care
about is how good are my answers, you know
, and how quickly can I stuff. Sometimes it's
hard to quantify, but that's really about a month
. Right. For the science, they don't really
care about your box, they don't really care even
about your beautiful, you know, software framework or
whatever they want to know. Can I predict where
the hurricane is going to strike, you know,
by tomorrow? Or is it gonna take me a
week in which case is used to state? It's
pretty hard. So lots of different ways to think
about this, leading to lots of different concerns.
All this stuff is important in certain contexts. And
the trick is to keep, you know, the
right for a weighted combination of these things in mind
as you design and evaluate. Uh just and then
it goes more recently, we've gotten because of the
power issues. If all these things are raised,
you know, range per second per second scientific results
for a second, maybe per second isn't the right
denominator, right. Maybe the right denominator is some
measure of energy, your money or something. That's
actually the case, especially in the largest system today
. And this is why uh DR Cameron, thank
you from the degree problem which asks the question,
not even the fastest, who's sort of the fastest
for a lot of the fastest, dual, very
important issue. So lots of different ways to look
at what's useful, what's important uh higher computing and
computational science. And so I wanted to give you
the background and let me just take one other take
. And and this is this is where, you
know, I told Dennis it's like I put the
word beast in the title. And then I started
working on the slide and my my beast. I
don't know. I probably should have called it a
fall or or an amorphous suit or something like that
. But I was trying to suggest that, you
know, beast like in a sense of very powerful
, but a little hard to deal with sometimes.
All right, So let me, let me just
back up. This is like historical confession time or
whatever. So, I'm I'm a surprisingly old guy
who actually, I taught a class when I was
a graduate student where the student's used punch cards.
So that was pretty exciting. I have no idea
what I was doing, but it was those were
the days, let me tell you. Um but
anyway, when I was climbing in this business and
we did a high performance computing in hindsight, the
world Australia soon, right compared to what it is
now. And this is kind of gets me to
my, you know, sort of pieces of why
runtime systems are so much more important today than they
were to say 25 or 30 years ago. So
when I got it business, if we needed to
do work, uh we had some kind of model
, right? My own dissertation work was in pe
based personal differential based models, classics or mathematical way
to represent a lot of what's going on in nature
. So we had probably models. We had our
we spent a lot of time and we spoke today
figuring out better algorithms to approximate american solutions to pds
. We had people, you know, that book
code, we're trying basically a little bit, you
know, very sophisticated compilers. Uh we had,
you know, we have furry models, obviously we
thought about how to write this code and what it
meant tactically and semantically and so on. We had
no pilot sophisticated compiler first empires that were written for
the first vector machines, for example, the craze
. There was a lot of fancy stuff in there
. No question about it. A lot of intellectual
energy went into the building and then we must have
machines. Yes, we did. And you know
, there we go. We ran codes. We
sort of we sort of got cold to them over
the fence. They ran we got the answer back
. Uh and that was it. A lot of
interesting science was done. Very important work was done
. Well then we started getting a little more sophisticated
, We noticed, you know, well, machines
are changing a little bit. A lot of people
are writing code. So let's be a little fancier
about reusing codes and uh you know, libraries right
. And portability and performance portability and correctness portability.
So we started getting a little fancier in terms of
mathematical software back in the seventies and eighties and those
were important and useful issues. Well then we started
noticing that the machines change and change and change.
Guess what performance change. Right. The scale goes
up as a capability of the machines increases and as
the sort of architecture in the machines changes different kinds
of parallelism, different kinds of networks suddenly performance can
really change a lot. You know very important some
area and I perform this community this performance measuring performance
modeling, performance tuning all that sort of that sort
of stuff. And you start to start to hear
, you know, we have even more runtime health
at this point so let's see what else happened.
So then obviously there's always been data issues. You
had input data. We had a complicated but as
most of you know the last you know five years
or so what we live in the era of the
data data Right? So that data is really our
first order of concern in terms of how you're gonna
move what you need, how you're going to store
what you generate, you can't generate as much as
you want to because there's nowhere to put it,
you know, there's all kinds of issues with data
now that weren't as much of a concern, certainly
20 or 30 years. Uh and then then we
get into things like you know how we're gonna deal
with that data, we can't just look at numbers
this it's alright, became a huge and important research
area. Maybe even more broadly we can talk about
analytics today. Data money issues and so on and
so forth to deal with this data. Uh And
then another thing I want to mention is that the
whole, you know, the fact that I'm running
a big resource that involves other users and other jobs
becomes more and more of an issue right back in
the day, we want to share systems and so
on. But as a sort of scope scale and
heterogeneity of the systems were running on, get bigger
, probably should have said job management or something.
Right. Because nowadays some of our largest uh applications
and you know, problems are simulated on re resources
, you know, big resources that consist of literally
physically distributed stuff, lots of different, you know
, storage here is here, you know, clusters
here, various other machines here and that becomes an
issue. It's not just here run my job where
, I guess the question, where is my job
money and who's keeping track of it? And who's
making sure that the right data gets to the right
place at the right time and who's making sure,
you know, that the right people can see the
data and the wrong people cannot see the data,
right? That's becoming a huge issue nowadays, as
we do these big distributed sort of applications and,
you know, even more like human beings. Again
, so we got people running the data, we've
got various other users, we got people paying the
bill. All these things are now on the table
as we think about buying, compute and you can't
people on your head at once, but you start
to see this trend and I guess I just put
it down as uh, enter a little power and
that's becoming a huge issue as well. So in
the abstract, right next to the other things,
You know, paul cars, uh just parallelism issues
, low balance, that kind of thing. Uh
certainly uh power management and having algorithms and systems that
are more efficient with respect to power. All these
things need runtime up. All right, all these
things can benefit, let's at least say from one
time, right. If you restrict yourself to kind
of the way we work three years ago and said
, I'm writing a pilot chuck it over the fence
that's gonna run and get my answer back. You
can't really deal with a lot of these new issues
nearly as well. So there's a really strong trend
over the last uh describe with decades now, but
certainly in the last 5 to 10 years, especially
to think about doing more and more and more money
. Okay, When you can take advantage of reveal
with the potential, uh, both good and bad
uh, inherent in this sort of suit doesn't look
like it looks like a small uh power. Okay
, one more ticket this and it's the same diagram
I had before. But I think about, you
know what runtime systems and this is a little bit
being the dead horses with the beast. Uh,
but what I want to do, it sounds like
a couple of themes that are common across that,
that far with that beast that I have the previous
. Uh, the two themes are uh, scale
and energy, but that's really characterized italian systems today
and, and drives this need to do fancy stuff
. Everything's alright. Simple idea. Most of you
know, all this stuff. But by scale I
simply mean more uh Right. The more right.
It's obvious down here. Right. Systems themselves are
getting very, very big in terms of core counts
, the amount of memory is not a power consumed
. Any measure you want to take. The largest
systems today have just ridiculously huge feature count numbers of
things that you have to marshall that you have to
keep track of, that. You have to tolerate
failure in. Right? So, so scale is
a problem, but it's still everywhere. Modern computational
science is really defined by bringing more things together at
every level so that for example, just pick a
couple here. So, so nowadays, a really
important area up here is what's called multi physics or
multi scale modeling. Right? So that we try
to stimulate systems not just that one physical scale or
one time scale, but we try to link together
more than one physical scale or more than one time
scale. Because some of the physics of some of
the chemistry makes sense to track at one scale,
you know, one time scale or one space scale
. Others make sense to track with another state.
Alright, so dr Sanders does atmospheric model and a
lot of the atmospheric model. And you can get
away with discrimination that is splitting up the atmosphere into
distances that might be many kilometers, Right? If
you want just average things like wind speed or content
of certain uh certain features in the atmosphere, you
get away with multiple kilometers, you can destroy the
United States with a few 100,000 points or something in
the atmosphere of others. But other things in those
models are chemistry and chemistry, and the length of
a collaborator doesn't make any sense. Right? Chemistry
, you got to be found in a much smaller
scale. So you got throughout a link, you
can't drive the whole simulation at the size of the
molecule. That time simulation ridiculous debate. But some
of the simulation has to be done on the side
of the model. Right? So that's a challenge
. You think you have two different kinds of math
, two different kinds of colours, Probably multiple kinds
of algorithms, they all have to somehow be linked
together. This is a challenging problem. You just
throw all that together and make it work. Is
challenging. Mathematically challenging, algorithmic lee is very challenging
from a software engineering and I'm going to do as
well. That's what I mean by state. Just
as an aside, you can bug Akari later.
Uh one of the cool things that people do the
ideas is something called poly algorithmic Memphis. The ideas
that you have a challenging problem and on a particular
days that you literally don't know ahead of time which
of four or five or six algorithms or flavors of
algorithms, it's gonna work best for that computation or
it's gonna work best for the next time step of
that calculation. So. All right. But the
framework as sort of a side project that does something
called speculative execution, that's a really slick idea.
You have the first one to do it. This
framework doesn't really slick. Right. Basically, it's
a nice way to exploit some parallels. You just
fire up all five of your candidate algorithms and somehow
you think the winner and you kill the other place
. Right. What could be easier? Well,
there's some really subtle issues about shared memories, for
example, because you want the world after four of
them are killed and one survives. You want the
world would look like as the state of the machines
that look like only the winner ever executed and the
other four never happened. All right. So that's
kind of a little things expected execution. You can
part of the product. Uh, but that's an
example of scale and Hetero today. Right. We
have four or five different algorithms are all very different
, but we want to combine them somehow. You
all know the story about heterogeneity here, Right.
Use and various other certainly accelerators made our age systems
very ingenious. Uh, we're trying to link all
that together. Uh, everywhere here. I could
talk for a long time. The point is that
dealing with that originated, dealing with that Scale introduced
a lot of things that I really need to do
at one time. I really cannot figure out how
to marshal all this stuff together, how to react
to what's going on a particular run a particular data
set unless I have some capabilities that allow me to
make that one. That's the idea. Okay.
Nothing controversial there. It's just that it kind of
helps explain why in places like the check center,
in other places we spend most of our time building
sometimes. Alright, as an important component of this
. Uh Uh what about that? That is a
real example. So, so these are two projects
that we worked on over the last 3 to 4
years, something like that. The second is still
very much on going on the first one student graduated
and they're still not interesting work to do there.
Let me let me take uh 15 or 20 minutes
on these. So what is the ST paul about
first of all, it's working with just two sides
of the case. The students graduated a couple years
ago. Okay, come out. Uh This is
a city located in the beast here. This is
my same diagramming in. You can't do everything at
once. All right. So what this focuses on
is the runtime system. This focuses on uh first
of all sort of system stakeholders, and what we
have in mind here in particular is people that design
and sort of oversee queuing system, basically. Right
. A big high end systems questions, for example
, uh back system you submit jobs and somehow this
queuing system decide who runs next to. All Right
. So there's there's a lot of interesting questions about
how to actually do that much study titled uh so
that's kind of where this is located in the business
of uh curing systems, taking advantage of what's going
on on the machine, uh and then reflecting hopefully
some insights in the performance, which we can only
tell which we're gonna we're gonna do at runtime,
we're gonna try to attempt to reflect in our decisions
what's actually going on in the machine. Uh and
we're trying to take a reflect anyway, we're trying
to reflect common programming models that people use new sciences
. All right, So we're ignoring the rest of
the world. You have to do something. So
let me, let me uh it's gonna be a
fairly high little presentation. What I want to get
across is kind of what the issues are. Uh
what was the motivation is what the issues are that
we have to solve here and a little bit about
how we did it and sort of weird and the
benefit that you get. So very simple motivated observations
. Okay, so clusters are a big deal.
Uh if you go to the top 500 list,
85% probably are clusters. Right? We all know
this. Uh So most of the biggest systems nowadays
are built out a fairly common components interconnected by some
high end network. So it's a very important architecture
in high end computing, not to mention another data
center. So the other observation is that, uh
, clusters, you know, something came from Washington
system 10 days. You know, we have a
machine called system, we've been messing around from eight
or nine years now. And the thing has the
following property. Typically you see us another day to
another client computing senators to, um, there's always
jobs waiting in the queue essentially. Right. There's
plenty of work for these questions to do, but
it's rarely 100% utilized, you know, so there's
a realization of 357 10 11%. 20 little numbers
like that. Not a big deal. Yes.
You know, another big deal. Right. On
the one hand, 10% is a big deal.
On the other hand, 10% of 10,000 cores is
a really big deal. You know why? Why
am I throwing away 10% of my utilization. Okay
, well the reason is if you look at the
job mix on these machines, it's pretty easy to
see why there's jobs waiting even though there's unused knows
because those jobs need more nose than our bills.
Usually run jobs on a big cluster because what you
need a lot of you only needed three knows why
are you using this gigantic system? Right. So
the jobs waiting tend to either need more notes than
are available or there's other constraints. Virtually every queuing
system and every policy has various per user constraints.
So they're gonna be somebody stuck in the queue only
wants 10 cars. But that guy has already got
four jobs running in the system, will not remember
them for jobs because then you'll take off all the
other. So there's always these policies that perfectly understandable
policies that caused unnecessary utilization in many ways we have
the real data from assistance and other other clusters to
show. Uh, the other observation is that most
, I would say essentially all clusters, scheduling queuing
systems are stacked in the sense that when a job
arrives, the user says, I would like this
job to run on X number. Of course I
would like this job run on 40 course by the
way, I Corps notes or entertainment. I don't
care units of hardware that I need for this.
Uh, this job. So it's static in the
sense that the system when it launches that job but
only does. So when you can find those 40
courts, the courts or whatever they wanted. And
then I did static in the sense that never changed
job runs until it finishes on those 40 process.
That's what I mean. My staff Okay. But
the thing is, it doesn't have to be that
way then I would say most, but many uh
actually most, most uh most parallel on high end
systems have a property that uh there at least what's
called Moldable, I have a word malleable up here
uh in the business is a term Moldable for a
job that at launch time when it starts could actually
run on more or less any number of processes.
Okay. Now, maybe not literally, but it's
going to be written distributed and recode FBI code or
whatever. Right. The typical first thing you do
in the front and you find out how many tasks
, how many processes are associated with this run and
then you do the right thing. You split up
the day you split up the work by that meeting
by that fact. So the code itself will typically
we're trying you started on 20 processors or just started
on 30 or just started out for that old?
Less common because you can't do it. And then
you find in systems any current system less common is
to have an FBI code distributed in the code that
where the number of processors can change dynamically. That's
where we're headed, right for the number of processors
can change at runtime so that they can start on
the 40 and then expand for a while to 60
. Maybe expand the 70 for a while and shrink
back to 25. Okay, that's less common.
So that's kind of where we're headed here, is
to ask the question, could that happen more often
? Is there any sort of inherent deep reason?
Codes or an algorithm that that couldn't happen? Often
? The answer is no. Uh or is there
something just technical, you know, sort of engineering
reason why it's not done? All right. That's
kind of where this research I started. Um So
uh actually one of the only emphasize here. So
if the answer to this question is the question,
if this claim is true, that is that many
co it could be resized? We call it.
I think the thing is running on some set of
processes. If it's true that the job could be
resized dynamically. Um that kind of begs the question
uh to what should it be recycled? Alright.
It's one thing to say. I have an infrastructure
, I have an execution model um that allows,
you know, the number of threads of execution to
change processes to change at runtime. It's another thing
to say. And here's what you should run it
. Right. Should I go to 40? Should
I go to seventies? Should I go back to
20? Good question. So that's kind of where
this research started. Uh to what extent can we
make job's valuable and then what advantage can we take
? That's the basic So let me say a little
more about that last point is degree of parallels.
But I mean, how many cores? So many
processes? Uh so so important fact, the degree
of parallelism. The number of processors let's say that
I give to you uh in practice, you know
, how is this question answered? How is the
question? How many quarters do I get? How
many how many processes? And in fact, if
you go out and you're honest and you look at
like real close running on real systems. It's answered
lots of funky with uh for example, uh theoretician
will say, well, the number of processors paper
, What's right? And that's a good answer.
If you're doing there, it's actually the radio.
So I'm not complexity analysis and you ask me how
big the problem is, I want to say.
And and if I'm doing parallel complexity analysis that you
asked me how many processors there are gonna be next
question, good answer. Uh but I need more
when I'm running on a real system that has 1206
process P isn't so the greedy answer as many as
I can. That sounds like a smart comment,
but it's the right answer. If you know,
if I have a machine to myself, maybe some
share. Remember machine or some small clusters. There
are 16 processors, I have some work to do
and I know runs finance 16 prices and I'm just
gonna take. All right. So there's not really
a question there. It's more than enough question.
If I'm on a big share resources where I have
a bunch of jobs running and maybe some unused cores
unused process, then it becomes more interesting question.
How do you answer that? Well, sometimes you
have some algorithmic constraints. Right. Particular algorithm.
Maybe you have some one answer might be 5 42
something, but one answer might be might be that
the algorithm itself, you know, is based on
some functional parallelism. Right? Some task parallelism where
there's literally five different things that could be done at
the same time. You know, five threads or
processes that could run a private. That's it.
So that happens. Um other times you have an
algorithm constraint that that's based on maybe the date of
the composition of the communication pattern on your algorithm that
it runs really sweetly or any runs at all.
Only if you have a power of two number of
processors right there there is a lot of FFT algorithms
that if you run on anything other than a power
to do some clues, the things that basically pretend
they're on a product. So you might be running
on the property or it needs to be a perfect
square or cube or whatever. So there are constraints
like that. A lot of algorithms have they prefer
sir, the numbers of processors or certain properties that
that set a process which had. Uh but honestly
, you know, if you look at most of
them, if you go to the real data on
the real systems and you ask people which I've done
right to submit set at 64 they say, well
, you know, the graduate graduate student graduated last
year, that's what, that's what she always managed
to uh You know, or more more realistic.
Look at this right here, it's I know this
thing will run great at 200 processors. If I
asked for 200 process, will be stuck in the
queue for 48 hours. If I asked for 100
processors, I'll be stuck in the queue for X
hours. But if I ask for 60 processes,
I know I get through in about an hour.
So there's no science there at all. It's just
add experiential knowledge. I think we're going to grow
up with it. Okay. But it seems like
people, a lot of it, it seems like
you can do a lot better if you take advantage
of what could be known at runtime. And that's
kind of the point of this research is to think
about, you know, sort of context aware,
dynamically determined at runtime, answer to the question,
How many process should this job run on, you
know now? And I'm gonna ask you get an
hour, should it change? Right? What should
it depend that sort of generically? It seems like
it ought to depend on all this stuff, Right
? But also depend on the job itself. By
that. I mean, the code that's running the
particular data set it's running on. Maybe there's some
user priority queueing systems have some priority schemes that are
functional. How long you been weighing how much money
you pay? Who, you know, who knows
how this works. But there are priority schemes.
Um, and then even potentially if we could somehow
base our decision on some performance information. All right
. This is where it starts to get interesting because
one can imagine all things being equal. If I
have two jobs, that would be very glad to
absorb those 3 40 cores, those 3 40 prosecutors
, Maybe I should favor the one that can actually
use those 40 cores better than the other. Alright
. Or if I have to squeeze somebody to make
room for somebody else is paying my money. Maybe
I should squeeze the one who will be hurt less
by being squeezed. These are questions you can start
to answer if you have some clue about parallel performance
of the job running now on that machine, along
with who else is running on that machine. That's
what I mean by the lower right job and job
to job. Okay. If I have information which
is in the job doesn't have but the queuing system
, the manager doesn't uh, maybe I can take
that into account obviously what machine and time matters what
time it is. Right. We have policies that
actually a function of. What time did you have
a policy that did something different in the middle of
the night or on weekends? Then during the day
you can tune the policies and the ones we have
now to do things like favor will jobs during the
day because people hate to wait. They gotta run
something that's only supposed to take 10 minute. But
if you're gonna run finishing to stay awake kind of
big deal, they made a few hours, you
know, they go on vacation with uh and honestly
policies, how you, how you set up the
system that, so this is kind of our approach
and we're really just scratching the surface to try to
dynamically the runtime system, building some ability to not
just resize the applications, but resize them in a
way that made some sense. I mean, some
people All right, so very quick. That's gonna
take a few more minutes. You know, talk
about the, you know, what what are some
things? We don't let me just sort of uh
list them all here. Um so we spent a
lot of time thinking about just this is even not
work, but what set of codes you can actually
do this because if you start it all about distributed
memory, computing, done FBI programming, you ought
to have a couple of questions. First of all
, doesn't work actually start more processes that time.
If you're FBI expert, the answer is yes.
If you're running FBI to something called FBI spawned,
that allows your runtime to actually generate more prostheses.
If you're curing system cooperates and gives you more,
of course, uh and then you can build a
new, you know, mp Icom world, you
know what I mean? That that consists of a
full set of processes. Uh more challenging thing is
gonna move today, distributed every machine. And so
you go from P to Q processors, right?
You've got to redistribute day so that can contribute to
the application part of the research, see for what
kind of applications could do that, you know,
under what situations could do that and what situations not
. So, uh and then if you can do
it, you can do it, you know,
once a week, what's the better? And there's
some sort of typical things you already mentioned uh based
on runtime performance, you can do clever things like
depending on policies, you can try to schedule waiting
jobs and squeezing in sooner by shrinking some other guys
. You can expand some guys who need to finish
by some deadline. You know, lots of things
you can do if you have the ability to decide
. So that was sort of the focus of research
. This thing that the prototype just you call it
, reshaped the obligatory forced accident, uh re sizing
and scheduling and homogeneous applications environment. Let me pull
disco full disclosure. Let me just mention homogeneous is
an important assumption here. So the first for the
simple version that we build, we make progress,
but I want to make one very important simplifying assumptions
. Which which is realistic, but it's not as
general as we like. And that is that we're
only able to do something useful with, first of
all long running applications. Doesn't make sense. That
be thrashing around changing the number of processors for something
that runs from milliseconds or even seconds. Probably we're
targeting scientific applications that run for hours, days and
not weeks. Very common. So the overhead of
moving data around, uh there's a barrier that says
, hold on, we need to move from P
to q processors. There's no synchronization in there.
There's overhead there. But in the context it's not
the kind of thing to do in a few seconds
, that kind of thing you do every 10,
20 minutes every hour, whatever a run that lasted
a day or two. We're talking about large scale
computation. But the other important assumption, these are
computations that are characterized by being very homogeneous in the
sense that they do kind of the same thing over
and over again. Very common scientific simulations. Classic
example, get time dependent situation, right? So
if you look at the computation is doing the same
thing essentially over and over again for thousands or hundreds
of thousands of time steps. So there's some outer
look, the guts of Bush computational is more or
less the same every time. If you don't have
that, you have that. Then you can Christopher
the performance evaluation stuff, the performance measuring stuff.
It's a big win, right? Because if you
know where that is. You know that the way
the system works is the code, a simple api
code actually has to call back to the to reshape
server essentially reshaped demon every so often and the code
has to agree that it's calling back everything it calls
back. It's about the same model of computation.
That's what uh that's the typical use cases you stick
in this call, you know, like the bottom
of your time step for every 10 generations of your
time step or whatever you call, reshaped and say
, here, I am appreciate says, oh,
you know, I assume you've got about the same
amount of work since last time you checked in and
if I no work and no time I can really
, you know, of course, that's useful estimates
of how productively you're using the course that I gave
. All right. So that's the that's the simplifying
assumption that we did that we use here. And
then we look at some real app that allows us
to do this and he in his system, spends
a lot of time thinking about how to do the
scheduling. You know, once I had this capability
, what are some fancy things I can do and
then how to move data around when you resize from
P to Q process. But I'm not going to
go to a architecture and we don't have time to
talk about that. Let me uh let me just
show you a couple results and then I'll spend 10
minutes on the other one and rocks get nervous.
It works not getting any air time here, but
the kind of experience, you know, hundreds,
hundreds experiments. But basically the kind of things we
look at, we look at different strategies. So
static scheduling means the standard thing you do. If
you don't have mainly ability, you don't have the
sides of the standards are first come for sure.
Backfill standard sort of stuff. You money simple.
We're not actually cases with synthetic benchmarks with like I
think 120 jobs, 400 cores of system G.
And we're running over and over again in a different
arrival borders and different arrival times and all sorts of
stuff. And we look at this is just this
is just average job completion time across the so called
large jobs, medium jobs and a small job that's
like green tea and you get some measure of the
wind and it's not dramatic. You know, the
differences here, so lower is better. Uh the
differences here are, you know, 5 10 15
20% in some cases between the different scenario that you
can find here, but they're very different than what
you care about. So some of them, for
example, are really good at getting small jobs through
as quick as possible. So they work really hard
at the small job comes in and he's just eight
cores. It goes to the machine and find the
guy who can best afford to give up a few
cores, squeezes him a little bit, sticks that
a core job and it's really fast and other ones
are not so good at the small jobs, but
a really good job, the long running because for
example, once the job is running, it works
really hard to try to finish that guy as soon
as possible any time, any course come over,
it'll give uh, so lots of battles you've been
through the parameters you can mess with uh once you
have this capability. Uh The other graph here is
a similar one that asked the question. What if
in my mix of jobs, what if they're not
already size it? And I said not all jobs
, maybe I can do this. And so what
this says is if their already sizable, this is
the exact same data from the previous slide with one
of the scenarios. I get these results. If
none of them are recyclable, that's the static case
I get the results. And what this shows is
that even on that quarter or 50% of the jobs
that resided? I start to get a pretty good
uh piece of the potential benefit, uh kind of
what you would expect. But that's a more typical
use case. Right. And that I have this
set of jobs that are coming in, some are
recited somewhere, not just have a few that are
decided to take advantage of the unused project. Alright
, 10 minutes around here, I want to talk
about second project and that's a quick questions about reshape
before uh I catch you at uh exactly what uh
there's other things we can give and take away,
but that's all right. 10 minutes on the distributed
shared memory. So there's a system called Sanskrit.
Word for collection. Thank you very much. Uh
This is basically grass work is in the audience.
You can harass them later. And uh and I
would advise him. So this isn't there distributed shared
memory. It basically pays attention again, runtime system
. And what we're dealing with here is we're dealing
with the fact there's a lot of existing codes and
very comfortable programmers like share and for good reason,
I don't particularly distribute them. Right? So people
write the trends, for example, for lots of
reasons. Uh the question is how are you going
to deal with the conflict on the one hand between
the fact that there's a lot of shared memory codes
out there and the radio is being written is going
up not down because everywhere you look, everything's many
core, this multi core. Right? So every
machine including most of them in this room, at
least two cores. And so there's a lot of
reasons there's a sort of ecosystem where we have a
lot of Sherman recode's insurance programs. But the previous
after the talk we like clusters for economic reasons.
Just like the high end, we build a lot
of customers. We build a lot of distributed memory
machines. So this is an old problem. That
is how can I keep my shared memory semantics and
I shared memory view of the world and run it
over physically distributed memory architecture. This is probably you
were thinking about it for a long time. I
don't know if at 12 05 I really want to
look at this. Uh Let me just uh you
need to look at the numbers. Let me give
you the takeaway point from this from this slide are
last people. We will we actually titled something like
distributed shared memory. Is it time for another look
? Uh The reason we titled at that because it's
a it's an old cop distributed shared memory in the
nineties. There's tons of papers, distributed shared memory
. Uh all those projects did uh did a lot
of interesting things, but it never really made a
big impact. And you know, if you want
to go back and look at the paper off the
website and study this table, what it will tell
you is that back in the nineties, the difference
between how fast you can move a bit across the
network and how fast you can move a bit from
memory to the CPU with dramatic many orders of magnitude
. Okay, well flash forward, especially over the
last 3 to 5 years, networks are getting ridiculously
fast to the point where things we do to uh
, to manage normal memory, main memory, uh
, you can start to play a lot of those
same cars in particular cash, like strategies. You
can start to at least this is our question.
Uh, you can start to play a lot of
the same cars. The same ideas with with the
memory, if you will sitting on the other side
of the networks. All right. When there was
when there were several orders of magnitude difference in latency
across the network versus local memory. That's what those
people ran up against in the nine. But the
world is really quite different now. Okay. Very
legacies are basically stuck. My family has has gotten
better. And of course, we've used that combined
with multilevel memories caches to hide that weight problem,
that memory wall there. But now, as these
guys get increasingly better and if you look at the
road that it's not stopping anytime soon, these numbers
are continuing to get better. A lot of the
same kinds of tricks you use to feed the CPU
using caches or multiple levels of cash from main memory
. You can start to think about doing that across
the at least. That's the conjecture. All right
. So then what you do is you uh you
know, take 4.5, 5 years grass life and
you make them write some really nasty code to see
how well this works. Alright. That's how research
works. You find some really good at writing a
very nasty uh current code and you see what happens
. But more seriously. So yeah, a lot
of sweat doesn't actually designing and implementing this stuff.
It's got another that people you want to take the
shared memory code running on your question. Right?
That's the goal. So a lot of work goes
into that applicability means doesn't perform well. It will
be correct. We have a system not a system
built. You can take a p trade code and
very minimal modification. Very minimal modifications. The kind
you can do with a source to source translated,
but we haven't got doing that. But very minimal
modifications. You can take that Pizza is going to
run on a question. Question is what run?
Well, that's the applicability. So there are some
, you know, if you have, if you
have a pizza really high for lack acquisition rate,
right? And some interlude grabbing a lot, releasing
a lot or lots of barriers. Lots of synchronization
. That thing is going to be a challenge across
the question. All right. Lots of shared memory
codes that have, you know, better properties in
respect of those issues run very, very well.
Once it works, then you can do lots of
fancy things with cashing sorts of issues right back in
the whole game of thinking about eviction policies and affinity
and uh, you know, uh, page size
and profession and all the clever things you can do
with cashing. Well, that's what we can do
here just with larger pages moving literally bigger. Physical
, that's sort of the uh, in the interest
of time. Let me skip ahead if you want
a lot of details about about how this thing is
working with some in the system, which is uh
prototype GSM system that is built, you can talk
to him or meeting afterwards. Um I think what
I want to do then is skip ahead just a
sample of uh well, let me say one thing
about the current, I already said this is that
we're targeting people basically, which is by far the
most common way that people write parallel codes and shared
memory context. Uh you have to think a lot
about so called consistency models. You know, anything
about shared memory programming. You have to answer the
question, you know, when I when I want
to write happens or whatever, some particular piece of
shared data under what conditions, you know, sort
of when can under process these other threads see the
effect of that night. Right. And there's a
very subtle and important issues that have to be defined
. And so this uh, this system actually defines
the new consistency bottles similar to several well known ones
, but it's it's relaxed in a subtle way that
a lot of good performance. And then we have
to provide the usual synchronization stuff that uh, I'm
gonna skip the details about architecture and implementation and let
me just give you just a quick flavor. This
is actually old data. But what we're doing now
is testing this on a bunch of a bunch of
benchmarks, a bunch of codes. Right? So
here's just one simple one. This is actually a
year old now. So this is uh this is
Elliot. This is basically the cost elimination. Right
? The same thing that uh and what we're comparing
here is uh shared memory, code, red code
run over, sending to All right. On a
cluster up to 256 course uh cluster. So in
this particular cluster that was probably uh 30 to 60
. But across the question and then what we're showing
here is computational rate. This is so called the
scaling. And what do you know what that means
? All we're doing is we're measuring how fast this
code computing answers. And as we scaling and what
that means is as you increase the number, of
course, as you move across the diagram, the
size of the problem actually gets bigger to sort of
fill up however much of the machine because you're solving
a bigger problem here that you are here. But
we're measuring is the rate at which I'm computing answer
. All right. And what you want to see
is that the number of course doubles the computational rate
More or less, you see, actually kind of
intuitively uh that attracts the standard scale back album and
this is NPR Green tries to scale back out just
fine, actually passes it here, but that's a
little screwy because what's going on here is this is
joining about, Tell you this is what's called a
11 D one dimensional decomposition of the data. Three
people here know what that means. Um And it's
well known that that thing, it's kind of a
scalability uh me sooner than two D. What's a
little weird and we're gonna hit it eventually, but
we hit it later than the M P versus Np
is doing some unnecessary buffering and so on that.
We, you know, we talk straight to the
incredible and we missed. So we actually this thing
actually scales better on me than it does over NPR
. We don't see that in most other applications.
Uh but we are, this is as far as
we know, this is the biggest and we can
have a bigger amount. This is the biggest uh
GSM system that anybody can run. Okay, so
now we're in a very exciting time because we're able
to run lots of different benchmarks and sort of to
this day and start playing with the cash and so
on. All right. I want you all to
long uh let me just stop right there and I
hope that I can be a little flavor of,
you know, the kinds of things we're working on
, you know, try to deal with this complexity
to try to deal with the fact that a lot
of things going on that we can't do anything about
it. We don't want anything about until we're actually
running on the hardware and uh how's that? So
a lot of examples that you have situations, I
think the one that works best is you still focus
on the small dose, uh, at least today
, we've seen, in other words, as long
as you're kind of, it's almost like, uh
, you know, cholesterol in your veins or whatever
. As long as you can clean out, clean
out these small jobs that tend to fill up the
queue. The big jobs that are going to run
for days or whatever If they're waiting time. So
that's the problem is queuing time is waiting to like
, it's a queuing time with a delay of a
large job increases by 30 minutes. It's not a
big deal because they're going to run for two days
. So 30 minutes out of two days isn't a
big deal, but the small job is really gonna
run for 10 minutes and they have a waiting time
of 30 minutes relatively speaking. That's a lot of
pain for the small down. But the answer is
completely, technically the answer is somewhat psychological. You
wanna, it's a user experience questions, right?
And they users submitting a small job expects an answer
back quickly. So if you think about anxiety and
the user, it's easier to to annoy the person
submitting a large job a little bit, the person's
psychological. Sure, well, the first thing first
out plus going through something called backfield. So what
actually means is even if the big job is,
you know, there's little jobs after that that the
schedule can put in the system without affecting the predicted
start time of that big job schedule will do that
. So it's not strictly its first in first out
plus some kind of backfill, which means you take
guys that are further down the queue and stick them
in it. It's not strictly, you're right.
That would be that would be it. Yeah.