Record Details

Interprocedural slicing of multithreaded programs with applications to Java

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Interprocedural slicing of multithreaded programs with applications to Java
 
Creator NANDA, MANGALA GOWRI
RAMESH, S
 
Subject computer programming
mathematical models
synchronization
algorithms
 
Description Slicing is a well-known program reduction technique where for a given program P and a variable of interest v at some statement P in the program, a program slice contains those set of statements belonging to P that affect v. This article presents two algorithms for interprocedural slicing of concurrent programs--a context-insensitive algorithm and a context-sensitive algorithm. The context-insensitive algorithm is efficient and correct (it includes every statement that may affect the slicing criterion) but is imprecise since it may include certain extra statements that are unnecessary. Precise slicing has been shown to be undecidable for concurrent programs. However, the context-sensitive algorithm computes correct and reasonably precise slices, but has a worst-case exponential-time complexity. Our context-sensitive algorithm computes a closure of dependencies while ensuring that statements sliced in each thread belong to a realizable path in that thread.A realizable path in a thread with procedure calls is one that reflects the fact that when a procedure finishes, execution returns to the site of the most recently executed call in that thread. One of the novelties of this article is a practical solution to determine whether a given set of statements in a thread may belong to a realizable path. This solution is precise even in the presence of recursion and long call chains in the flow graph.The slicing algorithms are applicable to concurrent programs with shared memory, interleaving semantics, explicit wait/notify synchronization and monitors. We first give a solution for a simple model of concurrency and later show how to extend the solution to the Java concurrency model. We have implemented the algorithms for Java bytecode and give experimental results.
 
Publisher Association for Computing Machinery
 
Date 2009-07-03T04:43:45Z
2011-11-25T15:05:02Z
2011-12-26T13:04:42Z
2011-12-27T05:50:42Z
2009-07-03T04:43:45Z
2011-11-25T15:05:02Z
2011-12-26T13:04:42Z
2011-12-27T05:50:42Z
2006
 
Type Article
 
Identifier ACM Transactions on Programming Languages and Systems (TOPLAS) 28(6), 1088-1144
0164-0925
http://dx.doi.org/10.1145/1186632.1186636
http://hdl.handle.net/10054/1585
http://dspace.library.iitb.ac.in/xmlui/handle/10054/1585
 
Language en