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

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

On Wed, 7 Mar 2007 23:45:23 -0600, Randy Brukardt wrote:

> "Dr. Adrian Wrigley" <amtw@linuxchip.demon.co.uk.uk.uk> wrote in message
> news:pan.2007.03.07.20.42.03.883636@linuxchip.demon.co.uk.uk.uk...
> ...
>> The contribution is the very lightweight syntax and semantics.
>> One extra keyword, to permit a wide choice of implementations,
>> parallel, serial, hardware, pipeline, threaded etc.
>>
>> PAR is ideal for the common case of running absolutely independent code!
> 
> But only if the code is guaranteed to be independent! Otherwise, all of
> those different implementation techniques will give different results. And
> relying on programmers to understand the many ways that this could go wrong
> is not going to help any (or give this technique a good reputation, for that
> matter).
> 
> If I was designing this sort of language feature, I would start with a very
> strong set of restrictions known to prevent most trouble, and then would
> look for additional things that could be allowed.

Absolutely
 
> The starting point would be something like a parallel block:
>       [declare in parallel
>            declarative_part]
>       begin in parallel
>             sequence_of_statements;
>       end in parallel;
> 
> where the declarative part could only include object declarations
> initialized by parallel functions (new, see below), and the
> sequence_of_statements could only be parallel procedure calls.
> 
> A parallel subprogram would be defined by the keyword parallel. They would
> be like a normal Ada subprogram, except:
>     * Access to global variables is prohibited, other than protected
> objects, atomic objects, and objects of a declared parallel type. Note that
> this also includes global storage pools!
>     * Parameters are results can only be by-copy types, protected objects,
> and objects of a declared parallel type.
> These restrictions would be somewhat like those of a pure package, but would
> be aimed at ensuring that only objects that are safe to be accessed
> concurrently could be accessed. (It would still be possible to get in
> trouble by having objects accessed in different orders in different
> subprograms - which could matter in parallel execution - but I don't think
> it is practical to prevent that. It's likely that the operations will need
> to access some common data store, and rules that did not allow that could
> not go anywhere.)
> 
> A "declared parallel type" would be a private type that had a pragma that
> declared that all of it's operations were task-safe. (That's needed to
> provide containers that could be used in parallel subprograms, for
> instance.) Precisely what that would mean, I'll leave for some other time.
> (It would be possible to survive without this, as you could try to use
> protected objects and interfaces for everything. That sounds like a pain to
> me...)

That's the big question. Is task-safety a type property or one of the
object? The fine-granularity approach presumes that task-safety could be
hung on objects later on, i.e. sort of:

declare parallel in parallel -- (:-))
   I : Integer; -- Same as if it were declared atomic

Since Ada 83 the language moved in the opposite direction, IMO. I suppose
because there was no obvious way of making an unsafe ADT safe.

The problem with the container types (and all other more or less elaborated
types) is that fine-granularity concurrency does not work for them. That
was the reason of my original claim that PAR were worth of nothing without
a feasible concept of synchronization somehow different from protected
actions and rendezvous we have by now.

> Humm, I think you'd actually need two separate blocks: "declare in parallel"
> (and execute statements sequentially) and "begin in parallel" (with
> sequential declarations). There seems to be a sequential (combining) stage
> that follows the parallel part in most of these algorithms.

> Anyway, food for thought...

Yes, indeed. 

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de