=> Karakteristik
Parallel Reduction yaitu pentingnya data umum dalam parallel
sederhana(primitive). Parallel Reduction mudah di implementasikan dalam
CUDA,namum sulit untuk melakukannya dengan benar. Parallel Reduction melayani
optimasi yang besar contohnya kita akan menjalankan langkah demi langkah
melalui 7 versi yang berbeda dan menunjukan beberapa strategi optimasi penting.
=) CONTOH
Reduksi
secara paralel dapat digambarkan dengan pohon biner. Sekelompok n nilai
ditambahkan dalam langkah penambahan paralel.
Parallel reduction
•
Implementasi algoritma penjumlahan, setiap node dari pohon merupakan elemen
dalam array.
+_+
Kelebihannya
:
=) Parallel
Reduction mampu untuk menggunakan beberapa blok thread contohnya yaitu mampu
memproses array yang sangat besar, untuk menyimpan semua multiprocessor pada
GPU yang sibuk dan setiap blok thread akan mengurangi sebagian dari array.
=) Masalah dalam
Prallel Reduction adalah sinkronisasi global (Global Synchronization). Jika
kita bisa melakukan sinkronisasi di semua blok thread, maka dengan mudah kita
dapat mengurangi array yang sangat besar. Hal tersebut dapat dilakukan dengan
cara mensinkronisasi global setelah masing-masing blok menghasilkan hasil atau
output, setelah semua blok telah tersinkronisasi maka lanjutkan rekursif.
+-+
Kekurangannya
:
=) Cuda tidak
memiliki global sinkronisasi karena mahal untuk membangun sebuah hardware untuk
GPU dengan jumlah prosesor yang tinggi, dan akan memaksa programmer untuk
menjalankan sedikit blok ( tidak lebih dari # multiprocessors * # resident blocks / multiprocessor) umtuk menghindari
kebuntuan yang dapat mengurangi efisiensi keseluruhan.
- Peluncuran kernel berfungsi sebagai titik sinkronisasi global.
- Peluncuran kernel mengabaikan hardware overhead dan software overhead
yang rendah.
Optimasi
Solusi untuk Meningkatkan Kinerja Paralel Pengurangan Fungsi algorithmic di
CUDA
=)Menggunakan analisis mendalam tentang buku pemrograman CUDA
dan praktek-praktek terbaik digambarkan dalam literatur [2], [3], [4], [5], [6]
untuk mengembangkan aplikasi yang sukses di CUDA, kami telah mengidentifikasi
dan mengembangkan serangkaian
solusi optimasi untuk pengurangan paralel fungsi algoritmik.Solusi utama optimasi yang kami telah dikembangkan dan
diterapkan, aspek sasaran mengenai: memanfaatkan GPU, kinerja AOS, penggunaan
optimal bandwidth memori bersama, kemungkinan sinkronisasi, kerjasama yang
efisien antara GPU dan CPU.
=) Berikut
ini kita akan menjelaskan solusi dan pengembangan progresif yaitu :
o Solusi 1 - The interleaved teknik pengalamatan.
Dengan menggunakan teknik ini, kita
telah menginstruksikan pertama setiap thread untuk memuat satu elemen dari
memori global ke dalam memori bersama.Kami kemudian dilakukan tahap penurunan
memori bersama (itu memiliki keuntungan dari throughput yang tinggi) dan hasil
yang diperoleh dimuat kembali ke memori global. Kami telah menemukan bahwa
teknik ini memiliki kelemahan menghasilkan warps berbeda di mana benang tidak
memproses tugas yang sama. Ini warps tidak efisien dalam tahap reduksi karena
mereka memperlambat pengolahan data, karena itu, kami telah memutuskan untuk
mengelola divergen percabangan dalam rangka meningkatkan kinerja.
o Solusi
2 - Menghindari divergen percabangan.
Kami telah
menghilangkan keterbatasan yang disebutkan di atas dan kami telah meningkatkan
kinerja dengan mengganti divergen bercabang dengan yang non-divergen
menggunakan pengindeksan langsung untuk setiap elemen dari vektor input yang
akan berkurang. Teknik ini telah
menghilangkan warps berbeda, tetapi dihasilkan bersama bank konflik memori
karena beberapa permintaan dari memori bank yang sama, bahwa kita harus
mengelola menggunakan teknik pengalamatan berurutan.
o Solusi
3 - sekuensial teknik pengalamatan.
Kami telah
menggunakan benang, Aos pengindeksan bukannya pengindeksan langsung untuk
mengelola shared konflik bank memori. Meskipun kami telah memperoleh perbaikan
yang signifikan mengenai waktu eksekusi dan bandwidth, kami telah mengamati
bahwa optimasi lebih lanjut masih mungkin sebagai GPU, sumber daya AOS tidak
sepenuhnya bekerja. Ketika masing-masing benang beban elemen dari memori global
ke dalam memori bersama, setengah dari benang dalam blok tetap siaga. Oleh
karena itu, untuk memecahkan situasi ini, kami telah memutuskan untuk melakukan
pengurangan memori global sebelum memuat data dalam memori bersama.
o Solusi 4 - Melakukan pengurangan data yang disimpan dalam
memori global sebelum loading ke dalam memori bersama.
Solusi ini memecahkan kelemahan dari
teknik pengalamatan sekuensial dan membawa perbaikan kinerja yang signifikan.Bahkan jika bandwidth meningkat pesat, optimasi lebih
lanjut masih dapat dicapai.Fungsi pengurangan tidak melibatkan upaya
komputasi meningkat tetapi jumlah besar operasi sinkronisasi yang diperlukan
menyebabkan hukuman kinerja.Untuk mengatasi
hukuman ini kami telah meminimalkan jumlah instruksi dieksekusi.
o Solusi
5 - Meminimalkan jumlah instruksi dieksekusi.
Paralel
pengurangan fungsi algoritmik yang kami kembangkan adalah berguna untuk
multicore arsitektur seperti SIMD (Instruksi Single, Multiple Data), di mana
instruksi kasus yang sinkron dalam setiap warp. Kami telah memperhatikan bahwa,
sebagai proses reduksi berlangsung, jumlah thread aktif menurun, dan ketika
jumlah thread kurang dari atau sama dengan 32, hanya warp lalu tetap akan
dieksekusi. Dalam warp ini kita
tidak harus melakukan sinkronisasi atau untuk memvalidasi benang, Ao indeks
lagi. Akibatnya, kami telah memutuskan untuk
menghapus instruksi ini untuk mendapatkan peningkatan kinerja secara
keseluruhan dan untuk meminimalkan sebanyak mungkin jumlah operasi
sinkronisasi.
o Solusi 6 - Pengolahan beberapa elemen per thread.
Dengan mengurangi beberapa elemen per thread
selama sama langkah pengurangan (8 elemen untuk GTX280, GTX480 16 elemen untuk
elemen dan 512 untuk GTX680), kita telah mendapatkan peningkatan kinerja yang
cukup untuk fungsi algoritmik reduksi.
o Solusi 7 - Decomposing fungsi pengurangan beberapa yang lebih
kecil, dalam rangka mencapai sinkronisasi global.
Setelah
setiap langkah reduksi, blok benang harus antar-mengkomunikasikan hasil parsial
mereka, jadi kami harus menyinkronkannya. Tapi
dalam CUDA secara teknis tidak mungkin untuk secara langsung global
sinkronisasi, jadi kami telah memutuskan untuk menguraikan fungsi pengurangan
menjadi beberapa fungsi kernel yang lebih kecil.Setiap panggilan fungsi kernel
memberikan titik sinkronisasi dan karena itu kami telah mencapai sinkronisasi
dengan biaya komputasi minimal.
o Solusi 8 - Menggunakan CPU untuk melakukan perhitungan akhir
dalam langkah terakhir dari algoritma reduksi.
Pada langkah
terakhir dari algoritma reduksi dimensi dataset berukuran dan dengan demikian,
jika kita telah menggunakan GPU untuk melakukan pengurangan dalam hal ini,
sumber daya akan sia-sia. Oleh karena itu, kami telah memutuskan untuk
mengurangi array, elemen AOS dari memori global dalam langkah terakhir dari
pengurangan menggunakan CPU. Keuntungan utama dari pendekatan ini adalah bahwa
GPU sudah tersedia untuk memproses perhitungan lain sementara CPU memfinalisasi
operasi pengurangan. Dengan menerapkan delapan solusi, kami telah meningkatkan
pengurangan paralel fungsi algoritmik, kinerja AOS, baik mengenai waktu
eksekusi dan bandwidth.
Referensi :
3. Penelitian Ion LUNG, Dana-Mihaela PETROSAN,
Alexandru PIRJAN Academy of Economic Studies, Bucharest, RomaniaUniversity
Politehnica of Bucharest, RomaniaRomanian-American University, Bucharest
