Oleh: Edmond Febrinicko Armay
Sudoku adalah teka-teki penempatan angka yang menggunakan grid bujur sangkar 9×9 yang mana angka 1 sampai 9 ditempatkan. Grid tersebut dibagi menjadi kotak 3×3, dalam masing-masing sel 3×3. Teka-teki dimulai dengan grid yang hampir kosong dengan beberapa sel yang terisi. Tujuan teka-teki adalah mengisi grid sehingga setiap baris, kolom, dan kotak 3×3 mengandung angka 1 sampai 9. Secara implisit, ini berarti bahwa baris, kolom, atau kotak tidak boleh memiliki angka yang berulang di dalamnya, seperti terlihat pada Gambar 1.
Gambar 1: Grid awal dan grid akhir pada teka-teki Sudoku [1]
Tantangan yang dihadapi adalah bagaimana membangkitkan teka-teki dengan 39 petunjuk – satu dengan 38 petunjuk yang telah diproduksi oleh orang lain. Terdapat lebih dari 6×1021 Sudoku dalam grid 9×9. Menggunakan brute force untuk mencoba seluruh kombinasi angka bukanlah pemrograman komputer yang sulit, tantangan sebenarnya adalah mendapatkan program komputer yang dapat menyelesaikan kalkulasi dalam seumur hidup programmer!
Tiga strategi yang digunakan untuk menurunkan waktu eksekusi:
- Langkah 1: Mengubah algoritma untuk memintas pendekatan brute force
- Langkah 2: Mengoptimalkan kode serial, mengambil keuntungan dari instruksi Streaming Single Instruction Multiple Data (SIMD) Extension (SSE)
- Langkah 3: Menambahkan paralelisme
Metodologi
Langkah 1: Mengubah Algoritma
Desain program Sudoku yang digunakan terdiri dari dua komponen: generator dan solver. Generator mengambil teka-teki yang ada, menghapus satu atau dua petunjuk, kemudian menggunakan solver rekursif untuk menghasilkan teka-teki baru, daripada menggunakan metode brute force untuk menciptakan semua kemungkinan solusi yang berbeda.
Gambar 2 memperlihatkan bagaimana menciptakan teka-teki 17 petunjuk.
Gambar 2: Generator dan solver [1]
Generator menghapus dua petunjuk dari teka-teki 18 petunjuk, menambah satu petunjuk baru, kemudian menggunakan solver untuk mencari solusi yang valid. Sebagai contoh, dalam teka-teki di bawah ini pada Gambar 3, petunjuk 3 dan 9 dihapus dari kolom 1.
Gambar 3: Pembuatan Sudoku 17 petunjuk [2]
Solver mengisi setiap sel yang tidak terpecahkan dengan daftar alternatif yang valid.
Secara rekursif, solver memangkas alternatif untuk menemukan teka-teki yang valid, dan berhati-hati agar tidak ada petunjuk yang berlebihan. Metode pembuatan teka-teki baru ini dikenal sebagai algoritma “-2+1”. Teknik yang sama digunakan untuk menemukan ‘thirty-niner’. Menggunakan ‘thirty-eighter’, satu petunjuk dihapus dan menambahkan dua petunjuk baru – dikenal sebagai algoritma “-1+2”.
Langkah 2: Mengoptimalkan Kode Serial
Central Processing Unit (CPU) modern memiliki instruksi yang dapat bekerja pada lebih dari satu item data pada saat yang sama yaitu SIMD. Mengganti instruksi tradisional dengan instruksi SIMD dapat menyebabkan kode berjalan lebih cepat. Contoh instruksi tersebut termasuk MMX dan berbagai SSE (SSE2, SSE3, SSE4).
SSE adalah fungsi assembly yang dibuat oleh compiler yang dapat dipanggil dari kode C/C++ dan menyediakan akses tingkat rendah ke fungsi SIMD tanpa perlu menggunakan bahasa assembly. SSE dapat meningkatkan keterbacaan kode, membantu penjadwalan instruksi, dan membantu mengurangi upaya debugging daripada menggunakan bahasa assembly. SSE memberikan akses ke instruksi yang tidak dapat dihasilkan menggunakan konstruksi standar bahasa C dan C++.
Compiler Intel® mendukung berbagai ekstensi arsitektur dari instruksi MMX awal hingga instruksi generasi terbaru SSE4. Kode pada Gambar 4 memperlihatkan bagaimana register 128 bit SSE2 digunakan dalam kode Sudoku.
| for(int num=0; num < 9; num++)
{ __m128i xmm0 = _mm_and_si128(BinSmallNum, BinNum[num]); for(int i=0; i < 9; i++) { __m128i BoxSum = _mm_and_si128(BinBox[i], xmm0); __m128i RowSum = _mm_and_si128(BinRow[i], xmm0); __m128i ColumnSum = _mm_and_si128(BinColumn[i], xmm0); if (ExactlyOneBit(BoxSum)) { int cell=BitToNum(BoxSum); FoundNumber(cell, num); return true; } } } |
Gambar 4: Penggunaan SSE2 untuk meningkatkan kinerja
Variabel xmm0 menjadi bitmask untuk semua kemunculan angka tertentu, sedangkan variabel i digunakan untuk melintasi setiap baris, kolom dan kotak. Penggunaan register SSE2 menghasilkan speedup beberapa ratus kali menggunakan perangkat keras yang sama.
Langkah 3: Menambahkan Paralelisme
Task OpenMP dapat digunakan untuk menambahkan paralelisme ke looping, linked list, dan panggilan rekursif. Gambar 5 adalah contoh penggunaan task OpenMP.
| #pragma omp parallel
{ #pragma omp single nowait { For (int i=0; i< NUM_NODES -1; i++) { NODE Node1 = pPuzzle ->Nodes [i]; if (Node1.number > 0) { //buat salinan node tingkat atas; memcpy (&gPuzzles[i], pPuzzle, sizeof (SUDOKU)); #pragma omp taskprivate(i) GenDoWork (&gPuzzles[i],i); } } } } |
Gambar 5: Kode yang menggunakan task OpenMP
Task #pragma omp parallel adalah kumpulan thread, sedangkan task #pragma omp single nowait adalah suatu thread yang mengeksekusi looping “for”. Thread tunggal “for” membuat task untuk setiap fungsi GenDoWork().
Intel® Parallel Studio mendukung sejumlah cara yang berbeda untuk memparalelkan suatu program komputer. Diagram pada Gambar 6 memperlihatkan Intel® Parallel Building Blocks yang menawarkan banyak dukungan untuk pemrograman paralel.
Gambar 6: Intel® Parallel Building Blocks menawarkan beberapa model pemrograman paralel [2]
Cilk Plus adalah salah satu cara termudah untuk memparalelkan program yang ada. Penambahan Cilk ke kode C yang ada sangatlah mudah, karena Cilk menggunakan tiga kata kunci: cilk_spawn, cilk_sync, dan cilk_for. Setelah header cilk.h dimasukkan dalam file, kata kuncinya dapat digunakan seperti terlihat pada Gambar 7.
| #include <cilk/cilk.h>
void work(int num} { //tambahkan kode di sini } void func1() { cilk_spawn work(1); work(2); cilk_sync; } void func2() { cilk_for(int i=0; i<9; i++) { work(3); } } |
Gambar 7: Tiga kata kunci Intel Cilk Plus
Baris antara cilk_spawn dan cilk_sync dikenal sebagai continuation. cilk_spawn memberikan izin ke runtime untuk menjalankan fungsi work(1) secara paralel dengan kode continuation. Jika ada pekerja cadangan yang tersedia, penjadwal mencuri kode continuation dari pekerja pertama dan menugaskannya ke pekerja kedua – pada saat yang sama pekerja pertama terus melaksanakan fungsi work(1). Kode akan kembali ke eksekusi serial setelah cilk_sync. cilk_for menggantikan C/C++ standar untuk looping. Looping di-share antara pekerja yang tersedia. Tidak ada jaminan urutan eksekusi tertentu. Program komputer terus berlanjut setelah semua looping dieksekusi. Jika looping melakukan jumlah pekerjaan yang tidak seimbang maka load balancing akan dijaga oleh algoritma penjadwal.
Di Cilk, programmer tidak mengontrol paralelisme suatu program, tapi hanya mengekspresikan niat. Programmer memberi izin agar kode dijalankan secara paralel dengan menempatkan kata kunci Cilk dalam program. Keputusan apakah menjalankan kode secara paralel atau tidak, dibuat oleh penjadwal Cilk pada saat runtime. Runtime Intel Cilk Plus menangani load balancing secara otomatis.
Gambar 8 memperlihatkan kode Sudoku dibuat paralel menggunakan kata kunci cilk_for.
| #include <cilk/cilk.h>
. . . cilk_for(int i = 0 ; i < NUM_NODES -1; i++ ) { NODE Node1 = pPuzzle->Nodes[i]; if(Node1.number > 0) { //buat salinan node tingkat atas; memcpy(&gPuzzles[i],pPuzzle,sizeof(SUDOKU)); GenDoWork(&gPuzzles[i],i); } } |
Gambar 8: Penambahan cilk_for pada kode Sudoku
Kode dimasukkan di tempat yang sama dengan task OpenMP (Gambar 5). Programmer harus berhati-hati agar tidak ada data race ketika membuat kode paralel. Jika ada variabel global maka kode harus dikerjakan ulang sehingga ruang lingkup variabel dibatasi oleh penggunaan variabel lokal atau variabel otomatis daripada variabel global. Jika mustahil menghapus semua variabel global, maka akses ke variabel tersebut harus dilindungi sehingga hanya satu thread dapat memodifikasinya pada suatu waktu.
Di Cilk, cara termudah menangani variabel global dan variabel share adalah menyatakannya sebagai reducer. Ketika pekerja mengakses reducer, pekerja diberikan tampilan pribadinya sendiri yang dapat dimanipulasi dengan aman. Tampilan kemudian digabungkan di bagian kode serial dengan panggilan fungsi get_value(). Kode pada Gambar 9 memperlihatkan bagaimana variabel global gNumCilkPuzzlesSolved dinyatakan sebagai reducer_opadd.
| int gNumCilkPuzzlesSolved; //variabel global
. . gNumCilkPuzzlesSolved++; //suatu tempat dalam kode paralel . . int Tmp = gNumCilkPuzzlesSolved; //suatu tempat dalam kode serial |
#include <cilk/reducer_oppad.h> cilk::reducer_opadd<int> gNumCilkPuzzlesSolved;
. . gNumCilkPuzzlesSolved++; //dalam kode paralel . . int Tmp = gNumCilkPuzzlesSolved.get_value(); //dalam kode serial |
| (a) | (b) |
Gambar 9: Perbaikan masalah data race menggunakan reducer Intel Cilk Plus, (a) Variabel global gNumCilkPuzzlesSolved tidak aman digunakan dalam kode paralel, (b) Variabel global dinyatakan sebagai reducer sehingga aman diakses
Panggilan fungsi get_value() yang dipanggil dari bagian kode serial menggabungkan semua nilai reducer sehingga memperoleh nilai yang benar.
Hasil
Setelah kode paralel ditambahkan ke program Sudoku, didapat bahwa pada komputer quad core Surface-Mount Technology (SMT) – yang mendukung 12 thread perangkat keras – seluruh thread perangkat keras tetap sibuk seperti terlihat pada Gambar 10.
Gambar 10: Setiap thread perangkat keras berjalan pada penggunaan 100% dengan paralelisme yang diimplementasikan dalam kode [2]
Sebagai hasil dari pekerjaan yang dilakukan, tiga “thirty-niner” baru ditemukan seperti terlihat pada Gambar 11.
Gambar 11: Tiga solusi minimal dari Sudoku 39 petunjuk ditemukan menggunakan algoritma -1+2 [2]
Referensi
- Blair-Chappell, A. Stokes, Parallel Programming with Intel Parallel Studio XE, John Wiley & Sons, Inc., 2012.
- Blair-Chappell, The World’s First Sudoku* ‘Thirty-Niner’, The Parallel Universe, Issue 3, June 2010, hal. 20-25.