权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

形成MPMD型程序的高度并行编程语言编译器的基础研究

基本信息

批准号：
11680357
负责人：
HAGIHARA Kenichi
金额：
$ 0.45万
依托单位：
Osaka University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
1999
资助国家：
日本
起止时间：
1999 至 2000
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-11680357/
关键词：
task scheduling task graph division parallel computation message package super step heuristics MPMD High-speed processor communication network タスクスケシューリング負荷分散通信遅延

项目摘要

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.

我们通过任务图对并行程序的执行进行建模，通过任务调度形成调度，根据调度编码可以形成MPMD类型的并行程序。从我们应该使用评估标准作为最后生产的并行程序的执行性能的情况来看，最近已经认识到形成消息包可以应用的调度的重要性。我们将这样的时间表称为“BSP 时间表”。 BCSH 被称为形成良好 BSP 调度的算法。但是BCSH在处理大型任务图时计算时间变得巨大，因此对于大问题来说并不实用。去年我们牺牲了任务图的并行度以获得大规模任务图的调度。具体来说，我们将任务图的粒度变粗，并取得了很好的结果。今年，我们尝试通过将任务图划分为适当数量的子图并并行处理它们来保持任务图的粒度较细，并加快调度过程。结果，到目前为止，BCSH 需要大约 1.2 年的计算时间，并行计算大约 2 小时，成功计算出大任务图的 BSP 调度。我们设计了一种询问图的划分方法来获得良好的 BSP 时间表。当我们将其转换为并行程序时，性能几乎没有下降。