KAL
Menu

Paralelisme Tingkat Instruksi

Pipeline, superscalar, dan out-of-order secara konseptual: cara satu prosesor menjalankan banyak instruksi sekaligus.

Daftar isi

Satu aliran instruksi dari satu program memuat banyak peluang untuk dikerjakan bersamaan, dan prosesor modern memanfaatkannya sekuat kemampuan perangkat kerasnya. Topik ini membahas instruction-level parallelism (ILP), yaitu paralelisme yang tersedia di antara instruksi-instruksi dalam satu aliran program. Dua mekanisme yang memanfaatkannya dijelaskan setelahnya, yaitu superscalar yang menerbitkan beberapa instruksi per clock dan eksekusi out-of-order yang tidak terikat urutan program saat mengeksekusi. Diagram perbandingan dan simulasi Python di bagian akhir menampilkan jadwal instruksi dengan dan tanpa penyusunan ulang, sehingga selisih siklusnya terlihat dalam angka.

Peluang paralel dalam satu aliran instruksi#

Peluang yang dimaksud ILP lahir dari ketergantungan data, bukan dari banyaknya instruksi. Dua instruksi yang saling bebas, misalnya dua penjumlahan pada register yang berbeda, dapat berjalan bersama tanpa saling menunggu, sedangkan instruksi yang membaca hasil instruksi lain harus menunggu produsennya selesai. Peluang ini dimiliki oleh program, sedangkan prosesor menentukan seberapa banyak peluang itu benar-benar dimanfaatkan. Pipeline lima tahap pada modul Membangun CPU sudah menempatkan banyak instruksi di dalam prosesor, tetapi setiap tahapnya masih mengerjakan satu instruksi pada satu waktu, sehingga sisa peluangnya masih luas.

Jumlah peluang itu berbeda-beda antarbagian program. Rantai perhitungan yang panjang, yaitu deretan instruksi yang tiap anggotanya membaca hasil anggota sebelumnya, hampir tidak menyisakan kebebasan, sedangkan perulangan yang tiap putarannya bebas menyimpan banyak pasangan instruksi yang dapat berjalan bersama. Karena peluang itu berpindah dari satu bagian program ke bagian lain, mekanisme perangkat keras harus mampu menyesuaikan dirinya setiap clock, dan dua mekanisme berikut mengambil dua tingkat penyesuaian yang berbeda.

Superscalar menerbitkan lebih dari satu instruksi per clock#

Prosesor superscalar menduplikasi jalur pengambilan dan penafsiran instruksi sehingga dapat menerbitkan lebih dari satu instruksi pada clock yang sama. Penerbitan (issue) adalah pengiriman instruksi yang sudah didekode ke unit eksekusi. Kemampuan ini disebut multiple issue, dan jumlah instruksinya per clock disebut lebar penerbitan, dengan nilai dua sampai enam pada prosesor desktop modern. Pada lebar dua, enam instruksi yang saling bebas selesai dalam tiga clock, setengah dari enam clock pengerjaan berurutan.

Diagram berikut membandingkan kedua cara itu pada enam instruksi fiktif I1 sampai I6 yang tidak saling bergantung.

Berurutan (satu instruksi per clock)clock 1I1clock 2I2clock 3I3clock 4I4clock 5I5clock 6I6selesai pada clock ke-6Superscalar (dua instruksi per clock)clock 1I1I2clock 2I3I4clock 3I5I6tidak ada instruksi lagiselesai pada clock ke-3
Enam instruksi bebas pada eksekusi berurutan dan superscalar berlebar dua

Keuntungan penuh pada diagram hanya tercapai karena seluruh instruksinya saling bebas. Apabila instruksi berikutnya menunggu hasil instruksi sebelumnya, slot yang tersedia terpakai kosong, dan penerbitan berurutan (in-order issue) memperparah keadaannya karena instruksi yang macet memblokir semua instruksi di belakangnya meskipun semuanya siap. Kesenjangan antara lebar penerbitan dan peluang yang tersisa itulah yang mendorong lahirnya penjadwalan dinamis.

Out-of-order dan penjadwalan dinamis#

Eksekusi out-of-order adalah penjadwalan dinamis, yaitu keputusan urutan eksekusi diambil oleh perangkat keras setiap clock berdasarkan kesiapan operand, bukan berdasarkan urutan program. Instruksi yang sudah didekode ditampung dalam instruction window, yaitu penampung kecil di dalam prosesor, dan setiap clock prosesor memeriksa isinya lalu menerbitkan instruksi yang operandnya sudah siap apa pun letaknya dalam urutan program. Instruksi yang masih menunggu hasil tetap menunggu di dalam window, sedangkan instruksi bebas yang letaknya di belakang maju lebih dahulu.

Sebelum masuk ke window, ketergantungan semu perlu dibersihkan dengan register renaming. Dua instruksi yang menulis register yang sama, atau satu instruksi yang menulis pada saat instruksi lain masih membaca register itu, tidak benar-benar bergantung pada datanya, melainkan hanya berebut nama register. Register renaming memberi register fisik yang berbeda untuk setiap penulisan, sehingga ketergantungan atas nama itu hilang dan instruksi yang benar-benar bebas dapat dieksekusi bersamaan. Pola penjadwalan dinamis semacam ini dipopulerkan oleh algoritma Tomasulo pada era 1960-an, dan detail lengkapnya berada di luar cakupan topik ini.

Dua hal menentukan perilaku penjadwalan dinamis. Pertama, hasil eksekusi tidak langsung mengubah keadaan program, karena pengesahan hasil (commit) tetap berjalan sesuai urutan program, sehingga keadaan akhir register dan memori persis seperti eksekusi berurutan. Kedua, sumber dayanya terbatas, karena window dan register fisik tambahan hanya berukuran tertentu, sehingga prosesor dapat kehabisan tempat dan terpaksa kembali menerbitkan instruksi sesuai urutan. Instruksi dari jalur tebakan cabang juga ikut masuk ke window dan dieksekusi secara spekulatif, sehingga tebakan yang meleset memaksa pembuangan hasilnya, dengan penanganan lengkap pada topik Prediksi Cabang dan Spekulasi.

Simulasi jadwal in-order dan out-of-order#

Berkas jadwal.py menyusun jadwal terbit untuk enam instruksi fiktif yang memuat ketergantungan, pada model prosesor berlebar dua dengan latensi mul dua clock dan add satu clock. Aturannya sederhana, yaitu instruksi hanya boleh terbit setelah seluruh produsen operandnya selesai, versi in-order melarang melewati instruksi yang menunggu, sedangkan versi out-of-order memilih instruksi siap yang paling awal dalam urutan program. Jalankan berkasnya, lalu bandingkan kedua jadwalnya.

python jadwal.py 
"""Perbandingan jadwal terbit in-order dan out-of-order pada enam instruksi.

Model: prosesor menerbitkan paling banyak dua instruksi per clock, mul
berlatensi dua clock, add berlatensi satu clock, dan hasil sebuah
instruksi siap dipakai pada clock setelah latensinya berakhir.
Instruksi hanya boleh terbit bila seluruh produsen operandnya selesai.
"""

LEBAR = 2  # maksimum instruksi yang diterbitkan per clock
LATENSI = {"mul": 2, "add": 1}

# (mnemonik, register tujuan, register sumber, tampilan)
PROGRAM = [
    ("mul", "R2", ("R0", "R1"), "mul  R2, R0, R1"),
    ("add", "R3", ("R2", "R2"), "add  R3, R2, R2"),
    ("add", "R4", ("R3", "R2"), "add  R4, R3, R2"),
    ("add", "R5", ("R0", "R1"), "add  R5, R0, R1"),
    ("add", "R6", ("R5", "R5"), "add  R6, R5, R5"),
    ("add", "R7", ("R4", "R6"), "add  R7, R4, R6"),
]


def jadwal(boleh_lewati):
    """Susun jadwal terbit enam instruksi.

    boleh_lewati False berarti in-order: instruksi terdepan yang belum siap
    memblokir seluruh instruksi di belakangnya. True berarti out-of-order:
    instruksi siap yang paling awal dalam urutan program terbit lebih dahulu.
    """
    n = len(PROGRAM)
    terbit = [0] * n   # clock penerbitan tiap instruksi
    selesai = [0] * n  # clock saat hasil tiap instruksi siap
    produksi = {p[1]: i for i, p in enumerate(PROGRAM)}
    tersisa = n
    c = 1
    while tersisa:
        slot = 0
        for i in range(n):
            if terbit[i]:
                continue
            if slot == LEBAR:
                break
            sumber_siap = all(
                produksi.get(rs) is None
                or (terbit[produksi[rs]] and selesai[produksi[rs]] <= c)
                for rs in PROGRAM[i][2]
            )
            if sumber_siap:
                terbit[i] = c
                selesai[i] = c + LATENSI[PROGRAM[i][0]]
                slot += 1
                tersisa -= 1
            elif not boleh_lewati:
                break
        c += 1
    return terbit, c - 1


def cetak(judul, terbit, total):
    print(judul)
    for c in range(1, total + 1):
        isi = ", ".join(
            f"I{i + 1}" for i in range(len(PROGRAM)) if terbit[i] == c
        ) or "(stall)"
        print(f"  clock {c}: {isi}")
    print(f"  total {total} clock")


print("Program uji (lebar terbit 2, latensi mul 2 clock, latensi add 1 clock):")
for i, p in enumerate(PROGRAM):
    print(f"  I{i + 1}: {p[3]}")
print()

terbit, total = jadwal(False)
cetak("Jadwal in-order (instruksi yang menunggu memblokir yang di belakangnya):", terbit, total)
print()

terbit, total = jadwal(True)
cetak("Jadwal out-of-order (instruksi siap terbit tanpa menunggu urutan):", terbit, total)
text Keluaran 
Program uji (lebar terbit 2, latensi mul 2 clock, latensi add 1 clock):
  I1: mul  R2, R0, R1
  I2: add  R3, R2, R2
  I3: add  R4, R3, R2
  I4: add  R5, R0, R1
  I5: add  R6, R5, R5
  I6: add  R7, R4, R6

Jadwal in-order (instruksi yang menunggu memblokir yang di belakangnya):
  clock 1: I1
  clock 2: (stall)
  clock 3: I2
  clock 4: I3, I4
  clock 5: I5
  clock 6: I6
  total 6 clock

Jadwal out-of-order (instruksi siap terbit tanpa menunggu urutan):
  clock 1: I1, I4
  clock 2: I5
  clock 3: I2
  clock 4: I3
  clock 5: I6
  total 5 clock

Jadwal in-order memperlihatkan harga urutan yang kaku. Pada clock 2, kepala jadwal I2 masih menunggu R2 dari I1 yang berlatensi dua clock, sehingga clock itu tercatat (stall), yaitu clock tanpa satu instruksi pun diterbitkan meskipun I4 sudah siap. Keterlambatan itu merambat sampai I5 yang hanya bisa terbit setelah I4 selesai. Totalnya enam clock. Jadwal out-of-order mengisi clock 2 dengan I5 dan menyusun ulang sisanya, sehingga totalnya lima clock.

Lima clock bukan kebetulan, melainkan batas rantai ketergantungan I1, I2, I3, dan I6. I1 butuh dua clock sebelum R2 siap, lalu I2, I3, dan I6 menyusul satu clock demi satu clock karena masing-masing membaca hasil sebelumnya, sehingga lima clock adalah batas bawah mutlak untuk program ini pada latensi yang sama. Jadwal out-of-order mencapai batas itu dengan menggeser I4 dan I5 ke celah yang ditinggalkan rantai, sedangkan jadwal in-order membayar satu clock kosong karena urutannya. Perlu ditegaskan juga bahwa perubahan ini hanya menyusun ulang penerbitannya, karena ketergantungan data tetap menjamin tiap instruksi membaca nilai yang sama seperti pada urutan program.

Kesalahan umum#

Kesalahan pertama adalah menganggap lebar penerbitan menentukan speedup secara proporsional. Lebar empat tidak mengubah program yang penuh rantai ketergantungan menjadi empat kali lebih cepat, karena slotnya tetap kosong bila instruksinya saling menunggu, dan peluang paralelnya memang milik program. Perbaikannya berada pada kedua sisi, yaitu algoritma yang mengurangi ketergantungan dan perangkat keras yang memanfaatkan sisa peluangnya dengan lebih baik.

Kesalahan kedua adalah menyangka eksekusi out-of-order mengubah hasil program. Urutan penerbitan boleh berantakan, tetapi commit tetap berjalan sesuai urutan program, sehingga keadaan akhir register dan memori persis sama dengan eksekusi berurutan. Apabila hasilnya benar-benar berbeda, yang terjadi adalah bug pada perangkat keras atau modelnya, bukan perilaku wajar penjadwalan dinamis.

Kesalahan ketiga adalah menyamakan pipeline dengan superscalar. Pipeline membagi satu instruksi menjadi tahap-tahap yang berurutan agar satu instruksi baru dapat dimulai setiap clock, sedangkan superscalar menerbitkan beberapa instruksi pada clock yang sama. Keduanya dapat dipadukan, dan prosesor modern memakai keduanya sekaligus, tetapi manfaat dan biayanya berbeda, karena pipeline memperpendek clock sedangkan superscalar menambah jalur datanya.

Ringkasan#

  • ILP adalah peluang menjalankan instruksi yang saling bebas secara bersamaan dalam satu aliran program, dan besarnya ditentukan ketergantungan data, bukan oleh prosesor semata.
  • Prosesor superscalar menerbitkan beberapa instruksi per clock dengan menduplikasi jalur pengambilan dan penafsirannya, tetapi slotnya kosong bila instruksi berikutnya menunggu hasil.
  • Eksekusi out-of-order menampung instruksi dalam instruction window, menerbitkan yang siap lebih dahulu, dan mengesahkan hasilnya sesuai urutan program, dengan register renaming menghilangkan ketergantungan semu.
  • Simulasi jadwal.py menunjukkan out-of-order mengisi clock yang terbuang dan mencapai batas rantai ketergantungannya, yaitu lima clock berbanding enam clock in-order.

Referensi#