Detecting Pipeline Structural Hazards Quickly

Abstract

This paper describes a method for detecting structural hazards 5--80 times faster than its predecessors, which generally have simulated the pipeline at compile time. It accepts a compact specification of the pipeline and creates a finitestate automaton that can detect structural hazards in one table lookup per instruction. The automaton maintains an integer state that encodes all potential structural hazards for all instructions in the pipe. It accepts an instruction type and a state and either reports a hazard or produces the state that folds in the new instruction and advances the pipeline by one cy-