Automatic I/O Hint Generation through Speculative Execution

Summary. The authors present a speculative execution system for IO prefetching. They show that their system can decrease execution time nearly as well as manually-hinted prefetching. They:

• Use time spent waiting for I/O to speculatively execute and, in doing so, fetch pages which may be accessed in the future.
• Use a shadow thread for speculative execution.
• Avoid modifying state by using copy-on-write for data in the speculating thread and using software fault isolation to sandbox it.

More detail

Prefetching background. "Prefetching, requesting data before it is needed in order to move it from a high-latency locale to a low-latency locale is a well-known technique for hiding read latency." A table condensing the evolution of prefetching described in the paper is here

Architecture. Introduce a speculating thread at low priority which runs during IO idle times. Ensure correctness in spite of speculating thread by catching signals, disallowing system calls which have undesirable side-effects, and using software enforced copy-on-write techniques. The spec thread issues TIP (see TIP background here) hints and records the hints issued in a hint log. When the original thread is about to perform an IO read, it checks the hint log. If there is no next entry in the hint log or if the next hint is not correct, the spec thread is deemed off-track and is set on-track by setting its PC as if it had just returned from the current read.

If the speculative thread strays too far from the execution path, will not help and could hurt performance.

Correctness. Below is more detail on the 3 ways in which the speculating thread could change the apps behavior and how they are avoided.

1. Change code or data values. Software-enforced copy-on-write: Inspired by SFI, they instrument the code with checks around loads and stores and add a data structure which maps original memory regions to copied memory regions. Before any store, the code checks whether the memory to be accessed has been copied and, if not, copies it and updates the mapping table.
2. Produce side-effects visible outside the code. Forbid thread from issuing system calls besides the TIP calls, fstat() and sbrk().
3. Use inappropriate data values (divide by 0 or access illegal address). Catch any signals thrown and halt execution of the thread until the next IO read.

Load and stores comprise approximately 30% of the instruction mix. To lessen the cost of the load/store checks, they make a copy of the binary text section and leave the original uninstrumented.

They assume a system with strictly prioritized thread (or speculative thread could run at times other than when main threads blocked on IO). Also assume that disk-striping in effect to increase disk bandwidth.

Performance. The performance closely matches that of manually modified applications. Impressive.

Additional overhead now includes (but obviously the negative impact doesn't overcome the performance gain):

• Increased image size since the text section is copied and instrumented.
• Inaccurate hints can take IO bandwidth and cache space (manually modified issues no inaccurate hints).
• Copy-on-write copies takes memory.