Algoritma Paralel - Model

Model algoritma paralel dikembangkan dengan mempertimbangkan strategi pembagian data dan metode pengolahan serta menerapkan strategi yang sesuai untuk mengurangi interaksi. Pada bab ini, kita akan membahas Model Algoritma Paralel berikut -

  • Model paralel data
  • Model grafik tugas
  • Model kolam kerja
  • Model budak master
  • Konsumen produsen atau model saluran pipa
  • Model hibrida

Data Paralel

Dalam model paralel data, tugas diberikan ke proses dan setiap tugas melakukan jenis operasi serupa pada data yang berbeda. Data parallelism merupakan konsekuensi dari operasi tunggal yang diterapkan pada beberapa item data.

Model data-paralel dapat diterapkan pada ruang alamat bersama dan paradigma penyampaian pesan. Dalam model data-paralel, overhead interaksi dapat dikurangi dengan memilih lokalitas yang mempertahankan dekomposisi, dengan menggunakan rutinitas interaksi kolektif yang dioptimalkan, atau dengan komputasi dan interaksi yang tumpang tindih.

Karakteristik utama dari masalah model data-paralel adalah bahwa intensitas paralelisme data meningkat dengan ukuran masalah, yang pada gilirannya memungkinkan untuk menggunakan lebih banyak proses untuk memecahkan masalah yang lebih besar.

Example - Perkalian matriks padat.

Model Grafik Tugas

Dalam model grafik tugas, paralelisme dinyatakan dengan a task graph. Grafik tugas bisa berupa trivial atau nontrivial. Dalam model ini, korelasi antar tugas digunakan untuk mempromosikan lokalitas atau untuk meminimalkan biaya interaksi. Model ini diterapkan untuk memecahkan masalah di mana jumlah data yang terkait dengan tugas-tugas sangat besar dibandingkan dengan jumlah komputasi yang terkait dengannya. Tugas diberikan untuk membantu meningkatkan biaya perpindahan data di antara tugas-tugas tersebut.

Examples - Pengurutan cepat paralel, faktorisasi matriks renggang, dan algoritme paralel yang diturunkan melalui pendekatan divide-and-conquer.

Di sini, masalah dibagi menjadi tugas atom dan diimplementasikan sebagai grafik. Setiap tugas adalah unit pekerjaan independen yang memiliki ketergantungan pada satu atau lebih tugas sebelumnya. Setelah menyelesaikan tugas, output tugas sebelumnya diteruskan ke tugas dependen. Sebuah tugas dengan tugas anteseden memulai eksekusi hanya ketika seluruh tugas antesedennya selesai. Keluaran akhir grafik diterima setelah tugas dependen terakhir diselesaikan (Tugas 6 pada gambar di atas).

Model Kolam Kerja

Dalam model kumpulan kerja, tugas ditetapkan secara dinamis ke proses untuk menyeimbangkan beban. Oleh karena itu, proses apa pun berpotensi menjalankan tugas apa pun. Model ini digunakan ketika jumlah data yang terkait dengan tugas relatif lebih kecil daripada komputasi yang terkait dengan tugas.

Tidak ada penetapan tugas yang diinginkan ke dalam proses. Penetapan tugas terpusat atau terdesentralisasi. Pointer ke tugas disimpan dalam daftar yang dibagikan secara fisik, dalam antrian prioritas, atau dalam tabel atau pohon hash, atau mereka dapat disimpan dalam struktur data yang didistribusikan secara fisik.

Tugas mungkin tersedia di awal, atau dapat dibuat secara dinamis. Jika tugas dibuat secara dinamis dan penetapan tugas yang terdesentralisasi dilakukan, maka algoritme deteksi penghentian diperlukan agar semua proses benar-benar dapat mendeteksi penyelesaian keseluruhan program dan berhenti mencari tugas lainnya.

Example - Pencarian pohon paralel

Model Master-Budak

Dalam model master-slave, satu atau lebih proses master menghasilkan tugas dan mengalokasikannya ke proses slave. Tugas dapat dialokasikan sebelumnya jika -

  • master dapat memperkirakan volume tugas, atau
  • penugasan acak dapat melakukan pekerjaan keseimbangan beban yang memuaskan, atau
  • budak diberi tugas yang lebih kecil pada waktu yang berbeda.

Model ini umumnya sama-sama cocok untuk shared-address-space atau message-passing paradigms, karena interaksi secara alami ada dua cara.

Dalam beberapa kasus, tugas mungkin perlu diselesaikan secara bertahap, dan tugas di setiap tahap harus diselesaikan sebelum tugas di tahap berikutnya dapat dibuat. Model master-slave dapat digeneralisasikan menjadihierarchical atau multi-level master-slave model di mana master tingkat atas memberikan sebagian besar tugas kepada master tingkat kedua, yang selanjutnya membagi tugas di antara budaknya sendiri dan dapat melakukan sebagian dari tugas itu sendiri.

Tindakan pencegahan dalam menggunakan model master-slave

Perhatian harus diberikan untuk memastikan bahwa master tidak menjadi titik kemacetan. Ini mungkin terjadi jika tugas-tugasnya terlalu kecil atau para pekerjanya relatif cepat.

Tugas-tugas harus dipilih sedemikian rupa sehingga biaya pelaksanaan tugas mendominasi biaya komunikasi dan biaya sinkronisasi.

Interaksi asynchronous dapat membantu interaksi tumpang tindih dan komputasi yang terkait dengan pembuatan pekerjaan oleh master.

Model Pipa

Itu juga dikenal sebagai producer-consumer model. Di sini sekumpulan data diteruskan melalui serangkaian proses, yang masing-masing melakukan beberapa tugas padanya. Di sini, kedatangan data baru menghasilkan eksekusi tugas baru melalui proses dalam antrian. Proses tersebut dapat membentuk antrian dalam bentuk array linier atau multidimensi, pohon, atau grafik umum dengan atau tanpa siklus.

Model ini merupakan rantai produsen dan konsumen. Setiap proses dalam antrian dapat dianggap sebagai konsumen dari urutan item data untuk proses sebelumnya dalam antrian dan sebagai penghasil data untuk proses yang mengikutinya dalam antrian. Antrian tidak harus berupa rantai linier; itu bisa menjadi grafik berarah. Teknik minimisasi interaksi yang paling umum berlaku untuk model ini adalah interaksi yang tumpang tindih dengan komputasi.

Example - Algoritma faktorisasi LU paralel.

Model Hibrida

Model algoritme hibrid diperlukan jika lebih dari satu model mungkin diperlukan untuk memecahkan masalah.

Model hybrid dapat terdiri dari beberapa model yang diterapkan secara hierarki atau beberapa model yang diterapkan secara berurutan ke fase yang berbeda dari algoritme paralel.

Example - Urutan cepat paralel