Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #41625 > unrolled thread
| Started by | dunno <dunno@dunno.dunno> |
|---|---|
| First post | 2015-08-31 07:20 +0000 |
| Last post | 2015-09-14 18:21 -0700 |
| Articles | 20 on this page of 115 — 25 participants |
Back to article view | Back to comp.lang.forth
GA144 use cases dunno <dunno@dunno.dunno> - 2015-08-31 07:20 +0000
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-08-31 09:55 -0400
Re: GA144 use cases Syd Rumpo <usenet@nononono.co.uk> - 2015-08-31 16:49 +0100
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-08-31 18:35 -0400
Re: GA144 use cases Dennis Ruffer <daruffer@gmail.com> - 2015-08-31 19:08 -0700
Re: GA144 use cases Mux <Yvo.Zoer@gmail.com> - 2015-09-02 10:57 -0700
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-09-02 14:17 -0400
Re: GA144 use cases Mux <Yvo.Zoer@gmail.com> - 2015-09-02 11:28 -0700
Re: GA144 use cases hughaguilar96@gmail.com - 2015-09-02 13:41 -0700
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-09-02 16:50 -0400
Re: GA144 use cases Mux <Yvo.Zoer@gmail.com> - 2015-09-02 15:03 -0700
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-09-02 18:18 -0400
Re: GA144 use cases Mux <Yvo.Zoer@gmail.com> - 2015-09-02 16:14 -0700
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-09-02 20:40 -0400
Re: GA144 use cases Greg <borota@gmail.com> - 2015-09-02 17:53 -0700
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-09-02 21:25 -0400
Re: GA144 use cases Mux <Yvo.Zoer@gmail.com> - 2015-09-02 22:28 -0700
Re: GA144 use cases Paul Rubin <no.email@nospam.invalid> - 2015-09-02 22:53 -0700
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-09-03 11:32 -0400
Re: GA144 use cases Paul Rubin <no.email@nospam.invalid> - 2015-09-03 11:57 -0700
Re: GA144 use cases anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-09-03 10:35 +0000
Re: GA144 use cases Bernd Paysan <bernd.paysan@gmx.de> - 2015-09-03 15:54 +0200
Re: GA144 use cases anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-09-03 16:11 +0000
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-09-03 13:06 -0400
Re: GA144 use cases anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-09-04 08:07 +0000
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-09-04 11:49 -0400
Re: GA144 use cases anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-09-05 11:06 +0000
Re: GA144 use cases Paul Rubin <no.email@nospam.invalid> - 2015-09-05 09:05 -0700
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-09-05 12:59 -0400
Re: GA144 use cases mhx@iae.nl - 2015-09-05 10:56 -0700
Re: GA144 use cases anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-09-06 14:29 +0000
Re: GA144 use cases Bernd Paysan <bernd.paysan@gmx.de> - 2015-09-03 22:08 +0200
Re: GA144 use cases Paul Rubin <no.email@nospam.invalid> - 2015-09-03 14:00 -0700
Re: GA144 use cases Bernd Paysan <bernd.paysan@gmx.de> - 2015-09-04 01:28 +0200
Re: GA144 use cases franck.bensusan@gmail.com - 2015-09-03 23:04 -0700
Re: GA144 use cases anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-09-04 08:24 +0000
Re: GA144 use cases Bernd Paysan <bernd.paysan@gmx.de> - 2015-09-04 15:09 +0200
Re: GA144 use cases anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-09-05 15:10 +0000
Re: GA144 use cases Bernd Paysan <bernd.paysan@gmx.de> - 2015-09-05 22:04 +0200
Re: GA144 use cases anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-09-06 14:51 +0000
Re: GA144 use cases Bernd Paysan <bernd.paysan@gmx.de> - 2015-09-06 22:51 +0200
Re: GA144 use cases Greg <borota@gmail.com> - 2015-09-06 17:30 -0700
Re: GA144 use cases Paul Rubin <no.email@nospam.invalid> - 2015-09-04 22:27 -0700
Re: GA144 use cases Bernd Paysan <bernd.paysan@gmx.de> - 2015-09-05 13:07 +0200
Re: GA144 use cases anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-09-05 11:22 +0000
Re: GA144 use cases anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-09-04 08:14 +0000
Re: GA144 use cases Bernd Paysan <bernd.paysan@gmx.de> - 2015-09-04 15:13 +0200
Re: GA144 use cases anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-09-05 16:06 +0000
Re: GA144 use cases Bernd Paysan <bernd.paysan@gmx.de> - 2015-09-05 21:05 +0200
Re: GA144 use cases anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-09-06 14:37 +0000
Re: GA144 use cases Andrew Haley <andrew29@littlepinkcloud.invalid> - 2015-11-30 04:17 -0600
Re: GA144 use cases Bernd Paysan <bernd.paysan@gmx.de> - 2015-12-01 23:06 +0100
Re: GA144 use cases Mark Wills <markwills1970@gmail.com> - 2015-09-03 00:05 -0700
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-09-03 13:08 -0400
Re: GA144 use cases forther <forther@gmail.com> - 2015-09-07 11:26 -0700
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-09-02 15:15 -0400
Re: GA144 use cases forther <forther@gmail.com> - 2015-09-07 11:21 -0700
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-11-30 16:33 -0500
Re: GA144 use cases forther <forther@gmail.com> - 2015-12-03 12:12 -0800
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-12-03 16:10 -0500
Re: GA144 use cases Jason Damisch <jasondamisch@yahoo.com> - 2015-09-02 12:10 -0700
Re: GA144 use cases Stefan Mauerhofer <smauerhofer@androsoft.ch> - 2015-09-03 01:27 -0700
Re: GA144 use cases Syd Rumpo <usenet@nononono.co.uk> - 2015-09-03 13:32 +0100
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-09-03 11:32 -0400
Re: GA144 use cases mhx@iae.nl (Marcel Hendrix) - 2015-09-03 18:57 +0200
Re: GA144 use cases Bernd Paysan <bernd.paysan@gmx.de> - 2015-09-03 23:58 +0200
Re: GA144 use cases anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-09-04 07:52 +0000
Re: GA144 use cases Waldek Hebisch <hebisch@antispam.uni.wroc.pl> - 2015-09-05 16:32 +0000
Re: GA144 use cases mhx@iae.nl - 2015-09-05 10:52 -0700
Re: GA144 use cases Bernd Paysan <bernd.paysan@gmx.de> - 2015-09-05 22:11 +0200
Re: GA144 use cases anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-09-06 14:18 +0000
Re: GA144 use cases anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-09-07 07:49 +0000
Re: GA144 use cases Waldek Hebisch <hebisch@math.uni.wroc.pl> - 2015-09-05 23:42 +0000
Re: GA144 use cases Paul Rubin <no.email@nospam.invalid> - 2015-09-05 17:25 -0700
Re: GA144 use cases Stefan Mauerhofer <smauerhofer@androsoft.ch> - 2015-09-07 03:18 -0700
Re: GA144 use cases Raimond Dragomir <raimond.dragomir@gmail.com> - 2015-09-07 03:31 -0700
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-09-07 15:06 -0400
Re: GA144 use cases Stefan Mauerhofer <smauerhofer@androsoft.ch> - 2015-09-08 21:41 -0700
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-09-09 02:54 -0400
Re: GA144 use cases Stefan Mauerhofer <smauerhofer@androsoft.ch> - 2015-09-09 03:02 -0700
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-09-09 16:55 -0400
Re: GA144 use cases Paul Rubin <no.email@nospam.invalid> - 2015-09-09 20:12 -0700
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-09-09 23:40 -0400
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-09-09 23:43 -0400
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-09-10 00:07 -0400
Re: GA144 use cases Stefan Mauerhofer <smauerhofer@androsoft.ch> - 2015-09-09 21:55 -0700
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-09-10 01:43 -0400
Re: GA144 use cases Stefan Mauerhofer <smauerhofer@androsoft.ch> - 2015-09-09 23:49 -0700
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-09-10 14:43 -0400
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-09-10 16:10 -0400
Re: GA144 use cases Stefan Mauerhofer <smauerhofer@androsoft.ch> - 2015-09-12 03:15 -0700
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-09-12 10:28 -0400
Re: GA144 use cases Greg <abiforth@gmail.com> - 2015-09-13 13:05 -0700
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-09-13 18:59 -0400
Re: GA144 use cases Greg <abiforth@gmail.com> - 2015-09-13 18:42 -0700
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-09-13 22:47 -0400
Re: GA144 use cases Greg <abiforth@gmail.com> - 2015-09-13 21:24 -0700
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-09-14 02:00 -0400
Re: GA144 use cases borota@gmail.com - 2015-09-14 08:35 -0700
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-09-14 12:06 -0400
Re: GA144 use cases borota@gmail.com - 2015-09-14 09:33 -0700
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-09-14 13:25 -0400
Re: GA144 use cases Greg <borota@gmail.com> - 2015-09-14 14:17 -0700
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-09-14 18:12 -0400
Re: GA144 use cases Greg <schmegner@gmail.com> - 2015-09-14 18:15 -0700
Re: GA144 use cases rickman <gnuarm@gmail.com> - 2015-09-14 22:16 -0400
Re: GA144 use cases Greg <borota@gmail.com> - 2015-09-18 14:50 -0700
Re: GA144 use cases Jason Damisch <jasondamisch@yahoo.com> - 2015-09-18 15:11 -0700
Re: GA144 use cases Greg <borota@gmail.com> - 2015-09-19 05:32 -0700
Re: GA144 use cases Dennis Ruffer <daruffer@gmail.com> - 2015-09-19 08:39 -0700
Re: GA144 use cases Greg <borota@gmail.com> - 2015-09-20 19:03 -0700
Re: GA144 use cases Dennis Ruffer <daruffer@gmail.com> - 2015-09-21 06:44 -0700
Re: GA144 use cases Dennis Ruffer <daruffer@gmail.com> - 2015-09-22 13:10 -0700
Re: GA144 use cases Mark Wills <markwills1970@gmail.com> - 2015-09-18 16:18 -0700
Re: GA144 use cases schmegner@gmail.com - 2015-09-14 18:21 -0700
Page 2 of 6 — ← Prev page 1 [2] 3 4 5 6 Next page →
| From | anton@mips.complang.tuwien.ac.at (Anton Ertl) |
|---|---|
| Date | 2015-09-03 10:35 +0000 |
| Message-ID | <2015Sep3.123542@mips.complang.tuwien.ac.at> |
| In reply to | #41685 |
Greg <borota@gmail.com> writes:
>In this interview: http://www.informit.com/articles/article.aspx?p=1193856
>Donald Knuth says: "Let me put it this way: During the past 50 years, I've
>written well over a thousand programs, many of which have substantial size.
>I can't think of even five of those programs that would have been enhanced
>noticeably by parallelism or multi-threading."
I think that's more a sign that he did not think about parallelism
very much.
The next sentence is: "Surely, for example, multiple processors are no
help to TeX.[1]".
And then there is a footnote (makes me wonder how that interview was
conducted) that says:
|[1] My colleague Kunle Olukotun points out that, if the usage of TeX
|became a major bottleneck so that people had a dozen processors and
|really needed to speed up their typesetting terrifically, a
|super-parallel version of TeX could be developed that uses
|"speculation" to typeset a dozen chapters at once: Each chapter could
|be typeset under the assumption that the previous chapters don't do
|anything strange to mess up the default logic. If that assumption
|fails, we can fall back on the normal method of doing a chapter at a
|time; but in the majority of cases, when only normal typesetting was
|being invoked, the processing would indeed go 12 times faster. Users
|who cared about speed could adapt their behavior and use TeX in a
|disciplined way.
And the same goes for paragraphs. OTOH, TeX is so fast on modern CPUs
that one can really say that paralellizing it would not enhance it.
Also, parallelizing it would require quite a bit of effort.
>So maybe that's the problem, most programs that we write are sequential in
>nature. Or at least our brains have a harder time solving problems by slicing
>into small independent units and then assembling results together.
I don't think so. Small units are not hard, but inefficient (slower
than sequential). If you want to have a speedup from parallelizing,
you need relatively big units; and the unit size is dependent on the
number of cores and the input data, and all that is not very
compatible with he usual abstraction mechanisms that we use to conquer
the complexity of programming.
- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2015: http://www.rigwit.co.uk/EuroForth2015/
[toc] | [prev] | [next] | [standalone]
| From | Bernd Paysan <bernd.paysan@gmx.de> |
|---|---|
| Date | 2015-09-03 15:54 +0200 |
| Message-ID | <ms9jb8$fre$1@dont-email.me> |
| In reply to | #41693 |
Anton Ertl wrote: > And the same goes for paragraphs. OTOH, TeX is so fast on modern CPUs > that one can really say that paralellizing it would not enhance it. > Also, parallelizing it would require quite a bit of effort. Well, TeX is written in an "unmaintainable" programming language, c-web. Let's go with the paragraphs: TeX tries to render the paragraph with several different attempts, and chooses the best-"looking", with a metric of what is "best". That is fairly easy to parallelize, you just run all the trials in parallel, and then collect the results. The one with the lowest badness wins, and the others get deleted. The problem with parallelism I have is not that I can't imagine it, but that the overhead is too large. E.g. take net2o: I send and receive messages (each takes time in the kernel), and I decrypt and encrypt them. With a four-core CPU, I could run that in four tasks. However, when trying that, I found that the IPC is killing the performance. These tasks don't take too much time - en/decrypting a 1k block takes 10k cycles, and the IPC then takes about as long, too, so all the gain goes down the flush. What we need for this sort of lightweight tasks done in parallel is a lightweight, fast, in-hardware IPC, similar in spirit to the GA144 connections or Transputer links. Such a link would pass up to one word (that's 64 bit now) in a go, and each process can wait for data from a link or several links (whichever comes first, will be used). The links would be routed links, so there's no need to put a task on a specific core. And the registers of a waiting task would still be kept in the register file; maybe you can have 2 active tasks per core (SMT), and 8 waiting. If the OS decides that one task needs to be swapped out of the core, its links become dangling, and will send a "wake me up" token to the scheduler task (which the OS never throws out of a core). This sort of GA144-like nanosecond-turnaround for IPC is necessary the microseconds we need today is completely inacceptable for distributing small tasks. And many tasks that can be parallelized *are* small tasks. The next issue I have is that the shared memory approach is broken, it is way too hard to debug. I'd prefer a single-writer, multiple reader shared memory approach, so each process would have its writable memory, and all other threads can only read that. You may have common shared memory for something like the root pointers of RCU trees (you can read and copy from other nodes into your own writable memory, and then update the root pointer), which need more care, but most of the memory really shouldn't be writable by every thread. A common address space is still ok. That could be done with some more fields in the page table entry, having access rights for the thread itself and others. The thread itself is identified by some higher bits in the virtual address, so the property "this thread" vs "other threads" is decided by the first level page table. -- Bernd Paysan "If you want it done right, you have to do it yourself" net2o ID: kQusJzA;7*?t=uy@X}1GWr!+0qqp_Cn176t4(dQ* http://bernd-paysan.de/
[toc] | [prev] | [next] | [standalone]
| From | anton@mips.complang.tuwien.ac.at (Anton Ertl) |
|---|---|
| Date | 2015-09-03 16:11 +0000 |
| Message-ID | <2015Sep3.181126@mips.complang.tuwien.ac.at> |
| In reply to | #41696 |
Bernd Paysan <bernd.paysan@gmx.de> writes:
>Anton Ertl wrote:
>> And the same goes for paragraphs. OTOH, TeX is so fast on modern CPUs
>> that one can really say that paralellizing it would not enhance it.
>> Also, parallelizing it would require quite a bit of effort.
>
>Well, TeX is written in an "unmaintainable" programming language, c-web.
>Let's go with the paragraphs: TeX tries to render the paragraph with several
>different attempts, and chooses the best-"looking", with a metric of what is
>"best". That is fairly easy to parallelize, you just run all the trials in
>parallel, and then collect the results. The one with the lowest badness
>wins, and the others get deleted.
And you can do many paragraphs in parallel.
>The problem with parallelism I have is not that I can't imagine it, but that
>the overhead is too large. E.g. take net2o: I send and receive messages
>(each takes time in the kernel), and I decrypt and encrypt them. With a
>four-core CPU, I could run that in four tasks.
>
>However, when trying that, I found that the IPC is killing the performance.
>These tasks don't take too much time - en/decrypting a 1k block takes 10k
>cycles, and the IPC then takes about as long, too, so all the gain goes down
>the flush.
>
>What we need for this sort of lightweight tasks done in parallel is a
>lightweight, fast, in-hardware IPC, similar in spirit to the GA144
>connections or Transputer links.
If it's just communication, that can go pretty fast through shared
memory; on a single-socket multi-core CPU, that's a trip through the
L3 cache (<100 cycles latency for the first cache line; and you can
communicate pretty long blocks with pretty low additional overhead).
If it's synchronization, that's a bit more expensive, but also
determined by L3 latency in such a system if you do it on the user
level (with locked instructions or similar).
If you manage to use large blocks and synchronization is rare, you can
make good use of multiple cores. OTOH, if you need to create lots of
short-running tasks and combine their results, you will probably see a
lot of overhead.
>The next issue I have is that the shared memory approach is broken, it is
>way too hard to debug.
Yes, especially with the perverse consistency models that some
architectures provide. But as a primitive for better models (such as
pipelining), it's not too bad. I first thought that one would need
something like links for implementing pipelines, but it can be done
with shared memory.
> I'd prefer a single-writer, multiple reader shared
>memory approach, so each process would have its writable memory, and all
>other threads can only read that. You may have common shared memory for
>something like the root pointers of RCU trees (you can read and copy from
>other nodes into your own writable memory, and then update the root
>pointer), which need more care, but most of the memory really shouldn't be
>writable by every thread. A common address space is still ok.
>
>That could be done with some more fields in the page table entry, having
>access rights for the thread itself and others. The thread itself is
>identified by some higher bits in the virtual address, so the property "this
>thread" vs "other threads" is decided by the first level page table.
You can get that by mmap()ing the memory once read-only and once
read/write. If you want to mmapt them to the same address, I think
you need to do that in two different processes.
But that would still expose the programs to the perversities of the
consistency models.
- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2015: http://www.rigwit.co.uk/EuroForth2015/
[toc] | [prev] | [next] | [standalone]
| From | rickman <gnuarm@gmail.com> |
|---|---|
| Date | 2015-09-03 13:06 -0400 |
| Message-ID | <ms9uj8$1f8$1@dont-email.me> |
| In reply to | #41699 |
On 9/3/2015 12:11 PM, Anton Ertl wrote: > Bernd Paysan <bernd.paysan@gmx.de> writes: >> Anton Ertl wrote: >>> And the same goes for paragraphs. OTOH, TeX is so fast on modern CPUs >>> that one can really say that paralellizing it would not enhance it. >>> Also, parallelizing it would require quite a bit of effort. >> >> Well, TeX is written in an "unmaintainable" programming language, c-web. >> Let's go with the paragraphs: TeX tries to render the paragraph with several >> different attempts, and chooses the best-"looking", with a metric of what is >> "best". That is fairly easy to parallelize, you just run all the trials in >> parallel, and then collect the results. The one with the lowest badness >> wins, and the others get deleted. > > And you can do many paragraphs in parallel. I think the point is that until the previous paragraphs have been processed, you can't finalize the current paragraph. It may have different margins or be on a page break, etc. all dependent on previous document code. Like many programs, I expect there would be ways to parallelize even word processor code if it is considered. Some have said parallel code needs to be done at a high level, but I think it would be better done on the details. But then I am thinking of low level code such as would be run on the GA144, not parallel code run on the x86 megalith. -- Rick
[toc] | [prev] | [next] | [standalone]
| From | anton@mips.complang.tuwien.ac.at (Anton Ertl) |
|---|---|
| Date | 2015-09-04 08:07 +0000 |
| Message-ID | <2015Sep4.100730@mips.complang.tuwien.ac.at> |
| In reply to | #41702 |
rickman <gnuarm@gmail.com> writes:
>On 9/3/2015 12:11 PM, Anton Ertl wrote:
>> Bernd Paysan <bernd.paysan@gmx.de> writes:
>>> Anton Ertl wrote:
>> And you can do many paragraphs in parallel.
>
>I think the point is that until the previous paragraphs have been
>processed, you can't finalize the current paragraph. It may have
>different margins or be on a page break, etc. all dependent on previous
>document code.
Different margins are rare for TeX documents, so you can format the
paragraph assuming the usual margins, and if the margins for the
current paragraph are as you assumed, you don't need to recompute it.
Page breaks don't influence paragraphs in TeX AFAIK, because the model
is that text is rendered to a scroll, and that is then cut into pages.
Also, TeX (at least LaTeX) takes page numbers and other references
from the last run, so you don't get any dependencies from that, either
(you may need to rerun it until it's stable, but that also happens for
the sequential version).
- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2015: http://www.rigwit.co.uk/EuroForth2015/
[toc] | [prev] | [next] | [standalone]
| From | rickman <gnuarm@gmail.com> |
|---|---|
| Date | 2015-09-04 11:49 -0400 |
| Message-ID | <mscefi$irl$2@dont-email.me> |
| In reply to | #41717 |
On 9/4/2015 4:07 AM, Anton Ertl wrote: > rickman <gnuarm@gmail.com> writes: >> On 9/3/2015 12:11 PM, Anton Ertl wrote: >>> Bernd Paysan <bernd.paysan@gmx.de> writes: >>>> Anton Ertl wrote: >>> And you can do many paragraphs in parallel. >> >> I think the point is that until the previous paragraphs have been >> processed, you can't finalize the current paragraph. It may have >> different margins or be on a page break, etc. all dependent on previous >> document code. > > Different margins are rare for TeX documents, so you can format the > paragraph assuming the usual margins, and if the margins for the > current paragraph are as you assumed, you don't need to recompute it. > Page breaks don't influence paragraphs in TeX AFAIK, because the model > is that text is rendered to a scroll, and that is then cut into pages. > Also, TeX (at least LaTeX) takes page numbers and other references > from the last run, so you don't get any dependencies from that, either > (you may need to rerun it until it's stable, but that also happens for > the sequential version). I'm not sure the paged waterfall approach works properly. Anytime you have an illustration, table, etc, it will be fitted into the page depending on the page break. If text is flowing around it potentially two pages will need to be reformatted depending on which page the illustration ends up on. How is this handled? -- Rick
[toc] | [prev] | [next] | [standalone]
| From | anton@mips.complang.tuwien.ac.at (Anton Ertl) |
|---|---|
| Date | 2015-09-05 11:06 +0000 |
| Message-ID | <2015Sep5.130637@mips.complang.tuwien.ac.at> |
| In reply to | #41727 |
rickman <gnuarm@gmail.com> writes:
>On 9/4/2015 4:07 AM, Anton Ertl wrote:
>> rickman <gnuarm@gmail.com> writes:
>>> On 9/3/2015 12:11 PM, Anton Ertl wrote:
>>>> Bernd Paysan <bernd.paysan@gmx.de> writes:
>>>>> Anton Ertl wrote:
>>>> And you can do many paragraphs in parallel.
>>>
>>> I think the point is that until the previous paragraphs have been
>>> processed, you can't finalize the current paragraph. It may have
>>> different margins or be on a page break, etc. all dependent on previous
>>> document code.
>>
>> Different margins are rare for TeX documents, so you can format the
>> paragraph assuming the usual margins, and if the margins for the
>> current paragraph are as you assumed, you don't need to recompute it.
>> Page breaks don't influence paragraphs in TeX AFAIK, because the model
>> is that text is rendered to a scroll, and that is then cut into pages.
>> Also, TeX (at least LaTeX) takes page numbers and other references
>> from the last run, so you don't get any dependencies from that, either
>> (you may need to rerun it until it's stable, but that also happens for
>> the sequential version).
>
>I'm not sure the paged waterfall approach works properly. Anytime you
>have an illustration, table, etc, it will be fitted into the page
>depending on the page break. If text is flowing around it potentially
>two pages will need to be reformatted depending on which page the
>illustration ends up on. How is this handled?
I have seen examples of shape-formatted text formatted with TeX, but
I did not follow how it was done. In LaTeX without special packages
for such things, floats (figures an tables) are full-width (a columns
wide or a page wide), so it does not affect paragraph formatting.
Even if you have a few paragraphs flowing around a figure, you just
need to reformat those, and can use the parallel-processed ones for
the majority of cases.
- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2015: http://www.rigwit.co.uk/EuroForth2015/
[toc] | [prev] | [next] | [standalone]
| From | Paul Rubin <no.email@nospam.invalid> |
|---|---|
| Date | 2015-09-05 09:05 -0700 |
| Message-ID | <87613o26n2.fsf@jester.gateway.pace.com> |
| In reply to | #41753 |
anton@mips.complang.tuwien.ac.at (Anton Ertl) writes: > Even if you have a few paragraphs flowing around a figure, you just > need to reformat those, and can use the parallel-processed ones for > the majority of cases. TeX is essentially an imperative programming language, e.g. any paragraph might have a command that changes the font size. Of course that completely changes the formatting of the next paragraph. It can also set the equivalent of mutable variables and things like that, which could also affect the next paragraph. I've seen some large TeX documents like manuals organized into multiple files, e.g. one file per chapter. I guess those could be done in parallel. There is some kind of two-pass formatting system in LaTeX where the first pass figures out the page numbers of cross-references so the second pass can fill them in. I guess that can also be used to deal with page-numbering the second chapter. I'm not sure exactly how it is done. I could imagine some cases where there is a chance of getting a wrong page number, so for the final production copy, you might have to format serially to be sure. Metafont of course should parallelize nicely, first in computing the shapes of all the letters, then in rasterizing them.
[toc] | [prev] | [next] | [standalone]
| From | rickman <gnuarm@gmail.com> |
|---|---|
| Date | 2015-09-05 12:59 -0400 |
| Message-ID | <msf6v9$2cl$1@dont-email.me> |
| In reply to | #41763 |
On 9/5/2015 12:05 PM, Paul Rubin wrote: > anton@mips.complang.tuwien.ac.at (Anton Ertl) writes: >> Even if you have a few paragraphs flowing around a figure, you just >> need to reformat those, and can use the parallel-processed ones for >> the majority of cases. > > TeX is essentially an imperative programming language, e.g. any > paragraph might have a command that changes the font size. Of course > that completely changes the formatting of the next paragraph. It can > also set the equivalent of mutable variables and things like that, which > could also affect the next paragraph. > > I've seen some large TeX documents like manuals organized into multiple > files, e.g. one file per chapter. I guess those could be done in > parallel. There is some kind of two-pass formatting system in LaTeX > where the first pass figures out the page numbers of cross-references so > the second pass can fill them in. I guess that can also be used to deal > with page-numbering the second chapter. I'm not sure exactly how it is > done. I could imagine some cases where there is a chance of getting a > wrong page number, so for the final production copy, you might have to > format serially to be sure. I had a compiler problem like this. The jump was a variable size instruction based on the address offset. The offset value could change the length of the instruction. The instruction length change could change the value of the offset again in a non-resolvable loop. In the end I had to leave the instruction format in the long form with an offset that would fit in the short form. -- Rick
[toc] | [prev] | [next] | [standalone]
| From | mhx@iae.nl |
|---|---|
| Date | 2015-09-05 10:56 -0700 |
| Message-ID | <c1cccaab-54fb-4b79-9b56-3dc2bba69f80@googlegroups.com> |
| In reply to | #41771 |
On Saturday, September 5, 2015 at 7:00:16 PM UTC+2, rickman wrote: > On 9/5/2015 12:05 PM, Paul Rubin wrote: > > anton@mips.complang.tuwien.ac.at (Anton Ertl) writes: > >> Even if you have a few paragraphs flowing around a figure, you just > >> need to reformat those, and can use the parallel-processed ones for > >> the majority of cases. > > > > TeX is essentially an imperative programming language, e.g. any > > paragraph might have a command that changes the font size. Of course > > that completely changes the formatting of the next paragraph. It can > > also set the equivalent of mutable variables and things like that, which > > could also affect the next paragraph. > > > > I've seen some large TeX documents like manuals organized into multiple > > files, e.g. one file per chapter. I guess those could be done in > > parallel. There is some kind of two-pass formatting system in LaTeX > > where the first pass figures out the page numbers of cross-references so > > the second pass can fill them in. I guess that can also be used to deal > > with page-numbering the second chapter. I'm not sure exactly how it is > > done. I could imagine some cases where there is a chance of getting a > > wrong page number, so for the final production copy, you might have to > > format serially to be sure. > > I had a compiler problem like this. The jump was a variable size > instruction based on the address offset. The offset value could change > the length of the instruction. The instruction length change could > change the value of the offset again in a non-resolvable loop. In the > end I had to leave the instruction format in the long form with an > offset that would fit in the short form. Because of the variable length transputer instructions, our metacompiler for tForth had that problem very frequently. I see it iForth too, but generous alignment can take care of it -- I am only interested in speed , not in size. -marcel
[toc] | [prev] | [next] | [standalone]
| From | anton@mips.complang.tuwien.ac.at (Anton Ertl) |
|---|---|
| Date | 2015-09-06 14:29 +0000 |
| Message-ID | <2015Sep6.162907@mips.complang.tuwien.ac.at> |
| In reply to | #41771 |
rickman <gnuarm@gmail.com> writes:
>On 9/5/2015 12:05 PM, Paul Rubin wrote:
>> I've seen some large TeX documents like manuals organized into multiple
>> files, e.g. one file per chapter. I guess those could be done in
>> parallel. There is some kind of two-pass formatting system in LaTeX
>> where the first pass figures out the page numbers of cross-references so
>> the second pass can fill them in. I guess that can also be used to deal
>> with page-numbering the second chapter. I'm not sure exactly how it is
>> done. I could imagine some cases where there is a chance of getting a
>> wrong page number, so for the final production copy, you might have to
>> format serially to be sure.
Serial formatting does not help, because for forward references you
would have to look into the future. If the references don't resolve
as predicted, you get a warning and you just rerun LaTeX. Nomally
(and I have never seen any deviation from this) it is fixed after the
second run. If it is not resolved after several runs, the solution is
to change the source such that this does not happen.
>I had a compiler problem like this. The jump was a variable size
>instruction based on the address offset. The offset value could change
>the length of the instruction. The instruction length change could
>change the value of the offset again in a non-resolvable loop. In the
>end I had to leave the instruction format in the long form with an
>offset that would fit in the short form.
That's a classic problem. The usual solution is to start with all
offsets short, have a pass and remember those that don't fit; repeat
the same, with long offsets for those that did not fit. Repeat until
everything fits in the space allocated to them. One can construct
funny problems where this is suboptimal, but in the usual case, this
is also optimal.
- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2015: http://www.rigwit.co.uk/EuroForth2015/
[toc] | [prev] | [next] | [standalone]
| From | Bernd Paysan <bernd.paysan@gmx.de> |
|---|---|
| Date | 2015-09-03 22:08 +0200 |
| Message-ID | <msa991$ga4$1@dont-email.me> |
| In reply to | #41699 |
Anton Ertl wrote: > If it's just communication, that can go pretty fast through shared > memory; on a single-socket multi-core CPU, that's a trip through the > L3 cache (<100 cycles latency for the first cache line; and you can > communicate pretty long blocks with pretty low additional overhead). No, the main problem is telling the other thread that there is some data for it. That's using an OS IPC call, and that takes several thousand cycles. You can pass around a lot of data between the cores; that works well. AMD's recent GPUs have hardware support for asynchronous tasks, and that includes activating them. That's the tough part, passing the data around is already solved. NVidia screwed that up completely, and as a result, using asyncronous tasks on a modern NVidia card (with DirectX 12) doesn't work. > If you manage to use large blocks and synchronization is rare, you can > make good use of multiple cores. OTOH, if you need to create lots of > short-running tasks and combine their results, you will probably see a > lot of overhead. Yes, and that's the problem. There are a lot of low-hanging fruits for parallelization which are short-running tasks. >>The next issue I have is that the shared memory approach is broken, it is >>way too hard to debug. > > Yes, especially with the perverse consistency models that some > architectures provide. But as a primitive for better models (such as > pipelining), it's not too bad. I first thought that one would need > something like links for implementing pipelines, but it can be done > with shared memory. Plus IPC, to notify the other task that there is something to do. Or you spin-loop, which means each task blocks an entire core, even if they don't have much work -> no a good idea. > You can get that by mmap()ing the memory once read-only and once > read/write. If you want to mmapt them to the same address, I think > you need to do that in two different processes. Multiple threads in one process all see the same mapping. It works between different processes, because they have different page tables. If you want to avoid that overhead, you need hardware support. > But that would still expose the programs to the perversities of the > consistency models. Yes. The consistency models are still a problem with single-writer, multiple-readers. -- Bernd Paysan "If you want it done right, you have to do it yourself" net2o ID: kQusJzA;7*?t=uy@X}1GWr!+0qqp_Cn176t4(dQ* http://bernd-paysan.de/
[toc] | [prev] | [next] | [standalone]
| From | Paul Rubin <no.email@nospam.invalid> |
|---|---|
| Date | 2015-09-03 14:00 -0700 |
| Message-ID | <877fo7gqvv.fsf@jester.gateway.sonic.net> |
| In reply to | #41706 |
Bernd Paysan <bernd.paysan@gmx.de> writes: > No, the main problem is telling the other thread that there is some data for > it. That's using an OS IPC call, and that takes several thousand cycles. > You can pass around a lot of data between the cores; that works well. In the uncontended case you check a futex in user space and proceed if there's something to do, or yield to the kernel if there's nothing to do. There's only IPC overhead if there's contention in which case you have to make a system call.
[toc] | [prev] | [next] | [standalone]
| From | Bernd Paysan <bernd.paysan@gmx.de> |
|---|---|
| Date | 2015-09-04 01:28 +0200 |
| Message-ID | <msal0b$udo$1@dont-email.me> |
| In reply to | #41707 |
Paul Rubin wrote: > Bernd Paysan <bernd.paysan@gmx.de> writes: >> No, the main problem is telling the other thread that there is some data >> for >> it. That's using an OS IPC call, and that takes several thousand cycles. >> You can pass around a lot of data between the cores; that works well. > > In the uncontended case you check a futex in user space and proceed if > there's something to do, or yield to the kernel if there's nothing to > do. There's only IPC overhead if there's contention in which case you > have to make a system call. Unfortunately, the contention is the rule, and the uncontented case the exception. The problem of asynchronous tasks is that either the producer or the consumer waits, and that's the contented case. So either the producer has to tell the consumer "good morning, time to wake up, I've some new data for you", or the consumer says "good afternoon, producer, stop napping, and give me another chunk of data". In a non-trivial parallel program, you have tasks which run short, and tasks which run longer, joins where you wait for all inputs to compilete, and so on. This only works well if the context switch and wake/sleep IPC by itself is a lightweight operation. -- Bernd Paysan "If you want it done right, you have to do it yourself" net2o ID: kQusJzA;7*?t=uy@X}1GWr!+0qqp_Cn176t4(dQ* http://bernd-paysan.de/
[toc] | [prev] | [next] | [standalone]
| From | franck.bensusan@gmail.com |
|---|---|
| Date | 2015-09-03 23:04 -0700 |
| Message-ID | <0b85bede-74a2-43b1-b097-91e96f80251e@googlegroups.com> |
| In reply to | #41712 |
Le vendredi 4 septembre 2015 01:28:57 UTC+2, Bernd Paysan a écrit :
> Paul Rubin wrote:
>
> > Bernd Paysan <bernd.paysan@gmx.de> writes:
> >> No, the main problem is telling the other thread that there is some data
> >> for
> >> it. That's using an OS IPC call, and that takes several thousand cycles.
> >> You can pass around a lot of data between the cores; that works well.
> >
> > In the uncontended case you check a futex in user space and proceed if
> > there's something to do, or yield to the kernel if there's nothing to
> > do. There's only IPC overhead if there's contention in which case you
> > have to make a system call.
>
> Unfortunately, the contention is the rule, and the uncontented case the
> exception. The problem of asynchronous tasks is that either the producer or
> the consumer waits, and that's the contented case. So either the producer
> has to tell the consumer "good morning, time to wake up, I've some new data
> for you", or the consumer says "good afternoon, producer, stop napping, and
> give me another chunk of data".
>
> In a non-trivial parallel program, you have tasks which run short, and tasks
> which run longer, joins where you wait for all inputs to compilete, and so
> on. This only works well if the context switch and wake/sleep IPC by itself
> is a lightweight operation.
>
> --
> Bernd Paysan
> "If you want it done right, you have to do it yourself"
> net2o ID: kQusJzA;7*?t=uy@X}1GWr!+0qqp_Cn176t4(dQ*
> http://bernd-paysan.de/
Hello,
Oforth parallelism model is lightweight tasks that can communicate
using channels.
Tasks are created using & on a word (or a quotation or a closure).
They are not threads, they are just small objects that can run
concurrently. They can be long-running or short-running objects.
For instance, writing this on the interpreter :
#[ "Hello world" . 5000 System sleep "Done" . ] &
will run this quotation into a separate task.
.w lists all tasks that are currently running or waiting in the system.
A task can wait on a channel using #receive word. If the channel is empty, the
task stops until something is into the channel. When stopped, a task
does not use CPU (no spin-loop, no system call) and does not block any core or thread.
Channels are multiple-writers / multiple-readers queues.
They are the only way to synchronize tasks. There is no other mecanism for
synchronisation (no CAS, no mutex, no semaphore, ... nothing). Tasks are never
waiting for other tasks, but for a resource. And if the resource is empty, the
task just stops and will resume when the resource is available.
For instance, a basic ping pong between 2 tasks :
: pongTask(n, ping, pong) // ( aChannel aChannel aInteger -- )
{
| i |
n loop: i [ ping receive pong send drop ]
}
: pingpong(n) // ( aInteger -- )
{
| ping pong i |
Channel new ->ping
Channel new ->pong
#[ pong ping n pongTask ] &
n loop: i [ i ping send drop pong receive . ]
}
This will write all integers between 1 and n.
- Two channels are created.
- A closure that runs pongTask is created and launched using &
==> pongTask is now running in parallel, waiting for something into ping
channel.
- Each integer is sent to ping channel.
- pongTask receives it and resend it to pong channel.
- pingpong function waits for the return on pong channel and write the result.
Franck
[toc] | [prev] | [next] | [standalone]
| From | anton@mips.complang.tuwien.ac.at (Anton Ertl) |
|---|---|
| Date | 2015-09-04 08:24 +0000 |
| Message-ID | <2015Sep4.102450@mips.complang.tuwien.ac.at> |
| In reply to | #41712 |
Bernd Paysan <bernd.paysan@gmx.de> writes:
>Paul Rubin wrote:
>> In the uncontended case you check a futex in user space and proceed if
>> there's something to do, or yield to the kernel if there's nothing to
>> do. There's only IPC overhead if there's contention in which case you
>> have to make a system call.
>
>Unfortunately, the contention is the rule, and the uncontented case the
>exception. The problem of asynchronous tasks is that either the producer or
>the consumer waits, and that's the contented case.
No, the contended case is when both want to change the status at the
same time.
> So either the producer
>has to tell the consumer "good morning, time to wake up, I've some new data
>for you", or the consumer says "good afternoon, producer, stop napping, and
>give me another chunk of data".
Sounds to me like you have a GA144-like model with little or no
buffering. Then of course you will have little parallelism; after
all, the GA144 was designed to let many of the cores sleep most of the
time.
But that's the wrong model for an AMD64 or ARM CPU. If you really
have lots of parallelism, then there is no need for an OS-level
synchronization after every piece of work; instead, each thread calls
its scheduler, which looks in the list of tasks to be done, and then
performs the next one, possibly producing another task (in the case of
a producer). Most of that can be done with user-level
synchronization, and if even that is too expensive, reduce it with
batching. You do need buffering for that, however.
>In a non-trivial parallel program, you have tasks which run short, and tasks
>which run longer, joins where you wait for all inputs to compilete, and so
>on. This only works well if the context switch and wake/sleep IPC by itself
>is a lightweight operation.
So don't use the OS in the normal case.
- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2015: http://www.rigwit.co.uk/EuroForth2015/
[toc] | [prev] | [next] | [standalone]
| From | Bernd Paysan <bernd.paysan@gmx.de> |
|---|---|
| Date | 2015-09-04 15:09 +0200 |
| Message-ID | <msc53k$en6$1@dont-email.me> |
| In reply to | #41719 |
Anton Ertl wrote: > Bernd Paysan <bernd.paysan@gmx.de> writes: >>Paul Rubin wrote: >>> In the uncontended case you check a futex in user space and proceed if >>> there's something to do, or yield to the kernel if there's nothing to >>> do. There's only IPC overhead if there's contention in which case you >>> have to make a system call. >> >>Unfortunately, the contention is the rule, and the uncontented case the >>exception. The problem of asynchronous tasks is that either the producer >>or the consumer waits, and that's the contented case. > > No, the contended case is when both want to change the status at the > same time. No, that's not a resource lock, that's a wakeup signal. Therefore, the contented (expensive) case is when one or the other sleeps, and the uncontended is when both are awake. >> So either the producer >>has to tell the consumer "good morning, time to wake up, I've some new >>data for you", or the consumer says "good afternoon, producer, stop >>napping, and give me another chunk of data". > > Sounds to me like you have a GA144-like model with little or no > buffering. Then of course you will have little parallelism; after > all, the GA144 was designed to let many of the cores sleep most of the > time. When the consumers are faster than the produces, your buffers won't fill up. You can introduce arbitrary delays to keep your buffers filled, but this also reduces performance, as other tasks will be waiting much longer for the results. And yes, I've a model in mind, where more compute cores are sleeping than working; with a x64-style implementation, you would use SMT for that, not multiple cores. Some part of the large register file is for sleeping tasks. > But that's the wrong model for an AMD64 or ARM CPU. If you really > have lots of parallelism, then there is no need for an OS-level > synchronization after every piece of work; instead, each thread calls > its scheduler, which looks in the list of tasks to be done, and then > performs the next one, possibly producing another task (in the case of > a producer). Most of that can be done with user-level > synchronization, and if even that is too expensive, reduce it with > batching. You do need buffering for that, however. And buffering reduces performance, as it requires way more actual parallelism. >>In a non-trivial parallel program, you have tasks which run short, and >>tasks which run longer, joins where you wait for all inputs to compilete, >>and so >>on. This only works well if the context switch and wake/sleep IPC by >>itself is a lightweight operation. > > So don't use the OS in the normal case. Anton, that's the entire point of suggesting that the wake/sleep IPC should be done in hardware. -- Bernd Paysan "If you want it done right, you have to do it yourself" net2o ID: kQusJzA;7*?t=uy@X}1GWr!+0qqp_Cn176t4(dQ* http://bernd-paysan.de/
[toc] | [prev] | [next] | [standalone]
| From | anton@mips.complang.tuwien.ac.at (Anton Ertl) |
|---|---|
| Date | 2015-09-05 15:10 +0000 |
| Message-ID | <2015Sep5.171017@mips.complang.tuwien.ac.at> |
| In reply to | #41721 |
Bernd Paysan <bernd.paysan@gmx.de> writes:
>Anton Ertl wrote:
>
>> Bernd Paysan <bernd.paysan@gmx.de> writes:
>>>Paul Rubin wrote:
>>>> In the uncontended case you check a futex in user space and proceed if
>>>> there's something to do, or yield to the kernel if there's nothing to
>>>> do. There's only IPC overhead if there's contention in which case you
>>>> have to make a system call.
>>>
>>>Unfortunately, the contention is the rule, and the uncontented case the
>>>exception. The problem of asynchronous tasks is that either the producer
>>>or the consumer waits, and that's the contented case.
>>
>> No, the contended case is when both want to change the status at the
>> same time.
>
>No, that's not a resource lock, that's a wakeup signal.
Only one thread is active, so there can be no contention. You are
thinking about something that is not contention.
>>> So either the producer
>>>has to tell the consumer "good morning, time to wake up, I've some new
>>>data for you", or the consumer says "good afternoon, producer, stop
>>>napping, and give me another chunk of data".
>>
>> Sounds to me like you have a GA144-like model with little or no
>> buffering. Then of course you will have little parallelism; after
>> all, the GA144 was designed to let many of the cores sleep most of the
>> time.
>
>When the consumers are faster than the produces, your buffers won't fill up.
>You can introduce arbitrary delays to keep your buffers filled, but this
>also reduces performance, as other tasks will be waiting much longer for the
>results.
If the consumers are faster than the producers, run the producers on
more cores than the consumers. If you have only one producer, and
that is sequential, and the consumers combined are still faster than
the producer, you have a parallelism of <2. You can still reduce the
wakeup overhead by only sending wakeup signals when the producer has
produced enough (and stored it in a buffer) that the wakeup overhead
is small compared to the processing time. Yes, this increases
latency, so it's a balance of efficiency vs. latency; you can bound
the increase in latency by waking the consumer some fixed time after
the producer has started producing.
>And yes, I've a model in mind, where more compute cores are sleeping than
>working; with a x64-style implementation, you would use SMT for that, not
>multiple cores.
If there are not enough active threads for all the cores, the only
reason to use SMT is to conserve energy or because communication is
cheaper (the shared cache is L1 instead of L3). But if you are
interested in performance, I expect that, running two threads on two
otherwise idle cores usually gives better performance than running
them in the same core, even if they communicate. Sure, there is the
PAUSE instruction for slowing a waiting thread down, but even with
that, i expect that situation where SMT performs better than two cores
are not very common.
>And buffering reduces performance, as it requires way more actual
>parallelism.
Buffering also enables parallelism. E.g., with a conventional screen
and with vertical synchronization to avoid tearing, double buffering
means that rendering has to wait for the vsync, while with tripple
buffering there can be rendering all the time.
Anyway, yes, you were talking of having lots of little tasks, which
sounds like having lots of parallelism to me. Then you switch to a
hardly-parallel problem of one sequential producer and consumers that
need little CPU. Of course these different kinds of problems need
different solutions.
>> So don't use the OS in the normal case.
>
>Anton, that's the entire point of suggesting that the wake/sleep IPC should
>be done in hardware.
Well, Intel tried that kind of thing in the iAPX 432 and in the 80286
protected mode and the hardware operations (task gates) were slow. A
context switch is slow whether it is done in hardware or in software.
You may be dreaming of hardware that has, say, dozens sets of
process/thread states per core, most of which are sleeping most of the
time, and that can put themselves to sleep cheaply, and be woken up
cheaply, but you have to make a really good case for that to get it
included in hardware. Is your model of lots of small tasks with
little parallelism overall really that relevant?
- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2015: http://www.rigwit.co.uk/EuroForth2015/
[toc] | [prev] | [next] | [standalone]
| From | Bernd Paysan <bernd.paysan@gmx.de> |
|---|---|
| Date | 2015-09-05 22:04 +0200 |
| Message-ID | <msfhog$ej7$1@dont-email.me> |
| In reply to | #41764 |
Anton Ertl wrote:
>>No, that's not a resource lock, that's a wakeup signal.
>
> Only one thread is active, so there can be no contention. You are
> thinking about something that is not contention.
"Contention" here is when someone has to wait. The producer needs space in
the queue - if the queue is full, it's a contention for the producer
("congestion", write access is blocked). The consumer needs data in the
queue, if the queue is empty, it's a contention for the consumer, read
access is blocked.
It's not the same sort of contention you have with equal processes, it's
"pipeline contention".
> If the consumers are faster than the producers, run the producers on
> more cores than the consumers. If you have only one producer, and
> that is sequential, and the consumers combined are still faster than
> the producer, you have a parallelism of <2.
I don't quite see the problem of having a parallelism of say 1.8, and be
able to use it. When the wake/sleep operation costs me as much as
processing one block, I can't use it. The overall number of available cores
today is a small integer, so I can't have 10 producers and 9 consumers
running in parallel.
> You can still reduce the
> wakeup overhead by only sending wakeup signals when the producer has
> produced enough (and stored it in a buffer) that the wakeup overhead
> is small compared to the processing time. Yes, this increases
> latency, so it's a balance of efficiency vs. latency; you can bound
> the increase in latency by waking the consumer some fixed time after
> the producer has started producing.
net2o's timing-based flow control breaks with that approach. You have to
process each packet as soon as possible, and finally, when a packet arrived
unencrypted in its destination, you take the time of arrival.
There are cases where you can do that, though.
>>And yes, I've a model in mind, where more compute cores are sleeping than
>>working; with a x64-style implementation, you would use SMT for that, not
>>multiple cores.
>
> If there are not enough active threads for all the cores, the only
> reason to use SMT is to conserve energy or because communication is
> cheaper (the shared cache is L1 instead of L3). But if you are
> interested in performance, I expect that, running two threads on two
> otherwise idle cores usually gives better performance than running
> them in the same core, even if they communicate. Sure, there is the
> PAUSE instruction for slowing a waiting thread down, but even with
> that, i expect that situation where SMT performs better than two cores
> are not very common.
My situation is different: I've running and sleeping processes, and I want
to wake/sleep them quickly. Using different cores and having them all spin-
loop is consuming energy and a waste of resources, because the threads are
waiting. So I put them all as "semi-active" on a SMT core, where the
sleeping threads only consume registers in the register file, but can start
running within a nanosecond.
SMT with more than one active thread per core is also faster with your usual
pipeline bubbles like mispredicted branches and waits for cache accesses (L2
and beyond), where one thread has all resources for itself.
For real-time tasks, just being able to run at all, even at a slower pace,
is better than having to wait for the next time slice.
>>And buffering reduces performance, as it requires way more actual
>>parallelism.
>
> Buffering also enables parallelism. E.g., with a conventional screen
> and with vertical synchronization to avoid tearing, double buffering
> means that rendering has to wait for the vsync, while with tripple
> buffering there can be rendering all the time.
But the right solution is to go away from the fixed refresh, and display the
buffers when they are ready. So the rendering only has to wait when the
render time is so short that it exceeds the bandwidth (e.g. 140fps), and not
when it's just faster than the minimum acceptable rate (e.g. 30fps).
> Anyway, yes, you were talking of having lots of little tasks, which
> sounds like having lots of parallelism to me. Then you switch to a
> hardly-parallel problem of one sequential producer and consumers that
> need little CPU. Of course these different kinds of problems need
> different solutions.
The little tasks are usually connected in such a way. There may be overall
way more than just two tasks, but the typical relation between these tasks
is often producer/consumer, and they aren't well balanced.
>>> So don't use the OS in the normal case.
>>
>>Anton, that's the entire point of suggesting that the wake/sleep IPC
>>should be done in hardware.
>
> Well, Intel tried that kind of thing in the iAPX 432 and in the 80286
> protected mode and the hardware operations (task gates) were slow. A
> context switch is slow whether it is done in hardware or in software.
That's why I say "use the SMT capabilities". That's how to do that cheap.
BTW: Just moving the task switch from software into microcode doesn't make
it "hardware". Neither iAPX 432 or 286 PM had any hardware capabilities for
task switching, they both just had complicated microcode. AFAIK, a Forth
PAUSE with pusha/mov sp,[up+next]/popa was about two orders of magnitude
faster than a task gate call.
> You may be dreaming of hardware that has, say, dozens sets of
> process/thread states per core, most of which are sleeping most of the
> time, and that can put themselves to sleep cheaply, and be woken up
> cheaply, but you have to make a really good case for that to get it
> included in hardware. Is your model of lots of small tasks with
> little parallelism overall really that relevant?
That's your model, not mine. Let's repeat it:
* The tasks are small, so that expensive wake/sleep operations don't work,
and moving the tasks from one core to the other is also not a good idea.
Hot tasks which are already in the L1 code cache and data in L1 data cache
can easily be several times faster than "cold tasks". There's not enough
work for one specific task to run all the time, because the tasks are
diverse.
* The tasks are related to each other in a consumer-producer relation,
sometimes with DAG-like structures, i.e. a task may combine the output of
two producers, or feed two consumers.
* There are enough of those tasks to keep all cores in current CPUs active
(and maybe many more), but when used with the current high-overhead IPC,
there's no benefit.
Take Marcel's ngspice as example: You really can compute the "next
voltage/current" output for all active nodes at the same time (and that's
often only a part of the entire circuit, not all devices have fast input
voltage or current swings). The parallelism is there. Nodes depending on
fast-changing voltages need to recalculate their output more often when
triggered, but those nodes which stay mostly the same don't need to
calculate often (then the linear solver is sufficient). The number of
different device models can easily be 20 or more, with device-parameter
depending pathes (CMOS, NMOS, different gate thickness, Zener, Schottky and
"normal" diodes, NPN, PNP bipolars, several types of capacitors, including
parasitics, and resistors, including parasitics).
AMD's GCN GPUs have to some extend what I'm asking for: you can run several
asynchronous tasks, and feed data from one to the next, context switching is
cheap.
http://www.anandtech.com/show/9124/amd-dives-deep-on-asynchronous-shading
It does considerably improve performance. This is a rather new approach for
GPU-style parallelism; it's not just 1000s of cores, each doing the same
thing on different data. The number of different contexts active at the
same time might be a bit on the low side now, but that stuff is just new.
--
Bernd Paysan
"If you want it done right, you have to do it yourself"
net2o ID: kQusJzA;7*?t=uy@X}1GWr!+0qqp_Cn176t4(dQ*
http://bernd-paysan.de/
[toc] | [prev] | [next] | [standalone]
| From | anton@mips.complang.tuwien.ac.at (Anton Ertl) |
|---|---|
| Date | 2015-09-06 14:51 +0000 |
| Message-ID | <2015Sep6.165104@mips.complang.tuwien.ac.at> |
| In reply to | #41779 |
Bernd Paysan <bernd.paysan@gmx.de> writes:
>Anton Ertl wrote:
>>>No, that's not a resource lock, that's a wakeup signal.
>>
>> Only one thread is active, so there can be no contention. You are
>> thinking about something that is not contention.
>
>"Contention" here is when someone has to wait.
It does not help if you use established terms with a different
meaning. When someone talks about locks (and mutexes (including
futexes) are kinds of locks), contention has a specific meaning, and
when only one thread is accessing the lock, there is no contention.
>It's not the same sort of contention you have with equal processes, it's
>"pipeline contention".
Googling for "pipeline contention" did not give me appropriate hits,
so it seems that is not an established term.
>> If the consumers are faster than the producers, run the producers on
>> more cores than the consumers. If you have only one producer, and
>> that is sequential, and the consumers combined are still faster than
>> the producer, you have a parallelism of <2.
>
>I don't quite see the problem of having a parallelism of say 1.8, and be
>able to use it. When the wake/sleep operation costs me as much as
>processing one block, I can't use it.
Make the blocks longer, and you can. Or, if you don't want to do
that, and you are certain about the 1.8 paralellism, use busy waiting
with PAUSE. It would be cool if you could slow the clock for the core
with the faster thread, but I think that's not possible (having only
one thread on the core and that using PAUSE might be a sign to the
hardware to slow the clock down, but I doubt that this is done yet).
>The overall number of available cores
>today is a small integer, so I can't have 10 producers and 9 consumers
>running in parallel.
On some Xeons you can, but anyway, you get different problems when you
want to exploit a parallelism of 1.8 on a four-core CPU, or a
parallelism of 19.
>> You can still reduce the
>> wakeup overhead by only sending wakeup signals when the producer has
>> produced enough (and stored it in a buffer) that the wakeup overhead
>> is small compared to the processing time. Yes, this increases
>> latency, so it's a balance of efficiency vs. latency; you can bound
>> the increase in latency by waking the consumer some fixed time after
>> the producer has started producing.
>
>net2o's timing-based flow control breaks with that approach. You have to
>process each packet as soon as possible, and finally, when a packet arrived
>unencrypted in its destination, you take the time of arrival.
So when your machine is busy and may context-switch your net2o threads
out in favor of something else, your control-flow approach breaks.
Hmm. Maybe it needs some more work to be less brittle.
>>>And yes, I've a model in mind, where more compute cores are sleeping than
>>>working; with a x64-style implementation, you would use SMT for that, not
>>>multiple cores.
>>
>> If there are not enough active threads for all the cores, the only
>> reason to use SMT is to conserve energy or because communication is
>> cheaper (the shared cache is L1 instead of L3). But if you are
>> interested in performance, I expect that, running two threads on two
>> otherwise idle cores usually gives better performance than running
>> them in the same core, even if they communicate. Sure, there is the
>> PAUSE instruction for slowing a waiting thread down, but even with
>> that, i expect that situation where SMT performs better than two cores
>> are not very common.
>
>My situation is different: I've running and sleeping processes, and I want
>to wake/sleep them quickly. Using different cores and having them all spin-
>loop is consuming energy and a waste of resources, because the threads are
>waiting.
Yes, but it's what is available.
>So I put them all as "semi-active" on a SMT core, where the
>sleeping threads only consume registers in the register file, but can start
>running within a nanosecond.
Sure, but if you have such such sleep/wakeup instructions, there is no
need to restrict this to SMT. An otherwise idle core can also sleep
with the thread state in the register file etc, and then wake up in a
nanosecond.
>>>And buffering reduces performance, as it requires way more actual
>>>parallelism.
>>
>> Buffering also enables parallelism. E.g., with a conventional screen
>> and with vertical synchronization to avoid tearing, double buffering
>> means that rendering has to wait for the vsync, while with tripple
>> buffering there can be rendering all the time.
>
>But the right solution is to go away from the fixed refresh, and display the
>buffers when they are ready.
If you have a screen that supports that, fine. Most screens don't,
yet. Anyway, this is an example of how having more buffers helps
parallelism. I can also give others: E.g., CPUs have write buffers,
OSs have write buffers, hard disk drives have write buffers, ... They
also have read buffers, and data from disk is stored in buffers in RAM
instead of being caught from the wire by the CPU.
>BTW: Just moving the task switch from software into microcode doesn't make
>it "hardware". Neither iAPX 432 or 286 PM had any hardware capabilities for
>task switching, they both just had complicated microcode. AFAIK, a Forth
>PAUSE with pusha/mov sp,[up+next]/popa was about two orders of magnitude
>faster than a task gate call.
It also does much less. But it seems that, what the task gate does
more is not actually worth the price (although there are probably
still fans of advanced security concepts that disagree).
>> You may be dreaming of hardware that has, say, dozens sets of
>> process/thread states per core, most of which are sleeping most of the
>> time, and that can put themselves to sleep cheaply, and be woken up
>> cheaply, but you have to make a really good case for that to get it
>> included in hardware. Is your model of lots of small tasks with
>> little parallelism overall really that relevant?
>
>That's your model, not mine. Let's repeat it:
>
>* The tasks are small, so that expensive wake/sleep operations don't work,
>and moving the tasks from one core to the other is also not a good idea.
>Hot tasks which are already in the L1 code cache and data in L1 data cache
>can easily be several times faster than "cold tasks". There's not enough
>work for one specific task to run all the time, because the tasks are
>diverse.
>
>* The tasks are related to each other in a consumer-producer relation,
>sometimes with DAG-like structures, i.e. a task may combine the output of
>two producers, or feed two consumers.
>
>* There are enough of those tasks to keep all cores in current CPUs active
>(and maybe many more), but when used with the current high-overhead IPC,
>there's no benefit.
But for that problem, you don't need much OS-level stuff. If you can
keep all the cores (and hardware threads) busy, the solution is to
create one OS-level thread per hardware thread and have a user-level
schedulers within each thread that schedules the tasks and coordinates
with the other schedulers (using user-level means) to balance the load
etc.
I don't see a need for special hardware for that problem. It's only
when you cannot keep everything busy that OS-level stuff (or busy
waiting) comes into play.
- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2015: http://www.rigwit.co.uk/EuroForth2015/
[toc] | [prev] | [next] | [standalone]
Page 2 of 6 — ← Prev page 1 [2] 3 4 5 6 Next page →
Back to top | Article view | comp.lang.forth
csiph-web