On optimal slicing of parallel programs
On optimal slicing of parallel programs
复制标题
并行程序的最优切片
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
H. Seidl
中科院分区：
文献类型：
--
作者：
M. Müller;H. Seidl
最优程序切片确定程序π中的语句S是否影响指定的一组语句，假设π中的所有条件都被解释为非确定性选择。
Optimal program slicing determines for a statement S in a program π whether or not S affects a specified set of statements, given that all conditionals in π are interpreted as non-deterministic choices.
Only recently, it has been shown that reachability of program points and hence also optimal slicing is undecidable for multi-threaded programs with (parameterless) procedures and synchronization [23]. Here, we sharpen this result by proving that slicing remains undecidable if synchronization is abandoned---although reachability becomes polynomial. Moreover, we show for multi-threaded programs without synchronization, that slicing stays PSPACE-hard when procedure calls are forbidden, and becomes NP-hard for loop-free programs. Since the latter two problems can be solved in PSPACE and NP, respectively, even in presence of synchronization, our new lower bounds are tight.
Finally, we show that the above decidability and lower bound properties equally apply to other simple program analysis problems like copy constant propagation and true liveness of variables. This should be contrasted to the problems of strong copy constant propagation and (ordinary) liveness of variables for which polynomial algorithms have been designed [15, 14, 24]
.