Nasıl yapılır: paralel sıralama rutin yazmak için parallel_invoke kullanın

Bu belge nasıl kullanılacağını açıklar parallel_invoke bitonic sıralama algoritmasını performansını artırmak için algoritma. Bitonic sıralama algoritmasını özyinelemeli olarak daha küçük sıralanmış bölümlere giriş sırası böler. Her bölüm işlemi tüm diğer işlemleri bağımsız olduğundan bitonic sıralama algoritmasını paralel olarak çalıştırabilirsiniz.

Bitonic sıralama örneği olsa da bir Ağ sıralama , tüm birleşimleri giriş dizileri sıralar, bu örnek, uzunluğu ikinin gücü olan sıraları sıralar.

Not

Bu örnek için resimde paralel sıralama yordamını kullanır.ppl sağlayan yerleşik sıralama algoritmaları da kullanabilirsiniz: concurrency::parallel_sort, concurrency::parallel_buffered_sort, ve concurrency::parallel_radixsort.Daha fazla bilgi için bkz. Paralel algoritmalar.

Bölümler

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

• Bitonic sıralama seri olarak gerçekleştirme

• Parallel_invoke Bitonic sıralama yapmak için paralel olarak kullanma

Bitonic sıralama seri olarak gerçekleştirme

Aşağıdaki örnek bitonic sıralama algoritmasını seri sürümünü gösterir. bitonic_sort İşlev sırası iki bölüme ayırır, bu bölümler, zıt yönlere sıralar ve sonuçları birleştirir. Bu işlev, kendisi her bölüm sıralamak için iki kez yinelemeli olarak çağırıyor.

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

Top

Parallel_invoke Bitonic sıralama yapmak için paralel olarak kullanma

Bu bölüm nasıl kullanılacağını açıklar parallel_invoke bitonic sıralama algoritmasını paralel olarak algoritması.

Yordamlar

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

1. Add bir #include üstbilgi dosyası ppl.h yönergesi.

   #include <ppl.h>
   

2. Add bir using yönergesi için concurrency ad alanı.

   using namespace concurrency;
   

3. Adı verilen yeni bir işlev oluşturun parallel_bitonic_mege, kullanan parallel_invoke iş yapmak için yeterli miktarda ise paralel dizileri birleştirme algoritması. Aksi halde, Ara bitonic_merge sıralarını seri olarak birleştirmek için.

   // 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ımda ancak için benzer bir işlem gerçekleştirmek bitonic_sort işlevi.

   // 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. Aşırı yüklü bir sürümünü oluşturmak parallel_bitonic_sort dizi artan düzende sıralar işlevi.

   // 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 Algoritmasını arama içeriğine görev dizisi son gerçekleştirerek yükünü azaltır. Örneğin, parallel_bitonic_sort işlevi, ilk görev, ayrı bir içerik üzerinde çalışır ve ikinci görev arama içerik ü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 örneğin seri ve paralel bitonic sıralama algoritmasını sürümlerini gerçekleştirir. Bu örnek ayrıca her hesaplama gerçekleştirmek için gereken süreyi konsola 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 çıktı dört işlemci bulunan bir bilgisayar içindir.

serial time: 4353
parallel time: 1248

Top

Kod Derleniyor

Kodu derlemek için kopyalayın ve sonra Visual Studio Project'te yapıştırın veya adlı bir dosyaya yapıştırın paralel bitonic sort.cpp ve Visual Studio komut istemi penceresinde aşağıdaki komutu çalıştırın.

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

Güçlü programlama

Bu örnek parallel_invoke yerine algoritması concurrency::task_group yaşam her görev grubunun bir işlevin genişletmek değil çünkü sınıf. Sizin kullanmanızı öneririz parallel_invoke ne zaman yapabilecekleriniz yükü daha az yürütme olduğundan task group nesneleri ve bu nedenle daha iyi performanslı yazmanýza olanak verir.

Bazı algoritmalar paralel sürümleri daha iyi yapmak için yeterli iş olduğunda gerçekleştirin. Örneğin, parallel_bitonic_merge işlevini çağırır seri sürüm bitonic_merge, sırayla 500 veya daha az sayıda öğe varsa. İş miktarına göre Genel sıralama stratejinizi da planlayabilirsiniz. Örneğin, dizi 500'den az öğe içeriyorsa aşağıdaki örnekte gösterildiği gibi hızlı sıralama algoritması seri sürümünü kullanmanız 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);
   }
}

Herhangi bir paralel algoritması ile gibi profil ve kodunuzu uygun olarak ayarlamak öneririz.

Ayrıca bkz.

Başvuru

parallel_invoke işlevi

Kavramlar

Görev paralellik (eşzamanlılık çalışma zamanı)