Implementing and Exploiting Static Speculation on Multiple Instruction Issue Processors

Abstract

Trends in processor architecture and design suggest that static speculation will become a candidate for implementation on future high-performance processors. In this dissertation, we shall examine issues related to the implementation and exploitation of static speculation. There are four primary results: 1) Precise Exceptions: Prior work in static speculation has not examined the interaction between exception handling and speculative instructions in any great detail. We investigate this interaction, exhibiting certain problematic subtleties that arise, and show how they can be overcome. 2) Speculative Tagging: Earlier proposals for implementing speculative instructions tended to have several drawbacks, including restricted applicability. We introduce speculative tagging, a new, more general, mechanism for specifying static speculation, and show it is possible to optimize exception recovery through this mechanism. 3) Whole-DAG Scheduling: Recently, there has been some work on scheduling regions of acyclic code larger than a basic block so as to take advantage of static speculation. We describe another such algorithm, known as whole-DAG scheduling, that contains innovations that make it more flexible, and allow it to use better heuristics. 4) Dynamic Speculation: The work on static speculation and exceptions suggested an alternative approach to implementing dynamic speculation. This approach results in simpler hardware than prior schemes, and is consequently cheaper to implement and potentially has a lesser impact on cycle-time. Additionally, we report results of experimental studies measuring the effectiveness of whole-DAG scheduling. In it, we show, among other things, that our scheduling technique can result in near-optimal schedules, and that the selection heuristics we adopt are superior to those used in earlier algorithms.