Ich verwende ein Beispiel aus der Finite-Elemente-Theorie, aber jeder, der eine große Datenstruktur unterhält und diese sukzessive erweitert, wird etwas Ähnliches finden.
Angenommen, ich habe ein unstrukturiertes Netz aus Punkten und Dreiecken, wobei die Punkte durch Koordinaten (z. B. und ) gegeben sind und die Dreiecke jeweils aus drei Punktindizes (z. B. , und ) bestehen.y i j k
Wie in FEM üblich, wird das Netz nacheinander verfeinert. Wenn wir auf eine globale regelmäßige Verfeinerung zurückgreifen, wächst die Anzahl der Dreiecke mit jeder Iteration der Verfeinerung um den Faktor . Je nachdem, wie dies gemacht wird, entwickelt sich das Speicherlayout unterschiedlich.
Angenommen, das Netz belegt die Speicherzellen 1 bis 300, alles darüber hinaus ist frei.
Beispiel 1:
Wir weisen den Platz für das neue Netz, die Zellen 301 bis 1501, zu, füllen es mit den Daten des verfeinerten Netzes und vergessen das alte. Das nächste verfeinerte Netz wird in den Zellen 1501 bis 6300 platziert, das nächste in den Zellen 6301 bis 21500 und so weiter. Die Position des aktuellen Netzes wird im Speicher "nach rechts" verschoben, während ein riesiger Patch nicht verwendet wird. Möglicherweise geht uns vorzeitig der Speicher aus.
Man könnte im obigen Beispiel beobachten, dass dies uns nur für einen Verfeinerungsschritt behindert, da uns auch ohne diese Fragmentierung eine Verfeinerung später der gesamte Speicher ausgehen würde. Wenn auch das Scheitelpunktarray berücksichtigt wird, kann das Problem schwerwiegender werden.
Wie kann dies umgangen werden?
Beispiel 2:
Ordnen Sie das Dreiecksarray den Zellen 1..1200 neu zu. Erstellen Sie das neue Netz in den Zellen 1201 bis 2400. Kopieren Sie den Inhalt dieser Arbeitskopie in die Zellen 1..1200 und vergessen Sie die Arbeitskopie. Ähnlich wiederholen.
Ok, wir haben immer noch vorzeitig keinen Speicher mehr, weil wir eine Arbeitskopie benötigen. Wie wäre es damit:
Beispiel 3:
Ordnen Sie das Dreiecksarray den Zellen 1..1500 neu zu. Kopieren Sie das alte Netz nach 1201 .. 1500. Erstellen Sie ein neues Netz in den Zellen 1..1200. Dann vergessen Sie die Kopie des alten Netzes.
Der Fall hier ist künstlich, weil man auf diesen Skalen keine globale Netzverfeinerung verwenden würde. Wenn das Wachstum viel kleiner ist, ist eine Neuausrichtung des Speichers möglich, um eine Fragmentierung zu vermeiden. Jedoch,
Fragen:
Wird die Speicherfragmentierung im praktischen wissenschaftlichen Rechnen / Hochleistungsrechnen jemals kritisch?
Wenn überhaupt, wie vermeidest du das? Vielleicht ist mein Maschinenmodell sogar falsch, und das Betriebssystem richtet den Speicher durch starke Magie stillschweigend neu aus oder verwaltet fragmentierte Blöcke auf dem Heap.
Genauer gesagt, wie wirkt es sich auf das Netzmanagement aus?
quelle
In Deal.II verfeinern wir das Netz, indem wir alte Zellen wegwerfen und durch neue ersetzen. Es werden aber auch neue in die Speicherlöcher gelegt, die gelöschte Zellen hinterlassen. Alle Schleifen über alle Zellen werden dann in der Reihenfolge ausgeführt, in der Zellen im Speicher angetroffen werden, um die Cache-Treffer hoch zu halten.
Die größere Frage ist, wie Sie die Daten speichern, die Zellen definieren. Sie können natürlich auch Simplex {Vertex vertices [4]; int material_id; int subdomain_id; Bool verwendet; void * user_data; };
Klassentriangulation {Simplex * -Zellen; }; Dies ist jedoch nicht cacheeffizient, da die meisten Schleifen über alle Zellen nur eine Teilmenge der Daten berühren, die Sie in Ihrer Simplex-Datenstruktur speichern, und daher nur ein Bruchteil der Daten verwendet wird, die im Cache landen. Eine bessere Strategie besteht darin, Folgendes zu tun: class Triangulation {Vertex * vertices; int * material_ids; int * subdomain_ids; bool * used_flags; void * * user_data; }; Da in Schleifen über alle Zellen nachfolgende Iterationen wahrscheinlich auf dieselbe Teilmenge von Daten zugreifen, die Zellen definieren, laden Read-Ahead-Caches nur die Daten vor, die Sie tatsächlich verwenden werden, und führen folglich zu hohen Cache-Trefferquoten.
quelle
1) Nein. Der Solver-Speicher überwiegt bei weitem den Mesh-Speicher. Selbst wenn Sie den leichtesten, explizitesten Löser ausführen, macht das Netz höchstens 25% des Speichers der Simulation aus und viel wahrscheinlicher <10%.
2) Teilen Sie Ihre Zuordnung auf und verwenden Sie Speicherpooling. Sie müssen nicht für das gesamte Netz einen zusammenhängenden Block zuweisen, da Sie normalerweise nur über lokale Teile iterieren müssen. Die Einführung einer Indirektionsebene wirkt sich nicht sinnvoll auf die Leistung aus.
quelle
Wenn Ihnen der Speicher ausgeht, führen Sie einfach mehr Knoten aus, damit Sie mehr Speicher haben. Sie verschwenden eine sehr wertvolle Ressource (das menschliche Gehirn), um ein Problem zu lösen, das sehr einfach zu lösen ist.
quelle