Pipelining dan Hazard

Cara pipeline menaikkan throughput, tiga jenis hazard yang mengganggunya, dan cara masing-masing diredakan.

Daftar isi

Datapath siklus tunggal menyelesaikan satu instruksi dalam satu clock, tetapi cara kerja itu membiarkan sebagian besar komponennya menganggur karena ALU hanya bekerja pada satu potongan kecil dari seluruh siklus. Topik ini membahas pipeline, yaitu teknik membagi datapath, jalur data yang menghubungkan memori, register, dan ALU di dalam CPU, menjadi beberapa tahap sehingga banyak instruksi menempati CPU secara bersamaan. Pembahasan dimulai dari dua ukuran performa yang berbeda, dilanjutkan dengan struktur lima tahap, tiga jenis hazard, yaitu keadaan yang memaksa pipeline menahan instruksinya, beserta cara meredakannya, dan diakhiri simulasi jumlah siklus yang membandingkan tiga konfigurasi pada program delapan instruksi fiktif.

Analogi cucian dan dua ukuran performa#

Analogi cucian yang terkenal dari buku teks Patterson dan Hennessy memberi gambaran pertama yang tepat. Apabila satu beban cucian dijalankan dari awal sampai akhir sebelum beban berikutnya dimulai, empat beban membutuhkan empat kali lamanya satu beban karena alat cuci, pengering, dan meja lipat hanya bekerja bergantian untuk beban yang sama. Cara kedua memulai beban berikutnya sebelum beban sebelumnya selesai, yaitu beban kedua masuk ke alat cuci saat beban pertama pindah ke pengering. Setelah tahap pertama terisi, satu beban utuh keluar pada setiap selang waktu satu tahap, sehingga empat beban selesai dalam enam selang tahap, bukan dua belas.

Dua ukuran performa yang berbeda muncul dari cerita ini. Latensi adalah waktu yang dibutuhkan satu instruksi dari masuk sampai selesai, sedangkan throughput adalah jumlah instruksi yang selesai per satuan waktu. Pipeline memperbaiki throughput, bukan latensi, dan latensi satu instruksi bahkan sedikit bertambah karena adanya biaya register antartahap. Untuk pipeline dengan $k$ tahap yang mengolah $n$ instruksi, jumlah siklus idealnya $k + n - 1$ , sedangkan pengerjaan satu per satu membutuhkan $n \times k$ siklus. Pada $n$ yang besar, laju penyelesaiannya mendekati satu instruksi per clock, yakni $k$ kali laju pengerjaan satu per satu.

Lima tahap pipeline#

Pipeline lima tahap membagi datapath menjadi lima bagian yang masing-masing menyelesaikan satu potongan pekerjaan pada satu clock, sehingga panjang clocknya bisa jauh lebih pendek daripada clock siklus tunggal. Tabel berikut memetakan setiap tahap ke pekerjaannya untuk instruksi fiktif add, load, store, dan beq yang digunakan sepanjang modul ini.

Tahap	Nama	Pekerjaan
IF	instruction fetch	mengambil instruksi dari memori instruksi pada alamat PC
ID	instruction decode	menafsirkan field instruksi dan membaca register sumber
EX	execute	menghitung dengan ALU, termasuk alamat memori
MEM	memory access	membaca atau menulis memori data
WB	write-back	menulis hasil ke register file, kumpulan register yang dibaca dan ditulis instruksi

Antara setiap pasang tahap berdiri register antartahap, yaitu register yang menampung seluruh keadaan satu instruksi pada akhir siklus dan menyerahkannya ke tahap berikutnya pada siklus berikutnya. Register ini berbeda dari register file karena tugasnya hanya meneruskan pekerjaan, bukan menyimpan variabel program. Keadaan yang ditampung mencakup instruksi itu sendiri, nilai register sumber, hasil ALU, dan alamat memori, sehingga setiap tahap dapat bekerja tanpa membaca ulang bagian awal pipeline. Lama satu clock ditentukan oleh tahap yang paling lambat, bukan oleh seluruh datapath, sehingga pembagian tahap yang seimbang memberikan throughput terbaik. Konsekuensi lain muncul pada pemakaian memori karena tahap IF dan tahap MEM kini aktif pada siklus yang sama, dan persoalan itu kembali sebagai salah satu hazard pada bagian berikutnya.

Tiga jenis hazard dan cara meredakannya#

Hazard adalah situasi ketika instruksi berikutnya tidak boleh maju ke tahapnya pada siklus berikutnya karena hasilnya bisa keliru. Pipeline yang dihadang hazard tidak berhenti sepenuhnya, melainkan menahan satu atau beberapa instruksinya, dan siklus yang terbuang itu disebut stall. Ada tiga jenis hazard pada pipeline lima tahap, yaitu hazard struktural (structural hazard), hazard data (data hazard), dan hazard kontrol (control hazard).

Hazard struktural terjadi ketika dua instruksi merebut komponen yang sama pada siklus yang sama. Contoh yang paling umum adalah satu memori tunggal yang harus melayani pengambilan instruksi pada tahap IF sekaligus akses data pada tahap MEM. Datapath pada modul ini bebas dari hazard tersebut karena memori instruksinya sudah terpisah dari memori datanya, dan pemisahan atau penduplikasian komponen memang menjadi solusi standar jenis ini.

Hazard data muncul ketika satu instruksi membaca register yang nilainya belum ditulis oleh instruksi di depannya, pola yang disebut RAW (read after write). Jenis ini paling sering ditemui pada program umum, sehingga penanganannya paling menentukan jumlah stall. Potongan program berikut memuat dua ketergantungan berturut-turut, yaitu R1 yang diproduksi instruksi pertama dan R4 yang diproduksi instruksi load.

text Contoh: rantai ketergantungan RAW

add   R1, R2, R3    # memproduksi R1
load  R4, R1, 2     # memproduksi R4, membaca R1
add   R5, R4, R1    # membaca R4 dan R1

Solusi utama hazard data adalah forwarding, yaitu menyambungkan hasil dari register antartahap langsung ke masukan ALU, sehingga hasil produsen diteruskan tanpa menunggu tahap WB. Jalur tambahan ini berangkat dari register antartahap, bukan dari register file, dan sasarannya adalah masukan ALU pada tahap EX. Forwarding menghapus hampir seluruh stall data, kecuali satu kasus yang ditandai peringatan berikut.

Hazard kontrol timbul dari instruksi cabang seperti beq. Keputusan cabang baru jatuh setelah ALU membandingkan dua register pada tahap EX, tetapi tahap IF sudah mengambil instruksi berikutnya satu siklus sebelumnya dan akan terus mengambil instruksi di sepanjang jalur yang belum tentu benar. Solusi yang paling umum adalah menebak jalurnya, mengambil instruksi dari jalur tebakan, lalu membuang seluruh instruksi yang sudah masuk apabila tebakan meleset, dan proses pembuangan ini disebut flush. Penanganan lengkapnya menjadi pembahasan topik Prediksi Cabang dan Spekulasi dalam modul yang sama.

Tabel berikut merangkum ketiganya beserta solusi utamanya.

Jenis hazard	Pemicu	Solusi utama
struktural	dua instruksi merebut komponen yang sama	memisahkan atau menduplikasi komponen
data (RAW)	membaca register sebelum produsennya menulis	forwarding dan stall
kontrol	arah PC bergantung pada hasil cabang yang belum jatuh	prediksi jalur dan flush

Simulasi jumlah siklus#

Berkas pipeline.py membandingkan tiga konfigurasi pada program delapan instruksi fiktif yang memuat rantai ketergantungan RAW, termasuk satu pola load-use antara instruksi pada indeks 1 dan 2. Simulator menjadwalkan lima tahap untuk setiap instruksi, menerapkan aturan hazard sesuai konfigurasi yang dipilih, lalu mencetak tabel posisi tahap setiap instruksi pada setiap siklus. Jalankan berkasnya, lalu bandingkan kedua tabelnya dan ringkasan di bagian akhir keluarannya.

python pipeline.py

"""Perbandingan jumlah siklus: tanpa pipeline, pipeline tanpa forwarding,
dan pipeline dengan forwarding, untuk program delapan instruksi fiktif.

Model: lima tahap (IF, ID, EX, MEM, WB), satu instruksi masuk per siklus,
hazard data RAW diselesaikan dengan stall bila forwarding dimatikan dan
dengan forwarding bila dinyalakan.
"""

# (mnemonik, register tujuan, sumber, produsen load?, tampilan)
PROGRAM = [
    ("add", "R1", ("R2", "R3"), False, "add   R1, R2, R3"),
    ("load", "R4", ("R1",), True, "load  R4, R1, 2"),
    ("add", "R5", ("R4", "R1"), False, "add   R5, R4, R1"),
    ("add", "R6", ("R5", "R4"), False, "add   R6, R5, R4"),
    ("store", None, ("R6", "R1"), False, "store R6, R1, 4"),
    ("beq", None, ("R1", "R6"), False, "beq   R1, R6, 2"),
    ("add", "R7", ("R2", "R2"), False, "add   R7, R2, R2"),
    ("add", "R2", ("R7", "R7"), False, "add   R2, R7, R7"),
]
TAHAPAN = 5


def jadwal(forwarding):
    n = len(PROGRAM)
    ifc = [0] * n
    idc = [0] * n
    exc = [0] * n
    mec = [0] * n
    wbc = [0] * n
    for j in range(n):
        if j == 0:
            ifc[j], idc[j] = 1, 2
        else:
            ifc[j] = max(ifc[j - 1] + 1, idc[j - 1])  # tahap IF bebas
            idc[j] = max(ifc[j] + 1, exc[j - 1])      # tahap ID bebas
        batas = idc[j] + 1
        for i in range(j):
            if PROGRAM[i][1] in PROGRAM[j][2]:        # instruksi i memproduksi sumber j
                if forwarding:
                    if PROGRAM[i][3]:                 # load: nilai siap akhir MEM
                        batas = max(batas, mec[i] + 1)
                    else:                             # ALU: nilai siap akhir EX
                        batas = max(batas, exc[i] + 1)
                else:
                    # register file menulis paruh pertama dan membaca paruh
                    # kedua siklus yang sama, sehingga ID boleh = WB produsen
                    batas = max(batas, wbc[i] + 1)
        exc[j] = batas
        mec[j] = exc[j] + 1
        wbc[j] = mec[j] + 1
    return ifc, idc, exc, mec, wbc


def cetak_tabel(judul, jadwal_):
    ifc, idc, exc, mec, wbc = jadwal_
    total = wbc[-1]
    stall = total - (len(PROGRAM) + TAHAPAN - 1)
    print(f"{judul} ({total} siklus, {stall} siklus stall)")
    print(f"{'siklus':>6} | " + " ".join(f"{j:>3}" for j in range(len(PROGRAM))))
    for t in range(1, total + 1):
        sel = []
        for j in range(len(PROGRAM)):
            if t == ifc[j]:
                sel.append("IF")
            elif t == idc[j]:
                sel.append("ID")
            elif t == exc[j]:
                sel.append("EX")
            elif t == mec[j]:
                sel.append("ME")
            elif t == wbc[j]:
                sel.append("WB")
            elif ifc[j] <= t <= wbc[j]:
                sel.append("**")   # menunggu di IF atau stall di ID
            else:
                sel.append(".")
        print(f"{t:>6} | " + " ".join(f"{s:>3}" for s in sel))
    print()


print(f"Program uji ({len(PROGRAM)} instruksi, ISA fiktif):")
for i, p in enumerate(PROGRAM):
    print(f"  {i}: {p[4]}")
print()

cetak_tabel("Pipeline tanpa forwarding", jadwal(False))
cetak_tabel("Pipeline dengan forwarding", jadwal(True))

print(f"Ringkasan ({len(PROGRAM)} instruksi, 5 tahap, ideal = {len(PROGRAM) + TAHAPAN - 1} siklus):")
print(f"  tanpa pipeline             : {len(PROGRAM) * TAHAPAN} siklus ({len(PROGRAM)} x 5)")
print(f"  pipeline tanpa forwarding  : {jadwal(False)[4][-1]} siklus")
print(f"  pipeline dengan forwarding : {jadwal(True)[4][-1]} siklus")

text Keluaran

Program uji (8 instruksi, ISA fiktif):
  0: add   R1, R2, R3
  1: load  R4, R1, 2
  2: add   R5, R4, R1
  3: add   R6, R5, R4
  4: store R6, R1, 4
  5: beq   R1, R6, 2
  6: add   R7, R2, R2
  7: add   R2, R7, R7

Pipeline tanpa forwarding (22 siklus, 10 siklus stall)
siklus |   0   1   2   3   4   5   6   7
     1 |  IF   .   .   .   .   .   .   .
     2 |  ID  IF   .   .   .   .   .   .
     3 |  EX  ID  IF   .   .   .   .   .
     4 |  ME  **  **   .   .   .   .   .
     5 |  WB  **  **   .   .   .   .   .
     6 |   .  EX  ID  IF   .   .   .   .
     7 |   .  ME  **  **   .   .   .   .
     8 |   .  WB  **  **   .   .   .   .
     9 |   .   .  EX  ID  IF   .   .   .
    10 |   .   .  ME  **  **   .   .   .
    11 |   .   .  WB  **  **   .   .   .
    12 |   .   .   .  EX  ID  IF   .   .
    13 |   .   .   .  ME  **  **   .   .
    14 |   .   .   .  WB  **  **   .   .
    15 |   .   .   .   .  EX  ID  IF   .
    16 |   .   .   .   .  ME  EX  ID  IF
    17 |   .   .   .   .  WB  ME  EX  ID
    18 |   .   .   .   .   .  WB  ME  **
    19 |   .   .   .   .   .   .  WB  **
    20 |   .   .   .   .   .   .   .  EX
    21 |   .   .   .   .   .   .   .  ME
    22 |   .   .   .   .   .   .   .  WB

Pipeline dengan forwarding (13 siklus, 1 siklus stall)
siklus |   0   1   2   3   4   5   6   7
     1 |  IF   .   .   .   .   .   .   .
     2 |  ID  IF   .   .   .   .   .   .
     3 |  EX  ID  IF   .   .   .   .   .
     4 |  ME  EX  ID  IF   .   .   .   .
     5 |  WB  ME  **  **   .   .   .   .
     6 |   .  WB  EX  ID  IF   .   .   .
     7 |   .   .  ME  EX  ID  IF   .   .
     8 |   .   .  WB  ME  EX  ID  IF   .
     9 |   .   .   .  WB  ME  EX  ID  IF
    10 |   .   .   .   .  WB  ME  EX  ID
    11 |   .   .   .   .   .  WB  ME  EX
    12 |   .   .   .   .   .   .  WB  ME
    13 |   .   .   .   .   .   .   .  WB

Ringkasan (8 instruksi, 5 tahap, ideal = 12 siklus):
  tanpa pipeline             : 40 siklus (8 x 5)
  pipeline tanpa forwarding  : 22 siklus
  pipeline dengan forwarding : 13 siklus

Ketiga angka pada ringkasan keluaran merangkum seluruh perbandingan. Tanpa pipeline, delapan instruksi membutuhkan 40 siklus karena setiap instruksi menempati kelima tahap sendirian. Pipeline tanpa forwarding menurunkan jumlahnya menjadi 22 siklus, dan pipeline dengan forwarding menurunkannya lagi menjadi 13 siklus, sedangkan batas idealnya untuk delapan instruksi dengan lima tahap adalah 12 siklus. Selisih satu siklus pada konfigurasi forwarding adalah pola load-use pada instruksi indeks 2, yang menunggu satu siklus untuk nilai yang dimuat dari instruksi indeks 1.

Tabel tanpa forwarding memperlihatkan harga setiap ketergantungan dengan jelas. Instruksi pada indeks 1 menunggu dua siklus agar R1 selesai ditulis, instruksi pada indeks 2 menunggu empat siklus, dan penantian sejenis berlanjut sampai indeks 5 karena setiap konsumen menunggu produsennya menyelesaikan tahap WB. Satu stall juga menggeser seluruh instruksi di belakangnya, sehingga deretan ** menjalar ke banyak kolom sekaligus. Hasil produsen sebenarnya sudah tersedia jauh lebih awal di register antartahap, dan forwarding hanya memindahkan sambungan nilainya ke masukan ALU konsumen. Tabel dengan forwarding menyingkirkan hampir seluruh penantian itu dan menyisakan satu ** yang tidak terhindarkan.

Apabila yang dibutuhkan hanya angka ringkasannya, jalankan perintah berikut dari direktori topik.

bash

# tampilkan empat baris terakhir keluaran simulator
python3 pipeline.py | tail -n 4

text Keluaran

Ringkasan (8 instruksi, 5 tahap, ideal = 12 siklus):
  tanpa pipeline             : 40 siklus (8 x 5)
  pipeline tanpa forwarding  : 22 siklus
  pipeline dengan forwarding : 13 siklus

Kesalahan umum#

Kesalahan pertama adalah menyamakan throughput dengan latensi. Pipeline lima tahap tidak membuat satu instruksi selesai lima kali lebih cepat, sehingga klaim kecepatan naik lima kali lipat untuk program apa pun keliru. Program pendek dengan jumlah instruksi kecil bahkan hampir tidak merasakan manfaatnya karena sebagian besar siklusnya habis untuk mengisi dan mengosongkan pipeline. Ukur kedua ukuran itu secara terpisah, yaitu waktu satu instruksi untuk latensi dan jumlah instruksi per clock untuk throughput.

Kesalahan kedua adalah menganggap forwarding menghapus seluruh stall data. Instruksi yang sumbernya berasal dari load tetap menunggu satu siklus karena nilai yang dimuat baru ada di akhir tahap MEM, sehingga tabel dengan forwarding masih memuat satu **. Salah paham ini biasanya muncul setelah membaca definisi forwarding tanpa memperhatikan kapan setiap komponen menghasilkan nilainya. Perbaikan pada tingkat program adalah menyusun ulang instruksi yang tidak saling bergantung agar mengisi celah satu siklus itu.

Kesalahan ketiga adalah menyangka pipeline mengubah hasil program. Urutan tulis register tetap dijaga oleh mekanisme penanganan hazard, sehingga keadaan akhir register dan memori sama persis dengan pengerjaan satu per satu. Apabila sebuah implementasi menghasilkan keadaan akhir yang berbeda, ada bug pada logika hazardnya, bukan perilaku yang wajar dari pipeline.

Ringkasan#

Pipeline membagi datapath menjadi lima tahap, yaitu IF, ID, EX, MEM, dan WB, yang dihubungkan register antartahap, sehingga banyak instruksi menempati CPU secara bersamaan.
Pipeline menaikkan throughput, bukan latensi, dan jadwal idealnya untuk $n$ instruksi dengan $k$ tahap adalah $k + n - 1$ siklus.
Hazard struktural diredakan dengan memisahkan atau menduplikasi komponen, hazard data RAW dengan forwarding dan stall, sedangkan hazard kontrol dengan prediksi jalur dan flush.
Forwarding menghapus hampir seluruh stall data, tetapi pola load-use dari instruksi load masih menyisakan satu siklus tunggu karena nilai yang dimuat baru ada di akhir tahap MEM.

Referensi#

6.004 Computation Structures — MIT OpenCourseWare — Materi kuliah yang membahas pipeline lima tahap dan penanganan hazardnya sebagai bagian dari rancangan prosesor.
Computer Systems: A Programmer’s Perspective — Carnegie Mellon University — Buku yang menjelaskan pipeline lima tahap, hazard data, dan forwarding dari sudut pandang pemrogram.