Pengurangan paralel mengasumsikan bahwa operasi yang sesuai adalah asosiatif. Asumsi ini dilanggar karena penambahan angka floating point. Anda mungkin bertanya mengapa saya peduli tentang ini. Yah, itu membuat hasil yang kurang dapat direproduksi. Dan menjadi lebih buruk ketika anil simulasi digunakan untuk mengoptimalkan (atau menyesuaikan parameter) dibandingkan subrutin yang menghasilkan hasil yang tidak dapat direproduksi.
Apa cara umum untuk mengatasi masalah ini? Apa yang bisa dikatakan tentang strategi berikut?
- Jangan pedulikan hal yang tidak dapat direproduksi.
- Jangan gunakan reduksi paralel dengan angka floating point dan penambahan.
- Buat paket kerja berukuran sesuai dengan cara yang dapat direproduksi, dan lakukan reduksi akhir dengan tangan.
- Gunakan presisi yang lebih tinggi untuk penambahan (tetapi tidak semua kompiler menawarkan tipe floating point presisi yang lebih tinggi).
parallel-computing
reproducibility
Thomas Klimpel
sumber
sumber
Jawaban:
Pengurangan yang diimplementasikan menggunakan
MPI_Allreduce()
direproduksi selama Anda menggunakan jumlah prosesor yang sama, asalkan implementasi mengamati catatan berikut ini muncul di Bagian 5.9.1 dari standar MPI-2.2.Jika Anda perlu menjamin reproduktifitas dengan cara apa pun, Anda dapat mengikuti panduan di paragraf berikut:
Dalam skema yang lebih luas, algoritma yang efisien untuk sebagian besar aplikasi memanfaatkan lokalitas. Karena algoritma ini benar-benar berbeda ketika dijalankan pada sejumlah proses yang berbeda, tidak praktis untuk mereproduksi hasil secara tepat ketika dijalankan pada sejumlah proses yang berbeda. Pengecualian yang mungkin adalah multigrid dengan Jacobi teredam atau polinomial (misalnya Chebyshev), di mana dimungkinkan untuk metode sederhana ini bekerja dengan sangat baik.
Dengan jumlah proses yang sama, seringkali bermanfaat bagi kinerja untuk memproses pesan dalam urutan yang diterima (misalnya menggunakan
MPI_Waitany()
), yang memperkenalkan non-determinisme. Dalam kasus seperti itu, Anda dapat mengimplementasikan dua varian, yang cepat yang menerima dalam urutan apa pun dan yang "men-debug" yang menerima dalam urutan statis. Ini mensyaratkan bahwa semua pustaka yang mendasarinya juga ditulis untuk menawarkan perilaku ini.Untuk debugging dalam beberapa kasus, Anda dapat mengisolasi bagian dari perhitungan yang tidak menawarkan perilaku yang dapat direproduksi ini dan melakukan hal itu secara berlebihan. Tergantung pada bagaimana komponen dirancang, perubahan itu mungkin sejumlah kecil kode atau sangat mengganggu.
sumber
Untuk sebagian besar saya mengirim jawaban Jed. Namun, ada jalan keluar yang berbeda: Mengingat ukuran angka floating point normal, Anda dapat menyimpan setiap angka dalam angka titik tetap bit 4000 atau lebih. Jadi, jika Anda melakukan pengurangan angka floating point yang tertanam, Anda mendapatkan perhitungan yang pasti, tidak peduli asosiatifitasnya. (Maaf, saya tidak punya referensi untuk yang datang dengan ide ini.)
sumber
Anda dapat menerapkan algoritme reduksi yang stabil secara numerik dalam MPI sama seperti yang Anda lakukan secara serial. Mungkin ada hit kinerja, tentu saja. Jika Anda mampu mereplikasi vektor, cukup gunakan MPI_Gather dan lakukan pengurangan serial secara stabil pada root. Dalam beberapa kasus, Anda mungkin menemukan performa yang baik bukan masalah besar.
Solusi lain adalah dengan menggunakan akumulator luas seperti yang dijelaskan di sini . Anda dapat melakukan ini dengan MPI sebagai pengurangan yang ditentukan pengguna, meskipun akan menggunakan bandwidth yang lebih banyak.
Kompromi untuk hal di atas adalah menggunakan penjumlahan terkompensasi. Lihat referensi "penjumlahan Kahan" untuk detailnya. “ Akurasi dan Stabilitas Algoritma Numerik ” Higham adalah sumber yang bagus untuk topik ini.
sumber
Untuk mengatasi masalah ini dalam konteks utas pada sistem memori bersama, saya telah menulis halaman ini yang menjelaskan apa yang kami lakukan. II: http://dealii.org/developer/doxygen/deal.II/group__threads.html #MTWorkStream
sumber
Saya ingin menunjukkan bahwa alih-alih menggunakan aritmatika presisi lebih tinggi untuk penambahan, ada kemungkinan menggunakan penjumlahan terkompensasi (lihat [1]). Ini bisa meningkatkan akurasi penjumlahan tanpa perlu menggunakan tipe data yang lebih besar.
[1] Higham, NJ Akurasi Penjumlahan Floating Point. Jurnal SIAM pada Scientific Computing 14, 783-799 (1993).
sumber