um, today I'm going to talk about dynamic
Optimizations for irregular application on many core architectures. So
Before I get started, I want to give you
, an idea, um, a high level idea of
what I have been doing in the past. So
nowadays we're enjoying the benefits of technology and
investors in architecture. We have been increasing parallelism in
different devices from handheld devices to hand paint into medical
supercomputers and were being more and more technology. The
benefits such as a non volatile memory space, change
memory of breeding memory and in memory computing. However
, uh, so this is the hardware died from
the software side. So, um, we have
the program, uh, this is a structure programmer
. So not only has to deal with all these
different heads of computing devices, it has a programming
models, other programming languages, but there is a
problem in the problem, which is how can you
turn this potential, the huge, potentially hard work
into real stuff world woman. Okay, so,
um, most of the time the peak performance that
can be provided by the hardware doesn't equal to the
real moment we could get when we run and that
want to run the uh, software. So my
world has been long um, providing smart programming support
for remembers and for them to develop uh, efficient
applications that work to the advantage of the exciting advantage
in technology war, etcetera. Okay. Uh,
so, uh, so far I worked on three
major project. So the first one is about optimizing
the irregular G. P. Applications. And the
second one is about non uniform has shared aware program
program and the third one is about cross issues dad
application. And I'm going to talk about the first
one. Number is today. Oh, and I
want a briefly about the other two. All right
. So, um, why would like to use
as a platform for my research? So there are
three reasons. So, first of all, if
you have a massive power so hire me if you
car today we can do it achieved over 500 device
pick a lock for over and over 1 117 device
the second memory families and also give us are costing
visions and power stations for example, the hopeless feeling
. Uh, excellent example. That shows how deep
you can be used to help serve the energy and
also help improve the performance in high performance computing community
and uh, certainly Gpus everywhere we have them in
the tablet. We can have some cell phone uh
, helping them, you know, uh, personal
computers, they can one can be used for graphics
rendering and on the other hand, is to accelerate
general purpose applications. Um, so, so,
uh, most important reason I want to work on
GPS is that so, uh, so november 2011
, three of the world's fastest computers are used,
the CPU GPS system. And if we're careful that
looked at the performance of impact on the super computers
. So the average, the average performance that we
can get out in time for the Gpu business system
is 48 percent of the people performance. And for
the city of basic, uh, several computer so
we can get 80% of the components. So you
see, there is a gap between the real performance
to get in the peak performance potential all this system
. Um, so, uh, next, I'm
going to tell you a little bit about Gpu execution
model. So there are many immigrants on the stand
by, uh, many uh, vector processing so
that the process of hearing, uh, streaming multiple
center and in the process of the threat uh,
in parallel and have to execute the send instructions like
Cindy at the make model. And this is a
group of threat that run in the same fashion,
which means they run exactly one instruction a time called
a walk and many walks a master to this.
Uh used to run continuously and our contact switching which
uh frequently to hide relation to uh memory, latency
and communication. Uh and this is a typical gpu
from called we write it included. Uh so we
specify the block which is uh so uh so I
got introduced. So look out for the organized into
blocks and the blocks of flats are the minimal are
synchronization unit that can be uh maid enabled by hard
work. So when we write a function we have
to specify the block side. We have to specify
how many threads on the block and the grade means
how many blocks we want to know what we want
to run this broken assumptions. And then we have
this regular parameters like when you uh feel depressed.
So there are two major problems in Gpu computing that
prevent developers from, we went to lake take advantage
of this massive methodology of them in your view.
So the first problem is irregular memory access patterns.
So here, if we assume even walk, therefore
fled. And also every time we initialize a back
channel from the memory. So we assume a memory
segment has recorded a limit. So every time of
western Look. Gordon Levitt. Um, so if
we have a regular, remember except I didn't like
a P I D P uh 0127 can do that
for everyone. We all have to load uh mangal
. However, if we have memory expect pattern like
this and you can see that for the first of
all we access data that that is scattered into two
memory sentiment and similar to the second world. So
now we have to have to initiate for memory load
for this thread walk which is uh twice in the
afternoon we have in the second problem is the control
that wasn't a problem. So still assume we have
a whole thread in the world and on the right
hand side, I show you the product is the
value of A. It's not very well that it
will actually put some segments in this racket. And
if you have the values of ray A from a
zero to a three, uh you will find that
all the elements are there except one, the third
threat. And so all of the third thread will
perform some computation and moving meanwhile all the other threat
of the other risk that the world will remain.
I don't Okay, so uh the rules have similar
problems. So if the number of directions a lot
depends on the value, then we can have problems
. Some um some recognized it may not be executing
any instructions at all and the I don't waiting and
we have intellectual processing cycles. So in the worst
case the circles may be degraded by all kinds and
what the outside world is typical, especially to uh
more than you actually. Uh Okay, so uh
this irregular memory effect has happened in this control divergent
happened. Uh Is this commonly in scientific applications?
Uh for example, CFC uh DNA sequence analysis tool
, um Data mining applications. On the right hand
side, on the left hand side, on your
right side. I'll show you could benefit from the
media about benchmark suite, which is in error correction
application and there are many next in branches that cause
divergence which becomes a serious problem for this particular application
. And on the left hand side of this,
uh like I show you the potential. So this
is a hand optimistic. If we uh if we
are offline profile, all the irregular memory talents and
the central beverages, we remove all the irregularities,
how much you can get and for all the benchmarks
which are already optimized, they're uh they're from a
different put a different application Benjamin, we can get
beat up between 1.46 and 5 to 7. So
there is huge potential here um for us to improve
the performance of scientific applications. Okay. Um so
yeah, what was the baseline reference used uh using
the reference point here again. Uh So the original
problem behind uh original Yes, you did that.
All original review applications. Okay. So um President
working a lot of work has been a status of
migration and static analysis of the irregularity and for example
people direction is not really eliminated by the problem is
eliminated uh by uh handle in some special cases.
And so the irregularity because we do not know the
pattern, remember the title of control division. And
then we have to run the program with english.
So the president has never been on proposed a natural
extension and evaluated advice in later studies and they're not
going to come out in the uh anytime sooner in
about 10 years. Okay. So the next question
is, can we do this in a stop to
work way? We remove this irregularity dynamically. You
can talk to us to answer this question. We
have to think about some fundamental. Uh So first
of all, what are the root causes of the
regularity? So what is the relation between rather than
data mapping that can cause this product? And how
can we resolve this problem by doing uh the mapping
? And if we do regular lacking and what are
the best layout we can use? And what is
the complexity of finding a remote hideout? And finally
uh revolving a different type of irregularities may conflict with
each other. If we solve the diversion problem,
we might uh we like to make the correction problem
uh serious. So, so um you start here
uh let me talk about my work on uh completely
software solution which is called the streamline. It doesn't
require an outline providing hardware extensions and it can remove
the irregularity dynamically. And also it provides a unified
transformation solutions to both type of irregularity. And it
consists of three components. The first component. After
the first question I mentioned in the last slide.
So what is the relation between weather and data that
calls this problem? And what can we do?
What transformation transformation techniques we can use to remove this
irregularity. The second component is uh the optimal it
and the approximation component which is this component will provide
the package layout that's going to be used in this
transformation. Uh The third component is the efficiency control
components so that the doctor will approach and in the
long dynamic way. So there's a lot of overhead
. And how can we do the overhead? Um
So just streamline can make the overhead completely transparent in
the system and we can guarantee the original the basic
performance of this program regardless the overhead that could happen
. Okay, so I will first talk about the
transformation components. So in this transformation components we first
realized that both memory and control serabian regularity problem come
from the same reason which is the fighting between threat
and data. That in the damn walk we have
to make the execution has converting assembled all we try
we need to put data obsessed by present assemble coalesced
as elected as possible. Um and another connection between
these two types of uh irregularities is that so uh
if we find a solution for one then we can
use the aphorism for another. Which are going to
talk about using examples. So so basically I'm going
to talk about free technical transformation. So the first
set of transformation is better reordering and the second type
of transformation is uh job working for exporting the job
for the different threat. Five perform transformation on the
red eye. And the first information is a combination
of this. Okay, so this is the example
for data regarding solutions to memory regularity and the uh
here we have all threats in the world and for
this element in a marriage segment. Uh as you
can see that every walk up uh takes very low
. And so if we consider them on walking data
a long and a five then we can remove one
memory low. But first of all and now we
have to remember those together. So using job for
the approach, let's go back to the original case
. If we swapped the drop of a line,
25 of these were walking too much of a threat
and then scale we can get only one memory load
for the first world still to memory to the second
war. So the transformation is basically before the assumption
that's running, we replace the spread ideas with the
new red eyed and other computation and then set that's
going to use by this letter will be inferred from
the thread idea. So the transformation is simple.
Okay, so let's consider the hybrid approach. First
we swap data a zero and a walk and we
have memories that pattern like this and that if we
consider walking drop out thread 01 in 345 Now now
we can achieve the optimal every walk only need to
do one memory load by using hybrid transformation. So
we can apply the similar approach for the development of
the average simulation. So similarly on we have uh
don't buy used before. We have for the first
world that uh a zero to a degree they all
have their very success uh A two and then we
swap in two and a four. Now we make
the threat in every walk access exactly the types of
data which is their own number and there will be
no divisions within every blood work and thinking they're looking
for jobs or square to and spread world and now
we still can make threats upset the fantastic with every
single. Okay also here's the original this to type
text transformation. So job smoking incurs a small transform
NATO. And what we need to do is replace
is but I think with the new thread idea um
after the new great idea uh for however it may
have some satisfaction. The memory patterns may be changed
like in this example the uh the memory changes.
Um so then reorganizing relatively high slash transformation over have
to move it around memory. High rate has also
had the benefit and how separate approaches moved through with
it has the potential uh different transformation apply in different
scenarios. Okay so now I'm going to talk about
the second component. So after we know how can
we move this irregularity by doing a matter how can
we get the best thread data mapping out? How
can we get the best data layout? So this
is what this uh this complains about. Okay,
so I want to share example to show that practical
of um finding awesome money out for data reality.
So you can send example. So if we want
to the first world access to all in the stand
longer segment we'll have to put a 08283 and uh
fight together. And uh okay so for the second
world we also want to have one memory connection.
We have to put uh a two a two a
three a six agreement together. And now they see
a conflict impact of life. We can only have
45 seconds. And then where did I put a
to a respect to do with 6705 So they're accomplished
. So we have proved that uh this is uh
this is a complete problem, difficult problem and also
opinion for the central every problem when the conflict it's
also np complete. So we propose heuristic space approaches
. So the data gathering, we apply data packing
like approaches. So we basically have the data that
accepted by the sample. And then when they're uh
different possible duplication, we use the parameters to control
the amount of duplication has to use. So we
are using uh most straight to help alleviate this problem
. And this is a proclamation approach And for the
control of urgent problems. So we propose something called
active factor. We should move in this path vector
, every element visit by which branch uh this regular
tape. And then we will be starting based based
on this rest. Better. Okay. So now
if we uh look at their work out so this
is the potential and then if we can deal with
the overhead and then we perform all the transformation for
the different uh page. As you can see that
always three benchmark can benefit from such a transformation.
Um so one little bit that one into the baseline
. And for the other four applications we actually experience
theories slow down. Um So the next question is
how can we meaning Michael? Yes. Uh Yes
. Uh Yeah and also there's you know, a
approximation case basically well, you know the you know
everything? Yes. Okay. Okay. So this
brings me to the next component which is about uh
efficiently control. How can we reduce the overhead?
How can we make the transformation is actually for example
and how can replace it transformation adapt to? This
kind of program includes can different programs, places and
different longtime environment. So the basic idea is the
CPU Gpu pipeline which I'm going to talk about more
and then uh so there are also problems like demanded
uh with proposals called breaking and also to discuss more
than that like okay, so this might explain the
idea of the Gpu pipeline while we are performing computation
on Gpu, we can start doing transformation on CPU
and then we can transfer the uh and we can
transfer the data but if you could give you so
that you can use the transform data out of the
best dressed in matching. So uh in this case
if we have a move in this room we call
the construction of four times on different data from the
different dinner trump. Um then we can when the
first uh iteration, uh first call to the review
um Something starts with that transformation for the third Gpu
acceleration and when the second gear really starts with the
letter back from you can give you and meanwhile with
that transformation, four different regulations and we do this
so on and so forth. So this is the
intuition behind it. But there are problems right in
this uh this uh so scenarios like if we don't
have a clue. Right? So this is a
very correct in a correction application and there's alleged the
one function call. So can we use Gpu planning
? And another case if we have dependent so we
won't be able to have the data available and with
the black resin finish so we cannot do anything transformation
before that. So this has to a practical problems
for the Gpu planning. Okay so this is the
uh so we use something called sleeping. So basically
we transform on one single call to GPS function to
two different Gpu chemicals. So for the first give
you a call we make it to the ground on
part of the threat and also part of the data
. And then for the second uh we use the
rest of the threat and then that work on the
rest of the data because the Gpu execution model,
there are many more threat than the total number of
course on ship. So this right all around entertaining
. Right? So if we petition them into two
parts, the total uh this to function college will
be nearly equal the total time of the first.
The original assumption for because the threat that most independent
from each other so we can petition into different parts
and then now we have to potential GPU function court
. Now we can use the Gpu pipelines. We
have new transformation for the second Gpu call while the
first Gpu is involved. Okay. Alright, okay
. So let's uh cBgb high planning idea and next
how we designed this CBgb uh pipeline team and how
to promote speaking, how can we determine the best
ratio? And also there are different challenges, practical
problems. So one track problem is unlike traditional CPU
architecture pipeline every stage has fixed the running time for
the doctor of pipeline stages. The running time,
there is some included because memory, exercise and exercise
because control uh the divergence part presents a different,
so this is the idea. Okay, so area
stage can be perfectly even while the sushi provides money
so in a not super birthday um so only start
transformation for the third generation um Here it takes it
takes more time than it is allowed so when a
third generation starts and the transformation still hasn't been finished
so um so the scheme. Okay, so another
problem is that also the red, the use of
you pipeline can be start, can do it myself
. Okay, so this is a solution. So
if the transformation takes too much time we do automatic
shut down and we keep monitoring the status of the
GPU and memory channel so it takes too much time
we turn with it. So this is a foundation
of this efficiency control scheme and the neck. The
problem is uh what we terminate this transformation. Politicalization
. How about the transformation of the next century information
doing this stop here just doing nothing. We can
keep adjusting and find the best approximated transformation. We
reduce the transformation overhead while we also reduce the event
, but we still can't get something from this transformation
. So next uh the next call is how much
they can do it. And what is the approximation
ratio? What is the ratio of How can we
know that during runtime and where we're from uh running
environment pressure back pressure from interested into. Okay,
so the solution here is we first estimate initial uh
the ratio and then we keep adjusting by using feedback
from previous situation. So um so first we estimate
the we estimate the stacking uh approximation ratio. So
so that the formula doing is to approximate situation.
So for a pending case, a team, we
want to optimize the artist and of the workload.
Then we have to make sure that the uh so
we took for example the ratio between the two overhead
and the colonel by running a small portion of transformation
. And we assume that still leaning like this is
a threat. And then the forming right here is
we have to make sure the first part of the
colonel which runs along mandatory percent of the time for
some time be greater than or equal to our present
or the time that the order which is the total
has transformed the rest of now is uh with formulating
here are the ratio and now if we don't do
clipping which is the transformation on the uh one of
the primary americans implemented operation. So for the The
formula is simplest over the first situation, we just
need to make sure the 12 point of time is
better than the first time the total ahead. So
the basic dynamics just scheme if we start with initial
approximation ratio and while we're running multiple regression so we
get the information from that situation. So if it
solves that means the transformation too aggressive. So we
reduce it by 1/6 step and we keep decreasing it
. And here we re show operation that transformation actually
on the city. And if at the beginning we
find that using this approximation ratio it's 16. That
means we can keep pushing forward, we can transform
this more great in place. So we keep increasing
the approximation racial back step by every inspiration and then
we stopped when we reach a state that transformation actually
. So this is uh the information product and this
works perfectly however uh in a non small case.
So I want to show you the problem that the
basic scheme doesn't work, it doesn't work here.
So in the ideal case while we are transforming for
the fourth generation we use the overhead over 40% of
the overhead. And uh and also we are using
the uh the criminal execution which is what kind of
uh in the state of state it's supposed to be
like that allowed overhead. And uh okay so uh
we are during your dynamic a judgment if we use
the basic scheme so if it's 16 that's the present
arrangement, if they Um 40 water just 40 then
it succeeded. And next we increased all has to
be 50%. However the time we can use to
hide the overhead to the criminal language that's optimized for
40 and then so it can be a problem here
. So um it doesn't so so they're like multiple
decisions we can make. So if we keep using
the dynamic the basic thing that increasing step and uh
every information or decreased by the duration we probably can
get into trouble here. Um Okay so the solution
is to uh make a more complicated definition so we
divide in certain points and then so that we make
sure the approximation ratio we use for transformation and the
approximation to the final match. And then we can
be sure this is the information racial state if you
can step feet and they really like information we use
in the future. So that is the same condition
for that. All right. So now let's take
a look at the role results. So this is
when we take over head into account, we have
severe slowdown multiple applications. Now, if we do
efficient control, you can see that our application to
run faster than original. Uh and also for this
one that's supposed to run slower. So if we
simply only use automatic shutdown scheme, we'll get exactly
before now we actually get more for to get 1.1
month or 2, 200 a hand picked up by
using approximation dynamic adjustment. Um However we admit there
is still some distance between the ideal case and the
current leader we can get. So the problem is
for these two cases because of the dependence we have
to transfer data between CPU and Gpu. And this
has become the bottleneck because um that's connecting the G
. B. Uh lower memory much lower memory value
is compared to the two of you mary menu and
which can be uh address innovation by using uh the
regime use or abuse the whole technology to make the
memory connect factor. Also also we can improve the
heuristics based approaches uh improve the average to make the
transform any member transformation molestation. Okay so this is
hard work to counter provided without. So we can
reduce the total number of connection uh by between 10%
to 67% and direction with branch reduction, which means
a total number of instructions that are divergent. We
produce a lot of baggage in terms of 1999% and
uh empty here because uh memory sexual activity that thank
you. Okay to summarize. So we developed a
culture streamline that can dynamically remove irregularities in japan treatment
. We can make almost completely here in the system
by I think the whole system enemy. And we
can adapt by choosing the best transformation parameters so that
we can make the transformation uh profitable, maximum,
maximize the profit a profit you can get. So
that's what my project on optimizing deregulation application and I'm
going to talk a little bit about my project on
program locality enhancement, non uniform shared cash. So
what I did is uh from the extensive study on
the expected uh explore the implications for its nine share
cash on more than hello application. So the fact
is that no matter how we schedule the threat to
make them uh to take advantage of the share the
cash to make threats compared and different. No matter
how we prepare the threat, we don't see much
performance improvement of human degradation. So and we are
buried all different factors such as um different sectors and
different localization model is different number of stress. So
what is the implication implicating that the non uniform shape
cash section, which is common today? Comedy and
textures like intel OMG position. So it's non uniform
shape cash reflects. Um So actually we find out
the wonder is no. So the problem is a
mismatch between the software development and hardware features. So
we generally protected by proposing cash share where transformation.
And we were able to increase the group by up
to 1.47 times uh simply three simple transformation to make
a threat that share data. Uh make thread that
uh the left share cash to share more data.
And then we have proved that a large potential for
us to look at look at this direction and to
to build cash sharing will hold. Uh The next
project the project I worked on is uh products include
program the adaptation for GPS applications. So the main
idea is to build a model that captures the relationship
between the input and the best optimization level for GPU
applications. So first we are we have a computer
that will transform the program of lightweight with profound the
performance but automatically running trans different transformed version over different
input. And then we go back into a database
and then we use statistical techniques to do the model
to predict the best program optimization level from the program
. And then we we generate different and in the
end, when we are giving a new input,
then we'll produce the important active code to get the
national performance, you know, And this is uh
, numbers for the uh, for this project.
So All right. So, uh people uh in
my life, I want to talk a bit about
the future world. So, uh, today we
are in the era of Peta still including and the
fastest supercomputers more can produce. Pay the pay to
block, which is 10 to the 15th block.
And hope you provide. Can you 100.5 petaflop if
I remember them? So, the next milestone is
extra computing, which is the milestone that I do
. So. Excellent. Still tend to 18 people
flock and which is uh, 1000 times faster uh
than the current, uh current, faster current,
fastest supercomputers. Okay, so the problem um,
in sample is powerful. So the politicians, the
problem has been studied extensively in the future. So
when the different this time. So first of all
the different, the problem comes from the design of
micro architecture. So before we can decrease the final
transistors, so we can put more than more transistors
on the same area and we can while at the
same time we can maintain the same power density,
which is truly amazing. If we scale the device
by reduce the size of device by two, then
we can get eight times capacity. If we keep
the same core identity, it will provide the elemental
energy. Um uh However, when uh what is
getting and when the device to better device, so
you know, A level uh this uh just stop
working because we have more and more public. So
which means we cannot use the same amount of power
and we cannot keep reducing the size of the minister
. So we cannot put more than more clothes on
the same night. So, this is the implication
. So, so this uh this uh this uh
so this is more in small works before before we
enter pattern still competing. Uh so this is how
what this is how it helps us from building systems
that uh make a plus uh to either, but
still too carol, sarah sarah sarah teraflops to pay
almost still. And in the future there is a
limit on highway. So there's a limit on the
number of forces on the on the ship to increase
the performance. And there will be more normal powerful
tension and the subject matter uh facility that will be
part of it. So this uh so this uh
this time we have to seriously consider the software energy
efficient. So we understand what how much stock the
world uh performance solution again. And we need really
need to build. And energy is the energy efficiency
aware program. And we can expose more information from
the program level to help reduce the energy consumption.
Which is also a major distinction from a lot of
work has been down operating system level and a special
level. And now we don't have much potential from
the potential of war. And that may be a
break to the material sciences. And so so I
consider this a very promising build. And there are
also a lot of challenging, interesting problem to resolve
. And this will be very important for us to
kill the program. Uh and uh still the performance
of high uh scientific applications. Uh so there are
three major differences of this uh energy efficiency problems.
So the first difference is uh peter genius. So
now there's a system that behind this morning on this
is not the only way to find gPS and GPS
and connect them with practice, but also on the
same ship. We do the we integrate different goals
, different types of, for example, the entity
we have an efficiency that integrate people and uh To
achieve power proponents power efficiency and there's a media research
project language we should try to achieve with over 1000
calls on the same ship to achieve at the still
confusion. So the implication that is the problem techniques
we use for energy efficiency uh mostly of homogeneous system
. And this new challenges the new trade off for
different types of uh what can we use? Uh
how can we the results allocations and how can we
do the wonder which has regenerated the whole invasion like
And certain difference is uh standing uh here by that
power. I mean what we keep a fixed uh
frequency and voltage amount of parliament. However for example
of memory uh if we move data from memory to
center for computation we consume extra power. So this
is the dynamic uh energy consumption and this is dominated
by the behavior of the provides which cannot be absent
from operating system. Uh And the third is different
is the plastic artists the Communistic. Uh Now that
we can have millions of direct money contamination and the
memory behavior and also the connection between different different courts
will also become very complicated. And the like you
and your men follow that low so tastic roles that
we can use in just looking gentlemen we develop programs
from our program. So my goal is to first
abuse lacking between the high level behavior is the most
uh Level of energy consumption and then you uh,
prospect, uh, adaptation and optimization to improve the
power efficiency and to help much into the expertise competing
by 2008, which is the problem that's very important
for the future. And this is a shift of
uh research from opponents to power. So this brings
me to handle myself. Now. I will be
happy to under any question, Yeah.