blognya komarudin bin sayuti

blognya komarudin bin sayuti header image 2

Multi thread simplex tableau

January 15th, 2012 · No Comments

Berawal ketika menonton ceramahnya Prof. Trick di sini, saya tertarik dengan konsep algoritma simpleks parallel. Sudah maklum bahwasanya algoritma branch and bound sangat mudah dijalankan secara parallel. Percabangan dalam branch and bound dapat dijalankan secara parallel karena hampir tidak ada interaksi resource (data) dengan percabangan yang lain. Akan tetapi, Prof. Trick mengisyaratkan algoritma simpleks sendiri perlu diimplementasikan secara parallel.

Penerapan algoritma simplex secara parallel diharapkan dapat menurunkan waktu komputasi yang dibutuhkan untuk persoalan-persoalan optimasi linear. Selain itu, karena algoritma simplex merupakan salah satu komponen penyusun algoritma lainnya, seperti branch and bound, maka diharapkan penerapan simplex secara parallel juga bisa memberikan kontribusi bagi parent-algoritma tersebut. Dengan algoritma simplex yang lebih cepat, proses fathoming/bounding akan menjadi lebih cepat juga. Akan tetapi perlu diteliti lebih jauh tentang perbandingan keuntungan yang didapat dengan memparalelkan simplex dengan memparalelkan percabangan/branching.

Saya mencoba untuk menerapkan konsep parallel/concurrent/multi-thread untuk algoritma simplex tableau. Algoritma ini saya pilih karena ia mudah diterapkan dan masih memiliki peranan penting untuk menyelesaikan persoalan dengan struktur matriks yg padat (dense). Selain itu, sebenarnya saya sudah pernah mengimplementasikan algoritma ini untuk Excel. Sehingga saya hanya perlu memporting kodenya ke bahasa pemrograman lain. Saya pilih C++ karena pernah bergelut dengannya ketika S2 dulu. Perlu dicatat bahwa implementasi parallel disini hanya untuk komputer dengan multi-core processors. Saya belum menerapkan algoritma parallel untuk multi-komputer yang berkomunikasi melalui network connection.

Kalau kita cermati algoritma simplex tableau, komputasi terbesar yang diperlukan adalah ketika meng-update tabel simplex-nya. Setelah mendapatkan baris pivot, maka kita perlu meng-update baris-baris lain dalam tabel tersebut. Jika jumlah kendala adalah m, dan jumlah variabel adalah n, maka kita perlu melakukan operasi mn tiap iterasi. Sehingga, disinilah letak bottleneck yang kiranya perlu dibuat secara parallel. Kalau kita amati lebih jauh, proses ini bisa dibuat secara parallel karena operasi update pada tiap baris tidak akan mempengaruhi operasi update pada baris yang lain.

Ide dari multi-thread yang saya terapkan adalah membagi matriks tableau menjadi sub-matriks yang lebih kecil. Kemudian sub-matriks tersebut di-update oleh thread yang berbeda. Secara teknis, jika sebuah matriks tableau berukuran m x n, kemudian kita ingin menggunakan k buah thread, maka sub matriksnya menjadi (m/k) x n. Sengaja saya memilih untuk membagi dalam rangkaian baris karena satu baris akan memiliki operasi update yang sangat mirip.

Untuk melihat performa dari algoritma multi-thread simplex matriks yang saya kembangkan, beberapa permasalahan simpleks dibangkitkan secara random. OK, di literatur ada banyak persoalan LP akan tetapi saya dikalahkan oleh kemalasan untuk mencari dan mengolah-nya . Di sini saya hanya akan menampilkan hasil untuk dua persoalan. Persoalan pertama berukuran 1000 x 1000 sedangkan persoalan kedua 5000 x 5000. Algoritma simpleks yang saya terapkan akan menambahkan sendiri variabel slack/surplus/artificial. Sehingga ukuran matriks sebenarnya untuk kedua persoalan ini bisa jadi lebih besar. Jumlah iterasi saya batasi masing-masing 10 000 dan 1 000 iterasi untuk problem 1000×1000 dan 5000×5000.

Kalau ada yang mau mencoba main-main, program dan dua contoh problem bisa didonlod di sini:

Opt_Lil_Khair

Berikut saya tampilkan tabulasi dari waktu komputasi algoritma simpleks untuk kedua problem di atas. Eksperimen sederhana ini saya lakukan di laptop kantor yang kelihatannya memiliki quad-core 2 cores and 4 threads maximum (hyper threading) configuration.

Keterangan:

  • Partition 0 artinya simplex tableau dilakukan oleh satu thread secara terus-menerus
  • Partition 1 artinya simplex tableau dilakukan oleh satu thread utama, kemudian tabelnya diupdate oleh thread anak
  • Partition >= 2 artinya tabel matriks dibagi menjadi beberapa partisi dan diupdate oleh thread yang berbeda

Terlihat dari tabel diatas, penggunaaan multi-thread dan multi-processor bisa menurunkan waktu komputasi. Perbandingan antara partition 0 dan 1 menunjukkan bahwa ada sejumlah overhead yang harus dibayar ketika menggunakan multi-thread. Sementara penggunaan partisi lebih dari 1 (termasuk di dalamnya penggunaan multi-thread) dapat menurunkan waktu komputasi. Akan tetapi perlu dicatat bahwa penurunan ini tidak sebanding dengan jumlah penggunaan thread yang digunakan.

Kurang baiknya penurunan waktu ini mungkin dijelaskan bahwa adanya overhead yang diperlukan untuk membagi pekerjaan dan berkomunikasi antar thread. Sementara, waktu komputasi per-iterasi yang sudah kecil membuat waktu overhead ini terlihat signifikan. Bisa jadi juga komputer saya yg kurang oke dalam menangani komputasi multi-thread. Akan tetapi yang jelas, kemampuan programmer yang menerapkan algoritma tersebut adalah sumber utama kurang bagusnya hasil ini .

Print Friendly, PDF & Email

Tags: Linear Programming · Mathematical programming