DocumentCode :
3566868
Title :
State space reduction in abstract interpretation of parallel programs
Author :
Chow, Jyh-Herng ; Harrison, Williams Ludwell, III
Author_Institution :
IBM Santa Teresa Lab., San Jose, CA, USA
fYear :
1994
Firstpage :
277
Lastpage :
288
Abstract :
Traditional compiler techniques operating on control flow graphs are not adequate for analyzing parallel programs where data can flow from one node to another through the shared memory, even though the nodes are not related by control flow edges. Abstract interpretation provides a general and unified framework for program analyses, and can be applied to parallel programs without much difficulty. However, the state space explosion problem in abstract interpretation of parallel programs must be relieved in order to make compile-time analyses practical. Although abstract interpretation itself provides an excellent mechanism for state space reduction by state abstraction, lower precision analysis often results from taking a higher degree of abstraction. In this paper, we present state space reduction that preserves analysis precision by eliminating redundant interleavings, based on Valmari´s (1990) stubborn set method. We also propose an iterative algorithm for analyzing programs with pointers and closures, in which knowledge about shared locations required by existing methods is not available. The proposed algorithm has been implemented, and we discuss preliminary results of the implementation
Keywords :
parallel programming; program interpreters; state-space methods; system monitoring; abstract interpretation; closures; compiler techniques; control flow graphs; iterative algorithm; parallel programs; pointers; redundant interleavings; state space reduction; Algorithm design and analysis; Costs; Explosions; Flow graphs; Interleaved codes; Iterative algorithms; Laboratories; Program processors; State-space methods; Yarn;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computer Languages, 1994., Proceedings of the 1994 International Conference on
Print_ISBN :
0-8186-5640-X
Type :
conf
DOI :
10.1109/ICCL.1994.288373
Filename :
288373
Link To Document :
بازگشت