A multi-grain parallelizing compilation scheme for OSCAR (Optimally scheduled advanced multiprocessor)

H. Kasahara, H. Honda, A. Mogi, A. Ogura, K. Fujiwara, S. Narita

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Citations (Scopus)


This paper proposes a multi-grain parallelizing compilation scheme for Fortran programs. 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 exploited by carefully analyzing control dependences and data dependences. The macrotasks are dynamically assigned to processor clusters to cope with run-time uncertainties, such as, conditional branches among the macrotasks and variation of execution time of each macrotask. The parallel processing of macrotasks is called the macro-dataflow computation. A macrotask composed of a Do-all 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 sequential loop or 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 a multiprocessor system named OSCAR. The evaluation shows that the multi-grain parallel processing effectively exploits parallelism from Fortran programs.

Original languageEnglish
Title of host publicationLanguages and Compilers for Parallel Computing - 4th International Workshop, Proceedings
EditorsUtpal Banerjee, David Gelernter, Alex Nicolau, David Padua
PublisherSpringer Verlag
Number of pages15
ISBN (Print)9783540554226
Publication statusPublished - 1992
Event4th Workshop on Languages and Compilers for Parallel Computing, 1991 - Santa Clara, United States
Duration: 1991 Aug 71991 Aug 9

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume589 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other4th Workshop on Languages and Compilers for Parallel Computing, 1991
Country/TerritoryUnited States
CitySanta Clara

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'A multi-grain parallelizing compilation scheme for OSCAR (Optimally scheduled advanced multiprocessor)'. Together they form a unique fingerprint.

Cite this