M.Sc Thesis


M.Sc StudentShomroni Uri
SubjectPerformance Prediction of Programs on Heterogeneous and
Massively-Parallel Architectures
DepartmentDepartment of Computer Science
Supervisor PROF. Avi Mendelson
Full Thesis textFull thesis text - English Version


Abstract

Massively parallel, throughput-oriented processors are becoming increasingly common. Maximizing the benefit of these processors requires algorithms to be implemented differently than the sequential algorithms. This change is often very time consuming and is not guaranteed to provide good enough of a return on investment (ROI) in performance compared to the effort it will take. Most programmers do not have a clear view or estimate of when and how much would a program benefit from being ported to a parallel system, what considerations to apply when porting the programs, the effects of choices such as data ordering on the performance of parallel algorithms, and so forth.


This thesis proposes an approach to predicting the performance gain from porting a program from the CPU to the GPU, based on the characterization of the program, as measured by performance counters when being executed on the CPU only. The method calls to feed these measurements to a simple machine learning model trained on a given set of benchmarks, predicting the speedup.

The experiments show that the predictions’ accuracy is similar or better than existing methods, that usually require putting in the effort of converting the algorithm as a starting point. With the application of machine learning algorithms, measurements of CPU performance counters have shown a fairly good prediction of the logarithm of the GPU speedup value (within x1/3 - x3 of the actual value for most benchmarks). Comparison of the predictions against thresholds has shown over 80% prediction accuracy for all thresholds examined in all experiments. The sample set was also verified to not provide false positive results by performing the experiments with other value transformations that yielded much lower accuracy.