Progressive-BackSpace: Efficient Predecessor Computation for Post-Silicon Debug

As microprocessors become more complex, finding errors in their design becomes more difficult. Most design errors are caught before the chip is fabricated, however, some make it into the fabricated design. One challenge in determining what is wrong with a new design after fabrication is the lack of observability into the state of the fabricated chip. To address this challenge, BackSpace proposes generating a trace of the states that lead up to an erroneous state. To add one state to the trace, BackSpace first generates a set of possible predecessor states (the pre-image), then tests them one at a time to find one that is reached during execution. In this paper, we propose an improved algorithm called Progressive-BackSpace. It does not enumerate every state in the pre-image. Instead, it first finds a reachable candidate state, and then determines if it is a predecessor state. This results in a practical implementation of BackSpace by greatly reducing the time needed to find prede- cessor states. The hardware overhead is also reduced by 94.4% relative to a recently proposed implementation of BackSpace. These algorithms were implemented and evaluated on a RTL model of an out-of-order processor, that models non-deterministic effects.