A New Representation for Multithreaded Data-Parallel Code: PCFG (Parallel Control Flow Graph)

Data-parallel model is attractive in a point that data-parallelism is easily expressed in loops and the efficiency is likely to be the highest if processors perform computations on data elements stored in local memory. However, communication is necessary in many cases and single-threaded data-parallel programs have a limitation in efficient communication. In this paper, we introduce multithreading concept to overcome the limitation. We present a new representation, PCFG(Parallel Control Flow Graph) and show how to construct it. We also show multithreaded codes can be easily transformed from single-threaded data-parallel codes using PCFGs. Keywords: data-parallel, multithreading, control dependence, data dependence, parallel control flow graph. Technical area: Compilers and Languages. 1 Introduction Data-parallel loops, which have no-loop carried dependence, are the primary target of Fortran D[1] or HPF(High Performance Fortran)[2] compilers. Most of parallel loops are related to arr..