On Fri, 2005-07-01 at 22:20 -0300, Rafael Ávila de Espíndola wrote: > The finite automaton used in the pipeline hazard recognizer uses a cycle > advancing arc in every state to represent a clock pulse. Bala(1) uses a > different technique: All states were a instruction issue is not possible are > marked as "cycle advancing" and the pipeline state is update to reflect a > clock cycle. Every time the simulation gets to a cycle advancing state, it > knows that it cannot issue another instruction in this cycle. > > It appears to me that adding a cycle advance arc to every state has the > potential of increasing the size of the automaton quite significantly. Is > this true? >
There were a lot of efforts to decrease the automata size. Comb vectors are used to represent transition of one state to another. And advancing cycle transition is frequently reused. But I am sure that the automata size could be decreased more. There are a lot of methods to compress the tables (I read one article long ago where about 20 methods are reviewed and compared). The only problem is tradeoff between the size and the access speed. > What is the advantage of the "cycle advancing arc"? It is simpler to > understand, but the only use I can see is to represent a case were it was > possible to issue a instruction but, instead of doing this, the pipeline > advanced the clock. Does this happens in practice? > Yes, It is quite general situation. Even if there are enough resources to execute the insn, it has to wait a few cycle because the needed data are not ready yet. Generally speaking, data delays can be described by automaton too (using registers as resources), but the result automata will be huge. > 1) V.Bala and N.Rubin, Efficient Instruction Scheduling Using Finite State > Automata. It is probably the best article about using DFA for pipeline hazard recognizer. But gcc approach is more sophisticated. The major difference is to introduce an alternative in the automata description and optional treatment of the alternative in non-deterministic way. It makes generation of the pipeline hazard more interesting and complicated task.
