HW2

Read the following paper excerpts, and answer the questions below.

Reading

• It’s Time for Low Latency, Rumble et al, HotOS 2011
• Scheduling Policies, McClure et al, USENIX NSDI 2022 Sections 1-4.2 (rest optional)

Questions

The total length of your response should not exceed ~500 words. Submit responses via gradescope.

Summarization

Briefly describe the difference between load balancing and core allocation, and how they (both separately and together) affect task latency.

Comprehension

1. McClure et al. state in S4.2.1 that:

The enqueue choice curve is consistent with the well- known “power-of-two choices” result [55], showing that two choices of queues is much better than one (the “No Load Balancing” curve).

However, the paper also shows that work stealing significantly outperforms the “power of two choices”. Provide an intuitive explanation for why this is the case.

2. Design an adversarial workload for each of the following two cases in which:

• Work stealing, as McClure et al. describe, would have poor tail latency.
• Queueing-based or CPU utilization-based core allocation would have poor tail latency.

Importantly, keep the average load constant between your workload(s) and non-adversarial cases that have lower tail latency. In other words, we already know that increasing offered load will result in higher tail latency, and in this homework we want to focus on other effects. If no such adversarial workload exists, explain why not.

Synthesis

Rumble et al. argue that low latency enables new applications that make many small, dependent data accesses per request. Describe one such application, including its service-time distribution and arrival pattern. Describe a load balancing and core allocation pair from McClure et al. that you would deploy for this application, and describe the advantages and disadvantages of your choice relative to other options.