In defence of hardware engineers and out of order execution.

In defence of hardware engineers and out of order execution.

[David]

<miller@hamnavoe.demon.co.uk> writes:

>There's no need for anyone to feel under fire.  I think there has been a
>failure of imagination on the part of both hardware and software folks, as
>to just how much trickery our counterparts are likely to get up to.
>

OK, I wasn't really feeling got at, it's just easier to argue if you
take a side.
If at any time you feel my whitterings to be sounding grumpy, please
imagine my tongue to be somewhere near my cheek. I can't stand to use
those smiley things.

> I didn't mean that hardware designers were unreliable.
But we are. Don't believe the hype.

>But equally, anyone who thinks that only "some madman" would write the
>equivalent of
>	par {
>		{ a = 1; x = b; }
>		{ b = 1; y = a; }
>	}
>has unrealistic expectations about the way concurrent software is being
>written.

Yes, sorry. I'll rephrase that. "some person who is not fully aware of
the
implications of the differences between this weeks processors and last
weeks".
 
Anyway what I was getting at is that the solution that can be offered
only
makes sense at the machine level (instructions & modes), so a high
level language which assumes an ordering model (like if it comes
first in the source it get executed first in real time) is out of step
with
reality. Thus it's the language or compiler which should acquire
a means to enforce ordering.

Of course once I crack the design of the anticausal pipeline you'll
have to do something really clever to keep your threads talking.

Also I feel that EIEIO is the best ever instruction name in the
history of processor design.

David Johnston

Microsoft may add a sig or some MIME or some binary gunk to the
bottom of this email. Please ignore.

In defence of hardware engineers and out of order execution.

[miller]

David Johnston <DJ@symbionics.co.uk> writes:

> Being a hardware type (with a CS background) I'm feeling a little under
> fire here.

There's no need for anyone to feel under fire.  I think there has been a
failure of imagination on the part of both hardware and software folks, as
to just how much trickery our counterparts are likely to get up to.

When I wrote that

> it's better to be conservative with
> locks than to trust hardware designers to do what we expect.

I didn't mean that hardware designers were unreliable:  it's our own
expectations (that processors will conform to a simple model of behaviour
which hasn't been formally specified) that we shouldn't trust.
But equally, anyone who thinks that only "some madman" would write the
equivalent of
	par {
		{ a = 1; x = b; }
		{ b = 1; y = a; }
	}
has unrealistic expectations about the way concurrent software is being
written. Consider for example Peterson's Algorithm for mutual exclusion
using only shared variables:

P0:				    P1:	
    wanted[0] = 1;			wanted[1] = 1;
    turn = 0;				turn = 1;
    while (turn==0 && wanted[1])	while (turn==1 && wanted[0])
	{}		  		    {}
    /* ... critical section */		/* ... critical section */
    wanted[0] = 0;			wanted[1] = 0;

This algorithm, academically respectable enough to be in standard
Operating Systems textbooks, will presumably fail on any multiprocessor
which allows reads to overtake queued writes (no need to point the
finger at the Pentium Pro in particular).

-- Richard Miller

In defence of hardware engineers and out of order execution.

[David]

Being a hardware type (with a CS background) I'm feeling a little under
fire here. Out of order execution is a pretty reasonable way of making a
processor go faster. If processor designers didn't pull every trick to
make the things go faster you'd all go and buy somebody else's. Then
again you'd probably buy Intel anyway.

The general principal is of course that the computations performed have
the same end result as executing in order but for a single locus of
control only. It's a bit much to expect the processor to guess what the
other processors are up to at instruction rate. The introduction of
pipelines, caches and optimising compilers have all forced extra
constraints on software writers (self modifying code used to be
mandatory for efficient use of the 256bytes of program memory) so don't
be too surprised at this sort of jiggery pokery on a 30 billion gate
processor.

Intel are of course to be deplored for not documenting sufficiently that
you can analyse exactly what will happen but then Intel have a bit of
reputation to keep down. Documenting their processors would never do.

The poor, hassled micro designer has your best interests at heart and is
likely to provide something to fix the problem. From the top of my head
I think the powerPC provides an EIEIO instruction (Something like:
Enforce in order execution of something of other, I've lost the book)
god knows what the Pentiblob provides but the best a processor designer
can do is provide an instruction or a processor mode which switches off
the reordering. They can't second guess the compiler writers. So there
will inevitably be some machine dependency.

So why not provide a system call like:

  set_the_bloody_reordering_mode(reordermode a)

Which on many architectures will dissolve down to nothing, however on
pentiblob pros and the like it will land you with an assembler
instruction to do the business.

The whole messy edifice of parallel computing theory and practice has
been set up to sort out what happens when some madman goes and writes:

	par {
		{ a = 1; x = b; }
		{ b = 1; y = a; }
	}

Maybe this would be better:

 	set_the_bloody_reordering_mode(REORDERMODE_OFF);
	par {
		{ a = 1; x = b; }
		{ b = 1; y = a; }
	}
	set_the_bloody_reordering_mode(REORDERMODE_ON);

Apologies for the non plan9 style verbosity, but I've been writing VHDL
all this week, sigh.

David Johnston