A computer executed parallel program scalability bottleneck detection method is provided, which includes: building a program structure graph for a program source code; collecting performance data based on a sampling technique during runtime; the performance data including: performance data of each vertex of the program structure graph and inter-process communication dependence of communication vertices; building a program performance graph by filling the program structure graph with the collected performance data, the program performance graph recording data and control dependence of each process as well as inter-process communication dependence; detecting problematic vertices from the program performance graph, and starting from some or all of the problematic vertices, backtracking through data/control dependence edges within a process and communication dependence edges between different processes, to detect scalability bottleneck vertices.