Fundamental studies of a highly parallel programming language compiler forming MPMD type programs

点击翻译按钮获取中文摘要

We model an execution of parallel program by a task graph and form a schedule by a task scheduling and can form a parallel program of MPMD type by being coded according to the schedule. From a situation that we should use evaluation standard as execution performance of parallel program that is last production thing, importance of forming such the schedule that message package can apply has been recognized recently. We call such a schedule "BSP schedule". BCSH is known as an algorithm to form a good BSP schedule. But computation time of BCSH becomes enormous when it deals with a big task graph, thus it is not practical for big problems.Last year we sacrificed a parallel degree of a task graph in order to get a schedule for a large-scale task graph. Concretely we made the grain of the task graph coarse, and attained a good result.During this year we tried to keep a grain of a task graph being fine and to speedup scheduling process by dividing the task graph into a sutable number of subgraphs and processing them in parallel. As a result it was successful to compute a BSP schedule of a big task graph whose calculation time of about 1.2 year is necessary by BCSH until now in around 2 hours in parallel. We devised a division method of a ask graph to get good BSP schedule. There is little performance deterioration when we transformed it to a parallel program.