Approximating application performances in cloud data centers and simulated machines
Computing systems are ever-evolving and increasing in complexity. When incorporating new technologies into new computing systems, it is critical to ensure that these technologies are being used in a way that will maximize the efficiency of the applications to be executed in the new systems. Also we may be interested in predicting the performance of a system that incorporates a technology that does not yet exist. Predicting the performance of a new computing system is an on-going and challenging research area. In approximating the performances, applications characterization is widely used and it has proven to be a effective way to improve the performance of computing systems. For real-time systems, approximated application performances can be used to make better real-time decisions that can improve system performance, for example scheduling applications in cloud computing data centers. On the other hand, for systems that may not yet exist, simulators are commonly used to predict how an application would perform on such a system, unfortunately simulators are extremely slow. Sampled application simulation can be used to reduce the burden of simulation while still achieving high accuracy. This thesis presents cutting-edge research to better understand the application performances in these two important settings. The first setting uses application characterization and approximated performances to improve scheduling algorithms in cloud computing systems. We present a novel application characterization algorithm based on locality sensitive hashing (LSH), and we demonstrate that our technique is more accurate and faster than previous approaches. We then leverage this characterization approach into a scheduling algorithm for cloud computing data centers. This approach is also based on LSH, and we demonstrate that our scheduling algorithm is faster and results in higher quality-of-service and utilization than previous approaches. The second setting aims at decreasing the simulation time of applications by selecting simulation region samples for simulated machines. We use approximated application performances to measure the quality of the selected regions and measure the speedup gain in the simulation process. Here we used graph-matching based approach in finding equal-work regions and by using that result a new approximate sequence-alignment algorithm is applied on execution traces from the binaries to define intervals of semantically-equivalent work. This approach is able to mitigate the long interval lengths problem from the previous approaches, hence reduce the simulation time and have lower speedup error. While region selection is a mature area for single-threaded applications, it is still a challenge in case of multi-threaded applications. There is no existing work on this area to handle a multi-threaded application that uses any general synchronization such as lock, conditional variable, etc. This thesis proposes the first work to solve this issue. It starts with collecting a trace containing synchronizations. We build a happened-before graph and use a combination of the Max Flow algorithm and k-means clustering algorithm to compute a set of sampled regions. Our approach provides better simulation speedup while providing comparable accuracy in performance approximation compared to existing solution of this problem.