UNIVERSITAS

MUHAMMADIYAH
SIDOARJO

Parallel Processing
Matakuliah Arsitektur dan Organisasi Komputer

Oleh:
Azmuri Wahyu Azinar
Universitas Muhammadiyah Sidoarjo
 Multiple Processor Organization
• Single instruction, single • Multiple instruction, single data
data (SISD) stream (MISD) stream
• Prosesor tunggal mengeksekusi aliran • Urutan data ditransmisikan ke satu set prosesor,
instruksi tunggal untuk beroperasi pada yang masing-masing mengeksekusi urutan
data yang disimpan dalam satu memori
instruksi yang berbeda
• Uniprosesor termasuk dalam kategori ini
• Tidak diimplementasikan secara komersial

• Single instruction, multiple • Multiple instruction,

data (SIMD) stream multiple data (MIMD)
• Sebuah instruksi mesin tunggal
mengontrol eksekusi simultan dari stream
sejumlah elemen pemrosesan secara • Satu set prosesor secara bersamaan
berurutan mengeksekusi urutan instruksi yang
• Prosesor vektor dan array termasuk dalam berbeda pada set data yang berbeda
kategori ini • SMP, cluster, dan sistem NUMA cocok
dengan kategori ini
2
Multiple Processor Organization

3
Multiple Processor Organization

4
 Symmetric Multiprocessor (SMP)

Sebuah stand alone komputer dengan karakteristik sebagai berikut:

Prosesor berbagi Sistem dikendalikan

Semua prosesor
memori dan fasilitas I/O oleh sistem operasi
berbagi akses ke
yang sama terintegrasi
perangkat I/O
Dua atau lebih • Prosesor
• Baik melalui saluran Semua prosesor dapat • Menyediakan
prosesor yang serupa dihubungkan oleh melakukan fungsi yang interaksi antara
yang sama atau
dengan kapasitas yang bus atau koneksi sama (karenanya prosesor dan
saluran berbeda
sebanding internal lainnya "simetris") programnya di
• Waktu akses memori yang memberikan
tingkat job, task,
kira-kira sama untuk jalur ke perangkat
file, dan elemen
setiap prosesor yang sama
data

5
6
7
8
 Organisasi bus
Organisasi bus memiliki beberapa fitur menarik:

• Simplicity
Pendekatan paling sederhana untuk organisasi multiprosesor
• Flexibility
Umumnya mudah untuk memperluas sistem dengan memasang lebih
banyak prosesor ke bus
• Reliability
Bus pada dasarnya adalah media pasif dan kegagalan perangkat apa
pun yang terpasang seharusnya tidak menyebabkan kegagalan seluruh
sistem

9
 Organisasi bus
Kerugian dari organisasi bus:

• Kelemahan utama adalah kinerja

• Semua referensi memori melewati bus umum
• Performa dibatasi oleh waktu siklus bus
• Setiap prosesor harus memiliki memori cache
• Mengurangi jumlah akses bus
• Menyebabkan masalah dengan koherensi cache
• Jika sebuah kata diubah dalam satu cache, itu bisa membuat kata tidak
valid di cache lain
• Untuk mencegah hal ini, prosesor lain harus diberi tahu bahwa pembaruan telah terjadi
• Biasanya ditangani di perangkat keras daripada di sistem operasi

10
 Multiprocessor Operating System Design
Considerations
• Proses berjalan secara bersamaan
• Rutinitas OS perlu masuk kembali untuk memungkinkan beberapa prosesor mengeksekusi kode IS yang sama
secara bersamaan
• Tabel OS dan struktur manajemen harus dikelola dengan baik untuk menghindari deadlock atau operasi yang
tidak valid
• Penjadwalan
• Setiap prosesor dapat melakukan penjadwalan sehingga konflik harus dihindari
• Penjadwal harus menetapkan proses yang berstatus “ready” untuk prosesor yang tersedia
• Sinkronisasi
• Dengan beberapa proses aktif yang memiliki akses potensial ke shared address atau sumber daya I/O,
perhatian harus diberikan untuk menyediakan sinkronisasi yang efektif
• Sinkronisasi adalah fasilitas yang memberlakukan mutual exclusion dan event ordering
• Manajemen memori
• Selain menangani semua masalah yang ditemukan pada mesin uniprosesor, OS perlu mengeksploitasi
paralelisme perangkat keras yang tersedia untuk mencapai kinerja terbaik
• Mekanisme paging pada prosesor yang berbeda harus dikoordinasikan untuk menegakkan konsistensi ketika
beberapa prosesor berbagi halaman atau segmen dan untuk memutuskan penggantian halaman
• Keandalan dan toleransi kesalahan
• OS harus memberikan degradasi yang baik dalam menghadapi kegagalan prosesor
• Penjadwal dan bagian lain dari sistem operasi harus mengenali hilangnya prosesor dan melakukan
restrukturisasi yang sesuai

11
 Cache Coherence
Software Solutions

• Mencoba menghindari kebutuhan akan sirkuit dan logika

perangkat keras tambahan dengan mengandalkan kompiler
dan sistem operasi untuk menangani masalah
• Menarik karena overhead untuk mendeteksi potensi masalah
ditransfer dari waktu berjalan ke waktu kompilasi, dan
kompleksitas desain ditransfer dari perangkat keras ke
perangkat lunak
• Namun, pendekatan perangkat lunak waktu kompilasi umumnya harus
membuat keputusan konservatif, yang mengarah pada pemanfaatan
cache yang tidak efisien
12
 Cache Coherence
Hardware-Based Solutions

• Umumnya disebut sebagai protokol koherensi cache

• Solusi ini memberikan pengenalan dinamis saat menjalankan kondisi potensi
inkonsistensi
• Karena masalah hanya ditangani ketika benar-benar muncul, ada penggunaan
cache yang lebih efektif, yang mengarah pada peningkatan kinerja melalui
pendekatan perangkat lunak
• Pendekatan transparan untuk programmer dan compiler, mengurangi beban
pengembangan perangkat lunak
• Dapat dibagi menjadi dua kategori:
• Protokol direktori
• Protokol Snoopy

13
 Directory Protocols
Mengumpulkan dan Direktori
mantain informasi
tentang salinan data disimpan di
dalam cache memori utama

Permintaan diperiksa
berdasarkan direktori

Transfer yang Menciptakan 14

 Snoopy Protocols
• Bertanggung jawab untuk menjaga koherensi cache di antara semua
pengontrol cache dalam multiprosesor
• Cache harus mengenali saat baris yang dipegangnya dibagikan dengan cache lain
• Ketika pembaruan dilakukan pada saluran cache bersama, itu harus diumumkan ke
cache lain dengan mekanisme broadcast
• Setiap pengontrol cache dapat "mengintip" di jaringan untuk mengamati
pemberitahuan siaran ini dan bereaksi sesuai dengan itu
• Cocok untuk multiprosesor berbasis bus karena bus bersama menyediakan
sarana sederhana untuk broadcast dan snooping (mengintip)
• Harus diperhatikan bahwa peningkatan lalu lintas bus yang diperlukan untuk
broadcast dan pengintaian tidak membatalkan keuntungan dari penggunaan cache
lokal
• Dua pendekatan dasar telah dieksplorasi:
• Write invalidate
• Write update (or write broadcast)

15
 Write Invalidate
• Banyak reader, tetapi hanya satu writer dalam satu waktu
• Saat penulisan diperlukan, semua cache saluran lainnya tidak
valid
• Prosesor write kemudian memiliki akses eksklusif hingga
saluran diperlukan oleh prosesor lain
• Paling banyak digunakan dalam sistem multiprosesor komersial
seperti arsitektur x86
• Status setiap baris ditandai sebagai Modifierd, Exclusive,
Shared, atau Invalid
• Untuk alasan ini protokol write-invalidate disebut MESI

16
 Write Update

Dapat melibatkan banyak reader dan writer

Ketika prosesor ingin memperbarui baris bersama, word yang akan diperbarui didistribusikan
ke semua yang lain dan cache yang berisi baris itu dapat memperbaruinya

Beberapa sistem menggunakan campuran adaptif dari mekanisme write-invalidate dan

write-update
17
 MESI Protocol
Untuk memberikan konsistensi cache pada SMP, cache data mendukung
protokol yang dikenal sebagai MESI:

• Modified
Baris dalam cache telah dimodifikasi dan hanya tersedia di cache ini
• Exclusive
Baris dalam cache sama dengan yang ada di memori utama dan tidak ada di
cache lainnya
• Shared
Baris dalam cache sama dengan yang ada di memori utama dan mungkin ada di
cache lain
• Invalid
Baris dalam cache tidak berisi data yang valid
18
 MESI Protocol

Table 17.1
MESI Cache Line States

19
MESI Protocol

20
Multithreading and Chip Multiprocessors
• Performa prosesor dapat diukur dengan kecepatan pada saat
sedang mengeksekusi instruksi
• MIPS rate = f * IPC
• f = processor clock frequency, in MHz
• IPC = average instructions per cycle
• Meningkatkan Performa/kinerja dengan cara meningkatkan
frekuensi clock dan meningkatkan instruksi yang selesai selama
siklus
• Multithreading
• Memungkinkan paralelisme instruksi tingkat tinggi tanpa meningkatkan
kompleksitas sirkuit atau konsumsi daya
• Aliran instruksi dibagi menjadi beberapa aliran yang lebih kecil, yang
dikenal sebagai thread, yang dapat dieksekusi secara paralel
21
 Definitions of Threads
and Processes
Thread dalam prosesor multithread
mungkin sama atau tidak sama
dengan konsep thread perangkat
lunak dalam sistem operasi
multiprogram
Thread switch Thread berkaitan dengan penjadwalan
• Tindakan mengalihkan kontrol dan eksekusi, sedangkan proses
prosesor antara thread dalam proses berkaitan dengan
yang sama penjadwalan/eksekusi dan kepemilikan
• Biasanya lebih murah daripada sumber daya dan sumber daya nya
proses switching

Thread:
• Unit kerja yang dapat dikirim dalam
suatu proses
Process:
• Contoh program yang berjalan di
• Termasuk konteks prosesor (yang
komputer
mencakup penghitung program dan • Dua karakteristik utama:
stack pointer) dan area data stack •
• Kepemilikan sumber daya dan
Dieksekusi secara berurutan dan
dapat diinterupsi sehingga prosesor Process switch Penjadwalan/eksekusi
dapat beralih ke thread lain • Operasi yang mengalihkan prosesor
dari satu proses ke proses lainnya
dengan menyimpan semua data kontrol
proses, register, dan informasi lainnya
untuk yang pertama dan menggantinya
dengan informasi proses untuk yang
kedua 22
 Implicit and Explicit Multithreading
Semua prosesor komersial dan sebagian besar yang eksperimental
menggunakan multithreading eksplisit
 Secara bersamaan menjalankan instruksi dari thread eksplisit yang berbeda

 Interleave instruksi dari thread yang berbeda pada shared pipeline atau eksekusi paralel pada
parallel pipeline

Multithreading implisit adalah eksekusi bersamaan dari beberapa thread

yang diekstraksi dari program sekuensial tunggal
 Thread implisit didefinisikan secara statis oleh kompiler atau secara dinamis oleh perangkat
keras

23
 Approaches to Explicit Multithreading
• Interleaved • Blocked
• Prosesor menangani dua atau lebih • Thread dieksekusi sampai event
konteks thread sekaligus menyebabkan delay
• Mengganti thread pada setiap siklus jam • Efektif pada prosesor yang berjalan
secara urut
• Jika thread diblokir, itu dilewati • Menghindari kemacetan pipeline
• Simultaneous (SMT) • Chip multiprocessing
• Instruksi dikeluarkan secara bersamaan • Prosesor direplikasi pada satu chip
dari beberapa thread ke unit eksekusi • Setiap prosesor menangani thread
prosesor superscalar terpisah
• Keuntungannya adalah bahwa
area logika yang tersedia pada
sebuah chip digunakan secara
efektif

24
 Clusters
 Alternatif untuk SMP sebagai pendekatan untuk memberikan kinerja tinggi dan
ketersediaan tinggi
 Sangat menarik untuk aplikasi server

 Didefinisikan sebagai:
 Sekelompok komputer utuh yang saling berhubungan bekerja bersama sebagai sumber daya komputasi
terpadu yang dapat menciptakan ilusi menjadi satu mesin

 (Istilah komputer utuh berarti sistem yang dapat berjalan sendiri, terlepas dari cluster)

 Setiap komputer dalam sebuah cluster disebut node

 Benefits:
 Absolute scalability
 Incremental scalability
 High availability
 Superior price/performance
25
Table 17.2
Clustering
Methods:
Benefits and
Limitations

26
 Operating System Design Issues
• Bagaimana kegagalan dikelola tergantung pada metode clustering yang
digunakan
• Dua pendekatan:
• Highly available clusters
• Fault tolerant clusters

• Failover
• Fungsi mengalihkan aplikasi dan sumber daya data dari sistem yang gagal ke sistem
alternatif dalam cluster

• Failback
• Pemulihan aplikasi dan sumber daya data ke sistem original setelah diperbaiki
• Load balancing
• Skalabilitas tambahan
• Secara otomatis menyertakan komputer
© 2016 baru
Pearson Education, dalam
Inc., Hoboken,penjadwalan
NJ. All
rights reserved.
• Middleware perlu mengenali bahwa proses dapat beralih antar mesin
27
 Parallelizing Computation
Penggunaan cluster yang efektif membutuhkan perangkat lunak yang dijalankan dari satu aplikasi secara paralel

Tiga pendekatan:

Parallelizing compiler
• Menentukan pada waktu kompilasi bagian mana dari aplikasi yang dapat dieksekusi
secara paralel
• Ini kemudian dipisah untuk ditugaskan ke komputer yang berbeda yang ada di cluster

28
 Clusters Compared to SMP
 Keduanya menyediakan konfigurasi dengan beberapa
prosesor untuk mendukung aplikasi permintaan tinggi
 Kedua solusi tersedia secara komersial
SMP Clustering
• Lebih mudah untuk • Jauh lebih unggul dalam
dikelola dan hal skalabilitas
dikonfigurasi inkremental dan absolut
• Jauh lebih dekat dengan • Unggul dalam hal
model prosesor tunggal ketersediaan
original yang hampir • Semua komponen sistem
semua aplikasinya ditulis dapat dengan mudah
• Lebih sedikit ruang fisik dibuat
dan konsumsi daya yang
lebih rendah
• Terbentuk dengan baik
dan stabil
29
 Referensi
• William Stallings, Computer Organization and Architecture
Designing for Performance, tenth edition, 2016
• © 2016 Pearson Education, Inc., Hoboken, NJ. All rights
reserved.

30