Parallelisierung zweier BigInteger-Funktionen

[thomas235]

Hallo zusammen,

ich arbeite zurzeit an einem Programm, das 2 mal hintereinander die Methode BigInteger.probablePrime aufruft. Ich initialisiere diese mit einer SecureRandom Instanz und einer relativ großen Bitlänge (> 2048 Bit).
Demnach ist die Ausführung entsprechend langsam.
Also meine Frage: ist es möglich die probablePrime Methode an sich zu parallelisieren?

Falls nein: kann ich die beiden Methoden wenigstens in 2 verschiedenen Threads ausführen lassen und wie?
meine Idee:

            Thread t1 = new Thread(new Runnable() {

                @Override
                public void run() {
                    p1 = BigInteger.probablePrime(bitLength, rnd);
                }
            });
            t1.start();
            Thread t2 = new Thread(new Runnable() {

                @Override
                public void run() {
                    p2 = BigInteger.probablePrime(bitLength, rnd);
                }
            });
            t2.start();

Problem: woran merke ich, dass beide Primzahlen berechnet sind?

gruß thomas

 

[Ark]

Problem: woran merke ich, dass beide Primzahlen berechnet sind?

Daran, dass es nach [c]Thread.join()[/c] (siehe API-Doku) weitergeht.

t1.join();
t2.join();
// jetzt ist alles berechnet

Ark

 

[thomas235]

Danke

bin noch nicht so erfahren mit Threads
immerhin hab ich jetzt die Ausführungszeit schonmal halbiert

gibt es auch eine Möglichkeit die Methode probablePrime() selbst zu parallelisieren?

gruß thomas235

 

[SlaterB]

abgesehen davon dass ich wohl nicht genau definieren/ verstehen könnte was du unter 'eine Methode parallelisieren' meinst, dürfte gelten:
nein, das geht nicht (außer vielleicht mit ganz verrücken Dingen wie AOP) und ist auch normalerweise nicht nötig,

lasse die Methode einfach nur rechnen, erstelle eine neue Methode irgendwo probablePrimeXY(), die probablePrime() aufruft und drumherum noch anderes macht,
wie man allerdings an deinem Aufbau sieht, ist es mit einer einzelnen Methode wohl kaum getan,
was genau soll die Methode machen? selbst wenn sie einen neuen Thread startet, wie geht es weiter,
kehrt sie sofort zurück/ was gibt sie zurück?

wenn sie auf das Ende des gestarteten Threads warten müsste, wäre es doch nicht anders als direkt probablePrime() auszuführen,
man muss schon mehrere Threads starten und auf die Ergebnisse warten, ein größerer Verbund an Arbeit


edit:
ach ja, vielleicht meinst du die interne Berechnung, den Suchzahlraum aufsplitten usw.

 

[Empire Phoenix]

Statt zwei threads einfach nen ThreadPoolExecutor mit processoranzalh nehmen (unter der annahme das du mehr als nur zwei tests machst. Dann skaliert es immerhin schonmal schön über multicores.

 

[thomas235]

Die Methode soll 2 große Primzahlen wählen, die zum Diffie-Hellman Schlüsselaustauschprotokoll gebraucht werden.
Diese Berechnung (also die Aufrufe der Methoden probablePrime()) nimmt mit Abstand den größten Teil der Zeit in Anspruch (sonstige Berechnungen nur ca. eine Sekunde).
Ich bin nun aber zu dem Schluss gekommen, dass die Parallelisierung der Methode BigInteger.probablePrime() einen Eingriff in deren Implementierung erfordern würde.

gruß thomas235

 

[Marco13]

Oder eine Neuimplementierung. Notfalls mit Copy & Paste aus BigInteger.java Aber .. BigInteger an sich ist AFAIR ziemlich unperformant, es gibt sicher Bibliotheken für große Ganzzahlen die schneller sind...