OpenMP: derinlemesine ilk arama için iyi stratejiler

Question

Kapalı Knight's tours için kaba kuvvet araması yapan bir C++ programı yazıyorum. Kod here'dur.

Bunu OpenMP kullanarak paralel hale getirmek istiyorum. Benim problemim bunu yeterli bir paralellik oluşturan bir şekilde yapmak. Şu anda benim kod the relevant portion bu

#pragma omp parallel for reduction(+:count) if (depth==4) 
    for (size_t i=0;i<g.neighbours[last].size();i++){ 
    auto n = g.neighbours[last][i]; 
    // See if n can be used to extend or complete the tour 

if (depth==4) benziyor emin Çok fazla paralel görevler oluşturulan verildiğini ancak yeterince meşgul tüm işlemcileri tutmak için oluşturulan diğer taraftan yapmak benim girişimdir. depth==2 ayarı, programın çalışma zamanını değiştirmez.

Bu, çalışmıyor gibi görünmüyor. 3x12'lik bir sorun için, çift çekirdekli işlemcideki OpenMP sürümü tarafından tüketilen toplam CPU zamanı yaklaşık 130 saniyedir, OpenMP olmayan tek bir iş parçacığı sürümü ise yaklaşık 40s CPU süresine sahiptir.

OpenMP'nin ne kadar iyi kullanıldığına veya bu sorunun neden uygun olmadığına ilişkin önerileri takdir ediyorum.

GÜNCELLEME: @Zulan'a teşekkürler. Çok daha hızlı bir sıralı performansa ve iyi paralelleştirmeye sahip OpenMP görevlerini kullanarak bir newer version var.

Answer 1

Birincisi, perf kullanarak, uygulamanız kendi zaman harcıyor nerede bir süper-hızlı bir göz atalım:

perf record ./knights_tour_omp 3 12 
perf report 

# Overhead Command   Shared Object  Symbol                       
# ........ ............... ................... ................................................................................................. 
# 
    53.29% knights_tour_om libc-2.19.so   [.] malloc                      
    23.16% knights_tour_om libc-2.19.so   [.] _int_free                      
    10.31% knights_tour_om libc-2.19.so   [.] _int_malloc                     
    4.78% knights_tour_om knights_tour_omp  [.] _Z13continue_tourIZ4mainEUlRKSt6vectorIiSaIiEEE_EmRK5GraphS4_RKS0_IcSaIcEEiiRT_.constprop.119 
    2.64% knights_tour_om libc-2.19.so   [.] __memmove_ssse3_back                   
    1.48% knights_tour_om libc-2.19.so   [.] malloc_consolidate                 

Uygulama her zaman tahsis ve bellek boşaltma hepsi harcamaktadır. malloc is is not fully locked'un bazı raporları olsa da, güzel bir şekilde paralellik göstermiyor.

Bunun, her yineleme için visited ve path vektörlerinin kopyalanmasından kaynaklandığını anlamak için daha fazla araştırmaya gerek yoktur.

visited[n] = 1; 
path.emplace_back(n); 
count += continue_tour(g, path, visited, depth+1,remain-1, cb); 
visited[n] = 0; 
path.pop_back(); 

Ancak paralel döngü, her iş parçacığı için çalışan kopyalarını yapmak gerekir: Neyse DFS mutlaka, bunu yapmak gerekmez Eğer devlet yeniden kullanmak ve geri yükleyebilirsiniz olduğunu, güzel bir özelliği vardır Bu yüzden orijinal davayla bu dava için ayrı bir yol yapmalısınız.

Bu küçük değişiklik zaten seri çalışma süresini 22 saniyeden 2.65 saniyeye indiriyor. Ayrıca 2 dişli ile 2.0 s'ye iner. Bir hızlanma var, ama o kadar iyi değil - neden? Bunu göstermek için 4 iplik kullandım (yeterince büyük bir sistemde). Uygulamanın, Vampir'da gösterilen score-p ile kaydedilen zaman içinde yürütülmesi.

Kırmızı

fiili çalışma, mavi ipler boşta olan, yani bir örtük bariyer olmasıdır. Her zaman 3 veya 1 aktif iplik var gibi görünüyor. Nedeni basit: Gemideki pozisyonun çoğu 4 ya da 2 komşuya sahip, ancak bunlardan biri zaten ziyaret edildi, böylece bu döngü yinelemesi anında tamamlandı. Yani asıl iş, ya döngüde 3 ya da 1 iterasyondadır. Bu 2 iş parçacığı için özellikle kötü bir eşleşme. 3 iş parçacığı ile çalışma zamanı aşağı doğru 1,7 s olarak gider. Not: Tüm zamanlar E5-2690 @ 2.90 GHz'de gcc 5.3 ile turbo yok. Çalışma sürelerindeki varyansı telafi etmek için hiçbir özen gösterilmemiştir.

Tek bir döngünün bu sorun için çok kötü bir paralellik sergilediğini düşünürsek, paralel döngüleri yerleştirmek isteyebilirsiniz. Denemenizi tavsiye ederim ama bunun iyi sonuç vermeyeceğini düşünüyorum. Görevlerin bu bağlamda iyi çalıştığını düşünürdüm, çünkü görevler başka görevler doğurabilir. Böylece, her bir özyinelemeyi bir görev olarak oluşturabilir ve OMP çalışma zamanının iyi bir çizelgeleme yapmasına izin verebilirsiniz. Ancak, belirli bir depth ile sınırlandırdığınızdan emin olun, böylece görevler çok kısa olmaz.

Araçların kullanılmasının önemini vurgulamak istiyorum: Performans sorunlarını analiz aracı olmadan değerlendirmek, hata ayıklayıcı olmadan hataları bulmak gibidir. perf Linux için halihazırda mevcuttur ve kullanımı oldukça basit olan basit şeklidir. Yine de çok güçlüdür (gelişmiş kullanımda bazı tuzaklar olabilir).

Ek bir açıklama: OpenMP ile farklı derleyicileri denemek için çoğu zaman değerlidir. Örneğin, (sabit) görev koduyla, gcc artık 4 iş parçacığının ötesine ölçeklenmez; intel derleyici/omp çalışma zamanı, 24 iş parçacığına kadar bir hızlanma sağlar.