VectorLib

Index:

VectorLib

Inhaltsverzeichnis

---

1. Einführung

Dem Ziel der Vereinfachung dienen zwar in neuerer Zeit auch die Feldfunktionen von Fortran90 und templatisierte Vektor-Klassen in C++, doch sind dies lediglich Abkürzungen, die vom Compiler wieder in Schleifen übersetzt und entsprechend ineffizient verarbeitet werden. (Ähnliches gilt für die meisten der populären BLAS-Bibliotheken für Fortran). Demgegenüber bietet OptiVec eine hochoptimierte, in Assembler geschriebene Lösung, deren Geschwindigkeit nicht mehr durch die Qualität des Compilers, sondern nur noch durch die echte Geschwindigkeit des Prozessors bestimmt wird. Gegenüber compiliertem Code ergibt sich ein durchschnittlicher Geschwindigkeitsvorteil von einem Faktor 2 bis 3 (für einige Funktionen auch bis zu 8).

Nach unserem Kenntnisstand ist OptiVec die erste umfassende Vektor- und Matrix-Bibliothek für PC-Compiler, die praktisch vollständig in Maschinensprache geschrieben wurde.

OptiVec tritt in Konkurrenz zu etlichen teuren integrierten Programmsystemen für wissenschaftliche und Datenverarbeitungs-Anwendungen, ist aber eben nicht ein "geschlossenes" integriertes Paket, sondern zur Verwendung mit den gängigen Programmiersprachen bestimmt, wodurch dem OptiVec-Benutzer die Flexibilität seiner bevorzugten Programmierumgebung erhalten bleibt.

OptiVec tritt in Konkurrenz zu etlichen teuren integrierten Programmsystemen für wissenschaftliche und Datenverarbeitungs-Anwendungen, ist aber eben nicht ein "geschlossenes" integriertes Paket, sondern zur Verwendung mit den gängigen Programmiersprachen bestimmt, wodurch dem OptiVec-Benutzer die Flexibilität seiner bevorzugten Programmierumgebung erhalten bleibt.

Hier einige Stichworte:

• Alle Operatoren und mathematischen Funktionen von C/C++ und Pascal/Delphi sind in vektorisierter Form implementiert; zusätzlich sind viele weitere mathematische Funktionen aufgenommen, die sonst als mehr oder weniger komplizierte Kombination existierender Funktionen berechnet werden müßten. Ausführungsgeschwindigkeit und numerische Genauigkeit werden hierdurch stark verbessert.
• MatrixLib deckt einen großen Bereich optimierter Matrix-Funktionen ab: Arithmetik, Algebra, Faktorisierungen, Daten-Anpassungen usw.
  TensorLib ist als spätere Erweiterung dieser Konzepte auf multidimensionale Felder geplant.
• Fast-Fourier-Transform-Techniken für effiziente Faltungen/Entfaltungen, Korrelations- und Spektralanalysen, Filterung etc. sind sowohl für ein- als auch zweidimensionale Felder enthalten.
• Es gibt zahlreiche Bausteine für statistische Analyse.
• Ableitungen, Integrale, Interpolationen werden durch die Analysis-Funktionen von VectorLib berechnet.
• Graphik-Funktionen für Plots in cartesischen Koordinaten erlauben die Darstellung von Vektor- und Matrix-Daten.
• Alle Funktionen haben eine übersichtliche, intuitiv verständliche und einfache Syntax.
• Jede Funktion existiert für jeden Daten-Typ, für den dies sinnvoll ist, also meist für alle Ganzzahl-Typen, alle reellen und häufig auch komplexen Fließkomma-Typen. Der Datentyp wird einfach durch das Präfix des Funktionsnamens bestimmt. In der C/C++-Version werden keine impliziten Namensergänzungen ("name mangling") oder andere spezifische Eigenschaften von C++ verwandt. Dadurch kann OptiVec in C ebenso wie in C++ benutzt werden, und dadurch wird gewährleistet, daß Funktionsnamen und -syntax in den OptiVec-Versionen für C/C++ und Pascal/Delphi weitestgehend identisch sind.
• Die Eingabe- und Ausgabe-Vektoren und -Matrizen von OptiVec-Funktionen sind von variabler Größe, und es ist möglich, auch nur einen Teil (z.B. die ersten 100 Elemente, jedes 10. Element usw.) eines Vektors zu verarbeiten – ein weiterer Vorteil gegenüber anderen Ansätzen, bei denen nur ganze Felder verarbeitet werden können.
• Ein objekt-orientiertes Interface für C++, VecObj kapselt alle Vektorfunktionen und bietet noch einfachere Syntax sowie verbesserte Sicherheit der Speicherzugriffe.
• Der Einsatz von OptiVec-Funktionen anstatt Schleifen erlaubt es, Quellcode viel kompakter und lesbarer zu gestalten.
• Zusätzlich zu den komplexen Vektor- und Matrix-Routinen bietet CMATH eine Bibliothek Funktionen für skalare komplexe Zahlen aller drei Fließkomma-Genauigkeiten, sowohl in cartesischen als auch in Polarkoordinaten. Im Vergleich zu anderen erhältlichen komplexen Klassenbibliotheken sowie der Unit Complex von Delphi ist CMATH durch seine Implementierung in Assembler wesentlich schneller, genauer und stabiler. Außerdem benötigt die C/C++-Version nicht unbedingt C++, sondern kann auch in klassischen C-Modulen verwendet werden (dann mit typenspezifischen Funktions-Präfixen).

Der große Funktions-Umfang, die hohe numerische Genauigkeit und die Einfachkeit der Benutzung machen OptiVec zu einem Programmierwerkzeug der Spitzenklasse für wissenschaftlich-technische Datenverarbeitungs-Anwendungen. Hier tritt OptiVec in Konkurrenz zu etlichen teuren integrierten Programmsystemen, ist aber eben nicht ein "geschlossenes" integriertes Paket, sondern zur Verwendung mit den gängigen Programmiersprachen bestimmt, wodurch dem OptiVec-Benutzer die Flexibilität seiner bevorzugten Programmierumgebung erhalten bleibt.

1.1 Warum sich vektorisierte Programmierung auf dem PC lohnt

Vektorisierung war schon immer die Zauberformel für Supercomputer mit ihren aus vielen einzelnen Prozessoren gebildeten Parallel-Architekturen. Auf diesen Architekturen wird versucht, die Rechenlast möglichst gleichmäßig auf alle Prozessoren zu verteilen und so die Ausführungsgeschwindigkeit zu maximieren. Die sogenanten "divide and conquer"-Algorithmen spalten kompliziertere numerische Aufgaben in kleine Schleifen über Vektorelemente auf. Hochgezüchtete Compiler finden dann den effizientesten Weg für die Verteilung der Vektor-Elemente auf die Prozessoren. Viele Compiler für Supercomputer enthalten bereits große Bibliotheken vordefinierter Vektor- und Matrixfunktionen für viele Anwendungszwecke. Diese Vektor- und Matrixfunktionen bieten den besten Weg, maximalen Datendurchsatz zu erzielen.

Es ist offensichtlich, daß die massive Parallelverarbeitung einer Cray auf den meisten PCs mit ihren eher bescheidenen 2 oder 4 Prozessor-Kernen nicht in gleicher Weise möglich ist, ganz zu schweigen von den immer noch gängigen Ein-Prozessor-PCs. Auf den ersten Blick mag es daher sinnlos erscheinen, das Konzept der vektorisierten Programmierung auch auf dem PC anzuwenden. Tatsächlich aber sind auch viele vektor-spezifische Optimierungen möglich, selbst wenn nur eine CPU vorhanden ist. Viele dieser Optimierungen können von heutigen Compilern nicht durchgeführt werden. Stattdessen muß der Programmierer auf Maschinensprachen-Niveau heruntergehen. Hand-optimierte, in Maschinensprache geschriebene Vektorfunktionen übertreffen compilierte Schleifen in der Geschwindigkeit durchschnittlich um einen Faktor von 2-3. Dies bedeutet, daß Vektorisierung die Mühe sehr wohl lohnen kann, auch für PC-Programme.

1.1.1 Allgemeine Optimierungs-Strategien von OptiVec

Hier sind die wichtigsten Optimierungs-Strategien, die in OptiVec zur Steigerung der Performance auf eingesetzt werden &150; unabhängig von der Zahl der Prozessor-Kerne:

Prefetch von Gruppen von Vektor-Elementen
Ab dem Pentium III stehen sehr nützliche "Prefetch"-Befehle zur Verfügung, die es erlauben, Daten schon genügen im voraus aus dem Hauptspeicher in den Prozessor zu laden, so daß sie gleich zur Verfügung stehen, wenn sie verarbeitet werden sollen.

Cache-Kontrolle
Der Pentium III+ -Befehlssatz erlaubt es, Daten als "temporär" (zur Wiederverwendung vorgesehen) oder "nicht-temporär" (nur einmal verwendet) zu markieren, wenn sie geladen oder gespeichert werden. OptiVec-Funktionen gehen generell von der Annahme aus, daß Eingabevektoren (oder -matrizen) nicht noch einmal benutzt werden, während Ausgabevektoren wahrscheinlich ihrerseits zu Eingabedaten für folgende Operationen werden. Dementsprechend wird der Cache beim Laden von Eingabedaten umgangen, während Ausgabedaten in den Cache geschrieben werden. Natürlich wird dieses Schema zusammenbrechen, wenn Vektoren gar nicht mehr in den Cache passen. Für solche Fälle ist die "Large-Vector"-Version der OptiVec-Bibliotheken gedacht, die auch beim Speichern der Ausgabedaten den Cache umgeht. Für einfache arithmetische Operationen kann hierdurch im Vergleich zur Version für kleine und mittlere Vektoren ein Geschwindigkeitsgewinn von bis zu 20% erzielt werden. Da andererseits die "Large-Vector"-Version effektiv den Cache ausschaltet, resultiert ein drastisch verschlechterter Datendurchsatz (bis zu einem Faktor von 3-4) von ihrem eventuellen Mißbrauch für kleinere Vektoren, wo der Cache hätte benutzt werden können. Bevor Sie tatsächlich die "Large-Vector"-Version einsetzen, sollten Sie daher auch prüfen, ob sich Ihr Problem nicht in kleinere Vektoren aufspalten läßt, wodurch der Cache wieder genutzt und ein enormer Geschwindigkeitsvorteil erzielt werden könnte.

Verwendung von SIMD-Befehlen
Man mag sich wundern, warum diese Strategie nicht gleich an erster Stelle genannt ist. Die SSE oder "Streaming Single-Instruction-Multiple-Data Extensions" des Pentium III und Pentium 4 bieten explizite Unterstützung für Vektor-Programmierung mit Fließkommazahlen in float / single- oder double- Genauigkeit (letztere nur für Pentium 4). Auf den ersten Blick sollten sie also die Vektor-Programmierung auf dem PC geradezu revolutionieren. Angesichts einer immer noch vorhandenen Diskrepanz zwischen Prozessor- und Datenbus-Geschwindigkeit sind aber viele der einfachen arithmetischen Operationen in ihrer Geschwindigkeit durch den Datenfluß begrenzt. Hier können SIMD-Befehle nur noch zu einem geringeren Geschwindigkeitsvorteil führen, als man eigentlich erwarten würde. Die gleichzeitige Verarbeitung von vier float-Zahlen in einem einzigen Befehl erbringt so häufig nur eine Beschleunigung um 20-30% gegenüber gutem FPU-Code, was sich natürlich immer noch lohnt. Für kompliziertere Operationen allerdings können SIMD-Befehle oft gar nicht verwendet werden, wenn nämlich entweder bedingte Verzweigungen für jedes Vektor-Element individuell erforderlich sind, oder auch dann, wenn ohne die interne extended-Genauigkeit der FPU umständlichere Algorithmen gewählt werden müßten. OptiVec macht daher von den SSE-Befehlen überall dort Gebrauch, wo ein wirklicher Geschwindigkeitsvorteil erzielt werden kann. Man beachte allerdings, dass Operationen wie Matrix-Multiplikation oder Fourier-Transformation in float-Präzision zugunsten des hier möglichen erheblichen Geschwindigkeitsgewinnes einen Genauigkeitsverlust von 2-3 Stellen in Kauf nehmen. Wer demgegenüber auf maximale Genauigkeit Wert legen muss, sollte daher stets die ausschließlich FPU-Befehle verwendende P4-Version einsetzen.

Preload von Fließkomma-Konstanten
Anstatt Fließkomma-Konstanten am Ende jedes Funktionsaufrufes innerhalb einer Schleife von Coprozessor-Stack zu entfernen, bleiben sie für die Verarbeitung des nächsten Vektor-Elementes geladen.

Volle XMM- und FPU-AusnutzungWo immer nötig und sinnvoll, werden alle acht XMM-Register (in der 64-bit-Version sogar sechzehn) bzw. alle acht Coprozessor-Register eingesetzt (für einen Compiler ist es schon eine hervorragende Leistung, die Buchführung für vier Coprozessor-Register zu beherrschen).

Superscalar schedulingDurch sorgfältige "Paarung" von Befehlen, deren Ergebnisse nicht voneinander abhängen, können die parallelen Integer-Pipes und fadd/fmul-Einheiten moderner Prozessoren (seit Pentium) bestmöglich ausgenutzt werden.
Ältere Prozessoren profitieren hiervon nicht, zumeist schadet es aber auch nicht.

Loop-unrolling
Wo eine optimale Ausnutzung der parallelen Prozessor-Pipes nicht für einzelne Vektor-Elemente erzielt werden kann, werden die Vektor-Elemente häufig gleich zu zweit, zu viert oder noch mehreren verarbeitet. Hierdurch wird zusätzlich der relative Anteil des Schleifen-Managements an der gesamten Ausführungszeit zurückgedrängt. Im Zusammenhang mit den oben beschriebenen "Prefetch"-Mechanismen wird die Schleifengröße möglichst an die Cache-Zeilengröße von 64 Byte (32 Byte bei älteren Prozessoren) angepaßt.

Vereinfachte Adressierung
Die Adressierung von Vektor- und erst recht von Matrix-Elementen stellt noch immer eine Hauptquelle für ineffizienten Code heutiger Compiler dar. Durch Hin- und Herschaltung zwischen Eingabe- und Ausgabe-Vektoren wird eine große Zahl redundanter Adressierungs-Operationen ausgeführt. Durch die ebenso strikte wie einfache Definition "Verarbeitung von hier bis da" können die OptiVec-Funktionen den Aufwand für die Adressierung von Array-Elementen auf das nötige Minimum reduzieren.

Ersatz von Fließkomma- durch Ganzzahl-Befehle
Eine Reihe von Fließkomma-Operationen (wie Kopieren, Austauschen, Vergleich mit Sollwerten) kann wahlweise mit Ganzzahl- oder Fließkomma-Prozessorbefehlen implementiert werden. Hier wird natürlich die jeweils schnellste Methode angewandt.

Strikte Genauigkeits-Kontrolle
C/C++-Compiler wandeln eine float-Zahl in double um – Pascal/Delphi sogar in extended – bevor sie an eine mathematische Funktion übergeben wird. Diese Behandlung war einmal sinnvoll, als Festplattenspeicher zu teuer war, um in den .LIB-Dateien separate Funktionen für alle Datentypen einzuschließen. Auf heutigen PCs ist sie schlicht ineffizient. Konsequenterweise werden in den OptiVec-Routinen keine solchen impliziten Umwandlungen durchgeführt. Hier wird eine float-Funktion auch nur in float- (also einfacher) Genauigkeit berechnet, unter Verzicht auf die soundsovielte Stelle nach dem Komma, die ohnehin sofort wieder abgeschnitten wird. Zusätzlich kann V_setFPAccuracy( 1 ); aufgerufen werden, um die FPU auf einfache Genauigkeit umzuschalten, falls man sich generell mit dieser begnügen möchte. Hierdurch kann die Ausführungsgeschwindigkeit ab dem Pentium-Prozessor etwas gesteigert werden. Seien Sie aber darauf gefasst, dass die Genauigkeit Ihrer Endergebnisse noch deutlich unter der float-Spezifikation liegen kann, wenn schon die Zwischenergebnisse nur einfach-genau berechnet werden. Details werden bei V_setFPAccuracy aufgeführt.

Inline-Coding
Alle externen Funktionsaufrufe sind aus den Schleifen eliminiert. Dadurch wird die Ausführungszeit der "call / ret"-Paare sowie die Zeit für die Übergabe der Funktionsargumente eingespart.

Cache-line-Matching lokaler Variablen
Der Level-1-Cache aktueller Prozessoren ist in Zeilen von je 64 Byte organisiert (bei den Vorgängern waren es 32 Byte). Viele OptiVec-Funktionen benötigen doppelt- oder extended-genaue Variablen auf dem Stack (vor allem für Ganzzahl/Fließkomma-Umwandlungen oder für Bereichsprüfungen). Derzeit erhältliche Compiler richten den Stack an 4-Byte-Grenzen aus. Es besteht also die Gefahr, dass die 8 Bytes einer double oder die 10 bytes einer extended beim Speichern auf dem Stack eine 64-Byte-Grenze überschreiten. Dies wiederum würde zu starken Geschwindigkeits-Einbußen durch Cache-Zeilenumbrüche führen. Um diese zu vermeiden, richten alle OptiVec-Funktionen, für die dies eine Rolle spielt, ihre lokalen Variablen an 8-Byte- (für double), 16-Byte- (für extended) bzw. 64-Byte-Grenzen aus (XMM-Werte).

Ungeschützte und bereichsreduzierte Funktionen
OptiVec bietet alternative Formen einiger mathematischer Funktionen, bei denen man zwischen der geschützten Variante mit Fehlerbehandlung und einer ungeschützten Variante ohne Fehlerdetektion währen kann. In einigen Funktionen, die ganzzahlige Potenzen ausrechnen, erlaubt die Abwesenheit der Fehlerdetektion eine viel effizientere Codierung. Ähnliches gilt für die Sinus- und Cosinus-Funktion für mit Sicherheit zwischen -2p und +2p liegenden Argumenten. In diesen Spezialfällen kann die Ausführungszeit um bis zu 40% reduziert werden, abhängig von der Hardware-Umgebung. Dieser Geschwindigkeitsgewinn wird allerdings durch erhöhtes Risiko erkauft: Falls auch nur ein einziges Vektorelement außerhalb des gültigen Bereiches liegt, stürzen die ungeschützten und bereichsreduzierten Funktionen ohne Warnung einfach ab.

1.1.2 Multi-Prozessor-Optimierung

MultithreadSupport
Multi-Tasking und Multi-Threading können mit modernen Betriebssystemen auch auf den üblichen PCs mit nur einer CPU durchgeführt werden. Auf Multiprozessor-Computern (wie Intel i3, i5, i7, Core2Duo, AMD Athlon 64 X2 oder Workstations mit 2 oder 4 PentiumXX-Chips) können die Threads auf die vorhandenen Prozessoren verteilt und so die Performance verdoppelt oder vervierfacht werden. Hierfür muß aber sichergestellt sein, daß in parallelen Threads laufende Funktionen sich nicht gegenseitig ihre Zwischenergebnisse überschreiben. Mit sehr wenigen Ausnahmen (Plotting-Funktionen und nicht-lineare Datenanpassungen) sind alle übrigen OptiVec-Funktionen re-entrant, also darauf ausgerichtet, parallel zueinander laufen zu können.
Beim Multi-Threading ab der P6- Version von OptiVec ist Vorsicht mit äteren 32-bit-Windows-Versionen angesagt, da diese noch nichts von SIMD "wußten" und die für SIMD verwendeten XMM-Register bei Task-Umschaltungen nicht sichern. Ab Windows XP treten solche Probleme nicht mehr auf.

Bei der Entwicklung Ihrer Multi-Thread-Anwendung stehen Ihnen zwei grundsätzlich verschiedene Optionen zur Verfügung: Funktionale Parallelität und Daten-Parallelität.

Funktionelle Parallelität
Verschiedene Threads führen verschiedene Aufgaben aus – sie unterscheiden sich in ihrer Funktion. Als Beispiel denke man an eine Anwendung, bei der ein Thread Benutzer-Ein- und Ausgaben abarbeitet, während ein anderer Thread Hintergrund-Berechnungen durchführt. Selbst auf einer Ein-Kern-CPU kann diese Art des Multi-Threading durch die vom Betriebssystem bewirkte ständige Umschaltung zwischen den beiden Threads Vorteile bieten (z.B., dass das Benutzer-Interface nicht blockiert, während die Hintergrundberechnungen ausgeführt werden, sondern weiterhin Eingaben annehmen kann). Auf einem Mehr-Prozessor-Computer können die zwei (oder mehr) Threads tatsächlich gleichzeitig auf den verschiedenen Prozessor-Kernen laufen. Normalerweise ist die Lastverteilung zwischen den Prozessoren bei funktionellem Multi-Threading alles andere als perfekt: Oft läuft ein Prozessor unter Volllast, während ein anderer arbeitslos auf Eingaben wartet. Dennoch ist diese Art des Multi-Threading die beste Option für Anwendungen, die nur kleine bis mittelgroße Vektoren und Matrizen umfassen.

Daten-Parallelität
Um die Lastverteilung zwischen den vorhandenen Prozessor-Kernen zu verbessern und so den Datendurchsatz zu maximieren, kann die klassische Parallelverarbeitung angewandt werden: Die Daten-Vektoren und -Matrizen werden in kleinere Teile zerlegt, und jeder Thread arbeitet einen solchen Teil ab. Die Brauchbarkeit dieses Ansatzes wird dadurch beschränkt, dass der Aufwand für die Verteilung der Daten auf die verschiedenen Threads und für die dabei nötige Kommunikation der Threads untereinander ziemlich hoch ist. Außerdem lassen sich die Daten niemals vollständig parallelisieren; es verbleibt immer ein gewisser Teil der Aufgaben, der nur sequentiell abgearbeitet werden kann. Daher lohnt sich Daten-Parallelität nur für größere Vektoren und Matrizen. Typische Schwellen-Größen, ab denen die Leistung mehrerer Prozessoren den für die Verteilung auf sie nötigen Aufwand "zurückverdient", reichen von unter 100 (bei mathematischen Funktionen komplex-zahliger Vektoren) bis zu über 10.000 Elementen (bei den einfachen arithmetischen Funktionen). Erst wenn die Vektoren / Matrizen deutlich größer als diese Schwellenwerte sind, kommt die erhöhte Leistung voll zum Tragen. Dann erst nähert sich die Beschleunigung dem theoretischen Grenzwert einer Verdopplung, Vervierfachung usw. an.

Auswahl der passenden OptiVec-Bibliothek
Wenn Ihre Anwendung auf einem breiten Spektrum unterstützter Prozessoren laufen sollen und wenn Ihre Vektoren / Matrizen nur von kleiner bis mittlerer Größe sind (wenige 100 bis wenige 1000 Elemente, je nach Art der durchgeführten Berechnungen), empfehlen wir die Allzweck-Bibliotheken   OVVC4.LIB  (für MS Visual C++),  VCF4W.LIB  (für Borland C++),  oder die Units in OPTIVEC\LIB4  (für Delphi). Diese Bibliotheken verbinden gute Performance mit Rück-Kompatibilität zu älterer Hardware bis hinab zu 486DX, Pentium und den frühen Modellen des Athlon. Sie alle sind Thread-sicher und unterstützen funktionelle Parallelität. Falls Sie nicht die volle Fließkomma-Genauigkeit und auch nicht dieses Ausmaß an Rückwärts-Kompatibilität benötigen, können Sie höhere Leistungen erzielen durch den Einsatz der Bibliotheken für Pentium III+ (man ersetze "4" durch "6" im Bibliotheks-Namen), Pentium 4+ / AMD64 (gekennzeichnet durch die Ziffer "7") oder Core2xxx / AMD64xxx mit SSE3 (gekennzeichnet durch die Ziffer "8").

Für sehr große Vektoren und Matrizen auf Ein-Kern-Rechnern ab Pentium III+ kann die Leistung durch Einsatz spezieller Large-Vector-Bibliotheken erhöht werden, die durch Umgehung des für die großen Datenmengen ohnehin zu kleinen Caches den mit dessen Verwaltung verbundenen Aufwand sparen. Sie sind gekennzeichnet durch den Buchstaben "L":  OVVC6L.LIB  (für MS Visual C++),  VCF6L.LIB  (für Borland C++),  oder die Units in OPTIVEC\LIB6L  (für Delphi). Man ersetze die Ziffer "6" durch "7" oder "8" für den Einsatz nur auf aktuellen Prozessoren mit reduzierter Fließkomma-Genauigkeit. Man beachte, dass bei fälschlicher Anwendung der Large-Vector-Bibliotheken für kleinere Vektoren die Ausführungsgeschwindigkeit deutlich niedriger als mit den Allzweck-Bibliotheken ist.

Für mittlere bis große Vektoren und Matrizen auf Mehrkern-Maschinen schließlich bietet sich die Verwendung der neuen multi-core-optimierten Bibliotheken an. Diese verteilen für jede einzelne Funktion die Arbeitslast über die vorhandenen Prozessor-Kerne (Auto-Threading). Sie werden durch den Buchstaben "M" gekennzeichnet, also z.B. OVVC7M.LIB  (für MS Visual C++ mit SSE2-Verwendung),  VCF4M.LIB  (für Borland C++ ohne SSE-Verwendung, also mit voller Fließkomma-Genauigkeit),  oder die Units in OPTIVEC\LIB8M  (für Delphi). Diese Bibliotheken sind für Multiprozessor-Computer wie AMD Athlon 64 X2, Intel Core2Duo oder Workstations mit mehreren Chips auf Pentium 4+-Level gedacht.
Die CUDA-Bibliotheks-Versionen basieren auf den "M"-Bibliotheken und lagern die Verarbeitung nur für sehr große Vektoren auf die Graphik-Karte aus. Sie sind durch den Buchstaben "C" markiert, z.B.  OVVC8C.LIB.
Die "M"- und "C"- Bibliotheken laufen immer noch auf Ein-Kern-Computern. Durch die "Bürokratie-Verluste" beim Thread-Management sind sie hier aber deutlich langsamer als die Allzweck-Bibliotheken. Obwohl die "M"-Bibliotheken im Hinblick auf mittlere bis größere Vektoren entwickelt wurden, sind die Einbußen bei Verwendung mit kleinen Vektoren nicht sehr hoch, da die OptiVec Thread-Engine eine Funktion automatisch in einem einzelnen Thread ausführt, wenn die Vektor-Größe nicht ausreicht, um den Verteilungs-Aufwand durch die Parallel-Ausführung (oder gar durch die Auslagerung auf den Graphik-Prozessor) wieder aufzuholen.
Wenn Sie die "M"- oder "C"-Bibliotheken verwenden, muss Ihr Programm zu Beginn V_initMT aufrufen.

Zurück zum VectorLib-Inhaltsverzeichnis     OptiVec Home

2. Elemente von VectorLib-Funktionen

2.1 Synonyme einiger Datentypen

a) nur C/C++:

64-bit-Integers (__int64 in BC++ Builder und MS Visual C++, Int64 in Delphi, Comp in Turbo Pascal) werden in OptiVec als quad (für "quadruple integer", also Vierfach-Integer) bezeichnet.
Der Datentyp quad ist in 32-bit immer vorzeichenbehaftet; nur für Win64 bietet OptiVec den Datentyp uquad als vorzeichenlosen 64-bit Ganzzahltyp.

• Nur Borland C++ vor C++ Builder 2006: Da diese älteren BC-Versionen keine direkte Unterstützung für 64-bit Integers boten, ist hier der Typ quad als struct von zwei 32-bit-Werten implementiert. Fließkommazahlen – vorzugsweise der über eine 64-bit-Mantisse verfügende Typ long double – zur " müssen zur Vermittlung" eingesetzt werden. Hierzu dienen die Funktionen setquad,   quadtod und _quadtold. Alternativ können die beiden 32-bit-Teile auch einzeln zugewiesen werden, z.B.:.
  xq.Hi = 0x00000001UL;
  xq.Lo = 0x2468ABCDUL;

Der Pascal/Delphi-Benutzern wohlbekannte Datentyp extended wird in der Borland C++-Version von OptiVec als Synonym für long double verwendet. Da Visual C++ 80-bit-Fließkommazahlen nicht unterstützt, ist extended hier als double definiert.
Der Grund für die Einführung des Typs extended ist, daß alle OptiVec-Funktionen identische Namen in C/C++ und Pascal/Delphi haben sollen. Die Funktions-Präfixe aber sind vom Datentyp der verarbeiteten Vektoren abgeleitet (s.u.). Der Buchstabe "L" (der vielleicht für long double stehen könnte) ist bereits durch long int und unsigned long überbelegt. So bietet sich der Buchstabe "E" für extended an, was den zusätzlichen Vorteil der Nähe zu den Buchstaben "D" für double und "F" für float hat (vielleicht erfreut uns die Zukunft ja auch noch mit hochgenauen 128-bit-und 256-bit-Fließkommazahlen, die als "great" und "hyper" ihren Platz ebenfalls in alphabetischer Nachbarschaft finden könnten).

b) nur Pascal/Delphi:

Aus "historischen" Gründen weisen die Ganzzahl-Datentypen eine etwas konfuse Nomenklatur in Pascal/Delphi auf. Um die vom Datentyp abgeleiteten Präfixe mit der C/C++-Version von OptiVec kompatibel zu machen, definieren wir eine Anzahl von Synonymen, wie in der folgenden Tabelle beschrieben:  

type	Pascal/Delphi-Name	Synonym	abgeleitetes Präfix
8 bit signed	ShortInt	ByteInt	VBI_
8 bit unsigned	Byte	UByte	VUB_
16 bit signed	SmallInt		VSI_
16 bit unsigned	Word	USmall	VUS_
32 bit signed	LongInt		VLI_
32 bit unsigned		ULong	VUL_
64 bit signed	Int64	QuadInt	VQI_
64 bit unsigned	UInt64	UQuad	VUQ_
16/32 bit signed	Integer		VI_
16/32 bit unsigned	Cardinal	UInt	VU_

UQuads existieren nur in der 64-bit-Version. Für Win32 gibt es nur den vorzeichenbehafteten Typ Quad.

Um einen Bool'schen Datentyp derselben Größe wie Integer zur Verfügung zu haben, definieren wir den Typ IntBool. Er ist äquivalent mit LongBool. Man findet den Typ IntBool vor allem als Rückgabewert vieler mathematischer VectorLib-Funktionen.

2.2 Komplexe Zahlen:
Die Datentypen fComplex, dComplex, eComplex, fPolar, dPolar und ePolar

Unsere Ziele sind

• komplexe Zahlen in allen drei Genauigkeiten für C, C++, Pascal und Delphi zur Verfügung zu stellen
• sowohl cartesische als auch Polar-Koordinaten zu unterstützen
• eine saubere, effiziente Implementierung in Assembler zu liefern (anstelle der gebräuchlichen C++ Templates)
• und eine einfache, kompakte und konsistente Nomenklatur einzuführen.

Die entsprechenden Definitionen für Pascal/Delphi sind in der Unit VecLib enthalten:
type fComplex = record Re, Im: Float; end;
type dComplex = record Re, Im: Double; end;
type eComplex = record Re, Im: Extended; end;
type fPolar = record Mag, Arg: Float; end;
type dPolar = record Mag, Arg: Double; end;
type ePolar = record Mag, Arg: Extended; end;

Komplexe Zahlen werden initialisiert, indem ihrem Real- und Imaginärteil bzw. ihrem Mag- und Arg-Teil die gewünschten Werte zugewiesen werden, z.B.:
z.Re  = 3.0; z.Im  = 5.7;
p.Mag = 8.8; p.Arg = 3.14;
(Für Pascal/Delphi muß der Zuweisungs-Operator natürlich ":=" geschrieben werden).
Alternativ kann die Initialisierung auch mittels der Funktionen fcplx oder fpolr durchgeführt werden:
C/C++:
z = fcplx( 3.0, 5.7 );
p = fpolr( 4.0, 0.7 );

Pascal/Delphi:
fcplx( z, 3.0, 5.7 );
fpolr( p, 3.0, 5.7 );

Für doppelt-genaue komplexe Zahlen gebrauche man dcplx und dpolr, für extended-genaue ecplx und epolr.
Zeiger auf komplexe Felder oder Vektoren werden mithilfe der Datentypen cfVector, cdVector und ceVector (für cartesisch-komplexe Vektoren) sowie pfVector, pdVector und peVector (für Vektoren komplexer Zahlen in Polarkoordinaten) definiert, wie unten beschrieben.

2.3 Vektoren und Arrays:
Die Datentypen fVector, dVector, eVector,
cfVector, cdVector, ceVector, pfVector, pdVector, peVector,
iVector, biVector, siVector, liVector, qiVector,
uVector, ubVector, usVector, ulVector und uiVector

Die Basis aller VectorLib-Funktionen bilden die Vektor-Datentypen, die in <VecLib.h> bzw. der Unit VecLib definiert und unten aufgelistet sind. Im Unterschied zu den statischen Arrays, die immer eine beim Compilieren festgelegte Größe besitzen, arbeiten die VectorLib-Typen mit dynamischer Speicherzuweisung und daher mit variablen Größen. Wegen dieser Flexibilität empfehlen wir den vorzugsweisen Gebrauch der letzteren. Hier sind sie also:
 

C/C++ typedef float * fVector typedef double * dVector typedef extended * eVector typedef fComplex * cfVector typedef dComplex * cdVector typedef eComplex * ceVector typedef fPolar * pfVector typedef dPolar * pdVector typedef ePolar * peVector typedef int * iVector typedef byte * biVector typedef short * siVector typedef long * liVector typedef quad * qiVector typedef uquad * uqVector typedef unsigned * uVector typedef unsigned byte * ubVector typedef unsigned short * usVector typedef unsigned long * ulVector typedef ui * uiVector

Pascal/Delphi type fVector = ^Float; type dVector = ^Double; type eVector = ^Extended; type cfVector = ^fComplex; type cdVector = ^dComplex; type ceVector = ^eComplex; type pfVector = ^fPolar; type pdVector = ^dPolar; type peVector = ^ePolar type iVector = ^Integer; type biVector = ^ByteInt; type siVector = ^SmallInt; type liVector = ^LongInt; type qiVector = ^QuadInt; type uqVector = ^UQuad; type uVector = ^UInt; type ubVector = ^UByte; type usVector = ^USmall; type ulVector = ^ULong;

Intern handelt es sich also bei einem Datentyp wie fVector um einen "Zeiger auf float". Man sollte ihn sich allerdings lieber als "float-Vector" vorstellen.
 

N.B.: In der Windows-Programmierung wird häufig der Buchstabe l" oder L" eingesetzt, um long int-Variablen zu bezeichnen. Um Verwechslungen vorzubeugen, wird hier für long int stets das aus zwei Buchstaben bestehende Kürzel "li" oder "LI" verwendet und für unsigned long das Kürzel "ul" oder "UL". Konflikte mit den Präfixen für long double-Vektoren werden durch Ableitung deren Kürzel vom Alias-Namen "extended" und den Gebrauch von "e", "ce", "E" und "CE" umgangen, wie bereits oben und auch in den folgenden Abschnitten beschrieben.

 
C/C++-spezifisch:
Um auf Vektor-Elemente zuzugreifen, wird wie für statische Arrays der Operator [] verwendet, z.B. VA[375] = 1.234;
Alternativ können die typenspezifischen Funktionen VF_element (gibt den Wert des gewünschten Elementes zurück, der mit dieser Funktion aber nicht überschrieben werden kann) und VF_Pelement (gibt einen Zeiger auf das gewünschte Element zurück) verwendet werden. Insbesondere einige ältere Borland C-Versionen haben einen Fehler in der Pointer-Arithmetik, der die Verwendung von VF_Pelement anstelle der Schreibweise X+n für einen Zeiger auf das n-te Element nötig macht. VF_Pelement kann zur Zuweisung einzelner Vektor-Elemente verwendet werden, z.B.:
*VF_Pelement( X, 3 ) = 5.7;
In Ihren Programmen können Sie die dynamischen OptiVec-Vektoren mit klassischen statischen C-Arrays mischen.
Beispiel:
float a[100]; /* klassischer statischer Array */
fVector b=VF_vector(100); /* VectorLib-Vektor */
VF_equ1( a, 100 ); /* setze die ersten 100 Elemente von a = 1.0 */
VF_equC( b, 100, 3.7 ); /* setze die ersten 100 Elemente von b = 3.7 */

Pascal/Delphi-spezifisch:
Der Zugriff auf einzelne Elemente dynamisch erzeugter Vektoren ist bei Pascal/Delphi nicht mit dem Operator [] möglich, sondern nur über die typenspezifischen Funktionen VF_element (gibt den Wert des gewünschten Elementes zurück, der mit dieser Funktion aber nicht überschrieben werden kann) und VF_Pelement (gibt einen Zeiger auf das gewünschte Element zurück). VF_Pelement kann zur Zuweisung einzelner Vektor-Elemente verwendet werden, z.B.:
VF_Pelement( X, 3 )^ := 5.7;
Wie in C/C++ können die VectorLib-Vektortypen mit statischen Arrays des klassischen Pascal-Stils gemischt werden. Statische Arrays müssen mit Hilfe des Adress-Operators an OptiVec-Routinen übergeben werden. Hier lautet das oben für C/C++ gegebene Beispiel:
a: array[0..99] of Single; (* klassischer statischer Array *)
b: fVector;(* VectorLib-Vektor *)
b := VF_vector(100);
VF_equ1( @a, 100 ); (* setze die ersten 100 Elemente von a = 1.0 *)
VF_equC( b, 100, 3.7 ); (* setze die ersten 100 Elemente von b = 3.7 *)
Delphi bietet zusätzlich auch dynamisch allozierte Arrays, die ebenfalls als Argumente an OptiVec-Funktionen übergeben werden können. Die folgende Tabelle vergleicht die Zeiger-basierten Vektoren von VectorLib mit den verschiedenen Array-Typen von Pascal/Delphi:
 

	OptiVec-Vektoren	Pascal/Delphi-Arrays (statisch/dynamisch)
Ausrichtung des ersten Elements	an 32-byte-Grenze für optimale Cache-Zeilen-Anpassung	2- oder 4-byte-Grenze (kann Zeilenumbruchs-Strafzyklen für double, QuadInt zur Folge haben)
Ausrichtung folgender Elemente	gepackt (d.h. keine Dummy-Bytes zwischen Elementen, auch nicht für 10- und 20-bit-Typen)	Arrays müssen in Delphi als "packed" deklariert werden, um kompatibel mit OptiVec zu sein
Index-Bereichsprüfung	keine	automatisch mittels eingebauter Größeninformation
dynamische Speicherzuweisung	function VF_vector,  VF_vector0	procedure SetLength (nur Delphi)
Initialisierung mit 0	optional durch Aufruf von VF_vector0	immer (nur Delphi)
Freigabe	function V_free,  V_freeAll	procedure Finalize (nur Delphi)
einzelne Elemente lesen	function VF_element: a := VF_element(X,5); nur Delphi: typecast in Array ebenfalls möglich: a := fArray(X)[5];	Index in eckigen Klammern: a := X[5];
einzelne Elemente schreiben	function VF_Pelement: VF_Pelement(X,5)^ := a; nur Delphi: typecast in Array ebenfalls möglich: fArray(X)[5] := a;	Index in eckigen Klammern: X[5] := a;
Übergabe an OptiVec-Funktion	direkt: VF_equ1( X, sz );	Adress-Operator: VF_equ1( @X, sz );
Übergabe von Subvektor an OptiVec-Funktion	function VF_Pelement: VF_equC( VF_Pelement(X,10), sz-10, 3.7);	Adress-Operator: VF_equC( @X[10], sz-10, 3.7 );

 
Zusammenfassend läßt sich sagen, daß die Pascal/Delphi-Arrays etwas bequemer zu verwenden und durch die Index-Bereichsprüfung auch sicherer sind, während die Zeiger-basierten OptiVec-Vektoren schneller verarbeitet werden können (durch die bessere Speicherausrichtung und den Fortfall der Index-Bereichsüberprüfung).

Zurück zum VectorLib-Inhaltsverzeichnis     OptiVec Home

2.4 Vektorfunktions-Präfixe

Zurück zum VectorLib-Inhaltsverzeichnis     OptiVec Home

---

3. Nur C++: VecObj, das objekt-orientierte Interface für VectorLib

• automatische Speicherzuweisung und -freigabe
• vereinfachte Vektor-Behandlung
• stark vermindertes Risiko von Speicherfehlern
• erhöhte Sicherheit des Speicherzugriffs
• intuitive überladene Operatoren
• einfachere Funktionsaufrufe

• erhöhter Aufwand für den Compiler
• größerer Overhead (wie für jeden gekapselten C++-Code!) und als Folge hiervon
• erhöhte Programmcode-Länge
• leicht verminderte Rechengeschwindigkeit
• Vektoren können derzeit nur als Ganzes, nicht in Teilen verarbeitet werden

MS Visual C++ und Borland C++ Builder (nicht aber frühere Borland C++-Versionen): Die Direktive
"using namespace OptiVec;"
sollte entweder im Funktionskörper jeder ein tVecObj verwendenden Funktion oder im globalen Deklarationsteil eines Programmes auftauchen. Der Platz in den einzelnen Funktionskörpern ist sicherer, da er potentielle Namespace-Konflikte mit anderen Funktionen vermeidet.
Die Vektor-Objekte werden als classes vector<T> implementiert, die die Vektor-Adresse (den Zeiger) und seine Größe size kapseln.
Für einfachere Verwendung wurden diesen Klassen Alias-Namen zugewiesen als fVecObj, dVecObj usw., wobei der Datentyp wie sonst in OptiVec durch den ersten oder die ersten beiden Buchstaben des Klassennamens angezeigt wird.

Alle VectorLib für einen bestimmten Datentyp definierten Funktionen sind als Member-Funktionen der betreffenden class tVecObj enthalten.
Die Konstruktoren können vier Formen annehmen:
vector(); // kein Speicher zugewiesen; size auf 0 gesetzt
vector( ui size ); // Vektor von size Elementen erzeugt
vector( ui size, T fill ); // desgleichen, aber mit "fill" initialisiert
vector( vector<T> init ); // erzeugt eine Kopie des Vektors "init"

Für alle Vektor-Klassen sind die arithmetischen Operatoren
+    -    *    /    +=    -=    *=    /=
definiert, mit der Ausnahme, daß für die polar-komplexen Vektor-Klassen nur Multiplikationen und Divisionen, nicht aber Addition und Subtraktion unterstützt werden. Diese Operatoren stellen den einzigen Fall dar, in dem das Ergebnis einer Berechnung direkt einem Vektor-Objekt zugewiesen werden kann, wie z.B.
fVecObj Z = X + Y; oder
fVecObj Z = X * 3.5;
Man beachte aber, daß die Syntax-Regeln von C++ eine wirklich effiziente Implementierung dieser Operatoren nicht zulassen. Die arithmetischen Member-Funktionen sind wesentlich schneller. Wenn es auf Rechengeschwindigkeit ankommt, benutze man daher die letzteren anstelle der Operatoren-Syntax:
fVecObj Z.addV( X, Y ); oder
fVecObj Z.mulC( X, 3.5 );

Der Operator * bedeutet Multiplikation der einzelnen Elemente miteinander und nicht das Skalarprodukt zwier Vektoren.

Alle übrigen arithmetischen und mathematischen Funktionen können nur als Member-Funktion des betreffenden Ausgabe-Vektors aufgerufen werden, wie z.B. Y.exp(X). Obwohl es sicher logischer wäre, auch diese Funktionen so zu definieren, daß man stattdessen "Y = exp(X)" schreiben könnte, wurde die Syntax der Member-Funktionen gewählt, da sie wesentlich effizienter implementiert werden kann: Der einzige Weg, die zweite Variante zu implementieren, besteht darin, das Ergebnis der jeweiligen Funktion in einem temporären Vektor zwischenzuspeichern, der anschließend in Y kopiert wird. Hierdurch werden Rechenaufwand und Speicheranforderungen erhöht. Wir sind aber an Ihrer Meinung interessiert: Würden Sie trotzdem die Syntax "Y = func(X);" gegenüber der Member-Funktions-Syntax "Y.func(X);" vorziehen und ihre Nachteile in Kauf nehmen wollen? Bitte senden Sie uns Ihren Kommentar an support@optivec.de. Diese Syntax könnte in späteren Versionen von VecObj zur Verfügung gestellt werden.

Während die meisten VecObj-Funktionen Member-Funktionen des Ausgabe-Vektors sind, gibt es einige Funktionen, die gar keinen Ausgabe-Vektor haben. In diesen Fällen sind die Funktionen Member-Funktionen eines Eingabe-Vektors.
Beispiel: s = X.mean();.

Sollten Sie einmal in die Lage kommen, ein VecObj-Vektorobjekt mit einer "klassischen" C-VectorLib-Funktion verarbeiten zu wollen (z.B., um nur einen Teil zu verarbeiten), rufen Sie bitte die Member-Funktionen
getSize() für die Vektorlänge,
getVector() für den Zeiger (vom Typ tVector)  oder
Pelement( n ), um einen Zeiger auf das n'te Element zu bekommen.

Fortsetzung: Kap. 4. VectorLib-Funktionen: Ein kurzer Überblick
Zurück zum VectorLib-Inhaltsverzeichnis     OptiVec Home      OptiVec Home 

Copyright © 1998-2013 OptiCode – Dr. Martin Sander Software Development