Effiziente Speicher der Nutzung der Bandbreite für das Streaming

StackOverflow https://stackoverflow.com/questions/709308

Frage

Ich habe eine Anwendung, die über 250 MB von Datenströmen, eine einfache und schnelle neuralen Netz-Schwellenfunktion an den Daten-Chunks Anwendung (die nur 2 32-Bit-Worte sind jeweils). Basierend auf dem Ergebnis des (sehr einfach) Rechen-, wird der Chunk unvorhersehbar in eine von 64 Bins geschoben. Es ist also ein großer Strom in und 64 kürzer (variable Länge) ausströmt.

Dies wird oft mit verschiedenen Detektionsfunktionen wiederholt.

Die Rechen ist die Speicherbandbreite begrenzt. Ich kann das sagen, weil es keine Geschwindigkeitsänderung ist, auch wenn ich eine Diskriminanzfunktion verwenden, die viel rechenintensiv ist.

Was ist der beste Weg, um die Schreibvorgänge der neuen Ströme zu strukturieren, um meine Speicherbandbreite zu optimieren? ich besonders denke, dass Cache Verständnis und Cache-Zeilengröße eine große Rolle spielen kann. Stellen Sie sich den schlimmsten Fall, wo ich meine 64 Ausgabeströme und durch Pech, viele Karte auf den gleichen Cache-Zeile haben. Dann, wenn ich die nächsten 64 Bits von Daten in einen Strom zu schreiben, muss die CPU eine schale Cache-Zeile in dem Hauptspeicher spülen, und in der richtigen Cachezeile laden. Jede dieser verwendet 64 Bytes Bandbreite ... so meine Bandbreite begrenzte Anwendung kann 95% der Speicherbandbreite verschwenden (in diesem hypothetischen schlimmsten Fall, obwohl).

Es ist schwer zu versuchen, auch den Effekt zu messen, so Möglichkeiten, um es der Gestaltung ist noch vage. Oder bin ich jagen sogar einen Geist Engpass, der irgendwie die Hardware besser optimiert als ich es könnte?

Ich bin mit Core-II x86-Prozessoren, wenn das einen Unterschied macht.

Edit: Hier ist ein Beispiel-Code. Es strömt durch eine Anordnung und kopiert seine Elemente zu verschiedenen Ausgabeanordnungen aufgenommen pseudo-zufällig. Das Ausführen des gleichen Programms mit einer unterschiedlichen Anzahl von Ziel Bins gibt unterschiedliche Laufzeiten, obwohl die gleiche Menge an Rechen- und Speicher Lese- und Schreib wurden durchgeführt:

2 Ausgangsströme: 13 Sekunden
8 Ausgangsströme: 13 secs
32 Ausgangsströme: 19 secs
128 Ausgabeströme: 29 Sekunden
512 Ausgabeströme: 47 Sekunden

Der Unterschied gegenüber 2 512 Ausgangsströmen zwischen der Verwendung ist 4X, (wahrscheinlich ??), die durch Cache-Zeile Räumungsaufwand. 

#include <stdio.h>
#include <stdlib.h>
#include <ctime>

int main()
{
  const int size=1<<19;
  int streambits=3;
  int streamcount=1UL<<streambits; // # of output bins
  int *instore=(int *)malloc(size*sizeof(int));
  int **outstore=(int **)malloc(streamcount*sizeof(int *));
  int **out=(int **)malloc(streamcount*sizeof(int));
  unsigned int seed=0;

  for (int j=0; j<size; j++) instore[j]=j;

  for (int i=0; i< streamcount; ++i) 
    outstore[i]=(int *)malloc(size*sizeof(int));

  int startTime=time(NULL);
  for (int k=0; k<10000; k++) {
    for (int i=0; i<streamcount; i++) out[i]=outstore[i];
    int *in=instore;

    for (int j=0; j<size/2; j++) {
      seed=seed*0x1234567+0x7162521;
      int bin=seed>>(32-streambits); // pseudorandom destination bin
      *(out[bin]++)=*(in++);
      *(out[bin]++)=*(in++);
    }

  }
  int endTime=time(NULL);
  printf("Eval time=%ld\n", endTime-startTime);
}
War es hilfreich?

Lösung

Wie Sie zu den 64 Ausgabefächer schreiben, werden Sie viele verschiedene Speicherplätze werden. Wenn die Behälter im Wesentlichen zufällig gefüllt sind, bedeutet dies, dass Sie manchmal zwei Bins haben werden, die die gleiche Cache-Zeile teilen couls. Kein großes Problem; die Core-2-L1-Cache ist 8-Wege-assoziativ. Das bedeutet, dass Sie ein Problem mit der 9.en Cache-Zeile nur bekommen würden. Mit nur 65 Live-Speicherreferenzen jederzeit (1 lesen / 64 Schreiben), 8-fach assoziativ ist OK.

Die L2-Cache ist offenbar 12-fach assoziativ (3/6 MB insgesamt, so 12 ist nicht so seltsam eine Zahl). Also selbst wenn Sie Kollisionen in L1 haben würde, stehen die Chancen ziemlich gut du bist immer noch nicht Hauptspeicher zu treffen.

Allerdings, wenn Sie dies nicht möchten, neu ordnen die Behälter im Speicher. Statt stroing jeder Behälter der Reihe nach, verschachteln sie. Für Bin 0, speichern chunks 0-15 bei Versetzungen 0-63, aber speichern chunks 16-31 Offset bei 8.192-8.255. Für ist 1, speichern Brocken 0-15 bei Versetzungen 64-127, und so weiter. Dies dauert nur wenige Bit-Verschiebungen und Masken, aber das Ergebnis ist, dass ein Paar von Behältern 8 Cache-Zeilen teilen.

Eine andere Möglichkeit Ihren Code in diesem Fall zu beschleunigen, ist SSE4, vor allem im x64-Modus. Sie würden erhalten 16 Register 128 Bit x, und Sie können die Lese (MOVNTDQA) optimieren Cache-Verunreinigung zu begrenzen. Ich bin mir nicht sicher, ob das eine Menge mit der Lesegeschwindigkeit helfen, obwohl - ich die Core2 prefetcher diese zu fangen erwarten würde. Lese sequenzielle Zahlen ist die einfachste Art von Zugriff möglich, jeder prefetcher soll, dass optimieren.

Andere Tipps

Haben Sie die Möglichkeit, Ihre Ausgangsströme als einen einzelnen Strom mit Inline-Metadaten Schreiben jeden ‚Brocken‘ zu identifizieren? Wenn Sie ein lesen waren ‚Brocken‘ Ihre Funktion Schwelle darauf laufen, dann anstatt sie zu einem bestimmten Ausgabestrom schreiben würden Sie nur schreiben, die sie von den Originaldaten gefolgt gehörte (1 Byte) Stream, dann würden Sie ernsthaft reduzieren Sie Ihre Tracht Prügel.

Ich würde nicht vorschlagen, mit Ausnahme der Tatsache, dass Sie gesagt haben, dass Sie diese Daten oft zu verarbeiten haben. Auf jedem aufeinanderfolgenden Durchlauf, lesen Sie Ihren Eingabestrom die Behälternummer (1 Byte) dann tun, was Sie für diesen Behälter auf dem nächsten 8 Bytes tun müssen, um bekommen.

Was das Cachen Verhalten dieses Mechanismus, da sie nur durch zwei Datenströme gleiten und in allen außer dem ersten Fall, das Schreiben so viele Daten wie Sie lesen, wird die Hardware geben Ihnen alle Hilfe, die Sie könnte möglicherweise so weit wie Prefetching, Cache-Line-Optimierung hoffen, etc.

Wenn Sie, dass zusätzliches Byte jedes Mal, wenn Sie Ihre Daten verarbeitet hinzuzufügen hatte, Ihre schlimmsten Fall Cache-Verhalten ist der durchschnittliche Fall. Wenn Sie den Speicher Hit leisten können, scheint es wie ein Sieg für mich.

Hier sind einige Ideen, wenn Sie wirklich verzweifelt ...

Sie können ein Upgrade Hardware berücksichtigen. Für Anwendungen, etwas ähnlich wie bei Ihnen Streaming, habe ich festgestellt habe ich einen großen Geschwindigkeitsschub durch zu einem i7-Prozessor zu ändern. Auch AMD-Prozessoren sind angeblich besser als Core 2 für Speichergebundenen Arbeit (obwohl ich habe sie nicht vor kurzem selbst verwendet).

Eine andere Lösung, die Sie sich anschauen sollten tut, um die Verarbeitung auf einer Grafikkarte, die eine Sprache wie CUDA. Grafikkarten sind so abgestimmt, sehr hohe Speicherbandbreite haben und schnell Floating-Point-Mathematik zu tun. Erwarten Sie verbringen 5x bis 20x die Entwicklungszeit für CUDA-Code relativ zu einem geradlinig nicht optimierten C-Implementierung.

Sie möchten vielleicht entdecken Sie die Dateien in den Speicher abzubilden. Auf diese Weise der Kernel Pflege der Speicherverwaltung für Sie nehmen können. Der Kernel in der Regel am besten weiß, wie Seite Caches zu behandeln. Dies gilt insbesondere, wenn Ihre Anwendung auf mehr als einer Plattform laufen, da die verschiedenen Oses Speicherverwaltung auf verschiedene Weise behandeln.

Es gibt Frameworks wie ACE ( http: //www.cs.wustl. edu / ~ schmidt / ACE.html ) oder Boost ( http://www.boost.org ), dass Sie Code zu schreiben, ermöglichen, die Speicherzuordnung in einer plattformunabhängigen Art und Weise der Fall ist.

Die wirkliche Antwort für Situationen wie dieser ist mehrere Ansätze und Zeit, um sie zu codieren, auf. Was man natürlich getan hat. Alle Leute wie ich tun kann, sind andere Ansätze vorschlagen zu versuchen.

Zum Beispiel: auch in Abwesenheit von Cache-Thrashing (Ausgabeströme Zuordnung zu den gleichen Cache-Zeilen), wenn Sie Größe Ints schreiben, mit size = 1 << 19 und sizeof (int) = 4, 32-Bit - das heißt, wenn Sie 8 MB Daten schreiben, Sie sind 8MB tatsächlich zu lesen und dann 8MB zu schreiben. Denn wenn Sie Ihre Daten in gewöhnlichen WB (Write-Back) Speicher auf einem x86-Prozessor ist, auf eine Linie zu schreiben, müssen Sie zuerst die alte Kopie der Zeile lesen -. Obwohl Sie die Daten lesen wegzuwerfen gehen

Sie können eliminiert diese unnötigen RFO Verkehr durch (a) unter Verwendung von WC-Speicher (wahrscheinlich einen Schmerz zu gründen) oder (b) unter Verwendung von SSE-Streaming-Shops, auch bekannt als NT (Non-Temporal) Speichert lesen. MOVNT * - (. Es gibt auch eine MOVNTDQA Last-Streaming, wenn auch schmerzhaft verwenden) MOVNTQ, MOVNTPS etc.

ich eher wie dieses Papier, das ich nur durch googeln http://blogs.fau.de/hager/2008/09/04/a-case-for-the-non-temporal-store/

Jetzt: MOVNT * WB Speicher gelten, aber wie WC-Speicher arbeiten, eine kleine Anzahl von Schreib cmbining Puffer verwendet wird. Die tatsächliche Anzahl variiert je nach Prozessormodell: Es gibt nur 4 auf dem ersten Intel-Chip sie, P6 zu haben war (auch bekannt als Pentium Pro). Ooof ... Bulldozer 4K WCC (Write Cache Combining) im Grunde bietet 64 write combining Puffer pro http://semiaccurate.com/forums/showthread.php?t=6145&page=40 , obwohl es nur 4 klassischen WC Puffer sind. Aber http: // www. intel.com/content/dam/doc/manual/64-ia-32-architectures-optimization-manual.pdf sagt, dass einige processos 6 WC Puffer haben, und einige 8. Wie auch immer ... es gibt ein paar sind , aber nicht so viele. In der Regel nicht mehr als 64.

Aber hier ist etwas, das Sie könnten versuchen: implementieren Schreib selbst kombinieren.

a) zu einem einzigen Satz von 64 (#streams) Puffern, die jeweils eine Größe 64B (Cache-Zeilengröße) schreiben, - oder vielleicht 128 oder 256B. Lassen Sie diese Puffer in gewöhnlichen WB-Speicher sein. Sie können sie mit gewöhnlichen Geschäften zugreifen, obwohl, wenn Sie MOVNT * verwenden können, groß.

Wenn einer dieser Puffer voll ist, kopieren Sie es als einen Burst an den Ort im Speicher, wo der Strom wirklich gehen soll. Mit MOVNT * Streaming speichert.

Das wird am Ende tut * N Bytes zu den temporären Puffer gespeichert sind, der L1-Cache treffen * 64 * 64 gelesenen Bytes die temporären Puffer zu füllen * N Bytes von dem temporären Puffer, trifft die L1-Cache gelesen. * N Bytes per Streaming speichert geschrieben -. Im Grunde gerade in den Speicher gehen

D.h. N Bytes Cache-Trefferlese + N Bytes Cache-Trefferschreib + N Bytes Cache-Miss

im Vergleich zu N-Bytes Cache-Miss lesen + N Cache-Schreib-Lese-Bytes.

das N Bytes der Cache-Miss-Lese Reduzierung kann moe als für den zusätzlichen Aufwand zu machen.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top