期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

嵌入一致图语法的依赖图(英文) 被引量：2

Dependency Graphs Embedding Confluent Graph Grammars
下载PDF
导出
摘要 图语法将字符串上的形式文法扩充为图上的形式文法,提供一种能够使用精确的数学方法来模拟图变换的机制.提出了几种新的基于一致图语法的方法来表示控制流图、数据流图、控制数据流图、二分图和超图,并说明如何通过图重写来自动生成依赖图并挖掘并行性,从而协助并行编译器和并行语言的设计和实现. Graph grammars are developed as an extension of the formal grammars on strings to grammars on graphs, and provide a mechanism in which transformations on graphs can be modeled in a mathematically precise way. Based on confluent graph grammars, the authors present a novel representation for data-flow graphs, control-flow graphs, combined control-data-graphs, bipartite graphs and hyperedge graphs. How to extract parallelism is specified automatically at different levels by graph rewriting, thus facilitating the design and implementation of parallel compilers and parallel languages.
作者 李国东 张德富
机构地区 南京大学计算机软件新技术国家重点实验室
出处 《软件学报》 EI CSCD 北大核心 2004年第7期956-968,共13页 Journal of Software
关键词 框架图语法 图重写 依赖图 超图 编译 Computational grammars Formal languages Graph theory Program compilers
分类号 TP301 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献16

  • 1[1]Bruce H, Tamara GK. Graph partitioning models for parallel computing. Parallel Computing, 2000,26(12):1519～1534.
  • 2[2]Catalyurek VC, Aykanat C. Hypergraph-Partitioning based decomposition for parallel sparsematrix vector multiplication. IEEE Trans. on Parallel and Distributed Systems, 1999,10(7):673～693.
  • 3[3]Zhang K, Ma W. Graphical assistance in parallel program development. In: Proc. of the 10th IEEE Int'l Symp. on Visual Languages. St. Louis, 1994. 168～170.
  • 4[4]Corradini A, Montanari U, Rossi F, Ehrig H, Heckel R, Loewe M. Algebraic approaches to graph transformation. In: Rozenberg G,ed. Handbook of Graph Grammars and Computing by Graph Transformaton, Vol.l. Foundations: World Scientific Publishing,1997. 163～245.
  • 5[5]Nagl M. A tutorial and bibliographical survey of graph grammars. In: Claus Ⅴ, Ehrig H, Rozenberg G, eds.Graph Grammars.Lecture Notes in Computer Science 73, Berlin: Springer-Verlag, 1980. 70～126.
  • 6[6]Engelfrief J, Rozenberg G. Node replacement graph grammars. In: Rozenberg G, ed. Handbook of Grpah Grammars and Computing by Graph Transformation, Vol. 1. Foundations: World Scientific Publishing, 1997.1～94.
  • 7[7]Drewes F, Kreowski HJ, Habel A. Hyperedge replacement graph grammars. In: Rozenberg G, ed. Handbook of Grpah Grammars and Computing by Graph Transformation, Vol. 1. Foundations: World Scientific Publishing, 1997.95～162.
  • 8[8]Foster I, Chandy KM. Fortran M: A language for modular parallel programming. Journal of Parallel and Distributed Computing,1995,26(1):24～35.
  • 9[9]Foster I, Avalani B, Choudhary A, Xu M. A compilation system that integrates high performance Fortran and Fortran M. In: Proc.of the Scalable High Performance Computing Conf. Los Alamitos IEEE Computer Society Press, 1994 293～300.
  • 10[10]Girkar M, Polychronopoulos CD. Automatic extraction of functional parallelism from ordinary programs. IEEE Trans. on Parallel and Distributed Systems, 1992,3(2):166～178.

同被引文献28

  • 1牛亚文,边计年,吴强,薛宏熙.HCDFG-II—面向C语言系统描述的控制/数据流图表示[J].计算机辅助设计与图形学学报,2004,16(11):1547-1552. 被引量：4
  • 2陈国良,孙广中,张云泉,莫则尧.Study on Parallel Computing[J].Journal of Computer Science & Technology,2006,21(5):665-673. 被引量：5
  • 3张曦煌,邹治锋.基于用户级别的进程调度策略的研究与实现[J].计算机工程与设计,2006,27(20):3928-3930. 被引量：4
  • 4Gupta R, Pandeb S, Psarris K, et al. Compilation techniques for parallel systems [ J ]. Parallel Computing, 1999, 25 ( 13 ) : 1741 - 1783.
  • 5Ferrante J, Ottenstien K J, Warren J D. The program dependence graph and its use in optimization[J]. ACM Transactions on Programming Languages and Systems, 1987,9(3) : 319-349.
  • 6Ramaswamy S, Sapamekar S, Banerjee P. A framework for exploiting task and data parallelism on distributed memory multicomputers[ J]. IEEE Trans. on Parallel and Distributed Systems, 1997,8 (11) :1098-1116.
  • 7Girkar M, Constantine D. Extracting task-level parallelism [ J ]. ACM Trans. on Programming Languages and Systems, 1995,17 (4) :600-634.
  • 8Girkar M, Polychronopoulos C D. Automatic extraction of functional parallelism from ordinary programs[J]. IEEE Trans. on Parallel and Distributed Systems, 1992,3(2) :166-178.
  • 9Cytron R, Hind M, Hsieh W. Automatic generation of DAG parallelism[ C]. In Proc. of the SIGPLAN Conference on Programming Language Design and Implementation, Portland, Ore, SIGPLAN Notices, 1989,24(6) :54-68.
  • 10Zhang Y Q, Chen G L, Sun G Z, et al. Models of parallel computation: a survey and classification[J]. Frontiers of Computer Science in China, 2007,1 (2) : 156 -165.

引证文献2

软件学报
2004年 第7期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部