Re: Not enough parallelism in programming

Andy Glew wrote: 
Elaborating on my previous posts: I want somebody to define a parallel
or concurrent language where the meaning of not only the simple
statements such as are defined:

    pre.nxt := insertee,
    insertee.nxt := pre.nxt,
    insertee.prev := pre,
    pre.nxt.prev := insertee;

But where there is also a consistent definition of what it means to
say the concurrent statement:

obj1.method1(), obj2.method2();

Consistent in what sense? There are plenty of "parallel-aware" languages that define what happens when two methods execute in parallel. If by "consistent" you mean "sequentially consistent" or "deterministic", in many cases that is not desirable. "Desirable" can only be defined by the programmer and the user, so what is important is that the outcome is defined well enough that the programmer and user can agree on what it will/should do. That usually means satisfying some invariant. The utility of various languages is often in how much they facilitate the specification and verification of such invariants.

Plus, I'd like there to be defined efficient ways of computing such
parallel statements, on both parallel and uniprocessor machines.

That really comes down to the platform knowing enough about how and where and when data is being used that it can be where it is needed next before it is needed there, or as soon thereafter as possible. Whether that how/where/when information comes from static dataflow analysis or from user declarations is relatively unimportant. What is important is that the programmer or user isn't tasked with saying how to get the data to where it is needed (as with existing shared memory or message-passing tools), or with overspecifying the order in which independent data accesses occur (as is done with existing sequential languages). That way, on uniprocessor machines, it can all be sequentialized without data being copied around or locked needlessly, and on parallel machines, the appropriate communication and synchronization can be used while using using advantageous orderings.

What's so hard about obj1.method1(), obj2.method2();
?

Mainly, in any reasonable language such as C++ or Java, obj1 may
contain a reference to obj2, or vice versa.  Or, if not a direct
reference, obj1 and obj2 may refer to linked data structures that
overlap.

So people say "that's a programmer error - you aren't supposed to try
to execute in parallel two pieces of code that might overlap and
hence not be parallelizable."

The only people who can say whether the result is an error or not are the programmer and the user, in the context of the programming model. If the programming model doesn't provide any hint of what the result will be, then it is unlikely that the programmer and user will agree that it's OK, so it may feel universally like an error, but if the model does define it, you don't have enough info to call it an error.

If the parallel language or system cannot handle something
like
obj1.method1(), obj2.method2();
then it cannot handle the simplest possible concepts of modern object oriented languages.

Most of the time, even the programmer doesn't know whether ob1 and
obj2 overlap. Sure, they may not seem to... overlapping may not seem
to be an important aspect. E.g. they may be non-overlapping linked
lists. But say that the Object1 and Object2 classes have been instrumented
to do something like record into a logfile. Or maybe update some counter.
Then they are not independent, but the cross-dependence is invisible to
the programmer who writes obj1.method1(), obj2.method2(); It is visible only to the guys who implemented the classes, or the
language system.

If it is necessary to pass a reference to the logfile or counter to these objects in order for the objects to access it, then the call chain can be traversed to find that the same data is being passed into both. If that (reference to that) logfile or counter is hidden within other objects being passed to both obj1.method1() and obj2.method2, then the immediate caller may not know, but so what? There is no need for the caller to know as long as the caller is getting what it expects out of the object.


I conclude that THERE IS NO SUCH THING AS PARALLEL SEMANTICS
that obeys one of the most basic principles of software engineering:
data hiding or modularity.

A bigger problem for parallel software engineering lies in hiding behavior/timing. For example, I can ask two programmers to implement a module that takes value on two ports, A and B, and produces a result on port C that is their sum and one on D which is their difference (A-B). Even if both programmers implement the module to this spec, with no funny side effects or access to global info, one might work in my app and one might not solely due to the order in which they read their inputs from ports A and B and/or produce their results. Adding this sort of info to the spec (e.g. in temporal logic) can get very complex and error prone. I have wondered, in my ScalPL work, whether it's actually more convenient for the user and programmer to communicate the behavior in terms of a partial implementation than a spec in something like temporal logic. In other words, maybe it's OK for the user to take a peek under the covers as long as they can't see too much. This would only seem to work if you put behavioral layers (which you want them to see) above transformational layers (which you don't), as ScalPL tends to do (strategies above tasks).

The simple parallel statement
    pre.nxt := insertee,
    insertee.nxt := pre.nxt,
    insertee.prev := pre,
    pre.nxt.prev := insertee;
works only because potential overlaps between the data
structures are visible to the compiler.
   obj1.method1(), obj2.method2();
doesn't work because the overlaps are invisible
- and MUST be inivisible for data hiding.

What about making the parallelism, the full list of data structures
modified, part of the definition of the function.  Sure... but then
making some simple modifications to a class, like instrumenting it,
require changing the programs that use it.  Not acceptable.

That's a big jump. Just as information can be hidden within the object being called, it can also be hidden within objects that are passed to its methods/functions as arguments. The caller of the function/method doesn't need to (and often does not want to) know what is in those argument objects.

I.e. I conclude that the parallel
   statement1, statement2;
with desired semantics "statement1 is completely independent
of statement2 and can be run in parallel"
is not useful, if software modularity is also desired.

I completely agree that it is wrong-headed to make it the user's responsibility to determine whether two things should be *allowed to* be initiated in parallel. A better way is to simply provide semantics for what things will do when they run in parallel, whether they share resources or not.

The first thing that I am looking for is a language definition
that gives meaning to a statement such as obj1.method1(), obj2.method2();

Sequential semantics does.

Speculative parallelization does, but that's really just an implementation
of sequential semantics.

Transactional might try to do both in parallel, and, failing that, do
first one and then the other.  In some way that is "semantic": it says
that we can't rely on the order, but it will be as if one was done
first, then the other. Non-deterministic.

I wonder if there are definitions that are not quite so all or nothing
as transactions.

Of course. You're referring to atomic transactions. Non-atomic transactions can be built of atomic ones. The non-atomic ones will lose their serializability properties (i.e. your "as if one was done first, then the other"), but there are other ways of reasoning that don't require the overall transactions to be serializable in order to ensure that important invariants are still preserved during their concurrent execution.

Myrias has a consistent, deterministic, semantic: both are done in
parallel, and then the writes are merged in some prioritization,
possibly at byte granularity.  It is not clear to me that the Myrias
behavior is useful: merging on a byte by byte basis might corrupt some
data structures.  I wonder for what cases it would be correct.

I see no reason to believe that this approach would be highly fruitful, though there are lots of examples in database and version control systems where multiple users are allowed to update concurrently (e.g. after checkout) and re-integration is attempted later, often using "diffs". Without invariants referring to the data structure, it would be hard/impossible to ensure sequential consistency--i.e. even if updates don't overlap, the writes of one might have been different if they depended on writes in the other and vice versa.

  -Dave

.

Relevant Pages

  • Re: C # and C ++ learning curve
    ... They all borrow from the family of C languages but more languages like ... I have the utmost respect for any true C++ programmer and I can only ... understand data structures, hardware, and memory management as much as ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Is C99 the final C? (some suggestions)
    ... >> inevitably lead to BUS errors, ... > There's ample precedent in other languages ... call stack in a well-defined and programmer controlled way. ... semantics similar to C's function declaration. ...
    (comp.lang.c)
  • Re: Cobol News - Microfocus and AcuCOBOL
    ... I think they are the languages of today. ... I disagree strongly about problems for the programmer. ... It is a hard concept for COBOL people to grasp.. ... functionality comes along, it inherits what is there already and extends it. ...
    (comp.lang.cobol)
  • Re: The Demise of C#
    ... > There are syntactical conveniences (like the string concatenation operator) ... > in both languages would be nice to have at once. ... > Polymorphism to a VB programmer prior to .NET was to use variants. ...
    (microsoft.public.dotnet.framework.aspnet)
  • Re: Language Oriented Programming
    ... lot of skill and creativity to conceive and build it. ... I can explain the problem and solution to another programmer in a matter of hours, but encoding this solution into the computer takes much longer. ... "The process of OOD is necessary because these classes and methods are the only abstractions that object-oriented languages understand. ... "The traditional way to address this problem is to write comments or other forms of documentation to capture the design and model information. ...
    (comp.object)