微信服务号

微信订阅号

2025-4-6- 4
Home > Archive>Volume 24, Issue 10, 2013 >2289-2299. DOI:10.3724/SP.J.1001.2013.04372
PDF HTML XML Export Cite reminder
Highly Scalable MHP Analysis Algorithm
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [23]
    • |
  • Related [20]
    • | | |
  • Comments
    Abstract:

    May happen in parallel (MHP) analysis decides whether a pair of statements in a parallel program can be executed concurrently; it plays an important part in parallel analyses. This paper proposes a novel may-happen-in-parallel analysis algorithm for Java programs. Compared with the existing MHP algorithm, the new alogrithm discards the unnecessary assumption that a child thread can only be join-synchronized by its parent thread, and processes start-synchronization and join-synchronization independently in a decoupled way. This makes the processing logic of the algorithm more concise and more complete than that of the existing algorithm. When computing dominator information, the new algorithm has better scalability for it does not need to construct the global flow graph for the program by inlining, which is needed by the existing algorithms. The new MHP analysis algorithm is used to sift false warnings reported by a static data race detection tool. The experimental results on 14 Java programs show that the time of computing dominator information of the new MHP analysis is much shorter than that of the existing algorithm.

    Reference
    [1] Krinke J. Static slicing of threaded programs. In: Proc. of the ACM SIGPLAN/SIGSOFT Workshop on Program Analysis for Software Tools and Engineering. New York: ACM Press, 1998. 35?42. [doi: 10.1145/277631.277638]
    [2] Masticola S, Ryder B. A model of Ada programs for static deadlock detection in polynomial time. In: Proc. of the Workshop on Parallel and Distributed Debugging. New York: ACM Press, 1991. 97?107. [doi: 10.1145/122759.122768]
    [3] Naumovich G, Avrunin GS, Clarke LA. Data flow analysis for checking properties of concurrent Java programs. In: Proc. of the 21st Int'l Conf. on Software Engineering. New York: ACM Press, 1999. 399?410. [doi: 10.1145/302405.302663]
    [4] Zhang LB, Zhang FX, Wu SG, Chen YY. A lockset-based dynamic data race detection approach. Chinese Journal of Computers, 2003,26(10):1217?1223 (in Chinese with English abstract).
    [5] Fu H, Cai M, Dong JX, Jin X, Gong Y. Enhanced data race detection approach based on lockset algorithm. Journal of Zhejiang University (Engineering Science), 2009,43(2):328?333 (in Chinese with English abstract).
    [6] Wu P, Chen YY, Zhang J. Static data-race detection for multithread programs. Journal of Computer Research and Development, 2006,43(2):329?335 (in Chinese with English abstract). [doi: 10.1360/crad20060221]
    [7] Callahan D, Subhlok J. Static analysis of low-level synchronization. In: Proc. of the ACM SIGPLAN and SIGOPS Workshop on Parallel and Distributed Debugging. New York: ACM Press, 1988. 100?111. [doi: 10.1145/68210.69225]
    [8] Duesterwald E, Soffa ML. Concurrency analysis in the presence of procedures using a data flow framework. In: Proc. of the 4th ACM SIGSOFT Workshop on Software Testing, Analysis, and Verification. New York: ACM Press, 1991. 36?48. [doi: 10.1145/ 120807.120811]
    [9] Masticola S, Ryder B. Non-Concurrency analysis. In: Proc. of the 4th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming. New York: ACM Press, 1993. 129?138. [doi: 10.1145/155332.155346]
    [10] Naumovich G, Avrunin GS. A conservative data flow algorithm for detecting all pairs of statements that may happen in parallel. In: Proc. of the 6th ACM SIGSOFT Symp. on the Foundations of Software Engineering. New York: ACM Press, 1998. 24?34. [doi: 10.1145/288195.288213]
    [11] Agarwal S, Barik R, Sarkar V, Shyamasundar R. May-Happen-in-Parallel analysis of X10 programs. In: Proc. of the 12th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming. New York: ACM Press, 2007. 183?193. [doi: 10.1145/ 1229428.1229471]
    [12] Lee J, Palsberg J. Featherweight X10: A core calculus for async-finish parallelism. In: Proc. of the 15th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming. New York: ACM Press, 2010. 25?36. [doi: 10.1145/1693453.1693459]
    [13] Naumovich G, Avrunin GS, Clarke LA. An efficient algorithm for computing MHP information for concurrent Java programs. In: Proc. of the 7th European Software Engineering Conf. Held Jointly with the 7th ACM SIGSOFT Int'l Symp. on Foundations of Software Engineering. London: Springer-Verlag, 1999. 338?354. [doi: 10.1145/318774.319252]
    [14] Li L, Verbrugge C. A practical MHP information analysis for concurrent Java programs. In: Proc. of the 17th Int'l Workshop on Languages and Compilers for Parallel Computing (LCPC 2004). Berlin: Springer-Verlag, 2004. 194?208. [doi: 10.1007/ 11532378_15]
    [15] Barik R. Efficient computation of may-happen-in-parallel information for concurrent Java programs. In: Proc. of the 18th Int'l Workshop on Languages and Compilers for Parallel Computing. Berlin: Springer-Verlag, 2005. 152?169. [doi: 10.1007/978-3-540- 69330-7_11]
    [16] Lea D. Concurrent Programming in Java. 2nd ed., New York: Addison-Wesley, 1999. 305?308.
    [17] Naik M, Aiken A, Whaley J. Effective static race detection for Java. In: Proc. of the 2006 ACM SIGPLAN Conf. on Programming Language Design and Implementation. New York: ACM Press, 2006. 308?319. [doi: 10.1145/1133981.1134018]
    [18] Milanova A, Rountev A, Ryder B. Parameterized object sensitivity for points-to and side-effect analyses for Java. In: Proc. of the Int'l Symp. on Software Testing and Analysis. New York: ACM Press, 2002. 1?11. [doi: 10.1145/566172.566174]
    [19] Milanova A, Rountev A, Ryder B. Parameterized object sensitivity for points-to analysis for Java. ACM Trans. on Software Engineering Methodology, 2005,14(1):1?41. [doi: 10.1145/1044834.1044835]
    [20] The Java grande forum benchmark. http://www.epcc.ed.ac.uk/research/java-grande/
    [21] SPEC JVM98 benchmarks. http://wwww.spec.org/jvm98
    [22] SPEC2000 Java business benchmark. http://www.spec.org/osg/jbb2000/
    [23] Aho AV, Sethi R, Ullman JD. Compilers: Principles, Techniques, and Tools. New York: Addison Wesley, 1986. 671?672.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

印乐,黄磊.高可扩展性的MHP 分析算法.软件学报,2013,24(10):2289-2299

Copy
Share
Article Metrics
  • Abstract:3092
  • PDF: 5114
  • HTML: 0
  • Cited by: 0
History
  • Received:January 04,2012
  • Revised:January 07,2013
  • Online: October 12,2013
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2033286Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063