Re: PAR (Was: Embedded languages based on early Ada)

["Dr. Adrian Wrigley" <amtw@linuxchip.demon.co.uk.uk.uk>]

On Mon, 05 Mar 2007 11:01:59 -0800, Jacob Sparre Andersen wrote:

> Ray Blaak wrote:
> 
>> PAR would only be convenience shorthand for writing task bodies
>> around each statement.

Yes.  The semantics are very similar.

> Wouldn't "pragma Parallelize (Statement_Identifier);" be a more
> reasonable way to do this?  As I understand the wish is to tell the
> compiler that these statements are a likely target for parallel
> execution.

I don't think we share this understanding.

PAR is about indicating in the source code which statement sequences
are unordered.  The idea is to make the syntax for concurrency
as simple as the syntax for sequentality. Perhaps using "par"
instead of "begin" is the way to go.  Adding "all" to the for
loop also makes a lot of sense.

If you can persuade programmers to use "par" unless they explicitly
*need* sequential execution, a great many statements will be marked
as concurrent.  Numeric codes will use "par" in the computational
core, as well as outer layers of execution.

So "par" is really about program *semantics*, not about *mechanism*
of execution.  Simply being in a "par" block is not a hint or
a recommendation that the compiler should target the code for parallel
execution.  The "par" block grants the authority to reorder
(even when results vary, whatever the reason).  And it informs the
*reader* that there is no implication of sequentality.

Ultimately, the hardware should be choosing dynamically whether
to create execution threads according to execution statistics
and resource allocation.  The instruction stream should have
potential thread creation and joining points marked. Perhaps
this can be via a concurrent call instruction ("ccall"?), which
is identical to a normal "call" when threads are scarce,
and creates a thread and continues execution at the same time
when threads are readily available.  The objective is to
have zero overhead threading at a fine grain of concurrency.

So I think the pragma Parallelize () is like the equivalent
of the "register" directive in C.  The programmer is trying to
say "I use this variable a lot, so store it in a register for me".
This approach is considered obsolete and counterproductive.
Automatic register allocation, automatic data caching
and automatic thread allocation should all be handled by the
compiler and hardware, whether or not the programmer
recommends it.  Registerization and caching work well with
existing serial code.  Automatic thread allocation is almost
impossible with existing code simply because code must
always be executed in the order given unless concurrency
is provable.  Coding with "par" is no big challenge.
Most programs will use par a lot. Only very short or exceptional
programs can't use "par".

> The compilers are of course already allowed to parallelise the
> execution of statements, but hinting where it is worthwhile to try
> might be more efficient.  Such a pragma will of course introduce a
> discussion of whether the result of the parallel execution should be
> exactly the same as the result of the sequential execution, or if it
> should just be approximately the same.

Often parallel execution will give very different results.

for I in all 2 .. 15 loop
   PutIfPrime (I);
end loop;

Produces
 2 3 5 7 11 13
with sequential operation, but
 11 13 2 3 5 7
with parallel execution.  Or indeed any other order.

The "par" says "I don't care what the order is".
One benefit is being able to continue executing the program while
multiple page faults are being serviced from disk or RAM.  Such
page faults show why parallelisation is often outside the scope
of the compiler - how does it know when the faults occur?
Program execution becomes a hierarchy of concurrent threads,
perhaps with over 1.0e10 threads available during a program's execution.

Mandating sequential execution except where the "pragma" is used
puts parallel statements at an immediate disadvantage - it makes
them seem to be second class citizens, added on afterwards
in an attempt to speed things up. Par should be "everywhere", it's
a *basic* component of program semantics - like a loop or a function call.
It's absent from programming languages is because processors can't really
take advantage of it at present, and text is inherently linear, needing no
special "seq" directive.  Graphical languages on the other hand often
imply concurrency automatically, and so have the opposite property. "par"
is not a hint.

Enough ranting for now...
--
Adrian