Subscribe Now Subscribe Today
Science Alert
Curve Top
Information Technology Journal
  Year: 2008 | Volume: 7 | Issue: 2 | Page No.: 253-260
DOI: 10.3923/itj.2008.253.260
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail

A New Data Structure and Algorithm for Static Slicing Concurrent Programs

Huang Weiping and Xiao Jianyu

Internal representation and static slicing algorithm of concurrent programs are studied. Based on the comparison among existed slicing algorithms and analysis of the fact that Krinke`s algorithm produced imprecise program slice for the program structure which has loops nested with one or more threads, a conclusion is drawn that the reason for the impreciseness is that Krinke`s data structure-threaded program dependence graph had over coarse definitions of data dependence relations between threads and the constraint put on the execution path in concurrent program is unduly loose. An improved threaded program dependence graph is proposed which adds a new dependence relation of loop-carried data dependence crossing thread boundaries. An improved slicing algorithm is also proposed which introduces a new concept of regioned execution witness to further constrain the execution path. The pseudo code of algorithm adding loop-carried data dependence relations crossing thread boundaries is given. The pseudo code of the new slicing algorithm is also given whose complexity has been analyzed. Examples shows that the improved slicing algorithm designed on the improved data structure can restrain the impreciseness of Krinke`s.
PDF Fulltext XML References Citation Report Citation
  •    A Fast and Power Efficient Updating Algorithm for Partitioned TCAMs
How to cite this article:

Huang Weiping and Xiao Jianyu, 2008. A New Data Structure and Algorithm for Static Slicing Concurrent Programs. Information Technology Journal, 7: 253-260.

DOI: 10.3923/itj.2008.253.260


09 June, 2009
Nico Kretz:
This paper looks very, very similar to 'Slicing Concurrent Programs' of Mangala Gowri Nanda and S. Ramesh, published at ISSTA 2000. (

Even the Figures are almost identical.




Curve Bottom