Der schnellste Weg, um Eigenpaare einer kleinen unsymmetrischen Matrix auf einer GPU im gemeinsamen Speicher zu finden

Ich habe ein Problem, bei dem ich alle positiven (wie im Eigenwert positiv ist) Eigenpaare einer kleinen (normalerweise kleiner als 60x60) unsymmetrischen Matrix finden muss. Ich kann aufhören zu berechnen, wenn der Eigenwert kleiner als ein bestimmter Schwellenwert ist. Ich weiß, dass die Eigenwerte real sind. Irgendwelche Vorschläge zu Algorithmen, mit denen ich versuchen könnte, die beste Leistung herauszuholen? Ich muss mehrere tausend dieser Zerlegungen durchführen, daher ist Geschwindigkeit wichtig.

Danke im Voraus.

EDIT: Ich muss dies auf der GPU im Shared Memory tun. Die Matrizen sind auch nicht unbedingt gleich groß. Im Moment sind mir keine Bibliotheken bekannt, die dies tun. Vorschläge von Algorithmen, die für das Problem gut geeignet wären, wären willkommen.

performance eigensystem gpu Kantoku
quelle

Wenn ich es richtig verstanden habe, haben Sie einen CUDA-Kernel, der Tausende kleiner Matrizen im gemeinsamen Speicher berechnet, und Sie sind nicht bereit, sie in den globalen Speicher zu kopieren. Bevor Sie versuchen, eine Antwort zu geben, müssen einige Punkte geklärt werden. In CUDA ist die Lebensdauer des gemeinsam genutzten Speichers an die Blocklebensdauer gebunden: Wie viele Threads müssen für jede Matrix zerlegt werden? Ist extreme Leistung wirklich wichtig? (Wie sind die erwarteten Eigenwertextraktionszeiten im Vergleich zu den Matrixgenerierungszeiten?) Basierend auf welchem Argument wissen Sie, dass das Eigensystem real ist? Kann das Eigensystem defekt sein?

Stefano M

Hallo Stefano und danke für deinen Kommentar. Im Moment werde ich das Vielfache der Warp-Größe haben, das der Dimension der Matrix am nächsten kommt, die ich zerlegen möchte. Die Matrixgenerierungszeiten variieren stark, und es gibt Fälle, in denen die Matrixgenerierungszeit teurer ist, aber es gibt viele Situationen, in denen die Matrixgenerierungszeit kürzer als die Zerlegung ist. Ich weiß, dass die Eigenwerte aufgrund der Art und Weise, wie die Matrix erzeugt wird, real sind. Ich möchte hier lieber nicht auf die Details eingehen, da dies die ursprüngliche Frage beeinträchtigen würde. Schließlich kann das System defekt sein.

Kantoku

Antworten:

Ohne viel zu suchen empfehle ich Ihnen, sich die MAGMA- Bibliothek anzusehen . Frei verfügbarer Code mit kontinuierlicher Unterstützung. NVIDIA erkannte MAGMA als "Durchbruch bei Lösern für Eigenwertprobleme" an.

Es gibt auch eine CULA- Bibliothek, bei der es sich im Allgemeinen um ein kommerzielles Produkt handelt, obwohl sie kürzlich für den akademischen Gebrauch kostenlos zur Verfügung gestellt wurde (siehe Details hier ).

Alexander
quelle

Vielen Dank für Ihre Antwort Alexander. Ich habe mir zuvor beide Bibliotheken angesehen, und soweit ich weiß, werden die Funktionen vom Host aufgerufen, und der Speicher muss sich im globalen Speicher befinden. Ich glaube, der Aufwand wäre zu hoch, um die Verwendung zu rechtfertigen. Alle diese Matrizen werden im gemeinsamen Speicher generiert, im Kernel verwendet und dann verworfen. Ich möchte sie dort behalten, ohne sie wieder in den globalen Speicher stellen zu müssen. Selbst wenn ich sie dorthin schieben würde, würde es immer noch das Problem geben, viele Kernelfunktionen vom Host aufzurufen (wenn auch in mehreren Streams).

Kantoku

@Kantoku, ja, diese Bibliotheken sind allgemeiner und speichern die gesamte Matrix im globalen Speicher. Wenn sich Ihre Matrizen im gemeinsam genutzten Speicher befinden, kann nur ein SM daran arbeiten, nicht wahr? Die Implementierung von EVD sollte daher recht einfach sein.

Alexander

Ja, das würde ich mir vorstellen. Deshalb habe ich nach Algorithmen gesucht, die für die jeweilige Situation geeignet sind. Ich bin nicht allzu vertraut mit nicht symmetrischen evd, also habe ich nach Vorschlägen gesucht.

Kantoku

@ Kantoku (und Alexander). Nicht symmetrische EVDs sind selbst im sequentiellen Fall alles andere als einfach. Es ist immer noch ein aktives Forschungsgebiet.

Jack Poulson

@JackPoulson Ah ja, Sie haben Recht, aber ich (und ich nehme auch Alexander an) meinte, dass es einfach wäre, einen etablierten Algorithmus auf das Problem anzuwenden, da es viele Vereinfachungen gibt, die vorgenommen werden können, wenn wir die Größe und die Natur berücksichtigen der Matrix in Betracht. Das Problem ist: welcher Algorithmus.

Kantoku

Verwenden Sie die Funktionen in LAPACK. Es ist unwahrscheinlich, dass Sie sie in Ihrer eigenen Implementierung übertreffen können.

Wolfgang Bangerth
quelle

Hallo Wolfgang. Vielen Dank für die Antwort, aber ich beabsichtige, dies auf einer GPU mit CUDA und für mehrere Tausend dieser winzigen Matrizen (wobei jeder Block die Zerlegung einer einzelnen Matrix handhabt) zu implementieren, und die Matrizen sind nicht unbedingt gleich groß Etwas, das Shared Memory verwendet, scheint meine einzige Wahl zu sein. Irgendeine Idee, welcher Algorithmus für diese Arten von Matrizen am besten geeignet wäre? PS Danke für den Deal. II Vorlesungen, die Sie im letzten Semester bei KAUST gehalten haben. Ich habe sie genossen :)

Kantoku

@Kantoku Sie sollten diese Details in Ihre Frage aufnehmen, sonst ist es irreführend.

Alexander

@ Alexander Ich habe die Frage mit weiteren Details aktualisiert. Danke für den Vorschlag!

Kantoku

@Kantoku: GPUs sind etwas jenseits meines Bereichs, aber ich bin sicher, dass es bereits Bibliotheken gibt, die das tun, was Sie wollen (und tatsächlich sehe ich, dass andere Antworten bereits auf sie verweisen). Schön zu hören, dass dir mein Unterricht gefallen hat!

Wolfgang Bangerth