Speicherzugriff durch mehrere Threads

Question

Ich schreibe eine Java-Anwendung mit mehreren Threads, die auf einem Nehalem-Prozessor ausgeführt wird.Ich habe jedoch das Problem, dass ich ab 4 Threads die Beschleunigung in meiner Anwendung fast nicht mehr sehe.

Ich habe einen einfachen Test gemacht.Ich habe einen Thread erstellt, der einfach ein großes Array zuweist und auf zufällige Einträge im Array zugreift.Wenn ich also die Anzahl der Threads ausführe, sollte sich die Laufzeit nicht ändern (vorausgesetzt, ich überschreite nicht die Anzahl der verfügbaren CPU-Kerne).Was mir jedoch aufgefallen ist, ist, dass die Ausführung von 1 oder 2 Threads fast gleich lange dauert, die Ausführung von 4 oder 8 Threads jedoch deutlich langsamer ist.Bevor ich also versuche, das Algorithmus- und Synchronisationsproblem in meiner Anwendung zu lösen, möchte ich herausfinden, welche maximal mögliche Parallelisierung ich erreichen kann.

Ich habe verwendet -XX:+UseNUMA JVM-Option, daher sollten die Arrays im Speicher in der Nähe der entsprechenden Threads zugewiesen werden.

P.S.Wenn die Threads eine einfache mathematische Berechnung durchführten, gab es für 4 und sogar 8 Threads keinen Zeitverlust, sodass ich zu dem Schluss kam, dass ich einige Probleme habe, wenn die Threads auf den Speicher zugreifen.

Wir freuen uns über jede Hilfe oder Idee, danke.

---

BEARBEITEN

Vielen Dank euch allen für die Antworten.Ich sehe, dass ich mich nicht gut genug erklärt habe.

Bevor ich versuchte, Synchronisierungsprobleme in meiner Anwendung zu beseitigen, habe ich einen einfachen Test durchgeführt, um die bestmögliche Parallelisierung zu überprüfen, die erreicht werden konnte.Der Code lautet wie folgt:

public class TestMultiThreadingArrayAccess {
    private final static int arrSize = 40000000;

    private class SimpleLoop extends Thread {
        public void run() {
            int array[] = new int[arrSize];
            for (long i = 0; i < arrSize * 10; i++) {
                array[(int) ((i * i) % arrSize)]++; // randomize a bit the access to the array
            }
            long sum = 0;
            for (int i = 0; i < arrSize; i++)
                sum += array[i];
        }
    }

    public static void main(String[] args) {
        TestMultiThreadingArrayAccess test = new TestMultiThreadingArrayAccess();
        for (int threadsNumber : new int[] { 1, 2, 4, 8 }) {
            Statistics timer = new Statistics("Executing " + threadsNumber+ " threads"); // Statistics is a simple helper class that measures the times
            timer.start();
            test.doTest(threadsNumber);
            timer.stop();
            System.out.println(timer.toString());
        }
    }

    public void doTest(int threadsNumber) {
        Thread threads[] = new Thread[threadsNumber];
        for (int i = 0; i < threads.length; i++) {
            threads[i] = new SimpleLoop();
            threads[i].start();
        }

        for (int i = 0; i < threads.length; i++)
            try {
                threads[i].join();
            } catch (InterruptedException e) {
            };
    }
}

Wie Sie sehen, gibt es in diesem Minitest überhaupt keine Synchronisierung und auch die Zuordnung des Arrays erfolgt innerhalb des Threads, sodass es in dem Teil des Speichers platziert werden sollte, auf den schnell zugegriffen werden kann.Außerdem gibt es in diesem Code keine Speicherkonflikte.Bei 4 Threads sinkt die Laufzeit immer noch um 30 %, und 8 Threads laufen doppelt so langsam.Wie Sie dem Code entnehmen können, warte ich einfach, bis alle Threads ihre Arbeit beendet haben, und da ihre Arbeit unabhängig ist, sollte die Anzahl der Threads keinen Einfluss auf die Gesamtzeit haben, die die Ausführung benötigt.

Auf der Maschine sind 2 Quad-Core-Hyperthread-Nehalem-Prozessoren (insgesamt 16 CPUs) installiert, sodass jeder mit 8 Threads seine CPU exklusiv abfangen kann.

Als ich versuchte, diesen Test mit einem kleineren Array (20.000 Einträge) auszuführen, betrug der Rückgang der Ausführungszeit bei 4 Threads 7 % und bei 8 Threads 14 %, was zufriedenstellend ist.Aber wenn ich versuche, einen wahlfreien Zugriff auf ein großes Array (40 Millionen Einträge) durchzuführen, erhöhen sich die Laufzeiten dramatisch, sodass meiner Meinung nach ein Problem besteht, dass auf große Speicherblöcke zugegriffen wird (weil sie nicht in den Cache-Speicher passen?), ohne dass auf sie zugegriffen wird -effizienter Weg.

Gibt es Ideen, wie man das beheben kann?

Ich hoffe, das klärt die Frage besser, nochmals vielen Dank.

Answer 1

Der Engpass im Test ist die CPU-zu-Speicher-Bandbreite.Selbst wenn lokaler Speicher verfügbar ist, wird er von einer bestimmten Anzahl von Threads gemeinsam genutzt.(Der Speicher ist lokal für einen Knoten und nicht für einen bestimmten Kern.) Sobald die CPU die verfügbare Bandbreite für eine einfache Schleife wie Ihren obigen Test leicht überschreiten kann, verbessert die Erhöhung der Threads bei einem solchen Test die Leistung nicht, sondern kann die Leistung verschlechtern aufgrund einer verschlechterten Cache-Kohärenz.

Nur ein Plausibilitätstest. Benutzen Sie auch den Parallelkollektor? -XX:+UseParallelGC.Erst dann wird UseNUMA wirksam.

Answer 2

Ohne genau zu wissen, was Sie tun und welches Problem Sie lösen möchten.Es sieht so aus, als ob Ihr Code stark synchronisiert ist, da dies der Hauptgrund dafür sein könnte, dass er nicht ausreichend skalierbar ist.Übermäßige Synchronisierung führt dazu, dass die Beschleunigung verlangsamt wird, sobald Ihre Anwendung dadurch nahezu seriell wird.Daher empfehle ich Ihnen, Ihre Implementierung zu überprüfen und zu versuchen, dies herauszufinden.

HINZUFÜGEN.

Nachdem Sie Ihre Implementierung dessen, was Sie tun, hinzugefügt haben.Der Leistungsabfall könnte durch einen großen und massiven Speicherzugriff erklärt werden.Sobald Sie alle Ihre Threads ausführen und diese auf den Speichercontroller zugreifen müssen, um nicht zwischengespeicherte Daten zu erhalten, da sie auf verschiedenen CPUs ausgeführt werden, verhindert der Speichercontroller, dass die CPUs dies gleichzeitig tun, was bedeutet, dass bei jedem Cache-Fehler eine Synchronisierung auf Hardwareebene erfolgt.In Ihrem Fall ist es fast so, als würden Sie 10 verschiedene unabhängige Programme ausführen.Ich schätze, wenn Sie beispielsweise 10 Kopien Ihres Webbrowsers starten (Sie können 10 durch eine beliebige große Anzahl ersetzen), werden Sie den gleichen Effekt sehen, aber das bedeutet nicht, dass die Browserimplementierung ineffektiv ist, sondern Sie erzeugen lediglich eine enorme Belastung Computerspeicher.

Answer 3

Wie Artem anmerkt, ist es möglich, dass Sie eine unnötige Synchronisierung haben.Aber ich würde mit der Feststellung der Fakten beginnen.Läuft Ihre App WIRKLICH langsamer, als Sie es beschreiben?

Hier ist ein aufschlussreicher Artikel zu diesem Thema: http://codeidol.com/java/java-concurrency/Testing-Concurrent-Programs/Avoiding-Performance-Testing-Pitfalls/

Es ist tatsächlich ziemlich schwierig, nützliche Mikro-Benchmarks zu schreiben, insbesondere wenn Sie mit gleichzeitigem Code arbeiten.Beispielsweise können Sie eine „Eliminierung von totem Code“ durchführen, bei der der Compiler den Code optimiert, von dem Sie glauben, dass er ausgeführt wird.Es ist auch schwer zu erraten, wann die Garbage Collection ausgeführt wird.Die Laufzeitoptimierung von Hotspot erschwert zudem die Messung.Bei Threads müssen Sie die Zeit berücksichtigen, die für deren Erstellung aufgewendet wird.Daher müssen Sie möglicherweise eine „CyclicBarrier“ usw. verwenden.genaue Messung zu haben.Sachen wie diese..

Allerdings fällt es mir schwer, dass Sie Probleme beim Zugriff auf den Speicher haben, wenn Sie nur lesen.Möglicherweise können wir Ihnen besser helfen, wenn Sie den Code posten können ...

Answer 4

Es gibt zwei offensichtliche potenzielle Probleme, die mir in den Sinn kommen.

• Durch die Verwendung von mehr Threads werden mehr Arrays zugewiesen, die den Cache sprengen.Zugriffe auf den Hauptspeicher oder niedrigere Cache-Ebenen sind deutlich langsamer.
• Wenn Sie dieselbe Quelle wie die Instanz des Zufallszahlengenerators verwenden, streiten sich Threads um den Zugriff darauf.Es handelt sich möglicherweise nicht um eine vollständige Synchronisierung, sondern um Speicherbarrieren mit einem sperrfreien Algorithmus.Im Allgemeinen sind sperrenfreie Algorithmen zwar im Allgemeinen schnell, werden jedoch bei starker Konkurrenz viel langsamer.

Answer 5

Abgesehen von Parallelitätsproblemen ist die wahrscheinlichste Ursache für Ihre Verlangsamung ein Speicher-Cache-Konflikt.

Wenn alle Threads auf denselben Speicher zugreifen, besteht die Möglichkeit, dass er sich im Speichercache des anderen Prozessors befindet, wenn Sie darauf zugreifen möchten.

Wenn der Speicher „schreibgeschützt“ ist, könnten Sie jedem Thread eine eigene Kopie geben, was es der JVM und dem Prozessor ermöglichen würde, die Speicherzugriffe zu optimieren.

Answer 6

Ich habe Ihren Test mit den Ratschlägen aus dem von mir geposteten Artikel modifiziert.Auf meinem 2-Kern-Rechner (das ist alles, was ich gerade habe) scheint das Ergebnis vernünftig zu sein (beachten Sie, dass ich für jede Thread-Nummer zwei Tests durchgeführt habe):

Vielleicht kannst du das versuchen?(Bitte beachten Sie, dass ich Ihren Test leicht modifizieren musste (siehe Kommentar), da die Ausführung auf meiner schlechten Hardware sehr lange gedauert hat.)

Beachten Sie auch, dass ich diesen Test mit dem ausführe -server Möglichkeit.

Test with threadNum 1 took 2095717473 ns
Test with threadNum 1 took 2121744523 ns
Test with threadNum 2 took 2489853040 ns
Test with threadNum 2 took 2465152974 ns
Test with threadNum 4 took 5044335803 ns
Test with threadNum 4 took 5041235688 ns
Test with threadNum 8 took 10279012556 ns
Test with threadNum 8 took 10347970483 ns

Code:

import java.util.concurrent.*;

public class Test{
    private final static int arrSize = 20000000;

    public static void main(String[] args) throws Exception {
        int[] nums = {1,1,2,2,4,4,8,8};//allow hotspot optimization
        for (int threadNum : nums) {
            final CyclicBarrier gate = new CyclicBarrier(threadNum+1);
            final CountDownLatch latch = new CountDownLatch(threadNum);
            ExecutorService exec = Executors.newFixedThreadPool(threadNum);
            for(int i=0; i<threadNum; i++){
                Runnable test = 
                  new Runnable(){
                     public void run() {
                         try{
                             gate.await();
                         }catch(Exception e){
                             throw new RuntimeException(e);
                         }
                         int array[] = new int[arrSize];
                         //arrSize * 10 took very long to run so made it
                         // just arrSize.
                         for (long i = 0; i < arrSize; i++) {
                             array[(int) ((i * i) % arrSize)]++;
                         }//for
                         long sum = 0;
                         for (int i = 0; i < arrSize; i++){
                              sum += array[i]; 
                         }
                         if(new Object().hashCode()==sum){
                              System.out.println("oh");
                         }//if
                         latch.countDown();
                      }//run
                   };//test
                exec.execute(test);
             }//for
             gate.await();
             long start = System.nanoTime();
             latch.await();
             long finish = System.nanoTime();
             System.out.println("Test with threadNum " +
                 threadNum +" took " + (finish-start) + " ns ");
             exec.shutdown();
             exec.awaitTermination(Long.MAX_VALUE,TimeUnit.SECONDS);           
        }//for
    }//main

}//Test