A macrotask-level unlimited speculative execution on multiprocessors

The purpose of this paper is to propose a new fast execution scheme of FORTRAN programs. The proposed scheme enables the fast initiation of macrotask when its data dependences are satisfied even if the control flow has not been reached. The previous schemes to parallelize a program including conditional branches have a number of problems - 1) Though the theoretical speedup ratio is up to N when N conditional branches are jumped on either a VLIW or a superscalar machine, the number of N is restricted up to the number of ALU's on a chip, 2) Since conventional control schemes use a few processors to control macrotasks, the overhead to control them is large. The proposed scheme solves these problems - 1) The proposed scheme enables speculative execution between coarse grain tasks, i.e., macrotasks, on multiprocessors by jumping many conditional branches, 2) A distributed control scheme is proposed and implemented on the EM-4 multiprocessor to decrease the control overhead of macrotasks. Preliminary evaluations show that the control overhead of the proposed scheme is smaller than that of the other control schemes. Moreover, it is confirmed that the distributed control can be implemented by using software when the average macrotask execution time is larger than 14.4 (Is on the EM-4 multiprocessor.