Apakah ada sesuatu yang HARUS dilakukan pada CPU multi-core?

Ketika mempertimbangkan bagaimana multi-thread-friendly program kami harus, tim saya bingung tentang apakah ada sesuatu yang benar - benar tidak dapat dilakukan pada CPU single-core. Saya berpendapat bahwa pemrosesan grafis memerlukan pemrosesan paralel secara besar-besaran, tetapi mereka berpendapat bahwa hal-hal seperti DOOM dilakukan pada CPU single-core tanpa GPU.

Apakah ada sesuatu yang harus dilakukan pada prosesor multi-core?

Asumsikan ada waktu tak terbatas untuk pengembangan dan berjalan.

Jika Anda tidak peduli dengan waktu pengoperasian, apa pun yang dapat Anda lakukan pada mesin multi-core, Anda dapat melakukannya pada mesin single-core. Mesin multi-inti hanyalah cara mempercepat beberapa jenis perhitungan.

Jika Anda dapat memecahkan masalah dalam waktu pada mesin multi-core dengan core, maka Anda dapat menyelesaikannya waktu (atau kurang melihat hukum Amdahl ) pada mesin single-core. Mesin single-core dapat meniru mesin multi-core menggunakan time-slicing / time-sharing .n ∼ T $T$$n$$\sim Tn$

Pertanyaannya adalah: di bawah kendala apa?

Pasti ada masalah di mana, jika kita mengajukan pertanyaan "dapatkah kita memecahkan masalah ini pada perangkat keras X dalam jumlah waktu yang diberikan", jawabannya adalah tidak.

Tapi ini bukan jawaban "masa depan-bukti": hal-hal yang di masa lalu tidak bisa dilakukan cukup cepat dalam satu inti mungkin bisa sekarang, dan kami tidak dapat memprediksi apa perangkat keras masa depan akan mampu.

Dalam hal komputabilitas, kita tahu bahwa Turing Machine single-tape mampu menghitung semua fungsi yang sama dengan komputer tunggal atau multi-core, jadi, selain runtime, tidak ada masalah bahwa komputer multi-core dapat menyelesaikan single-core tidak bisa.

Dalam hal sesuatu seperti grafis, secara harfiah semua yang ada pada GPU dapat dilakukan pada CPU ... jika Anda bersedia menunggu cukup lama.

Seperti yang ditunjukkan oleh jawaban lain, satu CPU selalu dapat meniru banyak CPU dengan memotong waktu dan memainkan peran masing-masing CPU virtual. Persaingan ini tentu saja akan menghitung jawaban yang benar.

Di dunia nyata, waktu eksekusi mungkin penting. Ini bisa berarti perbedaan antara frame rate yang biasa-biasa saja dan pengalaman visual bintang. Atau perbedaan antara laba dan rugi dalam perdagangan.

Satu situasi patologis di mana multiprosesor jauh lebih cepat daripada uniprosesor adalah di mana pemrosesan adalah pipa data, pengalihan konteks mahal, dan kode mesin untuk setiap tahap pipa hanya pas di cache CPU.

Biarkan saya ilustrasikan dengan beberapa angka. Misalkan Anda memiliki jalur pipa data (rendering 3D, dll.) Yang memiliki 4 tahap pemrosesan, setiap tahap memiliki kode program 256 KiB, dan Anda dengan mudah memiliki 4 CPU dengan cache L2 256 KiB. Jika Anda mencoba menjalankan pemrosesan ini pada satu CPU, beralih di antara 4 tugas akan mahal dan melibatkan kesalahan cache yang berat. Di sisi lain, jika Anda menjalankannya pada sistem 4-core, perhitungan berpotensi menjadi sangat halus, cache misses minimal, dan konteks switch tidak ada. (Sebagai catatan, ini terkait dengan gagasan menyematkan aplikasi tertentu ke core tertentu - misalnya hanya melakukan operasi kernel OS dalam satu inti, atau penanganan TCP / IP, dll.)

Jauh lebih sulit untuk mengembangkan balapan data yang sangat jahat dengan satu CPU. Maksud saya, tentu saja, Anda dapat menarik antara kata-kata jika Anda mengganggu CPU tunggal, tetapi dapatkah Anda membuat skenario eksotis di mana tidak ada satu benang tunggal yang melakukan apa yang Anda inginkan?

Oke, mungkin membuat bug berbahaya tidak dianggap sebagai penggunaan multi-kode yang valid. Ternyata, tidak banyak yang mutli-core dapat lakukan bahwa core tunggal tidak dapat memberikan waktu. Alasannya sederhana. Jika Anda mencoba menghindari ras data jahat itu, Anda harus memiliki titik sinkronisasi dalam kode Anda. Jika Anda memodelkan kode Anda sebagai kisi perhitungan di mana input yang harus lengkap dan disinkronkan sebelum Anda dapat menghitung dan menghasilkan output, mudah untuk melihat bahwa satu CPU dapat dengan mudah berjalan di sepanjang kisi, menghitung blok kerja berikutnya yang tersedia .

Bahkan, jika Anda dapat menunjukkan bahwa algoritme Anda dapat diselesaikan dengan mesin Turing (yang hampir setiap algoritma yang kami pedulikan), dapat dibuktikan bahwa algoritme dapat dilakukan dengan tidak hanya satu CPU inti, tetapi pada kenyataannya mesin negara dengan selembar sangat panjang untuk memori!

The CHESS detektor lomba sebenarnya memanfaatkan ini untuk menemukan kasus ras. Ini menjalankan semua yang dilakukan secara singlethread dan secara sistematis mengeksplorasi semua interleaves yang mungkin di antara utas, mencoba menemukan kasus di mana tes gagal karena kasus ras. CHESS tergantung pada kenyataan bahwa Anda dapat menjalankan aplikasi multithreaded pada satu inti.

Kasus-kasus di mana Anda memerlukan multicore muncul ketika Anda mulai memperluas batas-batas perangkat keras. Yang jelas adalah ketika Anda memiliki keterbatasan waktu. Beberapa masalah dengan batasan waktu nyata tidak mungkin dilakukan dengan satu inti karena mereka tidak bisa menggerakkan jam satu inti dengan cukup cepat. Ada alasan mengapa CPU naik ke 4Ghz dan kemudian duduk sedikit, lebih memilih core lebih banyak pada kecepatan yang lebih rendah.

Versi yang lebih eksotis dari batasan waktu ini adalah dalam sistem waktu nyata yang sulit. Dalam beberapa sistem waktu nyata yang sulit, layanan interupsi sangat menuntut sehingga Anda benar-benar harus memilih CPU multi-core yang memungkinkan Anda membagi interupsi di seluruh core, atau Anda mengalami keterbatasan waktu.

Batas lain muncul dengan bus data. Pertimbangkan Blue Gene / P sebagai contoh. JUGENE, superkomputer Blue Gene / P tertentu, memiliki memori 144 terabyte . Mereka tidak membuat komputer CPU tunggal yang dapat mengakses semua memori itu.

Jika Anda perlu mengamati proses yang berjalan pada elemen pemrosesan tunggal tanpa mengganggu perilakunya yang real-time (atau sesedikit mungkin), seperti untuk pembandingan atau pencatatan aktivitas, Anda mungkin memerlukan sumber daya pemrosesan yang terpisah.

Jawaban lain mematuhi pandangan terbatas paralelisme sebagai "concurrency terdistribusi". Ini memberikan beberapa jawaban: dalam model komputasi yang bersih à la Turing, banyak core tidak menawarkan keuntungan; satu-satunya keuntungan yang Anda dapatkan adalah efisiensi.

Ada yang satu hal beberapa unit pengolahan (nanah) bisa melakukan itu satu pun tidak bisa, meskipun: melaksanakan operasi secara paralel , yaitu pada saat yang sama .

Itu sangat berguna jika Anda menjalankan banyak program secara bersamaan. Memang, jarang Anda benar-benar membutuhkan lebih dari eksekusi bersamaan, dan sebagian besar kegunaan meningkatkan efisiensi. Tapi ada adalah perbedaan ini.

Katakanlah Anda perlu memproses data sensor data dari berbagai sumber secara real time. Apa pun artinya dalam aplikasi Anda, satu PU hanya dapat menangani begitu banyak input stream bersamaan tanpa melanggar batas waktu responsnya. Jadi Anda perlu beberapa PU setelah Anda memiliki terlalu banyak sensor untuk generasi PU Anda saat ini.

Di ranah yang lebih klasik, salah satu contoh yang meyakinkan adalah algoritma portofolio . Katakanlah Anda memiliki masalah yang menyebabkan Anda memiliki banyak algoritma (misalkan ) dengan biaya ortogonal; kasus yang baik dari satu adalah kasus yang buruk untuk orang lain. Anda tidak dapat dengan cepat mengetahui mana yang terbaik untuk input yang diberikan.$k$

Anda dapat menjalankan semua algoritma secara paralel dan batalkan setelah satu selesai. Jika Anda memiliki setidaknya PU, Anda mendapatkan waktu berjalan minimum di antara semua algoritma dalam portofolio. Dengan hanya satu PU, Anda akan mendapatkan kali itu, dengan asumsi penjadwal yang adil, ditambah semua overhead.k $k$$k$$k$

dari pov CS, "multicore" tidak jauh berbeda dalam teori daripada "komputasi terdistribusi". konsep dasarnya adalah "elemen komputasi independen (yang menghitung secara paralel". sehingga sedikit mengulangi pertanyaan ("multicore" sebenarnya bukan konsep teoretis dalam CS) mengarah ke beberapa kemungkinan lain. seperti yang ditunjukkan dalam jawaban lain, pemrograman berurutan adalah setara dengan pemrograman paralel dari pov CS. Ini kembali ke definisi sistem teoritis untuk komputasi, yaitu mesin Turing. Analisis teoritis kinerja CS pada akhirnya dalam hal TMs di mana perbedaan paralel vs sekuensial tidak benar-benar berlaku ( meskipun ada beberapa analogi kasar dengan TM multitape ).

tetapi mengingat pertanyaan ini kurang abstrak, komputasi terdistribusi memang unggul atau bahkan mungkin hampir diperlukan untuk beberapa masalah yang melibatkan toleransi kesalahan . di area ini ada konsep yang berlaku ketika / di mana elemen-elemen komputasi independen dianggap memiliki tingkat tidak dapat diandalkan (ini bukan asumsi yang berlaku universal untuk semua konteks). berikut adalah beberapa kasus di mana toleransi kesalahan ditingkatkan dengan atau bahkan membutuhkan elemen komputasi independen.

• pertimbangkan bahwa setiap prosesor memiliki peluang independen "[x]%" untuk gagal selama perhitungan. suatu sistem dapat dirancang dimana melalui komunikasi toleransi kesalahan keseluruhan sistem lebih unggul dari komponen individu. ini telah diterapkan beberapa dekade yang lalu misalnya dalam sistem Space Shuttle. baru-baru ini ada protokol dasar yang dirancang untuk menggunakannya misalnya Paxos yang memecahkan apa yang disebut masalah konsensus . contoh yang lebih sederhana adalah Google yang memiliki banyak algoritme berpemilik untuk dasarnya membangun superkomputer mereka dari elemen-elemen yang tidak dapat diandalkan secara individual ditambah dengan algoritma toleran-kesalahan.

• Bitcoin melibatkan transaksi terdistribusi untuk menghitung buku besar dan itu bukan hanya karena masalah pemrosesan semata. Algoritma dirancang dengan hati-hati untuk menggagalkan node yang rusak. singkatnya "memecahkan" / mengimplementasikan masalah jenderal Bizantium yang bukan hanya tentang memaksimalkan kinerja paralel, itu melibatkan entitas independen "memeriksa" satu sama lain dan "secara algoritmik / kriptografis / aman" menolak perhitungan yang tidak valid alias semacam "curang" atau " korupsi".

• analisis klasik tentang paralelisme menyimpulkan ada sekitar 7 jenis pola masalah "mendasar" yang terurai menjadi gangguan eksekusi paralel tertentu. lihat The Landscape of Parallel Computing Research: A View from Berkeley

• ada beberapa elemen pertanyaan teoretis terbuka di sini pertimbangan kinerja yang dibahas dalam sebagian besar jawaban lain. pertanyaan apakah ada masalah yang "secara inheren lebih cepat" secara paralel daripada berurutan juga dikenal secara kasar sebagai masalah P =? NC di mana NC dianggap sebagai kelas dari algoritma "paralel yang efisien" dan P adalah "efisien [berurutan] algoritma "