4 ms·

Oh, so I just noticed the "Whitepaper" link, and that has lots more good info in (I wish the blog post was the whitepaper!). So does Pareon depend on running a

Oh, so I just noticed the "Whitepaper" link, and that has lots more good info in (I wish the blog post was the whitepaper!). So does Pareon depend on running an instrumented build? If so, wouldn't you need a sample data file (map, demo, whatever) that covers 100% of branches and dependencies in order to know for absolutely sure that there are no dependencies between code. Could you make a huge SSA of the program and determine dependencies that way (more of a reality now that we have 64bit desktops and GCC has "whopr" and friends)?

pascal_cuoq 14y ago
> If so, wouldn't you need a sample data file (map, demo, whatever) > that covers 100% of branches and dependencies in order to know > for absolutely sure that there are no dependencies between code. I am curious about that too. Even 100% statement coverage does not guarantee that you have discovered all dependencies. Think “array of pointers”. You may have good enough coverage to execute once the statement that gets a pointer from the array, but it does not mean that different values do not result in other pointers that create dependencies where you haven't seen any. I think this is why they call it “semiautomatic”. The tool hints at what looks parallelizable. The user takes responsibility for the changes. > Could you make a huge SSA of the program and determine > dependencies that way The difficulty with just C is not so much multiple assignments to the same memory locations, but everything else, including the pervasive reliance on pointers. C++ adds several abstractions on top of that that do not make it easier to statically tell what the program may do. There are whole-program static analyzers whose results can be used to resolve pointers and get useful dependencies on medium-sized C programs. I work on one: http://frama-c.com/try_out.html http://frama-c.com/try_out.html
- wladimir 14y ago
  A big part of the problem is trying to do this with C in the first place. The explicit memory operations create an extreme complexity in reasoning about a program exhaustively, not far from analyzing generic binary code. C is so permissive to be overkill for a lot of applications. Would this be more tractable with safer programming languages that avoid "wild" pointers, such as Rust? Or maybe by extending the C syntax so that the programmer can give hints to the compiler what he means, instead of what he has written so that the compiler can detect mismatches? BTW props on Frama-C, it's incredible what you guys are doing.
- fons 14y ago
  The new followup post [1] explains that Pareon indeed partly relies on good coverage: "Regarding the way Pareon performs its analysis: it relies on instrumentation and therefore coverage is key. The parts of the code of interest should be sufficiently covered. Partly it is the user's responsibility to make sure the right data sets are used. However Pareon helps the user by showing the achieved coverage of the parts you want to parallelize." [1] http://www.vectorfabrics.com/blog/item/accelerating_the_idtech_4_engine_with_pareon_a_follow_up http://www.vectorfabrics.com/blog/item/accelerating_the_idte...

pascal_cuoq 14y ago

> If so, wouldn't you need a sample data file (map, demo, whatever) > that covers 100% of branches and dependencies in order to know > for absolutely sure that there are no dependencies between code. I am curious about that too. Even 100% statement coverage does not guarantee that you have discovered all dependencies. Think “array of pointers”. You may have good enough coverage to execute once the statement that gets a pointer from the array, but it does not mean that different values do not result in other pointers that create dependencies where you haven't seen any. I think this is why they call it “semiautomatic”. The tool hints at what looks parallelizable. The user takes responsibility for the changes. > Could you make a huge SSA of the program and determine > dependencies that way The difficulty with just C is not so much multiple assignments to the same memory locations, but everything else, including the pervasive reliance on pointers. C++ adds several abstractions on top of that that do not make it easier to statically tell what the program may do. There are whole-program static analyzers whose results can be used to resolve pointers and get useful dependencies on medium-sized C programs. I work on one: http://frama-c.com/try_out.html http://frama-c.com/try_out.html

wladimir 14y ago
A big part of the problem is trying to do this with C in the first place. The explicit memory operations create an extreme complexity in reasoning about a program exhaustively, not far from analyzing generic binary code. C is so permissive to be overkill for a lot of applications. Would this be more tractable with safer programming languages that avoid "wild" pointers, such as Rust? Or maybe by extending the C syntax so that the programmer can give hints to the compiler what he means, instead of what he has written so that the compiler can detect mismatches? BTW props on Frama-C, it's incredible what you guys are doing.
fons 14y ago
The new followup post [1] explains that Pareon indeed partly relies on good coverage: "Regarding the way Pareon performs its analysis: it relies on instrumentation and therefore coverage is key. The parts of the code of interest should be sufficiently covered. Partly it is the user's responsibility to make sure the right data sets are used. However Pareon helps the user by showing the achieved coverage of the parts you want to parallelize." [1] http://www.vectorfabrics.com/blog/item/accelerating_the_idtech_4_engine_with_pareon_a_follow_up http://www.vectorfabrics.com/blog/item/accelerating_the_idte...