Wie man einen Graphalgorithmus gleichzeitig in Java unter Verwendung der Mehrkernparallelität laufen lässt

Question

Ich möchte einen Algorithmus auf großen Diagrammen gleichzeitig unter Verwendung der Mehrkernparallelität laufen lassen. Ich habe eine Weile daran gearbeitet, konnte mir aber keine gute Lösung einfallen lassen.

Dies ist der naive Algorithmus:

W - a very large number 
double weight = 0 

while(weight < W) 

    - v : get_random_node_from(Graph) 

    - weight += calculate(v) 

• Ich sah in Gabel-and-schließen, kann aber nicht einen Weg finden, um dieses Problem in kleinere Teilprobleme zu teilen.
• Dann versuchte ich Java 8 Streams, für die ich einen Lambda-Ausdruck erstellen muss. Als ich versuchte, so etwas wie dies zu tun:

double weight = 0 Callable<Object> task =() -> { can not update weight here, as it needs to be final }

Meine Frage ist, ist es möglich, eine Variable wie weight in einem Lambda-Verfahren zu aktualisieren? Oder gibt es einen besseren Weg, dieses Problem zu lösen?

Die nächste, die ich habe, ist mit ExecutorService, aber laufen Sie auf die Probleme der Synchronisation.

------------ EDIT --------------

Hier ist die detaillierte Algorithmus:

In Kurz gesagt, was ich versuche zu tun, ist ein riesiger Graph zu durchlaufen, eine Operation an zufällig ausgewählten Knoten durchzuführen (solange Gewicht < W) und einen globalen Strukturindex zu aktualisieren.

Dies dauert zu lange, da es nicht die volle Leistung der CPU nutzt.

Idealerweise alle Fäden/Prozesse auf mehrere Kerne würden die Operationen an den zufällig ausgewählten Knoten führen, und aktualisieren den freigegebenen Gewicht und Index.

Hinweis: Es spielt keine Rolle, wenn verschiedene Threads den gleichen Knoten aufnehmen, da es ohne Ersatz zufällig ist.

Algorithmus:

Funktion Serien() {

List<List<Integer>> I (shared data structure which I want to update) 
double weight 

//// Task which I want to parallelize 

while(weight < W) { 

    v : get_random_node_from(Graph) 

    bfs(v, affected_nodes) ...// this will fill up affected_nodes by v 

    foreach(affected_node in affected_nodes) { 

     // update I related to affected_node 
     // and do other computation 
    } 

    weight += affected_nodes.size() 

} 

///////// Parallelization ends here 

use_index(I) // I is passed now to some other method(not important) to get further results 

} 

Das Wichtigste ist, aktualisieren Sie alle Threads die gleiche I und weight.

Danke.

Answer 1

Nun, Sie könnten diese weight in ein Array eines einzelnen Elements wickeln, es ist eine Art von Know-Trick für diese Art von Sachen; auch intern von Java, wie dies getan:

weight[0] = weight[0] + calculate(v); 

Aber es gibt Probleme mit diesem, da Sie es parallel laufen zu lassen werden. Sie erhalten das gewünschte Ergebnis nicht, da weight[0] nicht Thread-sicher ist.Und Sie könnten eine Art von Synchronisation verwenden, aber Java hat bereits eine großartige Lösung dafür: DoubleAdder, die in konkurrierenden Umgebungen (und mehreren CPUs) viel besser skaliert.

Ein triviales und kleines Beispiel:

DoubleAdder weight = new DoubleAdder(); 

private static int calculate(int v) { 
    return v + 1; 
} 


Stream.of(1, 2, 3, 4, 5, 6, 7, 8, 9) 
      .parallel() 
      .forEach(x -> { 
       int y = calculate(x); 
       weight.add(y); 
      }); 

System.out.println(weight); // 54 

Dann gibt es das Problem der randomizer, die Sie für diese wählen gehen: get_random_node_from(Graph). Sie müssen in der Tat eine zufällige Node bekommen, aber zur gleichen Zeit müssen Sie bekommen alle von ihnen genau einmal. Aber Sie brauchen es vielleicht nicht, wenn Sie flatten alle Knoten in eine einzige List sagen können.

Das Problem hierbei ist, dass Graphen werden in der Regel in einer rekursiven Weise durchlaufen, Sie wissen nicht, die genaue Größe davon:

while(parent.hasChildren) { 
    traverse children and so on... 
} 

Diese schlechte unter Streams parallelisieren wird, können Sie sich in Spliterators#spliteratorUnknownSize suchen. Es wird arithmetisch von 1024 wachsen; deshalb mein Vorschlag, die Knoten zu einer einzigen Liste mit bekannter Größe zu verflachen; das wird viel besser parallelisieren.