NetNews Usenet Archive 1992 #18/NN_1992_18.iso/spool/comp/parallel/1931

Text File | 1992-08-17 | 6.3 KB | 150 lines

Newsgroups: comp.parallel
Path: sparky!uunet!destroyer!gatech!hubcap!fpst
From: cmcl2!vlsi3.ultra.nyu.edu![e-mail] (Eric Freudenthal)
Subject: Re: Is the overhead of spin lock acquisition always significant?
In-Reply-To: Ian Heavens's message of Tue, 18 Aug 1992 10:47:12 GMT
Message-ID: <[e-mail]>
Sender: cmcl2![e-mail] (Notes Person)
Nntp-Posting-Host: vlsi3.ultra.nyu.edu
Cc: [e-mail]@[e-mail]
Organization: /a/users/freudent/.organization
References: <[e-mail]>
Date: Wed, 19 Aug 1992 00:33:59 GMT
Approved: [e-mail]
Lines: 134

Ian,

In article <[e-mail]> Ian Heavens <[e-mail]> writes:

   Newsgroups: comp.parallel
   Path: cmcl2!yale.edu!jvnc.net!darwin.sura.net!paladin.american.edu!gatech!hubcap!fpst
   From: Ian Heavens <[e-mail]>
   Apparently-To: [e-mail]
   Sender: USENET News System <[e-mail]>
   Nntp-Posting-Host: redknee.spider.co.uk
   Organization: Spider Systems Limited, Edinburgh, UK
   Date: Tue, 18 Aug 1992 10:47:12 GMT
   Approved: [e-mail]
   Lines: 40

You wrote:

    I'd like to question one of the sacred cows of spin-lock based shared
    memory multiprocessing: that the number of spin locks acquired should be
    minimised, because the overhead in lock acquisition is significant.

I agree.  That rule is too simple.  Clearly, you want to avoid
unecessary work.  Determining the granularity of locking that is
appropriate for a particular problem can be difficult.

    I agree that contention is always significant, and that there are good
    other reasons for not having lots of locks (clarity and deadlock
    avoidance).  Also, in some applications, the overhead of lock
    acquisition may be significant, where the critical sections are
    very short and are executed very frequently.

Actually, I have heard a related argument for why you would want lots
of locks rather than a few.

    In our application, a TCP/IP protocol stack, the difference between
    acquiring 5 and 10 locks on a typical input or output path seems to me
    to be insignificant compared to the protocol processing, assuming no
    contention for those locks.

     This issue becomes important because multiple-reader/single-writer
    locks are much more convenient to use, and reduce contention, at
    a cost of increasing the overhead (three times that of a mutex lock?).

What atomic operations does the machine that you are using support?
Reader/Writer coordination becomes much easier if you have either an
atomic add (fetch and add) or increment/decrement operation:

With fetch & add, only one shared access is required to acquire or
release either lock if there is no contention.  (I can send you this
code).

With fetch&increment and fetch&decrement (or even, atomic increment
and decrement that indicate if the value - either before the operation
or afterwards - was zero), only two shared accesses are required to
acquire or release either lock if there is no contention.  (This code
appeared in last year's ASPLOS ("Process Coordination with Fetch and
Increment" by me and Allan Gottlieb; I can send it to you).

   Are their cache consistency or other reasons to inflate the overhead
   of testing and setting a memory location?  What have I missed?

   Can someone suggest a rough equivalent for a spin lock acquisition in
   terms of (some arbitrary mix of) instructions execution, where both
   instruction and data fetch are cache hits?

Such an algorthm (one that only references data in a local cache in
all cases) can not be constructed because (I assume) more than one
processor may access a particular lock.  If the lock's state variable
is changed by two processors, then at least one of them needs to do a
remote access.

For this reason, memory that is actively shared (such as state
variables for a contended-for lock) is much harder to cache
efficiently than memory that is mostly used by a single processor for
a long period of time.

original author:
   ---
   Ian Heavens                [e-mail]
   Spider Software
   Spider Park, Stanwell Street
   Edinburgh, EH6 5NG, Scotland        [phone] (Ext 4347)
   --


If you reply to me, PLEASE use the address in my signature, not the
account that I mailed this from.

Good luck,
Eric
--
 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
                Eric Freudenthal
                NYU Ultracompter Lab
                715 Broadway, 10th floor
                New York, NY  10003

                Phone:[phone] work
                      [phone] home
                Email:[e-mail]

Newsgroups: comp.parallel
Approved: [e-mail]
From: [e-mail] (Josef Fritscher (58801-5505))
Subject: Re: PVM: thoughts on data-passing routines
Sender: [e-mail]
Nntp-Posting-Host: edv6000.tuwien.ac.at
Reply-To: [e-mail]
Organization: Technical University of Vienna
References:  <[e-mail]> <[e-mail]>
Date: Tue, 18 Aug 1992 12:02:34 GMT
Apparently-To: [e-mail]

In article <[e-mail]>, [e-mail] (Roland Zink) writes:
|> In article <[e-mail]>, [e-mail] (James E. Kittock) writes:

|> In my Stuttgart Parallel Processing Library (SPPL) this is possible.

I always wonder why so much people invent their own stuff instead of using
the more populuar ones (like PVM) and improve them without loss of
portability... (Just my $ 0.02)

Joe
--
Josef Fritscher                     Internet: [e-mail]
Computing Center                      Bitnet: [e-mail]
Technical University of Vienna    in reality: [e-mail]
Wiedner Hauptstrasse 8-10              Voice: ++431 58 801/5505
A-1040 Vienna, Austria/Europe         Fax: ++431 58 74 211
Member of the Austrian Center for Parallel Computation (ACPC)
-------------------------------------------------------------------------
The function of local-in-Universe critical information-gathering and
local-in-Universe problem-solving is manifest in the cockpit of all
great airplanes.                                  (R. Buckminster Fuller)