A3 - basic serial (SISD) architecture

image: T Latham, lecture slides

• such diagrams represent the architecture of a computer
• here, a single program feeds instructions to a single processor
• the instructions include fetching and writing to/from the memory
• this is the Single Instruction Single Data (SISD) model

image: T Latham, lecture slides

• cache misses are when data is fetched from the cache, avoiding having to access the main memory

image: T Latham, lecture slides

image: T Latham, lecture slides

• cache thrashing (bad):
  
  image: T Latham, lecture slides

• padding:
  
  image: T Latham, lecture slides

• generally, details such as number and length of cache lines, or the mapping scheme between main memory and cache, are irrelevant

• modern cache are often at least in part 'associative', ie. data can be stored in any cache line, generally replace the least recently used one

• however, all caches work on this same basic principle

• this assumes that data access patterns have:

  • spatial locality: code needs A[i] and A[i+j] at the same time, for a small j
  • temporal locality: if A[i] was just used, it will likely be used again soon

• interleaving:
  
  image: T Latham, lecture slides

• access patterns:
  
  image: T Latham, lecture slides
  
  image: T Latham, lecture slides

• 2D data in C:
  
  image: T Latham, lecture slides

• solution:
  
  image: T Latham, lecture slides

• so, the right most index varies the most rapidly

• it is because C uses row-major ordering