###

DOI:

计算机系统应用英文版:2012,21(9):119-123

View/Add Comment 过刊浏览高级检索 HTML

←前一篇 | 后一篇→

码上扫一扫！

下载全文

串行程序的任务DAG图构造算法

孙立斌^1,2, 邓蓉^1,2, 陈闳中^1,2

(1.同济大学计算科学与技术系, 上海 201804;2.同济大学嵌入式系统与服务计算教育部重点实验室, 上海 201804)

Algorithm for Constructing Task DAGs of Serial Programs

SUN Li-Bin^1,2, DENG Rong^1,2, CHENG Hong-Zhong^1,2

(1.Department of Computer Science and Technology, Tongji University, Shanghai 201804, China;2.Key Lab of Services Computing and Embedded Systems of Ministry of Education, Tongji University, Shanghai 201804, China)

摘要

图/表

参考文献

相似文献

本文已被：浏览 4584次下载 6041次
Received:January 17, 2012 Revised:February 29, 2012

中文摘要: 任务DAG图是刻画程序中各任务间依赖关系的一种手段, DAG图上除了标有任务间的依赖关系, 还记录了各任务的计算量和任务之间的通信量, 这些信息共同构成了任务调度的依据, 国内外有许多基于任务DAG图的调度算法研究, 但通过分析串行程序的相关性来构造任务DAG图的研究却不多见. 分析了串行程序中存在的数据相关性和控制相关性, 就程序中的顺序, 分支, 循环三种基本结构进行分别讨论, 提出了一种串行程序任务DAG图的构造算法.

中文关键词: 串行程序并行化 DAG图数据相关性控制相关性资源相关性

Abstract:Task DAG is a mean of depicting dependency among tasks of a program. Apart from dependency between tasks, amount of computation and traffic between tasks are also reflected on DAG. All these information together provides a basis for scheduling. There are much research on scheduling base on DAG both domestic and abroad, but research on constructing task DAG based on analysis of correlation among serial program is rare. This paper focuses on analysis of data dependency and control dependency and discuss respectively on sequential, branch and loop structure, propose an algorithm for constructing task DAG of serial programs.

keywords: parallelization of serial programs directed acyclic graph data dependency control dependency resources dependency

文章编号： 中图分类号： 文献标志码：

基金项目:

引用文本：
孙立斌,邓蓉,陈闳中.串行程序的任务DAG图构造算法.计算机系统应用,2012,21(9):119-123
SUN Li-Bin,DENG Rong,CHENG Hong-Zhong.Algorithm for Constructing Task DAGs of Serial Programs.COMPUTER SYSTEMS APPLICATIONS,2012,21(9):119-123

Author Name	Affiliation
SUN Li-Bin	Department of Computer Science and Technology, Tongji University, Shanghai 201804, China Key Lab of Services Computing and Embedded Systems of Ministry of Education, Tongji University, Shanghai 201804, China
DENG Rong	Department of Computer Science and Technology, Tongji University, Shanghai 201804, China Key Lab of Services Computing and Embedded Systems of Ministry of Education, Tongji University, Shanghai 201804, China
CHENG Hong-Zhong	Department of Computer Science and Technology, Tongji University, Shanghai 201804, China Key Lab of Services Computing and Embedded Systems of Ministry of Education, Tongji University, Shanghai 201804, China

Author Name	Affiliation
SUN Li-Bin	Department of Computer Science and Technology, Tongji University, Shanghai 201804, China Key Lab of Services Computing and Embedded Systems of Ministry of Education, Tongji University, Shanghai 201804, China
DENG Rong	Department of Computer Science and Technology, Tongji University, Shanghai 201804, China Key Lab of Services Computing and Embedded Systems of Ministry of Education, Tongji University, Shanghai 201804, China
CHENG Hong-Zhong	Department of Computer Science and Technology, Tongji University, Shanghai 201804, China Key Lab of Services Computing and Embedded Systems of Ministry of Education, Tongji University, Shanghai 201804, China