D. Klausa jadwal
Wilayah paralel memiliki setidaknya satu penghalang, pada akhirnya, dan mungkin memiliki hambatan tambahan di dalamnya. Di setiap hambatan, anggota tim lainnya harus menunggu utas terakhir tiba. Untuk meminimalkan waktu tunggu ini, pekerjaan bersama harus didistribusikan sehingga semua utas tiba di pembatas pada waktu yang hampir bersamaan. Jika beberapa pekerjaan bersama tersebut terkandung dalam for
konstruksi, schedule
klausul dapat digunakan untuk tujuan ini.
Ketika ada referensi berulang ke objek yang sama, pilihan jadwal untuk for
konstruksi dapat ditentukan terutama oleh karakteristik sistem memori, seperti keberadaan dan ukuran cache dan apakah waktu akses memori seragam atau nonuniform. Pertimbangan tersebut dapat membuatnya lebih baik untuk memiliki setiap utas secara konsisten merujuk ke serangkaian elemen array yang sama dalam serangkaian perulangan, bahkan jika beberapa utas ditetapkan relatif kurang bekerja dalam beberapa perulangan. Penyiapan ini dapat dilakukan dengan menggunakan static
jadwal dengan batas yang sama untuk semua perulangan. Dalam contoh berikut, nol digunakan sebagai batas bawah dalam perulangan kedua, meskipun k
akan lebih alami jika jadwal tidak penting.
#pragma omp parallel
{
#pragma omp for schedule(static)
for(i=0; i<n; i++)
a[i] = work1(i);
#pragma omp for schedule(static)
for(i=0; i<n; i++)
if(i>=k) a[i] += work2(i);
}
Dalam contoh yang tersisa, diasumsikan bahwa akses memori bukanlah pertimbangan yang dominan. Kecuali dinyatakan lain, diasumsikan bahwa semua utas menerima sumber daya komputasi yang sebanding. Dalam kasus ini, pilihan jadwal untuk for
konstruksi tergantung pada semua pekerjaan bersama yang akan dilakukan antara hambatan sebelumnya terdekat dan penghapus penutup tersirat atau hambatan terdekat yang akan datang, jika ada nowait
klausul. Untuk setiap jenis jadwal, contoh singkat menunjukkan bagaimana jenis jadwal tersebut kemungkinan menjadi pilihan terbaik. Diskusi singkat mengikuti setiap contoh.
Jadwal static
ini juga sesuai untuk kasus paling sederhana, wilayah paralel yang berisi satu for
konstruksi, dengan setiap iterasi membutuhkan jumlah pekerjaan yang sama.
#pragma omp parallel for schedule(static)
for(i=0; i<n; i++) {
invariant_amount_of_work(i);
}
Jadwal static
ditandai oleh properti yang masing-masing utas mendapatkan jumlah iterasi yang kira-kira sama dengan utas lainnya, dan setiap utas dapat secara independen menentukan iterasi yang ditetapkan untuknya. Dengan demikian tidak ada sinkronisasi yang diperlukan untuk mendistribusikan pekerjaan, dan, dengan asumsi bahwa setiap iterasi memerlukan jumlah pekerjaan yang sama, semua utas harus selesai pada waktu yang hampir bersamaan.
Untuk tim utas p , biarkan langit-langit (n/p) menjadi bilangan bulat q, yang memenuhi n = p*q - r dengan 0 <= r < p. Salah satu implementasi static
jadwal untuk contoh ini akan menetapkan perulangan q ke utas p-1 pertama, dan iterasi q-r ke utas terakhir. Implementasi lain yang dapat diterima akan menetapkan iterasi q ke utas p-r pertama, dan iterasi q-1 ke utas r yang tersisa. Contoh ini menggambarkan mengapa program tidak boleh mengandalkan detail implementasi tertentu.
dynamic
Jadwal sesuai untuk kasus for
konstruksi dengan iterasi yang memerlukan berbagai, atau bahkan tidak dapat diprediksi, jumlah pekerjaan.
#pragma omp parallel for schedule(dynamic)
for(i=0; i<n; i++) {
unpredictable_amount_of_work(i);
}
Jadwal dynamic
ditandai oleh properti yang tidak ada utas yang menunggu di penghubung lebih lama daripada yang dibutuhkan utas lain untuk menjalankan iterasi terakhirnya. Persyaratan ini berarti perulangan harus ditetapkan satu per satu ke utas saat tersedia, dengan sinkronisasi untuk setiap penugasan. Overhead sinkronisasi dapat dikurangi dengan menentukan ukuran gugus minimum k lebih besar dari 1, sehingga utas ditetapkan k pada satu waktu sampai kurang dari k tetap. Ini menjamin bahwa tidak ada utas yang menunggu di penghubung lebih lama daripada yang dibutuhkan utas lain untuk menjalankan potongan akhir dari (paling banyak) k iterasi.
Jadwal dynamic
dapat berguna jika utas menerima berbagai sumber daya komputasi, yang memiliki efek yang jauh sama dengan berbagai jumlah pekerjaan untuk setiap perulangan. Demikian pula, jadwal dinamis juga dapat berguna jika utas tiba di for
konstruksi pada waktu yang bervariasi, meskipun dalam beberapa kasus ini jadwal mungkin lebih disukai guided
.
guided
Jadwal sesuai untuk kasus di mana utas dapat tiba pada waktu yang for
bervariasi pada konstruksi dengan setiap iterasi yang memerlukan jumlah pekerjaan yang sama. Situasi ini dapat terjadi jika, misalnya, for
konstruksi didahului oleh satu atau beberapa bagian atau for
konstruksi dengan nowait
klausa.
#pragma omp parallel
{
#pragma omp sections nowait
{
// ...
}
#pragma omp for schedule(guided)
for(i=0; i<n; i++) {
invariant_amount_of_work(i);
}
}
Seperti dynamic
, guided
jadwal menjamin bahwa tidak ada utas yang menunggu di penghubung lebih lama daripada yang dibutuhkan utas lain untuk menjalankan iterasi akhir, atau iterasi k akhir jika ukuran gugus k ditentukan. Di antara jadwal tersebut guided
, jadwal ditandai oleh properti yang memerlukan sinkronisasi terkecil. Untuk ukuran gugus k, implementasi umum akan menetapkan perulangan q = ceiling(n/p) ke utas pertama yang tersedia, mengatur n ke yang lebih besar dari n-q dan p*k, dan mengulangi hingga semua iterasi ditetapkan.
Ketika pilihan jadwal optimal tidak sejelas untuk contoh ini, runtime
jadwalnya nyaman untuk bereksperimen dengan jadwal dan ukuran gugus yang berbeda tanpa harus memodifikasi dan mengkompilasi ulang program. Ini juga dapat berguna ketika jadwal optimal tergantung (dengan beberapa cara yang dapat diprediksi) pada data input tempat program diterapkan.
Untuk melihat contoh trade-off antara jadwal yang berbeda, pertimbangkan untuk berbagi 1000 iterasi di antara delapan utas. Misalkan ada jumlah pekerjaan yang invarian di setiap iterasi, dan gunakan itu sebagai unit waktu.
Jika semua utas dimulai pada saat yang sama, static
jadwal akan menyebabkan konstruksi dijalankan dalam 125 unit, tanpa sinkronisasi. Tapi misalkan satu utas adalah 100 unit terlambat tiba. Kemudian tujuh utas yang tersisa menunggu 100 unit di penghadang, dan waktu eksekusi untuk seluruh konstruksi meningkat menjadi 225.
Karena jadwal dynamic
dan guided
memastikan bahwa tidak ada utas yang menunggu lebih dari satu unit di penghadang, utas yang tertunda menyebabkan waktu eksekusi mereka agar konstruksi hanya meningkat menjadi 138 unit, mungkin ditingkatkan oleh penundaan dari sinkronisasi. Jika penundaan tersebut tidak dapat diabaikan, menjadi penting bahwa jumlah sinkronisasi adalah 1000 untuk dynamic
tetapi hanya 41 untuk guided
, dengan asumsi ukuran gugus default satu. Dengan ukuran potongan 25, dynamic
dan guided
keduanya selesai dalam 150 unit, ditambah penundaan dari sinkronisasi yang diperlukan, yang sekarang masing-masing berjumlah 40 dan 20.