Di bawah ini saya mencoba membuat sketsa kode yang diparalelkan menggunakan tugas OpenMP.

Dalam fungsi utama, lingkungan paralel dimulai dan segera setelah melakukannya, kode dibungkus ke dalam bagian #pragma omp master. Setelah menghitung beban kerja yang diharapkan dan tergantung pada apakah beban kerja ini di bawah ambang batas yang diberikan, hal-hal yang harus dilakukan akan diteruskan ke fungsi serial atau ke fungsi yang akan membagi beban kerja secara rekursif dan menginisialisasi tugas terpisah. Hasil dari setiap #pragma omp task tunggal kemudian digabungkan setelah direktif #pragma omp taskwait.

int main() {
    #pragma omp parallel
    {
        #pragma omp master
        {
            //do some serial stuff
            
            //estimate if parallelisation is worth it.
            const int workload = estimateWorkload();
            if (workload < someBound) {
                serialFunction();
            }
            else {
                parallelFunction(workload);
            }
        }
    }
}

int parallelFunction(int workload) {
    if (workload < someBound) {
        return serialFunction();
    }
    int result1, result2;
    #pragma omp task shared(result1)
    {
        result1 = parallelFunction(workload/2);
    }    
    #pragma omp task shared(result2)
    {
        result2 = parallelFunction(workload/2);
    }
    #pragma omp taskwait
   return result1 < result2;
}

Bagaimana cara mengukur waktu komputasi aktual dari setiap utas dalam pengaturan seperti itu?

Jika saya mengukur waktu CPU dan memiliki k utas aktif, maka saya akan mendapatkan k*wallTime, yang masuk akal karena utas diinisialisasi oleh arahan #pragma omp parallel terkemuka dan tetap aktif sepanjang waktu. Namun ini tidak memberi saya informasi tentang berapa banyak waktu yang dihabiskan utas untuk benar-benar berfungsi, yang membuat kode sulit untuk dianalisis.

1
acaymo 6 Juli 2020, 14:44

1 menjawab

Jawaban Terbaik

Q : Bagaimana cara mengukur waktu komputasi sebenarnya dari setiap utas dalam setelan seperti itu?

MOCK-UP sepele KODE untuk pembuatan profil waktu eksekusi kode semi-manual yang sederhana:

enter image description here

Tidak perlu dikatakan, bahwa untuk platform eksekusi "berisik", pilihan CLOCK_MONOTONIC menghemat pembaruan waktu drifting, namun tidak "menyimpan" status tunggu di luar CPU, karena jika berat) "latar belakang"-(mengganggu)-proses yang dijadwalkan oleh O/S.

Namun, untuk fase pembuatan prototipe, ini jauh lebih mudah daripada memasang semua penanganan callbacks'
{ ompt_callback_task_create_t, ompt_callback_task_schedule_t, ompt_callback_task_dependence_t, ompt_callback_dispatch_t, ompt_callback_sync_region_t, ..., ompt_callback_thread_begin_t, ompt_callback_thread_end_t, ... } "omp-native" .


BONUS EFEK SAMPING :

Kode sepele memungkinkan, jika pelaporan dan pasca-pemrosesan durasi masing-masing eksekusi kode bersarang yang direkam, untuk "membingkai" biaya tersembunyi dari tanda tangan panggilan terkait dan overhead terkait bersarang rekursi.

revisi, overhead-strict Hukum Amdahl kemudian berhenti berbohong kepada Anda dan mulai menunjukkan kepada Anda dengan lebih tepat, ketika kode ini mulai hilang pada hal yang sangat terkait dengan overhead ( ditambah karena potensi atomicity-of-work-unit (s) ) terutama-[SERIAL]-biaya tambahan untuk setiap Benar- yang diharapkan [PARALLEL]-section(s) speedup ( diharapkan dari memanfaatkan lebih banyak (itu dan hanya yang gratis) sumber daya).

Itu selalu menjadi bagian tersulit dari Perang ( masih harus diperjuangkan ... ).


EFFICIENCY of SCHEDULING & OCCUPIED RESOURCES' of a CALL to 2-ary task-SCHEDULED fun() with hidden 1-ary RECURSION:

CALL
    42----*--------------------------------------------------------------------------------------*
     :    |                                                                                      |
     :    |                                                                                     21----*---------------------------------------*
     :    |                                                                                      :    |                                       |
     :    |                                                                                      :    |                                      10----*----------------*
     :    |                                                                                      :    |                                       :    |                |
     :    |                                                                                      :    |                                       :    |                5----*----*
     :    |                                                                                      :    |                                       :    |                :    |    |
     :    |                                                                                      :    |                                       :    |                :    |    2<
     :    |                                                                                      :    |                                       :    |                :    2<  /
     :    |                                                                                      :    |                                       :    5----*----*      5___/___/................ #taskwait  2
     :    |                                                                                      :    |                                       :    :    |    |     /
     :    |                                                                                      :    |                                       :    :    |    2<   /
     :    |                                                                                      :    |                                       :    :    2<  /    /
     :    |                                                                                      :    |                                       :    5___/___/    /
     :    |                                                                                      :    |                                      10___/____________/............................. #taskwait  5
     :    |                                                                                      :   10----*----------------*                /
     :    |                                                                                      :    :    |                |               /
     :    |                                                                                      :    :    |                5----*----*    /
     :    |                                                                                      :    :    |                :    |    |   /
     :    |                                                                                      :    :    |                :    |    2< /
     :    |                                                                                      :    :    |                :    2<  /  /
     :    |                                                                                      :    :    5----*----*      5___/___/  /
     :    |                                                                                      :    :    :    |    |     /          /     
     :    |                                                                                      :    :    :    |    2<   /          /
     :    |                                                                                      :    :    :    2<  /    /          /
     :    |                                                                                      :    :    5___/___/    /          /
     :    |                                                                                      :   10___/____________/__________/.......................................................... #taskwait 10
     :    |                                                                                     21___/
     :   21----*---------------------------------------*                                        /
     :    :    |                                       |                                       /
     :    :    |                                      10----*----------------*                /
     :    :    |                                       :    |                |               /
     :    :    |                                       :    |                5----*----*    /
     :    :    |                                       :    |                :    |    |   /
     :    :    |                                       :    |                :    |    2< /
     :    :    |                                       :    |                :    2<  /  /
     :    :    |                                       :    5----*----*      5___/___/  /
     :    :    |                                       :    :    |    |     /          /
     :    :    |                                       :    :    |    2<   /          /
     :    :    |                                       :    :    2<  /    /          /
     :    :    |                                       :    5___/___/    /          /
     :    :    |                                      10___/____________/          /
     :    :   10----*----------------*                /                           /
     :    :    :    |                |               /                           /
     :    :    :    |                5----*----*    /                           /
     :    :    :    |                :    |    |   /                           /
     :    :    :    |                :    |    2< /                           /
     :    :    :    |                :    2<  /  /                           /
     :    :    :    5----*----*      5___/___/  /                           /
     :    :    :    :    |    |     /          /                           /
     :    :    :    :    |    2<   /          /                           /
     :    :    :    :    2<  /    /          /                           /
     :    :    :    5___/___/    /          /                           /
     :    :   10___/____________/__________/                           /
     :   21___/_______________________________________________________/...................................................................................................................... #taskwait 21
    42___/
RET_/

EFFICIENCY

Of SCHEDULING & OCCUPIED RESOURCES' of a CALL to 2-ary task-SCHEDULED fun() with hidden 1-ary RECURSION matters more and more for any growing scale of the workload becoming soon workload < someBound * 2 ^ W only at a cost of an awfully high W ( which causes W * k-ary-many times re-{-acquired, -allocated, -released} Wasted all k-ary-times requested #pragma omp task shared(...)-handling-related resources, throughout the progression of the whole pure-[SERIAL]-by-definition recursion dive-&-resurfacing back ).

Sangat mudah untuk melihat berapa banyak sumber daya yang akan menunggu ( karena formulasi RECURSION 1-ary genap ), sampai setiap penyelaman ke tingkat terdalam gelembung rekursi kembali ke tingkat atas #pragma omp taskwait.

Biaya pengalokasian ulang sumber daya baru dan baru untuk setiap tingkat penyelaman rekursi paling sering akan membunuh Anda pada Hukum Amdahl yang ketat (dari segi kinerja), jika tidak masuk ke thrashing atau luapan terkait konfigurasi sistem, karena menghancurkan yang sebenarnya -sistem sumber daya fisik sebelumnya, untuk kedalaman rekursi yang cukup besar.

Ini adalah biaya yang tidak perlu Anda bayarkan, jika tidak menggunakan rumusan masalah rekursif-rekursif-namun-mahal-dalam-(idle/terbuang)-sumber daya, bahkan dengan kasus 1-ary yang paling ringan.

Lihat berapa banyak :-dilambangkan "waiting-lines" yang ada secara paralel, selain seberapa sedikit |-dilambangkan "computing-lines" di salah satu fase topologi, yang membuang/memblokir, namun harus dibiarkan menganggur, semua sumber daya terkait tugas (memori & ruang tumpukan hanya yang lebih terlihat yang dari segi kinerja sangat mahal untuk diperoleh (untuk membiarkan sebagian besar waktu pemrosesan menganggur menunggu) atau cenderung macet karena meluap jika berlangganan berlebihan di luar kapasitas konfigurasi sistem nyata).

Perang adalah milikmu! Terus Berjalan ...


Penafian Kepatuhan Situs :
------------------------------------- -----------------------------------------
Sesuai Kebijakan StackOverflow, kode mock-up lengkap diposting di sini, untuk kasus apa pun platform Godbolt.org mungkin menjadi tidak dapat diakses, jika tidak, silakan pilih dan/atau gunakan alat Penjelajah Kompilator. di luar urutan karakter dimasukkan ke dalam kode sumber mock-up di sana

Pilihan & kesenangan dari menjalankannya selalu milik Anda :o)

#include <time.h>

int estimateWorkload() {
    return 42; // _________________________________________________________ mock-up "workload"
}

int serial_a_bit_less_naive_factorial( int n ){
     return ( n < 3 ) ? n : n * serial_a_bit_less_naive_factorial( n - 1 );
}

int serialFunction() {
    return serial_a_bit_less_naive_factorial( 76 );
}

int parallelFunction( int workload, const int someBound ) { // __ pass both control parameters
    
    struct timespec T0, T1;
    int retFlag,
        retValue,
        result1,
        result2;
    
    retFlag = clock_gettime( CLOCK_MONOTONIC, &T0 ); // \/\/\/\/\/\/\/\/\/\ SECTION.begin

    if ( workload < someBound ) {
        retValue = serialFunction();
    }
    else { // -- [SEQ]----------------------------------------------------

        #pragma omp task shared( result1 ) // -- [PAR]|||||||||||||||||||| with (1-ary recursions)
        {
            result1 = parallelFunction( (int) workload / 2, someBound ); // (int) fused DIV
        }
        
        #pragma omp task shared( result2 ) // -- [PAR]|||||||||||||||||||| with (1-ary recursions)
        {
            result2 = parallelFunction( (int) workload / 2, someBound ); // (int) fused DIV
        }
        #pragma omp taskwait
    
        retValue = result1 < result2;
    }
    
    retFlag = clock_gettime( CLOCK_MONOTONIC, &T1 ); // \/\/\/\/\/\/\/\/\/\ SECTION.end

    // ____________________________________________________________________ MAY ADD ACCUMULATION (1-ary recursions)
    // ...
    // ____________________________________________________________________ MAY ADD ACCUMULATION (1-ary recursions)
    return retValue;
}


int main() {
    
    const int someBound = 3; // _______________________________________ a control parameter A

    #pragma omp parallel
    {
        #pragma omp master
        {
            // -- [SEQ]---------------------------------------- do some serial stuff
            
            // ------------------------------estimate if parallelisation is worth it
            const int workload = estimateWorkload();

            if ( workload < someBound ) {
                serialFunction();
            }
            else {
                parallelFunction( workload, someBound ); // -- [PAR]||||||| with (1-ary recursions)
            }
        }
    }
}
1
user3666197 6 Juli 2020, 16:58