PAR (Was: Embedded languages based on early Ada)
in [ADA]
|
Prev: Escape Codes
Next: Ada Supercompiler?
From: Jacob Sparre Andersen on 5 Mar 2007 14:01 Ray Blaak wrote: > PAR would only be convenience shorthand for writing task bodies > around each statement. 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. 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. The effect on a loop will also need some consideration. Greetings, Jacob -- I'm giving a short talk at Game Developers Conference (Mobile Game Innovation Hunt) Monday afternoon: http://www.gdconf.com/conference/gdcmobile_hunt.htm
From: Dr. Adrian Wrigley on 5 Mar 2007 21:01 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
From: Randy Brukardt on 5 Mar 2007 22:30 "Dr. Adrian Wrigley" <amtw(a)linuxchip.demon.co.uk.uk.uk> wrote in message news:pan.2007.03.06.02.02.27.892793(a)linuxchip.demon.co.uk.uk.uk... .... > 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. My $0.02 worth: One thing I'm absolutely certain of is that "par" would never, ever appear in Ada. That's because Ada keywords are always complete English words (that's true in the packages, too; abbreviations are frowned upon). I admit that "par" *is* an English word, but it doesn't have anything to do with parallel. So, I think the syntax would be more likely something like "begin in parallel" or the like. (Similarly, "all" in a for loop is just too small a keywork for such a major semantic change. I think I'd prefer "parallel" to be used somewhere in the loop syntax; but I could be proved wrong in this instance.) > 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. Yes, and a great number of programs will have become unstable. That's because the default in Ada is for objects that are *not* safe to access in parallel. (That's a problem for Ada tasks, too.) Only objects with pragma Atomic and objects wrapped in protected objects can be assumed safe. I know you've said that you would expect programmers to worry about such things. But that's the C way of thinking about things, and that is the root of much of the unreliably of modern software. Programmers are likely to test their programs on some compiler and then assume that they are correct. But when dealing with parallel execution, nothing could be further from the truth. The next compiler or OS will make the program execute completely differently. The only way to "test" these things is to have tools that enforce proper behavior (no access to global objects without synchronization, for instance). Of course, there is no problem with purely independent subprograms. The problem is that hardly anything is purely independent, even most independent algorithms depend on shared data (like a database) to guide their execution, and if something else is changing that data, there is a lot of potential for trouble. .... > 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... Darn, you were just getting interesting. ;-) $0.02 cents. Ada has the needed building blocks for parallel execution, given that it has defined what is and is not accessible in parallel. Most other programming languages have never thought of that, or found it too hard, or just don't care. But you also need enforcement of safe access to global objects (global here means anything outside of the subprograms that were called in parallel). I don't think that that would be very practical in Ada; the result would be pretty incompatible. (Maybe you could have procedures defined to allow parallel execution, sort of like a pure function, but it sounds messy. And we've never had the will to properly define Pure functions, either, that's because we couldn't decide between the "declared Pure and user beware" and "defined and checked Pure" approaches). What really would make sense would be a meta-compiler, that took source code in an Ada-like language with "begin in parallel" and other needed constructs and converted that to regular Ada code. (Parallel calls would turn into tasks, appropriate checking would occur, etc.). But the majority of the code would simply get rewritten into Ada - and then an Ada compiler could compile it. Such a system would be free of Ada compatibility concerns, but wouldn't necessarily have to give up much of Ada's power. (And, if it caught on, the Ada step could be dropped completely.) Clearly, the meta-compiler would have to know something about the target (how many threads are reasonable, for instance), but not necessarily a lot. Such a system could be a lot safer than Ada is (well, at least until you have to make a call to C...), especially for parallel execution. Randy Brukardt.
From: tmoran on 6 Mar 2007 01:04 > 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. When "virtual memory" was new some programmers thought about their program's access patterns and found that VM was a great simplification. Other programmers simply said "oh, good, I can write my program to randomly access many megabytes, though the physical memory is only a few hundred kilobytes." Those programs were a disaster. Nowadays, of course, very few people write programs that don't in fact fit inside physical memory. I suspect we'll see a similar thing with multi-core: some will carefully consider what they are doing and it will be good; others will just say "oh, good, I can multiply an m x n and an n x p matrix using m x p threads", and it will be bad. Meanwhile the hardware will develop to automatically do more and more hidden concurrency. If programmers think of "par" as "I've carefully analyzed this algorithm and it may be run in parallel" that's good. If they think of "par" as "I want you to run this in parallel", I think that would be a bad mindset. Explicit Ada tasks are more like the latter. My $.02
From: Ray Blaak on 6 Mar 2007 01:59
"Dr. Adrian Wrigley" <amtw(a)linuxchip.demon.co.uk.uk.uk> writes: > The "par" says "I don't care what the order is". I would nitpick a tiny bit. "Any possible order" is not precisely the same as true concurrent execution. This can be measured the the times of execution, since an unordered yet sequential execution is the sum of the statement times, whereas the true concurrent execution is the maximum of the statement times. -- Cheers, The Rhythm is around me, The Rhythm has control. Ray Blaak The Rhythm is inside me, rAYblaaK(a)STRIPCAPStelus.net The Rhythm has my soul. |