Computer processor providing error recovery with idempotent regions
Inventors
Sankaralingam, Karthikeyan • De Kruijf, Marc Asher • Ho, Chen-Han
Assignees
National Science Foundation NSF • Wisconsin Alumni Research Foundation
Publication Number
US-9244772-B2
Publication Date
2016-01-26
Expiration Date
2031-05-04
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Abstract
A computer architecture allows for simplified recovery after mis-speculation during speculative execution by controlling speculation to occur within idempotent regions that may be recovered by re-execution of the region without the need for restoring complex state information from checkpoints. A compiler for increasing the size of idempotent regions is also disclosed.
Core Innovation
The invention provides a computer processor architecture that simplifies recovery after mis-speculation during speculative execution by restricting speculation to occur within idempotent regions. Idempotent regions are defined as regions of sequentially executed instructions that may be repeated multiple times while having the same effect on variables as if executed once. Recovery from errors within these regions is achieved by re-executing the idempotent region without restoring complex state information from checkpoints.
The background describes the problem of complex and energy-consuming circuitry needed in conventional processors to create and maintain checkpoints during speculative execution, which enable recovery from mis-speculation by restoring processor state to a precise point. This checkpoint management is particularly challenging and resource-intensive in processors with many cores, such as GPUs, and limits the use of speculation in such processors.
The invention further discloses a compiler that analyzes program instructions to identify and mark idempotent regions. The compiler also employs techniques such as converting code to static single assignment form and performing redundancy elimination transformations to increase the contiguous size of idempotent regions. This approach enables processors to recover from instruction execution errors, including mis-speculation and hardware faults, without restoring from conventional checkpoints, thereby reducing circuit complexity and energy consumption.
Claims Coverage
The patent includes multiple independent claims covering processor units, a compiler, a method of execution, and a computer system, describing various inventive features related to idempotent regions and error recovery.
Processor without variable checkpoint storage circuitry
A processor unit that detects idempotent regions during execution and recovers from mis-speculation by restarting execution within the idempotent region without restoring variable values from a checkpoint, enabling speculation without traditional checkpoint storage.
Branch-speculation and execution stalling at idempotent region boundaries
The processor includes branch-speculation circuitry that speculatively executes instructions following a branch and stalls execution at the end of the idempotent region until branch speculation completes, ensuring correct speculative execution within the region.
Write buffering of stores during speculation
The processor uses a write buffer to hold all memory stores by instructions in the idempotent region until speculation relating to those stores completes, preventing premature memory updates that could compromise recovery.
Memory dependence speculation with execution stalling
The processor speculatively executes instructions reading variables following writes (memory dependence speculation) and stalls execution at the end of the idempotent region until this speculation completes, preserving correct memory dependence handling within the region.
Out-of-order execution with stalling and no reorder buffer
The processor executes instructions out of program order and stalls at idempotent region boundaries until all out-of-order instructions complete, eliminating the need for a reorder buffer.
Region detection by marker instructions
The processor identifies idempotent regions using marker instructions inserted into the program, facilitating hardware recognition of region boundaries.
Compiler identification and marking of idempotent regions
A compiler reviews program instructions to identify idempotent regions based on dependency analysis, provides markings for their boundaries, controls variable assignments to increase their size, and identifies them by analyzing clobber anti-dependencies.
Compiler conversion to static single assignment form
The compiler converts program code to static single assignment form prior to forming idempotent regions to remove artificial anti-dependencies and increase idempotency.
Compiler redundancy elimination transformation
The compiler performs redundancy elimination transformations to reduce unnecessary memory reads not controlled by the compiler, refining the identification of idempotent regions.
Execution method using idempotent regions and mis-speculation detection
A method for executing programs that identifies idempotent regions, detects mis-speculation within those regions during speculative execution without hardware faults, and recovers by re-executing without loading variable checkpoints.
Branch speculation execution and stalling method
The method includes branch speculation followed by stalling at the end of an idempotent region until branch speculation completes.
Buffering stores until speculation completion
The method buffers stores performed during speculation in an idempotent region until all speculation relating to those stores is complete, ensuring correct memory state.
Memory dependence speculation and stalling
The method speculatively executes memory dependent instructions and stalls at idempotent region boundaries until memory speculation is complete.
Out-of-order instruction execution with stalling
The method performs out-of-order instruction execution and stalls at the end of an idempotent region until all such instructions complete.
Computer system identifying idempotent regions by clobber anti-dependencies
A computer system executes a program that identifies idempotent regions by analyzing dependencies and separates regions at clobber anti-dependencies, where a variable is read then written without a prior write, enabling recovery.
Processor permitting speculation only in idempotent regions with mis-speculation recovery
A processor permits speculation solely within idempotent regions, detects mis-speculation without hardware faults, and recovers by restarting execution in the idempotent region.
The independent claims collectively describe a processor architecture and execution environment that enable error recovery without complex checkpointing by using idempotent regions, supported by compiler techniques for region identification and annotation, and including mechanisms for various speculation types and out-of-order execution all integrated with stalling and buffering methods to preserve correctness.
Stated Advantages
Simplification of recovery from mis-speculation by eliminating the need for complex checkpoint circuitry.
Reduction in circuit energy consumption and cost by avoiding traditional checkpoint and reorder buffer structures.
Enabling speculation in processors that traditionally would not support speculation circuitry, such as graphic processors.
Compatibility with out-of-order execution while maintaining simpler recovery mechanisms.
Capability to handle hardware execution errors caused by intermittent faults without detailed state restoration.
Compiler techniques increase the size of idempotent regions, improving the effectiveness of the processor architecture.
Documented Applications
Execution of speculative instructions in computer processors using idempotent regions to simplify recovery from mis-speculation.
Application in processors including graphics processing units (GPUs) that traditionally do not support speculation due to circuitry overhead.
Hardware fault detection and recovery in advanced processors experiencing transient errors such as thermal or electrical faults.
Compiler optimization for increasing idempotent region size in compiled programs to support efficient recovery.
Interested in licensing this patent?