Ich implementiere einen ultraschnellen Popcount auf Intel Xeon® Phi®, da es ein Performance-Hotspot für verschiedene Bioinformatik-Software ist.
Ich habe fünf Codeabschnitte implementiert,
%Vor%Eine Zusammenfassung des Codes mit OpenMP-Unterstützung kann von Ссылка
heruntergeladen werdenDer Code wurde mit dem Intel C / C ++ Compiler XE 13 mithilfe des folgenden Befehls kompiliert:
%Vor%Der Code wird nativ auf dem Co-Prozessor (61 Kerne) mit "122 Threads" und Thread-Affinität als "ausgewogen" unter Verwendung von Exporten ausgeführt:
%Vor%Ich benutze Xeon Phi SE10p, B1 Stepping, CentOS6.4 Testen auf 28 Megabyte Dschunken (gefüllt von rand ()) und iterieren für 10000-mal, die Leistung sind wie folgt:
%Vor%Die "scalar_popcountu" und "scalar_popcountlu" verwenden jeweils "_mm_countbits_32" und "_mm_countbits_64" intrinsics, die den skalaren "popcnt" Befehl verwenden. Die Einstellung "#pragma vector always" fordert den Compiler auf, die Last zu vektorisieren und als 16 vorzeichenlose Intets oder 8 vorzeichenlose longs zu addieren, obwohl der Popcount selbst immer noch eine skalare Anweisung ist.
Die Implementierung von vpu_popcount1 ist analog zu der SSSE3-Popcount-Implementierung Ссылка . 1) Xeon Phi unterstützt jedoch keine gepackten Byte-Operationen für Integer (das Minimum ist doppelte Wörter, aka 32-Bit) und 2) es implementiert somit nicht die "Gepackte Summe der absoluten Differenz" -Anweisung (wie _mm_sad_epu8 in SSSE3) Die Reduktionsaddition wurde durch eine Kombination von vier Gruppen von "vpermf32x4", "vpaddd" und "movslq" durchgeführt. Daher hat die Implementierung viel mehr Anweisungen generiert als die ursprüngliche SSSE3-Version.
Die Implementierung von vpu_popcount2 ist analog zur SSE2-Popcount-Implementierung (man kann sich auf "Hacker's Delight" beziehen). Die Implementierung generiert weniger Anweisungen als vpu_popcount1 und ist etwa 30% schneller. Das mühsame "Reduce Add" ist jedoch immer noch nicht zu vermeiden.
Die Implementierung von vpu_popcount3 ist sehr spezifisch für Xeon Phi. Mit der Mischung aus Vektor- und Skalaroperationen ist es etwa 15% schneller als vpu_popcount2 (die Skalaroperationen bei Vektoroperationen sind Freizeit in meiner Implementierung, man kann die Skalaroperationen entsprechend dem vom Compiler erzeugten Assemblercode neu anordnen, aber die erwartete Verbesserung ist begrenzt, soweit es mich betrifft). Die Verbesserung beruht auf der Beobachtung, dass 1) Xeon Phi eine In-Order-Planung ist, 2) zwei Skalaranweisungen oder "1 Vektor + 1 Skalar" -Befehle können pro Taktzyklus ausgegeben werden. Ich habe die Unroll von 8 auf 4 verringert, um Register-Datei-Sättigung zu vermeiden.
Der explizite Prefetch von Speicher zu L2 8 Schleifen im Voraus und von L2 zu L1 1 Schleifen im Voraus in jeder Funktion hat das L1 Hit Ratio von 0,38 auf 0,994 erhöht.
Das Aufrollen erhöht die Leistung um ca. 15%. Dies ist kontraintuitiv, da Xeon Phi eine In-Order-Planung ist. Mit dem Unroll-Befehl kann der ICC-Compiler jedoch so viel Zeit für die Kompilierzeitplanung aufwenden wie möglich.
Haben wir noch mehr Technik, um die Leistung zu steigern?
Zwei Stück schneller Codes von Brian Nickerson,
%Vor%vpu_popcount3_revised:
%Vor%vpu_popcount5:
%Vor%Seit gestern kann ich Ihren Code und meinen Vorschlag auf meiner eigenen Karte ausführen. Ich bekomme nicht genau die gleichen Timings wie du, wahrscheinlich aufgrund der Fortschreitung meiner Hardware und vielleicht in Bezug auf die Versionen meines Compilers. Aber der Trend hält an und mein Vorschlag schien einen Leistungsschub von fünfzehn Prozent zu erreichen.
Ich habe einen zusätzlichen kleinen Leistungsschub zwischen fünf und zehn Prozent, mit ein wenig mehr Feinabstimmung, wie im folgenden Code gezeigt. Beachten Sie, dass im folgenden Codefragment für B6 jedes Element auf 0x000000FF festgelegt ist. An diesem Punkt denke ich, dass der Algorithmus ziemlich nahe an die maximale nachhaltige Bandbreite heranreichen wird, die von GDDR an den L2-Cache geliefert werden kann.
(HINZUGEFÜGT NOTE: Ein Beweis für diese Behauptung ist, dass wenn ich den Körper der Funktion popcount5 mit einer for-Schleife umschließe, die ihn zehnmal wiederholt - und beachte, dass dies zehn schnelle Wiederholungen der "chunk_size" sind von Eingabedaten, so wird es neun mal in L2 heiß werden - die Gesamtzeit für den Test erhöht sich nur um einen Faktor von etwa fünf anstatt zehn. Ich bringe das auf, weil ich denke, dass dein Ziel es ist, das zu tunen B. die Geschwindigkeit der Bitzähllogik, aber vielleicht hat die Anwendung, in der Sie sie bereitstellen möchten, tatsächlich einen kleineren und / oder wärmeren Arbeitssatz.Wenn dies der Fall ist, schränkt das durch die DRAM- & gt; L2-Bandbreite eingeführteDrosseln das Bild ein Beachten Sie, dass das Zurückgeben der Größe Ihrer Testeingabe, so dass es in L2 tendenziell heißer bleibt, anderen Overhead - wahrscheinlich den OpenMP-Overhead - dazu bringt, relativ bedeutender zu werden.)
%Vor%Versuchen Sie bitte die folgende Variante und berichten Sie, ob dies die Leistung für Sie verbessert? Ich gehe auf einige Punkte ein, die meiner Meinung nach nicht optimal sind:
Tags und Links c hammingweight vectorization xeon-phi intel-mic