BB-CVXOPT: Basic Block Execution Count Estimation and Extrapolation Using Constrained Convex Optimization

Program execution time often scales with input size, making performance prediction without execution valuable if the model is efficient and scalable. While machine learning has been used for such predictions, we propose using Constrained Convex Optimization at the finer Basic Block (BB) level. Our BB-CVXOPT system models program performance by breaking down a target program into BBs and using a numerical solver to generate polynomial equations for each BB, based on input size. These equations predict BB execution counts, which can then estimate runtime when multiplied by BB execution times for a given system. BB-CVXOPT is architecture-independent, achieving error rates as low as 1.39e-16 and MAPE below 1.0e-07 for the largest 30% of the dataset, and a MAPE of 1.30e-03 for 65% of the dataset.