Research On GPU-based Parallelization Method Of Large-scale Program Static Analysis

Static analysis refers to program analysis performed without running code.It is widely used in software engineering tasks such as compiler optimization and bug detection.In recent years,a lot of research work in this direction has been devoted to how to obtain enough information from the program code,fully express its syntax and semantic model,in order to accurately predict its behavior.However,with the widespread reuse of common components and the continuous expansion of software applications,the scale and complexity of modern software systems continue to increase.Performing high-precision static analysis of large-scale complex software systems,due to their huge data volume calculation,especially under the condition of limited resources,has become a difficult and hot topic that has received continuous attention.As a common device with parallel computing capability,GPUs are widely used in computationally intensive fields such as big data analysis and image processing.And attempts have been made to use GPUs to accelerate static analysis,but only for specific analysesAiming at the low efficiency and low scalability problem of large-scale high-precision static analysis in a single-machine environment,this paper proposes a GPU-based out-of-core static analysis algorithm,and implements a highly efficient and scalable static analysis system called GpuSpa.The main work of this paper is as follows1.Aiming at the problem of low efficiency,proposes a GPU-based parallelization method of static analysis,which defines a data structure suitable for GPU's unique execution mode and memory model-variable wide bit vector called VWBitVector to represent the program graph,and designs corresponding highly parallelized graph operations,converts static analysis problems into graph reachability problems,to achieve the parallelization of high-precision static analysis algorithms.2.Aiming at the problem of low scalability,proposes a disk-based partitioned out-of-core method.It designs a scheduling strategy based on pre-estimated calculation amount,divides the program graph into several partitions according to the available video memory,and schedules the partitions from disk to GPU as needed in the process of static analysis,to improve the scalability of the algorithm and reduce the overhead of data transmission as much as possible at the same time.3.Based on the above algorithm,a static analysis system based on GPU and disk is implemented,and 5 large open source software systems are selected as analysis objects and 2 related static analysis tools as comparison objects,a performance evaluation experiment is performed.The experimental results show that GpuSpa has good efficiency and scalability.