Concurrency & Parallelism

Dua tuntutan abadi

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

1. kita ingin komputer melakukan lebih banyak
2. 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
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:

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, kita bisa merancang sistem tempat beberapa program berjalan pada saat yang sama. Dengan 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)

+-------------------------------------------------------+
| All processors                                        |
|                                                       |
| +------------------+  +-----------------------------+ |
| |                  |  | Multiprocessors             | |
| | Uniprocessors    |  |                             | |
| |                  |  |  +------------+ +---------+ | |
| |                  |  |  | Multi-core | | Hyper-  | | |
| |                  |  |  |            | | threaded| | |
| |                  |  |  +------------+ +---------+ | |
| +------------------+  +-----------------------------+ |
+-------------------------------------------------------+

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)

 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    |
                 +------------------+

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: 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.

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
Kata "thread" di sini berbeda makna dengan thread di §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 nproc di mesin 8 core melaporkan 16.

Dua cara multiprocessing meningkatkan performa

1. Mengurangi kebutuhan menyimulasikan concurrency saat mengerjakan banyak tugas. Bahkan komputer pribadi dengan satu pengguna tetap diharapkan melakukan banyak aktivitas sekaligus.
2. 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:

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 float) 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 gcc.

Gaya pemrograman ini dijelaskan di Web Aside opt:simd, 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, -O3 -march=native mengaktifkan vektorisasi otomatis, tapi hasilnya sering gagal karena pointer aliasing atau alur kontrol di dalam loop. Cek dengan -fopt-info-vec-missed 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. perf stat ./program 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 lscpu -e atau hwloc-ls.
• 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: lscpu -e untuk topologi thread-level, perf stat -e instructions,cycles ./prog untuk ILP, dan objdump -d ./prog | grep -E 'vadd|vmul' 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