Algoritma Paralel

Pustaka Pola Paralel (PPL) menyediakan algoritma yang secara bersamaan melakukan pekerjaan pada pengumpulan data. Algoritma ini menyerupai yang disediakan oleh Pustaka Standar C++.

Algoritma paralel terdiri dari fungsionalitas yang ada di Runtime Konkurensi. Misalnya, konkurensi::p arallel_for algoritma menggunakan objek konkurensi::structured_task_group untuk melakukan iterasi perulangan paralel. Partisi parallel_for algoritma bekerja dengan cara yang optimal mengingat jumlah sumber daya komputasi yang tersedia.

Bagian

• Algoritma parallel_for

• Algoritma parallel_for_each

• Algoritma parallel_invoke

• Algoritma parallel_transform dan parallel_reduce

  • Algoritma parallel_transform

  • Algoritma parallel_reduce

  • Contoh: Melakukan Peta dan Mengurangi Secara Paralel

• Pekerjaan Pemartisian

• Pengurutan Paralel

  • Memilih Algoritma Pengurutan

Algoritma parallel_for

Algoritma konkurensi::p arallel_for berulang kali melakukan tugas yang sama secara paralel. Masing-masing tugas ini diparameterkan oleh nilai iterasi. Algoritma ini berguna ketika Anda memiliki isi perulangan yang tidak berbagi sumber daya di antara iterasi perulangan tersebut.

Algoritma parallel_for mempartisi tugas dengan cara optimal untuk eksekusi paralel. Ini menggunakan algoritma pencurian kerja dan pencurian rentang untuk menyeimbangkan partisi ini ketika beban kerja tidak seimbang. Ketika satu iterasi perulangan memblokir secara kooperatif, runtime mendistribusikan ulang rentang iterasi yang ditetapkan ke utas saat ini ke utas atau prosesor lain. Demikian pula, ketika utas menyelesaikan berbagai iterasi, runtime mendistribusikan ulang pekerjaan dari utas lain ke utas tersebut. parallel_for Algoritma ini juga mendukung paralelisme berlapis. Ketika satu perulangan paralel berisi perulangan paralel lainnya, runtime mengoordinasikan pemrosesan sumber daya antara badan perulangan dengan cara yang efisien untuk eksekusi paralel.

parallel_for Algoritma memiliki beberapa versi yang kelebihan beban. Versi pertama mengambil nilai awal, nilai akhir, dan fungsi kerja (ekspresi lambda, objek fungsi, atau penunjuk fungsi). Versi kedua mengambil nilai awal, nilai akhir, nilai yang akan dilangkahi, dan fungsi kerja. Versi pertama fungsi ini menggunakan 1 sebagai nilai langkah. Versi yang tersisa mengambil objek partisi, yang memungkinkan Anda menentukan bagaimana parallel_for harus mempartisi rentang di antara utas. Partisi dijelaskan secara lebih rinci di bagian Pekerjaan Partisi dalam dokumen ini.

Anda dapat mengonversi banyak for perulangan untuk menggunakan parallel_for. Namun, parallel_for algoritma berbeda dari for pernyataan dengan cara berikut:

• parallel_for Algoritma parallel_for tidak menjalankan tugas dalam urutan yang telah ditentukan sebelumnya.

• parallel_for Algoritma tidak mendukung kondisi penghentian sewenang-wenang. parallel_for Algoritma berhenti ketika nilai variabel iterasi saat ini adalah kurang dari last.

• Parameter _Index_type jenis harus merupakan jenis integral. Jenis integral ini dapat ditandatangani atau tidak ditandatangani.

• Iterasi perulangan harus diteruskan. parallel_for Algoritma melemparkan pengecualian jenis std::invalid_argument jika _Step parameter kurang dari 1.

• Mekanisme penanganan pengecualian untuk parallel_for algoritma berbeda dari perulangan for . Jika beberapa pengecualian terjadi secara bersamaan dalam isi perulangan paralel, runtime hanya menyebarkan salah satu pengecualian ke utas yang disebut parallel_for. Selain itu, ketika satu iterasi perulangan melemparkan pengecualian, runtime tidak segera menghentikan perulangan keseluruhan. Sebaliknya, perulangan ditempatkan dalam status dibatalkan dan runtime membuang tugas apa pun yang belum dimulai. Untuk informasi selengkapnya tentang penanganan pengecualian dan algoritma paralel, lihat Penanganan Pengecualian.

parallel_for Meskipun algoritma tidak mendukung kondisi penghentian sewenang-wenang, Anda dapat menggunakan pembatalan untuk menghentikan semua tugas. Untuk informasi selengkapnya tentang pembatalan, lihat Pembatalan di PPL.

Catatan

Biaya penjadwalan yang dihasilkan dari penyeimbangan beban dan dukungan untuk fitur seperti pembatalan mungkin tidak mengatasi manfaat mengeksekusi bodi perulangan secara paralel, terutama ketika bodi perulangan relatif kecil. Anda dapat meminimalkan overhead ini dengan menggunakan partisi dalam perulangan paralel Anda. Untuk informasi selengkapnya, lihat Pekerjaan Partisi nanti dalam dokumen ini.

Contoh

Contoh berikut menunjukkan struktur parallel_for dasar algoritma. Contoh ini mencetak ke konsol setiap nilai dalam rentang [1, 5] secara paralel.

// parallel-for-structure.cpp
// compile with: /EHsc
#include <ppl.h>
#include <array>
#include <sstream>
#include <iostream>

using namespace concurrency;
using namespace std;

int wmain()
{
   // Print each value from 1 to 5 in parallel.
   parallel_for(1, 6, [](int value) {
      wstringstream ss;
      ss << value << L' ';
      wcout << ss.str();
   });
}

Contoh ini menghasilkan contoh output berikut:

1 2 4 3 5

parallel_for Karena algoritma bertindak pada setiap item secara paralel, urutan nilai dicetak ke konsol akan bervariasi.

Untuk contoh lengkap yang menggunakan parallel_for algoritma, lihat Cara: Menulis perulangan parallel_for.

[Atas]

Algoritma parallel_for_each

Algoritma konkurensi::p arallel_for_each melakukan tugas pada kontainer iteratif, seperti yang disediakan oleh Pustaka Standar C++, secara paralel. Ini menggunakan logika partisi yang sama dengan yang parallel_for digunakan algoritma.

parallel_for_each Algoritma menyerupai algoritma C++ Standard Library std::for_each, kecuali bahwa parallel_for_each algoritma menjalankan tugas secara bersamaan. Seperti algoritma paralel lainnya, parallel_for_each tidak menjalankan tugas dalam urutan tertentu.

parallel_for_each Meskipun algoritma bekerja pada iterator ke depan dan iterator akses acak, algoritma ini berkinerja lebih baik dengan iterator akses acak.

Contoh

Contoh berikut menunjukkan struktur parallel_for_each dasar algoritma. Contoh ini mencetak ke konsol setiap nilai dalam objek std::array secara paralel.

// parallel-for-each-structure.cpp
// compile with: /EHsc
#include <ppl.h>
#include <array>
#include <sstream>
#include <iostream>

using namespace concurrency;
using namespace std;

int wmain()
{
   // Create an array of integer values.
   array<int, 5> values = { 1, 2, 3, 4, 5 };

   // Print each value in the array in parallel.
   parallel_for_each(begin(values), end(values), [](int value) {
      wstringstream ss;
      ss << value << L' ';
      wcout << ss.str();
   });
}
/* Sample output:
   5 4 3 1 2
*/

Contoh ini menghasilkan contoh output berikut:

4 5 1 2 3

parallel_for_each Karena algoritma bertindak pada setiap item secara paralel, urutan nilai dicetak ke konsol akan bervariasi.

Untuk contoh lengkap yang menggunakan parallel_for_each algoritma, lihat Cara: Menulis perulangan parallel_for_each.

[Atas]

Algoritma parallel_invoke

Algoritma konkurensi::p arallel_invoke menjalankan serangkaian tugas secara paralel. Ini tidak kembali sampai setiap tugas selesai. Algoritma ini berguna ketika Anda memiliki beberapa tugas independen yang ingin Anda jalankan secara bersamaan.

parallel_invoke Algoritma mengambil sebagai parameternya serangkaian fungsi kerja (fungsi lambda, objek fungsi, atau penunjuk fungsi). parallel_invoke Algoritma kelebihan beban untuk mengambil antara dua dan sepuluh parameter. Setiap fungsi yang Anda lewati parallel_invoke harus mengambil parameter nol.

Seperti algoritma paralel lainnya, parallel_invoke tidak menjalankan tugas dalam urutan tertentu. Topik Paralelisme Tugas menjelaskan bagaimana parallel_invoke algoritma berkaitan dengan tugas dan grup tugas.

Contoh

Contoh berikut menunjukkan struktur parallel_invoke dasar algoritma. Contoh ini secara bersamaan memanggil twice fungsi pada tiga variabel lokal dan mencetak hasilnya ke konsol.

// parallel-invoke-structure.cpp
// compile with: /EHsc
#include <ppl.h>
#include <string>
#include <iostream>

using namespace concurrency;
using namespace std;

// Returns the result of adding a value to itself.
template <typename T>
T twice(const T& t) {
   return t + t;
}

int wmain()
{
   // Define several values.
   int n = 54;
   double d = 5.6;
   wstring s = L"Hello";

   // Call the twice function on each value concurrently.
   parallel_invoke(
      [&n] { n = twice(n); },
      [&d] { d = twice(d); },
      [&s] { s = twice(s); }
   );

   // Print the values to the console.
   wcout << n << L' ' << d << L' ' << s << endl;
}

Contoh ini menghasilkan output berikut:

108 11.2 HelloHello

Untuk contoh lengkap yang menggunakan parallel_invoke algoritma, lihat Cara: Menggunakan parallel_invoke untuk Menulis Rutinitas Pengurutan Paralel dan Cara: Menggunakan parallel_invoke untuk Menjalankan Operasi Paralel.

[Atas]

Algoritma parallel_transform dan parallel_reduce

Algoritma konkurensi::p arallel_transform dan konkurensi::p arallel_reduce adalah versi paralel dari algoritma Pustaka Standar C++ std::transform dan std::accumulate, masing-masing. Versi Runtime Konkurensi berperilaku seperti versi Pustaka Standar C++ kecuali bahwa urutan operasi tidak ditentukan karena dijalankan secara paralel. Gunakan algoritma ini saat Anda bekerja dengan set yang cukup besar untuk mendapatkan keuntungan performa dan skalabilitas dari diproses secara paralel.

Penting

parallel_transform Algoritma dan parallel_reduce hanya mendukung akses acak, dua arah, dan iterator maju karena iterator ini menghasilkan alamat memori yang stabil. Selain itu, iterator ini harus menghasilkan nilai non-lconst .

Algoritma parallel_transform

Anda dapat menggunakan parallel transform algoritma untuk melakukan banyak operasi paralelisasi data. Misalnya, Anda dapat:

• Sesuaikan kecerahan gambar, dan lakukan operasi pemrosesan gambar lainnya.

• Jumlah atau ambil produk titik antara dua vektor, dan lakukan perhitungan numerik lainnya pada vektor.

• Lakukan pelacakan sinar 3-D, di mana setiap iterasi mengacu pada satu piksel yang harus dirender.

Contoh berikut menunjukkan struktur dasar yang digunakan untuk memanggil parallel_transform algoritma. Contoh ini meniadakan setiap elemen objek std::vector dengan dua cara. Cara pertama menggunakan ekspresi lambda. Cara kedua menggunakan std::negate, yang berasal dari std::unary_function.

// basic-parallel-transform.cpp
// compile with: /EHsc
#include <ppl.h>
#include <random>

using namespace concurrency;
using namespace std;

int wmain()
{
    // Create a large vector that contains random integer data.
    vector<int> values(1250000);
    generate(begin(values), end(values), mt19937(42));

    // Create a vector to hold the results.
    // Depending on your requirements, you can also transform the 
    // vector in-place.
    vector<int> results(values.size());

    // Negate each element in parallel.
    parallel_transform(begin(values), end(values), begin(results), [](int n) {
        return -n;
    });

    // Alternatively, use the negate class to perform the operation.
    parallel_transform(begin(values), end(values), begin(values), negate<int>());
}

Peringatan

Contoh ini menunjukkan penggunaan parallel_transformdasar . Karena fungsi kerja tidak melakukan sejumlah besar pekerjaan, peningkatan performa yang signifikan tidak diharapkan dalam contoh ini.

parallel_transform Algoritma memiliki dua kelebihan beban. Kelebihan beban pertama mengambil satu rentang input dan fungsi unary. Fungsi unary dapat berupa ekspresi lambda yang mengambil satu argumen, objek fungsi, atau jenis yang berasal dari unary_function. Kelebihan beban kedua mengambil dua rentang input dan fungsi biner. Fungsi biner dapat berupa ekspresi lambda yang mengambil dua argumen, objek fungsi, atau jenis yang berasal dari std::binary_function. Contoh berikut mengilustrasikan perbedaan ini.

//
// Demonstrate use of parallel_transform together with a unary function.

// This example uses a lambda expression.
parallel_transform(begin(values), end(values), 
    begin(results), [](int n) { 
        return -n;
    });

// Alternatively, use the negate class:
parallel_transform(begin(values), end(values), 
    begin(results), negate<int>());

//
// Demonstrate use of parallel_transform together with a binary function.

// This example uses a lambda expression.
parallel_transform(begin(values), end(values), begin(results), 
    begin(results), [](int n, int m) {
        return n * m;
    });

// Alternatively, use the multiplies class:
parallel_transform(begin(values), end(values), begin(results), 
    begin(results), multiplies<int>());

Penting

Iterator yang Anda berikan untuk output parallel_transform harus sepenuhnya tumpang tindih dengan iterator input atau tidak tumpang tindih sama sekali. Perilaku algoritma ini tidak ditentukan jika iterator input dan output sebagian tumpang tindih.

Algoritma parallel_reduce

parallel_reduce Algoritma berguna ketika Anda memiliki urutan operasi yang memenuhi properti asosiatif. (Algoritma ini tidak memerlukan properti komutatif.) Berikut adalah beberapa operasi yang dapat Anda lakukan dengan parallel_reduce:

• Kalikan urutan matriks untuk menghasilkan matriks.

• Kalikan vektor dengan urutan matriks untuk menghasilkan vektor.

• Menghitung panjang urutan string.

• Gabungkan daftar elemen, seperti string, ke dalam satu elemen.

Contoh dasar berikut menunjukkan cara menggunakan parallel_reduce algoritma untuk menggabungkan urutan string ke dalam satu string. Seperti contoh untuk parallel_transform, perolehan performa tidak diharapkan dalam contoh dasar ini.

// basic-parallel-reduce.cpp
// compile with: /EHsc
#include <ppl.h>
#include <iostream>
#include <string>
#include <vector>

using namespace concurrency;
using namespace std;

int wmain()
{
  // Create a vector of strings.
  vector<wstring> words{
      L"Lorem ",
      L"ipsum ",
      L"dolor ",
      L"sit ",
      L"amet, ",
      L"consectetur ",
      L"adipiscing ",
      L"elit."};
      
  // Reduce the vector to one string in parallel.
  wcout << parallel_reduce(begin(words), end(words), wstring()) << endl;
}

/* Output:
   Lorem ipsum dolor sit amet, consectetur adipiscing elit.
*/

Dalam banyak kasus, Anda dapat menganggap sebagai singkatan parallel_reduce untuk penggunaan parallel_for_each algoritma bersama dengan kelas konkurensi::combinable .

Contoh: Melakukan Peta dan Mengurangi Secara Paralel

Operasi peta menerapkan fungsi ke setiap nilai secara berurutan. Operasi pengurangan menggabungkan elemen urutan menjadi satu nilai. Anda dapat menggunakan fungsi C++ Standard Library std::transform dan std::accumulate untuk melakukan operasi peta dan pengurangan. Namun, untuk banyak masalah, Anda dapat menggunakan parallel_transform algoritma untuk melakukan operasi peta secara paralel dan parallel_reduce algoritma melakukan operasi pengurangan secara paralel.

Contoh berikut membandingkan waktu yang diperlukan untuk menghitung jumlah bilangan prima secara serial dan paralel. Fase peta mengubah nilai non-prime menjadi 0 dan fase pengurangan menjumlahkan nilai.

// parallel-map-reduce-sum-of-primes.cpp
// compile with: /EHsc
#include <windows.h>
#include <ppl.h>
#include <array>
#include <numeric>
#include <iostream>

using namespace concurrency;
using namespace std;

// Calls the provided work function and returns the number of milliseconds 
// that it takes to call that function.
template <class Function>
__int64 time_call(Function&& f)
{
   __int64 begin = GetTickCount();
   f();
   return GetTickCount() - begin;
}

// Determines whether the input value is prime.
bool is_prime(int n)
{
   if (n < 2)
      return false;
   for (int i = 2; i < n; ++i)
   {
      if ((n % i) == 0)
         return false;
   }
   return true;
}

int wmain()
{   
   // Create an array object that contains 200000 integers.
   array<int, 200000> a;

   // Initialize the array such that a[i] == i.
   iota(begin(a), end(a), 0);

   int prime_sum;
   __int64 elapsed;

   // Compute the sum of the numbers in the array that are prime.
   elapsed = time_call([&] {
       transform(begin(a), end(a), begin(a), [](int i) { 
         return is_prime(i) ? i : 0; 
      });
      prime_sum = accumulate(begin(a), end(a), 0);
   });   
   wcout << prime_sum << endl;   
   wcout << L"serial time: " << elapsed << L" ms" << endl << endl;

   // Now perform the same task in parallel.
   elapsed = time_call([&] {
      parallel_transform(begin(a), end(a), begin(a), [](int i) { 
         return is_prime(i) ? i : 0; 
      });
      prime_sum = parallel_reduce(begin(a), end(a), 0);
   });
   wcout << prime_sum << endl;
   wcout << L"parallel time: " << elapsed << L" ms" << endl << endl;
}
/* Sample output:
   1709600813
   serial time: 7406 ms
   
   1709600813
   parallel time: 1969 ms
*/

Untuk contoh lain yang melakukan peta dan mengurangi operasi secara paralel, lihat Cara: Melakukan Operasi Peta dan Kurangi secara Paralel.

[Atas]

Pekerjaan Pemartisian

Untuk menyejajarkan operasi pada sumber data, langkah penting adalah mempartisi sumber ke dalam beberapa bagian yang dapat diakses secara bersamaan oleh beberapa utas. Partisi menentukan bagaimana algoritma paralel harus berkisar di antara utas. Seperti yang dijelaskan sebelumnya dalam dokumen ini, PPL menggunakan mekanisme partisi default yang membuat beban kerja awal dan kemudian menggunakan algoritma pencurian kerja dan rentang mencuri untuk menyeimbangkan partisi ini ketika beban kerja tidak seimbang. Misalnya, ketika satu perulangan perulangan menyelesaikan berbagai iterasi, runtime mendistribusikan ulang pekerjaan dari utas lain ke utas tersebut. Namun, untuk beberapa skenario, Anda mungkin ingin menentukan mekanisme partisi yang berbeda yang lebih cocok untuk masalah Anda.

parallel_forAlgoritma , parallel_for_each, dan parallel_transform menyediakan versi kelebihan beban yang mengambil parameter tambahan, _Partitioner. Parameter ini mendefinisikan jenis partisi yang membagi pekerjaan. Berikut adalah jenis partisi yang didefinisikan PPL:

konkurensi::affinity_partitioner
Membagi pekerjaan menjadi jumlah rentang tetap (biasanya jumlah utas pekerja yang tersedia untuk dikerjakan pada perulangan). Jenis partisi ini mirip static_partitioner, tetapi meningkatkan afinitas cache dengan cara memetakan rentang ke utas pekerja. Jenis partisi ini dapat meningkatkan performa ketika perulangan dijalankan selama himpunan data yang sama beberapa kali (seperti perulangan dalam perulangan) dan data cocok dalam cache. Partisi ini tidak sepenuhnya berpartisipasi dalam pembatalan. Ini juga tidak menggunakan semantik pemblokiran kooperatif dan oleh karena itu tidak dapat digunakan dengan perulangan paralel yang memiliki dependensi ke depan.

konkurensi::auto_partitioner
Membagi pekerjaan menjadi jumlah awal rentang (biasanya jumlah utas pekerja yang tersedia untuk dikerjakan pada perulangan). Runtime menggunakan jenis ini secara default ketika Anda tidak memanggil algoritma paralel berlebih yang mengambil _Partitioner parameter. Setiap rentang dapat dibagi menjadi sub-rentang, dan dengan demikian memungkinkan penyeimbangan beban terjadi. Ketika berbagai pekerjaan selesai, runtime mendistribusikan ulang sub-rentang pekerjaan dari utas lain ke utas tersebut. Gunakan partisi ini jika beban kerja Anda tidak termasuk dalam salah satu kategori lain atau Anda memerlukan dukungan penuh untuk pembatalan atau pemblokiran kooperatif.

konkurensi::simple_partitioner
Membagi pekerjaan menjadi rentang sehingga setiap rentang memiliki setidaknya jumlah iterasi yang ditentukan oleh ukuran gugus yang diberikan. Jenis partisi ini berpartisipasi dalam penyeimbangan beban; namun, runtime tidak membagi rentang menjadi sub-rentang. Untuk setiap pekerja, runtime memeriksa pembatalan dan melakukan penyeimbangan beban setelah _Chunk_size perulangan selesai.

konkurensi::static_partitioner
Membagi pekerjaan menjadi jumlah rentang tetap (biasanya jumlah utas pekerja yang tersedia untuk dikerjakan pada perulangan). Jenis partisi ini dapat meningkatkan performa karena tidak menggunakan pencurian kerja dan karenanya memiliki lebih sedikit overhead. Gunakan jenis partisi ini ketika setiap perulangan perulangan paralel melakukan jumlah pekerjaan tetap dan seragam dan Anda tidak memerlukan dukungan untuk pembatalan atau meneruskan pemblokiran kooperatif.

Peringatan

parallel_for_each Algoritma dan parallel_transform hanya mendukung kontainer yang menggunakan iterator akses acak (seperti std::vector) untuk partisi statis, sederhana, dan afinitas. Penggunaan kontainer yang menggunakan iterator dua arah dan teruskan menghasilkan kesalahan waktu kompilasi. Partisi default, auto_partitioner, mendukung ketiga jenis iterator ini.

Biasanya, partisi ini digunakan dengan cara yang sama, kecuali untuk affinity_partitioner. Sebagian besar jenis partisi tidak mempertahankan status dan tidak dimodifikasi oleh runtime. Oleh karena itu Anda dapat membuat objek partisi ini di situs panggilan, seperti yang ditunjukkan dalam contoh berikut.

// static-partitioner.cpp
// compile with: /EHsc
#include <ppl.h>

using namespace concurrency;

void DoWork(int n)
{
    // TODO: Perform a fixed amount of work...
}

int wmain()
{
    // Use a static partitioner to perform a fixed amount of parallel work.
    parallel_for(0, 100000, [](int n) {
        DoWork(n);
    }, static_partitioner());
}

Namun, Anda harus meneruskan affinity_partitioner objek sebagai referensi non-nilaiconst l sehingga algoritma dapat menyimpan status untuk digunakan kembali perulangan di masa mendatang. Contoh berikut menunjukkan aplikasi dasar yang melakukan operasi yang sama pada himpunan data secara paralel beberapa kali. Penggunaan affinity_partitioner dapat meningkatkan performa karena array cenderung pas dalam cache.

// affinity-partitioner.cpp
// compile with: /EHsc
#include <ppl.h>
#include <array>

using namespace concurrency;
using namespace std;

int wmain()
{
    // Create an array and fill it with zeroes.
    array<unsigned char, 8 * 1024> data;
    data.fill(0);

    // Use an affinity partitioner to perform parallel work on data
    // that is likely to remain in cache.
    // We use the same affinitiy partitioner throughout so that the 
    // runtime can schedule work to occur at the same location for each 
    // iteration of the outer loop.

    affinity_partitioner ap;
    for (int i = 0; i < 100000; i++)
    {
        parallel_for_each(begin(data), end(data), [](unsigned char& c)
        {
            c++;
        }, ap);
    }
}

Perhatian

Berhati-hatilah saat Anda memodifikasi kode yang ada yang bergantung pada semantik pemblokiran kooperatif untuk digunakan static_partitioner atau affinity_partitioner. Jenis partisi ini tidak menggunakan penyeimbangan beban atau pencurian rentang, dan oleh karena itu dapat mengubah perilaku aplikasi Anda.

Cara terbaik untuk menentukan apakah akan menggunakan partisi dalam skenario tertentu adalah dengan bereksperimen dan mengukur berapa lama waktu yang dibutuhkan operasi untuk diselesaikan di bawah beban perwakilan dan konfigurasi komputer. Misalnya, partisi statis mungkin memberikan kecepatan yang signifikan pada komputer multiinti yang hanya memiliki beberapa inti, tetapi dapat mengakibatkan perlambatan pada komputer yang memiliki relatif banyak inti.

[Atas]

Pengurutan Paralel

PPL menyediakan tiga algoritma pengurutan: konkurensi::p arallel_sort, konkurensi::p arallel_buffered_sort, dan konkurensi::p arallel_radixsort. Algoritma pengurutan ini berguna ketika Anda memiliki himpunan data yang dapat memperoleh manfaat dari diurutkan secara paralel. Secara khusus, pengurutan secara paralel berguna ketika Anda memiliki himpunan data besar atau saat Anda menggunakan operasi perbandingan yang mahal secara komputasi untuk mengurutkan data Anda. Masing-masing algoritma ini mengurutkan elemen di tempat.

Algoritma parallel_sort dan parallel_buffered_sort keduanya adalah algoritma berbasis perbandingan. Artinya, mereka membandingkan elemen berdasarkan nilai. parallel_sort Algoritma tidak memiliki persyaratan memori tambahan, dan cocok untuk pengurutan tujuan umum. parallel_buffered_sort Algoritma dapat berkinerja lebih baik daripada parallel_sort, tetapi membutuhkan ruang O(N).

parallel_radixsort Algoritma berbasis hash. Artinya, ia menggunakan kunci bilangan bulat untuk mengurutkan elemen. Dengan menggunakan kunci, algoritma ini dapat langsung menghitung tujuan elemen alih-alih menggunakan perbandingan. Seperti parallel_buffered_sort, algoritma ini membutuhkan ruang O(N).

Tabel berikut ini meringkas properti penting dari tiga algoritma pengurutan paralel.

Algoritma	Deskripsi	Mekanisme pengurutan	Urutkan Stabilitas	Persyaratan memori	Kompleksitas Waktu	Akses iterator
parallel_sort	Pengurutan berbasis perbandingan tujuan umum.	Berbasis perbandingan (naik)	Stabil	Tidak	O((N/P)log(N/P) + 2N((P-1)/P))	Acak
parallel_buffered_sort	Pengurutan berbasis perbandingan tujuan umum yang lebih cepat yang memerlukan ruang O(N).	Berbasis perbandingan (naik)	Stabil	Membutuhkan ruang O(N) tambahan	O((N/P)log(N))	Acak
parallel_radixsort	Pengurutan berbasis kunci bilangan bulat yang memerlukan ruang O(N).	Berdasarkan hash	Stabil	Membutuhkan ruang O(N) tambahan	O(N/P)	Acak

Ilustrasi berikut menunjukkan properti penting dari tiga algoritma pengurutan paralel secara lebih grafis.

Algoritma pengurutan paralel ini mengikuti aturan penanganan pembatalan dan pengecualian. Untuk informasi selengkapnya tentang pembatalan dan penanganan pengecualian di Runtime Konkurensi, lihat Membatalkan Algoritma Paralel dan Penanganan Pengecualian.

Tip

Algoritma pengurutan paralel ini mendukung pemindahan semantik. Anda dapat menentukan operator penetapan pemindahan untuk memungkinkan operasi pertukaran terjadi lebih efisien. Untuk informasi selengkapnya tentang memindahkan semantik dan operator penetapan pemindahan, lihat Deklarator Referensi Rvalue: &&, dan Pindahkan Konstruktor dan Pindahkan Operator Penugasan (C++). Jika Anda tidak menyediakan operator penetapan pemindahan atau fungsi pertukaran, algoritma pengurutan menggunakan konstruktor salinan.

Contoh dasar berikut menunjukkan cara menggunakan parallel_sort untuk mengurutkan vectorint nilai. Secara default, parallel_sort menggunakan std::less untuk membandingkan nilai.

// basic-parallel-sort.cpp
// compile with: /EHsc
#include <ppl.h>
#include <random>
#include <iostream>

using namespace concurrency;
using namespace std;

int wmain()
{
    // Create and sort a large vector of random values.
    vector<int> values(25000000);
    generate(begin(values), end(values), mt19937(42));
    parallel_sort(begin(values), end(values));

    // Print a few values.
    wcout << "V(0)        = " << values[0] << endl;
    wcout << "V(12500000) = " << values[12500000] << endl;
    wcout << "V(24999999) = " << values[24999999] << endl;
} 
/* Output:
   V(0)        = -2147483129
   V(12500000) = -427327
   V(24999999) = 2147483311
*/

Contoh ini menunjukkan cara menyediakan fungsi perbandingan kustom. Ini menggunakan metode std::complex::real untuk mengurutkan nilai ganda> std::complex<dalam urutan naik.

// For this example, ensure that you add the following #include directive:
// #include <complex>

// Create and sort a large vector of random values.
vector<complex<double>> values(25000000);
generate(begin(values), end(values), mt19937(42));
parallel_sort(begin(values), end(values),
    [](const complex<double>& left, const complex<double>& right) {
        return left.real() < right.real();
    });

// Print a few values.
wcout << "V(0)        = " << values[0] << endl;
wcout << "V(12500000) = " << values[12500000] << endl;
wcout << "V(24999999) = " << values[24999999] << endl;
/* Output:
   V(0)        = (383,0)
   V(12500000) = (2.1479e+009,0)
   V(24999999) = (4.29497e+009,0)
*/

Contoh ini menunjukkan cara memberikan fungsi hash ke parallel_radixsort algoritma. Contoh ini mengurutkan titik 3-D. Titik diurutkan berdasarkan jaraknya dari titik referensi.

// parallel-sort-points.cpp
// compile with: /EHsc
#include <ppl.h>
#include <random>
#include <iostream>

using namespace concurrency;
using namespace std;

// Defines a 3-D point.
struct Point
{
    int X;
    int Y;
    int Z;
};

// Computes the Euclidean distance between two points.
size_t euclidean_distance(const Point& p1, const Point& p2)
{
    int dx = p1.X - p2.X;
    int dy = p1.Y - p2.Y;
    int dz = p1.Z - p2.Z;
    return static_cast<size_t>(sqrt((dx*dx) + (dy*dy) + (dz*dz)));
}

int wmain()
{
    // The central point of reference.
    const Point center = { 3, 2, 7 };

    // Create a few random Point values.
    vector<Point> values(7);
    mt19937 random(42);
    generate(begin(values), end(values), [&random] {
        Point p = { random()%10, random()%10, random()%10 };
        return p;
    });

    // Print the values before sorting them.
    wcout << "Before sorting:" << endl;
    for_each(begin(values), end(values), [center](const Point& p) {
        wcout << L'(' << p.X << L"," << p.Y << L"," << p.Z 
              << L") D = " << euclidean_distance(p, center) << endl;
    });
    wcout << endl;

    // Sort the values based on their distances from the reference point.
    parallel_radixsort(begin(values), end(values), 
        [center](const Point& p) -> size_t {
            return euclidean_distance(p, center);
        });

    // Print the values after sorting them.
    wcout << "After sorting:" << endl;
    for_each(begin(values), end(values), [center](const Point& p) {
        wcout << L'(' << p.X << L"," << p.Y << L"," << p.Z 
              << L") D = " << euclidean_distance(p, center) << endl;
    });
    wcout << endl;
} 
/* Output:
    Before sorting:
    (2,7,6) D = 5
    (4,6,5) D = 4
    (0,4,0) D = 7
    (3,8,4) D = 6
    (0,4,1) D = 7
    (2,5,5) D = 3
    (7,6,9) D = 6

    After sorting:
    (2,5,5) D = 3
    (4,6,5) D = 4
    (2,7,6) D = 5
    (3,8,4) D = 6
    (7,6,9) D = 6
    (0,4,0) D = 7
    (0,4,1) D = 7
*/

Untuk ilustrasi, contoh ini menggunakan himpunan data yang relatif kecil. Anda dapat meningkatkan ukuran awal vektor untuk bereksperimen dengan peningkatan performa pada kumpulan data yang lebih besar.

Contoh ini menggunakan ekspresi lambda sebagai fungsi hash. Anda juga dapat menggunakan salah satu implementasi bawaan dari kelas std::hash atau menentukan spesialisasi Anda sendiri. Anda juga dapat menggunakan objek fungsi hash kustom, seperti yang ditunjukkan dalam contoh ini:

// Functor class for computing the distance between points.
class hash_distance
{
public:
    hash_distance(const Point& reference)
        : m_reference(reference)
    {
    }

    size_t operator()(const Point& pt) const {
        return euclidean_distance(pt, m_reference);
    }

private:
    Point m_reference;
};

 

// Use hash_distance to compute the distance between points.
parallel_radixsort(begin(values), end(values), hash_distance(center));

Fungsi hash harus mengembalikan jenis integral (std::is_integral::value harus true). Jenis integral ini harus dapat dikonversi ke jenis size_t.

Memilih Algoritma Pengurutan

Dalam banyak kasus, parallel_sort memberikan keseimbangan performa kecepatan dan memori terbaik. Namun, saat Anda meningkatkan ukuran himpunan data Anda, jumlah prosesor yang tersedia, atau kompleksitas fungsi perbandingan Anda, parallel_buffered_sort atau parallel_radixsort dapat berkinerja lebih baik. Cara terbaik untuk menentukan algoritma pengurutan mana yang akan digunakan dalam skenario tertentu adalah dengan bereksperimen dan mengukur berapa lama waktu yang diperlukan untuk mengurutkan data umum di bawah konfigurasi komputer perwakilan. Ingatlah panduan berikut saat Anda memilih strategi pengurutan.

• Ukuran himpunan data Anda. Dalam dokumen ini, himpunan data kecil berisi kurang dari 1.000 elemen, himpunan data sedang berisi antara 10.000 dan 100.000 elemen, dan himpunan data besar berisi lebih dari 100.000 elemen.

• Jumlah pekerjaan yang dilakukan fungsi perbandingan atau fungsi hash Anda.

• Jumlah sumber daya komputasi yang tersedia.

• Karakteristik himpunan data Anda. Misalnya, satu algoritma mungkin berkinerja baik untuk data yang sudah hampir diurutkan, tetapi tidak juga untuk data yang sepenuhnya tidak diurutkan.

• Ukuran gugus. Argumen opsional _Chunk_size menentukan kapan algoritma beralih dari paralel ke implementasi pengurutan serial karena membahayakan pengurutan keseluruhan menjadi unit kerja yang lebih kecil. Misalnya, jika Anda menyediakan 512, algoritma beralih ke implementasi serial saat satuan kerja berisi 512 atau lebih sedikit elemen. Implementasi serial dapat meningkatkan performa keseluruhan karena menghilangkan overhead yang diperlukan untuk memproses data secara paralel.

Mungkin tidak berguna untuk mengurutkan himpunan data kecil secara paralel, bahkan ketika Anda memiliki sejumlah besar sumber daya komputasi yang tersedia atau fungsi perbandingan atau fungsi hash Anda melakukan sejumlah besar pekerjaan. Anda dapat menggunakan fungsi std::sort untuk mengurutkan himpunan data kecil. (parallel_sort dan parallel_buffered_sort memanggil sort ketika Anda menentukan ukuran gugus yang lebih besar dari himpunan data; namun, parallel_buffered_sort harus mengalokasikan ruang O(N), yang dapat memakan waktu tambahan karena ketidakcocokan kunci atau alokasi memori.)

Jika Anda harus menghemat memori atau alokator memori Anda tunduk pada pertikaian kunci, gunakan parallel_sort untuk mengurutkan himpunan data berukuran sedang. parallel_sort tidak memerlukan ruang tambahan; algoritma lainnya memerlukan ruang O(N).

Gunakan parallel_buffered_sort untuk mengurutkan himpunan data berukuran sedang dan saat aplikasi Anda memenuhi persyaratan ruang O(N) tambahan. parallel_buffered_sort dapat sangat berguna ketika Anda memiliki sejumlah besar sumber daya komputasi atau fungsi perbandingan atau fungsi hash yang mahal.

Gunakan parallel_radixsort untuk mengurutkan himpunan data besar dan saat aplikasi Anda memenuhi persyaratan ruang O(N) tambahan. parallel_radixsort dapat sangat berguna ketika operasi perbandingan yang setara lebih mahal atau ketika kedua operasi mahal.

Perhatian

Menerapkan fungsi hash yang baik mengharuskan Anda mengetahui rentang himpunan data dan bagaimana setiap elemen dalam himpunan data diubah ke nilai yang tidak ditandatangani yang sesuai. Karena operasi hash bekerja pada nilai yang tidak ditandatangani, pertimbangkan strategi pengurutan yang berbeda jika nilai hash yang tidak ditandatangani tidak dapat diproduksi.

Contoh berikut membandingkan performa sort, , parallel_buffered_sortparallel_sort, dan parallel_radixsort dengan sekumpulan besar data acak yang sama.

// choosing-parallel-sort.cpp
// compile with: /EHsc
#include <ppl.h>
#include <random>
#include <iostream>
#include <windows.h>

using namespace concurrency;
using namespace std;

// Calls the provided work function and returns the number of milliseconds 
// that it takes to call that function.
template <class Function>
__int64 time_call(Function&& f)
{
   __int64 begin = GetTickCount();
   f();
   return GetTickCount() - begin;
}

const size_t DATASET_SIZE = 10000000;

// Create
// Creates the dataset for this example. Each call
// produces the same predefined sequence of random data.
vector<size_t> GetData()
{
    vector<size_t> data(DATASET_SIZE);
    generate(begin(data), end(data), mt19937(42));
    return data;
}

int wmain()
{
    // Use std::sort to sort the data.
    auto data = GetData();
    wcout << L"Testing std::sort...";
    auto elapsed = time_call([&data] { sort(begin(data), end(data)); });
    wcout << L" took " << elapsed << L" ms." <<endl;

    // Use concurrency::parallel_sort to sort the data.
    data = GetData();
    wcout << L"Testing concurrency::parallel_sort...";
    elapsed = time_call([&data] { parallel_sort(begin(data), end(data)); });
    wcout << L" took " << elapsed << L" ms." <<endl;

    // Use concurrency::parallel_buffered_sort to sort the data.
    data = GetData();
    wcout << L"Testing concurrency::parallel_buffered_sort...";
    elapsed = time_call([&data] { parallel_buffered_sort(begin(data), end(data)); });
    wcout << L" took " << elapsed << L" ms." <<endl;

    // Use concurrency::parallel_radixsort to sort the data.
    data = GetData();
    wcout << L"Testing concurrency::parallel_radixsort...";
    elapsed = time_call([&data] { parallel_radixsort(begin(data), end(data)); });
    wcout << L" took " << elapsed << L" ms." <<endl;
} 
/* Sample output (on a computer that has four cores):
    Testing std::sort... took 2906 ms.
    Testing concurrency::parallel_sort... took 2234 ms.
    Testing concurrency::parallel_buffered_sort... took 1782 ms.
    Testing concurrency::parallel_radixsort... took 907 ms.
*/

Dalam contoh ini, yang mengasumsikan bahwa dapat diterima untuk mengalokasikan ruang O(N) selama pengurutan, parallel_radixsort melakukan yang terbaik pada himpunan data ini pada konfigurasi komputer ini.

[Atas]

Topik Terkait

Judul	Deskripsi
Cara: Menulis perulangan parallel_for	Memperlihatkan cara menggunakan parallel_for algoritma untuk melakukan perkalian matriks.
Cara: Menulis perulangan parallel_for_each	Memperlihatkan cara menggunakan parallel_for_each algoritma untuk menghitung jumlah bilangan prima dalam objek std::array secara paralel.
Cara: Menggunakan parallel_invoke untuk Menulis Rutinitas Pengurutan Paralel	Memperlihatkan cara menggunakan parallel_invoke algoritma untuk meningkatkan performa algoritma pengurutan bitonik.
Cara: Menggunakan parallel_invoke untuk Menjalankan Operasi Paralel	Memperlihatkan cara menggunakan parallel_invoke algoritma untuk meningkatkan performa program yang melakukan beberapa operasi pada sumber data bersama.
Cara: Melakukan Operasi Peta dan Kurangi Secara Paralel	Memperlihatkan cara menggunakan parallel_transform algoritma dan parallel_reduce untuk melakukan peta dan mengurangi operasi yang menghitung kemunculan kata-kata dalam file.
Parallel Patterns Library (PPL)	Menjelaskan PPL, yang menyediakan model pemrograman imperatif yang mempromosikan skalabilitas dan kemudahan penggunaan untuk mengembangkan aplikasi bersamaan.
Pembatalan di PPL	Menjelaskan peran pembatalan dalam PPL, cara membatalkan pekerjaan paralel, dan cara menentukan kapan grup tugas dibatalkan.
Penanganan Pengecualian	Menjelaskan peran penanganan pengecualian dalam Runtime Konkurensi.

Referensi

Fungsi parallel_for

Fungsi parallel_for_each

Fungsi parallel_invoke

Kelas affinity_partitioner

Kelas auto_partitioner

Kelas simple_partitioner

Kelas static_partitioner

Fungsi parallel_sort

Fungsi parallel_buffered_sort

Fungsi parallel_radixsort