Synchronization Instructions

Mark Smotherman
Last updated: May 2006

Summary: ... tbd ... (is there enough history here to be interesting?)

UNDER CONSTRUCTION

... purpose
... aka atomic instructions
... list in chronological order of introduction, with sublist of machines using the instruction
... distinguish from Conway join (AFIPS FJCC 1963), semaphore wait, etc., in which control can be suspended [or add cites to impls. like Bull Gamma 60, Honeywell 800, Honeywell Series 60 / Level 64, etc.] ...

• Test and Set
  • IBM S/360 (1964) - ts
    • ts displacement(base_reg)
    • leftmost bit of addressed byte in memory is used to set the condition code; the byte in memory is set to all ones as it is fetched for testing.
    • Fred Brooks attributes test and set to J. Dirac, project memorandum, 1963
  • Univac 1108
  • DEC VAX - bbssi
  • first use of cache-friendly test and test and set appears to be L. Rudolph and Z. Segall, "Dynamic Decentralized Cache Schemes for MIMD Parallel Processors," Proc. ISCA, June 1984, pp. 340-347.

• Exchange (Swap)
  • Burroughs (?)
  • DEC PDP-10 - exch
  • Intel 8086 - lock xchg

• Compare and Swap
  • IBM S/370 (1973) - cs
    • cs r1,r3,disp2(r2)
    • the first and third operands are registers, and the second-operand location is a 32-bit word in memory.
    • the first and second operands are compared; if they are equal, then the third operand is stored into the second-operand location and the condition code is set to 0. (if they are unequal, the second operand is stored into the first-operand location and the condition code is set to 1.)
    • story about using initials?
    • compare double and swap - cds
    • Padegs (IBM JRD, Sept. 1981) says cs and cds introduced in Feb. 1973
  • Motorola 68K cas
  • Intel x86 compare and exchange

• Load Linked and Store Conditional
  • Livermore S-1 ref
  • MIPS - ll and sc
  • Alpha - ldl_l and stl_c (and ldq_l and stq_c)
  • PowerPC lwarx and stwcx
  • ARM - ldrex and strex

• Fetch-and-Add
  • NYU Ultracomputer
  • A. Gottlieb, R. Grishman, C. Kruskal, K. McAuliffe, L. Rudolph, and M. Snir, "The NYU Ultracomputer - Designing a MIMD Shared-Memory Parallel Machine", IEEE Trans. on Computers, 32(2), February 1983, pp. 175-189.

... should I list memory/exception barrier and fence instructions also? ...

[History page] [Mark's homepage] [CPSC homepage] [Clemson Univ. homepage]