Paralel Algoritmalar

Paralel Desenler Kitaplığı (PPL), veri koleksiyonları üzerinde eşzamanlı olarak çalışma gerçekleştiren algoritmalar sağlar. Bu algoritmalar, C++ Standart Kitaplığı tarafından sağlanan algoritmalara benzer.

Paralel algoritmalar Eşzamanlılık Çalışma Zamanı'ndaki mevcut işlevlerden oluşturulur. Örneğin, concurrency::p arallel_for algoritması paralel döngü yinelemelerini gerçekleştirmek için eşzamanlılık ::structured_task_group nesnesini kullanır. Algoritma parallel_for bölümleri, kullanılabilir bilgi işlem kaynağı sayısı göz önüne alındığında en uygun şekilde çalışır.

Bölümler

• parallel_for Algoritması

• parallel_for_each Algoritması

• parallel_invoke Algoritması

• parallel_transform ve parallel_reduce Algoritmaları

  • parallel_transform Algoritması

  • parallel_reduce Algoritması

  • Örnek: Paralel Olarak Eşleme ve Azaltma Gerçekleştirme

• Bölümleme Çalışması

• Paralel Sıralama

  • Sıralama Algoritması Seçme

parallel_for Algoritması

Concurrency ::p arallel_for algoritması aynı görevi sürekli olarak paralel olarak gerçekleştirir. Bu görevlerin her biri bir yineleme değeriyle parametrelendirilir. Bu algoritma, bu döngünün yinelemeleri arasında kaynakları paylaşmayan bir döngü gövdesine sahip olduğunuzda kullanışlıdır.

Algoritma, parallel_for görevleri paralel yürütme için en uygun şekilde bölümler. İş yükleri dengesiz olduğunda bu bölümleri dengelemek için bir iş çalma algoritması ve aralık çalma kullanır. Bir döngü yinelemesi işbirliğiyle engellendiğinde, çalışma zamanı geçerli iş parçacığına atanan yineleme aralığını diğer iş parçacıklarına veya işlemcilere yeniden dağıtır. Benzer şekilde, bir iş parçacığı bir dizi yinelemeyi tamamladığında, çalışma zamanı diğer iş parçacıklarından bu iş parçacığına yeniden dağıtır. Algoritma iç parallel_for içe paralelliği de destekler. Bir paralel döngü başka bir paralel döngü içerdiğinde, çalışma zamanı kaynakları paralel yürütme için verimli bir şekilde döngü gövdeleri arasında koordine eder.

Algoritmanın parallel_for birkaç aşırı yüklenmiş sürümü vardır. İlk sürüm bir başlangıç değeri, bir bitiş değeri ve bir iş işlevi (lambda ifadesi, işlev nesnesi veya işlev işaretçisi) alır. İkinci sürüm bir başlangıç değeri, bir bitiş değeri, adım atacak bir değer ve bir iş işlevi alır. Bu işlevin ilk sürümünde adım değeri olarak 1 kullanılır. Kalan sürümler, iş parçacıkları arasında aralıkları nasıl parallel_for bölümlemeniz gerektiğini belirtmenizi sağlayan bölümleyici nesnelerini alır. Bölümleyiciler, bu belgedeki Bölümleme Çalışması bölümünde daha ayrıntılı olarak açıklanmıştır.

Kullanmak parallel_foriçin birçok for döngü dönüştürebilirsiniz. Ancak, parallel_for algoritma aşağıdaki yollarla deyiminden for farklıdır:

• Algoritma parallel_for parallel_for , görevleri önceden belirlenmiş bir sırada yürütmez.

• Algoritma parallel_for rastgele sonlandırma koşullarını desteklemez. Yineleme parallel_for değişkeninin geçerli değeri değerinden lastküçük olduğunda algoritma durdurulur.

• _Index_type tür parametresi tam sayı türünde olmalıdır. Bu tam sayı türü imzalanabilir veya imzasız olabilir.

• Döngü yinelemesi ileriye doğru olmalıdır. Parametre parallel_for 1'den küçükse _Step algoritma std::invalid_argument türünde bir özel durum oluşturur.

• Algoritma için parallel_for özel durum işleme mekanizması bir for döngününkinden farklıdır. Paralel döngü gövdesinde aynı anda birden çok özel durum oluşursa, çalışma zamanı özel durumlardan yalnızca birini adlı parallel_foriş parçacığına yayılır. Buna ek olarak, bir döngü yinelemesi bir özel durum oluşturursa, çalışma zamanı genel döngünün hemen durmaz. Bunun yerine döngü iptal edildi durumuna yerleştirilir ve çalışma zamanı henüz başlatılmamış görevleri atar. Özel durum işleme ve paralel algoritmalar hakkında daha fazla bilgi için bkz . Özel Durum İşleme.

Algoritma rastgele sonlandırma koşullarını desteklemese de parallel_for , tüm görevleri durdurmak için iptali kullanabilirsiniz. İptal hakkında daha fazla bilgi için bkz . PPL'de İptal.

Örnek

Aşağıdaki örnekte algoritmanın temel yapısı gösterilmektedir parallel_for . Bu örnek, [1, 5] aralığındaki her değeri paralel olarak konsola yazdırır.

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

Bu örnek aşağıdaki örnek çıkışı oluşturur:

1 2 4 3 5

parallel_for Algoritma her öğe üzerinde paralel olarak hareket ettiğinden, değerlerin konsola yazdırılma sırası değişir.

Algoritmayı parallel_for kullanan eksiksiz bir örnek için bkz . Nasıl yapılır: parallel_for Döngüsü Yazma.

[Üst]

parallel_for_each Algoritması

concurrency::p arallel_for_each algoritması, C++ Standart Kitaplığı tarafından sağlananlar gibi yinelemeli bir kapsayıcıda görevleri paralel olarak gerçekleştirir. Algoritmanın kullandığı bölümleme mantığını parallel_for kullanır.

Algoritma parallel_for_each , C++ Standart Kitaplığı std::for_each algoritmasına parallel_for_each benzer, ancak algoritma görevleri eşzamanlı olarak yürütür. Diğer paralel algoritmalar gibi, parallel_for_each görevleri belirli bir sırada yürütmez.

Algoritma hem iletme yineleyicileri hem de rastgele erişim yineleyicileri üzerinde çalışsa parallel_for_each da, rastgele erişim yineleyicileri ile daha iyi performans gösterir.

Örnek

Aşağıdaki örnekte algoritmanın temel yapısı gösterilmektedir parallel_for_each . Bu örnek, std::array nesnesindeki her değeri konsola paralel olarak yazdırır.

// 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
*/

Bu örnek aşağıdaki örnek çıkışı oluşturur:

4 5 1 2 3

parallel_for_each Algoritma her öğe üzerinde paralel olarak hareket ettiğinden, değerlerin konsola yazdırılma sırası değişir.

Algoritmayı parallel_for_each kullanan eksiksiz bir örnek için bkz . Nasıl yapılır: parallel_for_each Döngüsü Yazma.

[Üst]

parallel_invoke Algoritması

concurrency::p arallel_invoke algoritması bir dizi görevi paralel olarak yürütür. Her görev bitene kadar geri dönmez. Bu algoritma, aynı anda yürütmek istediğiniz birkaç bağımsız göreviniz olduğunda kullanışlıdır.

Algoritma parallel_invoke , parametreleri olarak bir dizi iş işlevi (lambda işlevleri, işlev nesneleri veya işlev işaretçileri) alır. Algoritma parallel_invoke , iki ila on parametreyi alacak şekilde aşırı yüklenmiştir. Geçirdiğiniz parallel_invoke her işlev sıfır parametre almalıdır.

Diğer paralel algoritmalar gibi, parallel_invoke görevleri belirli bir sırada yürütmez. Görev Paralelliği konusu algoritmanın parallel_invoke görevler ve görev gruplarıyla ilişkisini açıklar.

Örnek

Aşağıdaki örnekte algoritmanın temel yapısı gösterilmektedir parallel_invoke . Bu örnek, işlevi üç yerel değişkende eşzamanlı olarak çağırır twice ve sonucu konsola yazdırır.

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

Bu örnek aşağıdaki çıkışı oluşturur:

108 11.2 HelloHello

Algoritmayı parallel_invoke kullanan tam örnekler için bkz . How to: Use parallel_invoke to Write a Parallel Sort Routine and How to: Use parallel_invoke to Execute Parallel Operations.

[Üst]

parallel_transform ve parallel_reduce Algoritmaları

Eşzamanlılık::p arallel_transform ve concurrency::p arallel_reduce algoritmaları sırasıyla std::transform ve std::accumulate C++ Standart Kitaplığı algoritmalarının paralel sürümleridir. Eşzamanlılık Çalışma Zamanı sürümleri C++ Standart Kitaplığı sürümleri gibi davranır, ancak işlem sırası paralel olarak yürütülür çünkü belirlenmemektedir. Paralel olarak işlenmekten performans ve ölçeklenebilirlik avantajları elde etmek için yeterince büyük bir kümeyle çalışırken bu algoritmaları kullanın.

parallel_transform Algoritması

Algoritmayı parallel transform kullanarak birçok veri paralelleştirme işlemi gerçekleştirebilirsiniz. Örneğin, şunları yapabilirsiniz:

• Görüntünün parlaklığını ayarlayın ve diğer görüntü işleme işlemlerini gerçekleştirin.

• noktalı ürünü iki vektör arasında toplama veya alma ve vektörler üzerinde diğer sayısal hesaplamaları gerçekleştirme.

• Her yinelemenin işlenmesi gereken bir piksele başvurduğu 3-B ışın izleme gerçekleştirin.

Aşağıdaki örnekte algoritmayı çağırmak parallel_transform için kullanılan temel yapı gösterilmektedir. Bu örnek, bir std::vector nesnesinin her öğesini iki şekilde yok eder. İlk yöntemde lambda ifadesi kullanılır. İkinci yol, std::unary_function türetilen std::negate kullanır.

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

Algoritmanın parallel_transform iki aşırı yüklemesi vardır. İlk aşırı yükleme bir giriş aralığı ve birli işlev alır. Birli işlev, bir bağımsız değişken, işlev nesnesi veya öğesinden unary_functiontüretilen bir tür alan bir lambda ifadesi olabilir. İkinci aşırı yükleme iki giriş aralığı ve bir ikili işlev alır. İkili işlev, iki bağımsız değişken alan bir lambda ifadesi, bir işlev nesnesi veya std::binary_function türetilen bir tür olabilir. Aşağıdaki örnekte bu farklar gösterilmektedir.

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

parallel_reduce Algoritması

Algoritma parallel_reduce , ilişkilendirici özelliği karşılayan bir dizi işleminiz olduğunda kullanışlıdır. (Bu algoritma, commutative özelliğini gerektirmez.) ile parallel_reducegerçekleştirebileceğiniz işlemlerden bazıları şunlardır:

• Matris oluşturmak için matris dizilerini çarpın.

• Vektör oluşturmak için bir vektöri matris dizisiyle çarpın.

• Dize dizisinin uzunluğunu hesaplama.

• Dizeler gibi öğelerin listesini tek bir öğede birleştirin.

Aşağıdaki temel örnekte, bir dizi dizeyi tek bir dizede parallel_reduce birleştirmek için algoritmanın nasıl kullanılacağı gösterilmektedir. örneklerinde parallel_transformolduğu gibi, bu temel örnekte de performans kazançları beklenmemektedir.

// 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.
*/

Çoğu durumda, concurrency::combinable sınıfıyla birlikte algoritmanın parallel_for_each kullanımı için kısaltma olarak düşünebilirsinizparallel_reduce.

Örnek: Paralel Olarak Eşleme ve Azaltma Gerçekleştirme

Eşleme işlemi, bir dizideki her değere bir işlev uygular. Azaltma işlemi, bir dizinin öğelerini tek bir değerde birleştirir. Eşleme ve azaltma işlemlerini gerçekleştirmek için C++ Standart Kitaplığı std::transform ve std::accumulate işlevlerini kullanabilirsiniz. Bununla birlikte, birçok sorun için algoritmayı parallel_transform kullanarak eşleme işlemini paralel ve parallel_reduce algoritma azaltma işlemini paralel olarak gerçekleştirebilirsiniz.

Aşağıdaki örnek, asal sayıların toplamını seri olarak ve paralel olarak hesaplamak için geçen süreyi karşılaştırır. Eşleme aşaması, asal olmayan değerleri 0'a dönüştürür ve azaltma aşaması değerleri toplar.

// 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
*/

Paralel bir eşleme ve azaltma işlemi gerçekleştiren başka bir örnek için bkz . Nasıl yapılır: Eşleme ve Azaltma İşlemlerini Paralel Olarak Gerçekleştirme.

[Üst]

Bölümleme Çalışması

Bir veri kaynağındaki bir işlemi paralelleştirmek için temel bir adım , kaynağı birden çok iş parçacığı tarafından eşzamanlı olarak erişilebilen birden çok bölüme bölmektir . Bölümleyici, paralel algoritmanın iş parçacıkları arasında aralıkları nasıl bölümlemesi gerektiğini belirtir. Bu belgede daha önce açıklandığı gibi, PPL bir ilk iş yükü oluşturan ve iş yükleri dengesiz olduğunda bu bölümleri dengelemek için bir iş çalma algoritması ve aralık çalma kullanan varsayılan bir bölümleme mekanizması kullanır. Örneğin, bir döngü yinelemesi bir dizi yinelemeyi tamamladığında, çalışma zamanı diğer iş parçacıklarından bu iş parçacığına yeniden dağıtır. Ancak bazı senaryolarda, sorununuz için daha uygun olan farklı bir bölümleme mekanizması belirtmek isteyebilirsiniz.

parallel_for, parallel_for_eachve parallel_transform algoritmaları, ek bir parametre _Partitioneralan aşırı yüklenmiş sürümler sağlar. Bu parametre, işi bölen bölümleyici türünü tanımlar. PPL'nin tanımladığı bölümleyici türleri şunlardır:

eşzamanlılık::affinity_partitioner
Çalışmayı sabit sayıda aralığa (genellikle döngü üzerinde çalışmak için kullanılabilen çalışan iş parçacığı sayısı) böler. Bu bölümleyici türü öğesine benzer static_partitioner, ancak aralıkları çalışan iş parçacıklarıyla eşleme yöntemiyle önbellek benzeşimini geliştirir. Bu bölümleyici türü, bir döngü aynı veri kümesi üzerinde birden çok kez yürütülürse (döngü içindeki döngü gibi) ve veriler önbelleğe sığdığında performansı iyileştirebilir. Bu bölümleyici iptal işlemine tam olarak katılmaz. Ayrıca işbirliğine dayalı engelleme semantiği kullanmaz ve bu nedenle ileriye doğru bağımlılığı olan paralel döngülerle kullanılamaz.

eşzamanlılık::auto_partitioner
çalışmayı ilk aralık sayısına (genellikle döngü üzerinde çalışmak için kullanılabilen çalışan iş parçacığı sayısı) böler. Parametre alan _Partitioner aşırı yüklenmiş bir paralel algoritma çağırmadığınızda çalışma zamanı varsayılan olarak bu türü kullanır. Her aralık alt aralıklara ayrılabilir ve böylece yük dengelemenin gerçekleşmesini sağlar. Bir çalışma aralığı tamamlandığında, çalışma zamanı alt iş aralıklarını diğer iş parçacıklarından bu iş parçacığına yeniden dağıtır. İş yükünüz diğer kategorilerden birine dahil değilse veya iptal veya işbirliğine dayalı engelleme için tam destek gerekiyorsa bu bölümleyiciyi kullanın.

eşzamanlılık::simple_partitioner
Her aralığın verilen öbek boyutu tarafından belirtilen yineleme sayısı en az olacak şekilde işi aralıklara böler. Bu bölümleyici türü yük dengelemeye katılır; ancak çalışma zamanı aralıkları alt aralıklara bölmez. Her çalışan için çalışma zamanı iptali denetler ve yinelemeler tamamlandıktan sonra _Chunk_size yük dengeleme gerçekleştirir.

eşzamanlılık::static_partitioner
Çalışmayı sabit sayıda aralığa (genellikle döngü üzerinde çalışmak için kullanılabilen çalışan iş parçacığı sayısı) böler. Bu bölümleyici türü, iş çalma kullanmadığından ve bu nedenle daha az ek yükü olduğundan performansı geliştirebilir. Paralel döngünün her yinelemesi sabit ve tekdüzen bir iş miktarı gerçekleştirdiğinde ve iptal veya ileriye dönük işbirliği engellemesi için destek gerektirmediğinizde bu bölümleyici türünü kullanın.

Bu bölümleyiciler genellikle dışında affinity_partitioneraynı şekilde kullanılır. Bölümleyici türlerinin çoğu durumu korumaz ve çalışma zamanı tarafından değiştirilmez. Bu nedenle, aşağıdaki örnekte gösterildiği gibi çağrı sitesinde bu bölümleyici nesnelerini oluşturabilirsiniz.

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

Ancak, algoritmanın gelecekteki döngülerin yeniden kullanılabilmesi için durumu depo edebilmesi için nesneyi affinity_partitioner l olmayan birconst başvuru olarak geçirmeniz gerekir. Aşağıdaki örnekte, bir veri kümesinde aynı işlemi birden çok kez paralel olarak gerçekleştiren temel bir uygulama gösterilmektedir. dizinin önbelleğe sığma olasılığı yüksek olduğundan kullanımı affinity_partitioner performansı geliştirebilir.

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

Belirli bir senaryoda bölümleyicinin kullanılıp kullanılmayacağını belirlemenin en iyi yolu, temsili yüklemeler ve bilgisayar yapılandırmaları altında işlemlerin tamamlanmasının ne kadar sürdüğünü denemek ve ölçmektir. Örneğin, statik bölümleme yalnızca birkaç çekirdeği olan çok çekirdekli bir bilgisayarda önemli bir hız sağlayabilir, ancak nispeten çok sayıda çekirdeği olan bilgisayarlarda yavaşlamalara neden olabilir.

[Üst]

Paralel Sıralama

PPL üç sıralama algoritması sağlar: concurrency::p arallel_sort, concurrency::p arallel_buffered_sort ve concurrency::p arallel_radixsort. Bu sıralama algoritmaları, paralel olarak sıralanmanın avantajını sağlayabileceğiniz bir veri kümeniz olduğunda kullanışlıdır. Özellikle, büyük bir veri kümeniz olduğunda veya verilerinizi sıralamak için hesaplama açısından pahalı bir karşılaştırma işlemi kullandığınızda paralel sıralama yararlıdır. Bu algoritmaların her biri öğeleri yerinde sıralar.

parallel_sort ve parallel_buffered_sort algoritmalarının her ikisi de karşılaştırma tabanlı algoritmalardır. Yani, öğeleri değere göre karşılaştırır. Algoritmanın parallel_sort ek bellek gereksinimi yoktur ve genel amaçlı sıralama için uygundur. Algoritma parallel_buffered_sort , değerinden parallel_sortdaha iyi performans sergileyebilir, ancak O(N) alanı gerektirir.

Algoritma parallel_radixsort karma tabanlıdır. Yani, öğeleri sıralamak için tamsayı tuşlarını kullanır. Bu algoritma, anahtarları kullanarak karşılaştırmaları kullanmak yerine doğrudan bir öğenin hedefini hesaplayabilir. gibi parallel_buffered_sort, bu algoritma O(N) alanı gerektirir.

Aşağıdaki tabloda, üç paralel sıralama algoritmasının önemli özellikleri özetlemektedir.

Aşağıdaki çizimde üç paralel sıralama algoritmasının önemli özellikleri daha grafiksel olarak gösterilmiştir.

Bu paralel sıralama algoritmaları iptal ve özel durum işleme kurallarını izler. Eşzamanlılık Çalışma Zamanı'nda iptal ve özel durum işleme hakkında daha fazla bilgi için bkz . Paralel Algoritmaları İptal Etme ve Özel Durum İşleme.

Aşağıdaki temel örnekte, bir vector int dizi değeri sıralamak için nasıl kullanılacağı parallel_sort gösterilmektedir. Varsayılan olarak, parallel_sort değerleri karşılaştırmak için std::less kullanır.

// 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
*/

Bu örnekte, özel bir karşılaştırma işlevinin nasıl sağhılı olduğu gösterilmektedir. std::complex::real yöntemini kullanarak std::complex<çift> değerlerini artan düzende sıralar.

// 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)
*/

Bu örnekte algoritmaya karma işlevinin nasıl sağlanacağı gösterilmektedir parallel_radixsort . Bu örnek 3B noktaları sıralar. Noktalar, bir başvuru noktasından uzaklıklarına göre sıralanır.

// 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
*/

Bu örnek, çizim için görece küçük bir veri kümesi kullanır. Daha büyük veri kümelerine göre performans geliştirmeleri denemek için vektörünün ilk boyutunu artırabilirsiniz.

Bu örnekte karma işlevi olarak lambda ifadesi kullanılır. Ayrıca std::hash sınıfının yerleşik uygulamalarından birini kullanabilir veya kendi uzmanlığınızı tanımlayabilirsiniz. Bu örnekte gösterildiği gibi özel karma işlev nesnesi de kullanabilirsiniz:

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

Karma işlevi bir integral türü döndürmelidir (std::is_integral::value olmalıdır true). Bu tam sayı türü türüne size_tdönüştürülebilir olmalıdır.

Sıralama Algoritması Seçme

Çoğu durumda, parallel_sort hız ve bellek performansı için en iyi dengeyi sağlar. Ancak, veri kümenizin boyutunu, kullanılabilir işlemci sayısını veya karşılaştırma işlevinizin parallel_buffered_sort karmaşıklığını artırdıkça veya parallel_radixsort daha iyi performans gösterebilirsiniz. Belirli bir senaryoda hangi sıralama algoritmasının kullanılacağını belirlemenin en iyi yolu, tipik verileri temsili bilgisayar yapılandırmaları altında sıralamanın ne kadar sürdüğünü denemek ve ölçmektir. Sıralama stratejisini seçtiğinizde aşağıdaki yönergeleri göz önünde bulundurun.

• Veri kümenizin boyutu. Bu belgede, küçük bir veri kümesi 1.000'den az öğe, orta büyüklükte bir veri kümesi 10.000 ile 100.000 arasında öğe içerir ve büyük bir veri kümesi 100.000'den fazla öğe içerir.

• Karşılaştırma işlevinizin veya karma işlevinizin gerçekleştirdiği çalışma miktarı.

• Kullanılabilir bilgi işlem kaynaklarının miktarı.

• Veri kümenizin özellikleri. Örneğin, bir algoritma zaten neredeyse sıralanmış veriler için iyi performans gösterebilir, ancak tamamen sıralanmamış veriler için iyi değildir.

• Öbek boyutu. İsteğe bağlı _Chunk_size bağımsız değişken, genel sıralamayı daha küçük iş birimlerine bölerken algoritmanın paralelden bir seri sıralama uygulamasına ne zaman geçiş olduğunu belirtir. Örneğin, 512 sağlarsanız, bir iş birimi 512 veya daha az öğe içerdiğinde algoritma seri uygulamaya geçer. Seri uygulama, verileri paralel olarak işlemek için gereken ek yükü ortadan kaldırdığından genel performansı iyileştirebilir.

Çok fazla sayıda kullanılabilir bilgi işlem kaynağınız olsa veya karşılaştırma işleviniz veya karma işleviniz görece büyük miktarda iş gerçekleştirse bile, küçük bir veri kümesini paralel olarak sıralamak faydalı olmayabilir. Küçük veri kümelerini sıralamak için std::sort işlevini kullanabilirsiniz. (parallel_sort ve parallel_buffered_sort veri kümesinden daha büyük bir öbek boyutu belirttiğinizde çağrısı sort yapın; ancak kilit parallel_buffered_sort çekişmesi veya bellek ayırma nedeniyle ek zaman alabilen O(N) alanı ayırmanız gerekir.)

Bellek tasarrufu yapmanız gerekiyorsa veya bellek ayırıcınız kilit çekişmesiyle karşılanıyorsa, orta boyutlu bir veri kümesini sıralamak için kullanın parallel_sort . parallel_sort ek alan gerektirmez; diğer algoritmalar O(N) alanı gerektirir.

Orta büyüklükteki veri kümelerini ve uygulamanız ek O(N) alanı gereksinimini karşıladığında sıralamak için kullanın parallel_buffered_sort . parallel_buffered_sort özellikle çok sayıda bilgi işlem kaynağınız veya pahalı bir karşılaştırma işleviniz ya da karma işleviniz olduğunda yararlı olabilir.

Büyük veri kümelerini ve uygulamanız ek O(N) alanı gereksinimini karşıladığında sıralamak için kullanın parallel_radixsort . parallel_radixsort özellikle eşdeğer karşılaştırma işlemi daha pahalı olduğunda veya her iki işlem de pahalı olduğunda yararlı olabilir.

Aşağıdaki örnek , , parallel_sortparallel_buffered_sortve parallel_radixsort performansını sortaynı büyük rastgele veri kümesiyle karşılaştırır.

// 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.
*/

Sıralama sırasında O(N) alanı ayırmanın kabul edilebilir olduğunu varsayan bu örnekte, parallel_radixsort bu bilgisayar yapılandırmasında bu veri kümesinde en iyi performansı gösterir.

[Üst]

İlgili Konular'a

Başvuru

parallel_for İşlevi

parallel_for_each İşlevi

parallel_invoke İşlevi

affinity_partitioner Sınıfı

auto_partitioner Sınıfı

simple_partitioner Sınıfı

static_partitioner Sınıfı

parallel_sort İşlevi

parallel_buffered_sort İşlevi

parallel_radixsort İşlevi