Mengapa menggunakan lebih banyak utas membuatnya lebih lambat daripada menggunakan lebih sedikit utas

30

Mencoba menjalankan program X menggunakan 8 utas dan selesai dalam n menit .
Mencoba menjalankan program yang sama menggunakan 50 utas dan selesai dalam n * 10 menit .

Mengapa ini terjadi dan bagaimana saya bisa mendapatkan jumlah utas optimal yang dapat saya gunakan?

multithreading PoGibas
sumber

Jawaban:

33

Ini pertanyaan rumit yang Anda ajukan. Tanpa mengetahui lebih lanjut tentang sifat utas Anda, sulit untuk mengatakannya. Beberapa hal yang perlu dipertimbangkan ketika mendiagnosis kinerja sistem:

Apakah proses / utas

  • Terikat CPU (membutuhkan banyak sumber daya CPU)
  • Memori terikat (membutuhkan banyak sumber daya RAM)
  • I / O terikat (Sumber daya jaringan dan / atau hard drive)

Ketiga sumber daya ini terbatas dan siapa pun dapat membatasi kinerja sistem. Anda perlu melihat yang mana (mungkin 2 atau 3 bersama) situasi khusus Anda mengkonsumsi.

Anda dapat menggunakan ntopdan iostat, serta vmstatuntuk mendiagnosis apa yang sedang terjadi.

slm
sumber
8
Perangkat keras juga penting. Fisik, virtual, jumlah inti, jenis inti, cache L1 / L2 / L3, dll.
EightBitTony
46

"Mengapa ini terjadi?" agak mudah dijawab. Bayangkan Anda memiliki koridor yang dapat memuat empat orang, berdampingan. Anda ingin memindahkan semua sampah di satu ujung, ke ujung lainnya. Jumlah orang yang paling efisien adalah 4.

Jika Anda memiliki 1-3 orang maka Anda kehilangan menggunakan beberapa ruang koridor. Jika Anda memiliki 5 orang atau lebih, maka setidaknya salah satu dari orang-orang itu pada dasarnya terjebak mengantri di belakang orang lain sepanjang waktu. Menambahkan semakin banyak orang hanya menyumbat koridor, itu tidak mempercepat aktivitas.

Jadi, Anda ingin memiliki sebanyak mungkin orang yang bisa masuk tanpa menyebabkan antrian. Mengapa Anda memiliki antrian (atau kemacetan) tergantung pada pertanyaan dalam jawaban slm.

EightBitTony
sumber
1
Teladan Anda menyesatkan. Akan lebih baik untuk mengatakan sesuatu seperti: "Anda memiliki koridor yang dapat Anda masukkan empat orang ke bawah, berdampingan dan digunakan oleh Anda dan orang lain untuk tugas yang berbeda. Ada wasit yang memutuskan siapa yang dapat melewati koridor. Lalu jumlah orang yang paling efisien adalah lebih besar dari 4 dan lebih sedikit dari jumlah tertentu, di mana orang Anda mulai mengantri [sangat tergantung konteks]. " Biasanya memiliki beberapa utas lebih dari jumlah CPU berperforma lebih baik daripada menggunakan persis 4 utas. Jika Anda adalah satu - satunya yang menggunakan CPU, maka 4adalah angka terbaik.
Bakuriu
7
Contoh yang bagus, +1. Bakuriu, ini adalah contoh yang menggambarkan masalah sumber daya bersama yang terbatas. Ini menjelaskan masalahnya, bukan bagaimana menemukan jumlah utas yang optimal.
Bananguin
1
Ini juga akan berguna untuk diingat bahwa utas masih memiliki jenis pengalihan konteks sendiri yang berlangsung. Menambah jumlah utas tidak meningkatkan kapasitas kinerja (seperti yang Anda tunjukkan) tetapi juga menghabiskan waktu CPU dengan memberi lebih banyak pekerjaan pada kernel. Pada dasarnya, ada pengembalian yang menurun pada threading dan melakukan terlalu banyak menyebabkan kemunduran kinerja.
Bratchley
9
Setiap masalah dapat dijelaskan pada berbagai tingkat kompleksitas. Saya telah menawarkan perkiraan masalah, yang saya percaya berguna untuk menjelaskan dasar-dasarnya. Tentu saja bisa lebih disempurnakan, dan lebih rinci, tetapi semakin rinci Anda membuatnya, semakin tidak berguna sebagai pengantar masalah ini.
EightBitTony
Saya hanya akan menambahkan itu, alih-alih menghabiskan banyak waktu menghitung jumlah utas yang optimal, hanya kode itu sehingga dapat diubah dengan mudah. Penggabungan besar seperti ini akan membutuhkan banyak uji coba (kebanyakan dengan himpunan kecil data Anda) untuk menyempurnakan. Tingkatkan jumlah utas hingga Anda melihat penurunan besar dalam kinerja atau dampak pada aktivitas sistem lain tidak dapat diterima.
DocSalvager
20

Rekomendasi umum adalah n + 1 utas, n menjadi jumlah inti CPU yang tersedia. Dengan begitu n thread dapat bekerja pada CPU sementara 1 thread sedang menunggu disk I / O. Memiliki lebih sedikit utas tidak akan sepenuhnya memanfaatkan sumber daya CPU (pada titik tertentu akan selalu ada I / O untuk menunggu), memiliki lebih banyak utas akan menyebabkan utas memperebutkan sumber daya CPU.

Thread datang tidak gratis, tetapi dengan overhead seperti konteks switch, dan - jika data harus dipertukarkan antara thread yang biasanya terjadi - berbagai mekanisme penguncian. Ini hanya sepadan dengan biaya ketika Anda benar-benar memiliki inti CPU yang lebih berdedikasi untuk menjalankan kode. Pada CPU single core, proses tunggal (tanpa utas terpisah) biasanya lebih cepat daripada threading yang dilakukan. Utas tidak secara ajaib membuat CPU Anda lebih cepat, itu hanya berarti kerja ekstra.

frostschutz
sumber
Ini harus menjadi jawaban umum mengingat jumlah informasi yang tersedia dipertanyakan. kita tidak memerlukan tesis dan filosofi penuh seperti jawaban lain
Allahjane
9

Seperti yang telah ditunjukkan oleh orang lain ( jawaban slm , jawaban EightBitTony ) ini adalah pertanyaan yang rumit dan lebih lagi karena Anda tidak menggambarkan apa yang Anda lakukan dan bagaimana mereka melakukannya.

Tetapi secara definitif melemparkan lebih banyak utas dapat memperburuk keadaan.

Di bidang komputasi paralel ada hukum Amdahl yang dapat diterapkan (atau tidak bisa, tetapi Anda tidak menjelaskan detail masalah Anda, jadi ....) dan dapat memberikan wawasan umum tentang kelas masalah ini.

Inti hukum Amdahl adalah bahwa dalam program apa pun (dalam algoritma apa pun) selalu ada persentase yang tidak dapat dijalankan secara paralel (bagian berurutan ) dan ada persentase lain yang dapat dijalankan secara paralel (bagian paralel ) [Jelas dua bagian ini menambahkan hingga 100%].

Bagian ini dapat dinyatakan sebagai persentase dari waktu eksekusi. Sebagai contoh, bisa ada 25% waktu yang dihabiskan dalam operasi sekuensial ketat, dan 75% sisanya dihabiskan dalam operasi yang dapat dieksekusi secara paralel.

Gambar dari Wikipedia (Gambar dari Wikipedia )

Hukum Amdahl memperkirakan bahwa untuk setiap bagian paralel yang diberikan (misalnya 75%) dari suatu program Anda dapat mempercepat eksekusi sejauh ini (misalnya paling banyak 4 kali) bahkan jika Anda menggunakan lebih banyak prosesor untuk melakukan pekerjaan.

Sebagai aturan praktis, semakin banyak dari Anda memprogram yang tidak dapat Anda ubah dalam eksekusi paralel, semakin sedikit yang bisa Anda peroleh dengan menggunakan lebih banyak unit eksekusi (prosesor).

Mengingat Anda menggunakan utas (dan bukan prosesor fisik) situasinya bahkan bisa lebih buruk dari ini. Ingatlah bahwa utas dapat diproses (tergantung pada implementasi dan perangkat keras yang tersedia, mis. CPU / Cores) berbagi prosesor / inti fisik yang sama (ini adalah bentuk multitasking, seperti yang ditunjukkan dalam jawaban lain).

Prediksi teoretis ini (sekitar waktu CPU) tidak menganggap hambatan praktis lainnya sebagai

  1. Kecepatan I / O terbatas (hard disk dan "kecepatan" jaringan)
  2. Batas ukuran memori
  3. Lainnya

yang dapat dengan mudah menjadi faktor pembatas dalam aplikasi praktis.

DavAlPi
sumber
Ini harus dipilih jawaban.
Eonil
6

Pelakunya di sini adalah "KONTEKS BERALIH". Ini adalah proses menyimpan status utas saat ini untuk mulai mengeksekusi utas lainnya. Jika sejumlah utas diberi prioritas yang sama, mereka harus dialihkan hingga mereka menyelesaikan eksekusi.

Dalam kasus Anda, ketika ada 50 utas, banyak pergantian konteks terjadi bila dibandingkan dengan hanya menjalankan 10 utas.

Overhead waktu ini diperkenalkan karena pengalihan konteks yang membuat program Anda berjalan lambat

x-treme
sumber
Karena kita tidak tahu apa utasnya, ini sepertinya merupakan dugaan. Ya, pengalihan konteks menambahkan overhead, tetapi jika utas melakukan semacam analisis data, masalahnya bisa menjadi masalah cache (yaitu tidak dapat menggunakan cache karena setiap kali Anda mengganti utas Anda harus menyiramnya).
EightBitTony
Urutan konteks switching dalam dan dari dirinya sendiri , kecuali kita berhadapan dengan sejumlah besar switch konteks, kemungkinan tidak akan memiliki dampak urutan-besar pada kinerja. 50 utas tinggi tetapi tidak ekstrem (di kotak saya sekarang, ps ax | wc -lmelaporkan 225 proses, dan tidak berarti sangat dimuat). Saya cenderung untuk pergi dengan tebakan @ EightBitTony; cache cache kemungkinan masalah yang lebih besar, karena setiap kali Anda membersihkan cache, CPU harus menunggu ribuan tahun untuk kode dan data dari RAM.
CVn
3

Untuk memperbaiki metafora EightBitTony:

"Mengapa ini terjadi?" agak mudah dijawab. Bayangkan Anda memiliki dua kolam renang, satu penuh dan satu kosong. Anda ingin memindahkan semua air dari satu ke yang lain, dan memiliki 4 ember . Jumlah orang yang paling efisien adalah 4.

Jika Anda memiliki 1-3 orang maka Anda kehilangan beberapa ember . Jika Anda memiliki 5 orang atau lebih, maka setidaknya satu dari orang-orang itu terjebak menunggu ember . Menambahkan semakin banyak orang ... tidak mempercepat aktivitas.

Jadi, Anda ingin memiliki orang sebanyak yang dapat melakukan pekerjaan (menggunakan ember) secara bersamaan .

Seseorang di sini adalah utas, dan ember mewakili sumber daya eksekusi mana pun yang menjadi penghambatnya. Menambahkan lebih banyak utas tidak membantu jika tidak bisa melakukan apa pun. Selain itu, kita harus menekankan bahwa mengoper ember dari satu orang ke orang lain biasanya lebih lambat daripada satu orang yang hanya membawa ember dengan jarak yang sama. Yaitu, dua utas secara bergantian pada inti biasanya menghasilkan lebih sedikit pekerjaan daripada satu utas yang berjalan dua kali lebih lama: ini karena kerja ekstra yang dilakukan untuk beralih di antara kedua utas.

Apakah sumber daya eksekusi terbatas (bucket) adalah CPU, atau inti, atau pipa instruksi hyper-threaded untuk tujuan Anda tergantung pada bagian arsitektur mana yang menjadi faktor pembatas Anda. Perhatikan juga kami mengasumsikan utas sepenuhnya independen. Ini hanya terjadi jika mereka tidak membagikan data (dan menghindari tabrakan cache apa pun).

Seperti yang disarankan oleh beberapa orang, untuk I / O sumber daya pembatas mungkin adalah jumlah operasi I / O yang dapat antri: ini dapat bergantung pada sejumlah faktor perangkat keras dan kernel, tetapi dapat dengan mudah jauh lebih besar dari jumlah core. Di sini, saklar konteks yang sangat mahal dibandingkan dengan kode eksekusi-terikat, cukup murah dibandingkan dengan kode terikat I / O. Sedihnya saya pikir metafora akan sepenuhnya di luar kendali jika saya mencoba untuk membenarkan ini dengan ember.

Perhatikan bahwa perilaku optimal dengan kode terikat I / O biasanya masih memiliki paling banyak satu utas per pipa / inti / CPU. Namun, Anda harus menulis kode I / O asinkron atau sinkron / non-pemblokiran, dan peningkatan kinerja yang relatif kecil tidak selalu membenarkan kompleksitas tambahan.

PS. Masalah saya dengan metafora koridor asli adalah sangat menyarankan Anda harus dapat memiliki 4 antrian orang, dengan 2 antrian membawa sampah dan 2 kembali untuk mengumpulkan lebih banyak. Kemudian Anda dapat membuat setiap antrian hampir sepanjang koridor, dan menambahkan orang melakukan mempercepat algoritma (Anda pada dasarnya mengubah seluruh koridor ke ban berjalan).

Sebenarnya skenario ini sangat mirip dengan deskripsi standar tentang hubungan antara latensi dan ukuran jendela dalam jaringan TCP, itulah sebabnya ia melompat ke arah saya.

Tak berguna
sumber
Ini bukan metafora, ini adalah pendekatan yang dirancang untuk menjelaskan sistem kepada orang-orang dengan cara mereka dapat memvisualisasikannya dengan mudah. Karena itu, itu akan selalu 'dihancurkan' oleh orang-orang yang mengetahui tingkat detail selanjutnya, tetapi tidak menyadari level detail mereka sebenarnya tidak diperlukan untuk pemula. Tidak ada yang belajar fisika partikel dengan mulai dari tingkat PhD. Semua hal sebelumnya adalah perkiraan yang akan membawa Anda ke dalamnya secara bertahap, menyempurnakannya saat Anda pergi. Ini tidak 'salah' itu hanya bukan gambaran lengkapnya.
EightBitTony
Tidak ada yang bingung tentang kiasan mana yang Anda gunakan, dan itu bukan analogi yang buruk. Setiap analogi memiliki batas di luar yang menyimpang dari hal yang seharusnya dijelaskan dan tidak lagi berguna. Saya hanya menyebutkan ini karena aslinya mengingatkan saya begitu kuat pada skenario yang berbeda, dan karena saya tidak berpikir versi ini lebih rumit untuk (mudah-mudahan) meningkatkan prediksi.
berguna
0

Sangat mudah dan sederhana untuk dipahami. Memiliki lebih banyak utas daripada yang didukung CPU Anda, Anda benar-benar membuat serial dan tidak memparalelkan. Semakin banyak utas Anda, semakin lambat sistem Anda. Hasil Anda sebenarnya adalah bukti dari fenomena ini.

Bruno Taboada
sumber