Finding probably best systems quickly via simulations

The performance of computer systems can in theory be optimized by selecting the system configuration having the best simulated performance. Unfortunately, it is often computationally intractable to estimate the performance of all system configurations accurately via simulation. We propose an algorithm for finding the best system configuration without estimating the performance of each system configuration accurately, so that the total simulation time is minimized. We prove that with high probability our algorithm finds the best system configuration. In addition, our algorithm has an advantage in that it only infrequently changes the system configurations to be simulated. Numerical experiments show that our algorithm improves upon existing algorithms with respect to the total simulation time and the frequency of changing the system configurations.