19

The CAS2 instruction - double compare-and-swap - is an extremely powerful instruction that was coveted for quite awhile (and still is, really) for making lock-free and wait-free data structures - that is, data structures that operate correctly and quickly in the face of concurrent use without requiring locks of any kind.

But it is also extremely expensive, as it must atomically compare two different memory locations against two registers and proceed to update them (still under the atomic constraint) both if and only if both comparisons are equal.

You just can't find it today. (For a number of reasons, including that it would totally nuke performance on a multicore due to the synchronization required.) But it was implemented in the 68030 and 68040!

It's in the "Motorola MC68030 Enhanced 32-Bit Microprocessor User's Manual - 3e (1992)" in section "3.5.1 Using the CAS and CAS2 Instructions", for example.

So my question is: How, circa the late 1980s (the 68030 was introduced in '87, development must have started at least a year earlier?) did Motorola's engineers (and program managers) come to decide that such an unusual and expensive operation was desirable in their chip? And that it was higher priority than anything else they could throw in there? In other words, what specific use case(s) did they have in mind, what trends were they aware of, what customer was banging on their door demanding it, ...

(Apparently the first published research AFAIK to use CAS2 (aka DCAS) was in 1991 (Massalin, Pu. A lock-free multiprocessor OS kernel, TR, Columbia University, June 1991); publications on lock free data structures using CAS or LL/SC started around 1991 and interest in DCAS came later, I believe. There was quite a lot of academic research interest in DCAS in the early 90's.)

15
  • 3
    Doug MacGregor, Dave Mothersole, and Bill Moyer, "The Motorola MC68020", IEEE Micro, Vol. 4, No. 4, July/August 1984, pp. 101-118 : "There are several new instructions which are used to provide system support. The compare and swap (CAS) and compare and swap 2 (CAS2) instructions allow for locked-bus manipulation of byte, word, or long-word data elements to support system queue and stack functions."
    – njuffa
    Sep 13, 2021 at 3:37
  • 3
    It seems to me that it's only caching that makes this difficult at all. Otherwise it's just a modest sequence of microcode, with the memory bus locked throughout. Expensive to execute, but not expensive to implement. Sep 13, 2021 at 3:46
  • 3
    I mean, in order to have CAS in the first place, you already need a mechanism to lock the bus, so CAS2 doesn't need anything more - you just hold the lock for longer. And was microcode space so scarce? I'm seeing estimates that the 68020 had on the order of 100 kbits of microcode ROM already, and CAS2 can't have needed all that much. Everything has an opportunity cost, sure, but it doesn't seem like too much of a leap to recognize CAS2 as something potentially valuable that software can't achieve otherwise. Sep 13, 2021 at 4:05
  • 5
    A second publication by the Motorola folks: Paul F. Groepler and James Kennedy, "The MC68020 32-Bit Microprocessor", Byte, Vol. 9, No. 12, November 1984, p. 159-174 : "The MC68020 also offers other new security and system-level instructions. The CAS and CAS2 instructions use the same read-modify-write cycle as the M68000's TAS (test and set). These operations are indivisible and noninterruptible. which ensures data security in single and multiprocessor systems. [...] The CAS and CAS2 instructions are useful for updating system counters and for insertion and deletion from linked lists."
    – njuffa
    Sep 13, 2021 at 4:30
  • 2
    Just a speculation: I used to program 68000 processor in assembler a lot and I always wondered what the LINK, CHK and CHK2 (and other instructions) where good for. Only later, when I started programming in Ada, it occurred to me that those kind of instructions may have been included in order to support compiler development (in particular for Ada e.g. CHK is perfect for constraint checks which Ada uses a lot). The same may be true for CAS and CAS2 which may be used for tasking in Ada. Sep 13, 2021 at 12:41

1 Answer 1

18

TL;DR:

  • TS, CAS and CAS2 work thru bus locking

  • CAS2 was introduced with the '020, the '030 had to have it for compatibility

  • While the 'cost' of locking for a complex operation is high, it's not higher than for simpler versions doing the same

  • CAS2 is overall more performant than a series of CAS/TS instructions

[While all 4 points are valid, the second would rectify the effort on its own]


The Long Read:

The CAS2 instruction [...] for making lock-free and wait-free data structures

Not really. CAS2, like CAS and all similar, are locking instructions. For them to perform they need to make sure that no other access to the memory locations in question happens during execution.

The are not only atomic within the CPU but in relation to memory as well. For simple write operations these is done by such an operation being already atomic on memory. For more complex the CPU has to

  • lock the memory region before/with reading and keep locked until the last related write is done.

  • Or, more general, lock all of memory access during that time

  • Or, most 'primitive' way, with the assumption of the bus system being the only way to access memory for all components in a system doing so.

68k CPUs do exactly the last approach, they take and lock the bus during such a read/modify/write operation.

  • For early (68000) versions TS as a byte wide operation was the only such and locking was done by applying Address Strobe low over the whole read and write cycle.

This worked fine as it's one and the same address that got read and written, no address change was needed, so AS could be used to lock the bus, saving the need for a dedicated RMW-Lock Signal (*1)

  • Later, with CAS2 multiple addresses had to be read/written, thus AS was needed to signal each address, requiring the introduction of RMC (Read Modify Cycle) as a locking signal.

But it is also extremely expensive, as it must atomically compare two different memory locations against two registers and proceed to update them (still under the atomic constraint) both if and only if both comparisons are equal.

Per se, not expensive at all. It's a simple sequence of memory access operation. What you may think about here is effort in cache handling (as mentioned).

For a number of reasons, including that it would totally nuke performance on a multicore due to the synchronization required.

No it doesn't - or more exact, not more as any other atomic memory operation does. Each TAS has the same issues regarding to multiple cores and memory caching.

But it was implemented in the 68030 and 68040!

A 030 not compatible with the preceding 020 would have been a bad sell, wouldn't it?

So my question is: How, circa the late 1980s (the 68030 was introduced in '87, development must have started at least a year earlier?) did Motorola's engineers (and program managers) come to decide that such an unusual and expensive operation was desirable in their chip?

It was already part of the 68020 instruction set - sold as a high performance feature for modern 32 bit OSes. So any 030 design was bound to support it as well - unless Motorola was inclined to get bad press that important instructions at the core of modern OS management had to be replaced by some slower emulation or worse, existing OS couldn't run straight away on the newer faster chip.

what specific use case(s) did they have in mind

Exactly what you think about: handling linked lists in a most performant way. After all, they are at the core of data handling past the most trivial. Having CAS2 can speed up everything from task switch to data base caching.

(Apparently the first published research AFAIK to use CAS2 (aka DCAS) was in 1991 (Massalin, Pu. A lock-free multiprocessor OS kernel, TR, Columbia University, June 1991); publications on lock free data structures using CAS or LL/SC started around 1991 and interest in DCAS came later, I believe. There was quite a lot of academic research interest in DCAS in the early 90's.)

Are you sure? CAS style instructions date back to the 1960s. IBM introduced CS (Compare and Swap) with the /370 for all machines in 1970 (*2, *3). CAS2 like operations were as well available on other computers. For example the Siemens X-Series CPUs (/370 based) had a linked list operations (EXST - Execute Stack) that could do the same as CAS2 plus a few more steps like following a linked list until the insertion point was found.

And all of that was done of course in multi processor environments. Heck, that's where the real additional value is gained - let the hardware do synchronisation, not slow software.

The mentioned linked list operations (EXST) extreme potent compared with simple TS and CS operation. Not just in theory but very obvious in practical usage. When the OS finally got modified to take advantage of these instructions, an over all performance increase of OS functions of up to 20% could be seen. Most within the lowest level and thus most often needed ones. After all, an OS is most of it's time occupied with book keeping, mostly walking (*4) and rearranging lists.

So for the performance argument often made against operations like CAS2, is is only true when looking at the single operation compared to what others cost but not looking at the gain realized. Yes, they need to synchronize memory between cache levels and CPUs, but so does each and every 'simple' CAS. But in contrast to a series of CAS that are needed to replace a CAS2, that CAS2 will use less resources.


*1 - Intel type bus uses bus lock anyway.

*2 - It was available on certain /360 before.

*3 - By having the 68020 add a CS to the 68000 TS, Motorola more or less just copied IBM move here a decade later as the /360 had a TS (Test and Set) instruction first, to be complemented by CS with the /370.

*4 - The reason why several early CPUs had an indirect addressing feature using a bit within an address word to indicate that another addressing cycle is to be used to follow that address. It removes all the overhead of looping thru a series of high level instructions when all that's needed is a sequence of memory access cycles.

14
  • 1
    The notion of "lock free", "wait free", and "non-blocking" relate to the impossibility that a thread which gets waylaid while performing a sequence of operations might stall another thread indefinitely. One could design a system to guarantee the length of time a hardware bus lock could be held, an guarantee that the process holding the lock couldn't be waylaid without releasing it. Although the hardware cost and complexity of CAS2 would go up with the evolution of split bus designs, I think hardware vendors might have kept supporting it were it not for the development of...
    – supercat
    Sep 13, 2021 at 15:02
  • 1
    Single CS based algos were present way before multi word CS instructions - after all, the issues they handle were present from the very start of multiprocessing.
    – Raffzahn
    Sep 13, 2021 at 18:16
  • 1
    CAS allowed many tasks to be performed by non-blocking algorithms that would have otherwise required the use of blocking algorithms. That was obviously useful. What I am questioning is whether non-blocking updates to doubly-linked lists were recognized as being among the operations that could be performed in non-blocking fashion using single CAS in the 1980s. Looking through the dates of references in e.g. cl.cam.ac.uk/research/srg/netos/papers/2001-caslists.pdf suggests to me that it wasn't.
    – supercat
    Sep 13, 2021 at 19:10
  • 2
    But they are lock-free; they do not appear in application lock graphs because it is impossible to observe the lock in application code even by handling an interrupt.
    – Joshua
    Sep 13, 2021 at 19:17
  • 2
    What references do you have for a lock-free, wait-free, or non-blocking single-CAS doubly linked lists prior to the1986 design of the 68020? A claim that people hadn't come up with such a thing then doesn't imply people were stupid, but rather that blocking algorithms or data structures other than doubly-linked lists were considered adequate to meet the needs of the time. I think it's more plausible that no such algorithms were known in 1986 when CAS2 was designed into the 68020 than that the inventors of that chip wasted effort on something that was completely useless.
    – supercat
    Sep 14, 2021 at 3:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .