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

Groups > comp.arch.embedded > #26218

Re: Speaking of Multiprocessing...

Show all headers | View raw

On 3/24/2017 2:06 PM, David Brown wrote:
> On 24/03/17 18:36, rickman wrote:
>> On 3/24/2017 3:07 AM, Robert Wessel wrote:
>>> On Fri, 24 Mar 2017 01:58:26 -0400, rickman <gnuarm@gmail.com> wrote:
>>>
>>>> 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:
>
> <snip>
>
>>
>>>> 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.
>>>
>>>
>>> No, but such a situation is sufficiently uncommon that you'd really
>>> want to spec it up front.  Most cores these days don't even have
>>> single cycle L1 caches.
>>
>> Again, assuming an architecture and requirements.  This conversation is
>> not about designing the next generation of ARM CPU.
>
> It would be making architecture assumptions to require single-cycle
> memory - saying that memory may be multiple cycle is the general case.
>
> (You might /want/ to make architecture assumptions here - I gave some
> other suggestions of specific hardware for locking in another post.  The
> solutions discussed here are for general memory.)

We are having two different conversations here.   I am designing a CPU, 
you are talking about the theory of CPU design.


>>>>> 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.
>>>
>>>
>>> The granularity can be pretty coarse.  Commonly a cache-line or
>>> bigger.  But you don't want to add a bit per memory word.  With a
>>> cache, you'd keep track of any changes of ownership of the cache line.
>>> With direct memory, you can just track the memory area (perhaps make
>>> it blocks of 64B for simplicity) in each "thread", and then just watch
>>> all other writes from other threads/time-slices for matching
>>> addresses.
>>
>> Why don't I want to add a bit per memory location?  If that bit happens
>> to be free, I'd be silly to let it go to waste.
>>
>
> Normally, one does not have a bit free per memory location.
>
> LL/SC solutions usually have only a single tracker tracker per cpu, or
> even just a single tracker per shared memory bus.  The granularity might
> be for a machine word, or for a cache line.  The expectation is that
> these sequences will be so short that it is very rare for a conflict to
> occur, so it is fine to have just one tracker.  You set the tracker when
> reading from the memory to get the old value, then use a conditional
> store that will only do the write if nothing else has touched that same
> location since your load.  It gives you a "test and set" type operation,
> but split into RISC-friendly separate load and store operations.
>
>>
>>>> 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.
>>>
>>>
>>> No, that's not enough in typical multi-processor implementations  - if
>>> two cores/threads/whatever hit the same location, you can only return
>>> 0 to one of them, or both might think they acquires the lock.  What
>>> you've described *is* a TAS, but not an atomic one.
>>
>> You are ignoring that the instruction also writes a 1 to the location.
>> So two processors *can't* both read a zero.  Why is it not atomic?  The
>> write and read happen on the same clock cycle.  Much like Dekker's
>> algorithm it sets the flag to exclude other processors as a priority.
>> Then it can at leisure check if the flag was already set or if it
>> "captured" the flag.
>
> Normally, you cannot read and write a memory location at the same time.
>  It would only be possible with specialised hardware, or with a bus
> locking mechanism (which can be the basis of your synchronisation
> primitive).  In a normal memory bus, you have a read operation then a
> write operation.  If you don't have bus locking of some sort, then cpu 1
> could read 0, then cpu 2 could read 0, then cpu 1 would write 1, then
> cpu 2 would write 1.
>
>>
>> Again, an abbreviation I don't know.  What's a TAS?
>>
>
> "test and set".  It reads the old value in a memory location, sets the
> memory to 1, and returns the old value - all as an atomic operation.
> Atomicity is key here - and normal memories are not atomic.
>
> (If you are thinking of using an FPGA here, it is often possible to
> implement a memory block where you /do/ read the old value on the same
> clock cycle as writing the new one, making a TAS operation simple to
> implement.)
>
>>
>>> OTOH, since you have only a single core, and you appear to be
>>> proposing that your TAS *will* be atomic (since it's going to execute
>>> in a single clock, and presumably not interleave with any other TAS in
>>> another timeslice), you're good to go.
>>
>> Not sure what you are assuming here.  There is one "core", but it is
>> time shared N ways giving N functional processors.  Each one operates on
>> a different clock cycle however, so any single instruction which takes
>> one clock cycle is truly atomic and the other processors can't interfere.
>>
>
> If this is going to be efficient, it is unlikely that the core supports
> reading and writing within the same instruction - LL/SC is usually a
> better choice.

As I have said before, I am designing a CPU in an FPGA.  I have FPGA 
features available to me that are different than what is available to 
chip designers.  I do not have the same constraints as chip designers.

I was asking what is required in an instruction set to support 
multi-processors and I think the answer is that the memory swap 
instruction would do the job efficiently.

-- 

Rick C

Back to comp.arch.embedded | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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