* Ada 2012 automatic concurrency? @ 2012-12-25 17:26 charleshixsn 2012-12-26 22:02 ` John B. Matthews 2012-12-26 22:55 ` Niklas Holsti 0 siblings, 2 replies; 10+ messages in thread From: charleshixsn @ 2012-12-25 17:26 UTC (permalink / raw) 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? ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Ada 2012 automatic concurrency? 2012-12-25 17:26 Ada 2012 automatic concurrency? charleshixsn @ 2012-12-26 22:02 ` John B. Matthews 2012-12-26 22:55 ` Niklas Holsti 1 sibling, 0 replies; 10+ messages in thread From: John B. Matthews @ 2012-12-26 22:02 UTC (permalink / raw) 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> ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Ada 2012 automatic concurrency? 2012-12-25 17:26 Ada 2012 automatic concurrency? charleshixsn 2012-12-26 22:02 ` John B. Matthews @ 2012-12-26 22:55 ` Niklas Holsti 2012-12-27 5:57 ` charleshixsn 1 sibling, 1 reply; 10+ messages in thread From: Niklas Holsti @ 2012-12-26 22:55 UTC (permalink / raw) 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 . @ . ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Ada 2012 automatic concurrency? 2012-12-26 22:55 ` Niklas Holsti @ 2012-12-27 5:57 ` charleshixsn 2012-12-27 8:59 ` Dirk Heinrichs ` (2 more replies) 0 siblings, 3 replies; 10+ messages in thread From: charleshixsn @ 2012-12-27 5:57 UTC (permalink / raw) 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? ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Ada 2012 automatic concurrency? 2012-12-27 5:57 ` charleshixsn @ 2012-12-27 8:59 ` Dirk Heinrichs 2012-12-27 11:22 ` Brian Drummond 2012-12-27 22:13 ` Randy Brukardt 2012-12-27 14:27 ` Jeffrey Carter 2012-12-27 19:06 ` Niklas Holsti 2 siblings, 2 replies; 10+ messages in thread From: Dirk Heinrichs @ 2012-12-27 8:59 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Ada 2012 automatic concurrency? 2012-12-27 8:59 ` Dirk Heinrichs @ 2012-12-27 11:22 ` Brian Drummond 2012-12-27 22:13 ` Randy Brukardt 1 sibling, 0 replies; 10+ messages in thread From: Brian Drummond @ 2012-12-27 11:22 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Ada 2012 automatic concurrency? 2012-12-27 8:59 ` Dirk Heinrichs 2012-12-27 11:22 ` Brian Drummond @ 2012-12-27 22:13 ` Randy Brukardt 1 sibling, 0 replies; 10+ messages in thread From: Randy Brukardt @ 2012-12-27 22:13 UTC (permalink / raw) "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. ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Ada 2012 automatic concurrency? 2012-12-27 5:57 ` charleshixsn 2012-12-27 8:59 ` Dirk Heinrichs @ 2012-12-27 14:27 ` Jeffrey Carter 2012-12-27 20:13 ` tmoran 2012-12-27 19:06 ` Niklas Holsti 2 siblings, 1 reply; 10+ messages in thread From: Jeffrey Carter @ 2012-12-27 14:27 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Ada 2012 automatic concurrency? 2012-12-27 14:27 ` Jeffrey Carter @ 2012-12-27 20:13 ` tmoran 0 siblings, 0 replies; 10+ messages in thread From: tmoran @ 2012-12-27 20:13 UTC (permalink / raw) > 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. ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Ada 2012 automatic concurrency? 2012-12-27 5:57 ` charleshixsn 2012-12-27 8:59 ` Dirk Heinrichs 2012-12-27 14:27 ` Jeffrey Carter @ 2012-12-27 19:06 ` Niklas Holsti 2 siblings, 0 replies; 10+ messages in thread From: Niklas Holsti @ 2012-12-27 19:06 UTC (permalink / raw) 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 . @ . ^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2012-12-27 22:13 UTC | newest] Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2012-12-25 17:26 Ada 2012 automatic concurrency? charleshixsn 2012-12-26 22:02 ` John B. Matthews 2012-12-26 22:55 ` Niklas Holsti 2012-12-27 5:57 ` charleshixsn 2012-12-27 8:59 ` Dirk Heinrichs 2012-12-27 11:22 ` Brian Drummond 2012-12-27 22:13 ` Randy Brukardt 2012-12-27 14:27 ` Jeffrey Carter 2012-12-27 20:13 ` tmoran 2012-12-27 19:06 ` Niklas Holsti
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox