Atomic Operations

1. Goals

The TSAR architecture implements atomic read-then write operations to support various software synchronization mechanisms. The constraints are the following :

• A software program must have the possibility to read a data at address X, test this data, and write the (possibly modified) data at the same address X, with the guaranty that no other access to this data was done between the read and write access.
• As we want to support commodity operating systems and existing software applications, any memory address can be the target of an atomic access.
• As the atomic access can be used to implement spin-locks, the lock address must be cachable in order to benefit from the general coherence protocol, and avoid unnecessary transactions on the interconnection network.

2. LL/SC mechanism

The TSAR memory sub-system supports the LL/SC mechanism. The LL & SC commands are defined in the VCI/OCP protocol, and the LL and SC instructions must be defined in the processor Instructon Set Architecture. This is natively the case for the MIPS32 & PowerPC processors. On the direct network, the VCI CMD field can take four values : READ, WRITE, LINKED_LOAD (LL), and STORE_CONDITIONAL (SC). From a conceptual point of view, the atomicity his handled on the memory controller side (actually the memory cache controllers), as the memory controllers must maintain a list of all pending atomic operations in a reservation table :

• When a processor, identified by its SRCID, executes the LL(X) instruction to an address X, the memory controller registers an entry (SRCID, X) in the reservation table, and returns the memory value stored at address X in the VCI RDATA field. If there was another reservation for the same processor SRCID, but for another address X’, the previous reservation for X’ is lost (it means that the previous reservation can be cancelled).
• When a processor, identified by its SRCID, executes the SC(X) instruction, there is two possibilities. If there is a valid reservation entry (SRCID, X) indicating that no other access to the X address has been received, the atomic operation is a success : the write is done, the memory cache controller returns a “true” value in he RDATA VCI field, and all entries in the reservation table for the X address are cancelled. If there is no valid reservation entry (SRCID, X) in the reservation table, the atomic operation is a failure : The write is not done, and the memory cache returns a “false” value in the RDATA field.

Clearly, in case of concurrent access, the winner is defined by the first SC instruction received by the memory controller.

As described below, this mechanism can be used to implement a spin-lock, using any memory address :

• The lock acquisition is done by an atomic LL/SC operation.
• The lock release is done by a simple WRITE instruction.

			_itmask		        # enter critical section
# lock acquisition
loop		        LL Reg1 @		# Reg1 <= M[@]
			BNE Reg1 loop	        # continue if lock not taken (Reg1 == 0)
			SC  1 @		        # M[@] <= 1 / Reg2 <= KO
			BNE Reg2 loop	        # retry if not atomic (Reg2 != 0)
			...
# lock release
			SW 0 @		        # M[@] <= 0
			_itunmask		# exit critical section

3. Cachable atomic operations

In order to support cachable spin-locks, the memory cache controller, and the L1 cache controller must cooperate to implement the LL/SC mechanism.

3.1 memory cache controller

The memory cache controller contains a dedicated storage that is used to register, for each cache line the set of L1 caches that have copies. These sets of copies are implemented as linked lists of SRCIDs. To implement the Reservation Table, we just introduce, for each registered copy of a cache line, (i.e. each entry in this Reservation Table) one extra bit to register a pending LL/SC atomic operation. This approach is scalable, but creates the possibility of “false conflicts”, when several atomic access are done to the same cache line.

The actions done by the memory cache controller for the various commands are described below :

LL(SRCID, X)

   Scan all copies associated to the cache line containing the X address
  If ( a copy corresponding to SRCID.exists) {
      RESERVED = true
  } else {
      a new copy corresponding to SRCID is created in the linked list
      and marked RESERVED in the linked list 
  } 

SC(SRCID, X)

  Scan all copies associated to the cache line containing the X address
  If ( a copy corresponding to SRCID.exists and RESERVED == true ) {
      - scan again the linked list of copies to send an UPDATE request 
        to the other L1 caches, and invalidate all RESERVED bits
      - write data in the memory cache
      - after all responses to UPDATE have been received, return true 
        to the L1 cache.   
  } else {
      return false to the L1 cache
  }

WRITE(SRCID, X)

  - Scan the linked list of copies to send an UPDATE request 
    to the L1 caches (other than SRCID), and invalidate all RESERVED bits
  - Write data in the memory cache
  - after all responses to UPDATE have been received, acknowledge the 
    write request.

READ(SRCID, X)

  If ( cachable request ) {
    - register the SRCID in the list of copies associated to the X address.
    - return the complete cache line
  } else {
    - return a single word.
  }

3.2 L1 cache controller

The L1 cache controller receiving a new LL(X) request from the processor must locally register this reservation on the X address to validate the use of the locally cached copy, and to check the address when it receives a SC(X) request from the processor. This requires an extra register to store the address, and a RESERVED flip-flop in the L1 cache controller.

The actions done by the L1 cache controller for the various commands are described below :

LL(X) from processor

  If (RESERVED = true & ADDRESS = X) {    // local spin-lock         
    return the read data to the processor
  } else {                                          // first LL access                       
    RESERVED <= true
    ADDRESS <= X
    send a LL(X) request to memory cache,
    and return the read value to the processor
  } 

SC(X) from processor

  If (RESERVED = true & ADDRESS = X)  {    // possible success
    send a SC(X) request to the memory cache,
    and return the Boolean response to the processor
    RESERVED <= false
  } else {                                         // failure  
   return a false value to the processor
   RESERVED <= false
  }

INVAL(L) or UPDATE(L) from memory controller

  If (ADDRESS = L)  {                        // invalidate reservation
    RESERVED <= false
  }
  and the L1 cache is updated or invalidated.