Paralel algoritmalar

Paralel desen kitaplığı (ppl) aynı anda veri koleksiyonunda işini gerçekleştirmek algoritma sağlar.Bu algoritmalar standart şablon kitaplığı (stl) tarafından sağlanan benzer.

Gelen varolan işlevsellikte eşzamanlılık çalışma zamanı paralel algoritmalar oluşur.Örneğin, concurrency::parallel_for algoritması kullanan bir concurrency::structured_task_group paralel döngü yinelemelerinin yapılacağı nesne.parallel_for Algoritması bölümleri verilen bilgi işlem kaynaklarını kullanılabilir sayısını en iyi ş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: Eşleme gerçekleştirmek ve paralel olarak azaltmak

• Bölümlendirme çalışma

• Paralel sıralama

  • Sıralama algoritmasını seçme

Parallel_for algoritması

Concurrency::parallel_for algoritması paralel olarak sürekli olarak aynı görevi gerçekleştirir.Bu görevlerin her birini bir yineleme değeri tarafından parametrelenmiştir.Bu algoritma, kaynakları bu döngü yinelemesi arasında paylaşmak istemiyorsanız bir Döngünün gövdesi olduğunda kullanışlıdır.

parallel_for Algoritması bölümler görevleri paralel yürütme için en iyi bir şekilde.Bu bir iş çalarak algoritma ve iş yüklerini dengesiz olduğunda bu bölümler dengelemek için çalarak aralığını kullanır.Çalışma zamanı cooperatively bir döngü yineleme engellediğinde, diğer iş parçacıkları veya işlemciler için geçerli iş parçacığı atanmış olan yineleme aralığını yeniden dağıtır.Benzer şekilde, bir iş parçacığı bir yineleme aralığını tamamladığında, o iş parçacığı için iş diğer iş parçacıklarından çalışma zamanı yeniden dağıtır.parallel_for Algoritmasını destekler de iç içe geçmiş paralellik.Paralel bir döngü paralel başka bir döngü içeriyorsa, çalışma zamanı işleme kaynaklarını verimli bir şekilde paralel yürütme için döngü gövdeleri arasında eşgüdümünü sağlar.

parallel_for Birkaç aşırı yüklü sürümlerini algoritması vardır.İlk sürümü bir başlangıç değeri, son değeri ve iş işlevi (bir lambda ifadesi, işlev nesne veya işlev işaretçisi) alır.İkinci Sürüm başlangıç değeri, son değeri, bir değer olarak adım ve iş işlevi alır.Bu işlevin ilk sürüm 1 adım değeri kullanır.Kalan sürümler belirtmenize olanak sağlayan partitioner nesneleri ele nasıl parallel_for iş parçacıkları arasında aralıkları partition.Partitioners bölümünde daha ayrıntılı olarak açıklanmıştır Bölümleme iş bu belgede.

Çoğu dönüştürebilirsiniz for kullanmak için döngüleri parallel_for.Ancak, parallel_for algoritma farklı dan for deyimi aşağıdaki yöntemlerle:

• parallel_for Algoritması parallel_for görevleri hazırlaması sırayla yürütmez.

• parallel_for Rasgele sonlandırma koşulları algoritmasını desteklemiyor.parallel_for Algoritması değişkeni geçerli değeri olduğunda durur az _Last.

• _Index_type Türü parametresi bir tamsayı türü olmalıdır.Bu tamsayı türü işaretli veya işaretsiz.

• Döngü yinelemesini ileriye doğru olması gerekir.parallel_for Algoritma türü bir özel durum atar std::invalid_argument , _Step 1'den küçük bir parametredir.

• Özel durum işleme mekanizması için parallel_for algoritma farklı olan bir for döngü.Aynı anda birden çok özel paralel döngüsünün gövdesine oluşursa çalýþma zamaný çağıran iş parçacığının istisnaları yalnızca biri yayar parallel_for.Ayrıca, bir döngü yineleme özel durum oluşturduğunda, çalışma zamanının toplam döngü hemen durdurmaz.Bunun yerine, döngü iptal edildi durumuna yerleştirilir ve çalışma zamanı henüz başlatılmamış herhangi bir görevi atar.Özel durum işleme ve paralel algoritmalar hakkında daha fazla bilgi için bkz: Özel durum işleme eşzamanlılık çalışma zamanında.

Ancak parallel_for rasgele sonlandırma koşulları algoritmasını desteklemiyor, tüm görevleri durdurmak için İptal'i kullanabilirsiniz.İptal etme hakkında daha fazla bilgi için bkz: ppl iptali.

[!NOT]

Yük Dengeleme ve iptali gibi özellikler için destek sonuçlarından döngüsünün gövdesi paralel olarak yürütülen yararları aşmak değil, zamanlama, özellikle ne zaman döngünün gövdesi görece küçük maliyetidir.Paralel döngü içinde bir partitioner kullanarak bu ek yükünü en aza indirebilirsiniz.Daha fazla bilgi için bkz: Bölümleme iş bu belgede daha sonra.

Örnek

Aşağıdaki örnek, temel yapısını gösterir parallel_for algoritması.Bu örnek, her değer aralığı [1, 5] paralel 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 çıktı üretir:

Çünkü parallel_for paralel her öğe üzerinde algoritması çalışır, değerlerini konsola yazdırılan sıraya göre değişir.

Kullanan tam bir örnek için parallel_for algoritması Bkz: Nasıl yapılır: bir parallel_for döngü yazmak.

Top

Parallel_for_each algoritması

Concurrency::parallel_for_each algoritması gibi paralel stl sağlananlardan yinelemeli bir kapsayıcı üzerinde görevleri gerçekleştirir.Aynı bölümleme mantığı kullanır, parallel_for algoritmasını kullanır.

parallel_for_each Algoritması stl benzer std::for_each dışında algoritma parallel_for_each algoritması görevleri aynı anda yürütür.Gibi diğer paralel algoritmalar, parallel_for_each görevleri belirli bir sırada yürütmez.

Ancak parallel_for_each algoritması çalışır hem ileriye doğru yineleyiciler hem de rasgele erişim yineleyiciler, rasgele erişim yineleyiciler ile onu daha iyi yapar.

Örnek

Aşağıdaki örnek, temel yapısını gösterir parallel_for_each algoritması.Bu örnek, her değeri konsola yazdırır bir std::array Paralel nesne.

// 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), begin(values), [](int value) {
      wstringstream ss;
      ss << value << L' ';
      wcout << ss.str();
   });
}

Bu örnek, aşağıdaki örnek çıktı üretir:

Çünkü parallel_for_each paralel her öğe üzerinde algoritması çalışır, değerlerini konsola yazdırılan sıraya göre değişir.

Kullanan tam bir örnek için parallel_for_each algoritması Bkz: Nasıl yapılır: bir parallel_for_each döngü yazmak.

Top

Parallel_invoke algoritması

Concurrency::parallel_invoke algoritması paralel olarak bir dizi görevi yürütür.Her görev bitmeden döndürmez.Bu algoritma, aynı anda çalıştırmak istediğinizde birkaç bağımsız görevler olduğunda kullanışlıdır.

parallel_invoke Algoritması bir dizi çalışma işlevleri (lambda İşlevler, işlev nesne veya işlev işaretçileri), parametre olarak alır.parallel_invoke Aşırı algoritması yüklü iki ve on parametreleri arasında gerçekleştirilecek.Her işlev için bünyesinde parallel_invoke sıfır parametreleri gerçekleştirmeniz gerekir.

Gibi diğer paralel algoritmalar, parallel_invoke görevleri belirli bir sırada yürütmez.Konu Görev paralellik (eşzamanlılık çalışma zamanı) açıklar nasıl parallel_invoke algoritması ilişkili görevler ve görev grupları için.

Örnek

Aşağıdaki örnek, temel yapısını gösterir parallel_invoke algoritması.Bu örnek aynı anda çağırır twice üç yerel değişkenler işlev ve konsola sonucu 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 çıktıyı üretir:

Kullanan tüm örnekleri için parallel_invoke algoritması Bkz: Nasıl yapılır: paralel sıralama rutin yazmak için parallel_invoke kullanın ve Nasıl yapılır: parallel_invoke paralel işlemleri yürütmek için kullanın..

Top

Parallel_transform ve parallel_reduce algoritmaları

Concurrency::parallel_transform ve concurrency::parallel_reduce algoritmaları stl algoritmaları paralel sürümleri olan std::transform ve std::accumulate, sırasıyla.Eşzamanlılık Çalışma zamanı sürümleri bunlar paralel olarak yürütmek için işlem sırası belirlenir değil dışında stl sürümleri gibi davranır.Paralel olarak işlenen performans ve ölçeklenebilirlik yararları elde etmek için büyük bir grup ile çalışırken bu algoritmalar kullanın.

Önemli
parallel_transform Ve parallel_reduce bu yineleyiciler kararlı bellek adresleri üretmek için algoritmalarını destekleyen yalnızca rasgele erişim, çift yönlü ve ileriye doğru yineleyiciler.Ayrıca, bu yineleyiciler olmayan üretmelidir-const m değerleri.

Parallel_transform algoritması

Kullanabileceğiniz parallel transform pek çok veri parallelization işlemleri gerçekleştirmek için kullanılan algoritma.Örneğin şunları yapabilirsiniz:

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

• Toplamak veya iki vektör arasında nokta ürün alabilir ve başka vektörler üzerinde sayısal hesaplamalar.

• 3-B ışın izleme, burada her yineleme işlenip gereken bir piksel için başvuran gerçekleştirin.

Çağırmak için kullanılan temel yapısı aşağıdaki örnekte gösterilmiştir parallel_transform algoritması.Bu örnek, her bir öğesi geçersiz bir std::vector iki yolla nesnesi.Birinci yol lambda ifadesi kullanır.İkinci yolu kullanan std::negate, dan türetilen 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>());
}

Uyarı
Bu örnek temel kullanımını gösterir parallel_transform.Önemli miktarda iş iş işlevini gerçekleştirmez çünkü bu örnekte önemli bir artış beklenmiyor.

parallel_transform Algoritması iki tekrar yüklemesi vardır.İlk aşırı bir tekli işlevi ve bir giriş aralığı alır.Tekli işlev bir bağımsız değişken, işlev nesne veya türetilmiş bir tür götüren lambda ifadesi olabilir unary_function.İki giriş aralığı ve ikili işlevi ikinci aşırı alır.İkili işlevi iki bağımsız değişken, işlev nesne veya türetilmiş bir tür götüren lambda ifadesi olabilir std::binary_function.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>());

Önemli
Çıktısı için sağladığınız Yineleyici parallel_transform giriş Yineleyici tamamen üst üste veya hiç çakışma yok.Giriş ve çıkış yineleyiciler kısmen üst üste gelirse bu algoritma davranışını belirtilmemiş.

Parallel_reduce algoritması

parallel_reduce Algoritması, sıralı ilişkilendirilebilir özelliği karşılamak işlemler olduğunda yararlıdır.(Bu algoritma yer değiştirebilme özelliğine gerektirmez.) Aşağıda bazı ile gerçekleştirebileceğiniz işlemler parallel_reduce:

• Bir matris oluşturmak için matrisler dizileri ile çarpın.

• Bir vektör vektör üretmek için matrisler bir dizi tarafından çarpın.

• Dizelerden oluşan bir dizi uzunluğunu hesaplamak.

• Bir öğe dizeleri gibi öğeleri listesini birleştirin.

Aşağıdaki basit örnekte nasıl kullanılacağını gösterir parallel_reduce dizeler dizisi bir dize halinde birleştirmek algoritması.Örnekler için olduğu gibi parallel_transform, performans artışı değil bu basit örnekte bekleniyor.

// 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;
    words.push_back(L"Lorem ");
    words.push_back(L"ipsum ");
    words.push_back(L"dolor ");
    words.push_back(L"sit ");
    words.push_back(L"amet, ");
    words.push_back(L"consectetur ");
    words.push_back(L"adipiscing ");
    words.push_back(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, düşünebilirsiniz parallel_reduce kullanımı için kestirme olarak parallel_for_each algoritması ile birlikte concurrency::combinable sınıf.

Örnek: Eşleme gerçekleştirmek ve paralel olarak azaltmak

A Harita işlem bir dizideki her değer için bir işlev uygulanır.A azaltmak işlem içine bir değer bir dizi öğelerini birleştirir.Standart Şablon kitaplığı (stl) kullanabilirsiniz std::transformstd::accumulate map gerçekleştirmek ve işlemlerini azaltmak için sınıflar. Ancak, birçok sorunu için kullanabilirsiniz parallel_transform paralel olarak eşleme işlemi gerçekleştirmek için kullanılan algoritma ve parallel_reduce algoritmasını paralel olarak küçültme işlemi.

Aşağıdaki örnek, paralel ve seri olarak asal sayıların toplamını hesaplamak için geçen süre karşılaştırır.Harita aşama asal olmayan değerler 0 ve küçültme aşama toplamlar değerleri dönüştürür.

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

Harita gerçekleştirir ve paralel işlem azaltma başka bir örnek için bkz: Nasıl yapılır: harita gerçekleştirmek ve paralel işlemleri azaltma.

Top

Bölümlendirme çalışma

Bir veri kaynağı üzerinde bir işlem parallelize için için önemli bir adım olan bölüm kaynak aynı anda birden çok iş parçacığı tarafından erişilebilecek birden fazla bölümlere.Bir partitioner paralel bir algoritma nasıl iş parçacıkları arasında aralıkları bölümleme belirtir.Bu belgede daha önce açıklandığı gibi bir başlangıç iş yükü oluşturur ve daha sonra bir iş kurtulun ve iş yükleri dengesiz olduğunda bu bölümler dengelemek için çalarak aralığı kullanan bir mekanizma bölümleme varsayılan ppl kullanır.Örneğin, bir döngü yinelemeyi yineleme aralığını tamamladığında, o iş parçacığı için iş diğer iş parçacıklarından çalışma zamanı yeniden dağıtır.Ancak, bazı senaryolarda, daha iyi sorununuz için uygun olan farklı bir bölümleme düzeneğini belirtmek isteyebilirsiniz.

parallel_for, parallel_for_each, Ve parallel_transform algoritmaları sağlayan ek bir parametre aşırı yüklü sürümlerini _Partitioner.Bu parametre, iş ayıran partitioner türü tanımlar.ppl tanımlayan partitioners türleri şunlardır:

• concurrency::affinity_partitioner
  Sabit sayıda aralıkları (genellikle döngü üzerinde çalışmak kullanılabilir işçi iş parçacığı sayısı) içine böler çalışır.Bu partitioner türü benzer static_partitioner, ancak önbellek benzeşimi by the way için iş parçacıkları, eşler aralıkları artırır.Partitioner bu tür bir döngü aynı veri kümesinin birden çok kez (örneğin bir döngü içinde döngü) üzerinden yürütülür ve veri önbelleğinde uyan performansı artırabilir.Bu partitioner tamamen iptali içinde yer almaz.Bu da İşbirlikçi engelleme semantiği kullanmaz ve ileriye doğru bir bağımlılığa sahip paralel döngüleri ile kullanılamaz.

• concurrency::auto_partitioner
  Bir ilk sayı aralıkları (genellikle döngü üzerinde çalışmak kullanılabilir işçi iş parçacığı sayısı) içine böler çalışır.Geçen aşırı yüklü bir paralel algoritma çağırmayın, varsayılan olarak bu tür çalışma zamanı kullanır bir _Partitioner parametresi.Her aralık alt aralıkları işlemez ayrılabilir ve böylece etkinleştirir gerçekleşmesi için Yük Dengeleme.Bir dizi çalışma tamamlandıktan sonra çalışma zamanı alt aralıkları işlemez o iş parçacığı için iş diğer iş parçacıklarından yeniden dağıtır.İş yükünüzü diğer kategorilerden birini altında düşmüyor veya iptali veya işbirlikçi engellenmesi için tam destek gerektiren bu partitioner kullanın.

• concurrency::simple_partitioner
  Her aralığı tarafından verilen öbek boyutunu belirtilen yineleme sayısı en az sahip olduğunu böler aralıkları çalışır.Partitioner bu tür Yük Dengelemesi'nde yer aldığı; Ancak, çalışma zamanı alt aralıkları işlemez aralıkları bölünmez.Her çalışan için çalışma zamanı iptali denetler ve sonra Yük dengelemesi yapar _Chunk_size yineleme tamamlayın.

• concurrency::static_partitioner
  Sabit sayıda aralıkları (genellikle döngü üzerinde çalışmak kullanılabilir işçi iş parçacığı sayısı) içine böler çalışır.İş çalarak kullanmaz ve bu nedenle daha az yüke sahiptir çünkü bu partitioner türü performansı artırabilir.Sabit ve tek tip çalışma miktarını paralel bir döngünün her yineleme yapar ve iptali için destek gerektirmez veya işbirlikçi engelleme iletmek partitioner bu türü kullanın.

Uyarı
parallel_for_each Ve parallel_transform algoritmaları kullanan rasgele erişim yineleyiciler kapsayıcıları desteği (gibi std::vector) statik, basit ve benzeşme partitioners için.Çift yönlü ve ileriye doğru yineleyiciler kapsayıcıları kullanımını bir derleme zamanı hatası üretir.Varsayılan partitioner auto_partitioner, bu Yineleyici türlerinin üçü destekler.

Bu partitioners dışında aynı şekilde, tipik olarak kullanılan affinity_partitioner.Partitioner türlerinin çoğu durumunu saklamaz ve çalışma zamanı tarafından değiştirilmez.Bu nedenle aşağıdaki örnekte gösterildiği gibi arama sitesinde bu partitioner nesneleri 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, geçmesi gereken bir affinity_partitioner nesnesi olmayan bir olarak-const, l-değeri gelecekteki döngüleri yeniden kullanmak için durum algoritması depolayabileceğiniz başvuru.Aşağıdaki örnek, paralel olarak birden çok kez bir veri kümesi üzerinde aynı işlemi gerçekleştiren bir temel uygulama gösterir.Kullanımı, affinity_partitioner dizi önbelleğinde sığdırmak muhtemel olduğundan, performansı artırabilir.

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

using namespace concurrency;

int wmain()
{    
    // Create an arry 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);
    }
}

Uyarı
Dikkatli kullanmak için üzerinde işbirlikçi engelleme semantiği kullanır varolan kodu değiştirdiğinizde static_partitioner veya affinity_partitioner.Bu partitioner türleri aralığı çalarak veya Yük Dengeleme kullanmayın ve bu nedenle uygulamanızın davranışını değiştirebilir.

Denemeler ve işlemleri temsilcisi yükleri ve bilgisayar yapılandırmaları altında tamamlamak için ne kadar sürer ölçmek için verilen herhangi bir senaryoda bir partitioner kullanılıp kullanılmayacağını belirlemek için en iyi yolu değil.Örneğin, statik bölümleme yalnızca birkaç çekirdeği olan birden çok çekirdekli bir bilgisayarda önemli speedup sağlayabilir, ancak nispeten daha çok sayıda çekirdeği olan bilgisayarlarda yavaşlamaları neden olabilir.

Top

Paralel sıralama

ppl üç sıralama algoritmaları sağlar: concurrency::parallel_sort, concurrency::parallel_buffered_sort, ve concurrency::parallel_radixsort.Paralel olarak sıralanmış yararlı bir veri kümesi varsa, sıralama algoritmaları yararlı olurlar.Özellikle, paralel olarak sıralama büyük bir DataSet nesnesini varsa veya verilerinizi sıralamak için bir hesaplama açısından pahalı karşılaştırma işlemi kullandığınızda yararlıdır.Bu algoritmalar her yerinde öğeleri sıralar.

parallel_sort Ve parallel_buffered_sort algoritmaları olan iki karşılaştırma tabanlı algoritmalar.Diğer bir deyişle, bunlar öğeleri değeriyle karşılaştırın.parallel_sort Algoritması hiçbir ek bellek gereksinimlerine sahiptir ve genel amaçlı sıralama için uygundur.parallel_buffered_sort Algoritması gerçekleştirebilir daha iyi parallel_sort, ancak gerektirir O(N) alan.

parallel_radixsort Algoritması karma tabanlı.Diğer bir deyişle, öğeleri sıralamak için tamsayı anahtarları kullanır.Bu algoritma, tuşlarını kullanarak doğrudan karşılaştırmalar kullanmak yerine bir öğenin hedef hesaplayabilir.Gibi parallel_buffered_sort, bu algoritma gerektiren O(N) alan.

Aşağıdaki tablo üç paralel sıralama algoritmaları önemli özelliklerini özetler.

Algoritma	Tanımlama	Sıralama mekanizması	Sıralama kararlılık	Bellek gereksinimleri	Zaman karmaşıklık	Yineleyici erişim
parallel_sort	Genel amaçlı karşılaştırma tabanlı sıralama.	(Artan karşılaştırma tabanlı)	Kararsız	None	O((N/P)log(N/P) + 2N((P-1)/P))	Rasgele
parallel_buffered_sort	o(n) alanı gerektiren daha hızlı genel amaçlı karşılaştırma tabanlı sıralama.	(Artan karşılaştırma tabanlı)	Kararsız	Ek O(N) alanı	O((N/P)log(N))	Rasgele
parallel_radixsort	o(n) alanı gerektiren tamsayı anahtar tabanlı sıralama.	Karma tabanlı	Kararlı	Ek O(N) alanı	O(N/P)	Rasgele

Aşağıda üç paralel sıralama algoritmaları önemli özelliklerini daha grafiksel olarak gösterilmiştir.

Bu paralel algoritmalar sıralama iptalini ve özel durum işleme kurallarını izleyin.Eşzamanlılık Çalışma zamanı, özel durum işleme ve iptal etme hakkında daha fazla bilgi için bkz: Paralel algoritmalar iptal etme ve Özel durum işleme eşzamanlılık çalışma zamanında.

İpucu

Bu paralel algoritmalar sıralama taşıma semantiğini desteklemek.Takas işlemleri daha verimli bir şekilde gerçekleşmesini sağlamak için bir taşıma atama işleci tanımlayabilirsiniz.Taşıma semantik ve taşıma atama işleci hakkında daha fazla bilgi için bkz: Rvalue başvuru Bildiricisi: & &, ve Nasıl yapılır: taşıma kurucu yazma.Taşıma atama işlecini veya takas işlevini belirtmezseniz, kopya oluşturucusuna sıralama algoritmaları kullanır.

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

// 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 örnek özel karşılaştırma işlevi sağlamak nasıl gösterir.Kullandığı std::complex::real sıralama yöntemi std::complex <double> artan değerler.

// 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 örnek için karma işlevi sağlamak nasıl gösterir parallel_radixsort algoritması.Bu örnek, 3B noktaları sıralar.Puan kendi uzaklıkta bir referans noktası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
*/

Gösterim amacıyla bu örnek görece küçük bir veri kümesi kullanır.Vektör büyük veri kümelerinin performans iyileştirmeleri ile denemek için başlangıç boyutunu artırabilirsiniz.

Bu örnek lambda ifadesi karma işlevi kullanır.Yerleşik uygulamaları birini de kullanabilirsiniz std::hash sınıf veya kendi uzmanlığı tanımlayın.Bu örnekte gösterildiği gibi özel karma işlevi nesne 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, tamsayı türü döndürmesi gerekir (std::is_integral::value olması true).Bu tamsayı türü yazın dönüştürülebilir size_t.

Sıralama algoritmasını seçme

Çoğu durumda, parallel_sort hız ve bellek performansını en iyi dengeyi sağlar.Ancak, siz artırmak veri kümenizi, kullanılabilir işlemci sayısına veya karşılaştırma işlevinin, karmaşıklık boyutunu parallel_buffered_sort veya parallel_radixsort daha iyi gerçekleştirebilir.Denemeler ve temsilcisi bilgisayar yapılandırmaları altında tipik verileri sıralamak için ne kadar sürer ölçmek için verilen herhangi bir senaryoda kullanmak için hangi sıralama algoritması belirlemenin en iyi yolu değil.Sıralama bir strateji seçtiğinizde aşağıdaki kuralları göz önünde bulundurun.

• Veri kümenizi boyutu.Bu belgede, bir küçük veri kümesi 1000'den az öğe içeren bir Orta veri kümesi içeren öğeleri 10.000 ile 100.000 arasında ve bir büyük dataset, 000'den fazla öğe içerir.

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

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

• Veri kümenizi karakteristikleri.Örneğin, iyi neredeyse zaten sıralanmış veri, ancak aynı zamanda tamamen sıralı olmayan veriler için bir algoritma gerçekleştirebilir.

• Öbek boyutu.İsteğe bağlı _Chunk_size bağımsız değişkeni belirtir, Genel sıralama çalışmanın daha küçük birimlere subdivides olarak ne zaman algoritması seri sıralama uygulamasına paralel gelen geçer.Örneğin, 512 sağlarsanız, 512 ya da daha az öğe bir iş birimi içerdiğinde, algoritma seri uygulamasına geçer.Paralel işlem verileri için gereken ek yükü ortadan kaldırdığından seri uygulama genel performansı artırabilir.

Küçük bir dataset paralel, hatta çok sayıda bilgi işlem kaynaklarını kullanılabilir olması veya göreceli olarak büyük miktarda iş karşılaştırma işlevi veya karma işlev gerçekleştirir sıralamak için faydalı olabilir.Kullanabileceğiniz std::sort küçük DataSet'ler sıralamak için işlev.(parallel_sort ve parallel_buffered_sort çağrısı sort ; dataset'den daha büyük bir öbek boyutunu belirttiğinizde, Ancak, parallel_buffered_sort tahsis etmek zorunda O(N) boş alan nedeniyle kilit çakışması veya bellek ayırma için ek zaman alabilir.)

Kilit çakışması belleğini korumak gerekir ya da kendi bellek ayırıcısı, kullanın parallel_sort orta ölçekli veri kümesini sıralamak için.parallel_sortek boşluk gerektirir; diğer algoritmalar gerektiren O(N) alan.

Kullanım parallel_buffered_sort orta ölçekli veri kümeleri ve ne zaman uygulamanıza ek karşılayan sıralamak için O(N) alanı gereksinimi.parallel_buffered_sortçok sayıda bilgi işlem kaynaklarını veya pahalı karşılaştırma işlevi veya karma işlevi varsa, özellikle yararlı olabilir.

Kullanım parallel_radixsort büyük veri kümeleri ve ne zaman uygulamanıza ek karşılayan sıralamak için O(N) alanı gereksinimi.parallel_radixsorteşdeğer karşılaştırma işlemi daha pahalı olduğunda veya iki işlem de pahalı olduğunda özellikle yararlı olabilir.

Uyarı
İyi karma işlevi uygulama dataset aralığı ve dataset nesnesindeki her öğe için karşılık gelen bir işaretsiz değer nasıl dönüştürüldüğünü bilmeniz gerekir.Karma işlemi işaretsiz değerler üzerinde çalıştığı için farklı bir sıralama strateji imzasız karma değerlerini vermediyse göz önünde bulundurun.

Aşağıdaki örnek performansını karşılaştırır sort, parallel_sort, parallel_buffered_sort, ve parallel_radixsort karşı aynı sayıda rasgele veri.

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

Bu örnekte, varsayar tahsis etmek için kabul edilebilir olduğunu O(N) alan sıralama sırasında parallel_radixsort en iyi bu dataset nesnesinde bu bilgisayar yapılandırması gerçekleştirir.

Top

İlgili Konular

Başlık	Tanımlama
Nasıl yapılır: bir parallel_for döngü yazmak	Nasıl kullanılacağını gösterir parallel_for matris çarpma işlemi gerçekleştirmek için kullanılan algoritma.
Nasıl yapılır: bir parallel_for_each döngü yazmak	Nasıl kullanılacağını gösterir parallel_for_each algoritması asal sayıların adedini hesaplamak için bir std::array Paralel nesne.
Nasıl yapılır: paralel sıralama rutin yazmak için parallel_invoke kullanın	Nasıl kullanılacağını gösterir parallel_invoke bitonic sıralama algoritması performansını artırmak için algoritma.
Nasıl yapılır: parallel_invoke paralel işlemleri yürütmek için kullanın.	Nasıl kullanılacağını gösterir parallel_invoke bir paylaşılan veri kaynağı üzerinde birden çok işlemi gerçekleştiren bir program performansını artırmak için algoritma.
Nasıl yapılır: harita gerçekleştirmek ve paralel işlemleri azaltma	Nasıl kullanılacağını gösterir parallel_transform ve parallel_reduce dosyalarında sözcük oluşumlarını sayar işlem azaltmak ve harita gerçekleştirmek için algoritmalar.
Paralel Desenler kitaplığının (ppl)	Ölçeklenebilirlik ve kolay-eş zamanlı uygulamalar geliştirmek için kullanımı yükseltir kesinlik temelli bir programlama modeli sağlar ppl açıklar.
ppl iptali	İptal ppl, paralel iş iptal etmek nasıl ve ne zaman bir görev grubu iptal edildi belirleme rolünü açıklar.
Özel durum işleme eşzamanlılık çalışma zamanında	Eşzamanlılık Çalışma zamanı özel durum rolünü açıklar.

Reference

parallel_for işlevi

parallel_for_each işlevi

parallel_invoke işlevi

affinity_partitioner sınıfı

auto_partitioner sınıfı

simple_partitioner sınıfı

static_partitioner sınıfı

parallel_sort işlevi

parallel_buffered_sort işlevi

parallel_radixsort işlevi