iç içe döngüler, iç döngü paralelleştirme, tekrar iş parçacıkları

Question

Yasal Uyarı: Aşağıdaki örnek, sorunu hızlı bir şekilde anlayabilmeniz için yalnızca bir örnek niteliğindedir. Gerçek dünya problemini düşünüyorsanız, dinamik bir programlama düşünün.

sorun: Biz bir n * m matrisi var ve şu kodda olduğu gibi önceki satırdan unsurları kopyalamak istiyorum:

for (i = 1; i < n; i++) 
    for (j = 0; j < m; j++) 
     x[i][j] = x[i-1][j]; 

Yaklaşım: Dış döngü yineleme zorunda sırayla yürütülürler, sırayla yürütülürler. İç döngü paralelleştirilebilir. Konu oluşturma ve öldürme yükünü en aza indirgemek istiyoruz, bu yüzden sadece bir kez iş parçacığı oluşturmak istiyoruz, ancak bu OpenMP'de imkansız bir görev gibi görünüyor. Biz dış döngü ordered seçeneği uyguladığınızda

#pragma omp parallel private(j) 
{ 
    for (i = 1; i < n; i++) 
    { 
     #pragma omp for scheduled(dynamic) 
     for (j = 0; j < m; j++) 
     x[i][j] = x[i-1][j]; 
    } 
} 

, kod sıralı şekilde yürütülecektir, bu nedenle herhangi bir performans kazancı olacaktır. Yukarıdaki senaryo için, bazı geçici çözümler kullanmak zorunda kalsam bile, çözüm aramaya çalışıyorum.

Asıl kodumu ekliyorum. Bu aslında sekanstan daha yavaştır. sürümü. inceleyin:

ölçme gelince

/* load input */ 
for (i = 1; i <= n; i++) 
    scanf ("%d %d", &in[i][W], &in[i][V]); 

/* init */ 
for (i = 0; i <= wc; i++) 
    a[0][i] = 0; 

/* compute */ 
#pragma omp parallel private(i,w) 
{ 
    for(i = 1; i <= n; ++i) // 1 000 000 
    { 
     j=i%2; 
     jn = j == 1 ? 0 : 1; 

     #pragma omp for 
     for(w = 0; w <= in[i][W]; w++) // 1000 
      a[j][w] = a[jn][w]; 

     #pragma omp for 
     for(w = in[i][W]+1; w <= wc; w++) // 350 000 
      a[j][w] = max(a[jn][w], in[i][V] + a[jn][w-in[i][W]]); 
    } 
} 

, böyle bir şey kullanıyorum:

double t; 
t = omp_get_wtime(); 
// ... 
t = omp_get_wtime() - t; 

Answer 1

Bu özel durumla OpenMP içinde paralelliğini Özetle: O değmez.

Neden? İç döngülerdeki işlemler basittir. Kod -O3 ile derlenmiştir, bu nedenle max() çağrısı muhtemelen işlev gövdesi koduyla değiştirilmiştir. Kapalı bariyerin üstündeki yük, muhtemelen performans artışını telafi etmek için yeterince yüksektir ve genel yük, paralel kodu sıralı koddan daha da yavaşlatmaya yetecek kadar yüksektir.

#pragma omp parallel private(i,j) 
{ 
    for (i = 1; i < n; i++) 
    { 
     #pragma omp for 
     for (j = 0; j < m; j++) 
     x[i][j] = x[i-1][j]; 
    } 
} 

performans, çünkü yerleşik iplik GCC libgomp içinde yeniden bu bir

for (i = 1; i < n; i++) 
{ 
    #pragma omp parallel for private(j) 
    for (j = 0; j < m; j++) 
     x[i][j] = x[i-1][j]; 
} 

sayesinde benzer göre: Ben de böyle bir yapı içinde gerçek performans kazancı yoktur, öğrendim Bu makaleye: http://bisqwit.iki.fi/story/howto/openmp/

Dış döngü paralellize edilemediğinden (ordered seçeneği olmadan), p'nin performansını önemli ölçüde iyileştirmenin bir yolu yoktur. OpenMP kullanarak söz konusu rogram. Birisi yanlış bir şey yaptığımı hissederse ve bu mümkün ise, çözümü görmek ve test etmekten memnuniyet duyarım.