A Macrotask-level Unlimited Speculative Execution on Multiprocessors
(10/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 initiating condition of the macrotask
execution.
Macrotasks have two kinds of dependences. Control dependence and Data
dependence. Control dependence is defined as the reach of the control
flow to the macrotask. Data dependence is defined as the dependence
between the definition and reference of data.
With the normal execution, a macrotask is initiated when the both
are guaranteed. On the other hand, with the speculation, a macrotask
is initiated only when the data dependence is satisfied regardless of
the reach of control flow. So, fast initiation will be archived.
Next two figures show the desirable macrotasks for speculation.
What is the desirable macrotask ?
Firstly, preventing side-effects. Secondly enlarging its size.
Let me explain with these examples.
Here is 4 basictasks. When the value of a is defined differently
during the speculation, the following basictask can not be initiated
with speculation because the following basictask does not have the
unique value of a. This is called side-effect. In this case, the
following basictask is duplicated to prevent side-effects.
The next point is the size of macrotask. Since the speculation
is controlled macrotask by macrotask, the control overhead must be
small to achieve high performance. Therefore, we enlarge the size
of macrotask to hide the control overhead.