We would like to issue hints for as many of the read calls as possible so that TIP will have as much information as possible on which to base its prefetching and caching decisions. In addition, we would like to issue these hints as early as possible so that there will be ample opportunity to hide the latency of any prefetches. There are two situations that could obstruct these goals. First, because the speculating thread is only allowed to execute when the original thread is blocked, speculative execution could fall ``behind'' normal execution. If speculation is allowed to proceed in this situation, speculative execution would need to waste many cycles catching up to normal execution before it would be able to issue useful hints (that is, hints for read calls that have not already been issued). For some applications, including those with a long intermediate processing phase, speculative execution might never be able to catch up to normal execution. Second, because the speculating thread proceeds with incomplete state information, speculative execution could ``stray'' from the execution path that will be taken during normal execution. If speculation is allowed to proceed in this situation, the speculating thread might not be able to hint any future read calls. Even worse, it might generate a stream of incorrect hints, which could significantly hurt performance as explained at the beginning of Section 3. We describe speculative execution as being on track if the next hint issued would correctly predict the next unhinted future read call; otherwise, we describe speculative execution as being off track. We attempt to keep speculative execution on track as much as possible in order to increase the benefit we will be able to obtain through prefetching.
A pessimistic approach to keeping speculative execution on track would be to restart speculation every time the original thread blocks on a read call, where ``restarting speculation'' means causing the speculating thread to execute as if it had just returned from the call on which the original thread is currently blocked. However, this bounds how far speculative execution can predict the future to the distance it can progress during a single I/O stall, unnecessarily limiting the potential benefit of speculative execution. We attempt to increase the number of correct and timely hints generated by having the speculating and original threads cooperate to restart speculation only when they detect that speculative execution is off track.
Detecting when speculative execution is off track is accomplished by having the speculating thread record the hints it issues in a new data structure, called the hint log. The original thread maintains an index into the hint log and, whenever it is about to issue a read request, it checks the next entry in the hint log. If there is no next entry in the hint log, then the original thread knows that speculative execution is behind normal execution and is therefore off track. If there is an entry but it does not match the read request, then the original thread knows that speculative execution strayed from the correct execution path at some point in the past and is therefore off track. On the other hand, if the next entry matches the read, then, as far as the original thread can determine, speculative execution may still be on track.
Upon detecting that speculative execution is off track, the speculating and
original threads also cooperate to restart speculation.
In order to restart speculation, the speculating thread needs the original
thread's state. When the original thread detects that speculative execution
is off track, it copies the values of its registers into a data structure
since the speculating thread cannot otherwise acquire their values and sets a
``restart'' flag to inform the speculating thread that it is off track.
This work is performed before the original thread issues its read request
because, if the original thread blocks on the read request, the speculating
thread will have the opportunity to run. The speculating thread polls the
restart flag frequently and, if the flag is set, cleans up its current
speculation by cancelling any outstanding hints and clearing the copy-on-write
data structure. The speculating thread then restarts speculation by loading
the original thread's saved register values, making a copy of the original
thread's stack
, and jumping to the instruction
which immediately follows the read system call in the shadow code.
Through this cooperation, we ensure that the speculating thread will not waste
many cycles executing behind the original thread. We also ensure that the
speculating thread will not waste cycles restarting speculative execution
unless there is reason to believe that it is off track. While we cannot
ensure that the speculating thread will not perform incorrect speculation and
issue erroneous hints, we address this situation when it is detected by the
original thread. Finally, we require the original thread to perform little
additional work (at most, checking an entry in the hint log and saving its
registers once per read) so that observable overhead is small.