Program Execution Time Prediction Based On Program Instrumentation

Supercomputing systems are necessary tools for scientific computing. On the pur-pose of efficiently using these resources, predicting the execution time of parallel pro-grams becomes an importance work. Predicting parallel programs’ execution time can guide system users to apply computing resource properly, offer jobs schedulers basis to do better and solve some other problems during the operation of supercomputing systems.Program Instrumentation is a effective and mature technology widely used in pro-gram testing and program monitoring. This technology can extract features relevant to program’s source code and logic, so we can use the extracted features as input of a predicting model while the output of the model is the corresponding execution time of the same program. In this thesis, we present a method to predict the execution time of parallel programs based on program instrumentation. The main contributions of this thesis are as listed below:1. This thesis implement a toolset to instrument C/C++ parallel programs and extract features (branches, loops and variable values etc.) from instrumented programs.2. This thesis propose a procedure to filtrate these features and control the probe effect by filtrate features according to its’ timestamp and importance in prediction model. After these filtrations, the probe effect caused by probe codes can be controled at about 1%. This makes our work practically valuable.3. A prediction model of which the input is observed value of features and the out-put is the corresponding execution time using filtrated features is established at the end of our method using some frequently-used methods. Also, the method proposed in this thesis are experimented and analysised.Our method is experimented with two programs: Graph500 and GalaxSee at the end of this work. The results show that when the model is random forest and the input features are polynomial expanaded, our method achieves average prediction errors of 12.76% and 16.62% while the median errors are 3.15% and 6.88% accordingly with 1600 training records and 400 test records which is fairly good to put into practice.