Stall-Time Fair Memory Access Scheduling for Chip Multiprocessors

Problem

  • Allocating the DRAM Bandwidth Resource between threads on a Single Processor.
  • Decision is based entirely on contention in DRAM. It ignored the potential interaction through other resources like Cache but it is OK as this paper aims to solve problem related to DRAM allocation.
  • “Fairly” allocates memory resource at the same time optimizes the Memory throughput.

What is considered Fair?

Stall-Time Fair:

  • The memory slowdown due to thread interference is roughly the same for all threads adjusted for priority.
  • Memory slowdown is defined as aggregated extra latency due to sharing / latency when running alone.
  • The system aims to equalize slowdown across all threads.
  • Max MemSlowdown/ Min MemSlowdown < a (constant)

How is Slowdown Estimated?

  • STFM estimates two variables Tshared and Talone for each thread.
  • Tshared - Total number of cycles stalled on DRAM requests. Increased only when the processor stalls because of L2 cache miss.
  • Tinterference is estimated aggregated extra DRAM latency due to contention from other threads.
  • Talone = Tshared - Tinterference
  • Slowdown = Tshared/Talone

Network Fair Queuing(NFQ):

  • Equal Bandwidth share for all threads - Resource Allocation Fairness.
  • Not all applications need (or run with) the same bandwidth and if we know the need, the bandwidth share can be altered.
  • One problem with this fairness definition is the Allocated Bandwidth and Realized Bandwidth are different.
  • This technique doesn’t take into account row buffer locality and other inherent memory access parallelism. If DRAM is completely Random, this problem with NFQ is solved.
  • Idleness Problem: Unfairly penalize threads that uses DRAM without interfering with other threads.

Uniqueness:

  • Accounting for DRAM Scheduling.
  • How to estimate what the slowdown is and scheduling the DRAM accordingly.

Evaluation:

1 Performance:

* Various permutation of applications were used.
* Compared with many existing scheduling techniques.
* No targeted benchmarks e.g.: malicious code.
* Could have shown problem on real hardware (seems covered in next paper).

2 Implementation:

* Their approach of counting the number of extra states (bits) needed and describing the logic in very high level terms was not as convincing as they think.
* The communication and control overhead were not described. The cost involved in sending stall counts from core to the controller is not clear.
* The scalability of this approach beyond 16 processors is questionable.

Who the users are?

  • General Purpose Processor: All threads are general (don’t know anything) and equally important (equalized slowdown). Some threads can be prioritized.
  • Users who want well distributed slowdown.
  • Multiprogram single threaded (not sure for the case when an application requires more cores).

Other Notes

Fair Resource Sharing

* How to share resources fairly in a CMP? Would it be fair to allocate equal fraction of a resource (say memory) to each core? Though a core is allocated a certain fraction of a resource, the realized performance may be very different. Fairness depends on the program running on the core and other programs running on the CMP.
* Would it be fair to say the ratio between highest slowdown (thread) to the lowest slowdown (thread) is less than a constant. In this case the absolute slowdown is not clear.

Idleness Problem

* NFQ is based on earliest virtual deadline first scheme.
* Consider threads T1, T2 and T3 with memory requests as shown in Figure 1. T1 continuously issues memory requests whereas T2 & T3 issues requests in burst mode.

T1 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |

T2       |    |   |   |   |   |   |   |   |   |   |

T3          |    |     |    |    |    |    |    |    |

Figure 1: Vertical line represents a DRAM memory request.

* Until T2 issues its first request, T1’s requests are scheduled without interference and T1’s virtual deadline is advanced. When T2 issues its first request, its virtual deadline is zero whereas the virtual deadline of T1 is large hence T2’s requests are prioritized.
* Similarly T3’s requests are prioritized than T1 later. Thread T1 is starved and suffers significant performance loss over other threads.

Estimating Memory Related Slowdown:

* To estimate the slowdown for each thread, STFM maintains a set of registers for each thread and are updated every DRAM cycle.
* The author claimed that the update logic can be pipelined and components can be shared between threads as on-chip DRAM controller is not on the critical path. It was pointed out in the class that even the entire DRAM cycle may not be sufficient to perform update in case of multiple channel high speed DRAMS.