Address Dependencies

Definition

Address dependencies are a type of instruction dependency in microprocessor pipelining. They have a more complex structure than register dependencies and are tied to the internal organization of memory management units. They describe how two instructions relate to each other through the memory subsystem rather than through explicit register operands.

Examples

The following are recognized forms of address dependencies, each corresponding to a distinct level of the memory hierarchy:

VAEqual — equality of virtual addresses used by two instructions.
TLBEqual — equality of TLB (Translation Lookaside Buffer) entries accessed by two instructions.
PAEqual — equality of physical addresses referenced by two instructions.
CacheRowEqual — equality of cache rows touched by two instructions.

These four exemplar forms illustrate that address dependencies can be expressed at multiple stages of address translation and caching, which is what gives them their more complex structure relative to register dependencies.

Relation to Register Dependencies

Register dependencies are defined by the equality of registers used as operands of two instructions and are classified by the access pattern of those registers:

read-read — both instructions read from the same register.
read-write — the first instruction reads from a register while the second writes into it.
write-read — the first instruction writes into a register while the second reads from it.
write-write — both instructions write into the same register.

Address dependencies complement this view by capturing relationships that cannot be reduced to register-operand equality, since they involve the translation and storage mechanisms of the memory hierarchy.

Role in Pipeline Hazard Templates

Address dependencies are used as ingredients of pipeline hazard templates when generating test programs for microprocessors. In a hazard template, a hazard situation is specified by constraints on a set of parameters (P1 through PK). The dependencies between instructions — including address dependencies — partition a verification engineer's specification into equivalence classes, and these equivalence classes serve as the basis for constructing iterators used to generate the test program.