CASTalk.com

Bart · Guest

Hi,

I have developed more than a passing curiosity about processor
architecture and have a question regarding out-of-order execution vs.
static scheduling (such as the approach taken by VLIW and Itanium.) I
hope someone here can clarify my understanding of OOO and precisely why
it improves performance.

If I understand correctly, OOO cores work by dispatching instructions
which have already been fetched when it is possible to do so; meaning
when there are no data dependencies or those dependencies can be
"eliminated" through register renaming. So for example, this
instruction sequence:

[1] add r0=r1,r2
[2] and r3=r0,0xFF
[3] xor r5=r6,r7
....
[6] ld r0=(r4)

Faced with this instruction sequence, an OOO processor could
theoretically execute instructions 1, 3, and 6 simultaneously, right?
Instruction 6 would require the "architectural register" R0 to be
assigned to a different hardware register than the one used by
instruction 1. Am I comprehending register renaming correctly?

If so, I can certainly see the advantage this provides. However, on an
architecture such as Itanium, I could simply reorder the instructions
myself and exploit the same level of parallelism. Yet, I realize the
Itanium doesn't always perform as well as an OOO machine, to say the
least.

I once wrote a Mandelbrot plotting program which, for those who aren't
familiar with the idea, calculates each pixel to plot using a tight
loop with virtually no parallelism to exploit. It's a very serial
sequence of logic. Using an HP TestDrive account, I tested the code on
the following:

- EV5 Alpha 500MHz (in-order)
- EV6 Alpha 466 or 500MHz (OOO)
- Itanium (~800MHz)

On the EV6, the performance almost doubled vs. the EV5. The Itanium did
very poorly even when I wrote hand-tuned assembly code (which
admittedly wasn't the best but did exploit a bit of natural parallelism
in the instruction sequence.) I realize the gains I saw on the EV6 must
have been due to its OOO execution. But why? There was no parallelism
to exploit in the main loop body.

I have an idea as to what the answer may be and this is the primary
point of this rather long winded (sorry!) post: To find out if I'm
thinking along the right path or if I've got it all fundamentally
wrong! Here it goes:

I figure that branch prediction will direct the processor to follow the
loop back to the top while still executing the loop body and at this
point, it begins the next iteration of the loop (facilitated by
register renaming.) Here is the loop in question:

for (i = 0; i < MAX_ITERATIONS; i++)
{
x = next_x * next_x - next_y * next_y + cx;
y = 2 * next_x * next_y + cy;

next_x = x;
next_y = y;

if ((x * x + y * y) > 4) // while |Zn| < 2
break;
}

The thing that puzzles me is if my understanding is correct, the
processor wouldn't be able to schedule instructions from the next
iteration until next_x and next_y have been assigned (unless it is
smart enough to execute the next_x = x instruction right after x is
first computed and then move on to the next iteration -- but can it
really look ahead that deep into the instruction stream?)

I can't think of how else it could be so much faster than an EV5. Or,
for that matter, a much higher clocked Itanium (~800MHz) where I
exploited the obvious parallelism fairly well.

Thanks in advance!

Eric Gouriou · Guest

Bart wrote:
[...]

Eric Gouriou · Guest

Bart wrote:

Bart · Guest

It was a Merced. I used gcc on all of the machines (all Linux boxes.)
The code is indeed small, I've uploaded the entire thing to
http://www.trzy.org/mandbrot.zip -- all that matters is m.c. I also
included my clunky quick IPF implementation under ipf/ if you want to
see it. It's really old and quickly hacked together code. I just wanted
to play around with the machines on TestDrive.

I didn't do any in-depth profiling. Function-level profiling wouldn't
have helped anyway -- it's obvious where the program actually spends
its time. It's a very simple piece of code.

If you'd like to look at it, feel free :) I just assumed the speed-up
from EV5 -> EV6 (even if EV6 has a wider execution core) was primarily
due to the fact that the EV6 microarchitecture is significantly
different (OOO) and I wanted to see if my understanding of OOO is
correct.

Some usage notes on m.c: You can pass the xres and yres of the image to
render on the command line (e.g., "m 640 480" will spit out a 640x480
BMP.) Obviously bigger images are more useful for benchmarking. The
code might be messy but the only function of any relevance is
Mandelbrot().

Niels Jørgen Kruse · Guest

Bart <bart_trzynadlowski@yahoo.com> wrote:

Tommy Thorn · Guest

Eric Gouriou wrote:

Guest

Bart
Niels

Niels> 1) Unrolling twice, you could flip-flop between next_x and x
Niels> and avoid the copy.

No need to unroll, since the compiler has all those temporaries
along the way:

do { // 21164: 21264:
e = a*a; // cycle 1 cycle 1
f = b*b; // cycle 2 cycle 2
g = a*b; // cycle 3 cycle 3
h = e-f; // cycle 6 cycle 6
i = e+f; // cycle 7 cycle 7
j = 2*g; // cycle 7 cycle 7
a = h+c; // cycle 10 cycle 10
m = (i>4.0); // cycle 11 cycle 12
b = j+d; // cycle 12 cycle 11
} until( m ); // cycle 14 cycle 14
//...
// e = a*a; // cycle 14 cycle 14
// f = b*b; // cycle 16 cycle 15

Niels> 2) Once the sequence leaves the bounding circle it is not
Niels> going back, so there is no need to test at *every* iteration.
Niels> Stash the sequence into a fifo and test (say) every 20
Niels> iterations, then backtrack if outside the bound.

I never thought of that!

.... it might help on something with bad branch prediction, but both
EV-5 and EV-6 shouldn't be having much trouble here. IIRC, the
average loop has dozens of iterations, so one or two mispredictions
each is no big deal and may be less than you'd get with a
backtracking scheme.

Niels> 3) Calculate multiple pixels in parallel. Adjacent pixels
Niels> are often close in iteration count.

On the R8000, this was good for something like 50% speedup.

I'm actually mystified why the 21264 would do the code in a lot
fewer cycles than the 21164. Both machines have independent FP
* and + pipes. Latency for both ops is 4 cycles on both machines.
There are no memory references in the loops (or, there shouldn't
be).

The only thing I could think of is this: if there is a few cycles
of latency getting the FP comparison result (that's "m" in the code
above) over to the integer side, then the 21264 probably speculates
farther past the branch than the 21164. This isn't really an
out-of-order thing, it's more of a register-renaming thing.

I know that moving FP values from the FP register file to the
integer register file required a store and a load on these machines.
I'd be suprised if that were true for condition codes, though.

The R8000 provided 8 independent, named floating-point condition
code bits so that the compiler could software pipeline loops that
had to send back FP compare information to a branch. The apparent
latency of FP compare -> branch was often over 10 cycles if the
processor was running with imprecise FP exceptions.

Bart · Guest

Eric and Niels: Thanks for the profiling and the performance tips. So
the poor performance on Itanium can be attributed to the latency of the
FP instructions (as Eric said) and bubbles in the instruction stream
(it appears as though there really isn't much that can be done with the
scheduling judging from the output code shown.)

What about the performance gap between identically clocked EV5 and EV6
machines? I recall seeing a dramatic performance increase on EV6. Is it
because EV6 is a wider architecture or is it primarily because of its
OOO nature? The purpose of this post is to help me understand OOO first
and foremost. I'm just trying to use this program as an example (but
maybe it's a poor one.) What I'm getting at is: What benefits (if any)
would an OOO implementation of a processor give for code similar to
what I presented?

Tommy Thorn wrote:

Terje Mathisen · Guest

Niels Jørgen Kruse wrote:

Randy · Guest

Bart wrote:

Sander Vesik · Guest

Randy <joe@burgershack.com> wrote:

Jan Vorbrüggen · Guest

Niels Jørgen Kruse · Guest

<iain-3@truecircuits.com> wrote:

dcw · Guest

In article <1121136759.721988.22130@z14g2000cwz.googlegroups.com>,
Bart <bart_trzynadlowski@yahoo.com> wrote:

Tom Linden · Guest

On Thu, 14 Jul 05 10:11:54 GMT, dcw <D.C.Wood@ukc.ac.uk> wrote:

Where do the gains of OOO architecture actually take effect? Goto page 1, 2 Next

	CASTalk.com Forum Index -> Computer Architecture	All times are GMT Goto page 1, 2 Next
Page 1 of 2