RISC-V Atomic Compare and Swap (CAS) Instruction - Zacas

Introduction:

RISC-V (pronounced “risk-five”) is a new instruction set architecture (ISA) originally designed to support research and education in computer architecture. However, in recent years, it has evolved into a standardized, free, and open architecture for industrial implementations.

One significant advantage of the RISC-V instruction set is its scalability, allowing users to select appropriate extension instruction sets based on specific application needs.

RISC-V offers a variety of extensions, which will be introduced one by one. This article focuses on the Zacas extension. (Note: The main content is based on the official 20240411 version spec.)

Compare and Swap (CAS) Instruction

provides a simple and often faster way to perform thread synchronization operations. When supported as a hardware instruction, CAS is commonly used in lock-free and wait-free algorithms. The Zacas extension proposes CAS instructions that operate on 32-bit, 64-bit, and 128-bit (only for RV64) data values. The CAS instruction supports C++11 atomic compare and swap operations.

While CAS can be implemented using LR/SC for XLEN wide data, CAS atomic instructions are more scalable than LR/SC in highly parallel systems. Many lock-free algorithms, such as lock-free queues, require operations on pointer variables. A simple CAS operation may not be sufficient to prevent the common ABA problem in algorithms that operate on pointer variables. To avoid the ABA problem, algorithms associate a reference counter with the pointer variable and use four-word compare and swap (operating on both the pointer and the counter) for updates. Both double-word and four-word CAS instructions support algorithms that avoid the ABA problem.

The RISC-V Instruction Set Manual Volume I

CAS (Compare-And-Swap) Operation and the ABA ProblemThe Zacas extension relies on the Zaamo extension. When introducing the A extension, we specifically compared the advantages and disadvantages of LR/SC and CAS instructions. See: RISC-V Atomic Instruction Set – A ExtensionWord/Double Word/Four Word CAS (AMOCAS.W/D/Q)For RV32,AMOCAS.W atomically loads a 32-bit data value from the rs1 address, compares the loaded value with the 32-bit value in rd, and if they are bitwise equal, stores the 32-bit value from rs2 into the initial address of rs1. The loaded value is placed in register rd.AMOCAS.W performs the following operation on RV32:

    temp = mem[X(rs1)]    if ( temp == X(rd) )        mem[X(rs1)] = X(rs2)    X(rd) = temp

AMOCAS.D is similar to AMOCAS.W, but operates on 64-bit data values.For RV32,AMOCAS.D atomically loads a 64-bit data value from the rs1 address, compares the loaded value with the 64-bit value composed of rd and rd+1 in the register pair, and if they are bitwise equal, stores the 64-bit value from rs2 and rs2+1 in the register pair into the initial address of rs1. The loaded value is placed in the register pair rd and rd+1. The instruction requires the first register in the register pair to be even; the encoding for specifying odd registers in rs2 and rd is reserved. When the first register of the source register pair is x0, both halves of the register pair read as zero. When the first register of the destination register pair is x0, the entire register result is discarded, and no write occurs to any destination register.AMOCAS.D performs the following operation on RV32:

    temp0 = mem[X(rs1)+0]    temp1 = mem[X(rs1)+4]    comp0 = (rd == x0)  ? 0 : X(rd)    comp1 = (rd == x0)  ? 0 : X(rd+1)    swap0 = (rs2 == x0) ? 0 : X(rs2)    swap1 = (rs2 == x0) ? 0 : X(rs2+1)    if ( temp0 == comp0 ) &amp;&amp; ( temp1 == comp1 )        mem[X(rs1)+0] = swap0        mem[X(rs1)+4] = swap1    endif    if ( rd != x0 )        X(rd)   = temp0        X(rd+1) = temp1    endif

For RV64,AMOCAS.W atomically loads a 32-bit data value from the rs1 address, compares the loaded value with the low 32 bits of the value in rd, and if they are bitwise equal, stores the low 32 bits of the value from rs2 into the initial address of rs1. The 32-bit value loaded from memory is sign-extended and placed in register rd.AMOCAS.W performs the following operation on RV64:

    temp[31:0] = mem[X(rs1)]    if ( temp[31:0] == X(rd)[31:0] )        mem[X(rs1)] = X(rs2)[31:0]    X(rd) = SignExtend(temp[31:0])

For RV64,AMOCAS.D atomically loads a 64-bit data value from the rs1 address, compares the loaded value with the 64-bit value in rd, and if they are bitwise equal, stores the 64-bit value from rs2 into the initial address of rs1. The loaded value is placed in register rd.AMOCAS.D performs the following operation on RV64:

    temp = mem[X(rs1)]    if ( temp == X(rd) )        mem[X(rs1)] = X(rs2)    X(rd) = temp

AMOCAS.Q (only RV64) atomically loads a 128-bit data value from the rs1 address, compares the loaded value with the 128-bit value in the register pair composed of rd and rd+1, and if they are bitwise equal, stores the 128-bit value from rs2 and rs2+1 in the register pair into the initial address of rs1. The loaded value is placed in the register pair rd and rd+1. The instruction requires the first register in the register pair to be even; the encoding for specifying odd registers in rs2 and rd is reserved. When the first register of the source register pair is x0, both halves of the register pair read as zero. When the first register of the destination register pair is x0, the entire register result is discarded, and no write occurs to any destination register.AMOCAS.Q performs the following operation:

    temp0 = mem[X(rs1)+0]    temp1 = mem[X(rs1)+8]    comp0 = (rd == x0)  ? 0 : X(rd)    comp1 = (rd == x0)  ? 0 : X(rd+1)    swap0 = (rs2 == x0) ? 0 : X(rs2)    swap1 = (rs2 == x0) ? 0 : X(rs2+1)    if ( temp0 == comp0 ) &amp;&amp; ( temp1 == comp1 )        mem[X(rs1)+0] = swap0        mem[X(rs1)+8] = swap1    endif    if ( rd != x0 )        X(rd)   = temp0        X(rd+1) = temp1    endif

For future RV128 extensions,AMOCAS.Q will encode a single register with XLEN=128 in rs2 and rd.Some algorithms may load the previous data value from a memory location into the source register for the comparison data value used in Zacas instructions. When using Zacas instructions, using a register pair to provide the comparison value can be done with two separate loads. Two separate loads may read inconsistent value pairs, but this is not an issue because AMOCAS operations themselves use atomic loads to compare data values fetched from memory.The following example code sequence illustrates how to atomically increment a 64-bit counter using AMOCAS.D in an RV32 implementation.

# a0 - address of the counter.increment:  lw   a2, (a0)      # Load current counter value using  lw   a3, 4(a0)     # two individual loads.retry:  mv   a6, a2        # Save the low 32 bits of the current value.  mv   a7, a3        # Save the high 32 bits of the current value.  addi a4, a2, 1     # Increment the low 32 bits.  sltu a1, a4, a2    # Determine if there is a carry out.  add  a5, a3, a1    # Add the carry if any to high 32 bits.  amocas.d.aqrl a2, a4, (a0)  bne  a2, a6, retry # If amocas.d failed then retry  bne  a3, a7, retry # using current values loaded by amocas.d.  ret

Similar to AMO in the A extension,AMOCAS.W/D/Q requires the address in rs1 to be naturally aligned to the size of the operand (i.e., quadword aligned to 16 bytes, doubleword aligned to 8 bytes, word aligned to 4 bytes). If the address is not naturally aligned, the same exception options apply.Similar to AMO in the A extension,AMOCAS.W/D/Q optionally provides release consistency semantics, using aq and rl bits to help implement multiprocessor synchronization. When the aq bit is set to 1, the memory operations of AMOCAS.W/D/Q that successfully execute have acquire semantics; when the rl bit is set to 1, they have release semantics. When AMOCAS.W/D/Q is unsuccessful, the memory operations have acquire semantics (if the aq bit is set to 1), but do not have release semantics (regardless of the rl bit).A FENCE instruction can be used to order memory read accesses generated by AMOCAS.W/D/Q instructions and (if generated) memory write accesses. Unsuccessful AMOCAS.W/D/Q may not perform memory writes or may write back the old value loaded from memory.AMOCAS.W/D/Q instructions always require write permissions.The following example code sequence illustrates the AMOCAS.Q implementation of the enqueue operation for a non-blocking concurrent queue, using the algorithm outlined in the paper (Michael, M. M., & Scott, M. L. (1996). Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms. Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, 267–275）. This algorithm uses AMOCAS.Q instructions to atomically operate on pointers and their associated modification counters to avoid the ABA problem.

# Enqueue operation of a non-blocking concurrent queue.# Data structures used by the queue:#   structure pointer_t {ptr:   node_t *, count: uint64_t}#   structure node_t    {next: pointer_t, value: data type}#   structure queue_t   {Head: pointer_t, Tail:  pointer_t}# Inputs to the procedure:#   a0 - address of Tail variable#   a4 - address of a new node to insert at tailenqueue:  ld   a6, (a0)          # a6 = Tail.ptr  ld   a7, 8(a0)         # a7 = Tail.count  ld   a2, (a6)          # a2 = Tail.ptr-&gt;next.ptr  ld   a3, 8(a6)         # a3 = Tail.ptr-&gt;next.count  ld   t1, (a0)  ld   t2, 8(a0)  bne  a6, t1, enqueue   # Retry if Tail &amp; next are not consistent  bne  a7, t2, enqueue   # Retry if Tail &amp; next are not consistent  bne  a2, x0, move_tail # Was tail pointing to the last node?  mv   t1, a2            # Save Tail.ptr-&gt;next.ptr  mv   t2, a3            # Save Tail.ptr-&gt;next.count  addi a5, a3, 1         # Link the node at the end of the list  amocas.q.aqrl a2, a4, (a6)  bne  a2, t1, enqueue   # Retry if CAS failed  bne  a3, t2, enqueue   # Retry if CAS failed  addi a5, a7, 1         # Update Tail to the inserted node  amocas.q.aqrl a6, a4, (a0)  ret                    # Enqueue donemove_tail:               # Tail was not pointing to the last node  addi a3, a7, 1         # Try to swing Tail to the next node  amocas.q.aqrl a6, a2, (a0)  j    enqueue           # Retry

Additional AMO PMAs

The A extension defines four levels of AMO support. Zacas defines three additional support levels:AMOCASW、AMOCASD and AMOCASQ.AMOCASW indicates that, in addition to the instructions supported at the AMOArithmetic level, the AMOCAS.W instruction is also supported.AMOCASD indicates that, in addition to the instructions supported at the AMOCASW level, the AMOCAS.D instruction is also supported.AMOCASQ indicates that, in addition to the instructions supported at the AMOCASD level, the AMOCAS.Q instruction is also supported.AMOCASW/D/Q requires AMOArithmetic level support, as AMOCAS.W/D/Q instructions require the ability to perform arithmetic compare and swap operations.

RISC-V Atomic Compare and Swap (CAS) Instruction – Zacas

Additional AMO PMAs

Leave a Comment Cancel reply