Region analysis: a parallel elimination method for data flow analysis
- 1 January 1995
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Software Engineering
- Vol. 21 (11), 913-926
- https://doi.org/10.1109/32.473220
Abstract
Parallel data flow analysis methods offer the promise of calculating detailed semantic information about a program at compile-time more efficiently than sequential techniques. Previous work on parallel elimination methods has been hampered by the lack of control over interval size; this can prohibit effective parallel execution of these methods. To overcome this problem, we have designed the region analysis method, a new elimination method for data flow analysis. Region analysis emphasizes flow graph partitioning to enable better load balancing in a more effective parallel algorithm. In this paper, we present the design of region analysis and the empirical results we have obtained that indicate 1) the prevalence of large intervals in flow graphs derived from real programs and 2) the performance improvement of region analysis over parallel Allen-Cocke interval analysis. Our implementation analyzed programs from the Perfect Benchmarks and netlib running on a Sequent Symmetry S81.Keywords
This publication has 25 references indexed in Scilit:
- ISMM: the incremental software maintenance managerPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Performing data flow analysis in parallelPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Global optimizations for parallelism and locality on scalable parallel machinesPublished by Association for Computing Machinery (ACM) ,1993
- The semantic approach to program slicingPublished by Association for Computing Machinery (ACM) ,1991
- Interprocedural slicing using dependence graphsACM Transactions on Programming Languages and Systems, 1990
- Integrating noninterfering versions of programsACM Transactions on Programming Languages and Systems, 1989
- An overview of the PTRAN analysis system for multiprocessingJournal of Parallel and Distributed Computing, 1988
- Analysis of interprocedural side effects in a parallel programming environmentLecture Notes in Computer Science, 1988
- Advanced compiler optimizations for supercomputersCommunications of the ACM, 1986
- Fast Algorithms for Solving Path ProblemsJournal of the ACM, 1981