How many hardware threads?

How many hardware threads?

[Peter C. Chapin]

As we all know there is currently a lot of "buzz" about parallel
programming and about the "crisis in software development" that is
associated with it. People using languages with weak support for
concurrency are now wondering how they will use multi-core systems
effectively and reliably. Of course Ada already has decent support for
concurrency so part of the problem is solved for those of us using Ada.

But not all of the problem...

I see a couple of difficulties with writing effective parallel programs
for "ordinary" applications (that is, applications that are not
embarrassingly parallel). One difficulty is load balancing: how can one
decompose a problem to keep all processors reasonably busy? The other
difficulty is scalability: how can one design a single program that can
use 2, 4, 16, 128, or more processors effectively without knowing ahead
of time exactly how many processors there will be? I'm not an expert in
Ada tasking but it seems like these questions are as big a problem for
Ada as they are for any other language environment.

I'm not looking for a solution to all tasking problems here. But there
is one feature that seems like a necessary prerequisite to such a
solution. The language (or its standard library) needs to provide a
portable way for the program to determine how many hardware threads are
available.

I'm about to write a simple program that decomposes into parallel,
compute-bound tasks quite nicely. How many such tasks should I create? I
could ask the user to provide the number as a command line argument or
in a configuration file. Yet it seems like the program should just be
able to figure it out. Does Ada have a standard way of doing that? I
didn't see anything in my (admittedly short) review.

Thanks!

Peter

Re: How many hardware threads?

[Jeffrey R. Carter]

On 07/11/2010 05:47 PM, Peter C. Chapin wrote:
>
> I'm about to write a simple program that decomposes into parallel,
> compute-bound tasks quite nicely. How many such tasks should I create? I
> could ask the user to provide the number as a command line argument or
> in a configuration file. Yet it seems like the program should just be
> able to figure it out. Does Ada have a standard way of doing that? I
> didn't see anything in my (admittedly short) review.

No, it doesn't, and I've long thought it should.

GNAT has function System.Task_Info.Number_Of_Processors. But something standard 
would be better.

-- 
Jeff Carter
"I feel as though somebody stepped on my tongue
with muddy feet."
Never Give a Sucker an Even Break
112

Re: How many hardware threads?

[Pascal Obry]

Jeffrey,

> GNAT has function System.Task_Info.Number_Of_Processors. But something
> standard would be better.

http://www.ada-auth.org/cgi-bin/cvsweb.cgi/ai05s/ai05-0167-1.txt?rev=1.3

-- 

--|------------------------------------------------------
--| Pascal Obry                           Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--|    http://www.obry.net  -  http://v2p.fr.eu.org
--| "The best way to travel is by means of imagination"
--|
--| gpg --keyserver keys.gnupg.net --recv-key F949BD3B

Re: How many hardware threads?

[Yannick Duchêne (Hibou57)]

Le Mon, 12 Jul 2010 19:04:04 +0200, Pascal Obry <pascal@obry.net> a écrit:

>
> Jeffrey,
>
>> GNAT has function System.Task_Info.Number_Of_Processors. But something
>> standard would be better.
>
> http://www.ada-auth.org/cgi-bin/cvsweb.cgi/ai05s/ai05-0167-1.txt?rev=1.3

I wanted to check if this was now part of the new revision
http://www.ada-auth.org/ai-files/grab_bag/Amendment-2-D9.html
but could not find it.

I feel I also remember of something like CPU affinity in tasking, but  
could not find back this track (do not remember where I've read about it).

Re: How many hardware threads?

[Randy Brukardt]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 997 bytes --]

"Yannick Duch�ne (Hibou57)" <yannick_duchene@yahoo.fr> wrote in message 
news:op.vhjp21x8xmjfy8@garhos...
Le Mon, 12 Jul 2010 19:04:04 +0200, Pascal Obry <pascal@obry.net> a �crit:
...
>>> GNAT has function System.Task_Info.Number_Of_Processors. But something
>>> standard would be better.
>>
>> http://www.ada-auth.org/cgi-bin/cvsweb.cgi/ai05s/ai05-0167-1.txt?rev=1.3
>>
>I wanted to check if this was now part of the new revision
>http://www.ada-auth.org/ai-files/grab_bag/Amendment-2-D9.html
>but could not find it.

It was moved to AI-171, which was approved in Valencia, and it will appear 
in clause D.16 of the next Ada 2012 (whenever I get that finished and 
posted).

>I feel I also remember of something like CPU affinity in tasking, but 
>could not find back this track (do not remember where I've read about it).

That's a package in AI-167 (reference above). It's still being worked on, 
but it is still planned to be in Ada 2012.

                Randy Brukardt, ARG Editor.

Re: How many hardware threads?

[Pascal Obry]

Yannick,

> I feel I also remember of something like CPU affinity in tasking, but
> could not find back this track (do not remember where I've read about it).

GNAT Specific pragma?

http://www.adacore.com/wp-content/files/auto_update/gnat-unw-docs/html/gnat_rm_2.html#SEC109

Pascal.

-- 

--|------------------------------------------------------
--| Pascal Obry                           Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--|    http://www.obry.net  -  http://v2p.fr.eu.org
--| "The best way to travel is by means of imagination"
--|
--| gpg --keyserver keys.gnupg.net --recv-key F949BD3B

Re: How many hardware threads?

[tmoran]

> I'm about to write a simple program that decomposes into parallel,
> compute-bound tasks quite nicely. How many such tasks should I create? I
> could ask the user to provide the number as a command line argument or
> in a configuration file. Yet it seems like the program should just be
> able to figure it out. Does Ada have a standard way of doing that?
  In MS Windows you can call GetProcessAffinityMask and count the ones
in your process's mask.
  But just knowing how many CPUs there are is just the beginning.  Are
there other programs running on the machine and should you leave some CPUs
for them, or grab them all for your program?  What about cache?  It tends
to be small and if you (or your program plus any others running on the
system) actually try to use all the CPUs simultaneously you may thrash.
Thread overhead goes up with thread count.  The best algorithm may not be
the most straightforward.
  In the early days of virtual memory some people thought "I have a giant
memory, which I can access as I wish".  They soon found they needed to
consider access patterns or their program could thrash horribly.
Similarly for multi-core CPUs.

Re: How many hardware threads?

[Dmitry A. Kazakov]

On Sun, 11 Jul 2010 20:47:41 -0400, Peter C. Chapin wrote:

> I see a couple of difficulties with writing effective parallel programs
> for "ordinary" applications (that is, applications that are not
> embarrassingly parallel). One difficulty is load balancing: how can one
> decompose a problem to keep all processors reasonably busy? The other
> difficulty is scalability: how can one design a single program that can
> use 2, 4, 16, 128, or more processors effectively without knowing ahead
> of time exactly how many processors there will be? I'm not an expert in
> Ada tasking but it seems like these questions are as big a problem for
> Ada as they are for any other language environment.

Back in 90's, during the era of transputers, concurrent algorithms were
decomposed knowing in advance the number of processors and the topology of
the network of. (Unlike to multi-cores the transputers didn't share memory,
they communicate over serial links connected physically) That time the
consensus was that the problem is not solvable in general. So you designed
up front both the algorithm and the topology.

> I'm not an expert in
> Ada tasking but it seems like these questions are as big a problem for
> Ada as they are for any other language environment.
> I'm not looking for a solution to all tasking problems here. But there
> is one feature that seems like a necessary prerequisite to such a
> solution. The language (or its standard library) needs to provide a
> portable way for the program to determine how many hardware threads are
> available.

Well, maybe, but I don't think it would bring much. Especially because
normally cores support multi-tasking. It would be more important for the
architectures with the cores that do not (GPU etc).

BTW, "hardware thread" = core? processor? ALU + an independent memory
channel? etc. It is quite difficult to define and the algorithm's
performance may heavily depend on the subtleness. ARG would say, look, it
does not make sense for all platforms, forget it.

> I'm about to write a simple program that decomposes into parallel,
> compute-bound tasks quite nicely. How many such tasks should I create?

Back in time it was popular to make it adaptive. I.e. you monitor the
performance and adjust the size of the working threads pool as you go. I
remember some articles on this topic, but it was long long ago...

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

Re: How many hardware threads?

[Warren]

Dmitry A. Kazakov expounded in
news:xah7sg1n8ib8$.26txy5fbnmui.dlg@40tude.net: 

> On Sun, 11 Jul 2010 20:47:41 -0400, Peter C. Chapin wrote:
> 
>> I see a couple of difficulties with writing effective parallel
>> programs for "ordinary" applications (that is, applications that are
>> not embarrassingly parallel). One difficulty is load balancing: how
...
> 
> Well, maybe, but I don't think it would bring much. Especially because
> normally cores support multi-tasking. It would be more important for
> the architectures with the cores that do not (GPU etc).

I was thinking about GPUs recently. Is there any Ada efforts
aimed in that direction?  

I've read about C based interfaces (CUDA) for working with GPUs, 
which naturally aroused the Ada language question.

Warren

Re: How many hardware threads?

[Gene]

On Jul 12, 3:40 am, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
wrote:
> On Sun, 11 Jul 2010 20:47:41 -0400, Peter C. Chapin wrote:
> > I see a couple of difficulties with writing effective parallel programs
> > for "ordinary" applications (that is, applications that are not
> > embarrassingly parallel). One difficulty is load balancing: how can one
> > decompose a problem to keep all processors reasonably busy? The other
> > difficulty is scalability: how can one design a single program that can
> > use 2, 4, 16, 128, or more processors effectively without knowing ahead
> > of time exactly how many processors there will be? I'm not an expert in
> > Ada tasking but it seems like these questions are as big a problem for
> > Ada as they are for any other language environment.
>
> Back in 90's, during the era of transputers, concurrent algorithms were
> decomposed knowing in advance the number of processors and the topology of
> the network of. (Unlike to multi-cores the transputers didn't share memory,
> they communicate over serial links connected physically) That time the
> consensus was that the problem is not solvable in general. So you designed
> up front both the algorithm and the topology.
>
> > I'm not an expert in
> > Ada tasking but it seems like these questions are as big a problem for
> > Ada as they are for any other language environment.
> > I'm not looking for a solution to all tasking problems here. But there
> > is one feature that seems like a necessary prerequisite to such a
> > solution. The language (or its standard library) needs to provide a
> > portable way for the program to determine how many hardware threads are
> > available.
>
> Well, maybe, but I don't think it would bring much. Especially because
> normally cores support multi-tasking. It would be more important for the
> architectures with the cores that do not (GPU etc).
>
> BTW, "hardware thread" = core? processor? ALU + an independent memory
> channel? etc. It is quite difficult to define and the algorithm's
> performance may heavily depend on the subtleness. ARG would say, look, it
> does not make sense for all platforms, forget it.
>
> > I'm about to write a simple program that decomposes into parallel,
> > compute-bound tasks quite nicely. How many such tasks should I create?
>
> Back in time it was popular to make it adaptive. I.e. you monitor the
> performance and adjust the size of the working threads pool as you go. I
> remember some articles on this topic, but it was long long ago...
>
> --
> Regards,
> Dmitry A. Kazakovhttp://www.dmitry-kazakov.de

Dmitry has it exactly right.  When a "hardware thread" can be anything
from a fraction of a core to a node on an Ethernet-connected cluster,
how many you have is not such an important question.

Guessing high and allowing the OS to sort things out has severe
limitations.  What to guess?  4? 16? 256?

When there is only a small number of independent performance control
variables, e.g. one in the case of a common thread pool, the self-
monitoring and adjustment scheme is the only one with legs.

Other multi-threading models like work stealing present a more complex
tuning problem.  Evolutionary (genetic) algorithms ought to be a
powerful way for software to adapt to its own environment. Is there
anyone doing work on this?

Re: How many hardware threads?

[Shark8]

> Evolutionary (genetic) algorithms ought to be a
> powerful way for software to adapt to its own environment. Is there
> anyone doing work on this?

Gene: Father of the Cylons.
;)

Re: How many hardware threads?

[anon]

In <4c3a65d7$0$2405$4d3efbfe@news.sover.net>, "Peter C. Chapin" <pcc482719@gmail.com> writes:
>As we all know there is currently a lot of "buzz" about parallel
>programming and about the "crisis in software development" that is
>associated with it. People using languages with weak support for
>concurrency are now wondering how they will use multi-core systems
>effectively and reliably. Of course Ada already has decent support for
>concurrency so part of the problem is solved for those of us using Ada.
>
>But not all of the problem...
>
>I see a couple of difficulties with writing effective parallel programs
>for "ordinary" applications (that is, applications that are not
>embarrassingly parallel). One difficulty is load balancing: how can one
>decompose a problem to keep all processors reasonably busy? The other
>difficulty is scalability: how can one design a single program that can
>use 2, 4, 16, 128, or more processors effectively without knowing ahead
>of time exactly how many processors there will be? I'm not an expert in
>Ada tasking but it seems like these questions are as big a problem for
>Ada as they are for any other language environment.
>
>I'm not looking for a solution to all tasking problems here. But there
>is one feature that seems like a necessary prerequisite to such a
>solution. The language (or its standard library) needs to provide a
>portable way for the program to determine how many hardware threads are
>available.
>
>I'm about to write a simple program that decomposes into parallel,
>compute-bound tasks quite nicely. How many such tasks should I create? I
>could ask the user to provide the number as a command line argument or
>in a configuration file. Yet it seems like the program should just be
>able to figure it out. Does Ada have a standard way of doing that? I
>didn't see anything in my (admittedly short) review.
>
>Thanks!
>
>Peter

The normal programs should never need to know how many processors or if 
the processor on this machine or another. Because the job-scheduler 
sub-system of todays OS decides what processor to place the task and 
tries to maintain a balance load.  And in some of these systems they 
create anywhere from 1 to 32 or more virtual systems out of one or more 
processor cores so it might be a little too OS demanding research and 
programming for a initial parallel program.  Plus,  how do you deal with 
the other OS tasks and sub-system lplus the other user background tasks.
So, unless you are design a system that requires a number of processors I 
would skip trying to control processor usages for now. Get the program 
working first.

As for the number of tasks and memory size.  Well the number of task 
depends on your "Algorithm and Memory" requirements.  Data memory for 
each task should be keep at a system page size to reduce number of page 
swapping during task switching. In calculating: the total memory requirements 
divided by system page size should give you a idea of the number of tasks 
that you can use.

Note: back in the 80s and 90s there were a number of languages that would 
use the "Algorithm and Memory" requirements as well as other factors during 
compiling to build a balance number of task.  A lot of these languages were 
design to be used on a Cray system with only a small OS task and 
sub-systems running.

Re: How many hardware threads?

[Ludovic Brenta]

I can see the value in having your program discover the number of
hardware threads and starting one task on each. This value, however,
is only for quick and dirty solutions. A proper, more long-term and
Ada-like solution, takes into account a lot of factors:

* if a single processor core provides several threads, these threads
share execution units in the core, so assigning compute-intensive
tasks to such threads is counter-productive; in contrast, assigning
tasks that spend a lot of time waiting for external events to occur is
a good idea. So, for your problem, you probably want at most one task
per core, not one task per thread.

* if hardware threads or cores share a common data cache, using too
many tasks may result in cache contention and slow-downs.

* each task will need virtual memory; possibly lots of it; and backed
up by physical memory or you'll cause thrashing. So the number of
tasks you can run is constrained not only by the amount of hardware
threads and cores but also by the amount of physical memory you can
allocate to your program.

* finally, the system administrator must have the last word on how
many tasks your program should use; they might choose to spare one
processor core for the OS or interactive use while your program runs
in the background; or they can run several programs concurrently and
only allocate a fraction of the processors available to your program.

So, having your program discover the number of threads (more usefully,
cores) in the system should only provide a hint as to how many tasks
you can start and you should also provide at least a command-line
option for use by the administrator.

HTH

--
Ludovic Brenta.

Re: How many hardware threads?

[Egil Høvik]

On Jul 12, 2:47 am, "Peter C. Chapin" <pcc482...@gmail.com> wrote:
> As we all know there is currently a lot of "buzz" about parallel
> programming and about the "crisis in software development" that is
> associated with it. People using languages with weak support for
> concurrency are now wondering how they will use multi-core systems
> effectively and reliably. Of course Ada already has decent support for
> concurrency so part of the problem is solved for those of us using Ada.
>
> But not all of the problem...
>
> I see a couple of difficulties with writing effective parallel programs
> for "ordinary" applications (that is, applications that are not
> embarrassingly parallel). One difficulty is load balancing: how can one
> decompose a problem to keep all processors reasonably busy? The other
> difficulty is scalability: how can one design a single program that can
> use 2, 4, 16, 128, or more processors effectively without knowing ahead
> of time exactly how many processors there will be? I'm not an expert in
> Ada tasking but it seems like these questions are as big a problem for
> Ada as they are for any other language environment.
>
> I'm not looking for a solution to all tasking problems here. But there
> is one feature that seems like a necessary prerequisite to such a
> solution. The language (or its standard library) needs to provide a
> portable way for the program to determine how many hardware threads are
> available.
>
> I'm about to write a simple program that decomposes into parallel,
> compute-bound tasks quite nicely. How many such tasks should I create? I
> could ask the user to provide the number as a command line argument or
> in a configuration file. Yet it seems like the program should just be
> able to figure it out. Does Ada have a standard way of doing that? I
> didn't see anything in my (admittedly short) review.
>
> Thanks!
>
> Peter


Have a look at this proposal for Ada 2012:
http://www.ada-auth.org/cgi-bin/cvsweb.cgi/ai05s/ai05-0167-1.txt?rev=1.4

--
~egilhh