Reducing the Repairing Penalty on Misspeculation in Thread-Level Speculation

• DOI: 10.1145/3468081.3471120
• Publication Date: 2021-10-22T16:14:12Z
• Authors: Hiroaki Hirata; Atsushi Nunome
• Keywords: 0103 physical sciences; 0202 electrical engineering, electronic engineering, information engineering; 02 engineering and technology; 01 natural sciences

We have been developing a software-based Speculative Memory (SM) library to enlarge the opportunity for program parallelization. It enables tasks having possible unknown dependencies on each other to be executed speculatively in parallel while dynamically inspecting dependencies among those tasks. When a violation of dependencies (misspeculation) is detected, it aborts the execution of the violating task and re-executes it. But the re-execution of the task from its beginning may bring large performance losses. To reduce such losses, therefore, in this paper, we introduced a checkpoint repair mechanism into SM. The idea of checkpoint repair itself is not new, but we implemented the mechanism while enabling a programmer to optimize to reduce the overhead of data saving at a checkpoint and repairing. We also present a programming technique to enhance the quality of the speculative execution result by using other task’s uncommitted data. This can contribute to reducing the frequency of aborts. We evaluated the performance of our SSM library by using a sample program constructing a binary search tree. Consequently, we could verify the effectiveness of both our checkpoint repair mechanism and the quality enhancement of the speculative execution.