physically impossible

they talk to their L1 caches

• at this point, there’s generally more cache levels involved
• L1 cache doesn’t talk to memory directly anymore, it talks to a L2 cache – which in turns talks to memory
  • or maybe to a L3 cache

caches are organized into “lines”, corresponding to aligned blocks of memory

• 32 bytes (older ARMs, 90s/early 2000s x86s/PowerPCs)
• 64 bytes (newer ARMs and x86s)
• 128 bytes (newer Power ISA machines)

• even if you read/write 1 byte you're writing 64 bytes

• benefits of multithreading can disappear if the threads are competing for the same cache line
• note that the problem really is that we have multiple caches, not that we have multiple cores
  • we could solve the entire problem by sharing all caches between all cores (L1)
    • each cycle, the L1 picks one lucky core that gets to do a memory operation this cycle, and runs it
      • problem: cores now spend most of their time waiting in line for their next turn at a L1 request
        • processors do a lot of those, at least one for every load/store instruction
          • slow
        • solution: next best thing is to have multiple caches and then make them behave as if there was only one cache
          • this is what cache coherency protocols are for

• strong resemblance to the "lost update" problem

• getting read access to a cache line involves talking to the other cores
  • might cause them to perform memory transactions
• writing to a cache line is a multi-step process
  • before you can write anything, you first need to acquire both exclusive ownership of the cache line and a copy of its existing contents
    • "Read For Ownership" request
• each line in a cache is identified and referenced by a cache tag (block number)
  • allows the determination of the primary memory address associated with each element in the cache
• each individual cache must monitor the traffic in cache tags
  • corresponds to the blocks being read from and written to the shared primary memory
  • done by a snooping cache (or snoopy cache, after the Peanuts comic strip)
    • basic idea behind snooping is that all memory transactions take place on a shared bus that’s visible to all cores
    • caches don’t just interact with the bus when they want to do a memory transaction themselves
      • instead, each cache continuously snoops on bus traffic to keep track of what the other caches are doing
      • if one cache wants to read from or write to memory on behalf of its core, all the other cores notice
        • that allows them to keep their caches synchronized
        • one core writes to a memory location => other cores know that their copies of the corresponding cache line are now stale and hence invalid
          • problem: write-back model
            • it’s not enough to broadcast just the writes to memory when they happen
            • physical write-back to memory can happen a long time after the core executed the corresponding store
            • for the intervening time, the other cores and their caches might themselves try to write to the same location, causing a conflict
            • if we want to avoid conflicts, we need to tell other cores about our intention to write before we start changing anything in our local copy
    • memory itself is a shared resource
      • memory access needs to be arbitrated
        • only one cache gets to read data from, or write back to, memory in any given cycle
  • caches do not respond to bus events immediately
    • reason: cache is busy doing other things (sending data to the core for example)
      • it might not get processed that cycle
    • invalidation queue
      • place where bus message triggering a cache line invalidation sits for a while until the cache has time to process it

• example: if two caches contain the same line, and the line is updated in one cache, the other cache will unknowingly have an invalid value

• MESI
  • each cache line can be in one of these four distinct states: Modified, Exclusive, Shared, or Invalid
  • key feature: delayed flush to main memory
    • example: when no one reads the data there is no need to write main memory
      • better to write only to cache as it is much faster

• occur unless other cache monitor the memory traffic or receive some direct notification of the update.

1. with update protocol
   • after write to main memory message with the updated data is broadcast to all processor modules in the system
     • each processor updates the contents of the affected cache block if this block is present in its cache
2. with invalidation of copies
   • after write to main memory invalidation request is broadcast through the system
     • all copies in other caches are invalidated

• most of the cache line changes on a write-back => can issue one large memory transaction instead of several small ones
  • more efficient

• its value is different from the main memory

• it must be in the I state for all other cores

• on a cache miss, the cache still needs to write-back data to memory if it is in the modified state
  • processor must signal "Dirty" and write the data back to the shared primary memory
    • causing the other processor to abandon its memory fetch
• it is necessary to first write in memory and then read it from there
  • reading cores can't directly read from the cache of the writing core
    • it's more expensive
    • example
      1. suppose, both of A & B share that line and B got it directly from the cache line of A
      2. C needs that line for a write
      3. both A & B will have keep snooping that line
         • shared copies grows
         • greater impact on performance due to the snooping done by all the 'shared' processors
• example
  1. let's processor A has that modified line
  2. processor B is trying to read that same cache (modified by A) line from main memory
  3. A's snooping read attempts for that line
     • content in the main memory is invalid now (because A modified the content)
  4. A has to write it back to main memory
     • in order to allow processor B (and others) to read that line

• reduces traffic on a shared bus

• this tells all other cores to invalidate their copies of that cache line, if they have any

• even if that value is perfectly current => false sharing

by definition, any copy of the line in the caches of other processors must be in the Shared State

what happens depends on the state of the cache in the requesting processor

1. Modified
   • protocol does not specify an action for the processor
2. Shared
   • processor writes the data
   • marks the cache line as Modified
   • broadcasts a Cache Invalidate signal to other processors
3. Exclusive
   • processor writes the data and marks the cache line as Modified

example

1. Core A reads a value
2. Core B reads a value from the same are of memory
3. Core B writes into that value
4. Core A tries to read a value from that same part of memory
   • Core B's cache line is forced back to memory
   • Core A's cache line is re-loaded from memory

• write to main memory will be delayed up to very end
• assuming that threads are modifying not interlapping set of variables it's OK
• example

  private static final int THREADS = 6
  private static int[] results = new int[THREADS] // each thread has it's own place to accumulate results
  

  however, if we modify results using volatile machinery, we have false sharing

  VH.setVolatile(results, offset, results[offset] + 1)
  

• jdk.internal.vm.annotation.Contended
  • annotation to prevent false sharing
  • introduced by Java 8 under sun.misc package
    • repackaged later by Java 9
  • by default adds 128 bytes of padding
    • cache line size in many modern processors is around 64/128 bytes
    • configurable through the -XX:ContendedPaddingWidth
  • annotated field => JVM will add some paddings around it
  • annotated class => JVM will add the same padding before all the fields
  • -XX:-RestrictContended
    • disable @Contended annotation
  • use cases
    • ConcurrentHashMap
      • https://github.com/openjdk/jdk/blob/f29d1d172b82a3481f665999669daed74455ae55/src/java.base/share/classes/java/util/concurrent/ConcurrentHashMap.java#L2565
    • ForkJoinPool
      • https://github.com/openjdk/jdk/blob/1e8806fd08aef29029878a1c80d6ed39fdbfe182/src/java.base/share/classes/java/util/concurrent/ForkJoinPool.java#L774

• Vector Packed Add
• used for adding packed integer or floating-point values stored in SIMD registers
• vs add - typical instructions used for scalar operations

• Vector Move Unaligned
• used for moving data between memory and SIMD registers
• vs mov - typical instructions used for scalar operations