Research on Alias Set Slice and Parallelization

doi:10.3969/j.issn.1000-3428.2011.21.003

Computer Engineering ›› 2011, Vol. 37 ›› Issue (21): 6-10.

• Networks and Communications • Previous Articles Next Articles

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

别名集切片与并行化研究

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

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

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

Abstract

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

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

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

CLC Number:

N945

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

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

/ Recommend / Download Citations

URL:

https://www.ecice06.com/EN/Y2011/V37/I21/6

References

[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.

Please choose a citation manager

Content to export

Research on Alias Set Slice and Parallelization

别名集切片与并行化研究

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 3

Recommended Articles

Metrics

Comments

[1]	WANG Yaohui,WANG Dan,FU Lihua. SQL Vulnerability Detection System for PHP Program [J]. Computer Engineering, 2016, 42(4): 112-118.
[2]	WANG Xu, CHEN Yu-Ting. Static Data Race Detection for X10 Parallel Programs [J]. Computer Engineering, 2012, 38(15): 35-38,42.
[3]	ZHANG Zhi, ZHANG Lin, CENG Qiang-Kai. Improved Model Checking Technology for Program Temporal Safety Properties [J]. Computer Engineering, 2011, 37(7): 28-30.

模态框（Modal）标题

Please choose a citation manager

Content to export

Research on Alias Set Slice and Parallelization

别名集切片与并行化研究

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 3

Recommended Articles

Metrics

Comments