Multiprocessor •Topik Hari Ini: Taksonomi Multiprocessor Snooping-based cache coherence protocol Directory-based cache coherence protocol Sinkronisasi Konsistensi Menulis parallel programs SMT Contoh Multi-core
1
Taksonomi Multiprocessor •SISD: single instruction and single data stream: uniprocessor •MISD: tdk ada multiprosesor komersialnya: bayangkan data melalui sebuah jalur pipa dari mesin - mesin eksekusi •SIMD: arsitektur vector: fleksibilitas lebih rendah •MIMD: kebanyakan multiprosesor sekarang: mudah dibagun dengan komputer-komputer off-the-shelf, sangat fleksibel
2
Organisasi Memori - I •Centralized shared-memory multiprocessor atau Symmetric shared-memory multiprocessor (SMP) •Prosesor multipel dihubungkan dengan sebuah memori terpusat tunggal - karena semua prosesor melihat organisasi memori yg sama uniform memory access (UMA) •Shared-memori karena semua prosesor dapat akses keseluruhan ruang di alamat memori •Mungkinkan memori terpusat berubah menjadi sebuah bandwidth bottleneck? - tidak jika anda memiliki cache yg •besar dan mempekerjakan dibawah selusin (12) prosesor 3
SMPs atau Centralized Shared-Memory
Processor
Processor
Processor
Processor
Caches
Caches
Caches
Caches
Main Memory
I/O System
4
Organisasi Memori - II •Utk skalabilitas yg lebih tinggi, memori didistribusikan diantara prosesor distributed memory multiprocessors •Jika sebuah prosesor dapat secara langsung melihat memori lokal dari prosesor lainnya, ruang alamatnya di-shared distributed shared-memory (DSM) multiprosesor •Jika memorinya hanya utk lokal, diperlukan pesan utk komunikasi data komputer klaster atau multikomputer •Non-uniform memory architecture (NUMA) karena memori lokal memiliki latensi yg lebih rendah dibandingkan memori jauh 5
Distributed Memory Multiprocessors
Processor & Caches Memory
I/O
Processor & Caches Memory
I/O
Processor & Caches Memory
I/O
Processor & Caches Memory
I/O
Interconnection network
6
SMPs - Memori utama terpusat dan banyak cache banyak kopi dari data yg sama - Sebuah sistem adalah cache coherent jika sebuah read mengembalikan nilai terlulis terkini dari word
Time Event Value of X in Cache-A 0 1 CPU-A reads X 1 2 CPU-B reads X 1 3 CPU-A stores 0 in X 0
Cache-B 1 1
Memory 1 1 1 0
7
Cache Coherence Sebuah sistem memori disebut koheren jika: •P menulis ke X; tidak ada prosesor lain menulis ke X; P membaca ke X dan menerima nilai yg sebelumnya ditulis oleh P •P1 menulis ke X; tidak ada prosesor lain menulis ke X; bbrp saat berlalu; P2 membaca X dan menerima nilai yg ditulis P1 •Dua write ke lokasi yg sama oleh dua prosesor dilihat dengan urutan yang sama oleh semua prosesor - write serialization •Model konsistensi memori mendefinisikan “waktu berlalu (time elapsed) sebelum effek dari sebuah prosesor dilihat yg lainnya 8
Protokol Koherensi Cache •Berbasis direktori: Sebuah lokasi tunggal (direktori) melacak status sharing dari sebuah memori blok •Snooping: Setiap blok cache didampingi oleh status sharing dari blok tsb - semua kontroler cache memonitor shared bus sehingga dapat meng-update status sharing dari blok, jika diperlukan Write-invalidate: sebuah prosesor mendapatkan akses eksklusif ari sebuah blok sebelum menulis dengan membuat invalid kopi yang lain Write-update: ketika sebuah prosesor menulis, it mengupdate shared kopi dari blok itu 9
Isu Desain •Tiga status dari sebuah blok: invalid, shared, modified •Sebuah write ditempatkan pada bus dan yg sharing (sharer) meng-invalidate diri sendiri
Processor
Processor
Processor
Processor
Caches
Caches
Caches
Caches
Main Memory
I/O System 10
Protokol Berbasis Snooping •Tiga status dari sebuah blok: invalid, shared, modified •Sebuah write ditempatkan di bus dan pembagi (sharer) meng-invalid diri sendiri •Protokol ini dinamakan sebagai MSI, MESI, dll Processor
Processor
Processor
Processor
Caches
Caches
Caches
Caches
Main Memory
I/O System 11
Contoh •P1 membaca X: tdk ketemu di cache-1, mengirimkan request di bus, memori menjawab, X ditempatkan di cache-1 dgn status shared •P2 membaca X: tdk ketemu di cache-2, mengirimkan request di bus, semua mengendus (snoop) request ini, cache-1 tdk berbuat apapun krn hanya request baca, memori menjawab, X ditempatkan di cache-2 dgn status shared P1
P2
Cache-1
Cache-2
Main Memory
•P1 menulis X: cache-1 memiliki data dlm status shared (shared hanya utk ijin baca), request dikirim di bus, cache-2 mengendus dan menginvalid kopi X miliknya, cache-1 berubah statu menjadi modified •P2 membaca X: cache-2 punya data dlm status invalid, request dikirim ke bus, cache-1 mengedus dan menyadari ia sendiri punya kopi yg valid, ia menurunkan statusnya sendiri menjadi shared dan menjawab dgn data, X ditempatkan di cache-2 dalam status shared 12
Koheren di Distributed Memory Multiprocs Sistem memori terdistribusi biasanya besar snooping berbasis bus mungkin tdk bekerja baik •
•Opsi 1: mekanisme berbasis software - sistem pertukaran pesan atau software-controlled cache coherence •
Opsi 2: mekanisme berbasis hardware - directory-based cache coherence
13
Distributed Memory Multiprocessors
Processor & Caches Memory
Directory
I/O
Processor & Caches Memory
Directory
I/O
Processor & Caches Memory
Directory
I/O
Processor & Caches Memory
I/O
Directory
Interconnection network
14
Directory-Based Cache Coherence •Memori fisik terdistribusi diantara semua prosesor •Direktori juga terdistribusi bersama dengan memori yang terkorespondensi •Memori fisik cukup untuk menentukan lokasi dari memori •Banyak simpul (node) proses dihubungkan dengan sebuah interkoneksi yang bisa skalabel (bukan bus) - jadi, pesan tidak di-broadcast, tapi disalurkan dari pengirim ke penerima - karena node yang memproses tidak lagi snoop, direktori melacak status sharingnya 15
Status dari Cache Block •Apakah jenis status dari memori blok yang bisa diperoleh di dalam direktori? •Catat bahwa kita membutuhkan informasi dari setiap cache sehingga pesan utk meng-invalidate dapat dikirimkan •Direktori sekarang berperan sebagai arbitrator: jika menulis berganda terjadi secara simultan, direktori yg menentukan urutannya
16
Contoh Directory-Based
Processor & Caches Memory
Directory
I/O
Processor & Caches Memory Directory X
I/O
Processor & Caches Memory Directory Y
I/O
A: Rd B: Rd C: Rd A: Wr A: Wr C: Wr B: Rd A: Rd A: Rd B: Wr B: Rd B: Wr B: Wr
X X X X X X X X Y X Y X Y
Interconnection network 17
Aksi dari Direktori •Jika blok dalam status uncached: Read miss: kirim data, menjadikan blok shared Write miss: kirim data, menjadikan blok eksklusif •Jika blok dalam status shared: Read miss: kirim data, tambah node di daftar sharer Write miss: kirim data, meng-invalid sharer, jadikan eksklusif •Jika blok dalam statu ekslusif: Read miss: meminta data ke pemilik, menulis ke memori, kirim data, menjadikan shared, tambah node ke daftar sharer Data write back: menulis ke memori, menjadikan uncached Write miss: meminta data ke pemilik, menulis ke memori, kirim data, update identitas pemilik yg baru, tetap eksklusif 18
Membangun Locks •Aplikasi - aplikasi memiliki fase - fase (terdiri dari banyak instruksi) yang harus dieksekusi secara atomik, tanpa proses paralel yg lain memodifikasi data •Sebuah lock (kunci) di sekitar data / kode menjamin bahwa hanya satu program dapat menjadi bagian kritis pada suatu waktu •Hardware harus menyediakan primitif yang dasar yg memungkinkan membangun lock dengan properti yg berbeda Bank balance $1000 Rd $1000 Add $100 Wr $1100
Parallel (unlocked) banking transactions
Rd $1000 Add $200 Wr $1200
19
Sinkronisasi •Primitif hardware paling sederhana yang memfasilitasi implementasi sinkronisasi (lock, barrier, dll) adalah sebuah read-modify-write yg atomik •Pertukaran atomik: pertukaran isi dari register dan memori •Kasus khusus dari pertukaran atomik: tes & set: transfer lokasi memori ke register dan menulis 1 ke memori (jika memori memiliki 0, lock-nya bebas) • lock:
t&s register, location bnz register, lock CS st location, #0
Ketika thread multipel paralel mengekskusi kode ini, hanya satu yang bisa masuk ke CS 20
Koherensi Vs. Konsistensi •Ingat bahwa koherensi menjamin (i) propagasi write (sebuah write akan kelihatan di prosesor lainnya), dan (ii) serialisasi write (semua prosesor melihat write ke lokasi yang sama dengan urutan yang sama). •Model konsistensi mendefinisikan pengurutan dari write dan read ke lokasi memori yang berbeda - hardware menjamin sebuah model konsistensi tertentu dan programer berusaha menulis program yang benar dengan asumsi - asumsi ini
21
Contoh Konsistensi •Perhatikan sebuah multiprosesor dengan koheresi cache berbasis snooping and sebuah write buffer antara CPU dan cache Initially A = B = 0 P1 P2 A1 B1 … … if (B == 0) if (A == 0) Crit.Section Crit.Section
Programer berharap kode diatas mengimplementasikan sebuah lock - karena write buffering, kedua prosesor dapat masuk ke bagian kritis Model konsistensi mempersilakan programer utk mengetahui asumsi apa yang dapat dibuat terhadap kemampuan pengurutan kembali dari 22 hardware
Konsistensi Sekuensial •Sebuah multiprosesor adalah konsisten secara sekuensial jika hasil dari eksekusi dapat dicapai dengan memelihara urutan program di dalam sebuah prosesor dan akses secara interleaving (bergantian) oleh prosesor yang berbeda dengan cara acak •Multiprosesor dalam contoh sebelumnya tidak konsisten secara sekuensial •Kita dapat mengimplementasi konsistensi sekuensial dengan mensyaratkan: urutan program, serialisasi write, semua telah melihat update sebelum sebuah nilai dibaca - sangat intuitif utk programmer, tapi berjalan sangat lambat 23
Shared-Memory Vs. Message-Passing Shared-memory: •Model program yang mudah dipahami •Komunikasi secara implisit dan hardware menangani proteksi •Caching dikontrol hardware Message-passing: •Tidak ada koheresi cache hardware lebih simpel •Komunikasi scr eksplisit lbh mudah bagi programer utk mengatur ulang kode •Caching dikontrol software •Pengirim (sender) dapat memulai transfer data 24
Ocean Kernel Procedure Solve(A) begin diff = done = 0; while (!done) do diff = 0; for i 1 to n do for j 1 to n do temp = A[i,j]; A[i,j] 0.2 * (A[i,j] + neighbors); diff += abs(A[i,j] – temp); end for end for if (diff < TOL) then done = 1; end while end procedure
.
Row 1
.
Row k
Row 2k
Row 3k …
25
Shared Address Space Model int n, nprocs; float **A, diff; LOCKDEC(diff_lock); BARDEC(bar1); main() begin read(n); read(nprocs); A G_MALLOC(); initialize (A); CREATE (nprocs,Solve,A); WAIT_FOR_END (nprocs); end main
procedure Solve(A) int i, j, pid, done=0; float temp, mydiff=0; int mymin = 1 + (pid * n/procs); int mymax = mymin + n/nprocs -1; while (!done) do mydiff = diff = 0; BARRIER(bar1,nprocs); for i mymin to mymax for j 1 to n do … endfor endfor LOCK(diff_lock); diff += mydiff; UNLOCK(diff_lock); BARRIER (bar1, nprocs); if (diff < TOL) then done = 1; BARRIER (bar1, nprocs); endwhile
26
Message Passing Model main() read(n); read(nprocs); CREATE (nprocs-1, Solve); Solve(); WAIT_FOR_END (nprocs-1);
for i 1 to nn do for j 1 to n do … endfor endfor if (pid != 0) SEND(mydiff, 1, 0, DIFF); RECEIVE(done, 1, 0, DONE); else for i 1 to nprocs-1 do RECEIVE(tempdiff, 1, *, DIFF); mydiff += tempdiff; endfor if (mydiff < TOL) done = 1; for i 1 to nprocs-1 do SEND(done, 1, I, DONE); endfor endif endwhile
procedure Solve() int i, j, pid, nn = n/nprocs, done=0; float temp, tempdiff, mydiff = 0; myA malloc(…) initialize(myA); while (!done) do mydiff = 0; if (pid != 0) SEND(&myA[1,0], n, pid-1, ROW); if (pid != nprocs-1) SEND(&myA[nn,0], n, pid+1, ROW); if (pid != 0) RECEIVE(&myA[0,0], n, pid-1, ROW); if (pid != nprocs-1) RECEIVE(&myA[nn+1,0], n, pid+1, ROW);
27
Multithreading Dalam sebuah Prosesor •Sampai sekarang, kita telah mengeksekusi thread multipel dari sebuah aplikasi dalam prosesor berbeda - dapatkan thread multipel dieksekusi bersamaan dalam prosesor yang sama? •Mengapa ini dimungkinkan? Tidak mahal - satu CPU, tidak perlu interkoneksi eksternal Tidak ada miss jarak jauh dan miss koherensi (lebih ke miss kapasitas) •Mengapa ini lebih masuk akal? - kebanyakan CPU kekurangan pekerjaan IPC max adl 6, rata - rata IPC adalah 1.5! - threads dapat share sumber daya kita dapat meningkat28 kan threads tanpa peningkatan linier dari area
Bagaimana Sumber Daya di Share? Setiap bok adalah slot keluaran utk unit fungsional. Keluaran (throughput) puncak 4 IPC Thread 1 Thread 2 Thread 3
Cycles
Thread 4 Idle Superscalar
Fine-Grained Multithreading
Simultaneous Multithreading
•Prosesor superscalar memiliki utilisasi rendah - tidak cukup kerja untuk setiap siklus, khususnya jika terdapat miss cache •Multithreading fine-grained hanya dapat mengeluarkan instruksi dari thread tunggal dalam satu siklus - tidak dpt max kerja setiap siklus, tapi miss cache dpt ditoleransi •Multithreading simultan dapat mengeluarkan instruksi dari semua thread setiap siklus - memiliki probabilitas tertinggi untuk mendapat pekerjaan utk setiap slot 29
Implikasi Kinerja dari SMT •Kinerja utk thread tunggal akan turun (cache, branch predictors, register, dll semuanya di-share) - efek ini dapat dimitasi dengan mencoba memprioritaskan satu thread •Dengan delapan thread dalam sebuah prosesor dengan banyak sumber daya, SMT menghasilkan peningkatan keluaran (throughput) sekitar 2 - 4 kali
30
Pentium4: Hyper-Threading •Dua thread - dalam OS Linux, system beroperasi seakan mengeksekusi dalam sistem dua prosesor •Ketika hanya satu thread yg tersedia, berperilaku seperti sebuah prosesor superscalar thread tunggal
31
Multi-Programmed Speedup
32
Mengapa Multi-Core? •Batasan baru: power, temperatur, kompleksitas •Karena batasan diatas, kita tdk dapat mengenalkan teknik yg kompleks untuk meningkatkan kinerja thread tunggal •Kebanyakan peningkatan kinerja dari thread tunggal telah ditemukan dan diimplementasikan •Maka, penambahan transistor akan berakibat lbh besar pada keluaran (throughput) jika dipergunakan utk eksekusi thread ganda ... ini mengasumsi bahwa kebanyakan user akan menjalankan aplikasi thread ganda 33
Pemakaian Efisien dari Transistor Transistor dapat dipakai utk: •Hirarki dari cache •Jumlah core •Multi-threading dalam sebuah core (SMT) Apakah perlu menyederhanakan core supaya lebih mendapatkan transistor yg tersedia?
Core Cache bank
34
Design Space Exploration • Bullet
From Davis et al., PACT 2005
p – scalar pipelines t – threads s – superscalar pipelines 35
Studi Kasus I: Sun’s Niagara •Server komersial membutuhkan througput tingkat thread yg tinggi dan menderita miss cache • Sun’s Niagara fokus dalam: core yg simpel (power rendah, kompleksitas desain, dapat mengakomodasi core tambahan) Multi-threading secara fine-grained (dapat mentoleransi latensi memori)
36
Niagara Overview
37
SPARC Pipe
No branch predictor Low clock speed (1.2 GHz) One FP unit shared by all cores
38
Studi Kasus II: Arsitektur Intel Core •Eksekusi thread tunggal dianggap penting: eksekusi out-of-order dan spekulasi sangat hidup prosesor awal memiliki core tingkat tinggi yang sedikit •Utk mengurangi konsumsi daya, arsitektur Core (14 tingkat pipeline) lebih dekat ke Pentium M (12 tingkat) daripada P4 (30 tingkat) •Banyak transistor diinvestasikan untuk branch predictor yg besar untuk mengurangi pekerjaan terbuang (power) •Serupa, SMT juga tidak dijamin untuk semua penjelmaan dari arsitektur Core (SMT membuat hotspot lebih panas) 39
Organisasi Cache untuk Multi-cores •L1 cache selalu privat utk sebuah core •L2 cache dapat privat atau di-share - mana yg lbh baik?
P1
P2
P3
P4
P1
P2
P3
P4
L1
L1
L1
L1
L1
L1
L1
L1
L2
L2
L2
L2
L2 40
Organisasi Cache untuk Multi-cores •L1 cache selalu privat utk sebuah core •L2 cache dapat private atau di-share •Keuntungan L2 cache yg di-share: alokasi space dinamis yg efisien di setiap core data yg di-share di banyak core tidak direplikasi setiap blok memiliki “rumah” yg tetap - jadi, mudah utk mendapatkan kopi terbaru •Keuntungan L2 cache yg privat: akses cepat ke L2 privat - bagus utk set pekerjaan yg kecil bus privat utk L2 - sedikit persaingan 41
