Heim > Web-Frontend > js-Tutorial > LAPACK in Ihrem Webbrowser

LAPACK in Ihrem Webbrowser

Susan Sarandon
Freigeben: 2024-12-30 10:05:12
Original
123 Leute haben es durchsucht

Dieser Beitrag wurde ursprünglich im Blog von Quansight Labs veröffentlicht und wurde hier mit Genehmigung von Quansight geändert und erneut veröffentlicht.

Webanwendungen entwickeln sich schnell zu einer neuen Grenze für leistungsstarke wissenschaftliche Berechnungen und KI-gestützte Endbenutzererlebnisse. Grundlage der ML/KI-Revolution ist die lineare Algebra, ein Zweig der Mathematik, der sich mit linearen Gleichungen und deren Darstellungen in Vektorräumen und über Matrizen beschäftigt. LAPACK („Linear Algebra Package“) ist eine grundlegende Softwarebibliothek für numerische lineare Algebra, die robuste, kampferprobte Implementierungen gängiger Matrixoperationen bereitstellt . Obwohl LAPACK ein grundlegender Bestandteil der meisten Programmiersprachen und Bibliotheken für numerische Computer ist, muss eine umfassende, qualitativ hochwertige LAPACK-Implementierung, die auf die besonderen Einschränkungen des Webs zugeschnitten ist, noch verwirklicht werden. Das ist...bis jetzt.

Anfang dieses Jahres hatte ich das große Glück, ein Sommerpraktikant bei Quansight Labs zu sein, der gemeinnützigen Abteilung von Quansight und führend im wissenschaftlichen Python-Ökosystem. Während meines Praktikums habe ich daran gearbeitet, anfängliche LAPACK-Unterstützung zu stdlib hinzuzufügen, einer grundlegenden Bibliothek für wissenschaftliche Berechnungen, die in C und JavaScript geschrieben und für die Verwendung in Webbrowsern und anderen webnativen Umgebungen wie Node.js und Deno optimiert ist. In diesem Blogbeitrag bespreche ich meine Reise, einige erwartete und unerwartete (!) Herausforderungen und den weiteren Weg. Ich hoffe, dass diese Arbeit mit etwas Glück einen entscheidenden Baustein dafür liefert, Webbrowser zu einer erstklassigen Umgebung für numerische Berechnungen und maschinelles Lernen zu machen und eine Zukunft mit leistungsfähigeren KI-gestützten Webanwendungen vorwegzunehmen.

Klingt interessant? Auf geht's!

Was ist stdlib?

Leser dieses Blogs, die mit LAPACK vertraut sind, sind wahrscheinlich nicht so genau mit der wilden Welt der Webtechnologien vertraut. Für diejenigen, die aus der Welt der numerischen und wissenschaftlichen Berechnungen kommen und mit dem wissenschaftlichen Python-Ökosystem vertraut sind, kann man sich stdlib am einfachsten als eine Open-Source-Bibliothek für wissenschaftliche Berechnungen nach dem Vorbild von NumPy und SciPy vorstellen. Es bietet mehrdimensionale Array-Datenstrukturen und zugehörige Routinen für Mathematik, Statistik und lineare Algebra, verwendet jedoch JavaScript anstelle von Python als primäre Skriptsprache. Daher ist stdlib auf das Web-Ökosystem und seine Anwendungsentwicklungsparadigmen ausgerichtet. Dieser Fokus erfordert einige interessante Design- und Projektarchitekturentscheidungen, die stdlib im Vergleich zu traditionelleren Bibliotheken, die für numerische Berechnungen entwickelt wurden, ziemlich einzigartig machen.

Um NumPy als Beispiel zu nehmen: NumPy ist eine einzelne monolithische Bibliothek, in der alle ihre Komponenten, abgesehen von optionalen Abhängigkeiten von Drittanbietern wie OpenBLAS, eine einzige, unteilbare Einheit bilden. Man kann nicht einfach NumPy-Routinen zur Array-Manipulation installieren, ohne NumPy vollständig zu installieren. Wenn Sie eine Anwendung bereitstellen, die nur das ndarray-Objekt von NumPy und einige seiner Manipulationsroutinen benötigt, bedeutet die Installation und Bündelung von NumPy insgesamt, dass eine beträchtliche Menge „toter Code“ einbezogen wird. Im Webentwicklungsjargon würden wir sagen, dass NumPy nicht „baumschüttelbar“ ist. Für eine normale NumPy-Installation bedeutet dies mindestens 30 MB Festplattenspeicher und mindestens 15 MB Festplattenspeicher für einen benutzerdefinierten Build, der alle Debug-Anweisungen ausschließt. Für SciPy können diese Zahlen auf 130 MB bzw. 50 MB ansteigen. Es erübrigt sich zu erwähnen, dass die Auslieferung einer 15-MB-Bibliothek in einer Webanwendung für nur wenige Funktionen ein Kinderspiel ist, insbesondere für Entwickler, die Webanwendungen auf Geräten mit schlechter Netzwerkkonnektivität oder Speicherbeschränkungen bereitstellen müssen.

Angesichts der besonderen Einschränkungen bei der Entwicklung von Webanwendungen verfolgt stdlib beim Design einen Bottom-up-Ansatz, bei dem jede Funktionseinheit unabhängig von nicht verwandten und ungenutzten Teilen der Codebasis installiert und genutzt werden kann. Durch den Einsatz einer zerlegbaren Softwarearchitektur und radikaler Modularität bietet stdlib Benutzern die Möglichkeit, genau das zu installieren und zu verwenden, was sie benötigen, mit wenig bis gar keinem überschüssigen Code über einen gewünschten Satz von APIs und deren expliziten Abhängigkeiten hinaus, wodurch ein geringerer Speicherbedarf gewährleistet wird Größen und schnellere Bereitstellung.

Angenommen, Sie arbeiten mit zwei Matrizenstapeln (d. h. zweidimensionalen Scheiben dreidimensionaler Würfel) und möchten jede zweite Scheibe auswählen und die übliche BLAS-Operation y = a * x ausführen. Dabei sind x und y ndarrays und a eine Skalarkonstante. Um dies mit NumPy zu tun, müssen Sie zunächst NumPy vollständig installieren

pip install numpy
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren

und führen Sie dann die verschiedenen Vorgänge aus

# Import all of NumPy:
import numpy as np

# Define arrays:
x = np.asarray(...)
y = np.asarray(...)

# Perform operation:
y[::2,:,:] += 5.0 * x[::2,:,:]
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren

Mit stdlib können Sie nicht nur das Projekt als monolithische Bibliothek installieren, sondern auch die verschiedenen Funktionseinheiten als separate Pakete installieren

npm install @stdlib/ndarray-fancy @stdlib/blas-daxpy
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren

und führen Sie dann die verschiedenen Vorgänge aus

// Individually import desired functionality:
import FancyArray from '@stdlib/ndarray-fancy';
import daxpy from '@stdlib/blas-daxpy';

// Define ndarray meta data:
const shape = [4, 4, 4];
const strides = [...];
const offset = 0;

// Define arrays using a "lower-level" fancy array constructor:
const x = new FancyArray('float64', [...], shape, strides, offset, 'row-major');
const y = new FancyArray('float64', [...], shape, strides, offset, 'row-major');

// Perform operation:
daxpy(5.0, x['::2,:,:'], y['::2,:,:']);
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren

Wichtig ist, dass Sie nicht nur jedes der über 4.000 Pakete von stdlib unabhängig installieren können, sondern Sie können auch jedes dieser Pakete reparieren, verbessern und neu mischen, indem Sie ein zugehöriges GitHub-Repository forken (siehe z. B. @stdlib/ndarray-fancy ). Durch die Definition expliziter Abstraktionsebenen und Abhängigkeitsbäume bietet Ihnen stdlib die Freiheit, die richtige Abstraktionsebene für Ihre Anwendung auszuwählen. In mancher Hinsicht ist es eine einfache – und, wenn Sie mit dem herkömmlichen Design wissenschaftlicher Softwarebibliotheken vertraut sind, vielleicht unorthodoxe – Idee, aber wenn sie eng in die Webplattform integriert ist, hat sie wirkungsvolle Konsequenzen und schafft aufregende neue Möglichkeiten!

Was ist mit WebAssembly?

Okay, vielleicht ist Ihr Interesse geweckt; stdlib scheint faszinierend. Aber was hat das mit LAPACK in Webbrowsern zu tun? Nun, eines unserer Ziele im vergangenen Sommer war es, das stdlib-Ethos – kleine, eng begrenzte Pakete, die eine Sache tun und eine Sache gut machen – anzuwenden, um LAPACK ins Web zu bringen.

Aber warte, sagst du! Das ist ein extremes Unterfangen. LAPACK ist mit etwa 1.700 Routinen umfangreich, und selbst die Umsetzung von 10 % davon innerhalb eines angemessenen Zeitrahmens ist eine große Herausforderung. Wäre es nicht besser, LAPACK einfach in WebAssembly zu kompilieren, einem tragbaren Kompilierungsziel für Programmiersprachen wie C, Go und Rust, das die Bereitstellung im Web ermöglicht, und Schluss damit zu machen?

Leider gibt es bei diesem Ansatz mehrere Probleme.

  1. Das Kompilieren von Fortran zu WebAssembly ist immer noch ein Bereich der aktiven Entwicklung (siehe 1, 2, 3, 4 und 5). Zum Zeitpunkt dieses Beitrags bestand ein gängiger Ansatz darin, Fortran mit f2c in C zu kompilieren und dann einen separaten Kompilierungsschritt durchzuführen, um C in WebAssembly zu konvertieren. Dieser Ansatz ist jedoch problematisch, da f2c nur Fortran 77 vollständig unterstützt und der generierte Code umfangreiche Patches erfordert. Derzeit wird an der Entwicklung eines LLVM-basierten Fortran-Compilers gearbeitet, es bestehen jedoch weiterhin Lücken und komplexe Toolchains.
  2. Wie oben in der Diskussion über monolithische Bibliotheken in Webanwendungen angedeutet, ist die Größe von LAPACK Teil des Problems. Selbst wenn das Kompilierungsproblem gelöst ist, bedeutet das Einfügen einer einzigen WebAssembly-Binärdatei, die das gesamte LAPACK enthält, in eine Webanwendung, die nur eine oder zwei LAPACK-Routinen verwenden muss, erheblichen toten Code, was zu langsameren Ladezeiten und einem erhöhten Speicherverbrauch führt.
  3. Während man versuchen könnte, einzelne LAPACK-Routinen in eigenständige WebAssembly-Binärdateien zu kompilieren, könnte dies zu einer Aufblähung der Binärdateien führen, da mehrere eigenständige Binärdateien möglicherweise doppelten Code aus gemeinsamen Abhängigkeiten enthalten. Um die binäre Aufblähung zu verringern, könnte man versuchen, eine Modulaufteilung durchzuführen. In diesem Szenario gliedert man zunächst allgemeine Abhängigkeiten in eine eigenständige Binärdatei mit gemeinsam genutztem Code aus und generiert dann separate Binärdateien für einzelne APIs. Obwohl dies in manchen Fällen sinnvoll ist, kann dies schnell unhandlich werden, da dieser Ansatz die Verknüpfung einzelner WebAssembly-Module zur Ladezeit erfordert, indem die Exporte eines oder mehrerer Module mit den Importen eines oder mehrerer anderer Module zusammengefügt werden. Dies kann nicht nur mühsam sein, sondern dieser Ansatz führt auch zu Leistungseinbußen, da WebAssembly-Routinen beim Aufruf importierter Exporte nun in JavaScript wechseln müssen, anstatt in WebAssembly zu bleiben. Klingt komplex? Das ist es!
  4. Abgesehen von WebAssembly-Modulen, die ausschließlich mit skalaren Eingabeargumenten arbeiten (z. B. den Sinus einer einzelnen Zahl berechnen), muss jede WebAssembly-Modulinstanz mit WebAssembly-Speicher verknüpft sein, der in festen Schritten von 64 KB (d. h. einer „Seite“) zugewiesen wird "). Und was noch wichtiger ist: Zum Zeitpunkt dieses Blogbeitrags kann der WebAssembly-Speicher nur wachsen und niemals schrumpfen. Da es derzeit keinen Mechanismus zum Freigeben von Speicher für einen Host gibt, kann der Speicherbedarf einer WebAssembly-Anwendung nur zunehmen. Diese beiden Aspekte zusammen erhöhen die Wahrscheinlichkeit der Zuweisung von Speicher, der nie verwendet wird, und die Häufigkeit von Speicherlecks.
  5. Schließlich ist WebAssembly zwar leistungsstark, erfordert aber eine steilere Lernkurve und einen komplexeren Satz sich häufig schnell entwickelnder Toolchains. In Endbenutzeranwendungen führt die Schnittstelle zwischen JavaScript – einer webnativen, dynamisch kompilierten Programmiersprache – und WebAssembly zusätzlich zu einer erhöhten Komplexität, insbesondere wenn eine manuelle Speicherverwaltung durchgeführt werden muss.

Um den letzten Punkt zu veranschaulichen, kehren wir zur BLAS-Routine daxpy zurück, die die Operation y = a*x y ausführt und wobei x und y Schrittvektoren und a eine Skalarkonstante sind. Bei einer Implementierung in C könnte eine grundlegende Implementierung wie das folgende Codefragment aussehen.

pip install numpy
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren

Nach der Kompilierung in WebAssembly und dem Laden der WebAssembly-Binärdatei in unsere Webanwendung müssen wir eine Reihe von Schritten ausführen, bevor wir die c_daxpy-Routine aus JavaScript aufrufen können. Zuerst müssen wir ein neues WebAssembly-Modul instanziieren.

# Import all of NumPy:
import numpy as np

# Define arrays:
x = np.asarray(...)
y = np.asarray(...)

# Perform operation:
y[::2,:,:] += 5.0 * x[::2,:,:]
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren

Als nächstes müssen wir den Modulspeicher definieren und eine neue WebAssembly-Modulinstanz erstellen.

npm install @stdlib/ndarray-fancy @stdlib/blas-daxpy
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren

Nachdem wir eine Modulinstanz erstellt haben, können wir nun die exportierte BLAS-Routine aufrufen. Wenn Daten jedoch außerhalb des Modulspeichers definiert werden, müssen wir diese Daten zunächst in die Speicherinstanz kopieren und dies immer in Little-Endian-Byte-Reihenfolge tun.

// Individually import desired functionality:
import FancyArray from '@stdlib/ndarray-fancy';
import daxpy from '@stdlib/blas-daxpy';

// Define ndarray meta data:
const shape = [4, 4, 4];
const strides = [...];
const offset = 0;

// Define arrays using a "lower-level" fancy array constructor:
const x = new FancyArray('float64', [...], shape, strides, offset, 'row-major');
const y = new FancyArray('float64', [...], shape, strides, offset, 'row-major');

// Perform operation:
daxpy(5.0, x['::2,:,:'], y['::2,:,:']);
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren

Da nun die Daten in den Modulspeicher geschrieben wurden, können wir die c_daxpy-Routine aufrufen.

void c_daxpy(const int N, const double alpha, const double *X, const int strideX, double *Y, const int strideY) {
    int ix;
    int iy;
    int i;
    if (N <= 0) {
        return;
    }
    if (alpha == 0.0) {
        return;
    }
    if (strideX < 0) {
        ix = (1-N) * strideX;
    } else {
        ix = 0;
    }
    if (strideY < 0) {
        iy = (1-N) * strideY;
    } else {
        iy = 0;
    }
    for (i = 0; i < N; i++) {
        Y[iy] += alpha * X[ix];
        ix += strideX;
        iy += strideY;
    }
    return;
}
Nach dem Login kopieren
Nach dem Login kopieren

Und schließlich, wenn wir die Ergebnisse zur Visualisierung oder weiteren Analyse an eine Downstream-Bibliothek ohne Unterstützung für WebAssembly-Speicher-„Zeiger“ (d. h. Byte-Offsets) wie D3 übergeben müssen, müssen wir Daten aus dem Modul kopieren Speicher zurück zum ursprünglichen Ausgabearray.

const binary = new UintArray([...]);

const mod = new WebAssembly.Module(binary);
Nach dem Login kopieren
Nach dem Login kopieren

Allein die Berechnung von y = a*x y ist eine Menge Arbeit. Vergleichen Sie es im Gegensatz dazu mit einer einfachen JavaScript-Implementierung, die wie das folgende Code-Snippet aussehen könnte.

// Initialize 10 pages of memory and allow growth to 100 pages:
const mem = new WebAssembly.Memory({
    'initial': 10,  // 640KiB, where each page is 64KiB
    'maximum': 100  // 6.4MiB
});

// Create a new module instance:
const instance = new WebAssembly.Instance(mod, {
    'env': {
        'memory': mem
    }
});
Nach dem Login kopieren

Mit der JavaScript-Implementierung können wir daxpy dann direkt mit unseren extern definierten Daten aufrufen, ohne die im obigen WebAssembly-Beispiel erforderliche Datenverschiebung.

// External data:
const xdata = new Float64Array([...]);
const ydata = new Float64Array([...]);

// Specify a vector length:
const N = 5;

// Specify vector strides (in units of elements):
const strideX = 2;
const strideY = 4;

// Define pointers (i.e., byte offsets) for storing two vectors:
const xptr = 0;
const yptr = N * 8; // 8 bytes per double

// Create a DataView over module memory:
const view = new DataView(mem.buffer);

// Resolve the first indexed elements in both `xdata` and `ydata`:
let offsetX = 0;
if (strideX < 0) {
    offsetX = (1-N) * strideX;
}
let offsetY = 0;
if (strideY < 0) {
    offsetY = (1-N) * strideY;
}

// Write data to the memory instance:
for (let i = 0; i < N; i++) {
    view.setFloat64(xptr+(i*8), xdata[offsetX+(i*strideX)], true);
    view.setFloat64(yptr+(i*8), ydata[offsetY+(i*strideY)], true);
}
Nach dem Login kopieren

Zumindest in diesem Fall ist der WebAssembly-Ansatz nicht nur weniger ergonomisch, sondern es gibt auch, wie angesichts der erforderlichen Datenbewegung zu erwarten ist, negative Auswirkungen auf die Leistung, wie in der folgenden Abbildung dargestellt.

LAPACK in your web browser

Abbildung 1: Leistungsvergleich der C-, JavaScript- und WebAssembly (Wasm)-Implementierungen von stdlib für die BLAS-Routine daxpy für zunehmende Array-Längen (x-Achse). Im Wasm (Kopie)-Benchmark werden Eingabe- und Ausgabedaten in den Wasm-Speicher und aus dem Wasm-Speicher kopiert, was zu einer schlechteren Leistung führt.

In der Abbildung oben zeige ich einen Leistungsvergleich der C-, JavaScript- und WebAssembly (Wasm)-Implementierungen von stdlib für die BLAS-Routine daxpy für zunehmende Array-Längen, wie entlang der x-Achse aufgelistet. Die y-Achse zeigt eine normalisierte Rate relativ zu einer Baseline-C-Implementierung. Im Wasm-Benchmark werden Eingabe- und Ausgabedaten direkt im Speicher des WebAssembly-Moduls zugewiesen und bearbeitet, und im Wasm-Benchmark (Kopieren) werden Eingabe- und Ausgabedaten in den und aus dem Speicher des WebAssembly-Moduls kopiert, wie oben erläutert. Aus der Tabelle können wir Folgendes erkennen:

  1. Im Allgemeinen kann JavaScript-Code, wenn er sorgfältig geschrieben wird, dank hochoptimierter Just-in-Time-Compiler (JIT) nur zwei- bis dreimal langsamer ausgeführt werden als nativer Code. Dieses Ergebnis ist beeindruckend für eine lose typisierte, dynamisch kompilierte Programmiersprache und bleibt, zumindest für Daxpy, über verschiedene Array-Längen hinweg konsistent.
  2. Wenn die Datengröße und damit die in einem WebAssembly-Modul verbrachte Zeit zunehmen, kann WebAssembly eine nahezu native (~1,5-fache) Geschwindigkeit erreichen. Dieses Ergebnis stimmt allgemeiner mit der erwarteten WebAssembly-Leistung überein.
  3. Während WebAssembly nahezu native Geschwindigkeit erreichen kann, können sich Datenbewegungsanforderungen negativ auf die Leistung auswirken, wie bei Daxpy beobachtet. In solchen Fällen kann eine gut gestaltete JavaScript-Implementierung, die solche Anforderungen vermeidet, die gleiche, wenn nicht sogar bessere Leistung erzielen, wie es bei daxpy der Fall ist.

Insgesamt kann WebAssembly Leistungsverbesserungen bieten; Die Technologie ist jedoch kein Allheilmittel und muss sorgfältig eingesetzt werden, um die gewünschten Vorteile zu erzielen. Und selbst wenn eine überlegene Leistung geboten wird, müssen solche Gewinne gegen die Kosten erhöhter Komplexität, potenziell größerer Paketgrößen und komplexerer Toolchains abgewogen werden. Für viele Anwendungen reicht eine einfache JavaScript-Implementierung vollkommen aus.

Radikale Modularität

Nachdem ich nun den Fall angestrengt habe, einfach das gesamte LAPACK zu WebAssembly zu kompilieren und Schluss zu machen, wo bleibt uns das? Nun, wenn wir das stdlib-Ethos annehmen wollen, brauchen wir eine radikale Modularität.

Um radikale Modularität anzunehmen, muss man erkennen, dass das Beste in hohem Maße kontextabhängig ist und dass Entwickler je nach den Anforderungen und Einschränkungen von Benutzeranwendungen die Flexibilität benötigen, die richtige Abstraktion auszuwählen. Wenn ein Entwickler eine Node.js-Anwendung schreibt, bedeutet dies möglicherweise die Bindung an hardwareoptimierte Bibliotheken wie OpenBLAS, Intel MKL oder Apple Accelerate, um eine bessere Leistung zu erzielen. Wenn ein Entwickler eine Webanwendung bereitstellt, die einen kleinen Satz numerischer Routinen benötigt, ist JavaScript wahrscheinlich das richtige Werkzeug für diese Aufgabe. Und wenn ein Entwickler an einer großen, ressourcenintensiven WebAssembly-Anwendung arbeitet (z. B. für die Bildbearbeitung oder eine Gaming-Engine), ist es von größter Bedeutung, einzelne Routinen einfach als Teil der größeren Anwendung kompilieren zu können. Kurz gesagt, wir wollen ein radikal modulares LAPACK.

Meine Mission bestand darin, den Grundstein für ein solches Unterfangen zu legen, die Hürden zu beseitigen und die Lücken zu finden und uns hoffentlich der leistungsstarken linearen Algebra im Web ein paar Schritte näher zu bringen. Doch wie sieht radikale Modularität aus? Alles beginnt mit der grundlegenden Funktionseinheit, dem Paket.

Jedes Paket in stdlib ist ein eigenständiges Ding, das kolokalisierte Tests, Benchmarks, Beispiele, Dokumentation, Build-Dateien und zugehörige Metadaten (einschließlich der Aufzählung etwaiger Abhängigkeiten) enthält und eine klare API-Oberfläche mit der Außenwelt definiert . Um LAPACK-Unterstützung zu stdlib hinzuzufügen, müssen Sie für jede LAPACK-Routine ein separates eigenständiges Paket mit der folgenden Struktur erstellen:

pip install numpy
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren

Kurz,

  • Benchmark: ein Ordner mit Mikro-Benchmarks zur Bewertung der Leistung im Vergleich zu einer Referenzimplementierung (d. h. Referenz-LAPACK).
  • docs: ein Ordner mit Hilfsdokumentation, einschließlich REPL-Hilfetext und TypeScript-Deklarationen, die typisierte API-Signaturen definieren.
  • Beispiele: ein Ordner mit ausführbarem Demonstrationscode, der nicht nur als Dokumentation dient, sondern Entwicklern auch bei der Überprüfung des Implementierungsverhaltens hilft.
  • include: ein Ordner mit C-Header-Dateien.
  • lib: ein Ordner mit JavaScript-Quellimplementierungen, wobei index.js als Paketeinstiegspunkt dient und andere *.js-Dateien interne Implementierungsmodule definieren.
  • src: ein Ordner mit C- und Fortran-Quellimplementierungen. Jedes modulare LAPACK-Paket sollte eine leicht modifizierte Fortran-Referenzimplementierung enthalten (F77 für Freiform-Fortran). C-Dateien umfassen eine einfache C-Implementierung, die der Fortran-Referenzimplementierung folgt, einen Wrapper zum Aufrufen der Fortran-Referenzimplementierung, einen Wrapper zum Aufrufen hardwareoptimierter Bibliotheken (z. B. OpenBLAS) in serverseitigen Anwendungen und eine native Bindung zum Aufrufen in kompilierte Dateien C von JavaScript in Node.js oder einer kompatiblen serverseitigen JavaScript-Laufzeitumgebung.
  • test: ein Ordner mit Komponententests zum Testen des erwarteten Verhaltens sowohl in JavaScript als auch in nativen Implementierungen. Tests für native Implementierungen werden in JavaScript geschrieben und nutzen die native Bindung für die Zusammenarbeit zwischen JavaScript und C/Fortran.
  • binding.gyp/include.gypi: Build-Dateien zum Kompilieren der nativen Node.js-Add-ons, die eine Brücke zwischen JavaScript und nativem Code bilden.
  • manifest.json: eine Konfigurationsdatei für die interne Verwaltung von C- und Fortran-kompilierten Quelldateipaketen von stdlib.
  • package.json: eine Datei mit Paketmetadaten, einschließlich der Aufzählung externer Paketabhängigkeiten und einem Pfad zu einer einfachen JavaScript-Implementierung zur Verwendung in browserbasierten Webanwendungen.
  • README.md: eine Datei mit der Hauptdokumentation eines Pakets, die API-Signaturen und Beispiele für JavaScript- und C-Schnittstellen enthält.

Angesichts der anspruchsvollen Dokumentations- und Testanforderungen von stdlib ist das Hinzufügen von Unterstützung für jede Routine ein ordentlicher Arbeitsaufwand, aber das Endergebnis ist robuster, qualitativ hochwertiger und vor allem modularer Code, der als Grundlage für wissenschaftliche Berechnungen geeignet ist im modernen Web. Aber genug mit den Vorrunden! Kommen wir zur Sache!

Ein mehrstufiger Ansatz

Aufbauend auf früheren Bemühungen, die BLAS-Unterstützung zu stdlib hinzuzufügen, haben wir uns entschieden, beim Hinzufügen der LAPACK-Unterstützung einen ähnlichen mehrstufigen Ansatz zu verfolgen, bei dem wir zunächst JavaScript-Implementierungen und die damit verbundenen Tests und Dokumentation priorisieren und dann, sobald Tests und Dokumentation vorhanden sind , Backfill-C- und Fortran-Implementierungen und alle damit verbundenen nativen Bindungen an hardwareoptimierte Bibliotheken. Dieser Ansatz ermöglicht es uns, sozusagen einige frühe Punkte auf den Tisch zu bringen, APIs schnell den Benutzern zugänglich zu machen, robuste Testverfahren und Benchmarks zu etablieren und potenzielle Möglichkeiten für Tools und Automatisierung zu untersuchen, bevor wir uns in die Tiefe der Build-Toolchains und der Leistung stürzen Optimierungen. Aber wo soll man überhaupt anfangen?

Um zu bestimmen, auf welche LAPACK-Routinen zuerst abgezielt werden soll, habe ich den Fortran-Quellcode von LAPACK analysiert, um ein Aufrufdiagramm zu erstellen. Dadurch konnte ich den Abhängigkeitsbaum für jede LAPACK-Routine ableiten. Mit dem Diagramm in der Hand führte ich dann eine topologische Sortierung durch, die mir dabei half, Routinen ohne Abhängigkeiten zu identifizieren, die unweigerlich Bausteine ​​für andere Routinen sein werden. Während ein Tiefenansatz, bei dem ich eine bestimmte High-Level-Routine auswähle und rückwärts arbeite, es mir ermöglichen würde, ein bestimmtes Feature zu landen, könnte ein solcher Ansatz dazu führen, dass ich beim Versuch, Routinen mit zunehmender Komplexität zu implementieren, stecken bleibe. Durch die Konzentration auf die „Blätter“ des Diagramms konnte ich häufig verwendete Routinen (d. h. Routinen mit hohen Ingraden) priorisieren und so meine Wirkung maximieren, indem ich die Möglichkeit freischaltete, später mehrere Routinen auf höherer Ebene bereitzustellen meine Bemühungen oder von anderen Mitwirkenden.

Mit meinem Plan in der Hand freute ich mich darauf, mich an die Arbeit zu machen. Für meine erste Routine habe ich dlaswp ausgewählt, das eine Reihe von Zeilenaustauschvorgängen auf einer allgemeinen rechteckigen Matrix gemäß einer bereitgestellten Liste von Pivot-Indizes durchführt und ein wichtiger Baustein für die LU-Zerlegungsroutinen von LAPACK ist. Und da begannen meine Herausforderungen...

Herausforderungen

Legacy-Fortran

Vor meinem Praktikum bei Quansight Labs habe ich regelmäßig an LFortran, einem modernen interaktiven Fortran-Compiler, der auf LLVM aufbaut, mitgewirkt (und bin es immer noch!), und ich war ziemlich sicher in meinen Fortran-Kenntnissen. Eine meiner ersten Herausforderungen bestand jedoch einfach darin, zu verstehen, was heute als „alter“ Fortran-Code gilt. Im Folgenden hebe ich drei anfängliche Hürden hervor.

Formatierung

LAPACK wurde ursprünglich in FORTRAN 77 (F77) geschrieben. Während die Bibliothek in Version 3.2 (2008) auf Fortran 90 verschoben wurde, bestehen in der Referenzimplementierung weiterhin alte Konventionen. Eine der sichtbarsten dieser Konventionen ist die Formatierung.

Entwickler, die F77-Programme schrieben, verwendeten dazu ein festes Formularlayout, das von Lochkarten übernommen wurde. Dieses Layout stellte strenge Anforderungen an die Verwendung von Zeichenspalten:

  • Kommentare, die eine ganze Zeile einnehmen, müssen mit einem Sonderzeichen (z. B. *, ! oder C) in der ersten Spalte beginnen.
  • Für Nicht-Kommentarzeilen müssen 1) die ersten fünf Spalten leer sein oder eine numerische Beschriftung enthalten, 2) Spalte sechs ist für Fortsetzungszeichen reserviert, 3) ausführbare Anweisungen müssen in Spalte sieben beginnen und 4) jeglicher Code darüber hinaus Spalte 72 wurde ignoriert.

Fortran 90 führte das Freiform-Layout ein, das die Beschränkungen der Spalten- und Zeilenlänge aufhob und sich entschied ! als Kommentarzeichen. Der folgende Codeausschnitt zeigt die Referenzimplementierung für die LAPACK-Routine dlacpy:

pip install numpy
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren

Der nächste Codeausschnitt zeigt dieselbe Routine, jedoch implementiert mit dem in Fortran 90 eingeführten Freiform-Layout.

# Import all of NumPy:
import numpy as np

# Define arrays:
x = np.asarray(...)
y = np.asarray(...)

# Perform operation:
y[::2,:,:] += 5.0 * x[::2,:,:]
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren

Wie zu beobachten ist, ist moderner Fortran-Code durch die Entfernung von Spaltenbeschränkungen und die Abkehr von der F77-Konvention, Spezifizierer in GROSSBUCHSTABEN zu schreiben, sichtbar konsistenter und damit besser lesbar.

Beschriftete Kontrollstrukturen

Eine weitere gängige Praxis in LAPACK-Routinen ist die Verwendung gekennzeichneter Kontrollstrukturen. Betrachten Sie beispielsweise den folgenden Codeausschnitt, in dem die Bezeichnung 10 mit einem entsprechenden CONTINUE übereinstimmen muss.

npm install @stdlib/ndarray-fancy @stdlib/blas-daxpy
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren

Fortran 90 machte diese Vorgehensweise überflüssig und verbesserte die Lesbarkeit des Codes, indem es erlaubte, end do zu verwenden, um eine do-Schleife zu beenden. Diese Änderung wird in der oben bereitgestellten Freiformversion von dlacpy angezeigt.

Arrays mit angenommener Größe

Um Flexibilität bei der Handhabung von Arrays unterschiedlicher Größe zu ermöglichen, arbeiten LAPACK-Routinen üblicherweise mit Arrays mit einer angenommenen Größe. In der obigen dlacpy-Routine wird die Eingabematrix A als zweidimensionales Array mit einer angenommenen Größe gemäß dem Ausdruck A(LDA, *) deklariert. Dieser Ausdruck deklariert, dass A eine LDA-Anzahl von Zeilen hat und verwendet * als Platzhalter, um anzugeben, dass die Größe der zweiten Dimension vom aufrufenden Programm bestimmt wird.

Eine Konsequenz der Verwendung von Arrays mit angenommener Größe ist, dass Compiler keine Grenzprüfung für die nicht angegebene Dimension durchführen können. Daher besteht die aktuelle Best Practice darin, explizite Schnittstellen und Arrays mit angenommener Form (z. B. A(LDA,:)) zu verwenden, um Speicherzugriffe außerhalb der Grenzen zu verhindern. Dies bedeutet, dass die Verwendung von Arrays mit angenommener Form problematisch sein kann, wenn Untermatrizen an andere Funktionen übergeben werden müssen, da hierfür ein Slicing erforderlich ist, was häufig dazu führt, dass Compiler interne Kopien von Array-Daten erstellen.

Migration auf Fortran 95

Unnötig zu erwähnen, dass es eine Weile gedauert hat, bis ich mich an die LAPACK-Konventionen gewöhnt und eine LAPACK-Denkweise angenommen habe. Da ich jedoch eher ein Purist bin, wollte ich, wenn ich sowieso Routinen portieren wollte, zumindest die Routinen, die ich portieren konnte, in ein moderneres Zeitalter bringen, in der Hoffnung, die Lesbarkeit des Codes und die zukünftige Wartung zu verbessern. Nachdem ich die Dinge mit den stdlib-Betreuern besprochen hatte, entschied ich mich für die Migration von Routinen auf Fortran 95, das zwar nicht die neueste und beste Fortran-Version war, aber die richtige Balance zwischen der Beibehaltung des Erscheinungsbilds der ursprünglichen Implementierungen und der Gewährleistung ( gut genug) Abwärtskompatibilität und Nutzung neuerer syntaktischer Funktionen.

Testabdeckung

Eines der Probleme bei der Verfolgung eines Bottom-up-Ansatzes zum Hinzufügen von LAPACK-Unterstützung besteht darin, dass explizite Unit-Tests für Dienstprogramme auf niedrigerer Ebene in LAPACK oft nicht vorhanden sind. Die Testsuite von LAPACK basiert weitgehend auf einer hierarchischen Testphilosophie, bei der davon ausgegangen wird, dass beim Testen von Routinen auf höherer Ebene sichergestellt wird, dass ihre abhängigen Routinen auf niedrigerer Ebene als Teil eines Gesamtworkflows ordnungsgemäß funktionieren. Man kann zwar argumentieren, dass die Konzentration auf Integrationstests gegenüber Unit-Tests für Routinen auf niedrigerer Ebene sinnvoll ist, da das Hinzufügen von Tests für jede Routine möglicherweise den Wartungsaufwand und die Komplexität des Test-Frameworks von LAPACK erhöhen könnte, aber das bedeutet, dass wir uns nicht ohne weiteres auf frühere Tests verlassen konnten Kunst für Unit-Tests und müssten selbst umfassende eigenständige Unit-Tests für jede Routine auf niedrigerer Ebene entwickeln.

Dokumentation

Ähnlich wie bei der Testabdeckung war es außerhalb von LAPACK selbst eine Herausforderung, reale, dokumentierte Beispiele zu finden, die die Verwendung von Routinen auf niedrigerer Ebene veranschaulichen. Während LAPACK-Routinen stets ein Dokumentationskommentar mit Beschreibungen der Eingabeargumente und möglichen Rückgabewerte vorangestellt ist, kann die Visualisierung und Erfassung der erwarteten Eingabe- und Ausgabewerte ohne Codebeispiele eine Herausforderung darstellen, insbesondere beim Umgang mit speziellen Matrizen. Und obwohl das Fehlen von Unit-Tests oder dokumentierten Beispielen weder das Ende der Welt bedeutet, bedeutete es, dass das Hinzufügen von LAPACK-Unterstützung zu stdlib mühsamer sein würde, als ich erwartet hatte. Das Schreiben von Benchmarks, Tests, Beispielen und Dokumentationen würde einfach mehr Zeit und Mühe erfordern, was möglicherweise die Anzahl der Routinen einschränkte, die ich während des Praktikums implementieren konnte.

Speicherlayouts

Beim Speichern von Matrixelementen im linearen Speicher hat man zwei Möglichkeiten: entweder Spalten zusammenhängend oder Zeilen zusammenhängend speichern (siehe Abbildung 2). Das erstere Speicherlayout wird als spaltengroße-Reihenfolge und das letztere als zeilengroße-Reihenfolge bezeichnet.

LAPACK in your web browser

Abbildung 2: Schematische Darstellung der Speicherung von Matrixelementen im linearen Speicher entweder in (a) spaltengroßer (Fortran-Stil) oder (b) zeilengroßer (C-Stil) Reihenfolge. Die Wahl des zu verwendenden Layouts ist größtenteils eine Frage der Konvention.

Die Wahl des zu verwendenden Layouts ist größtenteils eine Frage der Konvention. Beispielsweise speichert Fortran Elemente in der Reihenfolge der Hauptspalten und C speichert Elemente in der Reihenfolge der Hauptzeilen. Bibliotheken höherer Ebenen wie NumPy und stdlib unterstützen sowohl spalten- als auch zeilenbezogene Ordnungen, sodass Sie das Layout eines mehrdimensionalen Arrays während der Array-Erstellung konfigurieren können.

pip install numpy
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren

Während keines der Speicherlayouts von Natur aus besser ist als das andere, ist die Anordnung der Daten zur Gewährleistung eines sequentiellen Zugriffs gemäß den Konventionen des zugrunde liegenden Speichermodells von entscheidender Bedeutung für die Gewährleistung einer optimalen Leistung. Moderne CPUs sind in der Lage, sequentielle Daten effizienter zu verarbeiten als nicht sequentielle Daten, was vor allem auf das CPU-Caching zurückzuführen ist, das wiederum die räumliche Referenzlokalität ausnutzt.

Um die Leistungsauswirkungen des sequentiellen vs. nicht-sequentiellen Elementzugriffs zu demonstrieren, betrachten Sie die folgende Funktion, die alle Elemente aus einer MxN-Matrix A in eine andere MxN-Matrix B kopiert und dabei davon ausgeht, dass Matrixelemente im Hauptspaltenformat gespeichert sind bestellen.

# Import all of NumPy:
import numpy as np

# Define arrays:
x = np.asarray(...)
y = np.asarray(...)

# Perform operation:
y[::2,:,:] += 5.0 * x[::2,:,:]
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren

Seien A und B die folgenden 3x2-Matrizen:

A=[123456], B=[00000 0]A = begin{bmatrix}1 & 2 \3 & 4 \5 & 6end{bmatrix}, B = begin{bmatrix}0 & 0 \0 & 0 \0 & 0end{bmatrix}A= 135 246 , B= 000 000

Wenn sowohl A als auch B in der Hauptspaltenreihenfolge gespeichert sind, können wir die Kopierroutine wie folgt aufrufen:

pip install numpy
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren

Wenn A und B jedoch beide in Zeilenreihenfolge gespeichert sind, ändert sich die Anrufsignatur zu

# Import all of NumPy:
import numpy as np

# Define arrays:
x = np.asarray(...)
y = np.asarray(...)

# Perform operation:
y[::2,:,:] += 5.0 * x[::2,:,:]
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren

Beachten Sie, dass wir im letzteren Szenario nicht in der innersten Schleife auf Elemente in sequentieller Reihenfolge zugreifen können, da da0 2 und da1 -5 ist und das Gleiche gilt für db0 und db1. Stattdessen springen die „Zeiger“ des Array-Index wiederholt weiter, bevor sie zu früheren Elementen im linearen Speicher zurückkehren, wobei ia = {0, 2, 4, 1, 3, 5} und ib gleich sind. In Abbildung 3 zeigen wir die Auswirkungen des nicht sequentiellen Zugriffs auf die Leistung.

LAPACK in your web browser

Abbildung 3: Leistungsvergleich bei der Bereitstellung quadratischer Spalten-Haupt- und Zeilen-Hauptmatrizen zum Kopieren, wenn Kopieren einen sequentiellen Elementzugriff entsprechend der Spalten-Hauptreihenfolge voraussetzt. Die x-Achse zählt zunehmende Matrixgrößen (d. h. Anzahl der Elemente) auf. Alle Raten werden im Verhältnis zu den Hauptergebnissen der Spalte für eine entsprechende Matrixgröße normalisiert.

Aus der Abbildung können wir ersehen, dass die spalten- und zeilenbezogene Leistung ungefähr gleich ist, bis wir mit quadratischen Matrizen mit mehr als 1e5 Elementen arbeiten (M = N = ~316). Bei 1e6-Elementen (M = N = ~1000) führt die Bereitstellung einer zu kopierenden Zeilenhauptmatrix zu einem Leistungsabfall von mehr als 25 %. Für 1e7-Elemente (M = N = ~3160) beobachten wir einen Leistungsabfall von mehr als 85 %. Die erhebliche Auswirkung auf die Leistung kann auf eine verringerte Referenzlokalität bei der Arbeit mit zeilengroßen Matrizen mit großen Zeilengrößen zurückgeführt werden.

Da es in Fortran geschrieben ist, geht LAPACK von einer spaltenorientierten Zugriffsreihenfolge aus und implementiert seine Algorithmen entsprechend. Dies führt zu Problemen für Bibliotheken wie stdlib, die nicht nur die Zeilenreihenfolge unterstützen, sondern diese auch zu ihrem Standardspeicherlayout machen. Würden wir die Fortran-Implementierungen von LAPACK einfach auf JavaScript portieren, würden Benutzer, die zeilenorientierte Matrizen bereitstellen, negative Auswirkungen auf die Leistung aufgrund des nicht sequentiellen Zugriffs erfahren.

Um negative Auswirkungen auf die Leistung abzumildern, haben wir eine Idee von BLIS übernommen, einer BLAS-ähnlichen Bibliothek, die sowohl zeilen- als auch spaltenorientierte Speicherlayouts in BLAS-Routinen unterstützt, und beschlossen, bei der Portierung von Routinen von Fortran nach JavaScript modifizierte LAPACK-Implementierungen zu erstellen C, die explizit sowohl spalten- als auch zeilenorientierte Speicherlayouts durch separate Schrittparameter für jede Dimension berücksichtigen. Bei einigen Implementierungen, wie z. B. dlacpy, das der oben definierten Kopierfunktion ähnelt, ist die Einbindung separater und unabhängiger Schritte unkompliziert und erfordert häufig Schritttricks und Schleifenaustausch. Bei anderen erwiesen sich die Änderungen jedoch aufgrund von als viel weniger einfach spezielle Matrixbehandlung, unterschiedliche Zugriffsmuster und kombinatorische Parametrisierung.

ndarrays

LAPACK-Routinen arbeiten hauptsächlich mit Matrizen, die im linearen Speicher gespeichert sind und auf deren Elemente gemäß den angegebenen Dimensionen und dem Schritt der führenden (d. h. ersten) Dimension zugegriffen wird. Dimensionen geben die Anzahl der Elemente in jeder Zeile bzw. Spalte an. Der Schritt gibt an, wie viele Elemente im linearen Speicher übersprungen werden müssen, um auf das nächste Element einer Zeile zuzugreifen. LAPACK geht davon aus, dass Elemente, die zur gleichen Spalte gehören, immer zusammenhängend sind (d. h. benachbart im linearen Speicher). Abbildung 4 bietet eine visuelle Darstellung der LAPACK-Konventionen (insbesondere die Schaltpläne (a) und (b)).

LAPACK in your web browser

Abbildung 4: Schematische Darstellung der Verallgemeinerung der LAPACK-Strided-Array-Konventionen auf nicht zusammenhängende Strided-Arrays. a) Eine zusammenhängende 5-mal-5-Matrix, die in Spaltenhauptreihenfolge gespeichert ist. b) Eine nicht zusammenhängende 3-mal-3-Untermatrix, die in der Hauptspaltenreihenfolge gespeichert ist. Untermatrizen können in LAPACK bearbeitet werden, indem ein Zeiger auf das erste indizierte Element bereitgestellt und der Schritt der führenden (d. h. ersten) Dimension angegeben wird. In diesem Fall beträgt der Schritt der führenden Dimension fünf, obwohl nur drei Elemente pro Spalte vorhanden sind, da die Untermatrixelemente im linearen Speicher nicht zusammenhängend sind, wenn sie als Teil einer größeren Matrix gespeichert werden. In LAPACK wird der Schritt der nachgestellten (d. h. zweiten) Dimension immer als Eins angenommen. c) Eine nicht zusammenhängende 3-mal-3-Untermatrix, die in der Hauptspaltenreihenfolge gespeichert ist und keine Einheitsschritte aufweist und die LAPACK-Schrittkonventionen sowohl auf führende als auch auf nachfolgende Dimensionen verallgemeinert. Diese Verallgemeinerung liegt den mehrdimensionalen Arrays von stdlib (auch als „ndarrays“ bezeichnet) zugrunde.

Bibliotheken wie NumPy und stdlib verallgemeinern die Strided-Array-Konventionen von LAPACK zur Unterstützung

  1. Nicht-Einheitsschritte in der letzten Dimension (siehe Abbildung 4 (c)). LAPACK geht davon aus, dass die letzte Dimension einer Matrix immer einen Einheitsschritt hat (d. h. Elemente innerhalb einer Spalte werden zusammenhängend im linearen Speicher gespeichert).
  2. Negative Fortschritte für jede Dimension. LAPACK erfordert, dass der Schritt einer führenden Matrixdimension positiv ist.
  3. Mehrdimensionale Arrays mit mehr als zwei Dimensionen. LAPACK unterstützt explizit nur Strided-Vektoren und (Sub-)Matrizen.

Die Unterstützung von Nicht-Einheitsschritten in der letzten Dimension gewährleistet die Unterstützung der O(1)-Erstellung nicht zusammenhängender Ansichten des linearen Speichers, ohne dass eine explizite Datenverschiebung erforderlich ist. Diese Ansichten werden oft als „Slices“ bezeichnet. Betrachten Sie als Beispiel den folgenden Codeausschnitt, der solche Ansichten mithilfe der von stdlib bereitgestellten APIs erstellt.

pip install numpy
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren

Ohne Unterstützung für Nicht-Einheitsschritte in der letzten Dimension wäre die Rückgabe einer Ansicht aus dem Ausdruck x['::2,::2'] nicht möglich, da ausgewählte Elemente in eine neue Linearität kopiert werden müssten Speicherpuffer, um die Kontiguität sicherzustellen.

LAPACK in your web browser

Abbildung 5: Schematische Darstellung der Verwendung der Schrittmanipulation zur Erstellung gespiegelter und gedrehter Ansichten von Matrixelementen, die im linearen Speicher gespeichert sind. Für alle Unterschemata werden die Schritte als [Trailing_Dimension, Leading_Dimension] aufgeführt. Implizit für jeden Schaltplan ist ein „Offset“, der den Index des ersten indizierten Elements angibt, sodass für eine Matrix A das Element Aij ist aufgelöst gemäß i⋅strides[1] j⋅strides[0] Offset. a) Bei einer 3x3-Matrix, die in Spaltenhauptreihenfolge gespeichert ist, kann man die Schritte der führenden und nachfolgenden Dimensionen manipulieren, um Ansichten zu erstellen, in denen auf Matrixelemente entlang einer oder mehrerer Achsen in umgekehrter Reihenfolge zugegriffen wird. b) Mit einer ähnlichen Schrittmanipulation können gedrehte Ansichten von Matrixelementen relativ zu ihrer Anordnung im linearen Speicher erstellt werden.

Die Unterstützung negativer Schritte ermöglicht die O(1)-Umkehr und Drehung von Elementen entlang einer oder mehrerer Dimensionen (siehe Abbildung 5). Um beispielsweise eine Matrix von oben nach unten und von links nach rechts umzudrehen, muss man nur die Schritte negieren. Aufbauend auf dem vorherigen Codeausschnitt demonstriert der folgende Codeausschnitt die Umkehrung von Elementen um eine oder mehrere Achsen.

pip install numpy
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren

Die Diskussion über negative Schritte impliziert die Notwendigkeit eines „Offset“-Parameters, der den Index des ersten indizierten Elements im linearen Speicher angibt. Für ein mehrdimensionales Array mit Schritten A und eine Liste von Schritten s der Index, der dem Element Aij⋅⋅⋅n entspricht kann gemäß der Gleichung gelöst werden

idx=Offset is0 js1 nsN1textrm{idx} = textrm{offset} i cdot s_0 j cdot s_1 ldots n cdot s_{N-1}idx=Offset i⋅s0 j⋅s1 n⋅sN−1

wobei N die Anzahl der Array-Dimensionen ist und sk dem k-ten Schritt entspricht.

In BLAS- und LAPACK-Routinen, die negative Schritte unterstützen – etwas, das nur bei der Arbeit mit Schrittvektoren unterstützt wird (siehe z. B. Daxpy oben) – wird der Index-Offset mithilfe einer Logik berechnet, die dem folgenden Codeausschnitt ähnelt:

pip install numpy
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren

wobei M die Anzahl der Vektorelemente ist. Dies setzt implizit voraus, dass ein bereitgestellter Datenzeiger auf den Anfang des linearen Speichers für einen Vektor zeigt. In Sprachen, die Zeiger unterstützen, wie z. B. C, passt man zum Bearbeiten eines anderen Bereichs des linearen Speichers typischerweise einen Zeiger mithilfe der Zeigerarithmetik vor dem Funktionsaufruf an, was zumindest für den eindimensionalen Fall relativ kostengünstig und unkompliziert ist.

Wenn wir beispielsweise zu c_daxpy wie oben definiert zurückkehren, können wir Zeigerarithmetik verwenden, um den Elementzugriff auf fünf Elemente im linearen Speicher zu beschränken, beginnend beim elften und sechzehnten Element (Hinweis: nullbasierte Indizierung) eines Eingabe- und Ausgabearrays. bzw. wie im folgenden Codeausschnitt gezeigt.

# Import all of NumPy:
import numpy as np

# Define arrays:
x = np.asarray(...)
y = np.asarray(...)

# Perform operation:
y[::2,:,:] += 5.0 * x[::2,:,:]
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren

In JavaScript, das keine explizite Zeigerarithmetik für binäre Puffer unterstützt, muss man jedoch explizit neue typisierte Array-Objekte mit einem gewünschten Byte-Offset instanziieren. Um im folgenden Codeausschnitt die gleichen Ergebnisse wie im obigen C-Beispiel zu erzielen, müssen wir einen typisierten Array-Konstruktor auflösen, einen neuen Byte-Offset berechnen, eine neue typisierte Array-Länge berechnen und eine neue typisierte Array-Instanz erstellen.

npm install @stdlib/ndarray-fancy @stdlib/blas-daxpy
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren

Bei großen Array-Größen sind die Kosten für die Instanziierung typisierter Arrays im Vergleich zu der Zeit, die für den Zugriff auf und die Bearbeitung einzelner Array-Elemente aufgewendet wird, vernachlässigbar; Bei kleineren Array-Größen kann die Objektinstanziierung jedoch erhebliche Auswirkungen auf die Leistung haben.

Um negative Auswirkungen auf die Objektinstanziierung zu vermeiden, entkoppelt stdlib den Datenpuffer eines Ndarrays von der Position des Pufferelements, das dem Anfang einer Ndarray-Ansicht entspricht. Dadurch können die Slice-Ausdrücke x[2:,3:] und x[3:,1:] neue ndarray-Ansichten zurückgeben, ohne dass neue Pufferinstanzen instanziiert werden müssen, wie im folgenden Codeausschnitt gezeigt.

// Individually import desired functionality:
import FancyArray from '@stdlib/ndarray-fancy';
import daxpy from '@stdlib/blas-daxpy';

// Define ndarray meta data:
const shape = [4, 4, 4];
const strides = [...];
const offset = 0;

// Define arrays using a "lower-level" fancy array constructor:
const x = new FancyArray('float64', [...], shape, strides, offset, 'row-major');
const y = new FancyArray('float64', [...], shape, strides, offset, 'row-major');

// Perform operation:
daxpy(5.0, x['::2,:,:'], y['::2,:,:']);
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren

Als Konsequenz der Entkopplung eines Datenpuffers vom Anfang einer Ndarray-Ansicht wollten wir ebenfalls vermeiden, dass beim Aufruf von LAPACK-Routinen mit Ndarray-Daten neue typisierte Array-Instanzen instanziiert werden müssen. Dies bedeutete die Erstellung modifizierter LAPACK-API-Signaturen, die explizite Offset-Parameter für alle Schrittvektoren und Matrizen unterstützen.

Der Einfachheit halber kehren wir zur JavaScript-Implementierung von daxpy zurück, die zuvor oben definiert wurde.

pip install numpy
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren

Wie im folgenden Codeausschnitt gezeigt, können wir die obige Signatur und Implementierung so ändern, dass die Verantwortung für die Auflösung des ersten indizierten Elements auf den API-Konsumenten verlagert wird.

# Import all of NumPy:
import numpy as np

# Define arrays:
x = np.asarray(...)
y = np.asarray(...)

# Perform operation:
y[::2,:,:] += 5.0 * x[::2,:,:]
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren

Bei ndarrays erfolgt die Auflösung während der ndarray-Instanziierung, sodass der Aufruf von daxpy_ndarray mit ndarray-Daten eine einfache Übergabe der zugehörigen ndarray-Metadaten darstellt. Dies wird im folgenden Codeausschnitt demonstriert.

npm install @stdlib/ndarray-fancy @stdlib/blas-daxpy
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren

Ähnlich wie bei BLIS sahen wir sowohl in herkömmlichen LAPACK-API-Signaturen (z. B. für Abwärtskompatibilität) als auch in modifizierten API-Signaturen (z. B. zur Minimierung nachteiliger Auswirkungen auf die Leistung) einen Wert und entschieden uns daher für einen Plan, sowohl konventionelle als auch andere API-Signaturen bereitzustellen geänderte APIs für jede LAPACK-Routine. Um die Codeduplizierung zu minimieren, wollten wir eine gemeinsame „Basis“-Implementierung auf niedrigerer Ebene implementieren, die dann von APIs auf höherer Ebene umschlossen werden könnte. Während die oben gezeigten Änderungen für die BLAS-Routine daxpy relativ einfach erscheinen mögen, war die Transformation einer herkömmlichen LAPACK-Routine und ihres erwarteten Verhaltens in eine generalisierte Implementierung oft viel weniger einfach.

dlaswp

Genug mit den Herausforderungen! Wie sieht ein Endprodukt aus?!

Lassen Sie uns den Kreis schließen und dies zurück zu dlaswp bringen, einer LAPACK-Routine zum Durchführen einer Reihe von Zeilenaustauschen in einer Eingabematrix gemäß einer Liste von Pivot-Indizes. Der folgende Codeausschnitt zeigt die Referenzimplementierung von LAPACK Fortran.

// Individually import desired functionality:
import FancyArray from '@stdlib/ndarray-fancy';
import daxpy from '@stdlib/blas-daxpy';

// Define ndarray meta data:
const shape = [4, 4, 4];
const strides = [...];
const offset = 0;

// Define arrays using a "lower-level" fancy array constructor:
const x = new FancyArray('float64', [...], shape, strides, offset, 'row-major');
const y = new FancyArray('float64', [...], shape, strides, offset, 'row-major');

// Perform operation:
daxpy(5.0, x['::2,:,:'], y['::2,:,:']);
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren

Um die Schnittstelle mit der Fortran-Implementierung von C aus zu erleichtern, stellt LAPACK eine zweistufige C-Schnittstelle namens LAPACKE bereit, die Fortran-Implementierungen umschließt und sowohl zeilen- als auch spaltenbezogene Eingabe- und Ausgabematrizen unterstützt. Die mittlere Schnittstelle für dlaswp wird im folgenden Codeausschnitt gezeigt.

void c_daxpy(const int N, const double alpha, const double *X, const int strideX, double *Y, const int strideY) {
    int ix;
    int iy;
    int i;
    if (N <= 0) {
        return;
    }
    if (alpha == 0.0) {
        return;
    }
    if (strideX < 0) {
        ix = (1-N) * strideX;
    } else {
        ix = 0;
    }
    if (strideY < 0) {
        iy = (1-N) * strideY;
    } else {
        iy = 0;
    }
    for (i = 0; i < N; i++) {
        Y[iy] += alpha * X[ix];
        ix += strideX;
        iy += strideY;
    }
    return;
}
Nach dem Login kopieren
Nach dem Login kopieren

Beim Aufruf mit einer Spaltenhauptmatrix a übergibt der Wrapper LAPACKE_dlaswp_work einfach die bereitgestellten Argumente an die Fortran-Implementierung. Wenn der Wrapper jedoch mit einer Zeilenhauptmatrix a aufgerufen wird, muss er Speicher zuweisen, a explizit in eine temporäre Matrix a_t transponieren und kopieren, den Schritt der führenden Dimension neu berechnen, dlaswp mit a_t aufrufen, die in a_t gespeicherten Ergebnisse transponieren und kopieren zu einem und schließlich frei zugewiesenen Speicher. Das ist ziemlich viel Arbeit und kommt bei den meisten LAPACK-Routinen vor.

Der folgende Codeausschnitt zeigt die auf JavaScript portierte Referenz-LAPACK-Implementierung mit Unterstützung für führende und nachgestellte Dimensionsschritte, Indexoffsets und einen Schrittvektor, der Pivot-Indizes enthält.

const binary = new UintArray([...]);

const mod = new WebAssembly.Module(binary);
Nach dem Login kopieren
Nach dem Login kopieren

Um eine API mit konsistentem Verhalten mit herkömmlichem LAPACK bereitzustellen, habe ich dann die obige Implementierung verpackt und Eingabeargumente an die „Basis“-Implementierung angepasst, wie im folgenden Codeausschnitt gezeigt.

pip install numpy
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren

Ich habe anschließend einen separaten, aber ähnlichen Wrapper geschrieben, der eine API-Zuordnung direkter zu den mehrdimensionalen Arrays von stdlib bereitstellt und eine spezielle Behandlung durchführt, wenn die Richtung, in die Pivots angewendet werden sollen, negativ ist, wie im folgenden Codeausschnitt gezeigt.

# Import all of NumPy:
import numpy as np

# Define arrays:
x = np.asarray(...)
y = np.asarray(...)

# Perform operation:
y[::2,:,:] += 5.0 * x[::2,:,:]
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren

Ein paar Punkte, die Sie beachten sollten:

  1. Im Gegensatz zur herkömmlichen LAPACKE-API ist der Parameter „matrix_layout“ (Reihenfolge) in den dlaswp_ndarray- und Basis-APIs nicht erforderlich, da die Reihenfolge aus den bereitgestellten Schritten abgeleitet werden kann.
  2. Im Gegensatz zur herkömmlichen LAPACKE-API müssen wir bei einer zeilenmajoren Eingabematrix keine Daten in temporäre Arbeitsbereich-Arrays kopieren, wodurch unnötige Speicherzuweisung reduziert wird.
  3. Im Gegensatz zu Bibliotheken wie NumPy und SciPy, die direkt mit BLAS und LAPACK verbunden sind, müssen wir beim Aufrufen von LAPACK-Routinen in stdlib vorher nicht zusammenhängende mehrdimensionale Daten in und aus temporären Arbeitsbereichs-Arrays kopieren bzw. nach dem Aufruf. Außer bei der Schnittstelle zu hardwareoptimiertem BLAS und LAPACK trägt der verfolgte Ansatz dazu bei, Datenbewegungen zu minimieren und die Leistung in ressourcenbeschränkten Browseranwendungen sicherzustellen.

Für serverseitige Anwendungen, die hardwareoptimierte Bibliotheken wie OpenBLAS nutzen möchten, stellen wir separate Wrapper bereit, die verallgemeinerte Signaturargumente an ihre optimierten API-Äquivalente anpassen. In diesem Zusammenhang kann sich zumindest bei ausreichend großen Arrays die Erstellung temporärer Kopien lohnen.

Aktueller Status und nächste Schritte

Trotz der Herausforderungen, unvorhergesehenen Rückschläge und mehreren Design-Iterationen freue ich mich, berichten zu können, dass ich zusätzlich zu dlaswp oben 35 PRs öffnen konnte, die Unterstützung für verschiedene LAPACK-Routinen und zugehörige Dienstprogramme hinzufügen. Natürlich sind es nicht ganz 1.700 Übungen, aber ein guter Anfang! :)

Dennoch ist die Zukunft rosig und wir sind sehr gespannt auf diese Arbeit. Es gibt noch viel Raum für Verbesserungen und zusätzliche Forschung und Entwicklung. Insbesondere liegt uns daran

  1. Entdecken Sie Werkzeuge und Automatisierung.
  2. Beheben Sie Build-Probleme beim Auflösen der Quelldateien von Fortran-Abhängigkeiten, die über mehrere stdlib-Pakete verteilt sind.
  3. Rollout von C- und Fortran-Implementierungen und nativen Bindungen für die vorhandenen LAPACK-Pakete von stdlib.
  4. die Bibliothek modularer LAPACK-Routinen von stdlib weiter ausbauen.
  5. Identifizieren Sie zusätzliche Bereiche zur Leistungsoptimierung.

Während mein Praktikum bei Quansight Labs beendet ist, habe ich vor, weiterhin Pakete hinzuzufügen und diese Bemühungen voranzutreiben. Angesichts des immensen Potenzials und der grundlegenden Bedeutung von LAPACK würden wir uns freuen, wenn diese Initiative, LAPACK ins Internet zu bringen, weiter wächst. Wenn Sie also daran interessiert sind, dies voranzutreiben, zögern Sie bitte nicht, uns zu kontaktieren! Und wenn Sie daran interessiert sind, die Entwicklung zu sponsern, stehen Ihnen die Leute von Quansight gerne für ein Gespräch zur Verfügung.

Und damit möchte ich Quansight für die Bereitstellung dieser Praktikumsmöglichkeit danken. Ich bin unglaublich glücklich, so viel gelernt zu haben. Ein Praktikant bei Quansight zu sein war schon lange ein Traum von mir und ich bin sehr dankbar, dass ich ihn erfüllt habe. Mein besonderer Dank gilt Athan Reines und Melissa Mendonça, die eine großartige Mentorin und rundum wundervolle Person ist! Und vielen Dank an alle stdlib-Kernentwickler und alle anderen bei Quansight, die mir auf diesem Weg sowohl im Großen als auch im Kleinen geholfen haben.

Prost!


stdlib ist ein Open-Source-Softwareprojekt, das sich der Bereitstellung einer umfassenden Suite robuster, leistungsstarker Bibliotheken widmet, um die Entwicklung Ihres Projekts zu beschleunigen und Ihnen die Gewissheit zu geben, dass Sie auf fachmännisch erstellte, qualitativ hochwertige Software angewiesen sind.

Wenn Ihnen dieser Beitrag gefallen hat, geben Sie uns einen Stern? auf GitHub und überlegen Sie, das Projekt finanziell zu unterstützen. Ihre Beiträge und Ihre kontinuierliche Unterstützung tragen dazu bei, den langfristigen Erfolg des Projekts sicherzustellen und werden sehr geschätzt!

Das obige ist der detaillierte Inhalt vonLAPACK in Ihrem Webbrowser. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Quelle:dev.to
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Neueste Artikel des Autors
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage