View source for Concurrency & Parallelism

== Dua tuntutan abadi ==

Sepanjang sejarah komputer digital, ada dua tuntutan yang jadi pendorong tetap perbaikan:

# kita ingin komputer '''melakukan lebih banyak'''
# kita ingin komputer '''berjalan lebih cepat'''

Keduanya membaik ketika processor '''mengerjakan lebih banyak hal sekaligus'''.

== Concurrency vs parallelism ==

Ini definisi yang wajib dipegang, dan bukunya memisahkan keduanya dengan tegas:

; Concurrency
: Konsep umum tentang '''sistem dengan banyak aktivitas yang simultan'''.
; Parallelism
: '''Penggunaan concurrency untuk membuat sistem berjalan lebih cepat'''.

{{Warning|title=Bukan sinonim, bukan juga lawan|Parallelism adalah ''bagian dari'' concurrency, bukan istilah sejajar. Concurrency menjawab pertanyaan "apakah sistem mengurus banyak hal sekaligus", parallelism menjawab "apakah keserentakan itu dipakai untuk mempercepat". Sistem bisa concurrent tanpa parallel — misalnya uniprocessor yang bergantian antar process.}}

Parallelism bisa dimanfaatkan pada '''beberapa tingkat abstraksi'''. Buku menyoroti tiga, dari yang tertinggi ke terendah:

{| class="wikitable"
! Tingkat !! Siapa yang mengatur
|-
| Thread-level concurrency || Programmer dan OS
|-
| Instruction-level parallelism || Hardware, otomatis
|-
| SIMD parallelism || Programmer dan compiler ||
|}

= Thread-Level Concurrency =

== Dari process ke thread ==

Berdiri di atas abstraksi [[process|process]], kita bisa merancang sistem tempat '''beberapa program berjalan pada saat yang sama'''. Dengan [[Threads|thread]], kita bahkan bisa punya '''beberapa alur kontrol di dalam satu process'''.

Dukungan untuk eksekusi concurrent sudah ada sejak munculnya '''time-sharing di awal 1960-an'''. Secara tradisional, eksekusi concurrent itu cuma '''disimulasikan''' — satu komputer berpindah cepat di antara process-process yang sedang berjalan, seperti pemain sulap yang menjaga beberapa bola tetap melayang di udara.

Bentuk concurrency ini memungkinkan:

* '''banyak user berinteraksi dengan satu sistem sekaligus''' — misalnya banyak orang meminta halaman dari satu Web server
* '''satu user mengerjakan banyak tugas sekaligus''' — browser di satu jendela, word processor di jendela lain, sambil memutar musik

== Uniprocessor dan multiprocessor ==

Sampai belum lama ini, sebagian besar komputasi nyata dikerjakan '''satu processor''', meski processor itu harus bergantian antar tugas. Konfigurasi ini disebut '''uniprocessor system'''.

Ketika kita membangun sistem yang terdiri dari '''beberapa processor, semuanya di bawah kendali satu kernel operating system''', itu disebut '''multiprocessor system'''. Sistem seperti ini sudah tersedia untuk komputasi skala besar sejak '''1980-an''', tapi baru jadi umum belakangan berkat multi-core dan hyperthreading.

=== Taksonomi (Figure 1.16) ===

<pre>
+-------------------------------------------------------+
| All processors                                        |
|                                                       |
| +------------------+  +-----------------------------+ |
| |                  |  | Multiprocessors             | |
| | Uniprocessors    |  |                             | |
| |                  |  |  +------------+ +---------+ | |
| |                  |  |  | Multi-core | | Hyper-  | | |
| |                  |  |  |            | | threaded| | |
| |                  |  |  +------------+ +---------+ | |
| +------------------+  +-----------------------------+ |
+-------------------------------------------------------+
</pre>

Perhatikan bahwa multi-core dan hyperthreaded '''dua-duanya masuk kategori multiprocessor''' — dan keduanya bisa ada bersamaan di satu chip.

== Multi-core processor ==

Multi-core processor punya '''beberapa CPU (disebut "core") yang diintegrasikan ke satu chip sirkuit terpadu'''.

=== Organisasi (Figure 1.17) ===

<pre>
 Processor package
+---------------------------------------------------------+
|  Core 0                              Core 3             |
|  +-------------------+               +----------------+ |
|  |       Regs        |               |      Regs      | |
|  +---------+---------+     . . .     +--------+-------+ |
|  | L1 d-$  | L1 i-$  |               | L1 d-$ | L1 i-$| |
|  +---------+---------+               +--------+-------+ |
|  |  L2 unified cache |               | L2 unified $   | |
|  +-------------------+               +----------------+ |
|                                                         |
|  +---------------------------------------------------+  |
|  |   L3 unified cache (dibagi semua core)            |  |
|  +---------------------------------------------------+  |
+---------------------------------------------------------+
                          |
                 +------------------+
                 |   Main memory    |
                 +------------------+
</pre>

Yang perlu dibaca dari gambar ini:

* Chip contohnya punya '''empat core'''.
* Tiap core punya '''L1 dan L2 cache sendiri'''.
* '''L1 dipecah dua''': satu menampung instruksi yang baru diambil, satu menampung data.
* Core '''berbagi level cache yang lebih tinggi''' (L3) serta '''antarmuka ke main memory'''.

Pakar industri memperkirakan akan ada '''puluhan, dan akhirnya ratusan core''' dalam satu chip.

{{Catatan|title=Kenapa L1 dipecah, L2 tidak|L1 dipisah instruksi dan data supaya processor bisa mengambil instruksi dan mengakses data dalam siklus yang sama tanpa saling menunggu. Di level L2 ke atas tekanannya sudah tidak sebesar itu, jadi cukup satu cache terpadu (''unified'').}}

== Hyperthreading ==

'''Hyperthreading''', kadang disebut '''simultaneous multi-threading (SMT)''', adalah teknik yang memungkinkan '''satu CPU mengeksekusi beberapa alur kontrol'''.

Caranya: '''menduplikasi sebagian hardware CPU''' sambil tetap '''menyisakan satu salinan untuk bagian lainnya'''.

{| class="wikitable"
! Diduplikasi !! Tetap satu salinan
|-
| Program counter || Unit aritmetika floating-point
|-
| Register file || (dan unit eksekusi lain)
|}

Perbedaan kecepatannya dramatis:

* Processor konvensional butuh sekitar '''20.000 clock cycle''' untuk berpindah antar thread.
* Processor hyperthreaded memutuskan thread mana yang dieksekusi '''pada basis siklus per siklus'''.

Ini memungkinkan CPU memanfaatkan sumber daya pemrosesannya lebih baik. Contohnya: kalau satu thread harus menunggu data dimuat ke cache, CPU bisa lanjut mengeksekusi thread lain.

Contoh dari buku: '''Intel Core i7''' bisa menjalankan dua thread per core, sehingga sistem empat core sebenarnya mengeksekusi '''delapan thread secara paralel'''.

{{Warning|title=Thread software vs thread hardware|Kata "thread" di sini berbeda makna dengan thread di [[Threads|§1.7.2]]. Thread di §1.7.2 adalah konsep OS yang dibuat programmer dan jumlahnya dinamis. Thread di hyperthreading adalah konsep hardware — set register dan PC yang diduplikasi di silikon, jumlahnya tetap dari pabrik. Analoginya: thread hardware adalah ''kursi'', thread software adalah ''orang yang duduk''. Inilah kenapa <code>nproc</code> di mesin 8 core melaporkan 16.}}

== Dua cara multiprocessing meningkatkan performa ==

# '''Mengurangi kebutuhan menyimulasikan concurrency''' saat mengerjakan banyak tugas. Bahkan komputer pribadi dengan satu pengguna tetap diharapkan melakukan banyak aktivitas sekaligus.
# '''Menjalankan satu program aplikasi lebih cepat''' — '''tapi hanya jika''' program itu dinyatakan dalam bentuk beberapa thread yang bisa benar-benar dieksekusi secara paralel.

Syarat pada poin kedua itu penting. Menambah core '''tidak otomatis''' mempercepat program yang ditulis single-threaded.

Prinsip concurrency sudah dirumuskan dan dipelajari lebih dari '''50 tahun''', tapi kehadiran sistem multi-core dan hyperthreaded sangat meningkatkan kebutuhan menemukan cara menulis program yang bisa memanfaatkan '''thread-level parallelism''' yang disediakan hardware.

= Instruction-Level Parallelism =

Pada tingkat abstraksi yang jauh lebih rendah, processor modern bisa '''mengeksekusi beberapa instruksi sekaligus'''. Sifat ini disebut '''instruction-level parallelism (ILP)'''.

Perbandingan angkanya:

{| class="wikitable"
! Processor !! Laju eksekusi
|-
| Intel 8086 (1978) || butuh '''3–10 clock cycle''' untuk '''satu''' instruksi
|-
| Processor modern || mempertahankan '''2–4 instruksi per clock cycle'''
|}

Yang mengejutkan: instruksi mana pun tetap butuh '''20 siklus atau lebih''' dari awal sampai selesai. Processor cuma memakai berbagai trik cerdas untuk '''memproses sampai 100 instruksi sekaligus''' dalam berbagai tahap penyelesaian.

== Pipelining ==

Dibahas di '''Bab 4'''. Idenya: tindakan yang dibutuhkan untuk mengeksekusi sebuah instruksi '''dipartisi jadi beberapa langkah''', dan hardware processor disusun sebagai '''rangkaian stage''', masing-masing mengerjakan satu langkah.

Stage-stage itu bisa '''beroperasi paralel''', mengerjakan bagian berbeda dari instruksi yang berbeda. Desain hardware yang cukup sederhana pun bisa mempertahankan laju eksekusi mendekati '''1 instruksi per clock cycle'''.

== Superscalar ==

Processor yang bisa mempertahankan laju eksekusi '''lebih cepat dari 1 instruksi per siklus''' disebut '''superscalar'''. Sebagian besar processor modern mendukung operasi superscalar.

Bab 5 menjelaskan model tingkat tinggi processor semacam ini — dan poin pentingnya: '''programmer aplikasi bisa memakai model itu untuk memahami performa programnya''', lalu menulis program supaya kode yang dihasilkan mencapai ILP lebih tinggi dan berjalan lebih cepat.

{{Catatan|ILP berjalan '''otomatis tanpa diminta'''. Programmer tidak menulis kode khusus untuk mengaktifkannya. Tapi programmer ''bisa'' menulis kode yang menghalanginya — misalnya rantai ketergantungan data yang panjang atau cabang yang sulit diprediksi.}}

= SIMD Parallelism =

Pada tingkat terendah, banyak processor modern punya hardware khusus yang memungkinkan '''satu instruksi menyebabkan beberapa operasi dilakukan secara paralel'''. Mode ini disebut '''single-instruction, multiple-data (SIMD) parallelism'''.

Contoh dari buku: generasi terbaru processor Intel dan AMD punya instruksi yang bisa '''menjumlahkan 8 pasang bilangan floating-point presisi tunggal''' (tipe data C <code>float</code>) secara paralel.

Instruksi SIMD ini '''terutama disediakan untuk mempercepat aplikasi yang memproses data gambar, suara, dan video'''.

== Cara memakainya ==

* Sebagian compiler '''berusaha mengekstrak SIMD secara otomatis''' dari program C.
* Metode yang '''lebih andal''' adalah menulis program memakai '''tipe data vector khusus''' yang didukung compiler seperti <code>gcc</code>.

Gaya pemrograman ini dijelaskan di Web Aside <code>opt:simd</code>, sebagai pelengkap pembahasan optimasi program di Bab 5.

= Catatan untuk kerja systems =

* '''Tiga level itu berlipat, bukan bergantian.''' Program yang dioptimalkan baik memanfaatkan ketiganya sekaligus: beberapa thread di beberapa core, tiap thread memanfaatkan superscalar, tiap instruksi memproses banyak elemen lewat SIMD. Faktor percepatannya berkalian.
* '''Auto-vectorization butuh diverifikasi, jangan diasumsikan.''' Di GCC dan Clang, <code>-O3 -march=native</code> mengaktifkan vektorisasi otomatis, tapi hasilnya sering gagal karena ''pointer aliasing'' atau alur kontrol di dalam loop. Cek dengan <code>-fopt-info-vec-missed</code> untuk melihat loop mana yang ditolak dan alasannya. Ini alasan buku menyebut menulis eksplisit lebih andal.
* '''SIMD sekarang jauh lebih lebar dari contoh di buku.''' Contoh "8 float sekaligus" itu setara AVX (256-bit). AVX-512 memproses 16 float sekaligus, dan ARM punya NEON serta SVE. Lebar vektor jadi parameter yang harus dipertimbangkan, bukan konstanta.
* '''Ukur IPC sebelum mengoptimalkan.''' <code>perf stat ./program</code> menampilkan ''instructions per cycle''. Angka di bawah 1 biasanya menandakan program terhambat memory atau salah prediksi cabang, bukan kekurangan compute — dan menambahkan SIMD ke program yang ''memory-bound'' tidak akan menolong.
* '''SMT bukan percepatan gratis.''' Dua thread hardware pada satu core berbagi unit eksekusi, L1, dan L2. Untuk beban kerja yang sering menunggu memory, SMT menguntungkan. Untuk beban kerja compute-bound padat seperti loop AVX, keduanya justru berebut sumber daya yang sama. Ini alasan SMT sering dimatikan di lingkungan HPC — keputusannya berdasarkan pengukuran, bukan preferensi.
* '''Hati-hati saat melakukan pinning.''' Karena satu core fisik menyumbang dua logical CPU, mem-''pin'' dua thread compute-heavy ke CPU 0 dan CPU 1 bisa saja berarti mengunci keduanya ke core fisik yang sama. Periksa topologi lebih dulu dengan <code>lscpu -e</code> atau <code>hwloc-ls</code>.
* '''Syarat pada poin kedua multiprocessing adalah inti Amdahl.''' Percepatan hanya datang dari bagian yang bisa diparalelkan. Bagian serial program menjadi batas atas yang tidak bisa dilewati berapa pun jumlah core yang ditambahkan.

{{Tip|Tiga perintah untuk melihat ketiga level sekaligus: <code>lscpu -e</code> untuk topologi thread-level, <code>perf stat -e instructions,cycles ./prog</code> untuk ILP, dan <code>objdump -d ./prog {{!}} grep -E 'vadd{{!}}vmul'</code> untuk memastikan instruksi SIMD benar-benar dihasilkan.}}

== Istilah kunci ==

; Concurrency
: Konsep umum sistem dengan banyak aktivitas simultan.
; Parallelism
: Penggunaan concurrency untuk membuat sistem berjalan lebih cepat.
; Uniprocessor system
: Sistem dengan satu processor yang bergantian antar tugas.
; Multiprocessor system
: Sistem dengan beberapa processor di bawah kendali satu kernel OS.
; Multi-core processor
: Beberapa CPU (core) yang diintegrasikan ke satu chip sirkuit terpadu.
; Hyperthreading
: Teknik yang memungkinkan satu CPU mengeksekusi beberapa alur kontrol dengan menduplikasi sebagian hardware seperti PC dan register file; disebut juga simultaneous multi-threading.
; Instruction-level parallelism
: Kemampuan processor mengeksekusi beberapa instruksi sekaligus.
; Pipelining
: Pembagian eksekusi instruksi jadi beberapa stage yang bisa beroperasi paralel.
; Superscalar
: Processor yang mempertahankan laju eksekusi lebih dari 1 instruksi per siklus.
; SIMD parallelism
: Mode ketika satu instruksi menyebabkan beberapa operasi dilakukan paralel.

== Lihat juga ==

* [[Process]]
* [[Threads]]
* [[Virtual Memory]]
* [[Files]]