Vergleichen von zwei verschiedenen Szenarien auf zwei verschiedenen Architekturen beim Auffinden des max-Elements eines Arrays

Question

Angenommen, wir haben das klassische Szenario, in dem wir das maximale Element (nur ganze Zahlen) eines Arrays suchen müssen, nicht aber dessen Position. Welche der folgenden 2 Codebeispiele (die innerhalb einer 'for' Schleife liegen) laufen schneller auf einer CPU und welche auf einer GPU, und warum?

if(array[i] > max) 
    max = array[i]; 

und

max = 0.5 * (a + b + abs(a-b));  //Where 'a' and 'b' refer to 'max' and 'array[i]' 

Darüber hinaus, was in dem zweiten Code-Block stört mich wirklich, ist der 'abs' Funktionsaufruf. Gibt es eine Möglichkeit, den absoluten Wert einer Zahl nur mit einem arithmetischen Ausdruck zu berechnen?

Answer 1

Ich denke, du versuchst wirklich zu fragen, über Zweigstellen vs. Verzweigen Wege zu tun m = max(m, array[i]). C-Compiler kompilieren die if() -Version bereits zu einem zweiglosen Code (unter Verwendung von cmov), abhängig von den Optimierungseinstellungen. Es kann sogar automatisch zu einer gepackten Vergleichs- oder gepackten Max-Funktion vektorisiert werden.

Ihre 0.5 * abs() Version ist offensichtlich schrecklich (viel langsamer als eine bedingte Bewegung), weil es in double und zurück konvertiert. anstatt durch zwei mit einer rechten Verschiebung zu teilen.

Siehe ASM auf the Godbolt Compiler Explorer:

// auto-vectorizes to PMAXSD, or without SSE4.1, to pcmpgt/pand/por emulation of the same 
int maxarray_if(int arr[], int n) { 
    int result = arr[0]; 
    for (int i=0 ; i<n; ++i) { 
    int tmp = arr[i]; 
    if (result < tmp) 
     result = tmp; 
    } 
    return result; 
} 

gcc 5.3 -O3 -march=haswell -mno-avx auto-vektorisiert inneren Schleife:

.L13: 
    add  eax, 1 
    pmaxsd xmm0, XMMWORD PTR [rdx] 
    add  rdx, 16 
    cmp  r8d, eax 
    ja  .L13 

Vs. die FP-Version:

Also die FP-Version ist offensichtlich komplette Müll.

Sie erhalten ähnliche Ergebnisse für jede Zielarchitektur. Die Konvertierung von/zu double wird nicht weggehen. gcc hält es sogar mit -ffast-math.

Answer 2

Load balance es auf CPU und GPU nach ihrer Arbeit Abschluss Timing.

Nehmen wir an, tx ist CPU-Zeit, ty ist GPU Zeit, wx ist CPU Arbeit teilen Prozent, wy ist GPU Workshare Prozent.

Iteration 1 
wx=0.5; wy=0.5; // just a guess as 1/(total number of devices) 

Iteration 2 
px= wx/tx; ----> compute power of cpu 
py= wy/ty; ----> compute power of gpu 
because doing work in less time means more 


ptotal=px+py; 

wx=px/ptotal; 
wy=py/ptotal; 

setting work share to exact power can alternate next shares 
so you may need relaxation constant 


wx=0.3 * (px/ptotal); 
wy=0.3 * (py/ptotal); 

so small changes in instantenous compute power won't bug this. 

Iteration 3: 

px= wx/tx; 
py= wy/ty; 

ptotal=px+py; 

wx=0.3 * (px/ptotal); 
wy=0.3 * (py/ptotal); 

aber in OpenCL würden Sie ihnen eine angemessene lokale worksize und Arbeit Aktien in Auflösung lokaler worksize erfolgen geben muss.

global_range_x= nearest_multiple_of_256(wx * total_global_range); 
global_range_y= nearest_multiple_of_256(wy * total_global_range); 

wenn Summe der globalen Bereiche gleich gesamten Bereich liegt, ist es in Ordnung, Versetzungen pro Gerät zu berechnen, nach anderen Geräten insgesamt Bereiche.

Wenn CPU einen berechneten Bereich von 768 und GPU einen Bereich von 256 hat, können Sie ihre globalen Offsets auf 0 (CPU) und 768 (GPU) setzen, damit sie sich nicht überlappen.