Hai, habrozhiteli! Bahasa C ++ dipilih ketika Anda perlu membuat aplikasi yang benar-benar secepat kilat. Dan pemrosesan kompetitif berkualitas tinggi akan membuat mereka lebih cepat. Fitur-fitur baru dari C ++ 17 memungkinkan Anda untuk menggunakan kekuatan penuh dari pemrograman multi-threaded untuk dengan mudah menyelesaikan masalah pemrosesan grafis, pembelajaran mesin, dll. termasuk pengembang yang paling berpengalaman.
Dalam buku ini • Tinjauan lengkap fitur C ++ 17. • Luncurkan dan kontrol aliran. • Sinkronisasi operasi kompetitif. • Pengembangan kode kompetitif. • Debugging aplikasi multithreaded. Buku ini cocok untuk pengembang tingkat menengah yang menggunakan C dan C ++. Pengalaman pemrograman kompetitif tidak diperlukan.
Pengembangan Kode Kompetitif
8.1. Cara untuk mendistribusikan pekerjaan di antara utas
Bayangkan Anda perlu membangun rumah. Untuk melakukan ini, Anda harus menggali lubang fondasi, mengisi fondasi itu sendiri, membangun dinding, meletakkan pipa dan kabel listrik, dll. Secara teoritis, dengan keterampilan yang memadai, semuanya dapat dilakukan secara mandiri, tetapi kemungkinan besar itu akan membutuhkan banyak waktu dan Anda harus beralih dari satu pekerjaan ke pekerjaan lain. satu lagi. Tapi Anda bisa mempekerjakan asisten. Maka akan perlu untuk memilih berapa banyak asisten untuk dipekerjakan, dan memutuskan apa yang harus mereka dapat. Anda dapat, misalnya, merekrut dua pekerja dan bekerja dengan mereka. Maka Anda masih harus beralih dari satu pekerjaan ke pekerjaan lain, tetapi sekarang segalanya akan berjalan lebih cepat, karena akan ada lebih banyak artis.
Anda dapat memilih opsi lain - menyewa tim spesialis, seperti tukang batu, tukang kayu, tukang listrik dan tukang ledeng. Masing-masing akan bekerja dalam kekhususannya sendiri, oleh karena itu, sampai tukang ledeng memiliki bagian depan pekerjaan, ia akan duduk diam. Namun segalanya akan berjalan lebih cepat dari sebelumnya, karena ada lebih banyak pekerja, dan sementara tukang listrik akan melakukan perkabelan di dapur, tukang ledeng dapat pergi ke kamar mandi. Tetapi ketika tidak ada pekerjaan untuk spesialis tertentu, lebih banyak downtime diperoleh. Namun, dapat dicatat bahwa bahkan dengan penghentian diperhitungkan, pekerjaan bergerak lebih cepat ketika spesialis datang untuk bekerja, daripada tim pekerja. Spesialis tidak perlu terus-menerus mengubah alat, dan pasti masing-masing dari mereka akan melakukan tugas mereka lebih cepat daripada pekerja. Apakah ini akan benar-benar tergantung pada keadaan spesifik: semuanya dipelajari dalam praktik.
Bahkan jika Anda melibatkan spesialis, Anda masih perlu memilih jumlah pekerja yang berbeda dari berbagai spesialisasi. Mungkin masuk akal untuk menyewa, misalnya, lebih banyak tukang batu daripada tukang listrik. Selain itu, komposisi tim Anda dan efektivitas keseluruhan pekerjaannya dapat berubah jika Anda harus membangun beberapa rumah sekaligus. Bahkan jika ada sedikit pekerjaan untuk tukang ledeng di satu rumah, maka ketika membangun beberapa rumah sekaligus, itu bisa diambil sepanjang hari. Selain itu, jika Anda tidak perlu membayar spesialis untuk downtime, Anda dapat merekrut tim yang lebih besar, bahkan jika jumlah orang yang bekerja secara bersamaan tidak berubah.
Tetapi berhenti berbicara tentang konstruksi. Apa hubungannya semua ini dengan utas? Dan Anda dapat menerapkan pertimbangan serupa pada mereka. Anda harus memutuskan berapa banyak utas untuk digunakan dan tugas apa yang harus mereka lakukan. Apakah kita memerlukan utas universal yang melakukan pekerjaan yang diperlukan pada saat tertentu, atau utas khusus yang disesuaikan dengan baik hanya pada satu hal? Atau mungkin perlu menggabungkan keduanya? Keputusan ini harus dibuat terlepas dari alasan untuk memparalelkan program, dan kinerja serta kejelasan kode secara signifikan tergantung pada seberapa sukses mereka. Oleh karena itu, sangat penting untuk membayangkan opsi apa yang tersedia untuk membuat keputusan yang kompeten ketika mengembangkan struktur aplikasi. Pada bagian ini, kami akan mempertimbangkan sejumlah metode untuk mendistribusikan tugas, mulai dengan distribusi data antara utas untuk melakukan pekerjaan lain.
8.1.1. Distribusi data antar utas sebelum diproses
Yang paling mudah untuk diparalelkan adalah algoritma sederhana, seperti std :: for_each, yang melakukan operasi pada setiap elemen kumpulan data. Untuk memparalelkan algoritma ini, Anda dapat menetapkan setiap elemen ke salah satu utas pemrosesan. Di masa depan, ketika mempertimbangkan masalah kinerja, akan menjadi jelas bahwa opsi distribusi terbaik untuk mencapai kinerja yang optimal tergantung pada karakteristik struktur data.
Saat mendistribusikan data, kasus paling sederhana adalah ketika elemen N pertama ditugaskan ke satu aliran, elemen N berikutnya ke yang lain, dan seterusnya (Gbr. 8.1), tetapi skema lain dapat digunakan. Terlepas dari metode distribusi data, setiap utas hanya memproses elemen yang ditugaskan padanya, tanpa berinteraksi dengan utas lainnya hingga selesai diproses.
Struktur harus akrab bagi siapa saja yang telah
bekerja dengan pemrograman di dalam Message Passing Interface (MPI,
www.mpi-forum.org ) atau lingkungan OpenMP (http://www.openmp.org/): tugas dibagi menjadi banyak tugas yang dieksekusi secara paralel, alur kerja menjalankannya secara independen satu sama lain, dan hasilnya dikumpulkan pada tahap akhir informasi. Pendekatan ini digunakan dalam contoh dengan fungsi akumulasi dari bagian 2.4: baik tugas paralel maupun tahap reduksi adalah akumulasi. Untuk algoritma for_each yang sederhana, langkah terakhir tidak ada, karena tidak ada yang dikurangi.
Fakta bahwa campuran didefinisikan sebagai esensi dari tahap akhir memainkan peran yang sangat penting: implementasi dasar mirip dengan yang ditunjukkan pada Listing 2.9 akan melakukan campuran ini sebagai tahap sekuensial akhir. Tetapi seringkali tahap ini juga diparalelkan: akumulasi adalah operasi pengurangan, sehingga kode pada Listing 2.9 dapat diubah untuk mendapatkan panggilan rekursif dari kode yang sama ketika, misalnya, jumlah utas lebih besar daripada jumlah minimum elemen yang diproses oleh utas. Anda juga dapat memaksa alur kerja untuk melakukan langkah-langkah rollup segera setelah masing-masing menyelesaikan tugas mereka, daripada memulai utas baru setiap kali.
Untuk semua efektivitasnya, teknik ini tidak serbaguna. Terkadang data tidak dapat dibagi secara akurat sebelumnya, karena komposisi setiap bagian hanya diketahui selama pemrosesan. Secara khusus, ini terbukti ketika menggunakan algoritma rekursif seperti Quicksort, sehingga mereka membutuhkan pendekatan yang berbeda.
8.1.2. Distribusi data rekursif
Algoritme Quicksort memiliki dua tahap utama: memecah data menjadi dua bagian - segala sesuatu yang muncul ke salah satu elemen (referensi), dan segala sesuatu yang datang setelahnya dalam urutan akhir, dan penyortiran rekursif dari kedua bagian ini. Tidak mungkin untuk memparalelasinya dengan memisahkan data awal, karena dimungkinkan untuk menentukan "setengah" mana yang termasuk dalam pemrosesan elemen. Jika Anda bermaksud untuk memparalelkan algoritma ini, Anda perlu menggunakan esensi rekursi. Pada setiap tingkat rekursi, semakin banyak panggilan ke fungsi quick_sort dilakukan, karena Anda harus mengurutkan keduanya yang lebih besar dari referensi dan yang lebih kecil dari itu. Panggilan rekursif ini tidak tergantung satu sama lain karena merujuk pada set elemen yang terpisah. Karena itu, mereka adalah kandidat pertama untuk daya saing. Distribusi rekursif ini ditunjukkan pada Gambar. 8.2.
Implementasi ini sudah dipenuhi di Bab 4. Alih-alih membuat dua panggilan rekursif untuk bagian yang lebih besar dan lebih kecil, kami menggunakan fungsi std :: async (), yang menjalankan tugas asinkron untuk setengah yang lebih kecil di setiap langkah. Karena penggunaan std :: async (), Perpustakaan C ++ Thread harus memutuskan kapan memulai tugas di utas baru, dan kapan - dalam mode sinkron.
Ada satu keadaan penting: saat menyortir kumpulan data besar, memulai utas baru untuk setiap rekursi akan mengarah pada peningkatan cepat dalam jumlah utas. Saat memeriksa masalah kinerja, akan ditampilkan bahwa terlalu banyak utas dapat memperlambat aplikasi. Selain itu, dengan sejumlah besar aliran data mungkin tidak cukup. Gagasan untuk membagi seluruh tugas dalam mode rekursif seperti ini tampaknya sangat berhasil, Anda hanya perlu memantau jumlah utas secara cermat. Dalam kasus sederhana, fungsi std :: async () menangani ini, tetapi ada opsi lain.
Salah satunya adalah dengan menggunakan fungsi std :: thread :: hardware_concurrency () untuk memilih jumlah utas, seperti yang dilakukan dalam versi paralel fungsi akumulasi () dari Listing 2.9. Kemudian, alih-alih memulai utas baru untuk setiap panggilan rekursif, Anda dapat menempatkan fragmen untuk diurutkan pada tumpukan aman-benang, misalnya, seperti yang dibahas dalam bab 6 dan 7. Jika utas tidak ada hubungannya atau telah selesai memproses semua fragmennya atau sedang menunggu fragmen diurutkan, ia dapat ambil satu fragmen dari tumpukan dan urutkan.
Listing 8.1 menunjukkan implementasi sederhana dari teknologi ini. Seperti dalam kebanyakan contoh lain, itu hanya menunjukkan maksud, dan bukan kode yang siap untuk penggunaan praktis. Jika Anda menggunakan kompiler C ++ 17 dan perpustakaan Anda mendukungnya, Anda harus menggunakan algoritma paralel yang disediakan oleh perpustakaan standar sesuai dengan deskripsi yang diberikan pada bab 10.
Daftar 8.1. Algoritma Quicksort paralel yang menggunakan tumpukan fragmen menunggu penyortiran
Di sini, fungsi parallel_quick_sort
(19) menempatkan sebagian besar tanggung jawab fungsional pada kelas sorter
(1) , yang menyediakan cara mudah untuk mengelompokkan tumpukan fragmen yang tidak disortir
(2) dan beberapa utas
(3) . Pekerjaan utama dilakukan dalam fungsi komponen do_sort
(9) , yang ditempati oleh partisi data biasa
(10) . Kali ini, alih-alih memulai utas baru untuk setiap fragmen, ia mendorong fragmen ini pada tumpukan (11) dan memulai utas baru hanya jika ada sumber daya prosesor gratis (12). Karena sebuah fragmen dengan nilai yang lebih rendah dari referensi yang dapat diproses oleh aliran lain, kita harus menunggu kesiapannya
(13) . Agar waktu tidak terbuang (jika kami memiliki satu utas atau semua utas lainnya sudah terisi), upaya dilakukan untuk memproses fragmen dari tumpukan untuk periode tunggu ini
(14) . Fungsi try_sort_chunk mengambil fragmen dari stack
(7) , mengurutkannya
(8), dan menyimpan hasilnya dalam janji janji sehingga mereka dapat menerima aliran yang meletakkan fragmen ini di stack
(15) .
Sekarang, utas yang baru saja diluncurkan berada dalam satu lingkaran dan mencoba untuk mengurutkan fragmen dari tumpukan
(17) jika flag end_of_data
(16) tidak disetel. Di antara pemeriksaan, mereka menyerahkan sumber daya komputasi ke utas lain sehingga mereka dapat mendorong pekerjaan tambahan ke tumpukan. Pekerjaan kode dalam hal menempatkan thread ini dalam urutan tergantung pada destructor kelas penyortir Anda
(4) . Ketika semua data diurutkan, fungsi do_sort akan mengembalikan kontrol (bahkan sambil mempertahankan aktivitas utas pekerja), utas utama akan kembali dari parallel_quick_sort
(20) dan menghancurkan objek sorter. Ini akan mengatur flag end_of_data
(5) dan akan menunggu utasnya selesai bekerja
(6). Mengatur bendera akan menghentikan loop pada fungsi utas (16).
Dengan pendekatan ini, masalah jumlah utas yang tidak terbatas yang melekat pada fungsi spawn_task yang meluncurkan utas baru akan menghilang dan ketergantungan pada pustaka utas C ++, yang memilih jumlah utas untuk Anda, seperti halnya ketika menggunakan std :: async (), akan menghilang. Sebagai gantinya, untuk mencegah pengalihan tugas terlalu sering, jumlah utas dibatasi oleh nilai yang dikembalikan oleh fungsi std :: thread :: hardware_concurrency (). Tetapi masalah lain muncul: mengelola aliran ini dan bertukar data di antara mereka sangat menyulitkan kode. Selain itu, terlepas dari kenyataan bahwa thread memproses elemen data individual, semuanya mengakses stack, menambahkan fragmen baru ke dalamnya dan mengambil fragmen untuk diproses. Persaingan yang ketat seperti itu dapat mengurangi kinerja, bahkan jika tumpukan bebas kunci (karenanya, non-pemblokiran) digunakan, dan alasannya akan segera dipertimbangkan.
Pendekatan ini adalah versi khusus dari kumpulan utas - satu set utas, yang masing-masing menerima pekerjaan dari daftar pekerjaan yang ditangguhkan, melaksanakannya, dan kemudian beralih ke daftar untuk yang baru. Beberapa potensi masalah yang melekat pada kumpulan thread (termasuk kompetisi ketika mengakses daftar karya), dan cara untuk menyelesaikannya dibahas pada Bab 9. Tentang penskalaan aplikasi yang dibuat sehingga dijalankan pada beberapa prosesor, kita akan membahas bab ini nanti (lihat ayat 8.2.1).
Saat mendistribusikan data baik sebelum pemrosesan maupun dalam mode rekursif, diasumsikan bahwa data tersebut diperbaiki terlebih dahulu, dan pencarian sedang dilakukan untuk distribusi mereka. Tetapi ini tidak selalu terjadi: jika data dibuat dalam mode dinamis atau berasal dari sumber eksternal, pendekatan ini tidak berfungsi. Dalam hal ini, mungkin lebih masuk akal untuk mendistribusikan pekerjaan sesuai dengan jenis tugas, dan tidak berdasarkan data itu sendiri.
8.1.3. Distribusi pekerjaan berdasarkan jenis tugas
Distribusi pekerjaan antar utas dengan menugaskan masing-masing (di muka atau secara rekursif selama pemrosesan data) bagian-bagian data yang berbeda dalam hal apa pun didasarkan pada asumsi bahwa utas akan melakukan pekerjaan yang sama pada setiap bagian. Distribusi alternatif pekerjaan adalah spesialisasi aliran, di mana masing-masing melakukan tugas yang terpisah, karena tukang ledeng dan listrik melakukan tugas yang berbeda dalam membangun rumah. Streaming dapat bekerja dengan data yang berbeda atau sama, tetapi dalam kasus terakhir mereka melakukannya untuk tujuan yang berbeda.
Pembagian kerja yang aneh ini muncul sebagai akibat dari pemisahan tugas dengan bantuan persaingan: masing-masing utas memiliki tugas yang terpisah, yang ia lakukan secara independen dari aliran lain. Terkadang utas lainnya dapat mengirimkan data ke arus atau menghasilkan acara yang harus ditanggapi, tetapi secara umum, setiap aliran berkonsentrasi pada kinerja berkualitas tinggi dari satu tugas. Ini adalah desain dasar yang baik, di mana setiap bagian kode harus bertanggung jawab atas satu hal.
Distribusi pekerjaan berdasarkan jenis tugas untuk berbagi tanggung jawab
Aplikasi single-threaded harus mengatasi konflik yang terkait dengan prinsip tanggung jawab tunggal, ketika ada beberapa tugas yang harus dilakukan terus menerus untuk waktu tertentu, atau aplikasi harus mengatasi pemrosesan peristiwa yang masuk secara tepat waktu (misalnya, pengguna menekan kunci atau data masuk melalui jaringan) di hadapan tugas-tugas lain yang belum selesai. Dalam lingkungan komputasi single-threaded, Anda harus secara independen membuat kode yang menjalankan bagian dari tugas A, bagian dari tugas B, memeriksa untuk melihat apakah kunci ditekan dan tidak ada paket jaringan, dan kemudian secara siklus kembali ke bagian berikutnya dari tugas A. Ini mempersulit kode untuk mengeksekusi tugas A karena kebutuhan untuk mempertahankan keadaannya dan secara berkala mengembalikan kontrol ke loop utama. Jika Anda menambahkan terlalu banyak tugas ke siklus, pekerjaan dapat melambat secara signifikan dan pengguna mungkin akan melihat reaksi lambat terhadap penekanan tombol. Saya yakin bahwa setiap orang mengamati manifestasi ekstrem dari situasi serupa di aplikasi tertentu: Anda menetapkan tugas untuk aplikasi tersebut, dan antarmuka tidak bereaksi terhadap apa pun sampai selesai.
Di sini mengalir ke atas panggung. Jika Anda menjalankan setiap tugas dalam utas terpisah, maka sistem operasi dapat melakukan ini sebagai ganti Anda. Dalam kode untuk tugas A, Anda bisa fokus menyelesaikan tugas tanpa khawatir mempertahankan status dan kembali ke loop utama, atau tentang berapa banyak waktu yang akan berlalu sebelum ini terjadi. Artinya, sistem operasi akan secara otomatis menyimpan status dan beralih ke tugas B atau C pada waktu yang tepat, dan jika sistem tempat program akan dijalankan memiliki beberapa inti atau prosesor, akan dimungkinkan untuk secara bersamaan menjalankan tugas A dan B. Kode untuk memproses penekanan tombol atau tanda terima paket jaringan sekarang dapat dieksekusi tepat waktu, dan semua orang akan mendapat manfaat: pengguna akan menerima respons program yang memadai, dan Anda, sebagai pengembang, akan menerima kode yang disederhanakan, karena setiap aliran dapat diarahkan untuk melakukan operasi yang terkait langsung dengan tugasnya, tanpa mencampurkannya dengan aliran kontrol dan interaksi pengguna.
Gambaran ideal muncul. Tapi bisakah semuanya menjadi seperti itu? Seperti biasa, semuanya tergantung pada keadaan tertentu. Jika independensi penuh dihormati dan arus tidak perlu saling bertukar data, maka itulah yang akan terjadi. Sayangnya, situasi serupa jarang diamati. Seringkali, tindakan yang diperlukan untuk pengguna memiliki bentuk tugas latar belakang yang mudah, dan mereka perlu memberi tahu pengguna tentang tugas tersebut, memperbarui antarmuka pengguna dalam beberapa cara. Atau pengguna mungkin perlu menghentikan tugas, sehingga antarmuka pengguna harus entah bagaimana mengirim pesan ke tugas latar belakang, menyebabkannya berhenti dieksekusi. Dalam kedua kasus, perlu untuk mempertimbangkan desain dan sinkronisasi yang tepat, tetapi tugas yang dilakukan akan tetap terfragmentasi. Utas antarmuka pengguna masih mengontrol antarmuka ini, tetapi mungkin ditugaskan untuk melakukan pembaruan atas permintaan utas lainnya. Utas yang mengimplementasikan tugas latar masih berkonsentrasi pada operasi yang diperlukan untuk menyelesaikannya, juga terjadi bahwa salah satu utas latar memungkinkan tugas untuk menghentikan utas lainnya. Dalam kedua kasus, arus tidak peduli dari mana permintaan itu berasal, mereka hanya peduli pada fakta bahwa permintaan itu dirancang untuk mereka dan secara langsung berkaitan dengan tanggung jawab mereka.
Ada dua bahaya serius dalam berbagi tanggung jawab di antara banyak utas. Pertama, mungkin ternyata tanggung jawab yang tidak pantas didistribusikan. Tanda ini adalah terlalu banyak data yang dibagikan oleh stream, atau fakta bahwa stream yang berbeda harus menunggu satu sama lain. . . , , , , . , , — , , .
. , , .
, . : , , .
— . , , . , , , .
, 8.1.1, , . , .
, : , . , 20 , 3 . , . , , , , 12 , 24 — . . 20 . . . , , , , 12 . , 12 , . , : , , , , , . 3 12 .
, 9 , . . , , . 25 , — . , , : , 100 , , 1 , 100 , 1 100 . , , . , , , .
, , , , .
8.2. ,
, , . , , . , 16 , .
, — , , ( ), . , : ?
8.2.1. ?
( ) , . , , , . , . , . , , ( ) . , , , .
16- 16 : 16 . , 16 . , , ( ). , 16 , , , 1. (oversubscription).
, , C++11 (Standard Thread Library) std::thread::hardware_concurrency(). .
std::thread::hardware_concurrency() : - , , . , , std::thread::hardware_concurrency(), . std::async() , . .
, , , . — , , . , , , , C++. , std::async(), , , . , . , , std::thread::hardware_concurrency(), . , , , .
, . , , , , .
, — .
»Informasi lebih lanjut tentang buku ini dapat ditemukan di
situs web penerbit»
Isi»
Kutipan25% —
C++Setelah pembayaran versi kertas buku, sebuah buku elektronik dikirim melalui email.