Changes between Initial Version and Version 1 of AtomicOperations

Timestamp:

Jun 30, 2009, 2:11:16 PM (15 years ago)

Author:

alain

Comment:

--

AtomicOperations

@@ +1 @@
+[[PageOutline]]
+
+= 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, as the LL & SC commands are defined in the VCI/OCP protocol. The LL and SC instructions must be defined by 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, 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 canceled.
+-       When a processor, identified by its SRCID, executes the SC(X) instruction, there is two possibilities. If there is a pending entry (SRCID, X) indicating that there 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 pending 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.
+
+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
+
+
+
+
+
+5.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.
+5.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 tTable) 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.
+
+  Request type    Actions in the memory cache controller 
+  
+  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.
+  }
+
+
+
+
+5.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.
+
+  Request type    Actions in the L1 cache controller 
+  
+  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 succès
+    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)
+          If (ADDRESS = L)  {                                        // invalidate reservation
+    RESERVED <= false
+  }
+
+  and the L1 cache must be updated or invalidated.
+ 
+