Re: Speaking of Multiprocessing...

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

Show all headers | View raw

On 3/24/2017 1:37 AM, Robert Wessel wrote:
> On Fri, 24 Mar 2017 01:05:02 -0400, rickman <gnuarm@gmail.com> wrote:
>
>> 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?
>
>
> It's two threads, on one processor or two.  Many discussion of
> Dekker's don't really consider software threads (as we know them
> today), as it predates common support for that in OSs.  Call it two
> competitors for the lock.
>
>
>> 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...
>
>
> This is one of the oldest, if not the very oldest, multi-threading
> technique for processors, dating back to the PPUs on the CDC-6600
> (circa 1965).  The PPUs were 10 time-sliced "threads" on the I/O
> processor.
>
>
>> 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.
>
>
> As soon as you have memory or FP, not all instructions are single
> cycle any more.  But as described below, LL/SC is the standard way of
> avoiding having a RMW instruction.

I don't know what you mean when you use abbreviations that aren't clear. 
  Is FP floating point?  There is nothing inherent in floating point 
that makes it multiple cycles in a custom processor design.

There certainly is no reason for memory to be multiple cycle.  I think 
you are picturing various implementations where memory is slow compared 
to the CPU.  That's not a given.


> It is important to understand how much synchronization you need
> between the threads.  If the individual tasks are very independent,
> and need little or no synchronization with tasks running on other
> threads, then you need only weak support for such in the hardware (and
> your code would probably run well on a GPU).

How dependent the tasks are will vary with the problem being solved. 
I'm just looking at how best to utilize the facility available in FPGAs. 
  The guy who was talking about the time slicing was looking into that 
when he was told about the need for a mutex.


>> 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...?
>
>
> Load-linked/store-conditional.  That's what most RISCs use to
> implement atomic operations.  Basically the load-linked establishes
> that you want to atomically update a location (as well as loading the
> existing value there), the store-conditional attempts to update that
> value (it's a store), but if something else had hit that location*,
> the SC will fail, and you have to retry the update.  In that sense
> it's similar to a compare-and-swap, rather than a true atomic update
> like test-and-set.

I need to think how that could be implemented.  One way would be to have 
an extra bit per memory location.  Another would be to make the memory 
interface "smart" where it tracks the location you read as part of this 
function and handles the logic of monitoring other writes to it.  That 
could be pretty simple really as long as it is one location per processor.

Would an instruction that reads a location while also writing to it do 
the job?  If you are trying to lock a resource by setting a location to 
a 1 say, you set the 1 but also read it.  If it comes back already a 1 
you know it was already locked.  There doesn't need to be the same 
difficulty of setting it to a 0 if you hold the lock.

Doing a read and a write at the same time in most FPGAs is not so hard. 
The block memory in an FPGA has simultaneous read/write functionality. 
In fact it looks like a large addressable register set requiring a clock 
edge to do the read.  By using the opposite edge of the clock to clock 
the memory (as the rest of the CPU) the write and read can happen at the 
same time with the read result coming out a half clock before it has to 
be written to its destination.  win-win.


> The desire to avoid multi-cycle instructions is the prime driver for
> LL/SC, as it lets the operation be split into individual simple
> operations.  So let's say you wanted to atomically add R2 to a memory
> location, you'd code something like:
>
>  retry:
>     ll r1,mem
>     add r1,r2
>     sc r1,mem
>     branch-if-fail retry
>
> The success flag is typically returned in a register.  Alpha, for
> example returned it in the register operand of the SC (STL_C or STQ_C)
> so a simple BEQ (to test if the returned value was zero) was all that
> was needed to trigger the retry.
>
>
> *FSVO "location" - usually the granularity is on something like a
> cache line or larger.  There are often other restrictions as well - no
> interrupts or exceptions  between the LL and SC, a maximum number of
> instructions between the pair, no other LL, loads or stores in
> general, branches, etc.  The exact details varied considerably.
> Commonly this is described as having a flag set by the LL, and various
> conditions can cause the flag to be cleared before the SC executes -
> and if that flag is clear the SC fails.
>


-- 

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