diff options
Diffstat (limited to 'src/a.tex')
| -rw-r--r-- | src/a.tex | 379 |
1 files changed, 379 insertions, 0 deletions
diff --git a/src/a.tex b/src/a.tex new file mode 100644 index 0000000..8c3c745 --- /dev/null +++ b/src/a.tex @@ -0,0 +1,379 @@ +\chapter{``A'' Standard Extension for Atomic Instructions, Version 2.0} +\label{atomics} + +The standard atomic instruction extension is denoted by instruction +subset name ``A'', and contains instructions that atomically +read-modify-write memory to support synchronization between multiple +RISC-V threads running in the same memory space. The two forms of +atomic instruction provided are load-reserved/store-conditional +instructions and atomic fetch-and-op memory instructions. Both types +of atomic instruction support various memory consistency orderings +including unordered, acquire, release, and sequentially consistent +semantics. These instructions allow RISC-V to support the RCsc memory +consistency model~\cite{Gharachorloo90memoryconsistency}. + +\begin{commentary} +After much debate, the language community and architecture community +appear to have finally settled on release consistency as the standard +memory consistency model and so the RISC-V atomic support is built +around this model. +\end{commentary} + +\section{Specifying Ordering of Atomic Instructions} + +The base RISC-V ISA has a relaxed memory model, with the FENCE +instruction used to impose additional ordering constraints. The +address space is divided by the execution environment into memory and +I/O domains, and the FENCE instruction provides options to order +accesses to one or both of these two address domains. + +To provide more efficient support for release +consistency~\cite{Gharachorloo90memoryconsistency}, each atomic +instruction has two bits, {\em aq} and {\em rl}, used to specify +additional memory ordering constraints as viewed by other RISC-V +threads. The bits order accesses to one of the two address domains, +memory or I/O, depending on which address domain the atomic +instruction is accessing. No ordering constraint is implied to +accesses to the other domain, and a FENCE instruction should be used +to order across both domains. + +If both bits are clear, no additional ordering constraints are imposed +on the atomic memory operation. If only the {\em aq} bit is set, the +atomic memory operation is treated as an {\em acquire} access, i.e., +no following memory operations on this RISC-V thread can be observed +to take place before the acquire memory operation. If only the {\em + rl} bit is set, the atomic memory operation is treated as a {\em + release} access, i.e., the release memory operation can not be +observed to take place before any earlier memory operations on this +RISC-V thread. If both the {\em aq} and {\em rl} bits are set, the +atomic memory operation is {\em sequentially consistent} and cannot be +observed to happen before any earlier memory operations or after any +later memory operations in the same RISC-V thread, and can only be +observed by any other thread in the same global order of all +sequentially consistent atomic memory operations to the same address +domain. + +\begin{commentary} +Theoretically, the definition of the {\em aq} and {\em rl} bits allows +for implementations without global store atomicity. When both {\em + aq} and {\em rl} bits are set, however, we require full sequential +consistency for the atomic operation which implies global store +atomicity in addition to both acquire and release semantics. In +practice, hardware systems are usually implemented with global store +atomicity, embodied in local processor ordering rules together with +single-writer cache coherence protocols. +\end{commentary} + +\section{Load-Reserved/Store-Conditional Instructions} + +\vspace{-0.2in} +\begin{center} +\begin{tabular}{R@{}W@{}W@{}R@{}R@{}F@{}R@{}O} +\\ +\instbitrange{31}{27} & +\instbit{26} & +\instbit{25} & +\instbitrange{24}{20} & +\instbitrange{19}{15} & +\instbitrange{14}{12} & +\instbitrange{11}{7} & +\instbitrange{6}{0} \\ +\hline +\multicolumn{1}{|c|}{funct5} & +\multicolumn{1}{c|}{aq} & +\multicolumn{1}{c|}{rl} & +\multicolumn{1}{c|}{rs2} & +\multicolumn{1}{c|}{rs1} & +\multicolumn{1}{c|}{funct3} & +\multicolumn{1}{c|}{rd} & +\multicolumn{1}{c|}{opcode} \\ +\hline +5 & 1 & 1 & 5 & 5 & 3 & 5 & 7 \\ +LR & \multicolumn{2}{c}{ordering} & 0 & addr & width & dest & AMO \\ +SC & \multicolumn{2}{c}{ordering} & src & addr & width & dest & AMO \\ +\end{tabular} +\end{center} + +Complex atomic memory operations on a single memory word are performed +with the load-reserved (LR) and store-conditional (SC) instructions. +LR loads a word from the address in {\em rs1}, places the +sign-extended value in {\em rd}, and registers a reservation on the +memory address. SC writes a word in {\em rs2} to the address in {\em + rs1}, provided a valid reservation still exists on that address. SC +writes zero to {\em rd} on success or a nonzero code on failure. + +\begin{commentary} +Both compare-and-swap (CAS) and LR/SC can be used to build lock-free +data structures. After extensive discussion, we opted for LR/SC for +several reasons: 1) CAS suffers from the ABA problem, which LR/SC +avoids because it monitors all accesses to the address rather than +only checking for changes in the data value; 2) CAS would also require +a new integer instruction format to support three source operands +(address, compare value, swap value) as well as a different memory +system message format, which would complicate microarchitectures; 3) +Furthermore, to avoid the ABA problem, other systems provide a +double-wide CAS (DW-CAS) to allow a counter to be tested and +incremented along with a data word. This requires reading five +registers and writing two in one instruction, and also a new larger +memory system message type, further complicating implementations; 4) +LR/SC provides a more efficient implementation of many primitives as +it only requires one load as opposed to two with CAS (one load before +the CAS instruction to obtain a value for speculative computation, +then a second load as part of the CAS instruction to check if value is +unchanged before updating). + +The main disadvantage of LR/SC over CAS is livelock, which we avoid +with an architected guarantee of eventual forward progress as +described below. Another concern is whether the influence of the +current x86 architecture, with its DW-CAS, will complicate porting of +synchronization libraries and other software that assumes DW-CAS is +the basic machine primitive. A possible mitigating factor is the +recent addition of transactional memory instructions to x86, which +might cause a move away from DW-CAS. +\end{commentary} + +The failure code with value 1 is reserved to encode an unspecified +failure. Other failure codes are reserved at this time, and portable +software should only assume the failure code will be non-zero. LR and +SC operate on naturally-aligned 64-bit (RV64 only) or 32-bit words in +memory. Misaligned addresses will generate misaligned address +exceptions. + +\begin{commentary} +We reserve a failure code of 1 to mean ``unspecified'' so that simple +implementations may return this value using the existing mux required +for the SLT/SLTU instructions. More specific failure codes might be +defined in future versions or extensions to the ISA. +\end{commentary} + +\label{lrscseq} + +In the standard A extension, certain constrained LR/SC sequences are +guaranteed to succeed eventually. The static code for the LR/SC +sequence plus the code to retry the sequence in case of failure must +comprise at most 16 integer instructions placed sequentially in +memory. For the sequence to be guaranteed to eventually succeed, the +dynamic code executed between the LR and SC instructions can only +contain other instructions from the base ``I'' subset, excluding +loads, stores, backward jumps or taken backward branches, FENCE, +FENCE.I, and SYSTEM instructions. The code to retry a failing LR/SC +sequence can contain backward jumps and/or branches to repeat the +LR/SC sequence, but otherwise has the same constraints. The SC must +be to the same address as the latest LR executed. LR/SC sequences +that do not meet these constraints might complete on some attempts on +some implementations, but there is no guarantee of eventual success. + +\begin{commentary} +One advantage of CAS is that it guarantees that some thread eventually +makes progress, whereas an LR/SC atomic sequence could livelock +indefinitely on some systems. To avoid this concern, we added an +architectural guarantee of forward progress to LR/SC atomic sequences. +The restrictions on LR/SC sequence contents allows an implementation +to capture a cache line on the LR and complete the LR/SC sequence by +holding off remote cache interventions for a bounded short +time. Interrupts and TLB misses might cause the reservation to be +lost, but eventually the atomic sequence can complete. We restricted +the length of LR/SC sequences to fit within 64 contiguous instruction +bytes in the base ISA to avoid undue restrictions on instruction cache +and TLB size and associativity. Similarly, we disallowed other loads +and stores within the sequences to avoid restrictions on data cache +associativity. The restrictions on branches and jumps limits the time +that can be spent in the sequence. Floating-point operations and +integer multiply/divide were disallowed to simplify the operating +system's emulation of these instructions on implementations lacking +appropriate hardware support. +\end{commentary} + +An implementation can reserve an arbitrary subset of the memory space +on each LR and multiple LR reservations might be active simultaneously +for a single hart. An SC can succeed if no accesses from other harts +to the address can be observed to have occurred between the SC and +the last LR in this hart to reserve the address. Note this LR might +have had a different address argument, but reserved the SC's address +as part of the memory subset. Following this model, in systems with +memory translation, an SC is allowed to succeed if the earlier LR +reserved the same location using an alias with a different virtual +address, but is also allowed to fail if the virtual address is +different. The SC must fail if there is an observable memory access +from another hart to the address, or if there is an intervening +context switch on this hart, or if in the meantime the hart executed a +privileged exception-return instruction. + +\begin{commentary} +The specification explicitly allows implementations to support more +powerful implementations with wider guarantees, provided they do not +void the atomicity guarantees for the constrained sequences. +\end{commentary} + +LR/SC can be used to construct lock-free data structures. An example +using LR/SC to implement a compare-and-swap function is shown in +Figure~\ref{cas}. If inlined, compare-and-swap functionality need +only take three instructions. + +\begin{figure}[h!] +\begin{center} +\begin{verbatim} + # a0 holds address of memory location + # a1 holds expected value + # a2 holds desired value + # a0 holds return value, 0 if successful, !0 otherwise + cas: + lr.w t0, (a0) # Load original value. + bne t0, a1, fail # Doesn't match, so fail. + sc.w a0, a2, (a0) # Try to update. + jr ra # Return. + fail: + li a0, 1 # Set return to failure. + jr ra # Return. +\end{verbatim} +\end{center} +\caption{Sample code for compare-and-swap function using LR/SC.} +\label{cas} +\end{figure} + +An SC instruction can never be observed by another RISC-V thread +before the immediately preceding LR. Due to the atomic nature of the +LR/SC sequence, no memory operations from any thread can be observed +to have occurred between the LR and a successful SC. The LR/SC +sequence can be given acquire semantics by setting the {\em aq} bit on +the SC instruction. The LR/SC sequence can be given release semantics +by setting the {\em rl} bit on the LR instruction. Setting both {\em + aq} and {\em rl} bits on the LR instruction, and setting the {\em + aq} bit on the SC instruction makes the LR/SC sequence sequentially +consistent with respect to other sequentially consistent atomic +operations. + +If neither bit is set on both LR and SC, the LR/SC sequence can be +observed to occur before or after surrounding memory operations from +the same RISC-V thread. This can be appropriate when the LR/SC +sequence is used to implement a parallel reduction operation. + +\begin{commentary} +In general, a multi-word atomic primitive is desirable but there is +still considerable debate about what form this should take, and +guaranteeing forward progress adds complexity to a system. Our +current thoughts are to include a small limited-capacity transactional +memory buffer along the lines of the original transactional memory +proposals as an optional standard extension ``T''. +\end{commentary} + +\section{Atomic Memory Operations} + +\vspace{-0.2in} +\begin{center} +\begin{tabular}{O@{}W@{}W@{}R@{}R@{}F@{}R@{}R} +\\ +\instbitrange{31}{27} & +\instbit{26} & +\instbit{25} & +\instbitrange{24}{20} & +\instbitrange{19}{15} & +\instbitrange{14}{12} & +\instbitrange{11}{7} & +\instbitrange{6}{0} \\ +\hline +\multicolumn{1}{|c|}{funct5} & +\multicolumn{1}{c|}{aq} & +\multicolumn{1}{c|}{rl} & +\multicolumn{1}{c|}{rs2} & +\multicolumn{1}{c|}{rs1} & +\multicolumn{1}{c|}{funct3} & +\multicolumn{1}{c|}{rd} & +\multicolumn{1}{c|}{opcode} \\ +\hline +5 & 1 & 1 & 5 & 5 & 3 & 5 & 7 \\ +AMOSWAP.W/D & \multicolumn{2}{c}{ordering} & src & addr & width & dest & AMO \\ +AMOADD.W/D & \multicolumn{2}{c}{ordering} & src & addr & width & dest & AMO \\ +AMOAND.W/D & \multicolumn{2}{c}{ordering} & src & addr & width & dest & AMO \\ +AMOOR.W/D & \multicolumn{2}{c}{ordering} & src & addr & width & dest & AMO \\ +AMOXOR.W/D & \multicolumn{2}{c}{ordering} & src & addr & width & dest & AMO \\ +AMOMAX[U].W/D & \multicolumn{2}{c}{ordering} & src & addr & width & dest & AMO \\ +AMOMIN[U].W/D & \multicolumn{2}{c}{ordering} & src & addr & width & dest & AMO \\ +\end{tabular} +\end{center} + +\vspace{-0.1in} The atomic memory operation (AMO) instructions perform +read-modify-write operations for multiprocessor synchronization and +are encoded with an R-type instruction format. These AMO instructions +atomically load a data value from the address in {\em rs1}, place the +value into register {\em rd}, apply a binary operator to the loaded +value and the original value in {\em rs2}, then store the result back +to the address in {\em rs1}. AMOs can either operate on 64-bit (RV64 +only) or 32-bit words in memory. For RV64, 32-bit AMOs always +sign-extend the value placed in {\em rd}. The address held in {\em + rs1} must be naturally aligned to the size of the operand (i.e., +eight-byte aligned for 64-bit words and four-byte aligned for 32-bit +words). If the address is not naturally aligned, a misaligned address +exception will be generated. + +The operations supported are swap, integer add, logical AND, logical +OR, logical XOR, and signed and unsigned integer maximum and minimum. +Without ordering constraints, these AMOs can be used to implement +parallel reduction operations, where typically the return value would +be discarded by writing to {\tt x0}. + +\begin{commentary} +We provided fetch-and-op style atomic primitives as they scale to +highly parallel systems better than LR/SC or CAS. A simple +microarchitecture can implement AMOs using the LR/SC primitives. More +complex implementations might also implement AMOs at memory +controllers, and can optimize away fetching the original value when +the destination is {\tt x0}. +\end{commentary} + +To help implement multiprocessor synchronization, the AMOs optionally +provide release consistency semantics. If the {\em aq} bit is set, +then no later memory operations in this RISC-V thread can be observed +to take place before the AMO. +Conversely, if the {\em rl} bit is set, then other +RISC-V threads will not observe the AMO before memory accesses +preceding the AMO in this RISC-V thread. + +\begin{commentary} +The AMOs were designed to implement the C11 and C++11 memory models +efficiently. Although the FENCE R, RW instruction suffices to +implement the {\em acquire} operation and FENCE RW, W suffices to +implement {\em release}, both imply additional unnecessary ordering as +compared to AMOs with the corresponding {\em aq} or {\em rl} bit set. +\end{commentary} + +AMOs can also be used to provide sequentially consistent loads and +stores. A sequentially consistent load can be implemented as an +AMOADD of x0 with both {\em aq} and {\em rl} set. A sequentially +consistent store can be implemented as an AMOSWAP that writes the old +value to x0 and has both {\em aq} and {\em rl} set. + +An example code sequence for a critical section guarded by a +test-and-set spinlock is shown in Figure~\ref{critical}. Note the +first AMO is marked {\em aq} to order the lock acquisition before the +critical section, and the second AMO is marked {\em rl} to order +the critical section before the lock relinquishment. + +\begin{figure}[h!] +\begin{center} +\begin{verbatim} + li t0, 1 # Initialize swap value. + again: + amoswap.w.aq t0, t0, (a0) # Attempt to acquire lock. + bnez t0, again # Retry if held. + # ... + # Critical section. + # ... + amoswap.w.rl x0, x0, (a0) # Release lock by storing 0. +\end{verbatim} +\end{center} +\caption{Sample code for mutual exclusion. {\tt a0} contains the address of the lock.} +\label{critical} +\end{figure} + +\begin{commentary} +We recommend the use of the AMO Swap idiom shown above for both lock +acquire and release to simplify the implementation of speculative lock +elision~\cite{Rajwar:2001:SLE}. + +At the risk of complicating the implementation of atomic operations, +microarchitectures can elide the store within the acquire swap if the +lock value matches the swap value, to avoid dirtying a cache line held +in a shared or exclusive clean state. The effect is similar to a +test-and-test-and-set lock but with shorter code paths. +\end{commentary} |