Cost Minimization for Heterogeneous Systems with Gaussian Distribution Execution Time

摘要

Time and cost are the most critical performance metrics for computer systems including embedded system, desktop, laptop, mainframe computer, and smart phone. In real world, the execution time may not be fixed and it usually follows Gaussian distribution. In this paper, we analyze how to minimize total cost while satisfying time constraints for heterogeneous systems with Gaussian execution time. This is called HAP-G (Heterogeneous Assignment with Probability - Gaussian) problem, which is a NP-complete problem. However, for simple path special cases, we find a polynomial-time optimal solution and propose the HAP-G-SP algorithm, and the experimental results show the effectiveness of our approach.