Papers for Scheduling, Memory Management, IPC, and Sync

Question 1

What is the premise of Fedorova’s paper on scheduling for chip multi processors?

Answer 1

That scheduling can have a high impact on CPU performance and can sometimes even counteract the benefits of smart chips

Question 2

Where does Fedorova consider the bottleneck to be for CPU performance?

Answer 2

contention for processor pipeline because that is resource that single vs multi-threaded processors are competing for

Question 3

What types of threads should be scheduled on the same CPU according to Fedorova?

Answer 3

Threads that won’t compete for the same resources as each other.

Question 4

What is Instruction delay latency?

Answer 4

delay between when an instruction starts and when it is completed (i.e. how long is the thread blocked by an instruction). Can be used to approximate processor pipeline performance

Question 5

How do we approximate the instruction delay latency?

Answer 5

Use the mean cycles-per-instruction (CPI), which is already supported by the hardware. High CPI == higher resource usage, low CPI == lower resource usage because that means that thread is blocked a lot

Question 6

What is the outcome of Fedorova paper?

Answer 6

That we should schedule threads with high and low CPIs together

Question 7

What is the test_and_set implementation?

Answer 7

while(test_and_set(lock) = BUSY) {}. (+) good latency and low delay, but (-) lots of contention

Question 8

What is the test_and_test_and_set implementation?

Answer 8

While((lock == busy) or (test_and_set(lock) == busy));

This is better because we spin on a cache lookup instead of a main memory lookup == better contention

Question 9

What is the spin lock delay implementation?

Answer 9

An improvement on test_and_test_and_set. Set a delay in the while loop. This helps decrease contention, but causes more delay. Can have static or dynamic delay

Question 10

What is a queuing lock?

Answer 10

waiting threads are placed in a queue. Requires more memory and has lower latency, but low delay and has best contention

Question 11

What are the considerations for spin lock performance according to Anderson?

Answer 11

1. Want to minimize the communication from spinning processors on the memory buses
2. Want to minimize delay between releasing a lock and a new thread acquiring it
3. Want to minimize the time it takes to acquire a lock when it is free (don’t want lots of checking to accomplish 1 and 2)

Question 12

What is quiescence?

Answer 12

time it takes for all of the waiting processors to each try their test_and_set when a lock is released

Question 13

What is the main problem with test_and_set according to Anderson?

Answer 13

• Lock is released -> invalidates caches
  
  • Each processor tries a test_and_set at the same time–> creates a queue of test_and_set operations that are waiting to happen
  • Each test_and_set invalidates every cache
  • Processors cannot unqueue their test_and_set operation
  • This is worse when the critical section is short

Question 14

What are the hardware improvements that Anderson mentions for test_and_set?

Answer 14

1. Provide parallel access to memory locations -> reduces test_and_set overhead
2. Only invalidate cache if test_and_set changes the value