  Scaling a parallel program to modern supercomputers is challenging due to
inter-process communication, Amdahl's law, and resource contention. Performance
analysis tools for finding such scaling bottlenecks either base on profiling or
tracing. Profiling incurs low overheads but does not capture detailed
dependencies needed for root-cause analysis. Tracing collects all information
at prohibitive overheads. In this work, we design ScalAna that uses static
analysis techniques to achieve the best of both worlds - it enables the
analyzability of traces at a cost similar to profiling. ScalAna first leverages
static compiler techniques to build a Program Structure Graph, which records
the main computation and communication patterns as well as the program's
control structures. At runtime, we adopt lightweight techniques to collect
performance data according to the graph structure and generate a Program
Performance Graph. With this graph, we propose a novel approach, called
backtracking root cause detection, which can automatically and efficiently
detect the root cause of scaling loss. We evaluate ScalAna with real
applications. Results show that our approach can effectively locate the root
cause of scaling loss for real applications and incurs 1.73% overhead on
average for up to 2,048 processes. We achieve up to 11.11% performance
improvement by fixing the root causes detected by ScalAna on 2,048 processes.
