Meningkatkan Kinerja dengan Pipelining • Topik hari ini: Pipeline 5-tahap Hazard dan penjadwalan instruksi Prediksi branch Eksekusi out-of-order
1
Prosesor Siklus Ganda
•Unit memori tunggal di-share oleh instruksi dan memori •ALU tunggal juga digunakan untuk memperbaharui PC •Register - register (latches) untuk menyimpan hasil setiap blok 2
Jalur Assembly Tanpa Pipeline Mulai dan akhir pekerjaan sebelum ke selanjutnya
Pekerjaan Waktu A
B A
C B A
C B A
C B
Memecah pekerjaan ke dalam tahapan yg lebih kecil C
Dengan Pipeline 3
Peningkatan Kinerja? •Apakah membutuhkan waktu yg lebih lama untuk menyelesaikan masing - masing pekerjaan? •Apakah lebih cepat menyelesaian pekerjaan secara serial? •Asumsi apakah yang dibuat untuk menjawab pertanyaan pertanyaan diatas? •Apakah pipeline 10 tahap lebih baik dari pipeline 5 tahap?
4
Efek Kuantitatif •Dari hasil mem-pipeline: Waktu dalam ns per instruksi meningkat Setiap instruksi membutuhkan siklus yg lbh lama Tapi ... rata-rata CPI tetap sama (kurang lebih) Kecepatan clock meningkat Waktu eksekusi total meningkat, menghasilkan rata - rata waktu per instruksi yang lebih rendah Pada kondisi ideal = rasio dari waktu tempuh antara penyelesaian instruksi yang berurutan = jumlah tahap dari pipeline = peningkatan kec. clock
5
Sebuah pipeline 5 tahap
6
Sebuah Pipeline 5 Tahap Menggunakan PC untuk mengakses I-cache dan menambah PC dengan 4
7
Sebuah Pipeline 5 Tahap Membaca register, membandingkan register, menghitung target branch; utk sekarang diasumsikan branch membutuhkan 2 siklus (banyak pekerjaan yang membuat branch membutuhkan lebih dari itu)
8
Sebuah Pipeline 5 Tahap Komputasi ALU, komputasi address efektif untuk load / store
9
Sebuah Pipeline 5 Tahap Akses memori ke / dari data cache, store selesai dalam 4 siklus
10
Sebuah Pipeline 5 Tahap Menuliskan hasil dari komputasi ALU atau load ke berkas register
11
Konflik / Permasalahan •I-cache dan D-cache diakses pada siklus yang sama - akan membantu apabila diimplementasikan terpisah •Registers dimatikan dan ditulis dalam siklus yang sama mudah dihandle apabila register baca/tulis sama dengan waktu siklus / 2 (yang lainnya, memakai bypassing) •Target branch berubah hanya pada akhir dari tahap kedua -- apa yang akan dikerjakan diantaranya? •Data antar tahap di-latch ke register - register (overhead yang meningkatkan latensi (kelambatan) per-instruksi 12
Hazards / Bahaya •Hazard struktural: instruksi yang berbeda di tahap berbeda (atau tahap yg sama) berkonflik di sumber daya yg sama •Hazard data: sebuah instruksi tidak dapat berlanjut karena membutuhkan sebuah nilai yang belum dihasilkan dari instruksi sebelumnya • Hazard kontrol: fetch tdk dapat berlanjut karena tidak tahu keluaran dari branch sebelumnya - kasus khusus hazard • data - kategori terpisah karena ditangani secara berbeda
13
Hazard Struktural Contoh: sebuah gabungan instruksi dan data cache tahap 4 (MEM) dan tahap 1 (IF) tidak boleh bertabrakan
•
Instruksi yang kedua dan yg selanjutnya ditunda sampai sebuah siklus dimana sumber dayanya bebas ini adalah balon (bubble) pipeline
•
Hazard struktural mudah untuk dihilangkan - meningkatkan sumber daya (contohnya, implementasi cache instruksi dan data).
•
14
Hazard Data
15
Bypassing
•Beberapa kemacetan (stall) dari hazard data dapat dihilangkan: bypassing 16
Kemacetan karena Hazard Data
17
Kemacetan karena Hazard Data
18
Contoh
add $1, $2, $3 lw
$4, 8($1)
19
Contoh
lw
$1, 8($2)
lw
$4, 8($1)
20
Contoh
lw
$1, 8($2)
sw
$1, 8($3)
21
Hazard Kontrol •Teknik sederhana untuk menangani kemacetan karena hazard kontrol: untuk setiap branch, diperkenalkan sebuah siklus stall (catatan: setiap instruksi ke-6 adalah branch!) asumsi bahwa branch tidak diambil dan mulai fetch instruksi selanjutnya - jika branch terjadi, perlu perangkat keras utk membatalkan efek dari instruksi di jalur yg salah fetch instruksi selanjutnya (slot dari branch delay) dan tetap eksekusi - jika instruksi ternyata jalur yg benar, pekerjaan yg berguna telah terjadi - jika instruksi ternyata di jalur yg salah, diharapkan kondisi program tidak hilang 22
Slot dari branch delay
23
Perlambatan Karena Stall / Kemacetan Pipeline sempurna dengan tanpa hazard sebuah instruksi selesai setiap siklus (siklus total ~ jumlah instruksi) peningkatan = penambahan kec. clock = jml tahap pipeline
•
•Dengan hazard dan stall, beberapa siklus (= waktu stall) akan hilang dimana tidak ada instruksi yang selesai, kemudian instruksi yg kena stall akan selesai •Total siklus = jumlah instruksi + siklus yg stall
24
Pipeline tanpa Prediksi Branch
IF (br) PC
Reg Read Compare Br-target
PC + 4
25
Pipeline dengan Prediksi Branch
IF (br) PC
Branch Predictor
Reg Read Compare Br-target
26
Prediksi Bimodal
14 bits
Branch PC
Table of 16K entries of 2-bit saturating counters
27
Prediksi 2-Bit •Utk setiap branch, memelihara conter 2-bit tersaturasi: jika branch terjadi: counter = min(3,counter+1) jika branch tdk terjadi: counter = max(0,counter-1) … ada kemiripan dgn hal lainnya? •Jika (counter >= 2), diprediksi terjadi branch, yg lain tdk terjadi branch •Counter berusaha menangkap kasus umum dari setiap branch
28
Instruksi multi-siklus
•Multiple paralles pipelines - setiap pipeline dapat memiliki tahap yg berbeda •Instruksi sekarang dapat selesai dengan urutan yang sembarang harus memastikan untuk menulis ke register dengan urutan yg benar
29
Implementasi dari Prosesor Urutan-Acak Buffer Reorder (ROB) Instr 1 Instr 2 Instr 3 Instr 4 Instr 5 Instr 6
Branch prediction and instr fetch
R1 R1+R2 R2 R1+R3 BEQZ R2 R3 R1+R2 R1 R3+R2 Antrian Fetch Instruksi
Decode & Rename
T1 T2 T3 T4 T5 T6
T1 R1+R2 T2 T1+R3 BEQZ T2 T4 T1+T2 T5 T4+T2
Register File R1-R32
ALU
ALU
ALU
Hasil ditulis di ROB dan tag-nya di-broadcast ke IQ
Antrial Issue (IQ) 30
