Ada 2012 automatic concurrency?

Ada 2012 automatic concurrency?

[charleshixsn]

In the RM I read (page 209):
NOTES
1 Concurrent task execution may be implemented on multicomputers, multiprocessors, or with interleaved execution on a
single physical processor. On the other hand, whenever an implementation can determine that the required semantic
effects can be achieved when parts of the execution of a given task are performed by different physical processors acting
in parallel, it may choose to perform them in this way.

    ----------------
Does this imply that if I use protected types, that the code will automatically be run concurrently on a multiprocessor system, or might automatically be run concurrently?  

If so, does Gnat do this?

Re: Ada 2012 automatic concurrency?

[John B. Matthews]

In article <af146e53-f736-4c59-8015-60a90d9f5fcf@googlegroups.com>,
 charleshixsn@earthlink.net wrote:

> In the RM I read (page 209):
> NOTES
> 1 Concurrent task execution may be implemented on multicomputers, 
> multiprocessors, or with interleaved execution on a single physical 
> processor. On the other hand, whenever an implementation can 
> determine that the required semantic effects can be achieved when 
> parts of the execution of a given task are performed by different 
> physical processors acting in parallel, it may choose to perform them 
> in this way.
> 
>     ----------------
> Does this imply that if I use protected types, that the code will 
> automatically be run concurrently on a multiprocessor system, or 
> might automatically be run concurrently?  

Perhaps, to the extent possible, but Ada 95 Rationale, Section 9.1 
Protected Types suggests that the approach was chosen, in part, to 
"enable the implementation of a synchronization mechanism that scales 
smoothly from a single processor to a multiprocessor."

Similar language appeared in the Ada 83 LRM, Section 9: Tasks, and it 
has remained unchanged since Ada 95, Section 9: Tasks and 
Synchronization.

> If so, does Gnat do this?

I don't know what it does currently, but I recall an older version 
targeting Mac OS 9: absent preemptive multi-tasking, the implementation 
used  an available FSU threads library. Protected types proved ideal for 
synchronizing access to the platform's single-threaded GUI library.

-- 
John B. Matthews
trashgod at gmail dot com
<http://sites.google.com/site/drjohnbmatthews>

Re: Ada 2012 automatic concurrency?

[Niklas Holsti]

On 12-12-25 19:26 , charleshixsn@earthlink.net wrote:
> In the RM I read (page 209): NOTES 1 Concurrent task execution may be
> implemented on multicomputers, multiprocessors, or with interleaved
> execution on a single physical processor. On the other hand, whenever
> an implementation can determine that the required semantic effects
> can be achieved when parts of the execution of a given task are
> performed by different physical processors acting in parallel, it may
> choose to perform them in this way.
> 
> ---------------- Does this imply that if I use protected types, that
> the code will automatically be run concurrently on a multiprocessor
> system, or might automatically be run concurrently?

I believe that the second sentence in your quote has a more general
meaning: that an Ada compiler is allowed to generate code that uses
several processors or cores in parallel just to implement a logically
sequential (single-task) computation. For example, if your program
contains the two statements:

   x := a + b;
   y := a - b;

and the target computer has two processors or cores capable of addition
and subtraction, the Ada compiler may generate code that uses these two
processors in parallel, one to compute a+b and the other to compute a-b.
This is allowed, since the semantic effects are the same as when using
one processor for both computations (assuming that none of these
variables is declared "volatile").

So I don't think that your use or non-use of protected types (or tasks)
is relevant to this RM sentence.

> If so, does Gnat do this?

I think not, but it might be a feature of the GCC back-end rather than
the GNAT Ada front-end.

However, many high-performance processors today have multiple
"functional units" per core, and the processor core itself can issue or
execute several instructions in parallel, from the same program, even if
the compiler intends or assumes sequential execution when it generates
the instruction sequence.

This multi-issue feature of modern processors means that there is less
interest and profit in doing such fine-grain parallelization at
compile-time. At most, the compiler should sequence instructions
according to the data dependencies, to let the processor run several
consecutive data-independent instructions in parallel.

For large-grain parallelization, you should use tasks. I don't know of
any Ada compiler, including GNAT, that does automatic large-grain
parallelization.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
      .      @       .

Re: Ada 2012 automatic concurrency?

[charleshixsn]

On Wednesday, December 26, 2012 2:55:11 PM UTC-8, Niklas Holsti wrote:
> On 12-12-25 19:26 , charleshixsn@earthlink.net wrote:
> 
> > In the RM I read (page 209): NOTES 1 Concurrent task ex...
> 
> 
> I believe that the second sentence in your quote has a more general 
> meaning: that an Ada compiler is allowed to generate code that uses 
> several processors or cores in parallel just to implement a logically 
> sequential (single-task) computation. For example, if your program 
> contains the two statements:
>  
>    x := a + b;
>    y := a - b;
> 
> and the target computer has two processors or cores capable of addition
> and subtraction, the Ada compiler may generate code that uses these two
> processors in parallel, one to compute a+b and the other to compute a-b.
> This is allowed, since the semantic effects are the same as when using
> one processor for both computations (assuming that none of these
> variables is declared "volatile").
>  
> So I don't think that your use or non-use of protected types (or tasks)
> is relevant to this RM sentence.
> 
The use of protected types would be to ensure that the sections were independent.
>  
> > If so, does Gnat do this?
> 
> I think not, but it might be a feature of the GCC back-end rather than
> the GNAT Ada front-end.
>  
> However, many high-performance processors today have multiple
> "functional units" per core, and the processor core itself can issue or
> execute several instructions in parallel, from the same program, even if
> the compiler intends or assumes sequential execution when it generates
> the instruction sequence.
>  
> This multi-issue feature of modern processors means that there is less
> interest and profit in doing such fine-grain parallelization at
> compile-time. At most, the compiler should sequence instructions
> according to the data dependencies, to let the processor run several
> consecutive data-independent instructions in parallel.
>  
> For large-grain parallelization, you should use tasks. I don't know of
> any Ada compiler, including GNAT, that does automatic large-grain
> parallelization.
> -- 
> 
> Niklas Holsti
> 
> Tidorum Ltd
> 
> niklas holsti tidorum fi
> 
>       .      @       .
Thank you.  That was the answer I was expecting, if not the one I was hoping for.  Tasks it is.

IIUC, there shouldn't be more than about twice as many tasks as cores.  Is this about right?

Re: Ada 2012 automatic concurrency?

[Dirk Heinrichs]

charleshixsn@earthlink.net wrote:

> IIUC, there shouldn't be more than about twice as many tasks as cores.  Is
> this about right?

Hmm, taking into account that your application isn't alone on your system 
and task switches have their price, too, I think you'd better go with "# of 
CPUs/Cores + 1", like the Gentoo Linux Handbook suggests for the level of 
parallel compilation:

"A good choice is the number of CPUs (or CPU cores) in your system plus one, 
but this guideline isn't always perfect." [1]

However, I'm still confused about the "+1".

Sometimes it may also be application dependent, so you should try different 
models to find the one that suits you best.

HTH...

	Dirk

[1]: http://www.gentoo.org/doc/en/handbook/handbook-x86.xml?part=1&chap=5
-- 
Dirk Heinrichs <dirk.heinrichs@altum.de>
Tel: +49 (0)2471 209385 | Mobil: +49 (0)176 34473913
GPG Public Key C2E467BB | Jabber: dirk.heinrichs@altum.de

Re: Ada 2012 automatic concurrency?

[Brian Drummond]

On Thu, 27 Dec 2012 09:59:44 +0100, Dirk Heinrichs wrote:

> charleshixsn@earthlink.net wrote:
> 
>> IIUC, there shouldn't be more than about twice as many tasks as cores. 
>> Is this about right?
> 
> Hmm, taking into account that your application isn't alone on your
> system and task switches have their price, too, I think you'd better go
> with "# of CPUs/Cores + 1", like the Gentoo Linux Handbook suggests for
> the level of parallel compilation:
> 
> "A good choice is the number of CPUs (or CPU cores) in your system plus
> one,
> but this guideline isn't always perfect." [1]
> 
> However, I'm still confused about the "+1".

Probably an attempt to ensure there is always one task waiting to do 
useful work when a currently running task suspends. 

I have my doubts about the "+1" too in practice, since it may mean tasks 
migrating between CPUs and trashing their caches.

There may be times when it is better to have "+1" per CPU, and mark each 
task with affinity for the CPU it starts out with. 

In any case, too many tasks means too much inactive state, which 
increases pressure on cache and slows up task swapping. So "+1" may be 
more of an ideal asymptotic target than a practical reality (like Colin 
Chapman's adage about the perfect race car - one that falls apart while 
crossing the finish line in first place).

It would be interesting to see some numbers though.

- Brian

Re: Ada 2012 automatic concurrency?

[Jeffrey Carter]

On 12/26/2012 10:57 PM, charleshixsn@earthlink.net wrote:
>
> IIUC, there shouldn't be more than about twice as many tasks as cores.  Is this about right?

Hardly. 2x#processors generally gives you the best speedup compared to a single 
task when parallelizing algorithms such as matrix multiplication or quick sort, 
but in general you should have a task per active entity in your problem domain.

-- 
Jeff Carter
"Now go away or I shall taunt you a second time."
Monty Python & the Holy Grail
07

Re: Ada 2012 automatic concurrency?

[Niklas Holsti]

On 12-12-27 07:57 , charleshixsn@earthlink.net wrote:
> On Wednesday, December 26, 2012 2:55:11 PM UTC-8, Niklas Holsti wrote:
>> On 12-12-25 19:26 , charleshixsn@earthlink.net wrote:
>>
>>> In the RM I read (page 209): NOTES 1 Concurrent task ex...
>>
>>
>> I believe that the second sentence in your quote has a more general 
>> meaning: that an Ada compiler is allowed to generate code that uses 
>> several processors or cores in parallel just to implement a logically 
>> sequential (single-task) computation. For example, if your program 
>> contains the two statements:
>>  
>>    x := a + b;
>>    y := a - b;
>>
>> and the target computer has two processors or cores capable of addition
>> and subtraction, the Ada compiler may generate code that uses these two
>> processors in parallel, one to compute a+b and the other to compute a-b.
>> This is allowed, since the semantic effects are the same as when using
>> one processor for both computations (assuming that none of these
>> variables is declared "volatile").
>>  
>> So I don't think that your use or non-use of protected types (or tasks)
>> is relevant to this RM sentence.
>>
> The use of protected types would be to ensure that the sections were independent.

I don't see how protected operations would help, in fact I think that
they hinder automatic parallelization.

A protected operation is allowed to access and modify global variables,
as well as its parameters and the components of the protected object.
For example, consider two operations, A and B, and a task that calls
them in sequence, like this:

   A;
   B;

Whether A and B are protected operations or not, the compiler would have
to look into their internals to discover if they access and/or modify
the same variables.

If A and B are ordinary operations, not protected ones, the compiler can
(at least conceptually) in-line the calls into the calling task, and
could then analyze the data dependencies and possibly arrange for
parallel execution of independent parts of the operations, or even of
the whole calls.

However, if A and B are protected operations, while they can (in
principle) be in-lined in the same way, the in-lined code will include
the PO locking and unlocking code, which is very likely to access
variables that the compiler should consider as "volatile", which means
that it would be difficult for the compiler to interleave any code
in-lined from A with code in-lined from B (because it must preserve the
order of volatile accesses). The compiler would then have less
opportunities for parallelization than when the operations are not
protected.

>> For large-grain parallelization, you should use tasks. I don't know of
>> any Ada compiler, including GNAT, that does automatic large-grain
>> parallelization.

> Thank you.  That was the answer I was expecting, if not the one
> I was hoping for.  Tasks it is.
> 
> IIUC, there shouldn't be more than about twice as many tasks as
> cores.  Is this about right?

That depends... If the tasks are logically different, I would use
whatever number of tasks make the design clearest. This would be using
concurrency or parallelism for logical purposes, not (mainly) for
performance increases.

If the tasks are all the same, as for example when you have a number of
identical "worker" tasks that grab and execute "jobs" from some pool of
"jobs to do", I would use a total number of tasks that makes the average
number of "ready" tasks about equal to the number of cores (or a bit
more, for margin). For example, if each worker task typically spends
half the time working, and half the time waiting for something, the
number of workers should be about twice the number of cores. (You should
not, of course, count as "waiting" the time that worker tasks spend
waiting for new jobs to work on.)

Usually, the amount of waiting in tasks is variable and dynamic, which
means that the number of "ready" tasks fluctuates and will, with the
above rule of thumb, sometimes be less than the number of cores, so some
cores will be idle when that happens. If you are very anxious to avoid
occasional idle cores, you can of course increase the number of tasks to
skew the distribution of the number of "ready" tasks to higher numbers,
making idle cores less likely. But this comes at the cost of more
overhead in task scheduling, task stack space consumption, and perhaps
in data-cache turnover.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
      .      @       .

Re: Ada 2012 automatic concurrency?

[tmoran]

> in general you should have a task per active entity in your problem domain.
  Absolutely.  You should try to program in the problem domain, not the
hardware domain (that's for optimization).  Some problems are most
naturally thought about with more than one task, even if the plan is to
execute on a single cpu machine.  And look at taskmgr in your local
Windows machine - there are already a large number of processes using
those cpus before your program even starts.

Re: Ada 2012 automatic concurrency?

[Randy Brukardt]

"Dirk Heinrichs" <dirk.heinrichs@altum.de> wrote in message 
news:kbh2m0$sou$1@online.de...
> charleshixsn@earthlink.net wrote:
>
>> IIUC, there shouldn't be more than about twice as many tasks as cores. 
>> Is
>> this about right?
>
> Hmm, taking into account that your application isn't alone on your system
> and task switches have their price, too, I think you'd better go with "# 
> of
> CPUs/Cores + 1", like the Gentoo Linux Handbook suggests for the level of
> parallel compilation:

I think this is totally dependent on your application. My spam filter/mail 
gateway has about 40 tasks, and it runs on a 2000-era computer with (of 
course) one core. But most of these tasks are waiting on work to be posted 
to one of the work queues (typically, messages get processed fast enough 
that there is very little parallelism in practice). Most of the actual 
parallelism is in sending and receiving messages from the Internet, and 
those tasks are usually waiting on I/O to complete.

OTOH, a program that has tasks doing a lot of processing surely should have 
much smaller numbers of tasks. Having more tasks that are running 95% of the 
time than the number of cores just makes them slower.

As to the advice, I suspect that the +1 comes from the notion that there is 
at least one control tasks that runs rarely. But I think that better advice 
is to design the tasks so that the sum of the average utilization of the 
tasks (expressed as a fraction) is roughly the same as the number of cores. 
That is, if 4 tasks run 95% of the time, and 2 other tasks do control 
functions and run about 10% of the time, the total utilization is 
0.95*4+0.10*2 = 4.00, so this would be a good fit on a 4 core machine. 
Figuring out the utilization is more work, of course, but it is a more 
accurate representation of the load of each task.

                                                      Randy.