Μελέτη ακρίβειας και ευστάθειας αλγορίθμων ομαδοποίησης σε αριθμητική κινητής υποδιαστολής

• Κύριος συγγραφέας: Αναγνώστου, Γεώργιος
• Άλλοι συγγραφείς: Γαλλόπουλος, Ευστράτιος
• Μορφή: Thesis
• Γλώσσα: Greek
• Έκδοση: 2020
• Θέματα: Ομαδοποίηση; Μισή ακρίβεια; Ευστάθεια; Κινητή υποδιαστολή; Ακρίβεια; Ανάλυση δεδομένων; Clustering; Half - precision; Stability; Floating point; Accuracy; Data analysis

Στις σύγχρονες εφαρμογές που βασίζονται σε αλγορίθμους ανάλυσης δεδομένων, όπως η ομαδοποίηση, έχει γίνει απαραίτητη η χρήση πόρων της υπολογιστικής υψηλών επιδόσεων (high performance computing ή ΗPC), καθώς οι κλίμακες των προβλημάτων έχουν αυξηθεί δραματικά. Πρόσφατες αρχιτεκτονικές υπολογιστικών μονάδων προσφέρουν εξαιρετικά υψηλές επιδόσεις στους υπολογισμούς, ιδιαίτερα αν οι εφαρμογές είναι ανεκτικές ως προς τα σφάλματα που υπάρχουν σε αυτούς. Αυτό επιτυγχάνεται με την υλοποίηση στις σύγχρονες αυτές υπολογιστικές μονάδες, αριθμητικής κινητής υποδιαστολής μειωμένης ακρίβειας και τη χρήση της αποκλειστικά ή σε μέρος των εφαρμογών. Επομένως, καθίσταται κρίσιμη η διερεύνηση των χαρακτηριστικών των αλγορίθμων και της επίδρασης των αριθμητικών σφαλμάτων στα αποτελέσματα που υπολογίζουν. Η παρούσα Διπλωματική Εργασία συνεισφέρει σ' αυτήν την κατεύθυνση διερευνώντας ορισμένους αλγορίθμους ομαδοποίησης και τη λειτουργία τους χρησιμοποιώντας προσομοιώσεις αριθμητικής μισής ακρίβειας (half precision arithmetic) σε περιβάλλον MATLAB. Αρχικά, γίνεται μία επισκόπηση της αριθμητικής κινητής υποδιαστολής, των υλοποιήσεων της μισής ακρίβειας σε κάρτες γραφικών νέων αρχιτεκτονικών, καθώς και μία συζήτηση για τη χρήση μεικτής ακρίβειας σε υπολογισμούς και των εργαλείων προσομοίωσης αριθμητικής μισής ακρίβειας σε MATLAB. Στη συνέχεια, επιχειρείται μία ειδική επέκταση της έννοιας της πίσω ευστάθειας (backward stability) για αλγορίθμους ομαδοποίησης καθώς και διερεύνηση της ευαισθησίας των αποτελεσμάτων ως προς ορισμένες αλλαγές στα δεδομένα. Η εργασία εστιάζει σε τρεις αλγορίθμους ομαδοποίησης. Αυτοί είναι ο ιεραρχικός διαιρετικός αλγόριθμος PDDP, ο διαχωριστικός αλγόριθμος K-means και ο υβριδικός αλγόριθμος PDDP-2means. Η μελέτη της πίσω ευστάθειας των αλγορίθμων πραγματοποιείται με την προσομοίωση αριθμητικής μισής ακρίβειας σε απευθείας σύγκριση με την εκτέλεσή τους σε αριθμητική διπλής ακρίβειας. Επιπλέον, επεκτείνεται μέσω του συνδυασμού της αριθμητικής μειωμένης ακρίβειας και της εναλλαγής συνθηκών αρχικοποίησης των αλγορίθμων. Τα αποτελέσματα προκύπτουν μέσα από μία σειρά πειραμάτων και ακολουθεί η αξιολόγησή τους και η καταγραφή συμπερασμάτων. Δεδομένου ότι η εν λόγω ακρίβεια έχει εισαχθεί στο πρότυπο IEEE 754-2008 ως binary-16 και υλοποιείται σε πρόσφατες κάρτες γραφικών όπως τα V100 και T4 της NVIDIA, που στοχεύουν σε εφαρμογές ανάλυσης δεδομένων και τεχνητής νοημοσύνης, η παρούσα εργασία αναμένεται να διευκολύνει τη μελέτη της επίδοσης και ακρίβειας αλγορίθμων στα εν λόγω συστήματα.