[Soot-list] How can I retrieve the read/write access sets of a statement?

[Will Benton]

On Jun 8, 2010, at 11:51 AM, Jochen Huck wrote:

> I'd like to create a new thread for each method call if it is safe to do so.

Hi Jochen,

You might be interested in my VMCAI 2009 paper "Mostly-functional behavior in Java programs,"[1] which describes an efficient and useful analysis related to purity analysis.  Unfortunately, the code is not available for this analysis (it was implemented in a special framework that used Soot and prolog cooperatively; this framework is not currently compatible with contemporary Soot releases), but it should be fairly straightforward to implement in Soot directly.  You might also be interested in my doctoral dissertation, _Fast, effective program analysis for object-level parallelism_[2], which includes references to a great deal of related work (in chapter 2), a more detailed presentation of the aforementioned analysis (in Chapter 4), and an evaluation of the runtime possibilities for automatically parallelizing methods on Java objects (in Chapter 5).

In case you don't want to read a bunch of prose, here's a summary of the most relevant parts (spoiler alert!):  while a lot of people have shown good results finding parallelism out of obviously parallel programs (e.g. matrix multiplication, the Olden benchmarks, etc.) it will likely require heroic analysis and runtime-hacking effort to see worthwhile speedups on interesting, idiomatic Java programs.  The methods that you can obviously execute in parallel are very small and don't necessarily have a lot of slack between invocation and result use.  With more aggressive runtime support you can use an unsound analysis that will identify more possible candidate methods, but that has its own (engineering and runtime) costs.  

There are a lot of issues here, and each is worthy of its own investigation:  How do you spawn off parallel tasks?  (surely you don't want to just create a new java.lang.Thread!)  How do you model costs, load-balance, and make scheduling decisions?  How do you deal with open programs or reflection?[3]  Precisely what does "safe to execute in parallel" mean, and what approximations of this are useful?

If this area is interesting to you, I suspect that you would be more profitably served at this point in history by devising some execution model that can schedule some restricted subset of Java methods in parallel, implementing efficient runtime support for this, defining some programmer-specified annotations to indicate that methods should be executed in parallel, and then implementing analyses and transformations to ensure that methods that are marked for parallel execution actually can be guaranteed to meet the restrictions of your model.  Any two or three of these problems probably constitutes a couple of years of good work.

I'm happy to chat with you more about this off-line.




best,
wb

[1]  http://pages.cs.wisc.edu/~willb/papers/benton-vmcai09.pdf
[2]  http://web.willbenton.com/research/dissertation
[3]  For inspiration on these two questions, see Naik, Aiken, and Whaley in PLDI 06 and Eric Bodden's TamiFlex tool, respectively.

--
William C. Benton
http://www.cs.wisc.edu/~willb/