别名集切片与并行化研究

doi:10.3969/j.issn.1000-3428.2011.21.003

计算机工程 ›› 2011, Vol. 37 ›› Issue (21): 6-10. doi: 10.3969/j.issn.1000-3428.2011.21.003

别名集切片与并行化研究

桑春雷^1,2，张兆庆¹

(1. 中国科学院计算技术研究所计算机系统结构重点实验室，北京 100190；2. 中国科学院研究生院，北京 100049)

收稿日期:2011-04-19 出版日期:2011-11-05 发布日期:2011-11-05
作者简介:桑春雷(1979－)，男，博士研究生，主研方向：编译技术，程序分析，自动并行化；张兆庆，研究员
基金资助:
国家“973”计划基金资助项目(2011CB302504)；“核高基”重大专项(2009ZX01036-001-002)；国家自然科学基金创新研究群体资助项目(60921002)

Research on Alias Set Slice and Parallelization

SANG Chun-lei ^1,2, ZHANG Zhao-qing ¹

(1. Key Laboratory of Computer System and Architecture, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China; 2. Graduate University of Chinese Academy of Sciences, Beijing 100049, China)

Received:2011-04-19 Online:2011-11-05 Published:2011-11-05

摘要/Abstract

摘要： 针对复杂程序的分析问题，提出基于别名集切片的切片级并行技术与并行程序分析技术。利用传统分析算法，在每个切片上并行地进行复杂程序分析，从而实现复杂程序分析的并行化，加快复杂程序分析速度。以SPEC CPU2000/CPU2006中的部分C程序为测试用例进行实验，结果表明，利用别名集切片技术可在4个进程并行情况下，获得3.42的加速比。

关键词: 别名集切片, 并行程序分析, 切片技术, 别名分析, 程序检错

Abstract: In this paper, it presents a new slicing technique and alias set slicing technique. Based on alias set slice, it partitions the input program into several independent slices which can analyzed by complex program analyzer, because slices contain all statements which they dependent on. It uses this method to parallelize complex alias analysis and error checking analysis. With the experiments on SPEC CPU2000/CPU2006, it can achieve speedup 3.42 for parallel error checking analysis.

Key words: alias set slice, parallel program analysis, slicing technique, alias analysis, program error checking

中图分类号:

N945

桑春雷, 张兆庆. 别名集切片与并行化研究[J]. 计算机工程, 2011, 37(21): 6-10.

SANG Chun-Lei, ZHANG Zhao-Qiang. Research on Alias Set Slice and Parallelization[J]. Computer Engineering, 2011, 37(21): 6-10.

http://www.ecice06.com/CN/Y2011/V37/I21/6

参考文献

[1] Mark W. Program Slicing[C]//Proc. of the 5th Int’l Conf. on Software Engineering. [S. l.]: IEEE Press, 1981.
[2] Ottenstein K, Ottenstein L. The Program Dependence Graph in a Software Development Environment[J]. ACM SIGPLAN Notices, 1984, 19(5): 177-184.
[3] Ferrante J, Ottenstein K J, Warren J D. The Program Dependence Graph and Its Use in Optimization[J]. ACM Trans. on Programming Languages and Systems, 1987, 9(3): 319-329.
[4] Horwitz S, Reps T. Inter-procedural Slicing Using Dependence Graphs[C]//Proc. of ACM Conf. on Programming Language

Design and Implementation. [S. l.]: ACM Press, 1988.
[5] Susan H, Thomas R, David B. Inter-procedural Slicing Using Dependence Graphs[J]. ACM Trans. on Programming Languages and Systems, 1990, 12(1): 26-60.
[6] Frank T. A Survey of Program Slicing Techniques[J]. Journal of Programming Languages, 1995, 3(3): 121-189.
[7] Liao Shih-Wei, Amer D, Robert P. SUIF Explorer: An Interactive and Inter-procedural Parallelizer[C]//Proc. of the 7th ACM Symposium on Principles and Practice of Parallel Programming. [S. l.]: ACM Press, 1999.
[8] Bjarne S. Program Slicing Techniques[C]//Proc. of the 23rd ACM Symp. on Principles of Programming Languages. Petersburg Beach, Florida, USA: [s. n.], 1996.
[9] Vineet K. Bootstrapping: A Technique for Scalable Flow and Context-sensitive Pointer Alias Analysis[C]//Proc. of 2008 ACM Conf. on Programming Language Design and Implemen- tation. Tucson, USA: [s. n.], 2008.
[10] Yu Hongtao, Xue Jingling, Huo Wei, et al. Level by Level: Making Flow and Context-sensitive Pointer Analysis Scalable for Millions of Lines of Code[C]//Proc. of the 8th Annual IEEE/ACM Int’l Symp. on Code Generation and Optimization. Toronto, Ontario, Canada: [s. n.], 2010.
[11] Mark W. Reconstructing Sequential Behavior from Parallel Behavior Projections[J]. Information Processing Letters, 1983, 17(3): 129-135.
[12] Spyridon T, Matthew J. A Framework for Unrestricted Whole- program Optimization[C]//Proc. of 2006 ACM Conf. on Program- ming Language Design and Implementation. Ottawa, Ontario, Canada: [s. n.], 2006.
[13] 吴国伟, 曹厚华. 快速自动程序流分析方法研究[J]. 计算机工程, 2010, 36(15): 55-56.

选择文件类型/文献管理软件名称

选择包含的内容

别名集切片与并行化研究

Research on Alias Set Slice and Parallelization

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

本文评价

[1]	王耀辉,王丹,付利华. 面向PHP程序的SQL漏洞检测系统[J]. 计算机工程, 2016, 42(4): 112-118.
[2]	王旭, 陈雨亭. X10并行程序中静态数据竞争检测[J]. 计算机工程, 2012, 38(15): 35-38,42.
[3]	张志, 张林, 曾庆凯. 改进的程序时序安全属性模型检测技术[J]. 计算机工程, 2011, 37(7): 28-30.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

别名集切片与并行化研究

Research on Alias Set Slice and Parallelization

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

本文评价