home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / parallel / 2768 < prev    next >
Encoding:
Text File  |  1992-12-21  |  3.3 KB  |  63 lines
  1. Newsgroups: comp.parallel
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!sdd.hp.com!ncr-sd!ncrcae!hubcap!fpst
  3. From: grout@sp90.csrd.uiuc.edu (John R. Grout)
  4. Subject: Re: Wanted: efficient software lock
  5. Message-ID: <1992Dec17.225025.3179@csrd.uiuc.edu>
  6. Keywords: mutual exclusion, memory models, locks
  7. Sender: news@csrd.uiuc.edu
  8. Reply-To: j-grout@uiuc.edu
  9. Organization: UIUC Center for Supercomputing Research and Development
  10. References: <1992Dec15.134502.7384@hubcap.clemson.edu> <liv2dcINN6c5@exodus.Eng.Sun.COM>
  11. Date: Thu, 17 Dec 92 22:50:25 GMT
  12. Approved: parallel@hubcap.clemson.edu
  13. Lines: 48
  14.  
  15. agn@bovic.Eng.Sun.COM (Andreas G. Nowatzyk) writes:
  16. >It might be of interest to note that the above algorithm (and many similar
  17. >ones) assume that memory operations are sequentially consistent (SC). There
  18. >is a significant performance advantage for systems that provide SC memory
  19. >only when needed. These weaker memory models generally require ordering or
  20. >synchronization instructions to appear SC.
  21.  
  22. >For example, if Peterson's algorithm were used on a Sparc based
  23. >multiprocessor, without using an atomic instruction (swap, test-and-set or
  24. >compare-and-swap), you would still need ordering instructions. In the current
  25. >version 8, this means adding a store-barrier instruction *and* a "swap" that
  26. >is used as a load-barrier (it is not possible to implement this particular
  27. >algorithm without "swap" or "ldstub" on V8 machines). Eventually, in the next
  28. >version of the Sparc architecture, a generalized ordering directive (membar)
  29. >can be used to implement Peterson's Algorithm correctly in all supported
  30. >memory models (TSO, PSO and RMO).
  31.  
  32. When one adds performance considerations (e.g., cache utilization, cache
  33. coherence and memory bus traffic) to memory consistency considerations (which
  34. determine whether software locking schemes implemented with ordinary
  35. instructions _can_ work), I believe that all software locking schemes should
  36. be comparatively inefficient even with the use of a "membar" instruction...
  37. both getting a word atomically on a system which was the last to update it and
  38. spinning on an unavailable word should be better optimized in atomic
  39. operations than in an implementation of Peterson's algorithm (at least in any
  40. chip I would want to build a shared-memory MP with).
  41.  
  42. Also, in a non-atomic memory system with instructions like "membar", atomic
  43. instructions may be weakened so that they only guarantee the consistency of
  44. synchronization variables... one might use one technique (e.g., atomic
  45. instructions, Peterson's algorithm with "membar") to control a critical region
  46. _and_ an instruction like "membar" to guarantee the memory consistency of
  47. non-synchronization variables used within it.  In an operating system
  48. environment, one frequently wants to update a shared variable (e.g., a
  49. counter) without entering a critical region... so if one had an atomic
  50. operation to attempt this without synchronizing other memory operations, it
  51. would gain.
  52.  
  53. I don't know how much consistency the existing atomic instructions will
  54. provide on a Sparc once "membar" is available... I would guess that, due to
  55. compatibility issues, what they do now would be preserved...  maybe Sparc will
  56. implement weaker versions of atomic operations?
  57.  
  58. --
  59. John R. Grout                        j-grout@uiuc.edu
  60. University of Illinois, Urbana-Champaign
  61. Center for Supercomputing Research and Development
  62.  
  63.