|
|
|
|
|
|
|
Here, M2 = M1* M1, etc. The M2 matrix defines the second-order dependencies, e.g., if x depends on y, and y depends on z, then x has a second-order dependency on z. The multiply operation is the logical "AND," and the sum is the logical "OR," so that: |
|
|
|
|
|
|
|
|
This is shown in an example in Figure 7.31. The resultant matrix is called the full precedence matrix. If a structure such as a precedence matrix is used to control the dispatching and scheduling of instructions, the result is control flow scheduling, which is performed at decode time. |
|
|
|
|
|
|
|
|
Regardless of how dependency is detected, it is important to maximize the available concurrency. This can be done by a number of different techniques: |
|
|
|
|
|
|
|
|
1. Enlarging the block size. |
|
|
|
|
|
|
|
|
2. Relieving the dependency constraints through hardware and compiler support. |
|
|
|
|
|
|
|
|
3. Extending the range of the concurrency detection across basic blocks. |
|
|
|
|
|
|
|
|
Simply increasing the instruction block size and attempting to detect additional concurrency within a single basic block has limited potential, as we shall see. Typically, the frequency of branch is high enough to limit the number of instructions that are available for simultaneous execution. Compiler support can, however, play an important role by loop unrolling and other techniques that minimize the occurrence of branches. |
|
|
|
|
|
|
|
|
Detection of concurrently executable instructions across branch boundaries is a difficult problem. It is clearly better to minimize the occurrence of branches through static or compile time techniques. Still, successive iterations of the same loop can be executed largely independently from one another, offering significant concurrency potential. |
|
|
|
|
|
|
|
|
Of the three conditions that determine dependencies among instructions, the first represents an essential dependency, where the sources of a particular instruction depend on the result of a previous instruction. Both ordering and output dependencies are resource problems for instructions using a common resource (register) to hold different values of variables. These two different values cannot occupy the same space (i.e., register) at the same time. If we can distinguish the two different values by renaming the second variable, we can avoid incurring this loss of concurrency. Schemes for accomplishing this are discussed shortly. |
|
|
|
|
|
|
|
|
7.6.3 Other Types of Dependencies |
|
|
|
|
|
|
|
|
In addition to data dependencies, two other types of dependencies can affect overall processor performance. |
|
|
|
|
|
|
|
|
1. Procedural or Control Dependency. This is a dependency created by a branch instruction. The dynamic execution of a program consists |
|
|
|
|
|
