Bagaimana perbandingan biaya operasi mpi_allgather dibandingkan dengan operasi pengumpulan / pencar?

Saya sedang mengerjakan masalah yang dapat diparalelkan dengan menggunakan satu operasi mpi_allgather atau satu mpi_scatter dan satu operasi mpi_gather. Operasi-operasi ini dipanggil dalam loop sementara, sehingga mereka dapat dipanggil berkali-kali.

Dalam implementasi dengan skema MPI_allgather, saya mengumpulkan vektor terdistribusi ke semua proses untuk pemecahan matriks duplikat. Dalam implementasi lain, saya mengumpulkan vektor terdistribusi ke prosesor tunggal (simpul akar), menyelesaikan sistem linear pada prosesor ini, dan kemudian menyebarkan vektor solusi kembali ke semua proses.

Saya ingin tahu apakah biaya operasi allgather secara signifikan lebih dari gabungan operasi pengumpulan dan pengumpulan. Apakah panjang pesan memainkan peran penting dalam kompleksitasnya? Apakah ini bervariasi antara implementasi mpi?

Edit:

Pertama, jawaban yang tepat tergantung pada: (1) penggunaan, yaitu argumen input fungsi, (2) kualitas dan detail implementasi MPI, dan (3) perangkat keras yang Anda gunakan. Seringkali, (2) dan (3) terkait, seperti ketika vendor perangkat keras mengoptimalkan MPI untuk jaringan mereka.

Secara umum, menggabungkan kolektif MPI lebih baik untuk pesan yang lebih kecil, karena biaya awal dapat nontrivial dan sinkronisasi yang disyaratkan oleh memblokir kolektif harus diminimalkan jika ada variasi dalam menghitung waktu antara panggilan. Untuk pesan yang lebih besar, tujuannya adalah meminimalkan jumlah data yang dikirim.

Sebagai contoh, secara teori, MPI_Reduce_scatter_blockharus lebih baik daripada MPI_Reducediikuti oleh MPI_Scatter, meskipun yang pertama sering diterapkan dalam hal yang terakhir, sehingga tidak ada keuntungan nyata. Ada korelasi antara kualitas implementasi dan frekuensi penggunaan di sebagian besar implementasi MPI, dan vendor jelas mengoptimalkan fungsi-fungsi yang diperlukan oleh kontrak mesin ini.

Di sisi lain, jika seseorang menggunakan Blue Gene, melakukan MPI_Reduce_scatter_blockpenggunaan MPI_Allreduce, yang melakukan lebih banyak komunikasi MPI_Reducedan MPI_Scattergabungan, sebenarnya sedikit lebih cepat. Ini adalah sesuatu yang baru-baru ini saya temukan dan merupakan pelanggaran yang menarik dari prinsip konsistensi diri kinerja dalam MPI (prinsip ini dijelaskan secara lebih rinci dalam "Pedoman Kinerja MPI yang Konsisten Sendiri" ).

Dalam kasus spesifik pencar + kumpulkan versus allgather, pertimbangkan bahwa pada yang pertama, semua data harus pergi ke dan dari satu proses tunggal, yang membuatnya menjadi hambatan, sedangkan pada allgather, data dapat mengalir masuk dan keluar dari semua peringkat segera , karena semua peringkat memiliki beberapa data untuk dikirim ke semua peringkat lainnya. Namun, mengirim data dari semua node sekaligus tidak selalu merupakan ide yang baik pada beberapa jaringan.

Akhirnya, cara terbaik untuk menjawab pertanyaan ini adalah dengan melakukan yang berikut dalam kode Anda dan menjawab pertanyaan dengan eksperimen.

#ifdef TWO_MPI_CALLS_ARE_BETTER_THAN_ONE
  MPI_Scatter(..)
  MPI_Gather(..)
#else
  MPI_Allgather(..)
#endif

Opsi yang lebih baik lagi adalah membuat kode Anda mengukurnya secara eksperimental selama dua iterasi pertama, kemudian gunakan mana yang lebih cepat untuk iterasi yang tersisa:

const int use_allgather = 1;
const int use_scatter_then_gather = 2;

int algorithm = 0;
double t0 = 0.0, t1 = 0.0, dt1 = 0.0, dt2 = 0.0;

while (..)
{
    if ( (iteration==0 && algorithm==0) || algorithm==use_scatter_then_gather )
    {
        t0 = MPI_Wtime();
        MPI_Scatter(..);
        MPI_Gather(..);
        t1 = MPI_Wtime();
        dt1 = t1-t0;
    } 
    else if ( (iteration==1 && algorithm==0) || algorithm==use_allgather)
    {
        t0 = MPI_Wtime();
        MPI_Allgather(..);
        t1 = MPI_Wtime();
        dt2 = t1-t0;
    }

    if (iteration==1)
    {
       dt2<dt1 ? algorithm=use_allgather : algorithm=use_scatter_then_gather;
    }
}

Jeff benar tentang satu-satunya cara untuk memastikan adalah dengan mengukur - kita adalah ilmuwan, dan ini adalah pertanyaan empiris - dan memberikan saran yang sangat baik tentang bagaimana menerapkan pengukuran tersebut. Biarkan saya sekarang menawarkan pandangan yang bertentangan (atau, mungkin, saling melengkapi).

Ada perbedaan yang harus dibuat antara menulis kode untuk digunakan secara luas, dan menyetelnya ke tujuan tertentu. Secara umum kami melakukan yang pertama - membangun kode kami sehingga a) kami dapat menggunakannya pada berbagai platform, dan b) kode dapat dipelihara dan dapat diperpanjang untuk tahun-tahun mendatang. Tapi kadang-kadang kita melakukan yang lain - kita punya alokasi satu tahun pada beberapa mesin besar, dan kita meningkatkan beberapa simulasi yang diperlukan dan kita membutuhkan dasar kinerja tertentu untuk mendapatkan apa yang perlu kita lakukan selama waktu alokasi yang diberikan.

Ketika kita sedang menulis kode, membuatnya dapat digunakan secara luas dan dipelihara jauh lebih penting daripada mencukur beberapa persen dari runtime pada mesin tertentu. Dalam hal ini, hal yang benar untuk dilakukan adalah hampir selalu menggunakan rutinitas yang paling menggambarkan apa yang ingin Anda lakukan - ini biasanya merupakan panggilan yang paling spesifik yang dapat Anda lakukan yang melakukan apa yang Anda inginkan. Misalnya, jika allgather atau allgatherv langsung melakukan apa yang Anda inginkan, Anda harus menggunakannya daripada menggulirkan sendiri dari operasi scatter / gatter. Alasannya adalah:

• Kode sekarang lebih jelas mewakili apa yang Anda coba lakukan, membuatnya lebih mudah dimengerti oleh orang berikutnya yang datang ke kode Anda tahun berikutnya tanpa tahu apa yang seharusnya dilakukan oleh kode tersebut (orang itu bisa jadi Anda);
• Optimalisasi tersedia di tingkat MPI untuk kasus yang lebih spesifik ini yang tidak ada dalam kasus yang lebih umum, sehingga perpustakaan MPI Anda dapat membantu Anda; dan
• Mencoba menggulung sendiri kemungkinan akan menjadi bumerang; bahkan jika kinerjanya lebih baik pada mesin X dengan implementasi MPI Y.ZZ, itu mungkin berkinerja jauh lebih buruk ketika Anda pindah ke komputer lain, atau memutakhirkan implementasi MPI Anda.

Dalam kasus yang cukup umum ini, jika Anda mengetahui bahwa beberapa kolektif MPI bekerja lambat secara tidak wajar pada mesin Anda, hal terbaik yang harus dilakukan adalah mengajukan laporan bug dengan vendor mpi; Anda tidak ingin menyulitkan perangkat lunak Anda sendiri yang berusaha mencari-cari dalam kode aplikasi apa yang harus diperbaiki di tingkat perpustakaan MPI.

Namun demikian . Jika Anda berada dalam mode "tuning" - Anda memiliki kode yang berfungsi, Anda harus meningkatkan skala yang sangat besar dalam waktu singkat (mis., Alokasi selama setahun), dan Anda telah membuat profil kode Anda dan menemukan bahwa bagian tertentu dari kode Anda adalah hambatan, maka masuk akal untuk mulai melakukan penyetelan yang sangat spesifik ini. Mudah-mudahan itu tidak akan menjadi bagian jangka panjang dari kode Anda - idealnya perubahan ini akan tetap di beberapa cabang repositori khusus proyek Anda - tetapi Anda mungkin perlu melakukannya. Dalam hal itu, pengkodean dua pendekatan berbeda dibedakan dengan arahan preprosesor, atau pendekatan "autotuning" untuk pola komunikasi tertentu - dapat membuat banyak akal.

Jadi saya tidak setuju dengan Jeff, saya hanya ingin menambahkan beberapa konteks tentang kapan Anda harus cukup peduli dengan pertanyaan kinerja relatif seperti itu untuk memodifikasi kode Anda untuk menghadapinya.