Unlimited Speculative Execution

A Macrotask-level Unlimited Speculative Execution on Multiprocessors (15/19)

The following description is based on the paper presented at 1995 ACM International Conference on Supercomputing head in Spain on July 3rd to 7th,1995.

If you want to have the copy of the paper, please let me know.

The next transparency shows the details of the macrotask control. We use three parameters.

level number represents the # of determined branch directions. At the beginning, it is set to 0.
assumed path represents the path from the root macrotask where the control flow has been reached.
and the maxim speculation depth N is determined by the hardware imitation to perform the speculation.

Every macrotask has these parameters. In this example, The root MT, MTi has level number L and null assumed path. These parameters show that the MTi has L-th conditional branch and it is a root macrotask where the control flow has been reached. The speculating MTk has the same level number L and the assumed path FT. The parameters show that the MTk is speculated on the assumption that the path "FT" is taken from the L-th conditional branch.
Let me consider the creation of the new MTn at MTk. Since the path from MTk to MTn is "FTT", the new MTn has the assumed path "FT + FTT". As for the level number, it is same as far as the root MT is same. When the length of the assumed path is less than N , then MTn creats MTk.
When the branch direction is determined as "Not Taken" at MKk, the control signal is broadcasted. L represents the level number, and "FTF" shows the branch direction is F on the assumption the path "FT" from root MT is taken.
The right hand side figure shows the updating of these parameters when the MTn receives the control signal (L,FTF). MTn checks the whether the assumed path is same or not. If the assumed path is same, the correspond branch direction is compared. When they are same, then it is checked as "selected". Otherwise, the MT n is discarded. When the all the assumed path are checked as selected, the MT becomes a ROOT MT. At this moment, the level number is updated. In the interest of time, I won't go into details on its manipulation.