A Distributed Control Scheme of Macrotask-level Speculative Execution 
on the EM-4 Multiprosessor

  The purpose of this paper is to propose a new fast control scheme of 
macrotasks with speculation. A macrotask is a coarse grain task which is 
a unit of speculation. Previous works have reported that the speedup 
ratio is 12 to 630 times in comparison with conventional execution schemes 
without speculation when both the speculation depth and the computational 
resource are infinite, that is called oracle model. The control overhead, 
however, prevents the speedup from attaining the theoretical speedup ratio. 
Thus, the control scheme with small overhead is desired. The distributed 
control scheme archives small control overhead by adopting two mechanisms 
- 1) Each macrotask creates its successive macrotasks and 2) Each macrotask 
snoops the broadcasted control signals and determines its next state by 
itself. Thus, the control of macrotasks can be parallelized and the overhead 
to control macrotasks does not depend on the number of macrotasks. The scheme 
has been implemented on the EM-4 multiprocessor. Preliminary evaluations 
using Boolean Recurrence loops show that the control overhead of the proposed 
scheme is smaller than that of conventional control schemes - centralized 
contorl schemes.