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 在期刊界中查找 在百度中查找 在本站中查找
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 在期刊界中查找 在百度中查找 在本站中查找
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 在期刊界中查找 在百度中查找 在本站中查找
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.
1 Smotherman M, Krishnamurthy S, Aravind PS, Hunnicutt D. Efficient DAG construction and heuristic calculation for instruction scheduling. Proc. of the 24th International Symposium on Microarchitecture. Albuquerque: IEEE Computer Society 1991,93-102.
7 Lilja DJ. Exploiting the parallelism available in loops. Computer, 1994,27(2):13-26.
8 Hwang YS, Saltz JH. Identifying parallelism in programs with cyclic graphs. Journal of Parallel and Distributed Computing, 2003,63(3):337-355.
9 Briš R. Parallel simulation algorithm for maintenance optimization based on directed Acyclic Graph. Reliability Engineering and System Safety, 2008,93(6):74-88.