Minimal Control Dependencies (MCD) Tutorial

After "Branch Effect Reduction Techniques", © 1997 IEEE.

The classic definition of control dependencies is that every instruction after a branch is control dependent on the branch, and must wait for the branch to execute before they may execute. In the example below, instructions 2 through 7 are control dependent on instruction 1, a branch.

1:  if (a == b) {   //or, in branch format: if (a != b) goto 3;
2:      z = y + x; }
3:  d = e * f;
4:  g = d - h;
5:  if (x == y) {   //or, in branch format: if (x != y) goto 7;
6:      u = y + e; }
7:  j = k - m;

However, instructions 3 through 7 will execute regardless of how the branch at 1 executes. Therefore, applying this concept (minimal control dependencies), instructions 3 through 7 are not control dependent on instruction 1, and may execute concurrently with it. This implies that in many cases branches can execute in parallel and out-of-order with other branches; in the example, the branch at 5 can be executed before or at the same time as the branch at 1.

The execution of branches in parallel is essential for the exploitation of high levels of Instruction Level Parallelism.

Also see: "A Theory of Reduced and Minimal Procedural Dependencies". (Procedural dependencies are the same as control dependencies.)

May 23, 1997 | Gus Uht |