Path: cmcl2!yale.edu!jvnc.net!darwin.sura.net!paladin.american.edu!gatech!hubcap!fpst
   From: Ian Heavens <ian@spider.co.uk>
   Apparently-To: comp-parallel@uunet.uu.net
   Sender: USENET News System <news@spider.co.uk>
   Nntp-Posting-Host: redknee.spider.co.uk
   Organization: Spider Systems Limited, Edinburgh, UK
   Date: Tue, 18 Aug 1992 10:47:12 GMT
   Approved: parallel@hubcap.clemson.edu
   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				ian@spider.co.uk                 
   Spider Software
   Spider Park, Stanwell Street		
   Edinburgh, EH6 5NG, Scotland		+44 31 555 5166 (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:(212) 998-3345 work
				      (718) 789-4486 home
				Email:freudent@lab.ultra.nyu.edu

Newsgroups: comp.parallel
From: jf@edv6000.tuwien.ac.at (Josef Fritscher (58801-5505))
Subject: Re: PVM: thoughts on data-passing routines
Reply-To: fritscher@email.tuwien.ac.at
Organization: Technical University of Vienna
Date: Tue, 18 Aug 1992 12:02:34 GMT
Apparently-To: comp-parallel@news.uu.net

In article <1992Aug17.140351.23197@hubcap.clemson.edu>, zink@phoenix.informatik.uni-stuttgart.de (Roland Zink) writes:
|> In article <1992Aug11.121234.28784@hubcap.clemson.edu>, jek@cs.duke.edu (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: fritscher@edvz.tuwien.ac.at
Computing Center                      Bitnet: fritscher@awituw64.bitnet
Technical University of Vienna    in reality: jf@edv6000.tuwien.ac.at
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)