Changes between Version 18 and Version 19 of AtomicOperations


Ignore:
Timestamp:
Dec 10, 2015, 1:00:13 PM (8 years ago)
Author:
pirouz
Comment:

--

Legend:

Unmodified
Added
Removed
Modified

  • AtomicOperations

    v18 v19  
    2121From a conceptual point of view, the atomicity is handled on the memory controller side, that is actually the L2 cache controller in the TSAR architecture. Each L2 cache controller contains a list of all pending LL/SC atomic operations in an associative ''reservation table'', that contains 32 entries.
    2222
    23  * When a processor P executes the LL(X) instruction for an address X, this réservation request is sent to the L2 cache by the L1 cache. The L2 cache allocates a 32 bits authentication key for this reservation. It registers both the X address and the K key in the associative ''reservation table'', and returns both the value stored at address X and the K value to the L1. Both the X address and the K key are also registered in the L1 cache. If another processor P' request a reservation for the same address X, it receives the save K value from the L2 cache.
     23 * When a processor P executes the LL(X) instruction for an address X, this réservation request is sent to the L2 cache by the L1 cache. The L2 cache allocates a 32 bits authentication key for this reservation. It registers both the X address and the K key in the associative ''reservation table'', and returns both the value stored at address X and the K value to the L1. Both the X address and the K key are also registered in the L1 cache. If another processor P' request a reservation for the same address X, it receives the saved K value from the L2 cache.
    2424
    25  * When a processor P executes the SC(X,D) instruction to an address X, this conditional write is sent to the L2 cache by the L1 cache, and the command contains both the reservation key K and the data to be written D. The L2 cache makes an associative search in the ''reservation table''. If both the address X and the key K match, the atomic operation is a success : The reservation is canceled in the ''reservation table'', the D value is written at address X, and a ''success'' value is returned to the L1 cache. If there is no match in the ''associative table'', the atomic operation is a failure: the D value is not written at address X, the ''reservation table is not modified, and a ''failure'' value is returned to the L1 cache.
     25 * When a processor P executes the SC(X,D) instruction to an address X, this conditional write is sent to the L2 cache by the L1 cache, and the command contains both the reservation key K and the data D to be written. The L2 cache makes an associative search in the ''reservation table''. If a reservation with the same address X and the same key K is found, the atomic operation is a success : The reservation is canceled in the ''reservation table'', the D value is written at address X, and a ''success'' value is returned to the L1 cache. If there is no match in the ''associative table'', the atomic operation is a failure: the D value is not written at address X, the ''reservation table is not modified, and a ''failure'' value is returned to the L1 cache.
    2626
    27 Clearly, in case of concurrent LL/SC access to the same address X by two or more L1 caches, the winner is defined by the first SC(X) instruction received by the L2 cache.
     27Clearly, in case of concurrent LL/SC access to the same address X by two or more L1 caches, the winner is defined by the first SC(X,D) instruction received by the L2 cache.
    2828
    2929=== 2.2 Key allocation policy ===
    3030
    31 Tha key allocator is a simple 32 bits counter, that is incremented each time a new K value is allocated to satisfy a LL requiring a new reservation. As there is a finite number of values, the mechanism requires that a K value allocated for a given reservation has a finite ''time of life''.
     31Tha key allocator is a simple 32 bits counter, that is incremented each time a new K value is allocated to satisfy a LL requiring a new reservation. As there is a finite number of values, the mechanism requires that a K value allocated for a given reservation have a finite ''time of life''.
    3232 
    33  * In the ''réservation table'' implemented in the L2 cache, the maximum ''time of  life'' for an entry containing the K value is defined by a maximum number of (2**31) allocated keys: Each time a new K' value is allocated, any entry in the ''reservation  table'' containing the K value, such as (|K-K'| == 2**31) is invalidated.   
     33 * In the ''réservation table'' implemented in the L2 cache, the maximum ''time of  life'' for an entry containing the K value is defined by a maximum number of (2^31^) allocated keys: Each time a new K' value is allocated, any entry in the ''reservation  table'' containing the K value, such as (|K-K'| == 2^31^) is invalidated.   
    3434
    35  * In the L1 cache, the bounded ''time of life'' of the registered reservation is implemented as a cycle counter: The counter starts when a new reservation is registered in the L1 cache, and the reservation is invalidated when the counter reaches 2**31 cycles.
     35 * In the L1 cache, the bounded ''time of life'' of the registered reservation is implemented as a cycle counter: The counter starts when a new reservation is initiated in the L1 cache, and the reservation is invalidated when the counter reaches 2^31^ cycles.
    3636
    3737=== 2.3 Replacement policy ===
    3838
    39 As the capacity of the ''reservation table'' is limited to 32 entries, this table can be full when a reservation request LL(x) is received by the L2 cache controller.
    40 An existing reservation entry must be invalidated in the associative table. In order to improve the robustness of the mechanism against malicious attacks, the victim selection algorithm is unbalanced: All slots have not the same probability to be evicted from the ''reservation table'', as some slots are selected with a high probability (1/2), and some other slots are selected with a very low probability (1/4096).
     39As the capacity of the ''reservation table'' is limited to 32 entries, this table can be full when a reservation request LL(X) is received by the L2 cache controller.
     40In this case, an existing reservation entry must be invalidated in the associative table. In order to improve the robustness of the mechanism against malicious attacks, the victim selection algorithm is unbalanced: All slots have not the same probability to be evicted from the ''reservation table''. This probability is of the form 1/2^i^ and ranges from 1/4096 to 1/2. Some slots are selected with a high probability (1/2), and some other slots are selected with a very low probability (1/4096).
    4141
    4242=== 2.4 Detailed specification for the L1 cache ===
    … …  
    4848 * valid reservation :  1 bit
    4949
    50 We summarize below the actions done by the L1 cache controller receiving a LL(X), SC(X,DT) or SW(X,DT) request from the processor:
    51  * '''LL(X)''' : The L1 cache registers the X address and the K key in the reservation register, activates the cycle counter, and send a single flit VCI LL command containing the X address to the L2 cache.
     50We summarize below the actions done by the L1 cache controller receiving a LL(X), SC(X,D) or SW(X,D) request from the processor:
     51 * '''LL(X)''' : The L1 cache registers the X address and its local reservation register, activates the cycle counter, and send a single flit VCI LL command containing the X address to the L2 cache. When the response is received from the L2 cache containg the value and the key K, the key is saved in the local reservation register and the value is send to the processor.
    5252 * '''SC(X,D)''' : The L1 cache checks the X address agains the registered address. In case of miss, it returns a ''failure'' code to the processor, without any VCI transaction on the network. In case of hit, it invalidates the local reservation and sent a two flits VCI SC command containing the X address, the registered K value, and the D value.
    5353 * '''SW(X,D)''' : The L1 cache checks the X address against the registered address. In case of hit the reservation is invalidated. In case of miss, the reservation is not modified. In both cases the write request is sent to the L2 cache.
    … …  
    6060 * valid reservation :  1 bit
    6161
    62 We summarize below the actions done by the L2 cache controller receiving a LL(X), SC(X,D,K) or SW(X,DT) VCI command from a L1 cache controller:
     62We summarize below the actions done by the L2 cache controller receiving a LL(X), SC(X,D,K) or SW(X,D) VCI command from a L1 cache controller:
    6363 * '''LL(X)''' : The L2 cache makes an associative search on the X address in the ''reservation table''. In case of hit (X = Xr), the L2 cache returns both the D value stored at address X, and the K value stored in the ''reservation table'' to the L1 cache. In case of miss, the L2 cache allocates a new K value from the key allocator,
    6464registers a new entry in the ''reservation table''(this can require a victim eviction), and returns the D and K values to the L1 cache.
    6565 * '''SC(X,D,K)''' : The L2 cache makes an associative search on both the the X address and the K key in the ''reservation table''. In case of hit, the reservation is invalided in the ''reservation table'', the D value is written at address X, and a ''success'' value is returned to the L1 cache. In case of miss, the D value is not written at address X, the ''reservation table'' is not modified, and a ''failure'' value is returned to the L1 cache.
    66  * '''SW(X,D)''' : The L2 cache makes an associative search on the X address in the ''reservation table''. As the write command can be a burst, with a Xmin and Xmax addresses, the HIT condition for each entry containing an address Xr is actually Xmin <= Xr <= Xmax. In case of hit, the reservation Xr is invalidated. In case of miss, the entry containing Xr is not invalided. In both cases the D value is written at address X.
     66 * '''SW(X,D)''' : The L2 cache makes an associative search on the X address in the ''reservation table''. As the write command can be a burst, with a Xmin and Xmax addresses, the HIT condition for each entry containing an address Xr is actually Xmin <= Xr <= Xmax. In case of hit, the reservation Xr is invalidated. In case of miss, the ''reservation table'' is not modified. In both cases the D value is written at address X.
    6767
    6868=== 2.6 Failure / Success encoding ===