High-Performance Embedded Computing

3.5 Models of Computation and Programming 197

, (EQ 3-11)

where is the time at which instruction i enters pipeline stage j; and

, (EQ 3-12)

which constrains the next instruction from entering a stage until the last instruc-

tion has finished. Branch instructions generate dependencies between the stage

at which the branch is decided and instruction fetching:

. (EQ 3-13)

Data dependencies generate additional dependencies, as

, (EQ 3-14)

in which the data dependency is between instructions i and k, and the k instruc-

tion must finish stage l before the i instruction can proceed. Longest-path algo-

rithms can be used to solve these systems of constraints. ...