Από 306 ms σε 86 ms

Υλοποίησα το C = A × B για τετραγωνικούς πίνακες N × N απλής ακρίβειας σε CUDA C και το χρονομέτρησα από N = 128 έως 4096. Για N = 4096, καθένα από τα 16,8 εκατομμύρια στοιχεία του C είναι άθροισμα 4096 γινομένων.

Το πρώτο kernel ακολουθεί κατευθείαν τον ορισμό: ένα thread για κάθε στοιχείο του C, σε blocks των 16 × 16 threads. Κάθε thread διατρέχει τη γραμμή του A και τη στήλη του B στη global memory, την κύρια μνήμη της GPU.

Πώς χρονομετρήθηκε κάθε kernel

Χρονόμετρο

gettimeofday γύρω από μία εκτέλεση και το cudaDeviceSynchronize, άρα χωρίς τις αντιγραφές από τον host στην GPU

Δεδομένα

οι ίδιοι τυχαίοι πίνακες, από σταθερό seed, για όλα τα kernels, και ο C μηδενισμένος πριν από καθένα

Εκτελέσεις

μία συνεδρία στο Colab, μία χρονομετρημένη εκτέλεση ανά kernel και μέγεθος

Έλεγχος

το άθροισμα όλων των στοιχείων του C, σε διπλή ακρίβεια

Η πρώτη εκτέλεση της συνεδρίας, το naive kernel για N = 128, χρειάστηκε 0,159 s, περίπου 300 φορές τον χρόνο του για N = 256, και κάτι τέτοιο δεν ξανασυνέβη. Τη θεώρησα κόστος εκκίνησης και άφησα το N = 128 έξω από τις συγκρίσεις.

Δεν έκανα profiling στα kernels, οπότε αυτό το βήμα στηρίζεται στον κώδικα. Το naive kernel διαβάζει δύο τιμές από τη global memory για κάθε πολλαπλασιασμό και πρόσθεση: 8.192 αναγνώσεις για κάθε στοιχείο του C, για N = 4096.

Οι περισσότερες επαναλαμβάνονται. Τα 16 threads μιας γραμμής του block διαβάζουν την ίδια γραμμή του A, τα 16 μιας στήλης την ίδια στήλη του B, και το καθένα φέρνει το δικό του αντίγραφο. Δεν έπρεπε να αλλάξουν οι πράξεις, αλλά το από πού έρχονταν οι τιμές τους.

Δύο αλλαγές, με μέτρηση μετά από την καθεμία.

Tiling

Τα 256 threads ενός block αντιγράφουν ένα πλακίδιο 16 × 16 του A και ένα του B στη shared memory, τη γρήγορη μνήμη του chip που μοιράζονται, και περιμένουν σε ένα barrier. Κάθε thread κάνει 16 πολλαπλασιασμούς από τα πλακίδια πριν φορτωθεί το επόμενο ζεύγος. Κάθε τιμή που διαβάζεται εξυπηρετεί πλέον 16 threads: 512 αναγνώσεις από τη global memory ανά στοιχείο του C αντί για 8.192.

Μέτρηση για N = 4096: 306,0 ms σε 190,7 ms επιτάχυνση 1,6×

Register blocking

Κάθε thread υπολογίζει ένα μπλοκ 4 × 4 του C και κρατά τα 16 μερικά αθροίσματά του σε registers, την ταχύτερη μνήμη της GPU. Σε κάθε βήμα διαβάζει τέσσερις τιμές του A και τέσσερις του B από τη shared memory και πολλαπλασιάζει κάθε ζεύγος: 16 πολλαπλασιασμοί για 8 αναγνώσεις, εκεί που το tiled kernel έκανε 1 για 2.

Μέτρηση για N = 4096: 190,7 ms σε 86,1 ms επιτάχυνση 2,2×

Το kernel αυτό διπλασίασε επίσης τα πλακίδια σε 32 × 32 και μείωσε τα blocks σε 64 threads, κάτι που υποδιπλασιάζει ξανά τις αναγνώσεις από τη global memory, σε 256 ανά στοιχείο. Το 2,2× ανήκει σε αυτόν τον συνδυασμό, όχι μόνο στο register blocking. Και οι 16 φορές λιγότερες αναγνώσεις έδωσαν 1,6×, όχι 16×: δεν ήταν όλο το κόστος, και χωρίς profiler δεν μπορώ να πω ποιο ήταν το υπόλοιπο.

Αυτό που κρατώ: πριν αλλάξω κώδικα, βρίσκω από πού έρχεται κάθε τιμή, και μετρώ μετά από κάθε αλλαγή. Την επόμενη φορά θα άλλαζα ένα πράγμα τη φορά, ώστε το register blocking να έχει τη δική του μέτρηση, θα επαναλάμβανα κάθε χρονομέτρηση μετά από ένα warm-up, και θα έκανα profiling, ώστε ο συλλογισμός για τη μνήμη να γίνει μέτρηση.