Static Granularity Optimization of a Committed-Choice Language Fleng

The committed-choice language Fleng can extract much parallelism easily even from irregular programs using dataflow synchronization. However, there is a large overhead because the granularity of execution is very fine. If granularity of a program is coarsened, such an overhead can be reduced. This can be attained by fusing several goals into one goal, but this may cause deadlock. In this paper, we propose a safe goal fusion algorithm that statically optimizes granularity of a Fleng program. We implemented the algorithm and evaluated it on a parallel computer PIE64. The evaluation shows that enough speedup can be attained by this method.