In previous post, we discussed the definition of precise interrupt. In this post, we will cover the implementations, based on J.E. Smith and A.R. Pleszkun’s paper Implementing Precise Interrupt in Pipelined Processor.

A total of 4 approaches will be discussed:

Result shift register
Reorder buffer with bypass
History buffer
Future file

The Processor Model

The precise interrupt implementation is based on the processor model shown below.

A few process states in this model have to be maintained, to implement precise interrupt. These states include

Program counter / PC
General purpose register
Main memory

Approach 1: Result Shift Register

In this approach, instructions are completed in order, and we need to maintain a result shift register, see diagram below:

When issuing an instruction which takes i cycles to complete, any stage j <= i will be reserved. When issuing a new instruction which takes k cycles to complete, if stage k is previously reserved, then it cannot be issued.

A logic on the result bus checks for exception condition when an instruction completes. If an exception occurs, the control logic will flush all subsequent instructions.

A store instruction can only modify memory state when it reaches stage 1, and all earlier instructions are free of exceptions, thus memory state is maintained.

Since result shift register stores the PC for each instruction, the PC will be part of saved state when an exception occurs.

Approach 2: Reorder Buffer with Bypass

This approach is similar to Tomasulo’s algorithm with speculation. Even though instructions can complete out of order, they commit in program order. The exception condition of an instruction will be checked when it reaches the head of reorder buffer. The “speculative” result in reorder buffer can be bypassed to younger instructions. A diagram is shown below:

Since store instructions cannot modify memory until they are the head of reorder buffer, memory state is maintained.

PC is stored in reorder buffer, thus PC state is known when an exception happens.

Approach 3: History Buffer

This approach introduces a history buffer, organized in a manner similar to reorder buffer. Instead of updating register file when instructions commit, it allows instructions to modify register file as soon as they finish, and it uses the history buffer to maintain “the last known good” state of register file, see diagram below.

As with reorder buffer, the head of history buffer guides the exception condition reports. When an exception is detected, register file can be recovered from history buffer, and the active history buffer entries are emptied from tail to head.

To make main memory precise, when a store entry shows up from the buffer, the actual store is committed to memory.

History buffer will store the PC, thus PC state will be precise as well.

Approach 4: Future File

This approach is similar to history buffer, but it uses two separate register files. The architectural file reflects the state of architectural machine, while the future file is updated as soon as instructions. Architectural file is used for exception recovering only. Future file runs ahead of architectural file, and it is used for feeding operands for functional units. See the diagram below:

A store only updates memory if it is the head of reorder buffer, thus memory state is precise. PC state is stored in reorder buffer, thus PC state is precise.

Conclusion

The precise interrupt implementation is tightly coupled with Tomasulo’s algorithm, thus it is a must-know when preparing interviews.

All these approaches have different philosophy behind them, thus it is worthy of understanding their trade-offs.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.