Re: Speaking of Multiprocessing...

From	rickman <gnuarm@gmail.com>
Newsgroups	comp.arch.embedded
Subject	Re: Speaking of Multiprocessing...
Date	2017-03-24 01:05 -0400
Organization	A noiseless patient Spider
Message-ID	<ob298g$677$1@dont-email.me> (permalink)
References	<ob1ij7$jja$1@dont-email.me> <qt49dchkfh2jssv9qrei0adlbi24r4asc0@4ax.com>

Show all headers | View raw

On 3/23/2017 11:43 PM, Robert Wessel wrote:
> On Thu, 23 Mar 2017 18:38:13 -0400, rickman <gnuarm@gmail.com> wrote:
>
>> I recall a discussion about the design of an instruction set
>> architecture where someone was saying an instruction was required to
>> test and set a bit or word as an atomic operation if it was desired to
>> support multiple processors.  Is this really true?  Is this a function
>> that can't be emulated with other operations including the disabling of
>> interrupts?
>
>
> Dekker's algorithm (circa 1962) can be used to implement a mutex
> without test-and-set, or even masking interrupts, and really only
> requires sequential consistency (and if that's a issue for your
> hardware, it should have appropriate memory barriers to force that).
>
> https://en.wikipedia.org/wiki/Dekker%27s_algorithm
>
> A limitation is that Dekker's only works with two threads/processors.

Interesting.  I'm not sure it's limited to two threads per processor 
rather than just two threads.  Even if they are on separate processors 
it's the same problem and the same limit, no?

The situation I am looking at resolving is a technique where rather than 
using a pipeline of length N to allow N-fold improvements in speed 
(other than when the pipeline has to be flushed) it can be used to get 
N-fold improvements in clock speed, but treating the CPU as N 
processors.  They are time-sliced if you will.  It also relieves a lot 
of the complexity of detecting problems and contingencies in the 
pipeline streamlining it that much more.  But...

When someone was proposing this design some time back another poster was 
insistent the design required an instruction level mutex, if I am using 
the term right.  I don't recall the details of what he wrote, but I've 
always wondered how important this is.

One of the things that can further streamline a processor is to make all 
instructions single cycle, truly single cycle.  So a read-modify-write 
instruction may be hard to implement depending on the memory used.  But 
in the context of the above multi-processor design, if the RMW 
instruction takes multiple clock cycles, it would not be truly 
uninterrupted since the other N-1 processors would all get a clock (and 
an instruction) between the multiple clocks of the RWM instruction.

I need to bat this around in my head a bit more I think.

> Several related algorithms exist, and generalizations of some of those
> (for example, Peterson's) can handle more than two threads.
>
> And once you have a mutex, you can implement everything else.
>
> OTOH, proper atomic instructions are a huge boon (even if only in
> LL/SC form), so they're provided by everyone who's serious about
> multiprocessor support.

LL/SC???  Low level, s.... c...?

-- 

Rick C

Thread

Speaking of Multiprocessing... rickman <gnuarm@gmail.com> - 2017-03-23 18:38 -0400
  Re: Speaking of Multiprocessing... Tim Wescott <seemywebsite@myfooter.really> - 2017-03-23 18:19 -0500
    Re: Speaking of Multiprocessing... Don Y <blockedofcourse@foo.invalid> - 2017-03-23 16:26 -0700
      Re: Speaking of Multiprocessing... Tim Wescott <seemywebsite@myfooter.really> - 2017-03-23 18:47 -0500
        Re: Speaking of Multiprocessing... Don Y <blockedofcourse@foo.invalid> - 2017-03-23 17:49 -0700
          Re: Speaking of Multiprocessing... upsidedown@downunder.com - 2017-03-24 09:48 +0200
            Re: Speaking of Multiprocessing... Don Y <blockedofcourse@foo.invalid> - 2017-03-24 01:22 -0700
        Re: Speaking of Multiprocessing... Clifford Heath <no.spam@please.net> - 2017-03-24 21:04 +1100
          Re: Speaking of Multiprocessing... Robert Wessel <robertwessel2@yahoo.com> - 2017-03-24 22:01 -0500
            Re: Speaking of Multiprocessing... Clifford Heath <no.spam@please.net> - 2017-03-25 18:49 +1100
    Re: Speaking of Multiprocessing... Grant Edwards <invalid@invalid.invalid> - 2017-03-24 14:36 +0000
  Re: Speaking of Multiprocessing... Robert Wessel <robertwessel2@yahoo.com> - 2017-03-23 22:43 -0500
    Re: Speaking of Multiprocessing... rickman <gnuarm@gmail.com> - 2017-03-24 01:05 -0400
      Re: Speaking of Multiprocessing... Robert Wessel <robertwessel2@yahoo.com> - 2017-03-24 00:37 -0500
        Re: Speaking of Multiprocessing... rickman <gnuarm@gmail.com> - 2017-03-24 01:58 -0400
          Re: Speaking of Multiprocessing... Robert Wessel <robertwessel2@yahoo.com> - 2017-03-24 02:07 -0500
            Re: Speaking of Multiprocessing... rickman <gnuarm@gmail.com> - 2017-03-24 13:36 -0400
              Re: Speaking of Multiprocessing... David Brown <david.brown@hesbynett.no> - 2017-03-24 19:06 +0100
                Re: Speaking of Multiprocessing... rickman <gnuarm@gmail.com> - 2017-03-24 14:12 -0400
                Re: Speaking of Multiprocessing... David Brown <david.brown@hesbynett.no> - 2017-03-25 01:48 +0100
                Re: Speaking of Multiprocessing... rickman <gnuarm@gmail.com> - 2017-03-24 22:10 -0400
                Re: Speaking of Multiprocessing... David Brown <david.brown@hesbynett.no> - 2017-03-25 15:25 +0100
                Re: Speaking of Multiprocessing... rickman <gnuarm@gmail.com> - 2017-03-25 15:27 -0400
                Re: Speaking of Multiprocessing... upsidedown@downunder.com - 2017-03-25 22:43 +0200
                Re: Speaking of Multiprocessing... rickman <gnuarm@gmail.com> - 2017-03-25 17:06 -0400
                Re: Speaking of Multiprocessing... David Brown <david.brown@hesbynett.no> - 2017-03-26 17:28 +0200
                Re: Speaking of Multiprocessing... rickman <gnuarm@gmail.com> - 2017-03-26 13:27 -0400
              Re: Speaking of Multiprocessing... Dimiter_Popoff <dp@tgi-sci.com> - 2017-03-25 00:42 +0200
                Re: Speaking of Multiprocessing... rickman <gnuarm@gmail.com> - 2017-03-24 19:22 -0400
                Re: Speaking of Multiprocessing... Rob Gaddi <rgaddi@highlandtechnology.invalid> - 2017-03-24 16:33 -0700
                Re: Speaking of Multiprocessing... Robert Wessel <robertwessel2@yahoo.com> - 2017-03-24 22:47 -0500
                Re: Speaking of Multiprocessing... Dimiter_Popoff <dp@tgi-sci.com> - 2017-03-25 12:40 +0200
                Re: Speaking of Multiprocessing... Robert Wessel <robertwessel2@yahoo.com> - 2017-03-26 00:42 -0500
  Re: Speaking of Multiprocessing... David Brown <david.brown@hesbynett.no> - 2017-03-24 09:17 +0100
    Re: Speaking of Multiprocessing... Tom Gardner <spamjunk@blueyonder.co.uk> - 2017-03-24 09:28 +0000
      Re: Speaking of Multiprocessing... David Brown <david.brown@hesbynett.no> - 2017-03-24 11:19 +0100
        Re: Speaking of Multiprocessing... Tom Gardner <spamjunk@blueyonder.co.uk> - 2017-03-24 11:06 +0000
          Re: Speaking of Multiprocessing... David Brown <david.brown@hesbynett.no> - 2017-03-24 12:21 +0100
        Re: Speaking of Multiprocessing... Tom Gardner <spamjunk@blueyonder.co.uk> - 2017-03-24 16:09 +0000
          Re: Speaking of Multiprocessing... David Brown <david.brown@hesbynett.no> - 2017-03-24 17:33 +0100
            Re: Speaking of Multiprocessing... Tom Gardner <spamjunk@blueyonder.co.uk> - 2017-03-24 17:52 +0000

csiph-web