Alles rund um Compiler und Softwareentwicklung

Nochmal zu Herrn Stillers Matrix-Reloaded. Wenn ich die Matrixmultiplikation zweier quadratischer Matrizen mit der Seitenlänge N habe, erfordert die Berechnung der Endmatrix 2*N^3 Fließkomma-Operationen? Oder liege ich da falsch?
Falls das stimmt: Auch mit dem neuen MinGW 4.9 kommt mein K8 @ 1,6 GHz nicht über 0,6 GFLOPs hinaus. Das ist ziemlich mager. LinX sagt mir, der Prozessor sollte auf einem Kern ca. 1,6 GFlops schaffen.
 
Die (beste) ausgefallenste Lösung bringt ohne den Softwaresupport nichts und die Freaks, die den Genius der Produkte erkennen, sind nicht "Der Markt".
Mantle ist jetzt endlich mal ein positives Beispiel für AMD, genau sowas meine ich ja.

Stimmt. Aber du musst dir im Klaren, dass dies ein sehr langer Weg ist.
Der erste Schritt ist erst mal eine Parallelisierung auf einem anerkannten Standard. Die meisten Hochsprachen haben dafür mittlerweile Sprachkonstrukte eingeführt, mit denen diese Abstraktion möglich ist, wie z.B. C++ AMP. Dann müssen Standards zur Zertifizierung eingereicht werden, welche dann verabschiedet werden müssen, bei allen Interessengegensätzen. Dann muss sich dieser Standard in den Compilern wiederfinden und letztlich dieser Standard von den Entwicklern angenommen werden. Bis es soweit ist, vergehen meist Jahre. Es ist natürlich hilfreich, wenn ein Entwickler sieht und fühlt, der neue Standard bringt Vorteile. Und zwar nicht nur auf einer wenig verbreiteten Plattfrom wie AMD. Wenn ist damit nur 10% der Kunden erreiche, wird das wenig Begeisterung auslösen.
 
Nochmal zu Herrn Stillers Matrix-Reloaded. Wenn ich die Matrixmultiplikation zweier quadratischer Matrizen mit der Seitenlänge N habe, erfordert die Berechnung der Endmatrix 2*N^3 Fließkomma-Operationen? Oder liege ich da falsch?
Passt im Grunde schon: für jedes einzelne Zell-Ergebnis E_ij in der Ergebnis-Matrix benötigt man genau N Multiplikationen und N - 1 Additionen. Die Ergebnis-Matrix hat wiederum N ^ 2 Zellen.

Code:
for(int i = 1;   i <= n; i++)
  for(int j = 1; j <= n; j++)  {
     rij= 0;
     for(int k = 1;  k <= n; k++)
       rij += a_ik * b_kj;
}

- Der Standardalgorithmus zur Multiplikation zweiern n x n -Matrizen benötigt n ^3 skalare Multiplikationen und n ^2 * (n–1) Additionen
- Zeitaufwand: theta (n^3)
- Speicherbedarf: theta (n^2)
S. 9 aus: http://cvpr.uni-muenster.de/teaching/ss09/info2SS09/script/Kapitel4-Komplexitaet-1.pdf
 
Zuletzt bearbeitet:
Passt im Grunde schon: für jedes einzelne Zell-Ergebnis E_ij in der Ergebnis-Matrix benötigt man genau N Multiplikationen und N - 1 Additionen. Die Ergebnis-Matrix hat wiederum N ^ 2 Zellen.
Wobei es in der Praxis tatsächlich N Additionen sein können. Sieht man ja auch gut an deinem Beispiel. Um auf N - 1 zu kommen, müsste man den ersten Durchlauf der innersten Schleife nach aussen ziehen. Also in etwa so:
Code:
for (int i = 0; i < n; ++i)
  for (int j = 0; j < n; ++j)
  {
    rij = a_i0 * b_0j;
    for (int k = 1; k < n; ++k)
      rij += a_ik * b_kj;
  }

Und ein Aufwand von 2 * N^3 ist in der Praxis auch nur Theorie. :) Du siehst ja an deinem Beispiel, dass da noch Inkrementoren/Dekrementoren für die Schleifen hinzukommen. Bei überschaubaren Schleifen, mit einer festen Anzahl an Durchläufen, lässt sich das problemlos mittels Loop Unrolling auflösen. Ansonsten hast du weitere N^3 + N^2 + N Operationen. Unterm Strich sind es in der Praxis also eher 3 * N^3 + N^2 + N Operationen.


@miriquidi

Du solltest halt bedenken, dass es ausser den ADD, INC/DEC und MUL Instruktionen noch andere Instruktionen drumherum gibt. Gerade Sprünge können viel kosten.
 
Zuletzt bearbeitet:
Ist ja auch bei Linpack nicht anders, Adressen usw. müssen parallel berechnet werden. Gezählt werden aber nur die Fließkomma-Operationen.
0,6 GFlops bei 1,6 GHz Takt wären 0,375 Fließkomma-Instruktionen pro Takt. Ziemlich mager.
 
Ja das ist Rosinen Pickerei, die ganz großen Schübe 100%+ kommen nicht durch Optimieren sondern durch den Einsatz von neuen Features (AVX2).
Intel ist nun mal soweit, das sie ihre Quell Code nur nochmal durch den Compiler laufen lassen damit neue Befehlssätze genutzt werden.
Das kann AMD noch nicht, sie sind aber auf dem richtigen Weg mit HSA.

Jein, bei beiden kam soweit ich richtig in Erinnerung habe AVX (2) zu Einsatz, selbst wenn es würde nur ein Faktor von ~2x ausmachen. Das ist ein Beispiel das zeigt, das ein guter Code und/oder ein guter Compiler mit den richtigen Flags mehr an Geschwindigkeit kosten bzw. herausholen kann, als jeder Befehlssatz XY oder neue CPU bringen kann. Das hat uns auch unser Professor aufgezeigt.

Die Software bzw. Compiler hat einen weit größeren Einfluss auf die Performance als die "richtige" Hardware, das ist die Grundaussage solcher Tests. Eine Benachteiligung um ein paar Prozent um einen Wettbewerbsvorteil zu erlangen, kann man die diesem breiten Performance-Spektrum sehr gut "verstecken" bzw. schwer nachweisen und falls man erwischt wird war es unabsichtlich ;-)
 
@Gruffi
Dein compilat macht bei x264 keine Unterschied gegenüber den VLAN.
Mit x265 bräuchte ich zuerst mal ein Crashkurs, die Parameter scheinen anders zu sein.

@bbott
Ok, und die Math Libs haben keinen Einfluss auf das Ergebnis?
Kennt dein Professor FMA4 & XOP überhaupt schon?

Ich kann ja mal SSE4.1, SSE3 und AVX(1) gegentesten mit dem y-cruncher.
 
Ist ja auch bei Linpack nicht anders, Adressen usw. müssen parallel berechnet werden. Gezählt werden aber nur die Fließkomma-Operationen.
0,6 GFlops bei 1,6 GHz Takt wären 0,375 Fließkomma-Instruktionen pro Takt. Ziemlich mager.
Für simple Matrixmultiplikationen ohne spezielle Optimierungen wäre das sogar ausgesprochen viel. Da liegen die erreichten GFLOPS normalerweise deutlich niedriger. Man sollte auch nicht vergessen, dass der Speicherzugriff aufgrund der orthogonalen Verarbeitung zum Flaschenhals wird. Das ist nochmal eine ganz andere Geschichte, als wenn du alle Daten schön linear hintereinander weg berechnen könntest. Woher kommen denn deine 0,6 GFLOPS? Und mit Linpack/Linx kann man die Ergebnisse auch nicht vergleichen. Das sind andere Algorithmen.


Intel ist nun mal soweit, das sie ihre Quell Code nur nochmal durch den Compiler laufen lassen damit neue Befehlssätze genutzt werden.
Das kann AMD noch nicht
Natürlich kann das AMD auch. Nur halt nicht mit dem Intel Compiler, sondern mit Compilern wie GCC oder Open64. Da wird auch genügend Vorarbeit geleistet, damit neue Hardware beim Release auch softwareseitig unterstützt werden.

---------- Beitrag hinzugefügt um 18:03 ---------- Vorheriger Beitrag um 17:53 ----------

Mit x265 bräuchte ich zuerst mal ein Crashkurs, die Parameter scheinen anders zu sein.
Ich habe die gleichen Parameter wie bei x264 verwendet. Sieht man ja auch in den Screenshots. Hat problemlos funktioniert.
 
Und ein Aufwand von 2 * N^3 ist in der Praxis auch nur Theorie. :) Du siehst ja an deinem Beispiel, dass da noch Inkrementoren/Dekrementoren für die Schleifen hinzukommen. Bei überschaubaren Schleifen, mit einer festen Anzahl an Durchläufen, lässt sich das problemlos mittels Loop Unrolling auflösen. Ansonsten hast du weitere N^3 + N^2 + N Operationen. Unterm Strich sind es in der Praxis also eher 3 * N^3 + N^2 + N Operationen.
Schleifen sind noch ein extra Punkt. Hatte auch ausdrücklich nur von Multiplikationen und Additionen geschrieben und mich vorsichtig ausgedrückt ("im Grunde schon").

Das Ganze dann für FMA optimieren... ?
 
@bbott
Ich kann ja mal SSE4.1, SSE3 und AVX(1) gegentesten mit dem y-cruncher.
Ok, zumindest bei 32M sind es nur wenige Sekunden die FMA4 & XOP schneller sind, scheint wirklich nicht so viel raus zu reisen!
Dein Professor scheint zu wissen wovon er redet! ;)
Mit x86 SSE3, wirkt auch das "NRAC Blocking disabled" (~25% schneller) im Vergleich zu x64 SSE3 immer noch langsamer.

Natürlich kann das AMD auch. Nur halt nicht mit dem Intel Compiler, sondern mit Compilern wie GCC oder Open64. Da wird auch genügend Vorarbeit geleistet, damit neue Hardware beim Release auch softwareseitig unterstützt werden.

---------- Beitrag hinzugefügt um 18:03 ---------- Vorheriger Beitrag um 17:53 ----------


Ich habe die gleichen Parameter wie bei x264 verwendet. Sieht man ja auch in den Screenshots. Hat problemlos funktioniert.
:o Wenn das die entsprechenden Compiler schon können, wird es wohl nicht mehr lang dauern bis CPU+GPU einen gemeinsamen Speicherpool zur Verfügung haben.
Ein WasserPool wäre jetzt auch cool! 8)

Ich hab die x264.exe einfach bei den bekannten BenchScripten eingefügt und die Original .exe in .org umbenannt.
Beim UHD Bench lief sie leider nicht, scheinbar keine mp4 Unterstützung.

MfG
 
Ja, ich schrieb doch weiter vorne, dass du beim Eingangsmaterial auf das beschränkt bist, was x264 von Haus aus verarbeiten kann, wie YUV. Für zusätzliche Unterstützung, wie MPEG, müsste man extra noch Bibliotheken übersetzen und dazu linken. Darauf hatte ich irgendwie keine Lust mehr.
 
Kennt dein Professor FMA4 & XOP überhaupt schon?.

Das gab es zu dieser Zeit nicht, da war SSE4.x das aktuellste. Aber warum sollte das etwas zur Sache tun?

---------- Beitrag hinzugefügt um 22:28 ---------- Vorheriger Beitrag um 22:10 ----------

Ok, zumindest bei 32M sind es nur wenige Sekunden die FMA4 & XOP schneller sind, scheint wirklich nicht so viel raus zu reisen!
Dein Professor scheint zu wissen wovon er redet! ;)

Ja, davon gehe ich aus. Wir mussten um den Kurs besuchen zu können einen Eignungstest machen, indem wir nur per Manuals zum Proggen nutzen durften in einem Text Editor (nur mit Highlighting), um die Ergebnisse am Semester Ende mit einem Abschusstest (anonym) öffentlich zu vergleichen.

Er hat Code immer in alle Einzelteile zerlegt, teils bis auf die Flags hinunter. Auch durften wir gegen Ende des Semesters selbst mit Code und Compiler Parametern herumspielen, allerdings meist ohne selbst solche Extremen Resultate bzw. Beschleunigungen zu erreichen.
 
Woher kommen denn deine 0,6 GFLOPS?
Die Matrizen haben jeweils N mal N Elemente wie in Herrn Stillers Progrämmchen.
Die GFlops habe ich über die Formel:
2 * N ^3 / Berechnungszeit
berechnet.

Muss mich wohl bei den 0,6 GFlops (K8 1,6 GHz) verrechnet haben. Sind eher 0,43. Wobei jetzt neben der erzeugten .exe immer noch ein Windows svchost.exe Prozess aufschnellt, der einen ganzen CPU-Kern für sich beansprucht. :-?
Ein i7-2640M (mit AVX Support) schafft 2,1 GFlops - mit der SSE3-LinX-Version sind es 20 GFlops.

Das ganze habe ich mit Codeblocks und MinGW 4.9 umgesetzt. Wie bekomme ich MinGW jetzt dazu SSE bzw. AVX-Code zu erzeugen?

---------- Beitrag hinzugefügt um 10:47 ---------- Vorheriger Beitrag um 07:59 ----------

Man kann das auch mit Octave/Matlab machen:
clc;
N = 5000;
A = ones(N);
B = -A;
tic
C = A*B;
D = toc;
disp( ['GFlops:', num2str(2*N^3/D/1e9)]);
Matlab R2007b:
K8 X2 1,6 GHz: 4,3 GFlops
Octace 3.8.1:
K8 X2 1,6 GHz: 0,43 GFlops
 
Das ganze habe ich mit Codeblocks und MinGW 4.9 umgesetzt. Wie bekomme ich MinGW jetzt dazu SSE bzw. AVX-Code zu erzeugen?
Wenn du die 64-bit Version von MinGW nutzt, wird automatisch mindestens SSE2 genutzt. Ansonsten kann man mit dem Flag -march eine Architektur festlegen. Dann werden alle Befehlssätze genutzt, die die Architektur unterstützt. Einzelne Befehlssatzerweiterungen kann man mit entsprechenden -m Flags explizit aktivieren, zB -mavx oder -mfma. Möchte man diese hingegen explizit nicht nutzen, dann ein no- am Anfang einfügen, zB -mno-avx oder -mno-fma. Will man maximale Optimierung mit dem MinGW, also zB auch Autovektorisierung, gibt es nach wie vor einiges beim Code zu beachten. Ein guter Artikel dazu findet sich hier.
 
Ja, ich schrieb doch weiter vorne, dass du beim Eingangsmaterial auf das beschränkt bist, was x264 von Haus aus verarbeiten kann, wie YUV. Für zusätzliche Unterstützung, wie MPEG, müsste man extra noch Bibliotheken übersetzen und dazu linken. Darauf hatte ich irgendwie keine Lust mehr.
Ich hatte nicht so viel Zeit und bin eher GUI gewohnt, ich hatte keine Parameter zur Hand bzw im Kopf.
Kein Stress, wenn du mal Zeit findest, wäre 2 Pass noch interessant. ;)

Übrigens, beim y-cruncher kann man sich ein paar Compiler Optionen Anzeigen lassen:

Evt. könnt ihr mehr damit Anfangen als meine Wenigkeit.
 
Kommt halt immer darauf an, wie portabel der Code gehalten ist. Laut Entwickler sollten aber auch andere Compiler funktionieren.
 
Wäre es für dich ein großer Aufwand, es zu versuchen? Ich habe keine Ahnung von so etwas.
 
Ich kann mir das Quellcodepaket ja mal angucken, ob da ein für MinGW geeigneter Buildpfad dabei ist.

---------- Beitrag hinzugefügt um 18:52 ---------- Vorheriger Beitrag um 16:52 ----------

Das Paket ist über ein halbes GB gross. Man müsste auch noch die Mozilla Build Tools einrichten. Sry, aber das ist mir im Moment zu viel Aufwand.
 
Wenn du die 64-bit Version von MinGW nutzt, wird automatisch mindestens SSE2 genutzt. Ansonsten kann man mit dem Flag -march eine Architektur festlegen. Dann werden alle Befehlssätze genutzt, die die Architektur unterstützt. Einzelne Befehlssatzerweiterungen kann man mit entsprechenden -m Flags explizit aktivieren, zB -mavx oder -mfma. Möchte man diese hingegen explizit nicht nutzen, dann ein no- am Anfang einfügen, zB -mno-avx oder -mno-fma. Will man maximale Optimierung mit dem MinGW, also zB auch Autovektorisierung, gibt es nach wie vor einiges beim Code zu beachten. Ein guter Artikel dazu findet sich hier.
Ich selbst habe hier nur 32-Bit Ausführmöglichkeiten. "-mss3" bringt bei mir nichts.

Bezüglich der Autovektorisierung-Anleitung: Mein kompiliertes Programm stürzt schon beim ersten Beispiel in der Ausführung ab.
Wenn ich mir den Artikel durchlesen, kann ich aber durchaus jene Software-Chefs verstehen, die lieber reichlich Geld für einen Intel-Compiler hinlegen, der auch mit halbwegs „normalem“ Code schnelle Programme erzeugt. Das kommt auf Dauer vermutlich wesentlich günstiger, als den erzeugten Maschinencode zu reassemblieren und zu analysieren. Man validiert keinen Rechencode um ihn das hinterher nochmal alles umzubauen, nur damit der Compiler auch die Autovektorisierung hinbekommt. Zumindest nicht, wenn man die Dienstleistung noch relativ günstig einkaufen kann.
 
Ich selbst habe hier nur 32-Bit Ausführmöglichkeiten. "-mss3" bringt bei mir nichts.

Bezüglich der Autovektorisierung-Anleitung: Mein kompiliertes Programm stürzt schon beim ersten Beispiel in der Ausführung ab.
Womöglich hast du dann Instruktionen im Code, die dein Prozessor nicht unterstützt. Für Matrixmultiplikationen reicht normalerweise SSE/SSE2 auch aus. Kannst du das Beispiel mal posten, wenn es nicht allzu lang ist?

Wenn ich mir den Artikel durchlesen, kann ich aber durchaus jene Software-Chefs verstehen, die lieber reichlich Geld für einen Intel-Compiler hinlegen, der auch mit halbwegs „normalem“ Code schnelle Programme erzeugt. Das kommt auf Dauer vermutlich wesentlich günstiger, als den erzeugten Maschinencode zu reassemblieren und zu analysieren.
Naja, das macht man normalerweise ja auch mit dem GCC nicht. Das ist halt ein Artikel, der mal etwas über den Tellerrand hinaus schaut. Und aus jedem x-beliebigen Code kann der ICC auch keine Autovektorisierung hervorzaubern. Auch da muss man einiges beachten. GCC ist da mittlerweile schon auf einem relativ guten Level und braucht sich vor dem ICC nicht mehr zu verstecken.
 
Der Zusatz "-msse2" bringt auch nichts.
Der Clou am ICC scheint wohl zu sein, dass er das häufiger hinbekommt als andere Compiler.

Hat jemand anderes die Matrixmultiplikation von Herrn Stiller mittels GCC als Vektorversion hinbekommen?
 
@gruffi
Zunächst einmal: Gib Bescheid, wenn es dich nervt, derartige Anfragen zu erhalten.
Hättest du Lust/Interesse zu versuchen, SMPlayer mit einem deiner Compiler zu erstellen? Es soll über Qt möglich sein, ab 14.3 mit bis zu Qt 5. SMPlayer gibt es in 32 und 64 Bit.
Downloads: http://smplayer.sourceforge.net/en/downloads
Compilier-Tutorial: http://forum.smplayer.info/viewtopic.php?f=4&t=4

Oder wie wäre es mit MPC BE? Auch dieses gibt es in 32 und 64 Bit.
Source code: http://sourceforge.net/projects/mpcbe/files/MPC-BE/MPC-BE Source Code/MPC-BE 1.4.2 Source Code/
 
Das How To zu SMPlayer ist eigentlich recht verständlich. Das bekommt man auch ohne grosse Compilerkenntnisse hin. MPC-BE kann ich mir mal anschauen. Vor dem Wochenende wird das aber nix.
 
Keine Ahnung ob das jemanden interessiert, aber nachdem der Global Foundries Prozesse Thread bereits von der Diskussion um defekte Motherboards oder Prozessoren belegt ist poste ich es mal hier.

Virtualbox erlaubt das Setzen der CPUID, ließe sich damit der Einfluß Einfluß der intelschen Compilerhandbremse auf den Code ermitteln?

--cpuid <leaf> <eax> <ebx> <ecx> <edx>: Advanced users can use this command before a teleporting operation to restrict the virtual CPU capabilities that VirtualBox presents to the guest operating system. This must be run on both the source and the target machines involved in the teleporting and will then modify what the guest sees when it executes the CPUID machine instruction. This might help with misbehaving applications that wrongly assume that certain CPU capabilities are present. The meaning of the parameters is hardware dependent; please refer to the AMD or Intel processor manuals.
 
Zurück
Oben Unten