FlowProf: Profiling Multi-threaded Program Performance using Information-Flow.

Amdahl's law implies that even small sequential bottlenecks can seriously limit the scalability of multi-threaded programs. To achieve scalability, developers must painstakingly identify sequential bottlenecks in their program and attempt to eliminate these bottlenecks by either changing synchronization strategies or rearchitecting and rewriting code with sequential bottlenecks. This can require significant effort by the developer to understand the best approach to address sequential bottlenecks.We bring a new tool, information flow, to the problem of understanding sequential bottlenecks. Information flow is powerful in that it helps developers understand whether a bottleneck is fundamental to the computation, or merely an artifact of the implementation. We combine information flow with field conflict analysis to help developers understand the limits and potential benefits of eliminating sequential bottlenecks through redesigning the locking strategy. Finally, we develop schedule impact analysis to help understand the potential impacts of optimizations before implementing them. We develop an implementation of this in FlowProf. We have evaluated FlowProf on a set of multi-threaded Java applications and manually examined the code to validate FlowProf's findings