Akselerator Khusus

CPU dirancang untuk menjalankan program apa pun, padahal banyak beban kerja nyata berputar pada satu pola perhitungan yang tetap, misalnya perkalian matriks pada inferensi model. Topik ini membahas akselerator khusus, yaitu perangkat keras yang dibangun untuk satu jenis pekerjaan tertentu, mulai dari definisi ASIC dan FPGA, alasan spesialisasi menurunkan energi per operasi, peran NPU dan TPU, sampai array systolic yang menjadi inti banyak akselerator modern. Pembahasan ditutup dengan simulasi array systolic 3x3 yang dapat dijalankan untuk melihat isi setiap sel pada tiap gelombangnya.

ASIC dan FPGA#

ASIC (application-specific integrated circuit) adalah sirkuit terpadu yang seluruh jalur datanya ditentukan pada saat perancangan untuk satu tugas tertentu. Tidak ada penafsiran instruksi di dalamnya, karena yang dibangun memang langsung sirkuit untuk pekerjaan tersebut, dan bentuk itu tidak dapat diubah setelah produksi. Sebaliknya, FPGA (field-programmable gate array) adalah chip yang berisi jutaan sel logika kecil yang koneksinya dapat dirangkai ulang oleh penggunanya, sehingga sirkuit khusus dapat dibentuk setelah chip diproduksi. Kedua bentuk ini menempati spektrum yang sama dengan CPU, yaitu menukar fleksibilitas dengan efisiensi, hanya pada posisi yang berbeda.

Spesialisasi menang karena fleksibilitas yang tidak dipakai dapat dihapus sepenuhnya. CPU membayar biaya umum untuk kemampuannya yang umum, yaitu pengambilan dan penafsiran instruksi, prediksi cabang, serta cache yang harus mengakomodasi pola akses apa pun, sedangkan pada ASIC transistor yang tersisa seluruhnya bekerja pada aritmetika yang diminta. Akibatnya energi per operasi turun tajam dan area untuk performa yang sama menjadi lebih kecil. FPGA membayar harga di antara keduanya, karena sel logika yang dapat dirangkai ulang beserta jaringan penghubungnya memakan area dan menurunkan kecepatan tertinggi yang dapat dicapai. Oleh karena itu, pilihan antara ketiganya bergantung pada kepastian beban kerja dan volume produksinya.

NPU dan TPU untuk perkalian matriks#

Beban kerja yang paling sering mendapat akselerator hari ini adalah inferensi model, yaitu menjalankan model yang sudah selesai dilatih untuk menghasilkan prediksi. Inti perhitungannya adalah perkalian matriks besar yang diulang terus-menerus, karena setiap lapisan model mengalikan matriks bobot dengan matriks aktivasi dari lapisan sebelumnya. Perkalian semacam ini padat, teratur, dan hampir tanpa percabangan, sehingga sangat cocok untuk sirkuit yang dibangun khusus untuknya. Ukurannya juga besar, yaitu matriks dengan ribuan baris dan kolom pada model modern, sehingga kebutuhan aritmetikanya jauh melampaui kemampuan beberapa lane SIMD milik CPU.

NPU (neural processing unit) adalah akselerator inferensi yang dipasang pada ponsel dan perangkat tepi, sedangkan TPU (tensor processing unit) adalah akselerator yang dibangun Google untuk pusat data dan dijelaskan pada paper tahun 2017. Keduanya memuat ribuan unit perkalian-akumulasi (multiply-accumulate, MAC), yaitu sirkuit yang menghitung $a \times b + c$ dalam satu langkah, yang disusun menjadi array dua dimensi. Presisi yang dipakai sengaja rendah, misalnya int8 dengan satu byte per nilai, karena inferensi tidak menuntut presisi penuh floating point dan nilai yang lebih kecil menghemat kabel, energi, serta area, sehingga lebih banyak MAC muat pada chip yang sama.

Hambatan utamanya bukan aritmetika melainkan pemindahan data. Ribuan MAC hanya berguna bila pasokan nilai dari memori tidak pernah kering, sehingga perancang akselerator sekaligus merancang aliran datanya, yaitu bagaimana masukan tiba, berpindah, dan dipakai ulang di dalam array. Jawaban yang paling berpengaruh atas pertanyaan itu adalah pola berikutnya, yaitu array systolic.

Array systolic#

Array systolic (systolic array) adalah kumpulan sel perkalian yang tersusun teratur dan mengalirkan data dari satu tetangga ke tetangga berikutnya dalam denyut yang seragam. Nama ini merujuk pada denyut jantung karena datanya berpindah berirama seperti aliran darah pada pembuluh, sebagaimana istilah itu diperkenalkan oleh Kung dan Leiserson pada akhir era 1970-an. Setiap sel, yang disebut processing element (PE), menyimpan satu akumulator, menerima nilai dari tetangga sebelah barat dan sebelah utara, mengalikan keduanya, menambahkan hasilnya ke akumulator, lalu meneruskan kedua nilai ke tetangga berikutnya. Sel tidak pernah mengambil data dari memori sendiri, sehingga seluruh array hanya memerlukan sedikit jalur menuju memori.

Konsekuensi utamanya adalah pemakaian ulang nilai. Elemen A[i][k] yang masuk dari barat melewati seluruh sel pada barisnya dan dipakai untuk perkalian di setiap sel yang dilewatinya, sedangkan elemen B[k][j] yang masuk dari utara dipakai oleh seluruh sel pada kolomnya. Untuk matriks berukuran $n \times n$, hubungan yang dihitung setiap sel adalah $C_{i,j} = \sum_{k} A_{i,k} \times B_{k,j}$, dan jumlah perkaliannya memang tetap $n^3$, sama seperti perkalian matriks biasa. Yang dihemat adalah pengambilan operand dari hierarki memori, yaitu bagian termahal dari sisi energi, bukan jumlah perkaliannya. Diagram berikut memperlihatkan aliran data pada array 3x3.

Nilai A[0][k] sampai A[2][k] memasuki array dari barat, satu nilai per baris, dan diteruskan ke timur setelah dipakai. Nilai B[k][0] sampai B[k][2] memasuki array dari utara, satu nilai per kolom, dan diteruskan ke selatan. Setiap sel menambahkan hasil kali kedua nilai yang sedang melewatinya ke akumulator C miliknya, sehingga setelah seluruh gelombang selesai, akumulator setiap sel berisi satu elemen hasil akhir.

Simulasi tiga gelombang pada matriks 3x3#

Simulasi berikut memodelkan array systolic 3x3 dengan aturan yang paling sederhana. Setiap sel menyimpan satu akumulator yang dimulai dari nol, dan pada gelombang ke-k setiap sel mengalikan A[i][k] dengan B[k][j] lalu menambahkan hasilnya ke akumulatornya. Jadwalnya disederhanakan dengan menyelaraskan fase seluruh sel, sehingga tiga gelombang cukup untuk menyelesaikan matriks 3x3, sedangkan array nyata mengalirkan nilai dengan jeda satu siklus antartetangga sehingga gelombangnya bergerak diagonal. Penyederhanaan ini tidak mengubah jumlah perkalian maupun jumlah pengambilan nilai dari memori. Jalankan berkasnya, lalu perhatikan baris yang menyebut gelombang mana yang sedang berjalan.

# Simulasi array systolic 3x3 untuk perkalian matriks C = A×B.
# Setiap sel menyimpan satu akumulator C[i][j]. Pada gelombang ke-k,
# elemen A[i][k] mengalir ke timur sepanjang baris i dan elemen
# B[k][j] mengalir ke selatan sepanjang kolom j, sehingga setiap
# sel cukup mengalikan dua nilai yang sedang melewatinya.

N = 3

A = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]
B = [
    [9, 8, 7],
    [6, 5, 4],
    [3, 2, 1],
]

c = [[0] * N for _ in range(N)]  # akumulator milik setiap sel

def cetak_c(judul):
    print(judul)
    for baris in c:
        print("  " + " ".join(f"{x:4d}" for x in baris))

for k in range(N):
    print(f"Gelombang {k + 1}: kolom {k} A mengalir ke timur, baris {k} B mengalir ke selatan")
    for i in range(N):
        for j in range(N):
            a_berjalan = A[i][k]  # nilai yang tiba dari barat
            b_berjalan = B[k][j]  # nilai yang tiba dari utara
            c[i][j] += a_berjalan * b_berjalan
    cetak_c("  isi sel setelah gelombang:")
    print()

cetak_c("Hasil akhir C = A×B:")
print(f"Perkalian dilakukan {N * N * N} kali dengan hanya {2 * N * N} nilai yang dibaca dari memori")
print(f"Setiap nilai yang dibaca dipakai {N} sel sebelum mengalir keluar")

Gelombang 1: kolom 0 A mengalir ke timur, baris 0 B mengalir ke selatan
  isi sel setelah gelombang:
     9    8    7
    36   32   28
    63   56   49

Gelombang 2: kolom 1 A mengalir ke timur, baris 1 B mengalir ke selatan
  isi sel setelah gelombang:
    21   18   15
    66   57   48
   111   96   81

Gelombang 3: kolom 2 A mengalir ke timur, baris 2 B mengalir ke selatan
  isi sel setelah gelombang:
    30   24   18
    84   69   54
   138  114   90

Hasil akhir C = A×B:
    30   24   18
    84   69   54
   138  114   90
Perkalian dilakukan 27 kali dengan hanya 18 nilai yang dibaca dari memori
Setiap nilai yang dibaca dipakai 3 sel sebelum mengalir keluar

Keluaran memperlihatkan isi seluruh sel setelah setiap gelombang. Setelah gelombang pertama, setiap sel memuat hasil kali gelombang pertama saja, misalnya sel (0,0) memuat $1 \times 9 = 9$. Setelah gelombang kedua dan ketiga, nilai baru tiba dan terakumulasi, sehingga sel yang sama memuat 21 lalu 30, yaitu jumlah lengkap C[0][0]. Baris statistik pada akhir keluaran merangkum penghematannya, yaitu 27 perkalian yang hanya menuntut 18 nilai dari memori, sedangkan perkalian matriks biasa dengan tiga perulangan menuntut dua pengambilan operand untuk setiap perkalian sehingga totalnya 54.

Kesalahan umum#

Tiga kekeliruan berikut paling sering muncul ketika akselerator khusus dinilai, dan setiap butirnya menyebut penyebab beserta perbaikannya.

1. Menganggap akselerator mempercepat semua beban kerja. Akselerator menang pada pola yang cocok dengan sirkuitnya, misalnya perkalian matriks padat, sedangkan beban kerja yang didominasi percabangan dan akses memori tidak teratur tetap membutuhkan CPU. Perbaikannya adalah memprofilkan beban kerja terlebih dahulu, lalu mencocokkan pola yang dominan dengan sirkuit yang ditawarkan.
2. Mengukur performa tanpa memperhitungkan pemindahan data. Waktu yang habis untuk mengirim masukan dan mengambil hasil dapat menghabiskan keuntungan aritmetikanya, terutama pada data kecil yang mengirim sedikit pekerjaan sekaligus. Perbaikannya adalah mengukur seluruh pekerjaan dari masukan sampai hasil, bukan hanya operasi intinya.
3. Menyamakan FPGA dan ASIC. FPGA dapat dirangkai ulang tetapi membayar area dan batas kecepatan untuk fleksibilitas itu, sedangkan ASIC lebih efisien dan tidak dapat diubah setelah produksi. Perbaikannya adalah memilih FPGA ketika rancangan masih berubah dan ASIC ketika beban kerja sudah stabil dengan volume produksi besar.

Ringkasan#

• ASIC menukar fleksibilitas dengan efisiensi, yaitu seluruh transistornya bekerja pada satu tugas sehingga energi per operasi dan luas areanya lebih kecil daripada CPU, sedangkan FPGA menempati posisi tengah dengan sirkuit yang dapat dirangkai ulang.
• NPU dan TPU adalah akselerator untuk perkalian matriks besar pada inferensi model, berupa ribuan unit MAC dengan presisi rendah seperti int8.
• Array systolic mengalirkan data antarsel tetangga sehingga satu nilai dari memori dipakai banyak sel, dan penghematannya terletak pada pengambilan operand, bukan pada jumlah perkalian.
• Simulasi 3x3 menyelesaikan perkalian matriks dalam tiga gelombang dengan 27 perkalian dari 18 nilai memori, berbanding 54 pengambilan operand pada cara biasa.

Referensi#

• In-Datacenter Performance Analysis of a Tensor Processing Unit — Jouppi dkk. (arXiv) — Paper TPU yang menjelaskan array systolic 256x256 di dalamnya beserta alasan domain khusus mengungguli CPU pada inferensi.
• Computer Systems: A Programmer’s Perspective, edisi ketiga — Randal Bryant dan David O’Hallaron — Buku yang membahas hierarki memori dan biaya pengambilan data yang menjadi hambatan utama akselerator.