2013-07-30 32 views
10

C++ ve D'de paralellik karşılaştırması yaptığım bir deney. Aynı tasarımı kullanarak her iki dilde de bir algoritmayı (ağlarda topluluk algılaması için paralel etiket yayılma şeması) uyguladım: Bir paralel yineleyici bir tutamaç işlevini (normalde bir kapanır) ve grafikteki her düğüm için uygular. Burada Bu paralel kod neden D ölçeğinde çok kötü?

kullanılarak uygulanan D yineleyici olduğu taskPool std.parallelism den:

/** 
* Iterate in parallel over all nodes of the graph and call handler (lambda closure). 
*/ 
void parallelForNodes(F)(F handle) { 
    foreach (node v; taskPool.parallel(std.range.iota(z))) { 
     // call here 
     handle(v); 
    } 
} 

Bu geçirilir kolu fonksiyonudur:

auto propagateLabels = (node v){ 
     if (active[v] && (G.degree(v) > 0)) { 
      integer[label] labelCounts; 

      G.forNeighborsOf(v, (node w) { 
       label lw = labels[w]; 
       labelCounts[lw] += 1; // add weight of edge {v, w} 
      }); 

      // get dominant label 
      label dominant; 
      integer lcmax = 0; 
      foreach (label l, integer lc; labelCounts) { 
       if (lc > lcmax) { 
        dominant = l; 
        lcmax = lc; 
       } 
      } 

     if (labels[v] != dominant) { // UPDATE 
      labels[v] = dominant; 
      nUpdated += 1; // TODO: atomic update? 
      G.forNeighborsOf(v, (node u) { 
       active[u] = 1; 
      }); 
     } else { 
      active[v] = 0; 
     } 

     } 
    }; 

C++ 11 uygulaması hemen hemen aynıdır ancak paralelleştirme için OpenMP kullanır. Peki, ölçekleme denemeleri ne gösteriyor?

scaling

Burada da parçacığı sayısını iki katına çıkarır ve çalışma süresi ölçüm sırasında giriş grafik boyutunu iki katına, zayıf ölçekleme inceleyin. İdeal olan doğru bir çizgi olurdu, ama elbette paralellik için bir miktar yük var. D programın iş parçacığı sayısını ayarlamak için ana işlevimde defaultPoolThreads(nThreads) kullanın. C++ için eğri iyi görünüyor, ancak D için eğri şaşırtıcı derecede kötü görünüyor. Yanlış bir şey yapıyorum w.r.t. D paralellik, ya da bu paralel D programlarının ölçeklenebilirliği üzerinde olumsuz yansıyor mu?

p.s. derleyici bayraklarını D

: C++ için rdmd -release -O -inline -noboundscheck

: -std=c++11 -fopenmp -O3 -DNDEBUG

PPS. Bir şey Ge uygulama sırayla daha paralel yavaştır, çünkü gerçekten yanlış olmalı:

enter image description here

KÖİ'ler. meraklı için burayı Mercurial klon URL'ler hem uygulamaları içindir:

+0

Eğer openmp olmadan yapsanız performans nasıl görünür? – greatwolf

+0

Kontrol etmeden, dmd derleyici şu anda openmp özelliğini destekliyor gibi görünmüyor. Bir sürüm openmp kullanıyorsa ve başka bir sürüm kullanmıyorsa, elmaları-elmaları benim için bir karşılaştırma gibi görünmüyor. – greatwolf

+0

@greatwolf Seni yanlış anladığım sürece, noktayı kaçırdığına inanıyorum. D OpenMP'ye sahip değildir, ancak benzer paralel yapılar sağlayan "std.parallelism" kütüphanesine sahiptir. Aslında, D programı çalışırken birçok çekirdek kullanır. – clstaudt

cevap

8

, ancak kodunuzun iş parçacığı güvenli olmadığı anlaşılıyor, bu da algoritmanın gereğinden fazla yineleme çalıştırmasına neden oluyor.

Ben PLP.run sonuna bu ekledi:

writeln(nIterations); 

10 iş parçacığı 100 parçacığı nIterations = 90 Gördüğünüz gibi Yani

ile nIterations = 34
ile nIterations = 19
iplik 1 ile, artık değil sürüyor std.parallelism ile ilgili bazı sorunlar nedeniyle, ancak daha fazla iş yaptığından dolayı.

Neden kodunuz iş parçacığı güvenli değil?

Eğer paralel olarak çalışan fonksiyon labels, nUpdated ve active için senkronlaştınlmamış erişim, paylaştı hangi propagateLabels olduğunu. Bunun ne tür garip davranışlar yaptığını kim bilir, ama iyi olamaz.

Profil oluşturmaya başlamadan önce, iş parçacığı için algoritmayı düzeltmeniz gerekir.

+1

İyi gözlem. Benim için ilginç olan soru şudur: Niçin bu davranış, neredeyse aynı C++ uygulamasından D'de çok farklı? Konuların "label", "active" ve "nUpdated" öğelerini paylaştığının farkındayım. Bu durum, sorun olmadığı C++/OpenMP uygulaması için aynıdır. – clstaudt

+1

Ne yazık ki OpenMP'ye aşina değilim, ancak işlerin nasıl sıraya konulduğu std.parallelism'den farklı olabilir, bu yüzden OpenMP çözümü bir şeyleri yürütme biçimiyle "sadece çalışır". –

5

Peter Alexander'ın belirttiği gibi, algoritmanız iş parçacığı güvensiz gibi görünüyor. İş parçacığı güvenli hale getirmek için, farklı iş parçacıklarında aynı anda veya tanımlanmamış bir sırada gerçekleşebilecek olaylar arasındaki tüm veri bağımlılıkları ortadan kaldırmanız gerekir. Bunu yapmanın bir yolu, WorkerLocalStorage (std.parallelism'de sağlanmıştır) kullanarak bazı halleri çoğaltmak ve muhtemelen algoritmanızın sonunda sonuçları nispeten ucuz bir döngüde birleştirmektir. Bu aynen uygulayacak süreci bir azalma olarak algoritma yazma ve ağır işleri yapmak (muhtemelen std.algorithm.map veya std.parallelism.map ile birlikte) std.parallelism.reduce kullanarak otomatik hale getirilebilir Bazı durumlarda

.

İlgili konular