Re: What happened to computer architecture (and comp.arch?)

MitchAlsup wrote:
On Sep 10, 10:04 pm, Mayan Moudgill<ma...@xxxxxxxxxxx> wrote:
Well, synchronization can be pretty easy to implement - depends on what
you are trying to accomplish with it (barriers, exclusion, queues,
etc.).

If it is so easy to implement then why are (almost) all
synchronization models at lest BigO( n**2 ) in time? per unit of
observation. That is, it takes a minimum of n**2 memory accesses for 1
processor to recognize that it is the processor that can attempt to
make forward progress amongst n contending processors/threads.

This is the crux of the matter:

It is _easy_ to provide sync when contention is (very close to) zero, it is _hard_ to do the same when lots of cores/threads tries to do it simultaneously.

The usual answer to this kind of situation is "Don't do that!".

To me, when I see an O(n*n) situation, I try to look for O(n*log(n)) or O(n):

One obvious approach would be to have a hierarchy of locks:

Just having two levels with sqrt(n) first-level barriers all protecting access to the single "real" lock would turn the problem into something that takes twice as long in the zero contention situation, but where the worst case becomes O(sqrt(n)*sqrt(n)) * 2 => O(n), right?

Each thread could use a hash of its thread ID to determine which first-level lock to use.

With log(n) levels, each lock would only have two users, making the time for each of them constant, and the total becomes O(log(n)).

However, if I ever found myself in a situation where this was a real consideration, I'd say that the solution must still be to make sure contention doesn't happen quite so often!

But think of the OS/runtime changes that are required to guarantee that
we can use spin-locks efficiently.

Don't want spin-locks--I want a means whereby everyone trying to
synchronize recognizes their place in line in BigO( ln(x) ) time and
then another means whereby they can use their place in line to access
the queue (or whatever) without (/with minimal) interfering with the
other threads doing likewise.

This is indeed the proper solution.

As I've stated previously, XADD is IMHO the best of the currently available primitives, as long as you use the return value as your index into the work table: A single access/update per thread to get forward progress for all of them, so at least we avoid looping by all those who didn't win the first exchange.


Sorry if I'm a little incoherent. Point is, in the appropriate
environment, with the appropriate (cheap) H/W assistance, we can
implement synchronization efficiently.

No, it does not and can not and its a problem of the primatives and
the memory order and cache coherent models these primitaves have to
live within.

To adequately solve the problem you have to make the BigO term smaller
than n**2.

Right.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"
.

Relevant Pages

  • Re: A new Critical Section for high contention situations
    ... my tests was done using correct code. ... You said "there is no synchroniztion", then, what does synchronization ... You said "there is no contention", ... At this point, Thread A owns the lock, but Thread B "thinks" it owns the ...
    (microsoft.public.win32.programmer.kernel)
  • Re: A new Critical Section for high contention situations
    ... synchronization means "accepting only one thread to access certain resource or functionality at a time". ... You said "there is no contention", ... You mentioned "race conditions" but, race conditions occurs on resources not on synchronization objects. ... At this point, Thread A owns the lock, but Thread B "thinks" it owns the lock. ...
    (microsoft.public.win32.programmer.kernel)
  • Re: Multi Threading Options
    ... If the avatars struct could be modified by any other thread, ... your modifications are so short that releasing the main lock and locking just ... Given that the refresh is timer=based, you could probably eliminate all synchronization ... If it is a UI thread, then while the drawing is happening, the PostMessage ...
    (microsoft.public.vc.mfc)
  • Re: threading - Monitor.Wait/Pulse
    ... thread synchronization is considered a "Bad Thing" since there is no way ... WaitOne/WaitAny/WaitAllmethods of the WaitHandle indicates whether ... don't get with WaitHandles is that it releases the Lock on the Object ... RendezvousDemo demo = new RendezvousDemo; ...
    (microsoft.public.dotnet.general)
  • Re: multithreaded tcp/ip monitoring application
    ... I used the "lock" synchronization mechanism to manage a shared arraylist object. ... So it would be better to have the network i/o code initiate the UI update. ...
    (microsoft.public.dotnet.languages.csharp)
Loading