Wartungskosten für die SIMD-Programmiercodebasis

Frage:

Der Konsens der Softwareindustrie ist, dass sauberer und einfacher Code für die langfristige Überlebensfähigkeit der Codebasis und der Organisation, die sie besitzt, von grundlegender Bedeutung ist. Diese Eigenschaften führen zu geringeren Wartungskosten und einer erhöhten Wahrscheinlichkeit, dass die Codebasis fortgesetzt wird.

SIMD-Code unterscheidet sich jedoch von allgemeinem Anwendungscode, und ich würde gerne wissen, ob es einen ähnlichen Konsens in Bezug auf sauberen und einfachen Code gibt, der speziell für SIMD-Code gilt.

Hintergrund meiner Frage.

Ich schreibe viel SIMD-Code (Single Instruction, Multiple Data) für verschiedene Bildverarbeitungs- und Analyseaufgaben. Kürzlich musste ich auch einige dieser Funktionen von einer Architektur (SSE2) auf eine andere (ARM NEON) portieren.

Der Code ist für eingeschweißte Software geschrieben, daher kann er nicht von proprietären Sprachen ohne uneingeschränkte Umverteilungsrechte wie MATLAB abhängen.

Ein Beispiel für eine typische Codestruktur:

• Verwendung des OpenCV - Matrixtyps ( Mat) für die gesamte Speicher-, Puffer- und Lebensdauerverwaltung.
• Nach Überprüfung der Größe (Dimensionen) der Eingabeargumente werden die Zeiger auf die Startadresse jeder Pixelzeile genommen.
• Die Pixelanzahl und die Startadressen jeder Pixelreihe aus jeder Eingabematrix werden an einige C ++ - Funktionen auf niedriger Ebene übergeben.
• Diese C ++ - Funktionen auf niedriger Ebene verwenden SIMD-interne Funktionen (für Intel Architecture und ARM NEON ), die von unformatierten Zeigeradressen geladen und in diesen gespeichert werden.
• Eigenschaften dieser einfachen C ++ - Funktionen:
  • Ausschließlich eindimensional (fortlaufend im Speicher)
  • Beschäftigt sich nicht mit Speicherzuordnungen.
    (Jede Zuordnung, einschließlich temporärer Zuordnungen, wird vom äußeren Code mithilfe von OpenCV-Funktionen verarbeitet.)
  • Der Bereich der Namenslängen von Symbolen (intrinsische Zeichen, Variablennamen usw.) beträgt ungefähr 10 bis 20 Zeichen, was ziemlich übermäßig ist.
    (Liest wie Techno-Babble.)
  • Von der Wiederverwendung von SIMD-Variablen wird abgeraten, da Compiler bei der korrekten Syntaxanalyse von Code, der nicht im Codierungsstil "Einfachzuweisung" geschrieben ist, ziemlich fehlerhaft sind .
    (Ich habe mehrere Compiler-Fehlerberichte eingereicht.)

Welche Aspekte der SIMD-Programmierung würden dazu führen, dass sich die Diskussion vom allgemeinen Fall unterscheidet? Oder warum ist SIMD anders?

In Bezug auf die anfänglichen Entwicklungskosten

• Es ist allgemein bekannt, dass die anfänglichen Entwicklungskosten für C ++ - SIMD-Code mit guter Leistung im Vergleich zu beiläufig geschriebenem C ++ - Code etwa 10- bis 100-fach (mit großem Spielraum) betragen .
• Wie in den Antworten zu Auswählen zwischen Leistung und lesbarem / saubererem Code angegeben? ist der meiste Code (einschließlich beiläufig geschriebenem Code und SIMD-Code) anfangs weder sauber noch schnell .
• Evolutionsbedingte Verbesserungen der Code-Leistung (sowohl bei skalarem als auch bei SIMD-Code) werden nicht empfohlen (da dies als eine Art Software-Überarbeitung angesehen wird ), und Kosten und Nutzen werden nicht erfasst.

In Bezug auf die Neigung
(zB das Pareto-Prinzip, auch bekannt als die 80-20-Regel )

• Selbst wenn die Bildverarbeitung nur 20% eines Softwaresystems umfasst (sowohl in Bezug auf die Codegröße als auch auf die Funktionalität), ist die Bildverarbeitung vergleichsweise langsam (als Prozentsatz der CPU-Zeit betrachtet) und nimmt mehr als 80% der Zeit in Anspruch.
  • Dies ist auf den Datengrößeneffekt zurückzuführen: Eine typische Bildgröße wird in Megabyte gemessen, wohingegen die typische Größe von Nichtbilddaten in Kilobyte gemessen wird.
• Innerhalb des Bildverarbeitungscodes wird ein SIMD-Programmierer so geschult, dass er den 20% -Code, der die Hotspots enthält, automatisch erkennt, indem er die Schleifenstruktur im C ++ - Code identifiziert. Aus Sicht eines SIMD-Programmierers ist 100% des "Codes, auf den es ankommt", ein Leistungsengpass.
• In einem Bildverarbeitungssystem sind häufig mehrere Hotspots vorhanden, die vergleichbare Zeitanteile beanspruchen. Beispielsweise kann es 5 Hotspots geben, die jeweils 20%, 18%, 16%, 14%, 12% der Gesamtzeit beanspruchen. Um einen hohen Leistungszuwachs zu erzielen, müssen alle Hotspots in SIMD neu geschrieben werden.
  • Dies wird als Ballon-Popping-Regel zusammengefasst : Ein Ballon kann nicht zweimal gepoppt werden.
  • Angenommen, es gibt einige Ballons, sagen wir 5 davon. Die einzige Möglichkeit, sie zu dezimieren, besteht darin, sie einzeln zu entfernen.
  • Sobald der erste Ballon platzt, machen die verbleibenden 4 Ballons nun einen höheren Prozentsatz der gesamten Ausführungszeit aus.
  • Um weitere Gewinne zu erzielen, muss man einen weiteren Ballon platzen lassen.
    (Dies steht im Widerspruch zur 80-20-Optimierungsregel: Ein gutes wirtschaftliches Ergebnis kann erzielt werden, wenn 20% der am niedrigsten hängenden Früchte gepflückt wurden.)

In Bezug auf Lesbarkeit und Wartung

• SIMD-Code ist offensichtlich schwer zu lesen.

  • Dies gilt auch dann, wenn alle Best Practices der Softwareentwicklung befolgt werden, z. B. Benennung, Kapselung, Konstanten-Korrektheit (und offensichtliche Nebenwirkungen), Funktionszerlegung usw.
  • Dies gilt auch für erfahrene SIMD-Programmierer.

• Optimaler SIMD-Code ist im Vergleich zu seinem äquivalenten C ++ - Prototypcode sehr verzerrt (siehe Anmerkung) .

  • Es gibt viele Möglichkeiten, SIMD-Code zu verzerren, aber nur 1 von 10 derartigen Versuchen führt zu akzeptabel schnellen Ergebnissen.
  • (Das heißt, im Bereich der 4x-10x Leistungssteigerung, um hohe Entwicklungskosten zu rechtfertigen. In der Praxis wurden sogar noch höhere Steigerungen beobachtet.)

(Bemerkung)
Dies ist die Hauptthese des MIT-Halide-Projekts, in der der Titel der Arbeit wörtlich zitiert wird:

"Entkopplung von Algorithmen von Zeitplänen zur einfachen Optimierung von Bildverarbeitungs-Pipelines"

In Bezug auf die Anwendbarkeit in Bezug auf die Zukunft

• SIMD-Code ist streng an eine einzelne Architektur gebunden. Jede neue Architektur (oder jede Erweiterung der SIMD-Register) erfordert ein Umschreiben.
• Im Gegensatz zur Mehrheit der Softwareentwicklung wird jeder SIMD-Code in der Regel für einen einzigen Zweck geschrieben, der sich nie ändert.
  (Mit Ausnahme der Portierung auf andere Architekturen.)
• Einige Architekturen sind perfekt abwärtskompatibel (Intel). Einige werden geringfügig unterschritten (ARM AArch64, ersetzt vtbldurch vtblq), was jedoch ausreicht, um zu verhindern, dass Code kompiliert wird.

In Bezug auf Fähigkeiten und Ausbildung

• Es ist nicht klar, welche Kenntnisse erforderlich sind, um einen neuen Programmierer zum Schreiben und Verwalten von SIMD-Code zu schulen.
• Hochschulabsolventen, die SIMD-Programmierung in der Schule gelernt haben, scheinen dies als unpraktische Laufbahn zu verachten und abzulehnen.
• Zerlegungslesung und Leistungsprofilerstellung auf niedriger Ebene werden als zwei grundlegende Fähigkeiten zum Schreiben von Hochleistungs-SIMD-Code angeführt. Es ist jedoch unklar, wie Programmierer systematisch in diesen beiden Fähigkeiten geschult werden sollen.
• Die moderne CPU-Architektur (die sich erheblich von den in Lehrbüchern gelehrten unterscheidet) macht das Training noch schwieriger.

In Bezug auf Richtigkeit und mangelbedingte Kosten

• Eine einzelne SIMD-Verarbeitungsfunktion ist tatsächlich zusammenhängend genug, um die Korrektheit zu ermitteln, indem:
  • Anwenden formaler Methoden (mit Stift und Papier) und
  • Überprüfen ganzzahliger Ausgabebereiche (mit Prototypcode und außerhalb der Laufzeit ausgeführt) .
• Der Überprüfungsprozess ist jedoch sehr kostspielig (100% Zeitaufwand für die Codeüberprüfung und 100% Zeitaufwand für die Prüfung von Prototypmodellen), wodurch sich die bereits hohen Entwicklungskosten von SIMD-Code verdreifachen.
• Wenn ein Fehler diesen Überprüfungsprozess irgendwie durchläuft, ist es nahezu unmöglich, die verdächtige fehlerhafte Funktion zu "reparieren" (zu beheben), außer sie zu ersetzen (neu zu schreiben).
• SIMD-Code leidet unter der Stumpfheit von Fehlern im C ++ - Compiler (Optimierung des Codegenerators).
  • SIMD-Code, der mit C ++ - Ausdrucksvorlagen generiert wurde, leidet ebenfalls stark unter Fehlern des Compilers.

In Bezug auf disruptive Innovationen

• Viele Lösungen wurden von der Wissenschaft vorgeschlagen, aber nur wenige sehen eine weitverbreitete kommerzielle Nutzung.

  • MIT Halogenid
  • Stanford Darkroom
  • NT2 (Numerical Template Toolbox) und das zugehörige Boost.SIMD

• Bibliotheken mit weit verbreiteter kommerzieller Nutzung scheinen nicht stark SIMD-fähig zu sein.

  • Open-Source-Bibliotheken erscheinen SIMD als lauwarm.
    • Kürzlich habe ich diese Beobachtung aus erster Hand, nachdem ich eine große Anzahl von OpenCV-API-Funktionen ab Version 2.4.9 profiliert habe.
    • Viele andere Bildverarbeitungsbibliotheken, die ich erstellt habe, nutzen SIMD ebenfalls nicht in großem Umfang, oder sie verpassen die wahren Hotspots.
  • Kommerzielle Bibliotheken scheinen auf SIMD zu verzichten.
    • In einigen Fällen habe ich sogar festgestellt, dass Bildverarbeitungsbibliotheken SIMD-optimierten Code in einer früheren Version auf Nicht-SIMD-Code in einer späteren Version zurückgesetzt haben, was zu schwerwiegenden Leistungseinbußen führte.
      (Die Antwort des Anbieters ist, dass es notwendig war, Compiler-Fehler zu vermeiden.)

Die Frage dieses Programmierers: Muss Code mit geringer Latenz manchmal "hässlich" sein? ist verwandt, und ich habe zuvor eine Antwort auf diese Frage geschrieben, um meine Ansichten vor ein paar Jahren zu erklären.

Diese Antwort ist jedoch ziemlich "Appeasement" für den Standpunkt der "vorzeitigen Optimierung", dh für den Standpunkt, dass:

• Alle Optimierungen sind per Definition verfrüht (oder von Natur aus kurzfristig ) und
• Die einzige Optimierung, die langfristig von Vorteil ist, ist die Vereinfachung.

Solche Standpunkte werden in diesem ACM-Artikel jedoch bestritten .

All dies führt mich zu der Frage:
SIMD-Code unterscheidet sich vom allgemeinen Anwendungscode, und ich möchte wissen, ob es einen ähnlichen Branchenkonsens hinsichtlich des Werts von sauberem und einfachem Code für SIMD-Code gibt.

Ich habe vor einigen Jahrzehnten nicht viel SIMD-Code für mich geschrieben, sondern viel Assembler-Code. AFAIK mit SIMD intrinsics ist im Wesentlichen Assembler-Programmierung, und Ihre ganze Frage könnte umformuliert werden, indem Sie "SIMD" durch das Wort "Assembly" ersetzen. Zum Beispiel mögen die Punkte, die Sie bereits erwähnt haben

• Der Code braucht 10x bis 100x als "High-Level-Code" zu entwickeln

• Es ist an eine bestimmte Architektur gebunden

• Der Code ist niemals "sauber" oder einfach umzugestalten

• Sie benötigen Experten zum Schreiben und Verwalten

• Das Debuggen und Warten ist schwierig und entwickelt sich sehr schwierig

sind für SIMD in keiner Weise "speziell" - diese Punkte gelten für jede Art von Assemblersprache und sie sind alle "Branchenkonsens". Und das Fazit in der Software-Branche ist so ziemlich dasselbe wie für Assembler:

• Schreiben Sie es nicht, wenn Sie es nicht müssen - verwenden Sie nach Möglichkeit eine Hochsprache und lassen Sie die Compiler die harte Arbeit erledigen

• Wenn die Compiler nicht ausreichen, kapseln Sie zumindest die "Low Level" -Teile in einigen Bibliotheken, aber vermeiden Sie es, den Code im gesamten Programm zu verbreiten

• Da es fast unmöglich ist, "selbstdokumentierenden" Assembler- oder SIMD-Code zu schreiben, versuchen Sie, dies durch viele Dokumentationen auszugleichen.

Natürlich gibt es tatsächlich einen Unterschied zur Situation mit "klassischem" Assembler- oder Maschinencode: Heutzutage produzieren moderne Compiler in der Regel hochwertigen Maschinencode aus einer Hochsprache, die häufig besser optimiert ist als manuell geschriebener Assembler-Code. Für die heute beliebten SIMD-Architekturen liegt die Qualität der verfügbaren Compiler mit AFAIK weit darunter - und vielleicht wird sie das nie erreichen, da die automatische Vektorisierung immer noch ein Thema der wissenschaftlichen Forschung ist. Siehe zum Beispiel diesen Artikel, in dem die Unterschiede in der Optimierung zwischen einem Compiler und einem Menschen beschrieben werden, und der den Eindruck vermittelt, dass es sehr schwierig sein könnte, gute SIMD-Compiler zu erstellen.

Wie Sie bereits in Ihrer Frage beschrieben haben, besteht auch bei aktuellen Bibliotheken ein Qualitätsproblem. Insofern können wir hoffen, dass in den nächsten Jahren die Qualität der Compiler und Bibliotheken zunimmt, dass möglicherweise die SIMD-Hardware geändert werden muss, um "compilerfreundlicher" zu werden, und dass möglicherweise spezielle Programmiersprachen zur Unterstützung einer einfacheren Vektorisierung (wie Halide, das du hast es zweimal erwähnt) wird populärer werden (war das nicht schon eine Stärke von Fortran?). Laut Wikipedia wurde SIMD vor ungefähr 15 bis 20 Jahren "ein Massenprodukt" (und Halide ist weniger als 3 Jahre alt, wenn ich die Dokumente richtig interpretiere). Vergleichen Sie dies mit der Zeit, in der Compiler für "klassische" Assemblersprachen ausgereift sein mussten. Laut diesem Wikipedia-ArtikelEs dauerte fast 30 Jahre (von ~ 1970 bis Ende der 1990er Jahre), bis Compiler die Leistung menschlicher Experten übertrafen (bei der Erstellung von nicht parallelem Maschinencode). Es kann also sein, dass wir noch 10 bis 15 Jahre warten müssen, bis dies auch bei SIMD-fähigen Compilern der Fall ist.

Meine Organisation hat sich genau mit diesem Problem befasst. Unsere Produkte befinden sich im Videobereich, aber ein Großteil des Codes, den wir schreiben, ist Bildverarbeitung, die auch für Standbilder funktionieren würde.

Wir haben das Problem "gelöst" (oder vielleicht "gelöst"), indem wir unseren eigenen Compiler geschrieben haben. Das ist nicht ganz so verrückt, wie es zunächst klingt. Es gibt nur eine begrenzte Anzahl von Eingängen. Wir wissen, dass der gesamte Code mit Bildern arbeitet, hauptsächlich mit RGBA-Bildern. Wir haben einige Einschränkungen festgelegt, so dass sich die Eingabe- und Ausgabepuffer niemals überlappen können, sodass kein Pointer-Aliasing auftritt. Sachen wie diese.

Wir schreiben dann unseren Code in der OpenGL Shading Language (glsl). Es wird kompiliert, um skalaren Code, SSE, SSE2, SSE3, AVX, Neon und natürlich tatsächliche Glsl. Wenn wir eine neue Plattform unterstützen müssen, aktualisieren wir den Compiler, um den Code für diese Plattform auszugeben.

Wir kacheln auch die Bilder, um die Cache-Kohärenz zu verbessern, und ähnliches. Indem wir die Bildverarbeitung auf einen kleinen Kernel beschränken und glsl (das nicht einmal Zeiger unterstützt) verwenden, reduzieren wir die Komplexität beim Kompilieren des Codes erheblich.

Dieser Ansatz ist nicht jedermanns Sache und hat seine eigenen Probleme (Sie müssen zum Beispiel die Korrektheit des Compilers sicherstellen). Aber für uns hat es ganz gut geklappt.

Es scheint nicht zu viel Wartungsaufwand zu verursachen, wenn Sie eine höhere Sprache verwenden:

Vector<float> values = GetValues();
Vector<float> increment = GetIncrement();

// Perform addition as a vector operation:
List<float> result = (values + increment).ToList();

vs

List<float> values = GetValues();
List<float> increment = GetIncrement();

// Perform addition as a monadic sequence operation:
List<float> result = values.Zip(increment, (v, i) => v + i).ToList();

Natürlich müssen Sie sich den Einschränkungen der Bibliothek stellen, aber Sie werden sie nicht selbst warten. Könnte ein gutes Gleichgewicht zwischen Wartungskosten und Leistungsgewinn sein.

http://blogs.msdn.com/b/dotnet/archive/2014/04/07/the-jit-finally-proposed-jit-and-simd-are-getting-married.aspx

http://blogs.msdn.com/b/dotnet/archive/2014/05/13/update-to-simd-support.aspx

Ich habe in der Vergangenheit Assembler-Programmierung durchgeführt, nicht zuletzt SIMD-Programmierung.

Haben Sie darüber nachgedacht, einen SIMD-fähigen Compiler wie den von Intel zu verwenden? Ist ein Leitfaden zur Vektorisierung mit Intel® C ++ - Compilern interessant?

Einige Ihrer Kommentare wie "Balloon-Popping" schlagen die Verwendung eines Compilers vor (um durchgehend Vorteile zu erzielen, wenn Sie keinen einzigen Hot-Spot haben).