[giffhorn09jase] | Dennis Giffhorn, Christian Hammer, Precise Slicing of Concurrent Programs - An Evaluation of Static
Slicing Algorithms for Concurrent Programs, Journal of Automated Software Engineering, Vol. 16, (2), pp. 197--234, June 2009.
|
Abstract
While there exist efficient algorithms to slice sequential programs
precisely, there are only two algorithms for precise slicing of concurrent
interprocedural programs with recursive procedures (Krinke in Proc.
ESEC/FSE'03, pp. 178-187, 2003; Nanda and Ramesh in ACM Toplas. 28(6):1088-1144,
2006). We present an empirical evaluation of both algorithms for
Java. We demonstrate that both algorithms provide the same precision
up to the model of concurrency in use and show that the concurrency
model has strong impact on slice precision and computation costs.
Furthermore, we extend both algorithms to support dynamic thread
creation both in loops and recursion - a feature that the original
algorithms could not fully handle. The worst case complexity of the
algorithms being exponential, we developed several optimizations
and compared these with each other and with algorithms that trade
precision for speed. Finally, we show that one algorithm may produce
incorrect slices and present a remedy.
Download
Original article available at springerlink.com.
BibTeX
Authors at the institute
Projects