Experiences with a parallel algorithm for data flow analysis |
| |
Authors: | Yong-Fong Lee Barbara G Ryder Thomas J Marlowe |
| |
Affiliation: | (1) Department of Computer Science, Rutgers University, 08903 New Brunswick, NJ, USA;(2) Department of Mathematics and Computer Science, Seton Hall University, 07079 South Orange, NJ, USA |
| |
Abstract: | We have designed a family of parallel data flow analysis algorithms for execution on distributed-memory MIMD machines, based on general-purpose, hybrid algorithms for data flow analysis Marlowe and Ryder 1990]. We exploit a natural partitioning of the hybrid algorithms and explore a static mapping, dynamic scheduling strategy. Alternative mapping-scheduling choices and refinements of the flow graph condensation used are discussed. Our parallel hybrid algorithm family is illustrated on Reaching Definitions, although parallel algorithms also exist for many interprocedural (e.g., Aliasing) and intraprocedural (e.g., Available Expressions) problems Marlowe 1989]. We have implemented the parallel hybrid algorithm for Reaching Definitions on an Intel iPSC/2. Our empirical results suggest the practicality of parallel hybrid algorithms.An earlier version of this paper was presented at Supercomputing '90.The research reported here was supported, in part, by the New Jersey Commission on Science and Technology and the CAIP Center's Industrial Members, by Siemens Research Corporation and by National Science Foundation grant CCR-8920078. |
| |
Keywords: | Data flow analysis distributed-memory machines hybrid algorithms parallel algorithms partitioning scheduling |
本文献已被 SpringerLink 等数据库收录! |
|