Fast convolution algorithms
Creators: name: Γιαννακέρης, Παναγιώτης Παρμενίωνα
Publisher: name: Aristotle University of Thessaloniki
Year: 2020
Subjects: Κυκλική συνέλιξη Winograd
Αλγόριθμος φωλιάς συνελίξεων
Πολυωνυμικός μετασχηματισμός
Winograd cyclic convolution
Nested convolutions
Polynomial transform

description: Modern machine learning and computer vision research rely heavily on deep learning techniques, and particularly in Convolutional Neural Networks, to carry out heavy-duty tasks, such as object detection, face recognition, activity detection and object tracking, to name a few. The convolution operation lies at the heart of those calculations, performed at various scales of hardware environments, from mobile phones and autonomous embedded systems, to huge cloud GPU clusters. In recent years, the increasing capabilities of graphics processing hardware, which are tailored to maximize paralellization performance, and posses dozens of Gigabytes of memory and teraflops of computing power, even on devices made for personal use, have made the practice of training and testing huge CNN models a common task at hand, in most most of today's image and video processing research projects. In parallel, fast convolution implementations, in widely used proprietary or open-source libraries, have made the processing of huge amounts of data, attainable with very low latency, even for the average home user on top of fairly inexpensive GPUs. Older techniques, like the Fast Fourier Transform, are well suited on large images and filters, but they prove inadequate to capitalize any advantage when the conventional small-sized kernels, i.e. 3×3, 5×5, or 7×7, used in modern CNNs are concerned. There is a very promising class of fast convolution algorithms, initially proposed by Winograd, which are proven to achieve minimal multiplicative complexity, and are gaining traction in recent years. Winograd's algorithms have already been implemented in popular deep learning frameworks and libraries. In this work, a systematic theoretical foundation for this class of algorithms is established, along with the exploration of the characteristics of other types of fast convolution algorithms, which follow similar principles, such as those based on polynomial transforms, as well as nesting algorithms, which exploit small size fast Winograd convolutions, so as to construct convolutions of larger size, with sub-optimal complexity, in cases where the Winograd methodology becomes very hard to follow in a non automated way.
description: Οι σύγχρονοι τομείς της μηχανικής μάθησης και όρασης υπολογιστών βασίζονται σε μεγάλο βαθμό στις τεχνικές βαθιάς μάθησης, και ιδιαίτερα στα συνελικτικά νευρωνικά δίκτυα, για την εκτέλεση απαιτητικών εργασιών, όπως η ανίχνευση αντικειμένων, η αναγνώριση προσώπων, η ανίχνευση δραστηριότητας και η παρακολούθηση αντικειμένων, για να αναφέρουμε μερικές. Η πράξη της συνέλιξης βρίσκεται στο επίκεντρο αυτών των υπολογισμών, και πραγματοποιείται σε διάφορες κλίμακες, από κινητά τηλέφωνα, φορητές συσκευές και αυτόνομα ενσωματωμένα συστήματα, έως μεγάλα υπολογιστικά νέφη. Τα τελευταία χρόνια, οι αυξανόμενες δυνατότητες του υλικού επεξεργασίας γραφικών, το οποίο σχεδιάζεται με γνώμονα τη μεγιστοποίηση της απόδοσης της παραλληλοποίησης υπολογισμών, προσφέροντας δυνατότητες δεκάδων Gigabyte μνήμης και teraflops υπολογιστικής ισχύος, ακόμη και σε συσκευές κατασκευασμένες για προσωπική χρήση, έχουν κάνει την πρακτική της εκπαίδευσης και δοκιμής περίτεχνων αρχιτεκτονικών συνελικτικών νευρωνικών δικτυών ευρέως διαδεδομένη σε μεγάλη κλίμακα στον τομέα της επεξεργασίας εικόνας και βίντεο. Παράλληλα, οι γρήγορες υλοποιήσεις, σε ευρέως χρησιμοποιούμενες βιβλιοθήκες λογισμικού, κατέστησαν δυνατή την επεξεργασία τεράστιων όγκων δεδομένων, με πολύ χαμηλή καθυστέρηση, ακόμη και για τον μέσο οικιακό χρήστη. Παλαιότερες τεχνικές, όπως ο γρήγορος μετασχηματισμός Fourier, είναι αποδοτικές ιγα μεγάλα μήκη συνελίξεων, αλλά αποδεικνύονται ανεπαρκή για τα συμβατικά φίλτρα μικρού μεγέθους, όπως 3x3, 5x5, ή 7x7, που χρησιμοποιούνται στα σύγχρονα συνελικτικά νευρωνικά δίκτυα. Υπάρχει μια πολλά υποσχόμενη κατηγορία αλγορίθμων γρήγορων συνελίξεων, που προτάθηκε αρχικά από τον Winograd, οι οποίοι αποδεικνύεται ότι επιτυγχάνουν ελάχιστη πολλαπλασιαστική πολυπλοκότητα, και κερδίζουν έδαφος τα πρόσφατα χρόνια. Οι αλγόριθμοι του Winograd έχουν ήδη εφαρμοστεί σε δημοφιλείς βιβλιοθήκες λογισμικού βαθιάς μάθησης. Σε αυτή την εργασία, παρουσιάζεται συστηματικά μια θεωρητική βάση για αυτήν την κατηγορία των αλγορίθμων, ταυτόχρονα με την εξερεύνηση των χαρακτηριστικών άλλων τύπων αλγορίθμων γρήγορων συνελίξεων, που ακολουθούν παρόμοιες αρχές, όπως αυτές που βασίζονται σε πολυωνυμικούς μετασχηματισμούς, καθώς και αλγόριθμους φωλιάς, κατά τους οποίους γρήγορες συνελίξεις Winograd μικρής διάστασης συνθέτουν συνελίξεις μεγαλύτερου μήκους, με υπο-βέλτιστη πολυπλοκότητα, σε περιπτώσεις όπου η μεθοδολογία Winograd γίνεται πολύ δύσκολο να ακολουθηθεί με μη αυτοματοποιημένο τρόπο.