Konkurensi besar-besaran dan perangkat keras adalah topik hangat abad ke-21. Ada beberapa alasan bagus untuk ini, dan satu yang agak menyedihkan.
Dua alasan yang bagus: kombinasi kinerja GPU yang sangat baik dalam permainan dan pada saat yang sama sisi tak terduga mereka digunakan dalam pembelajaran AI yang mendalam, karena paralelisme masif diterapkan pada tingkat perangkat keras di sana. Alasan yang menyedihkan adalah bahwa kecepatan sistem uniprosesor telah bertumpu pada hukum fisika sejak 2006. Masalah saat ini dengan kebocoran dan kerusakan termal secara tajam membatasi peningkatan frekuensi clock, dan penurunan tegangan klasik sekarang mengalami masalah serius dengan kebisingan kuantum.
Bersaing untuk mendapatkan perhatian publik, produsen prosesor berusaha untuk mendorong lebih banyak dan lebih banyak core prosesor ke dalam setiap chip, menggembar-gemborkan kinerja teoretis keseluruhan. Upaya konveyorisasi dan metode eksekusi spekulatif, yang menggunakan multithreading di bawah tenda, juga berkembang pesat, sehingga prosesor tunggal yang terlihat oleh programmer dapat memproses instruksi lebih cepat.
Kebenaran yang tidak nyaman adalah bahwa banyak dari tugas komputasi kita yang tidak terlalu glamor tidak dapat
menggunakan multithreading yang terlihat dengan baik. Ada berbagai alasan untuk ini, yang memiliki konsekuensi berbeda untuk programmer, dan ada banyak kebingungan. Pada artikel ini saya ingin mengklarifikasi situasinya.
Pertama, Anda perlu memahami dengan jelas di mana paralelisme perangkat keras berfungsi paling baik dan mengapa. Mari kita lihat perhitungan untuk grafik, jaringan saraf, pemrosesan sinyal dan penambangan bitcoin. Ada sebuah pola: algoritma paralelisasi bekerja paling baik pada peralatan yang (a) dirancang khusus untuk menjalankannya; (b) tidak dapat melakukan hal lain!
Kami juga melihat bahwa input untuk algoritma paralel paling sukses (pengurutan, pencocokan string, transformasi Fourier cepat, operasi matriks, kuantisasi terbalik gambar, dll.) Terlihat sangat mirip. Sebagai aturan, mereka memiliki struktur metrik dan perbedaan antara data "dekat" dan "jauh" tersirat, yang memungkinkan kita untuk memotong mereka menjadi bagian-bagian, karena hubungan antara elemen-elemen yang jauh tidak signifikan.
Dalam hal artikel terakhir tentang lokalitas semantik, kita dapat mengatakan bahwa metode paralel terutama berlaku di mana data memiliki lokalitas yang baik. Dan mereka bekerja paling baik pada peralatan yang hanya mendukung koneksi "jarak pendek", seperti matriks sistolik di jantung GPU.
Di sisi lain, sangat sulit untuk menulis perangkat lunak yang secara efektif menghasilkan bagian untuk input data dengan lokalitas yang buruk pada komputer serba guna (arsitektur von Neumann).
Sebagai hasilnya, kita dapat merumuskan heuristik sederhana:
Peluang menggunakan komputasi paralel berbanding terbalik dengan tingkat nonlocality semantik yang tidak dapat direduksi dalam data input.Keterbatasan lain dari komputasi paralel adalah bahwa beberapa algoritma penting tidak dapat diparalelkan sama sekali - bahkan secara teoritis. Ketika saya pertama kali membahas topik ini di blog saya, saya datang dengan istilah "algoritma sakit", di mana SICK adalah singkatan dari "Serial, Intrinscally - Cope, Kiddo!" Contoh penting termasuk: Algoritma Dijkstra untuk menemukan jalur terpendek; deteksi siklus dalam grafik terarah (menggunakan 3-SAT dalam solver); pencarian mendalam; menghitung anggota ke-n dalam rantai hash kriptografi; optimisasi aliran jaringan ... dan ini bukan daftar lengkap.
Buruknya lokasi data input juga memainkan peran di sini, terutama dalam konteks grafik dan struktur pohon. Rantai hash kriptografi tidak dapat diparalelkan, karena catatan dihitung dalam urutan yang ketat - ini benar-benar aturan penting untuk melindungi rantai dari pemalsuan.
Dan di sini kunci masuk: Anda tidak dapat memparalelkan apa pun saat algoritma SICK bekerja.
Kita belum selesai. Setidaknya ada dua kelas hambatan, dan yang sangat umum.
Pertama, tidak ada alat yang diperlukan. Sebagian besar bahasa tidak mendukung apa pun kecuali mutex dan semaphore. Ini nyaman, primitif mudah diimplementasikan, tetapi situasi ini menyebabkan ledakan kompleksitas yang mengerikan di kepala: hampir tidak mungkin untuk memahami skala lebih dari empat kunci yang saling berinteraksi.
Jika Anda beruntung, Anda akan mendapatkan kumpulan primitif yang lebih akomodatif, seperti saluran Go (alias Communicating Sequential Processes) atau sistem kepemilikan / kirim / sinkronisasi Rust. Tetapi pada kenyataannya, kita tidak tahu apa bahasa primitif “benar” untuk implementasi paralelisme pada arsitektur von Neumann. Mungkin tidak ada satu pun primitif yang benar. Mungkin dua atau tiga set berbeda cocok untuk area masalah yang berbeda, tetapi mereka tidak dapat dibandingkan sebagai unit dan akar kuadrat dari dua. Sampai saat ini, pada tahun 2018 tidak ada yang tahu.
Dan batasan terakhir, tetapi tidak kalah pentingnya adalah otak manusia. Bahkan pada algoritma yang jelas dengan lokalitas data yang baik dan alat yang efisien, pemrograman paralel cukup
sulit bagi orang-orang, bahkan jika algoritma tersebut diterapkan dengan cukup sederhana. Otak kita tidak memodelkan ruang keadaan paling sederhana dari program sekuensial murni, dan terutama yang paralel.
Kami tahu ini karena ada banyak bukti nyata bahwa debugging kode paralel lebih dari sulit. Hal ini terhambat oleh kondisi ras, kebuntuan, kunci penghancur diri, korupsi data berbahaya karena urutan instruksi yang sedikit tidak aman.
Saya pikir memahami batasan-batasan ini menjadi lebih penting setelah runtuhnya
hukum penskalaan Dennard . Karena semua hambatan dalam pemrograman ini, bagian dari sistem multi-core akan selalu menjalankan perangkat lunak yang tidak dapat memuat peralatan dengan daya komputasi 100%. Jika Anda melihat dari sisi lain, kami memiliki kelebihan besi untuk tugas saat ini. Berapa banyak uang dan usaha yang kita buang?
Produsen prosesor ingin Anda melebih-lebihkan manfaat fungsional dari chip baru yang cerdas dengan core lebih banyak lagi. Bagaimana lagi mereka dapat mengumpulkan uang untuk menutupi biaya produksi raksasa, sambil tetap menguntungkan? Pemasaran melakukan yang terbaik sehingga Anda tidak pernah bertanya-tanya tugas-tugas multithreading apa yang benar-benar bermanfaat.
Jujur, ada tugas seperti itu. Server di pusat data yang memproses ratusan ribu transaksi bersamaan per detik cenderung mendistribusikan beban dengan cukup baik di seluruh inti. Ponsel cerdas atau sistem tertanam, juga - dalam kedua kasus, upaya signifikan dilakukan untuk meminimalkan biaya dan konsumsi energi, yang membuatnya sulit untuk meminta kelebihan daya.
Tetapi untuk pengguna desktop dan laptop biasa? Keraguan yang samar menyiksaku. Sulit untuk memahami situasi di sini, karena peningkatan nyata dalam produktivitas berasal dari faktor-faktor lain, seperti transisi dari HDD ke SSD. Prestasi seperti itu mudah keliru untuk efek mempercepat CPU, jika Anda tidak melakukan profiling menyeluruh.
Berikut adalah alasan untuk kecurigaan tersebut:
- Komputasi paralel yang serius pada komputer desktop / laptop hanya terjadi pada GPU.
- Lebih dari dua core dalam sebuah prosesor biasanya tidak berguna. Sistem operasi dapat mendistribusikan aliran aplikasi, tetapi perangkat lunak biasa tidak dapat menggunakan paralelisme, dan sebagian besar pengguna jarang berhasil secara bersamaan meluncurkan sejumlah besar aplikasi yang berbeda yang mengkonsumsi banyak sumber daya CPU untuk memuat peralatan mereka secara penuh.
- Akibatnya, sebagian besar sistem quad-core melakukan sebagian besar waktu hanya menghasilkan panas.
Di antara para pembaca saya, ada banyak orang yang cenderung dapat mengomentari hipotesis ini secara wajar. Sangat menarik untuk melihat apa yang mereka katakan.
PEMBARUAN Komentator di G + menunjukkan satu manfaat menarik dari prosesor multi-core: mereka mengkompilasi kode dengan sangat cepat. Kode sumber bahasa seperti C memiliki lokalitas yang baik: di sini, unit yang dipisahkan dengan baik (file sumber) dikompilasi menjadi file objek, yang kemudian digabungkan oleh linker.