We left off last time, talking about some implementation issues around,
multithreading. so a little bit of background on what we're doing today is
we're going to be finishing up multithreading. We're going to be using
cutlery and you'll see why we're using cutlery in a minute. That's right. A whole
box a forks. And we'll be talking about synchronization and synchronization
permitives. So let's, let's go back to multithreading, And look a, actual
simultaneous multithreading which is where we left off. So just to recap, we talked
about different types of multithreading. We talked about not multithreading
processors, so we have a superscalar where we're trying to fill in the empty slots
here. So we can do some fine-grain, but not the simultaneous multithreading. We
can do coarse-grain multithreading we can even possibly think about trying to do
this in some fast software layer. You could think about just cutting your
cluster in half and using half your ALUs for one thread and half your ALUs for
another thread. That is sort of technically a version of multithreading.
It's just not executing oh, it is executing at the same time, but it's not
necessarily using all the resources. and then you could think about actual
simultaneous multithreading, where you're issuing instructions from different
threads into different functional units at the same time. So, we talked about this
last time and we, one of the things that came up was, how do you go about getting a
parallelism? So, if you have thread-level parallelism, you can mix and match
different instruction slots from different threads and get parallelism that way. And
one of the great things about simultaneous multithreading is that if you have a fast
superscalar machine and you try to use it for simultaneous multithreading, you could
think about trying to reduce the number of threads if you don't have enough
thread-levle parallelism and actually go at instruction-level parallelism. So here,
we see this blue crosshatch. block zero instructions, and this is the same threa d
running in the same sort of time period. And, if you have lots of threads running,
you could actually intermix the different threads and run the blue crosshatch
threads slower, than if you were try to use parallel resources to run one thread
faster. And this is one of the big insights here that symmetric
multithreading lets us go after. So we briefly talked and flew through this at
the end of lecture last time cuz we talked about, what is the cost of implementing
symmetric multithreading. So, conveniently, there is actually a really
good example of this, the Power four by IBM and the Power five by IB, IBM. They're
very similar architectures, except the Power five has two way simultaneous
multithreading, and the Power four is almost the same architecture without two
way symmetric multithreading. So you look at these two pictures. One of the big
things they added is they added more fetch bandwidth, so you can fetch from two
different program counters at the same time. You can decode more instructions,
and then, they added an extra pipe staging here, which they, they do what we'll call,
what they call group formation, which is basically the scheduling of the two
different threads instructions, together by the time that it reaches the execution
units. Also over here, they, as, as we've talked about before, even without
symmetric multithreading, it's pretty useful to have more registers or more
physical registers, registers and more architectural registers. You, you're
minimally going to need more architectural registers, more physical registers
probably is a good performance thing. So, we're talking about implementation
details. So, one of the questions that comes up is, what is the cost of actually
going to implement this symmetric multithreading on this processor? And one
of the questions that also comes up here is, why two threads instead of four
threads, or eight threads, or more threads? It has costs. So, that's one of
the things that they would actually have to start replicating more data structures.
For the pipeline th at they had roughly left over from the penny, excuse me, the
Power four, they had enough compute and bandwidth through their execution units to
be able to handle two threads. But if they wanted to try to go to more threads, they
basically bottleneck somewhere in their architectures. I don't completely know
exactly where they turtlenecked. They, the, the paper talks about this, it
basically says that they bottleneck. Somewhere in their execution I guess they
kind of leave it a little vague. so they decided that it wasn't worth adding more
than two threads, because it's not going to give you any performance increase,
unless you have threads that don't have or, or, threads that have a lot of stalls.
If you have threads with enough stalls, you probably have enough holes to try to
intermix another thread in there. So, some of the changes in the hardware they were
about doing. Well, they actually increased their cache size, they increased the
associativity of their caches their last level cache here that went to 1.92
megabytes versus 1.44 of the L2 and L3 together. Sorry. and you can see here one
of the interesting things is they start to actually separate data structures, because
if you have multiple threads running and you try to mix them all into one big data
structure, one of the problems like, or one of the big hardware data structure,
one of the problems that comes up is maybe one of the threads is going to hog the
data structure. So, threading actually introduces a lot of complexity, having to
do with figuring out how to be fair in the usage of the structures. So one solution
is you just replicate. So anywhere there was, it was hard to get it right or hard
to have they have a lot of conflicts you could just replicate. So they added a
separate instruction fetch, prefetch and buffering. and then they added more
physical they, they call them virtual registers here, but it's more physical
registers effectively, so more places to schedule into. So there were some added
hardware costs to this. And to give you an idea of sort of area, 24% area improvement
increase, a lot of this is just due to the cache, because they made the cache so much
larger. So, you have to ask yourself, does it make sense to use a 25, 24% more area
to run two threads or at one point does it make sense just to plop down a second
processor? It's tough trade there. Well, if it's 24% bigger and you get a two times
performance boost, it was a good trade. If it was 24% bigger and you get less than a
24% performance boost, it's pretty questionable. So let's look at another
example and then we'll wrap up on the performance of this and see if they did
get their 24% performance boost. The first implementation of symmetric
multithreading, there's been many implementations of multi threading. But
excuse me, not symmetric, simultaneous multithreading, was the Pentium four
processor. Now they called it, hyperthreading. that's a Intel marketing
term. it is simultaneous multithreading, but the Pentium four, they didn't actually
replicate very many structures. They didn't really change the processor very
much. And in fact there's basically modes to turn off simultaneous multithreading
they're paying for, and it was not a flagship feature when the processor was
first shipped. So the, the, the basic idea in the Pentium four, the, the, the little
bit of extra hardware they added was, they did duplicate some, some resources here.
So, overall they, they increased their dye area by about five%., So very, very small
amount. Now the question is what is the performance boost they can get from this?
, and one of the interesting things here is that there was a big problem that
started to come up with the Pentium four that when you were trying to run one
thread on it, well, you weren't guaranteed that the performance of that one thread
would be equal to if you turned off hyperthreading, or sorry, symmetric
simultaneous multithreading. So they had a mode switch, they could turn off, where
they would take some structures that they would partition when they were in
multithreading mode and partition t hem 50/50. So you didn't have deadlock
problems and you didn't have resource contention problems on the shared
structures. And when you turn this mode switch off, , some programs got faster, to
some extent what that meant is, they didn't size those structures correctly to
be running in multitraining mode at all times. And the switch was not a little
switch. It was like a big switch. It's like reboot the computer and change the
switch. It was it was a boot time parameter, parameter to the chip. And this
left such a bad taste in, in Intel's mouth that simultaneous multithreading got
kicked out of Intel land for a few generations. The Pentium M, Coreduo,
Core2duo all kicked out simultaneous multithreading. And it didn't work it's
way back in until inhalem core i5, i7 sort of processors there recently. So, it's
interesting to see that, you can use a little bit of hardware, but you have to be
careful, now, what was, what was the biggest problem that they had here? The,
the biggest problem was that the load store queue on the Pentium four was. Split
in half when they were running in two thread mode. So the first Pentium four
architecture that was shipped. It had symmetric or simultaneous multi threading
turned on. They just split the structure in half. And it didn't have enough
bandwidth for lots of programs. Or didn't have enough entries in there for lots of
programs when it was cut in half. So it was sized to run one thread. They cut it
in half statically and when they tried to run two threads it was, effectively. Not
providing enough performance. So they couldn't get enough loads out to the
memory system from one thread when they cut that structure in half. So it really
starts to bring up the question of what is the right allocation of resources. And,
should you use some sort of round robin scheme? Should you use dynamic allocation?
Should you use static allocation? Should you replicate? If you replicate it costs
more area and this is, these are some of the big challenges here. Okay so let's
look at the, the, some of the performance here. So the, The numbers were pretty
abysmal for the Pentium four. Even when. Everything was going well. So.
Example here. Pentium four. Extreme edition with simultaneous
multithreading give you one% speed up when you're running two threads, for spec int.
Rate. So you're running multiple, copies of the same program, that's how spec, spec
rate is done. And that was the integer of one. For the floating.1, it did a little
bit better. Seven% improvement. Now, that's not horrible, considering it was
only a five% area. Improvement or area increase, but still that's, that's not
saying a whole lot. I mean you have to question if that's really, this whole
level of complexity was worth it. And was at five% area, could have been used for
something else to get a few percent performance increase. And this was to some
extent pretty typical across applications for the Pentium four.
One of the, the interesting things about the, the, the Pentium four was. Because
the cash wasn't huge, especially the L1 cash was relatively small cuz they wanted
it to operate so fast, at the very high clock frequencies. You get a lot of data
pollution in there from the two threats that would actually destructively
interfere in the level one cache. So that was one of the big things they had to try
and make up was this is a problem of any multi-threading. Not just simultaneous
multi-threading, that you can actually fight for space in the cache. And end up
with both capacity and . The Power five did a lot better here. You know it was,
they, they thought a little bit harder about sharing structures, duplicating
structures, and allocation of different resources in there. So on, on Specint,
they, Specint rates, they were getting 23% improvement for their 25% area. Okay.
Well, this, this might actually be a good idea. It might have some value. And for
the floating point version, they are not doing great, but doing better here. And.
The, the floating point apps had a lot of, cache conflicts, so the floating point
spec FP apps, if you go look at them in the inside, they typically have very large
data sets, so they were basically conflicting in their large, larger, last
little caches and things like that. So finally I wanted to just give a little bit
of color to this idea of picking fairly and not having starvation in different
resources in a simultaneous multi trading pipeline. So one processor that's sort of
the famous, simultaneous multiframe processor that was never built, was the EV
eight, or the Digital Equipment Corporation last alpha, that was never
built. So this last alpha, the, EV eight or also known as the 21464, Have
introduced they had eight way threaded processors note this was never, never
built but, it was super scale that it had eight way, eight way. Simultaneous
multi-threading. It also was a very aggressive processor. And when I say it
was never built, it was never shipped commercially. They went pretty far in the
design of it. So one of the questions that they realized upon here is, what is the
right way in an out of order pipeline to make sure that you're getting correct
utilization of the pipeline when you're issuing instructions from different
threads? So in this example here, we have four different threads we'll say. And, you
need to choose to go into your multi issue out of order pipeline here, which thread
to go pick from. And, by definition you want to try to fill in the holes of one of
the threads with work from another thread. So, complete fairness here or lockstep
round robin choosing for instance is not what you want to do. Completely wrong
thing to do. Because you want to fill in when one processor is stalled, with other
processors work. But, you want to make sure that the thread which let's say, has
no dependencies on each other. Or could run very fast, doesn't go to memory very
often, we'll say, it just doesn't stall very often. Doesn't just hog the
processor. Because it's never going to introduce stall cycles on itself by
itself. So they came up with this idea called icount, and it was a choosing
policy which basically lo oked at the number of instructions that were retiring
out of the back of the pipeline, had like a moving window to try to estimate how
many instructions from each thread were completing and then, feedback around to
the front of the pipeline here to determine where to issue from. So I, I
just wanted to get across the idea that, if you try to intermix different threads
in a data structure, it's relatively simple. You can either cut the data
structure in half, or have some round-robin allocation there. It gets much
more complicated when you have a full processor pipeline that you need to figure
out how to issue into that processor pipeline. And, then you know twenty stages
later, if something happens, there's so much stuff in flight that you need to,
need to worry about this a little bit harder. So here, they, they basically were
looking at how many instructions were in flight and how many instructions had
recently committed from a thread to determine what to do. And, on average they
were hoping that they had some fairness between the threads.