Bina Histogram

Histogram mengira bilangan input yang jatuh ke dalam setiap bin. Banyak utas akan cuba menokok bin yang sama, jadi ini ialah masalah operasi atom. 📊

Setiap utas membaca satu elemen, mencari binnya dan menokok bin tersebut. Tanpa perlindungan, bin yang popular kehilangan kiraan akibat perlumbaan.

Penyelesaian betul yang paling mudah ialah satu atomicAdd bagi setiap elemen terus ke memori global. Ia berfungsi, tetapi bin yang sibuk menyebabkan utas dilaksanakan secara bersiri.

Apabila data terkumpul dalam beberapa bin, ribuan utas bertumpu pada alamat yang sama. Persaingan itu boleh menjadikan operasi atom global amat perlahan.

Penswastaan memberikan setiap blok histogram peribadinya sendiri dalam memori dikongsi yang pantas. Utas hanya bertembung dalam blok masing-masing, bukan di seluruh grid.

Setiap blok mengisytiharkan tatasusunan dikongsi yang saiznya mengikut bilangan bin. Tatasusunan ini berada pada cip, jadi operasi atom di situ jauh lebih murah berbanding operasi global.

Utas mengosongkan histogram dikongsi secara bekerjasama, kemudian memanggil __syncthreads supaya tiada utas mengira sebelum proses mengosongkan selesai.

Kini setiap utas menaikkan bin masing-masing secara atom dalam memori dikongsi. atomicAdd yang sama digunakan, tetapi pada salinan pantas pada cip dan bukannya salinan global.

Selepas sekatan, utas menambah setiap bin dikongsi ke dalam histogram global dengan satu atomicAdd bagi setiap bin. Jauh lebih sedikit operasi atom global berbanding sebelumnya.

Operasi atom pada memori dikongsi adalah pantas, dan operasi atom global yang mahal kini berlaku sekali bagi setiap bin bagi setiap blok, bukannya sekali bagi setiap elemen.

Histogram peribadi mesti muat dalam memori dikongsi. Jika terdapat terlalu banyak bin, bahagikannya kepada beberapa laluan atau kembali menggunakan operasi atom global.

Anda membina histogram dengan operasi atom global, kemudian mempercepatkannya menggunakan penswastaan memori dikongsi: kosongkan, kira secara tempatan dan cantumkan. ✅