KAL
Menu

Jebakan paralel

Race condition, hasil not-a-number, dan false sharing beserta cara menghindarinya.

Daftar isi

Kode paralel memperkenalkan kelas kesalahan yang tidak pernah muncul pada kode serial, dan sebagian besar di antaranya tidak terdeteksi kompiler. Topik ini membahas tiga jebakan yang paling sering ditemui, yaitu race condition pada data bersama, nilai not-a-number yang muncul dari operasi numerik tak sah, serta false sharing yang menggerus kinerja tanpa membuat hasil salah. Setiap jebakan diperagakan atau dijelaskan melalui program yang dikompilasi dan dijalankan sungguhan dengan gfortran, lengkap dengan cara menghindarinya. Setelah topik ini selesai dibaca, penyebab ketiganya dan solusi yang menyertainya sudah dikenali.

Race condition pada penghitung bersama#

Race condition (race condition) adalah keadaan ketika hasil program bergantung pada urutan eksekusi yang tidak dapat diprediksi, dan penyebabnya adalah dua thread atau lebih mengakses lokasi memori yang sama tanpa pengaturan. Penugasan jumlah = jumlah + 1 terlihat seperti satu langkah, tetapi prosesornya menjalankan tiga langkah, yaitu membaca nilai, menambahkannya, lalu menulis kembali. Apabila dua thread membaca nilai yang sama sebelum salah satunya selesai menulis, pembaruan milik thread yang lebih lambat tertimpa dan satu penambahan hilang begitu saja.

Program berikut menjalankan penghitung tanpa pengaturan tersebut sepuluh kali dengan dua thread. Program sengaja tidak mencetak nilai penghitungnya satu per satu, karena nilai persisnya berubah-ubah antar eksekusi, dan keluarannya hanya melaporkan kesimpulan logika atas kesepuluh percobaan. Karena kesimpulan itu sendiri ikut berubah antar eksekusi, blok perintah di bawah ini tidak disertai blok Keluaran yang menuntut kesamaan persis; sebagai gantinya, satu eksekusi nyata ditampilkan terpisah dalam blok berjudul Satu eksekusi nyata yang teramati.

fortran penghitung_balapan.f90 
program penghitung_balapan
  use omp_lib
  implicit none
  integer, parameter :: n = 200000
  integer(kind=8) :: jumlah
  integer :: i, percobaan
  logical :: ada_keliru

  ada_keliru = .false.
  do percobaan = 1, 10
    jumlah = 0
    ! penghitung diperbarui tanpa reduction dan tanpa critical: operasi
    ! baca-tambah-tulis oleh banyak thread dapat saling menimpa
    !$omp parallel do
    do i = 1, n
      jumlah = jumlah + 1
    end do
    !$omp end parallel do
    if (jumlah /= int(n, kind=8)) then
      ada_keliru = .true.
    end if
  end do

  print '(A, I0)', 'thread yang digunakan             : ', omp_get_max_threads()
  print '(A, I0)', 'percobaan yang dilakukan          : ', 10
  print '(A, L1)', 'minimal satu percobaan keliru     : ', ada_keliru
  print '(A, I0)', 'nilai yang benar setiap percobaan : ', int(n, kind=8)
end program penghitung_balapan
bash 
# mengatur jumlah thread lebih dahulu, lalu mengompilasi dan menjalankan
export OMP_NUM_THREADS=2
gfortran -fopenmp penghitung_balapan.f90 -o penghitung_balapan
./penghitung_balapan
text Satu eksekusi nyata yang teramati 
thread yang digunakan             : 2
percobaan yang dilakukan          : 10
minimal satu percobaan keliru     : T
nilai yang benar setiap percobaan : 200000

Eksekusi yang teramati di atas melaporkan T, yaitu minimal satu dari sepuluh percobaan menghasilkan nilai yang keliru. Pada eksekusi ulang yang lain, baris kesimpulan yang sama pernah mencetak F, yaitu kesepuluh percobaan menghasilkan nilai yang benar. Hasil F seperti itu muncul apabila kedua thread kebetulan tidak pernah berjalan bersamaan pada satu percobaan pun, sehingga tidak ada penambahan yang saling menimpa. Nilai T atau F itu baru menunjukkan gejala tingkat akhir, yaitu benar atau tidaknya hasil keseluruhan; gejala yang lebih rinci terlihat pada nilai penghitung yang diamati langsung selama perulangan berlangsung.

Pengamatan langsung terhadap nilai penghitung di akhir setiap percobaan memperlihatkan dua pola hasil. Pola pertama adalah nilai akhir yang tepat 200000, artinya tidak ada penambahan yang saling menimpa karena kedua thread kebetulan bergantian tanpa bertabrakan. Pola kedua adalah nilai akhir yang jauh lebih kecil, berkisar sekitar 96000 sampai 130000, yang berarti sebagian besar penambahan hilang karena ditimpa oleh thread yang lain. Ketidakpastian antara dua pola inilah inti dari race condition, yaitu program yang sama dapat memberikan keluaran berbeda setiap kali dijalankan, dan kesalahannya berbahaya karena program tetap berhenti normal tanpa pesan apa pun.

Solusi dengan reduction dan critical#

Solusi pertama dan yang paling disarankan untuk akumulasi adalah klausa reduction, yang mekanismenya telah dibahas pada topik Direktif OpenMP di modul ini. Setiap thread memperbarui salinan privatnya sendiri, lalu hasil semua salinan digabungkan sekali di akhir region. Program berikut adalah versi aman dari penghitung yang sama, dan blok berjudul Keluaran di bawahnya adalah hasil asli eksekusinya.

fortran penghitung_aman.f90 
program penghitung_aman
  use omp_lib
  implicit none
  integer, parameter :: n = 200000
  integer(kind=8) :: jumlah
  integer :: i

  jumlah = 0
  !$omp parallel do reduction(+:jumlah)
  do i = 1, n
    jumlah = jumlah + 1
  end do
  !$omp end parallel do

  print '(A, I0)', 'thread yang digunakan : ', omp_get_max_threads()
  print '(A, I0)', 'jumlah akhir program  : ', jumlah
  print '(A, I0)', 'nilai yang benar      : ', int(n, kind=8)
end program penghitung_aman
bash 
# mengatur jumlah thread lebih dahulu, lalu mengompilasi dan menjalankan
export OMP_NUM_THREADS=2
gfortran -fopenmp penghitung_aman.f90 -o penghitung_aman
./penghitung_aman
text Keluaran 
thread yang digunakan : 2
jumlah akhir program  : 200000
nilai yang benar      : 200000

Dengan reduction, hasil akhirnya selalu 200000 dan sama dengan nilai yang benar, berapa pun jumlah thread yang dipakai. Solusi kedua adalah pernyataan critical yang membuat satu blok kode hanya boleh dieksekusi satu thread pada satu waktu, sebagaimana diperlihatkan fragmen berikut.

fortran Contoh: blok critical sebagai pengganti reduction 
! tidak-dijalankan
!$omp critical
jumlah = jumlah + 1
!$omp end critical

Bentuk critical menghasilkan nilai yang benar, tetapi seluruh thread mengantre untuk masuk ke blok yang sama, sehingga paralelismenya praktis hilang pada perulangan yang badannya pendek. Untuk pola akumulasi, reduction mempertahankan kerja paralel penuh dan hanya menggabungkan hasilnya sekali, sehingga keduanya tidak dapat ditukar begitu saja.

NaN dan operasi numerik tak sah#

Nilai not-a-number (NaN) adalah representasi khusus tipe real yang menandai hasil perhitungan yang tidak terdefinisi, misalnya pembagian nol dengan nol atau akar kuadrat dari bilangan negatif. Program berikut membangkitkan kedua operasi tersebut dan mendeteksinya dengan fungsi ieee_is_nan dari modul ieee_arithmetic. Program dikompilasi dan dijalankan dari direktori topik, dan blok berjudul Keluaran di bawahnya adalah hasil asli eksekusi tersebut.

fortran demo_nan.f90 
program demo_nan
  use, intrinsic :: ieee_arithmetic
  implicit none
  real :: nol, negatif, hasil_bagi, hasil_akar

  nol = 0.0
  negatif = -1.0
  hasil_bagi = nol / nol
  hasil_akar = sqrt(negatif)

  print '(A, L1)', 'ieee_is_nan(0.0/0.0)    : ', ieee_is_nan(hasil_bagi)
  print '(A, L1)', 'ieee_is_nan(sqrt(-1.0)) : ', ieee_is_nan(hasil_akar)
  print '(A, F6.1)', 'cetak 0.0/0.0           : ', hasil_bagi
  print '(A, ES12.3)', 'cetak sqrt(-1.0)        : ', hasil_akar
end program demo_nan
bash 
# mengompilasi dan menjalankan program dari direktori topik
gfortran demo_nan.f90 -o demo_nan
./demo_nan
text Keluaran 
ieee_is_nan(0.0/0.0)    : T
ieee_is_nan(sqrt(-1.0)) : T
cetak 0.0/0.0           :    NaN
cetak sqrt(-1.0)        :          NaN

Program ini deterministik, yaitu kedua operasi selalu menghasilkan NaN pada setiap eksekusi, berbeda dengan race condition yang keluarannya berpindah-pindah. Pada program paralel, NaN sering muncul dari pola yang berkaitan dengan race condition, misalnya variabel real yang dibaca sebelum diinisialisasi sehingga isinya berupa pola bit yang tidak mewakili bilangan yang sah. Nilai NaN juga menular, karena setiap perhitungan yang melibatkan NaN menghasilkan NaN lagi, sehingga satu elemen yang rusak dapat merusak seluruh hasil akhir. Pemeriksaan ieee_is_nan pada hasil antara yang mencurigakan adalah cara termurah untuk menemukan sumbernya.

False sharing#

False sharing adalah penurunan kinerja yang terjadi ketika dua thread menulis ke variabel berbeda yang kebetulan bertetangga pada satu baris cache (cache line) yang sama. Prosesor memindahkan memori antar inti dalam satuan baris cache, bukan satuan variabel, sehingga dua tulisan yang secara logika tidak bersaing tetap saling membatalkan salinan cache milik inti lain. Gejalanya khas, yaitu waktu eksekusi tidak turun meskipun jumlah thread dinaikkan, sementara hasil perhitungannya selalu benar sehingga kesalahan ini tidak pernah tampil sebagai nilai yang salah.

fortran Contoh: pola yang memicu false sharing 
! tidak-dijalankan
! dua thread menulis elemen yang berselang-seling, sehingga satu baris
! cache terus berpindah antar inti
do i = 1, n
  indeks = mod(i - 1, 2) + 1
  hasil(indeks) = hasil(indeks) + berat(i)
end do

Cara menghindarinya adalah menyusun akses data agar setiap thread bekerja pada wilayah memori yang terpisah dan berurutan, misalnya membagi rentang perulangan menjadi potongan besar dan berurutan lewat klausul schedule(static), yaitu klausul yang menetapkan pembagian iterasi menjadi potongan berurutan yang tetap untuk setiap thread. Pola pembagian kerja semacam ini senada dengan skema default worksharing yang telah dibahas pada topik Direktif OpenMP. Pola lainnya adalah memberi setiap thread array privatnya sendiri, lalu menggabungkan seluruh array itu di akhir region, sehingga penulisan antar thread tidak pernah bertetangga. Biaya penggabungan yang ditambahkan biasanya jauh lebih kecil daripada biaya baris cache yang terus berpindah.

Ringkasan#

  • Race condition muncul ketika banyak thread memperbarui satu lokasi data tanpa pengaturan, akibatnya nilai akhir berubah-ubah antar eksekusi, dan solusinya adalah reduction untuk akumulasi atau critical untuk blok yang harus berjalan tunggal.
  • NaN menandai hasil perhitungan yang tidak terdefinisi, menular ke seluruh perhitungan selanjutnya, dan dideteksi dengan ieee_is_nan dari modul ieee_arithmetic.
  • False sharing terjadi karena dua thread menulis ke satu baris cache yang sama, tidak mengubah hasil tetapi menggerus kinerja, dan dihindari dengan memisahkan wilayah tulis antar thread.

Referensi#