A Macrotask-level Unlimited Speculative Execution on Multiprocessors
(5/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.
I think it would be the best to start off by reviewing the speculative
execution.
This figure shows the concept of speculation.
Here is a simple program consisting of 3 blocks. BK1, 2, and BK3.
Since the program has conditional branches, we must obey the decision
of each conditional branch. For example, when the second conditional branch
is determined as "Not Taken", then we are able to execute BK3.
In this way, BK1 to BK3 are executed in serial with normal execution.
However, if we could ignore the second decision and execute BK3 before
the control decision is made, we could shorten the total execution time
as shown here. After the decision of the conditional branch, we decide
whether to choose BK3 or not. This is called SPECULATION.
As you are already aware, here is one question. "Why is it impossible
to execute BK2 with speculation?". Because, BK2 has data dependence from
BK1. So, even if we ignore control dependence, BK2 is not able to be
executed because BK2 must wait the definition of the value of "a".
This is a key point described in the next part.