Pengalaman kami dalam menggunakan cluster komputasi 480 AMD RX 480 GPU untuk memecahkan masalah matematika. Sebagai masalah, kami mengambil bukti teorema dari sebuah artikel oleh Profesor A. Chudnov "
Dekomposisi siklik set yang memisahkan diagram dan kelas permainan siklik dengan hasil yang terjamin ." Tugasnya adalah menemukan jumlah minimum peserta dalam satu koalisi dalam game koalisi tipe Nim, yang menjamin kemenangan salah satu pihak.
Pengembangan CPU
Prosesor pertama yang benar-benar mendapat distribusi massal adalah 8086 dari Intel, dikembangkan pada tahun 1978. Kecepatan clock 8086 hanya 8 MHz. Beberapa tahun kemudian, prosesor pertama muncul di dalamnya yang ada 2, 4 dan bahkan 8 core. Setiap inti memungkinkan kodenya dieksekusi secara independen dari yang lain. Sebagai perbandingan, prosesor Intel Core i9-7980XE modern beroperasi pada frekuensi 2,6 GHz dan berisi 18 core. Seperti yang Anda lihat, kemajuan tidak berhenti!
Pengembangan GPU
Bersamaan dengan perkembangan prosesor sentral, kartu video juga dikembangkan. Pada dasarnya, karakteristik mereka penting untuk permainan komputer, di mana teknologi baru sangat berwarna dan rendering gambar 3D secara bertahap mendekati kualitas fotografi. Pada awal pengembangan permainan komputer, perhitungan gambar dilakukan pada CPU, tetapi daya cipta pengembang grafis 3D segera tercapai, yang berhasil mengoptimalkan bahkan hal-hal yang jelas (contoh yang baik dari ini adalah
InvSqrt () ). Jadi, prosesor-prosesor dengan seperangkat instruksi khusus untuk melakukan perhitungan 3D mulai muncul dalam kartu video. Seiring waktu, jumlah tim tersebut tumbuh, yang, di satu sisi, memungkinkan bekerja lebih fleksibel dan efisien dengan gambar, dan di sisi lain, mempersulit proses pengembangan.
Sejak 1996, akselerator grafis S3 ViRGE, 3dfx Voodoo, Diamond Monster dan lainnya mulai diproduksi. Pada tahun 1999, nVidia merilis prosesor GeForce 256, memperkenalkan istilah GPU - prosesor grafis. Ini sudah universal, dapat menangani perhitungan geometris, transformasi koordinat, penempatan titik pencahayaan, dan bekerja dengan poligon. Perbedaan antara GPU dan chip grafis lainnya adalah di dalamnya, di samping perintah khusus, ada satu set perintah standar yang dengannya Anda dapat menerapkan algoritma rendering Anda sendiri. Ini memberikan keuntungan yang signifikan, karena memungkinkan untuk menambahkan efek khusus, dan bukan hanya yang sudah diprogram ke dalam kartu video. Dimulai dengan GeForce 8000/9000, prosesor aliran muncul di GPU - komputer yang sudah lengkap. Jumlah mereka berkisar antara 16 hingga 128 tergantung pada modelnya.Dalam terminologi modern, mereka disebut unit shader terpadu, atau hanya unit shader. AMD Vega 64 GPU yang diproduksi hari ini memuat 4096 unit shader, dan frekuensi clocknya bisa mencapai 1.536 MHz!
Apa yang terkandung dalam GPU?
Arsitektur GPU berbeda dari CPU dalam sejumlah besar inti dan satu set instruksi minimalis yang terutama ditujukan untuk komputasi vektor. Pada tingkat arsitektur, masalah operasi paralel sejumlah besar core dan akses simultan ke memori telah diselesaikan. GPU modern terdiri dari 2 hingga 4 ribu unit shader, yang digabungkan menjadi unit komputasi (Compute Unit). Dalam komputasi paralel, masalah akses simultan ke memori sangat akut. Jika masing-masing prosesor aliran mencoba menulis ke sel memori, maka perintah-perintah ini akan berakhir di kunci dan mereka harus antri, yang akan sangat mengurangi kinerja. Oleh karena itu, stream prosesor menjalankan instruksi dalam kelompok-kelompok kecil: sementara satu kelompok melakukan perhitungan, yang lain memuat register, dll. Anda juga dapat menggabungkan inti ke dalam kelompok kerja dengan memori bersama dan mekanisme sinkronisasi internal.
Fitur penting lain dari GPU adalah keberadaan register vektor dan vektor ALU, yang dapat melakukan operasi secara bersamaan untuk beberapa komponen vektor. Ini terutama diperlukan untuk grafik 3D, tetapi karena dunia kita tiga dimensi, tidak ada yang mencegah kita menggunakannya untuk banyak perhitungan fisik. Dengan adanya ALU vektor gratis, mereka juga dapat digunakan untuk menghitung jumlah skalar.
Mereka sangat berbeda, CPU dan GPU
Untuk pengoperasian penuh sistem komputasi, kedua jenis perangkat ini penting. Misalnya, kami menjalankan program langkah demi langkah, suatu algoritma sekuensial tertentu. Tidak ada cara untuk melakukan langkah kelima dari algoritma, sehingga data untuk itu dihitung pada langkah empat. Dalam hal ini, lebih efisien menggunakan CPU dengan cache besar dan kecepatan clock tinggi. Tetapi ada seluruh kelas tugas yang cocok untuk paralelisasi. Dalam hal ini, efektivitas GPU jelas. Contoh paling umum adalah menghitung piksel dari gambar yang diberikan. Prosedur untuk setiap piksel hampir sama, data tentang objek dan tekstur 3D terletak di RAM kartu video, dan setiap prosesor aliran dapat secara mandiri menghitung bagian gambarnya sendiri.
Berikut adalah contoh dari tugas modern - melatih jaringan saraf. Sejumlah besar neuron identik perlu dilatih, yaitu, untuk mengubah koefisien berat masing-masing neuron. Setelah perubahan seperti itu, perlu untuk melewati urutan uji melalui jaringan saraf untuk pelatihan dan mendapatkan vektor kesalahan. Perhitungan semacam itu sangat cocok untuk GPU. Setiap prosesor aliran dapat berperilaku seperti neuron dan selama perhitungan tidak perlu membangun solusi secara berurutan, semua perhitungan kami akan terjadi secara bersamaan. Contoh lain adalah perhitungan aliran aerodinamis. Penting untuk mengetahui perilaku yang mungkin dari jembatan yang dirancang di bawah pengaruh angin, untuk mensimulasikan stabilitas aerodinamisnya, untuk menemukan tempat pemasangan yang optimal untuk fairing untuk menyesuaikan aliran udara atau untuk menghitung hambatan terhadap resonansi angin. Ingat "jembatan menari" yang terkenal di Volgograd? Saya pikir tidak ada yang mau berada di jembatan saat itu ...
Perilaku aliran udara di setiap titik dapat dijelaskan oleh persamaan matematika yang sama dan menyelesaikan persamaan ini secara paralel pada sejumlah besar inti.
GPU ada di tangan programmer
Untuk melakukan perhitungan pada GPU, bahasa khusus dan kompiler digunakan. Ada beberapa kerangka kerja untuk melakukan komputasi GPU umum: OpenCL, CUDA, C ++ AMP, OpenACC. Dua yang pertama banyak digunakan, tetapi penggunaan CUDA hanya dibatasi oleh GPU nVidia.
OpenCL dirilis pada 2009 oleh Apple. Belakangan, Intel, IBM, AMD, Google dan nVidia bergabung dengan Khronos Group dan mengumumkan dukungan mereka untuk standar bersama. Sejak itu, versi standar baru muncul setiap satu setengah hingga dua tahun dan masing-masing membawa perbaikan yang lebih dan lebih serius.
Sampai saat ini, bahasa OpenCL C ++ versi 2.2 sesuai dengan standar C ++ 14, mendukung eksekusi simultan beberapa program dalam perangkat, interaksi di antara mereka melalui antrian internal dan saluran pipa, dan memungkinkan pengelolaan buffer dan memori virtual yang fleksibel.
Tugas nyata
Masalah yang menarik dari teori permainan, dalam solusi yang kami ambil bagian, adalah bukti teorema dari sebuah artikel oleh Profesor A. Chudnov "
Dekomposisi siklik set yang memisahkan diagram dan kelas permainan siklik dengan hasil yang terjamin ." Tugasnya adalah menemukan jumlah minimum peserta dalam satu koalisi dalam game koalisi tipe Nim, yang menjamin kemenangan salah satu pihak.
Dari sudut pandang matematika, ini adalah pencarian untuk urutan siklik dukungan. Jika Anda mewakili urutan dalam bentuk daftar nol dan yang, maka pemeriksaan untuk dukungan dapat diimplementasikan oleh operasi bitwise logis. Dari sudut pandang pemrograman, urutan seperti itu adalah register yang panjang, misalnya, 256 bit. Cara paling andal untuk memecahkan masalah ini adalah memilah-milah semua opsi kecuali yang tidak mungkin karena alasan yang jelas.
Tujuan penyelesaian masalah adalah masalah pemrosesan sinyal yang efektif (deteksi, sinkronisasi, pengukuran koordinat, pengkodean, dll.).
Kompleksitas penyelesaian masalah ini adalah memilah-milah sejumlah besar opsi. Sebagai contoh, jika kita mencari solusi untuk n = 25, maka ini adalah 25 bit, dan jika n = 100, maka ini sudah 100 bit. Jika kita mengambil jumlah semua kombinasi yang mungkin, maka untuk n = 25 itu adalah 2 ^ 25 = 33 554 432, dan untuk n = 100 itu sudah 2 ^ 100 = 1 267 650 600 228 229 401 496 703 205 376 kombinasi. Peningkatan kompleksitas hanyalah kolosal!
Tugas ini diparalelkan dengan baik, yang artinya ideal untuk kluster GPU kami.
Pemrogram vs Matematika
Awalnya, matematikawan menyelesaikan masalah ini dalam Visual Basic di Excel, sehingga mereka berhasil mendapatkan solusi utama, tetapi rendahnya kinerja bahasa scripting tidak memungkinkan kita untuk bergerak jauh ke depan. Keputusan untuk n = 80 memakan waktu satu setengah bulan ... Kami menundukkan kepala di depan orang-orang yang sabar ini.
Tahap pertama, kami mengimplementasikan algoritma tugas di C dan meluncurkannya di CPU. Dalam prosesnya, ternyata banyak yang bisa dioptimalkan saat bekerja dengan urutan bit.
Selanjutnya, kami mengoptimalkan area pencarian dan menghilangkan duplikasi. Juga, analisis kode assembler yang dihasilkan oleh kompiler dan optimalisasi kode untuk fitur kompiler memberikan hasil yang baik. Semua ini memungkinkan untuk mencapai peningkatan signifikan dalam kecepatan perhitungan.
Tahap optimasi berikutnya adalah pembuatan profil. Pengukuran waktu eksekusi berbagai bagian kode menunjukkan bahwa di beberapa cabang algoritma, beban pada memori meningkat secara signifikan, dan percabangan program yang berlebihan terungkap. Karena cacat "kecil" ini, hampir sepertiga daya CPU tidak digunakan.
Aspek yang sangat penting untuk menyelesaikan masalah tersebut adalah keakuratan penulisan kode. Tidak ada yang tahu jawaban yang benar untuk masalah ini dan, karenanya, tidak ada vektor uji. Hanya ada bagian pertama dari rangkaian solusi yang telah ditemukan oleh ahli matematika. Keandalan solusi baru hanya dapat dijamin oleh keakuratan kode penulisan.
Jadi tahap mempersiapkan program untuk solusi pada GPU telah tiba dan kode telah dimodifikasi untuk bekerja di beberapa utas. Program kontrol sekarang terlibat dalam tugas pengiriman antar utas. Di lingkungan multi-utas, kecepatan perhitungan telah meningkat 5 kali! Ini dicapai karena operasi simultan dari 4 utas dan kombinasi fungsi.
Pada tahap ini, keputusan membuat perhitungan yang benar hingga n = 80 dalam 10 menit, sedangkan di Excel, perhitungan ini membutuhkan waktu satu setengah bulan! Sedikit kemenangan!
GPU dan OpenCL
Diputuskan untuk menggunakan OpenCL versi 1.2 untuk memastikan kompatibilitas maksimum antara platform yang berbeda. Debugging awal dilakukan pada CPU Intel, kemudian pada GPU Intel. Kemudian mereka beralih ke GPU dari AMD.
Standar OpenCL 1.2 mendukung variabel integer 64 bit. Dimensi 128-bit secara terbatas didukung oleh AMD, tetapi dikompilasi menjadi dua angka 64-bit. Untuk alasan kompatibilitas dan untuk mengoptimalkan kinerja, diputuskan untuk menghadirkan angka 256-bit sebagai kelompok angka 32-bit, operasi bitwise logis yang dilakukan pada GPU ALU internal secepat mungkin.
Program OpenCL berisi kernel - fungsi yang merupakan titik masuk dari suatu program. Data untuk diproses diunduh dari CPU ke RAM kartu video dan ditransfer ke kernel dalam bentuk buffer - pointer ke array data input dan output. Mengapa sebuah array? Kami melakukan komputasi kinerja tinggi, kami membutuhkan banyak tugas yang dilakukan secara bersamaan. Kernel berjalan pada perangkat dalam banyak hal. Setiap inti tahu pengenalnya dan mengambil bagian inputnya sendiri dari buffer bersama. Kasus di mana solusi paling sederhana adalah yang paling efektif. OpenCL tidak hanya bahasa, tetapi juga kerangka kerja yang komprehensif di mana semua rincian komputasi ilmiah dan game dipikirkan secara menyeluruh. Ini membuat hidup lebih mudah bagi pengembang. Misalnya, Anda dapat memulai banyak utas, pengelola tugas akan menempatkannya di perangkat itu sendiri. Tugas-tugas yang tidak memulai eksekusi segera akan diantrikan dan diluncurkan saat unit komputasi menjadi bebas. Setiap instance kernel memiliki ruang sendiri di buffer output, di mana ia menempatkan respons setelah menyelesaikan pekerjaan.
Tugas utama manajer OpenCL adalah untuk memastikan eksekusi paralel dari beberapa instance kernel. Pengalaman ilmiah dan praktis yang terakumulasi selama beberapa dekade diterapkan di sini. Sementara beberapa core memuat data ke dalam register, bagian lain saat ini bekerja dengan memori atau melakukan perhitungan - sebagai hasilnya, inti GPU selalu terisi penuh.
Kompilator OpenCL melakukan pekerjaan optimalisasi, tetapi lebih mudah bagi pengembang untuk memengaruhi kinerja. Optimalisasi GPU berjalan dalam dua arah - mempercepat eksekusi kode dan kemungkinan memparalelkannya. Seberapa baik kode diparalelkan oleh kompiler tergantung pada beberapa hal: jumlah register awal yang ditempati (yang terletak di memori GPU paling lambat - global), ukuran kode yang dikompilasi (Anda harus memasukkan cache 32 kb), jumlah vektor dan register skalar yang digunakan.
GPU ComBox A-480 atau Satu Juta Cores
Ini adalah bagian paling menarik dari proyek ini, ketika kami beralih dari Excel ke cluster komputasi yang terdiri dari 480 kartu grafis AMD RX 480. Besar, cepat, efisien. Benar-benar siap untuk memenuhi tugas dan mendapatkan hasil yang belum pernah dilihat dunia sebelumnya.
Saya ingin mencatat bahwa pada semua tahap meningkatkan dan mengoptimalkan kode, kami mulai mencari solusi dari awal dan membandingkan jawaban dari versi baru dengan yang sebelumnya. Ini memungkinkan kami untuk memastikan bahwa optimasi dan peningkatan kode tidak memperkenalkan kesalahan ke dalam solusi. Di sini Anda perlu memahami bahwa tidak ada jawaban yang benar di akhir buku pelajaran, dan tidak ada seorang pun di dunia yang mengetahuinya.
Peluncuran pada cluster mengkonfirmasi asumsi kami pada kecepatan solusi: pencarian untuk urutan n> 100 memakan waktu sekitar satu jam. Sungguh menakjubkan melihat bagaimana solusi baru pada cluster ComBox A-480 dalam beberapa menit, sementara pada CPU butuh berjam-jam.
Hanya dalam dua jam dari cluster komputasi, kami mendapatkan semua solusi hingga n = 127. Pemeriksaan solusi menunjukkan bahwa jawaban yang diperoleh dapat diandalkan dan sesuai dengan teorema Profesor A. Chudnov yang dinyatakan dalam artikel
Evolusi kecepatan
Jika Anda melihat peningkatan kinerja dalam penyelesaian masalah, hasilnya kira-kira sebagai berikut:
- satu setengah bulan hingga n = 80 di Excel;
- satu jam ke n = 80 pada Core i5 dengan program C ++ yang dioptimalkan;
- 10 menit hingga n = 80 pada Core i5 menggunakan multithreading;
- 10 menit hingga n = 100 pada satu GPU AMD RX 480;
- 120 menit hingga n = 127 pada ComBox A-480.
Prospek dan masa depan
Banyak tugas di persimpangan sains dan praktik yang tertunda untuk membuat hidup kita lebih baik. Pasar penyewaan daya komputasi baru saja muncul, dan kebutuhan akan komputasi paralel terus tumbuh.
Kemungkinan aplikasi komputasi paralel:
- tugas kontrol otomatis kendaraan dan drone;
- perhitungan karakteristik aerodinamik dan hidrodinamik;
- pengenalan suara dan gambar visual;
- pelatihan jaringan saraf;
- tugas astronomi dan astronotika;
- statistik dan analisis korelasi data;
- melipatgandakan senyawa protein-protein;
- diagnosis dini penyakit menggunakan AI.
Arah terpisah adalah komputasi awan pada GPU. Misalnya, raksasa seperti Amazon, IBM dan Google menyewakan daya komputasi mereka ke GPU. Hari ini kita dapat mengatakan dengan yakin bahwa masa depan komputasi paralel berkinerja tinggi akan menjadi milik kelompok GPU.