====== Write Back Cache internals ======



===== Cache line state =====

The finite state automaton below represent the possible states associated with the MESI protocol dealing
with cache coherency in CMP environment based on a snooping bus.

{{ cachewb:mesi.png }}

  * [[Coherency Protocols]]







===== Cache request state =====

Read and Write requests are put in the cache queue. Those cache queue entry have a large amount of
different states: For instance a read request will become a read miss, then a read miss that has been
requested to the memory, then a read miss that has been answered by the memory, and the data will be
sent back to the cpu.

The Figure 6.3 present the different possible values of this cache queue state. The green and red boxes
represents the possible cache request states. The blue rounded boxes represents the different functions
where the transition occurs in the cache module. \\
The black filled boxes occurs when the request is removed from the queue.



==== Read requests ====

<format dot>
digraph deps
{ bgcolor=white
  size="7,10"
  node [shape=box,style=filled,fillcolor=lightgrey,color=black,fontsize=8,fontname="Helvetica",height=0.33]

  READ [fillcolor=palegreen]
  READ_HIT_READY [fillcolor=palegreen]
  READ_MISS [fillcolor=palegreen]
  READ_MISS_REQUESTED [fillcolor=palegreen]
  READ_MISS_READY [fillcolor=palegreen]
  READ_MISS_LINE_READY [fillcolor=palegreen]
  READ_MISS_SERVICED [fillcolor=palegreen]
  READ_MISS_EVICTION [fillcolor=palegreen]
  READ_MISS_EVICTION_WRITE_DONE [fillcolor=palegreen]
  READ_MISS_EVICTION_WRITE_DONE_REQUESTED [fillcolor=palegreen]
  READ_MISS_EVICTION_WRITE_DONE_READY [fillcolor=palegreen]
  READ_MISS_EVICTION_WRITE_DONE_SERVICED [fillcolor=palegreen]

  node [shape=rect,style="rounded,filled",fillcolor=lightblue,color=black,fontsize=8]

  SetCacheHeadReadState
  CheckMemAcceptData
  ReadMemData
  ReadMemData2                        [label="ReadMemData"]
  ReadMemData5                        [label="ReadMemData"]
  CheckCPUAcceptedData
  CheckCPUAcceptedData2               [label="CheckCPUAcceptedData"]
  CheckCPUAcceptedData3               [label="CheckCPUAcceptedData"]
  CheckCPUAcceptedData4               [label="CheckCPUAcceptedData"]
  CheckMemAcceptedDatafromCache
  CheckMemAcceptedDatafromCache2      [label="CheckMemAcceptedDatafromCache"]
  UpdateCachePipelineWithWriteBuffer
  UpdateCachePipelineWithWriteBuffer2 [label="UpdateCachePipelineWithWriteBuffer"]

  node [shape=rect,color=black,style=filled,fillcolor=black,label="",width=0.25,height=0.125]

/*  ----------------- */

READ -> SetCacheHeadReadState
SetCacheHeadReadState -> READ_MISS
SetCacheHeadReadState -> READ_MISS_EVICTION
SetCacheHeadReadState -> READ_HIT_READY

READ_MISS_EVICTION -> CheckMemAcceptedDatafromCache -> READ_MISS_EVICTION_WRITE_DONE
READ_MISS_EVICTION_WRITE_DONE -> CheckMemAcceptedDatafromCache2 -> READ_MISS_EVICTION_WRITE_DONE_REQUESTED
READ_MISS_EVICTION_WRITE_DONE_REQUESTED -> UpdateCachePipelineWithWriteBuffer2 -> READ_MISS_EVICTION_WRITE_DONE_READY
READ_MISS_EVICTION_WRITE_DONE_READY -> CheckCPUAcceptedData4 -> READ_MISS_EVICTION_WRITE_DONE_SERVICED
READ_MISS_EVICTION_WRITE_DONE_READY -> ReadMemData5 -> READ_MISS_LINE_READY
READ_MISS_EVICTION_WRITE_DONE_SERVICED -> T6

READ_HIT_READY -> CheckCPUAcceptedData2 -> T4

READ_MISS -> CheckMemAcceptData -> READ_MISS_REQUESTED
READ_MISS_REQUESTED -> UpdateCachePipelineWithWriteBuffer -> READ_MISS_READY
READ_MISS_READY -> CheckCPUAcceptedData -> READ_MISS_SERVICED
READ_MISS_READY -> ReadMemData2 -> READ_MISS_LINE_READY
READ_MISS_LINE_READY -> CheckCPUAcceptedData3 -> T5

READ_MISS_SERVICED -> ReadMemData -> T1
}
</format>

==== Write requests ====

<format dot>
digraph deps
{ bgcolor=white
  size="7,10"
  node [shape=box,style=filled,fillcolor=lightgrey,color=black,fontsize=8,fontname="Helvetica",height=0.33]

  WRITE [fillcolor=lightsalmon]
  WRITE_MISS [fillcolor=lightsalmon]
  WRITE_MISS_REQUESTED [fillcolor=lightsalmon]
  WRITE_MISS_EVICTION [fillcolor=lightsalmon]
  WRITE_MISS_EVICTION_WRITE_DONE [fillcolor=lightsalmon]
  WRITE_MISS_EVICTION_WRITE_DONE_REQUESTED [fillcolor=lightsalmon]

  node [shape=rect,style="rounded,filled",fillcolor=lightblue,color=black,fontsize=8]

  ReadMemData3                        [label="ReadMemData"]
  ReadMemData4                        [label="ReadMemData"]
  CheckMemAcceptedDatafromCache3      [label="CheckMemAcceptedDatafromCache"]
  CheckMemAcceptedDatafromCache4      [label="CheckMemAcceptedDatafromCache"]
  CheckMemAcceptedDatafromCache5      [label="CheckMemAcceptedDatafromCache"]
  SetCacheHeadWriteState

  node [shape=rect,color=black,style=filled,fillcolor=black,label="",width=0.25,height=0.125]

/*  ----------------- */

WRITE -> SetCacheHeadWriteState
SetCacheHeadWriteState -> T2
SetCacheHeadWriteState -> WRITE_MISS
SetCacheHeadWriteState -> WRITE_MISS_EVICTION

WRITE_MISS -> CheckMemAcceptedDatafromCache3 -> WRITE_MISS_REQUESTED
WRITE_MISS_REQUESTED -> ReadMemData3 -> T3

WRITE_MISS_EVICTION -> CheckMemAcceptedDatafromCache4 -> WRITE_MISS_EVICTION_WRITE_DONE
WRITE_MISS_EVICTION_WRITE_DONE -> CheckMemAcceptedDatafromCache5 -> WRITE_MISS_EVICTION_WRITE_DONE_REQUESTED
WRITE_MISS_EVICTION_WRITE_DONE_REQUESTED -> ReadMemData4 -> T8
}
</format>