|
|
| Instructions in the I-window |
| | Dependency | | I1a | I2 | I3 | I4 | | Entry = 1 | I1a | 0 | - | - | - | | if I depends | I2 | 1 | 0 | - | - | | on instrucions | I3 | 0 | 1 | 0 | - | | in window | I4 | 0 | 0 | 1 | 0 | | a Always independent |
|
|
|
|
|
Figure 7.30 The M1 dependency matrix for sequentially dependent instructions. |
|
|
|
| I1 | I2 | I3 | I4 | | | I1 | I2 | I3 | I4 | | I1 | 0 | | | | | I1 | 0 | | | | | I2 | 0 | 0 | | | | I2 | 0 | 0 | | | | I3 | 1 | 0 | 0 | | | I3 | 0 | 0 | 0 | | | I4 | 0 | 1 | 0 | 0 | | I4 | 1 | 0 | 0 | 0 | | | |
|
|
|
|
|
Figure 7.31 (a) The M2 dependency matrix (M1* M1). (b) The M3 dependency matrix. |
|
|
|
|
|
|
|
|
These dependencies can be represented as an entry in a matrix, called a precedence matrix. The basic instruction-to-instruction dependencies are represented as a simple precedence matrix; together with secondary dependencies (if I3 depends on I2 and I2 depends on I1, then I3 depends on I1), they are represented in a higher-order matrix. In Figures 7.30 and 7.31, the N instructions in the instruction window are represented across the top of the matrix. The dependencies are represented as entries in the matrix; thus, if I4 has a dependency on instruction 3, it has a 1 at mub43. The precedence matrix is a lower triangular matrix with a zero diagonal, since an instruction does not depend upon itself. Suppose a precedence matrix is created for a particular sequence of code. Since I4 may depend upon I3, and I3 may depend upon I2, I4 also depends upon I2, although it may not have an entry in the precedence matrix for entry m42. This is not a concern for us, since instructions can only be executed when they are independent of all other instructions in the block. Independence is determined by having zeros for all elements in the row. Thus, the essential ordering is maintained despite the incompleteness of the dependency picture from the initial precedence matrix. This initial precedence matrix (M1) is determined by applying the aforementioned dependency criteria to all preceding instructions in the block. |
|
|
|
|
|
|
|
|
Simple precedence matrices cover the M1 dependencies. We can get a complete picture of all the dependencies present simply by raising the precedence matrix to increasingly higher powers, up to N - 1 (there are N elements in the window), and summing (OR ing) the resulting matrices: |
|
|
|
|
|
