Computational statistics and GPU acceleration

Abstract

Η πρακτική εφαρμογή σύγχρονων στατιστικών μεθόδων καθίσταται συχνά υπολογιστικά απαγορευτική, λόγω του διαρκώς αυξανόμενου όγκου των δεδομένων και της πολυπλοκότητας των μοντέλων. Η παρούσα εργασία εξετάζει πώς η επιτάχυνση μέσω Μονάδων Επεξεργασίας Γραφικών (GPU) μπορεί να διευρύνει το πεδίο εφαρμογής τέτοιων μεθόδων. Η εργασία δομείται σε τρεις άξονες: (1) τη θεωρητική ανάλυση των υπολογιστικών «σημείων συμφόρησης» σε δύο ευρέως διαδεδομένες αλλά και εξαιρετικά απαιτητικές μεθόδους, τις Μεθόδους Πυρήνα (Kernel Methods) και το Gradient Boosting, καθώς και του αλγοριθμικού ανασχεδιασμού που απαιτείται για την αποδοτική τους εκτέλεση σε GPU, (2) την εμπειρική επικύρωση των δυνητικών κερδών απόδοσης, μέσω της συγκριτικής αξιολόγησης δύο βιβλιοθηκών λογισμικού αιχμής σε GPU, των Falkon και XGBoost, έναντι των αντίστοιχων υλοποιήσεών τους σε CPU, ποσοτικοποιώντας την επιτάχυνση σε πραγματικά σύνολα δεδομένων, και (3) την επισκόπηση των πλαισίων λογισμικού που καθιστούν εφικτές τέτοιες υλοποιήσεις, χρησιμοποιώντας ως ενδεικτική μελέτη περίπτωσης την υλοποίηση ενός μαζικά παράλληλου δειγματολήπτη Markov Chain Monte Carlo (MCMC) σε CUDA. Τα αποτελέσματα καταδεικνύουν ότι η επίτευξη σημαντικών κερδών απόδοσης σε ευρέως διαθέσιμο υλικό GPU είναι εφικτή χωρίς καμία ουσιαστική απώλεια στατιστικής ακρίβειας, υπό την προϋπόθεση ότι οι αλγόριθμοι έχουν ανασχεδιαστεί ώστε να αξιοποιούν αποδοτικά τον παραλληλισμό και τις ιεραρχίες μνήμης. Γενικότερα, τα ευρήματα τεκμηριώνουν ότι η κλιμακωσιμότητα μεθόδων στατιστικής αποτελεί πρόβλημα τόσο μηχανικής λογισμικού, όσο και μεθοδολογίας: ο ανασχεδιασμός του αλγορίθμου, η δομή των δεδομένων, και η αρχιτεκτονική του υλικού απαιτούν συνδυαστική αντιμετώπιση. Προχωρώντας από τη θεωρία στην εμπειρική τεκμηρίωση και, τέλος, στην τεχνολογία της υλοποίησης, η παρούσα εργασία στοχεύει να γεφυρώσει το χάσμα μεταξύ της προηγμένης στατιστικής μοντελοποίησης και της υπολογιστικής υψηλών επιδόσεων, παρέχοντας τα εφόδια όχι μόνο για την αξιοποίηση των GPU, αλλά και για τη συνεισφορά στο ταχέως αναπτυσσόμενο αυτό πεδίο.

Modern statistical methods often become computationally prohibitive as data volumes and model complexity grow. This thesis examines how Graphics Processing Unit (GPU) acceleration can expand the practical scale of such methods. We organize the work around three components: (1) a theoretical analysis of computational bottlenecks in two widely-used but immensely intensive methods, Kernel Methods and Gradient Boosting, and the algorithmic redesign required for efficient GPU execution; (2) an empirical validation of the potential performance gains by benchmarking two state-of-the-art, GPU-accelerated libraries, Falkon and XGBoost, against CPU-based baselines on real-world datasets to quantify speedups and assess effects on predictive accuracy; and (3) an implementation-oriented overview of the enabling software frameworks, developing a massively parallel Markov Chain Monte Carlo (MCMC) sampler in CUDA as an illustrative case study. Results indicate that substantial performance gains are attainable on commodity GPU hardware with no material loss in statistical accuracy when algorithms are reformulated to exploit fine-grained parallelism and memory hierarchies. More broadly, the findings underscore that scalability in statistics is as much an engineering problem as it is a methodological one: algorithm design, data layout, and hardware architecture must be considered jointly. By moving from theory, to empirical evidence, to the underlying engineering, this thesis aims to bridge the gap between advanced statistical modelling and high-performance computing, and provides the tools to not only leverage but also contribute to this expanding field.