Pustaka paralel bersama-memori berbasis tugas di Scientific Computing

Dalam beberapa tahun terakhir, beberapa proyek perpustakaan / perangkat lunak telah muncul yang menawarkan beberapa bentuk atau paralelisme memori bersama untuk keperluan umum yang didorong oleh data.

Gagasan utamanya adalah bahwa alih-alih menulis kode yang diulir secara eksplisit, pemrogram mengimplementasikan algoritme mereka sebagai tugas yang saling tergantung yang kemudian dijadwalkan secara dinamis oleh middleware tujuan umum pada mesin memori bersama.

Contoh perpustakaan tersebut adalah:

• QUARK : Awalnya dirancang untuk perpustakaan aljabar linier paralel MAGMA , tampaknya telah digunakan untuk Metode Multipole Cepat paralel juga.

• Cilk : Awalnya proyek berbasis MIT, sekarang didukung oleh Intel, diimplementasikan sebagai ekstensi bahasa / kompiler ke C, digunakan dalam perangkat lunak catur komputer Cilkchess dan secara eksperimental dalam FFTW .

• Superscalar SMP : Dikembangkan di Barcelona Supercomputing Center, mirip dengan Cilk dalam banyak hal, berdasarkan #pragmaekstensi.

• StarPU : "Codelet" berbasis perpustakaan serupa yang dapat dikompilasi dan dijadwalkan pada beberapa arsitektur yang berbeda, termasuk GPU.

• Tugas OpenMP: Pada versi 3.0, OpenMP memperkenalkan "tugas" yang dapat dijadwalkan secara tidak sinkron (lihat Bagian 2.7 dari spesifikasi).

• Blok Bangunan Threading Intel : Menggunakan kelas C ++ untuk membuat dan meluncurkan tugas asinkron, lihat Bagian 11 dari Tutorial.

• OpenCL : Mendukung paralelisme berbasis tugas pada multi-core.

Meskipun ada banyak literatur yang menggambarkan kerja dalam dari perpustakaan / ekstensi bahasa ini dan aplikasinya untuk masalah-masalah spesifik, saya hanya menemukan sedikit sekali contoh yang digunakan dalam praktiknya dalam aplikasi komputasi ilmiah.

Jadi, inilah pertanyaannya: Apakah ada yang tahu kode komputasi ilmiah yang menggunakan pustaka / ekstensi bahasa ini, atau yang serupa, untuk paralelisme memori bersama?

deal.II menggunakan Blok Bangunan Threading di seluruh perpustakaan dan pada umumnya kami cukup senang dengan itu. Kami telah melihat beberapa alternatif, khususnya OpenMP karena semua orang tampaknya menggunakan itu untuk kode yang lebih sederhana, tetapi ternyata kurang. Secara khusus, OpenMP memiliki kelemahan besar bahwa model tugasnya tidak memungkinkan Anda untuk menangani tugas yang Anda mulai, dan akibatnya sulit untuk mengakses keadaan tugas (misalnya menunggu sampai selesai) atau mengembalikan nilai dari fungsi yang Anda jalankan pada tugas yang terpisah. OpenMP terutama baik untuk memparalelkan loop paling dalam tetapi Anda mendapatkan efisiensi paralel dengan memaralelkan loop terluar , kompleks, dan OpenMP bukan alat untuk itu sementara TBB cukup baik untuk itu.

Menurut pendapat saya, sistem ini relatif tidak berhasil terutama karena alasan berikut.

• Perspektif naif bahwa komputasi paralel adalah tentang memparalelkan perhitungan (misalnya jepit) lebih dari mengekspos lokalitas memori dan menghilangkan titik sinkronisasi. Meskipun beberapa masalah, seperti algoritma matriks padat, masih terbatas pada FP, yang hanya terjadi setelah pertimbangan cermat dari subsistem memori dan sebagian besar kernel komputasi (terutama di dunia PDE) lebih sensitif terhadap memori. Antrian kerja cenderung memperdagangkan lokalitas memori untuk keseimbangan jepit yang lebih naif dan lebih banyak operasi memori atom (karena sinkronisasi melalui antrian).
• Mengandalkan dekomposisi berlebihan untuk keseimbangan beban dinamis dengan mengorbankan skalabilitas yang kuat. Tugas umumnya memiliki ketergantungan data yang tumpang tindih (nilai hantu). Ketika ukuran interior menyusut, rasio hantu / interior meningkat. Bahkan ketika ini tidak menyiratkan pekerjaan yang berlebihan, itu menyiratkan peningkatan gerakan memori. Pengurangan yang signifikan dalam persyaratan bandwidth memori dapat dimiliki dengan pendekatan seperti prefetch kooperatif di mana beberapa utas berbagi cache L1 atau L2 dengan prefetching perangkat lunak untuk tetangga mereka (yang secara implisit membuat grup utas sekitar koheren). Ini persis kebalikan dari dekomposisi berlebihan.
• Performa yang tidak dapat diprediksi, sebagian besar disebabkan oleh masalah terkait memori di atas.
• Kurangnya komponen yang ramah perpustakaan. Ini hampir dapat diringkas sebagai tidak memiliki analog MPI_Commyang memungkinkan pustaka yang berbeda untuk melakukan operasi yang kaya tanpa bertabrakan, serta untuk melewatkan konteks antara pustaka dan memulihkan atribut yang diperlukan. Abstraksi yang disediakan oleh "komunikator" penting untuk komposisi perpustakaan terlepas dari apakah memori bersama atau didistribusikan digunakan.