Cara: Menggunakan parallel_invoke untuk Menulis Rutinitas Pengurutan Paralel

  • Artikel

Dokumen ini menjelaskan cara menggunakan algoritma parallel_invoke untuk meningkatkan performa algoritma pengurutan bitonik. Algoritma pengurutan bitonik secara rekursif membagi urutan input menjadi partisi yang diurutkan lebih kecil. Algoritma pengurutan bitonik dapat berjalan secara paralel karena setiap operasi partisi tidak bergantung pada semua operasi lainnya.

Meskipun pengurutan bitonik adalah contoh jaringan pengurutan yang mengurutkan semua kombinasi urutan input, contoh ini mengurutkan urutan yang panjangnya adalah kekuatan dua.

Catatan

Contoh ini menggunakan rutinitas pengurutan paralel untuk ilustrasi. Anda juga dapat menggunakan algoritma pengurutan bawaan yang disediakan PPL: konkurensi::p arallel_sort, konkurensi::p arallel_buffered_sort, dan konkurensi::p arallel_radixsort. Untuk informasi selengkapnya, lihat Algoritma Paralel.

Bagian

Dokumen ini menjelaskan tugas-tugas berikut:

Melakukan Pengurutan Bitonik Secara Serial

Contoh berikut menunjukkan versi serial algoritma pengurutan bitonik. Fungsi membagi bitonic_sort urutan menjadi dua partisi, mengurutkan partisi tersebut ke arah yang berlawanan, lalu menggabungkan hasilnya. Fungsi ini memanggil dirinya dua kali secara rekursif untuk mengurutkan setiap partisi.

const bool INCREASING = true;
const bool DECREASING = false;

// Comparator function for the bitonic sort algorithm.
template <class T>
void compare(T* items, int i, int j, bool dir)
{
   if (dir == (items[i] > items[j]))
   {
      swap(items[i], items[j]);
   }
}

// Sorts a bitonic sequence in the specified order.
template <class T>
void bitonic_merge(T* items, int lo, int n, bool dir)
{
   if (n > 1)
   {
      int m = n / 2;
      for (int i = lo; i < lo + m; ++i)
      {
         compare(items, i, i + m, dir);
      }
      bitonic_merge(items, lo, m, dir);
      bitonic_merge(items, lo + m, m, dir);
   }
}

// Sorts the given sequence in the specified order.
template <class T>
void bitonic_sort(T* items, int lo, int n, bool dir)
{
   if (n > 1)
   {
      // Divide the array into two partitions and then sort 
      // the partitions in different directions.
      int m = n / 2;
      bitonic_sort(items, lo, m, INCREASING);
      bitonic_sort(items, lo + m, m, DECREASING);

      // Merge the results.
      bitonic_merge(items,lo, n, dir);
   }
}

// Sorts the given sequence in increasing order.
template <class T>
void bitonic_sort(T* items, int size)
{
    bitonic_sort(items, 0, size, INCREASING);
}

[Atas]

Menggunakan parallel_invoke untuk Melakukan Pengurutan Bitonik secara Paralel

Bagian ini menjelaskan cara menggunakan parallel_invoke algoritma untuk melakukan algoritma pengurutan bitonik secara paralel.

Untuk melakukan algoritma pengurutan bitonik secara paralel

  1. Tambahkan direktif #include untuk file header ppl.h.

    #include <ppl.h>

  2. Tambahkan direktif using untuk concurrency namespace layanan.

    using namespace concurrency;

  3. Buat fungsi baru, yang disebut parallel_bitonic_mege, yang menggunakan parallel_invoke algoritma untuk menggabungkan urutan secara paralel jika ada cukup banyak pekerjaan yang harus dilakukan. Jika tidak, panggil bitonic_merge untuk menggabungkan urutan secara serial.

    // Sorts a bitonic sequence in the specified order.
template <class T>
void parallel_bitonic_merge(T* items, int lo, int n, bool dir)
{   
   // Merge the sequences concurrently if there is sufficient work to do.
   if (n > 500)
   {
      int m = n / 2;
      for (int i = lo; i < lo + m; ++i)
      {
         compare(items, i, i + m, dir);
      }

      // Use the parallel_invoke algorithm to merge the sequences in parallel.
      parallel_invoke(
         [&items,lo,m,dir] { parallel_bitonic_merge(items, lo, m, dir); },
         [&items,lo,m,dir] { parallel_bitonic_merge(items, lo + m, m, dir); }
      );
   }
   // Otherwise, perform the work serially.
   else if (n > 1)
   {
      bitonic_merge(items, lo, n, dir);
   }   
}

  4. Lakukan proses yang menyerupan satu di langkah sebelumnya, tetapi untuk fungsi .bitonic_sort

    // Sorts the given sequence in the specified order.
template <class T>
void parallel_bitonic_sort(T* items, int lo, int n, bool dir)
{   
   if (n > 1)
   {
      // Divide the array into two partitions and then sort 
      // the partitions in different directions.
      int m = n / 2;

      // Sort the partitions in parallel.
      parallel_invoke(
         [&items,lo,m] { parallel_bitonic_sort(items, lo, m, INCREASING); },
         [&items,lo,m] { parallel_bitonic_sort(items, lo + m, m, DECREASING); }
      );
      
      // Merge the results.
      parallel_bitonic_merge(items, lo, n, dir);
   }
}

  5. Buat versi parallel_bitonic_sort fungsi yang kelebihan beban yang mengurutkan array dalam urutan yang meningkat.

    // Sorts the given sequence in increasing order.
template <class T>
void parallel_bitonic_sort(T* items, int size)
{
   parallel_bitonic_sort(items, 0, size, INCREASING);
}

    parallel_invoke Algoritma mengurangi overhead dengan melakukan rangkaian tugas terakhir pada konteks panggilan. Misalnya, dalam parallel_bitonic_sort fungsi , tugas pertama berjalan pada konteks terpisah, dan tugas kedua berjalan pada konteks panggilan.

    // Sort the partitions in parallel.
parallel_invoke(
   [&items,lo,m] { parallel_bitonic_sort(items, lo, m, INCREASING); },
   [&items,lo,m] { parallel_bitonic_sort(items, lo + m, m, DECREASING); }
);

Contoh lengkap berikut melakukan versi serial dan paralel dari algoritma pengurutan bitonik. Contohnya juga mencetak ke konsol waktu yang diperlukan untuk melakukan setiap komputasi.

// parallel-bitonic-sort.cpp
// compile with: /EHsc
#include <windows.h>
#include <algorithm>
#include <iostream>
#include <random>
#include <ppl.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 bool INCREASING = true;
const bool DECREASING = false;

// Comparator function for the bitonic sort algorithm.
template <class T>
void compare(T* items, int i, int j, bool dir)
{
   if (dir == (items[i] > items[j]))
   {
      swap(items[i], items[j]);
   }
}

// Sorts a bitonic sequence in the specified order.
template <class T>
void bitonic_merge(T* items, int lo, int n, bool dir)
{
   if (n > 1)
   {
      int m = n / 2;
      for (int i = lo; i < lo + m; ++i)
      {
         compare(items, i, i + m, dir);
      }
      bitonic_merge(items, lo, m, dir);
      bitonic_merge(items, lo + m, m, dir);
   }
}

// Sorts the given sequence in the specified order.
template <class T>
void bitonic_sort(T* items, int lo, int n, bool dir)
{
   if (n > 1)
   {
      // Divide the array into two partitions and then sort 
      // the partitions in different directions.
      int m = n / 2;
      bitonic_sort(items, lo, m, INCREASING);
      bitonic_sort(items, lo + m, m, DECREASING);

      // Merge the results.
      bitonic_merge(items,lo, n, dir);
   }
}

// Sorts the given sequence in increasing order.
template <class T>
void bitonic_sort(T* items, int size)
{
    bitonic_sort(items, 0, size, INCREASING);
}

// Sorts a bitonic sequence in the specified order.
template <class T>
void parallel_bitonic_merge(T* items, int lo, int n, bool dir)
{   
   // Merge the sequences concurrently if there is sufficient work to do.
   if (n > 500)
   {
      int m = n / 2;
      for (int i = lo; i < lo + m; ++i)
      {
         compare(items, i, i + m, dir);
      }

      // Use the parallel_invoke algorithm to merge the sequences in parallel.
      parallel_invoke(
         [&items,lo,m,dir] { parallel_bitonic_merge(items, lo, m, dir); },
         [&items,lo,m,dir] { parallel_bitonic_merge(items, lo + m, m, dir); }
      );
   }
   // Otherwise, perform the work serially.
   else if (n > 1)
   {
      bitonic_merge(items, lo, n, dir);
   }   
}

// Sorts the given sequence in the specified order.
template <class T>
void parallel_bitonic_sort(T* items, int lo, int n, bool dir)
{   
   if (n > 1)
   {
      // Divide the array into two partitions and then sort 
      // the partitions in different directions.
      int m = n / 2;

      // Sort the partitions in parallel.
      parallel_invoke(
         [&items,lo,m] { parallel_bitonic_sort(items, lo, m, INCREASING); },
         [&items,lo,m] { parallel_bitonic_sort(items, lo + m, m, DECREASING); }
      );
      
      // Merge the results.
      parallel_bitonic_merge(items, lo, n, dir);
   }
}

// Sorts the given sequence in increasing order.
template <class T>
void parallel_bitonic_sort(T* items, int size)
{
   parallel_bitonic_sort(items, 0, size, INCREASING);
}

int wmain()
{  
   // For this example, the size must be a power of two.
   const int size = 0x200000;

   // Create two large arrays and fill them with random values.
   int* a1 = new int[size];
   int* a2 = new int[size];

   mt19937 gen(42);
   for(int i = 0; i < size; ++i)
   {
      a1[i] = a2[i] = gen();
   }

   __int64 elapsed;
   
   // Perform the serial version of the sort.
   elapsed = time_call([&] { bitonic_sort(a1, size); });
   wcout << L"serial time: " << elapsed << endl;

   // Now perform the parallel version of the sort.
   elapsed = time_call([&] { parallel_bitonic_sort(a2, size); });
   wcout << L"parallel time: " << elapsed << endl;
 
   delete[] a1;
   delete[] a2;
}

Contoh output berikut adalah untuk komputer yang memiliki empat prosesor.

serial time: 4353
parallel time: 1248

[Atas]

Mengompilasi Kode

Untuk mengkompilasi kode, salin lalu tempelkan dalam proyek Visual Studio, atau tempelkan dalam file yang diberi nama parallel-bitonic-sort.cpp lalu jalankan perintah berikut di jendela Prompt Perintah Visual Studio.

cl.exe /EHsc parallel-bitonic-sort.cpp

Pemrograman yang Kuat

Contoh ini menggunakan parallel_invoke algoritma alih-alih kelas konkurensi::task_group karena masa pakai setiap grup tugas tidak melampaui fungsi. Kami menyarankan agar Anda menggunakan parallel_invoke kapan Anda bisa karena memiliki lebih sedikit overhead eksekusi daripada task group objek, dan oleh karena itu memungkinkan Anda menulis kode yang berkinerja lebih baik.

Versi paralel dari beberapa algoritma berkinerja lebih baik hanya ketika ada cukup pekerjaan yang harus dilakukan. Misalnya, parallel_bitonic_merge fungsi memanggil versi serial, bitonic_merge, jika ada 500 atau lebih sedikit elemen dalam urutan. Anda juga dapat merencanakan strategi pengurutan anda secara keseluruhan berdasarkan jumlah pekerjaan. Misalnya, mungkin lebih efisien untuk menggunakan versi serial algoritma pengurutan cepat jika array berisi kurang dari 500 item, seperti yang ditunjukkan dalam contoh berikut:

template <class T>
void quick_sort(T* items, int lo, int n)
{
   // TODO: The function body is omitted for brevity.
}

template <class T>
void parallel_bitonic_sort(T* items, int lo, int n, bool dir)
{
   // Use the serial quick sort algorithm if there are relatively few
   // items to sort. The associated overhead for running few tasks in 
   // parallel may not overcome the benefits of parallel processing.
   if (n - lo + 1 <= 500)
   {
      quick_sort(items, lo, n);
   }
   else if (n > 1)
   {
      // Divide the array into two partitions and then sort 
      // the partitions in different directions.
      int m = n / 2;

      // Sort the partitions in parallel.
      parallel_invoke(
         [&items,lo,m] { parallel_bitonic_sort(items, lo, m, INCREASING); },
         [&items,lo,m] { parallel_bitonic_sort(items, lo + m, m, DECREASING); }
      );
      
      // Merge the results.
      parallel_bitonic_merge(items, lo, n, dir);
   }
}

Seperti halnya algoritma paralel apa pun, kami sarankan Anda membuat profil dan menyetel kode Anda sebagaimana mewajarinya.

Baca juga

Paralelisme Tugas
Fungsi parallel_invoke