Nasıl yapılır: Paralel Sıralama Rutini Yazmak için parallel_invoke Kullanma

  • Makale

Bu belgede, bitonik sıralama algoritmasının performansını artırmak için parallel_invoke algoritmasının nasıl kullanılacağı açıklanmaktadır. Bitonik sıralama algoritması, giriş dizisini yinelemeli olarak daha küçük sıralanmış bölümlere böler. Her bölümleme işlemi diğer tüm işlemlerden bağımsız olduğundan bitonik sıralama algoritması paralel olarak çalıştırılabilir.

Bitonik sıralama, giriş dizilerinin tüm bileşimlerini sıralayan bir sıralama ağı örneği olsa da, bu örnek uzunlukları iki olan dizileri sıralar.

Not

Bu örnekte, çizim için paralel sıralama yordamı kullanılır. PPL'nin sağladığı yerleşik sıralama algoritmalarını da kullanabilirsiniz: eşzamanlılık::p arallel_sort, concurrency::p arallel_buffered_sort ve concurrency::p arallel_radixsort. Daha fazla bilgi için bkz . Paralel Algoritmalar.

Bölümler

Bu belgede aşağıdaki görevler açıklanmaktadır:

Bitonik Sıralamayı Seri Olarak Gerçekleştirme

Aşağıdaki örnekte bitonik sıralama algoritmasının seri sürümü gösterilmektedir. bitonic_sort işlevi sırayı iki bölüme böler, bu bölümleri ters yönde sıralar ve ardından sonuçları birleştirir. Bu işlev, her bölümü sıralamak için kendisini iki kez özyinelemeli olarak çağırır.

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);
}

[Üst]

Bitonik Sıralamayı Paralel Olarak Gerçekleştirmek için parallel_invoke Kullanma

Bu bölümde, bitonik sıralama algoritmasını parallel_invoke paralel olarak gerçekleştirmek için algoritmanın nasıl kullanılacağı açıklanmaktadır.

Paralel olarak bitonic sıralama algoritmasını gerçekleştirmek için

  1. ppl.h üst bilgi dosyası için bir #include yönerge ekleyin.

    #include <ppl.h>

  2. Ad alanı için concurrency bir using yönerge ekleyin.

    using namespace concurrency;

  3. Yapılacak yeterli miktarda iş varsa dizileri paralel olarak birleştirmek için algoritmayı parallel_invoke kullanan adlı parallel_bitonic_megeyeni bir işlev oluşturun. Aksi takdirde, seri olarak dizileri birleştirmek için çağrısı bitonic_merge .

    // 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. Önceki adımdakine benzeyen ancak işlev için bir işlem gerçekleştirin 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. İşlevin diziyi parallel_bitonic_sort artan düzende sıralayan aşırı yüklenmiş bir sürümünü oluşturun.

    // 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);
}

    Algoritma, parallel_invoke çağrı bağlamındaki son görev serisini gerçekleştirerek ek yükü azaltır. Örneğin, işlevinde parallel_bitonic_sort ilk görev ayrı bir bağlamda, ikinci görev ise çağrı bağlamı üzerinde çalışır.

    // 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); }
);

Aşağıdaki tam örnek, bitonik sıralama algoritmasının hem seri hem de paralel sürümlerini gerçekleştirir. Örnek, her hesaplamayı gerçekleştirmek için gereken süreyi konsola da yazdırır.

// 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;
}

Aşağıdaki örnek çıkış, dört işlemcisi olan bir bilgisayara yöneliktir.

serial time: 4353
parallel time: 1248

[Üst]

Kod Derleniyor

Kodu derlemek için kopyalayın ve visual studio projesine yapıştırın veya adlı parallel-bitonic-sort.cpp bir dosyaya yapıştırın ve ardından visual studio komut istemi penceresinde aşağıdaki komutu çalıştırın.

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

Güçlü Programlama

Her görev grubunun ömrü bir işlevin ötesine geçmediği için bu örnek eşzamanlılık::task_group sınıfı yerine algoritmayı kullanırparallel_invoke. Nesnelere göre daha az yürütme yükü olduğundan ve bu nedenle daha iyi performans gösteren kod yazmanıza olanak sağladığındantask group, kullanabileceğiniz zamanları kullanmanızı parallel_invoke öneririz.

Bazı algoritmaların paralel sürümleri yalnızca yapılacak yeterli iş olduğunda daha iyi performans gösterir. Örneğin, dizide parallel_bitonic_merge 500 veya daha az öğe varsa işlev seri sürümünü bitonic_mergeçağırır. Genel sıralama stratejinizi çalışma miktarına göre de planlayabilirsiniz. Örneğin, aşağıdaki örnekte gösterildiği gibi dizi 500'den az öğe içeriyorsa hızlı sıralama algoritmasının seri sürümünü kullanmak daha verimli olabilir:

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);
   }
}

Her paralel algoritmada olduğu gibi, kodunuzu uygun şekilde profilinizi oluşturmanızı ve ayarlamanızı öneririz.

Ayrıca bkz.

Görev Paralelliği
parallel_invoke İşlevi