Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #59872

Re: How useful is parallel processing for the SIEVE?

Show all headers | View raw

albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) writes:
>This is a sure cache miss every time.
>
>I've 8 processors, and I could deal out each of the masks to one
>processor, running in the same Forth with 8 preemptive threads
>and one sieve.
>
>In view of the fact that cache misses remain the same, do I get
>- no speedup at all, just lower processor load
>- some speed up, but nowhere near a factor 8
>- a decent speedup approaching 8.

If you do it properly, with locking, you have a chance of getting a
heavy slowdown.  I very much doubt that you will see any speedup, but
try it.

>(There are only a few critical loops. Assume they are written in
>assembler or a good optimizing compiler.)

If you have cache misses all the time, you can afford quite a bit of instruction overhead around them.

>The basic operation is
>    get a byte from address N
>    AND it with a mask
>    store it back
>
>This is one instruction for the usual Intel/AMD processor fortunately.
>I think that means that two processors updating the same byte
>do not interfere. (that is rare, but anyway)

AFAIK you have to use a lock prefix, or you will get a race condition
on the update.  Even with LOCK, they will interfere as far as
performance goes.

The way you do it was already slow in Pentium times.  At the time I
wrote a sieve that used cache blocking, and I saw a speedup (on a
Pentium-133 with 256KB L2 cache, and on an Alpha 21064A).  And that's
the way to parallelize your sieve: let each processor work on a part
of the number space, and use cache blocking for the work of each
processor.  Then you see very few cache misses and writing the
critical loops in assembly language pays off.

- 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 2017: http://www.euroforth.org/ef17/

Back to comp.lang.forth | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

How useful is parallel processing for the SIEVE? albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2017-05-26 13:58 +0200
  Re: How useful is parallel processing for the SIEVE? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2017-05-26 15:06 +0000

csiph-web