CPU zamanının yığınının (>% 95) bir kısmının N ~ 200 siparişi için kötü (ve kaçınılmaz) O (N^2) etkileşiminin hesaplanması için harcanan bazı bilimsel C++ kodlarını paralel hale getirmeye (OpenMP) çalışıyorum farklı parçacıklar. Bu hesaplama 1e10 zaman adımı için tekrarlanır. OpenMP ile çeşitli ek yapılandırmalar denedim, her biri ek çekirdekler eklendikçe zayıf ölçekleme ile bazı kenar boşlukları (en azından büyüklük derecesi) ile seri koddan daha yavaş.OpenMP kodu, seri bellek veya iş parçacığı başındaki darboğazdan daha mı yavaş?
Aşağıda, ilgili kodun temsili bir veri hiyerarşisi Tree->Branch->Leaf ile ilgili bir çizimi görülmektedir. Her bir Leaf nesnesi, diğer şeylerin yanı sıra mevcut ve önceki üç zaman adımı için kendi konumunu ve hızlarını depolar. Her Branch, Leaf nesnesinin bir koleksiyonunu saklar ve her Tree, Branch nesnesinin bir koleksiyonunu depolar. Bu veri yapısı, her zaman adımında (aylarca mükemmel hale getirilmiş) gerçekleştirilmesi gereken karmaşık ancak daha az CPU-yoğun hesaplamalar için çok iyi çalışır.
#include <omp.h>
#pragma omp parallel num_threads(16) // also tried 2, 4 etc - little difference - hoping that placing this line here spawns the thread pool at the onset rather than at every step
{
while(i < t){
#pragma omp master
{
/* do other calculations on single core, output etc. */
Tree.PreProcessing()
/* PreProcessing can drastically change data for certain conditions, but only at 3 or 4 of the 1e10 time steps */
Tree.Output()
}
#pragma omp barrier
#pragma omp for schedule(static) nowait
for(int k=0; k < size; k++){
/* do O(N^2) calc that requires position of all other leaves */
Tree.CalculateInteraction(Branch[k])
}
/* return to single core to finish time step */
#pragma omp master
{
/* iterate forwards */
Tree.PropagatePositions()
i++
}
#pragma omp barrier
}
Çok kısaca, CPU-domuz fonksiyonu yapar:
void Tree::CalculateInteraction(Leaf* A){
// for all branches B in tree{
// for all leaves Q in B{
if(condition between A and Q){skip}
else{
// find displacement D of A and Q
// find displacement L of A and "A-1"
// take cross product of the two displacements
// add the cross-product to the velocity of leaf A
for(int j(0); j!=3; j++){
A->Vel[j] += constant * (D_cross_L)[j];
}
Sorum performansının bu sakat OpenMP iplik yönetimi havai egemen nedeniyle, ya da ister bir durum olup olmadığıdır Paralellik düşünülmeden tasarlanmış bir veri hiyerarşisi mi?
Her adımın, seriye göre paralel olarak önemli ölçüde daha uzun olması için zamanlandığına dikkat etmeliyim; bu, bazı başlangıç ek yükü sorunu değildir; iki versiyon, yaklaşık 10 saat süren ve en sonunda 30 saat sürebilen seri hesaplara (genellikle 2 kat hızlanmanın çok faydalı olacağı) hesaplamalar için test edilmiştir. Ayrıca, -fopenmp -march=native -m64 -mfpmath=sse -Ofast -funroll-loops ile g ++ 5.2.0 kullanıyorum bilmek değer olabilir.
OpenMP'ye yeni geldim, bu yüzden herhangi bir ipucu büyük bir memnuniyetle karşılanacaktır, lütfen açıklığa kavuşturulması gereken bir şey varsa lütfen bana bildirin.
Ağaç yapısı nasıl tam olarak düzenlenir? bitişik bir dizideki veya bağlantılı bir listede bulunan alt düğümler (diğer bir deyişle ana düğümler yalnızca ilk alt düğümün ve her alt düğümün kız kardeşine göstericidir)? Paralel octtrees (N-body simülasyonları ve SPH için) ile çok çalışıyorum, ama her zaman mükemmel ölçekleme buluyorum. Ayrıca, N (N^2) için neye ihtiyacınız olduğunu merak ediyorum - bu genellikle O (NlnN) veya O (N) içinde ağaç veya FMM ile yaklaşık olarak tahmin edilir. – Walter
@Walter Yapraklar, şube boyunca önceki ve sonraki yapraklara iki kez bağlı bir listede saklanır (bellekte 'herhangi bir yer' bulunabilir). Bir ağaç, bu özel tür hesaplamalar için standart bir seçenektir (süper akışkan helyumun vorteks filaman modeli, bakınız örneğin [bu gözden geçirme] (http://arxiv.org/abs/1305.2753)) fakat bu proje üzerindeki zaman kısıtlamaları nedeniyle Tek bir uzun hesaplamalar kümesini çalıştırmak için daha hızlı bir düzeltme arıyorum. – Matthew
@Walter Sanırım bitişik diziler kullanıyorsunuz? Ama tam olarak kaç tane altuzun olduğunu biliyorsun. Bir listeyi bilmiyorsanız ve kullanmanız gerekiyorsa, bellek erişimi gerçekten paralel ölçeklemeyi bozabilir. Bir iş parçacığı ayırıcısının yardımcı olacağını merak ediyorum. – emsr