A Fortran Parallelizing Compilation Scheme for OSCAR Using Dependence Graph Analysis

Hironori KASAHARA  Hiroki HONDA  Seinosuke NARITA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E74-A   No.10   pp.3105-3114
Publication Date: 1991/10/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: INVITED PAPER (Special Issue on Petri Nets and Discrete Event Systems)

Full Text: PDF>>
Buy this Article

This paper proposes a Fortran parallelizing compilation scheme for a multiprocessor system named OSCAR. The scheme hierarchically exploits parallelism among coarse grain tasks, such as, loops, subroutines or basic blocks, among medium grain tasks like loop iterations and among near fine grain tasks like statements. Parallelism among the coarse grain tasks called the macrotasks is detected by analyzing a macro-flow graph which explicitly represents control flow and data dependences. The detected parallelism among the macrotasks is represented by a directed acyclic graph called a macrotask graph. Macrotasks in a macrotask graph are dynamically assigned to processor clusters to cope with run-time uncertainties. A macrotask composed of a Do-all loop or a Do-across loop, which is assigned onto a processor cluster, is processed in the medium grain in parallel by processors inside the processor cluster. A macrotask composed of a basic block is processed on a processor cluster in the near fine grain by using static scheduling. A macrotask composed of subroutine or a large sequential loop is processed by hierarchically applying macro-dataflow computation inside a processor cluster. Performance of the proposed scheme is evaluated on OSCAR. The evaluation shows that the hierarchical parallel processing scheme using dynamic and static scheduling effectively exploits parallelism from Fortran programs.