AMD und SSE5
-
Theoretisch muesste das bei quadr. Matrizen reichen - ja.
Wobei man das praktisch aber so haeufig braucht: KA. Ich habe es bisher AFAIR noch nie gebraucht.
Aber die 128Bit sind trotzdem schoen.
-
ich meinte das auch nicht unbedingt wörtlich - indizes vertauschen ist allerdings etwas zu abstrakt für assembler. prinzipiell hat man ja zwei möglichkeiten (auch kombinierbar) einen algorithmus, der zunächst ohne SIMD arbeitet, auf SIMD zu erweitern:
1. bei manchen algorithmen kann man einzelne rechenschritte unmittelbar parallel auf mehrere elemente der eingangsdaten anwenden - das ist immer schön wenn es geht, weil man so änderungen am nutzercode vermeiden kann, aus einem
foo(T* input) wird also sinngemäß ein foo_SIMD(T* input)
2. man wendet den ursprungsalgorithmus relativ ungeändert unmittelbar auf mehrere (idealerweise 4 bzw. 2) verschiedene eingangsdatenströme an;
foo(T* input) wird zu foo_SIMD(T* input1, T* input2, T* input3, T* input4)
jeder einzelne inputdatenstrom korrespondiert dann mit der entsprechenden position in einem register
das bietet sich an, weil SIMD operationen grundsätzlich erstmal ein vertikales verarbeitungsmuster verwenden (d.h.jedes element des einen operanden wird mit dem entsprechenden element des anderen verknüpft). mit (S)SSE3 gibt es auch einige Operationen, die horizontal arbeiten, daraus allein wird man aber kaum komplexe algorithmen effizient ableiten können.problematisch daran ist nun, dass man dafür die einzelnen datenströmen abwechseln muss (und wenn der algorithmus seiner natur nach - zum beispiel ein hashing - nicht wiederholt auf denselben daten arbeitet, macht es keinen sinn, die daten in diesem transformierten zustand zwischenzuspeichern) - die Problamatik zwischen SoA und AoS Organisation in Intels Optimierungsmanual - und dieser reorganisationsvorgang ist nunmal äquivalent zum transponieren einer 4x4 matrix. und weil letzteres nicht einer so langen erklärung bedarf, hab ich dieses genannt - eigentlich hab ich selbst mit vektorrechnung auch nicht viel am hut
-
"Structure of Array" vs. "Array of Structure"? Mit dem Problem bin ich eigentlich nicht vertraut, aber geht es da nicht eher um Cache-Treffer? Ich glaube, das Problem wird eher durch immer größere Caches angegangen.
/me erwartet, im Jahr 2011 bis 2012 256MB L3-Cache auf Prozessoren zu finden.
-
Gregor schrieb:
"Structure of Array" vs. "Array of Structure"? Mit dem Problem bin ich eigentlich nicht vertraut, aber geht es da nicht eher um Cache-Treffer? Ich glaube, das Problem wird eher durch immer größere Caches angegangen.
/me erwartet, im Jahr 2011 bis 2012 256MB L3-Cache auf Prozessoren zu finden.
Mit Cache-Problemen hat das nichts zu tun.
-
camper schrieb:
Mit Cache-Problemen hat das nichts zu tun.
Dann war das wohl'n Schuss ins Leere. ...wenn ich mir über die Organisation der Daten aus technischer Sicht Gedanken mache, dann hat das fast immer mit dem Cache zu tun.
-
Nehmen wir einfach mal der Einfachkeit halber (und weil es für mich mal ein Problem war) einen Hashingalgorithmus, wie MD5
MD5 konsumiert schön sequentiell 32bit werte - und dieser vorgang ist selbstverständlich nicht vektorisierbar - denn das ist äquivalent zu erhöhter Angreifbarkeit.
wir haben also unseren bytestrom:
[..00..][..01..][..02..] (jedes Kästchen 32bit)
und der wird Konsumiert schematisch op(op(op(op(state,[00]),[01]),[02])...wenn ich jetzt SIMD einsetzen will - und SSE2 bietet sich da ja an, denn damit kann ich 4 integer in ein register stecken:
alsostream 0: [00|01|02|03] [04|05|06|07] [08|09|0A|0B] [0C|0D|0E|0F] ...
stream 1: [00|01|02|03] [04|05|06|07] [08|09|0A|0B] [0C|0D|0E|0F] ...
stream 2: [00|01|02|03] [04|05|06|07] [08|09|0A|0B] [0C|0D|0E|0F] ...
stream 3: [00|01|02|03] [04|05|06|07] [08|09|0A|0B] [0C|0D|0E|0F] ...movdqa liest jeweils eine Zeile ein
wir brauchen aber ein Register, das den Inhalt, so wie er hier vertikal jweils in einer Spalte steht, enthält - man sieht sehr schnell, dass nichts weiter als das transponieren einer 4x4 matrix istjeder bytestrom liegt sequentiel im speicher, für SIMD, muss ich aber jedesmal erst einmal je 4 bytes aus jedem bytestrom in ein register bekommen, um dann einen SIMD-Befehl, der äquvivalent zur einfachen Version des Algorithmus eine Operation auf 4 verschiedenen operanden durchführt.
Und das geht, nach dem Laden von je 16byte aus jedem stream, nur durch Reorganisation über iirc 12 Befehle, die sonst nichts weiter tun. Und wegen der großen Abhängigkeit dieser vielen Befehle von einander ist das Ganze im wesentlichen durch (zugegeben relativ geringe) Latenz begrenzt.Diese Problematik trifft letztlich jeden Algorithmus, bei dem ich SIMD einfach durch Vervielfachung des Inputs verwenden will.
-
Gibts eigentlich auch SSE4?
-
hmmmmmm schrieb:
Gibts eigentlich auch SSE4?
ja - wird mit der nächsten Prozessorgeneration von Intel eingeführt werden.
-
BTW: Diese SSE-Befehlssätze realisieren ja in gewisser Weise einiges an Parallelverarbeitung. Meint Ihr, das wird mit der Vermehrung an Kernen in Prozessoren auf Dauer heruntergefahren? Ich meine: Viele Kerne stellen IMHO ein mächtigeres Werkzeug bezüglich der Parallelverarbeitung dar. Da stellt sich für die Chiphersteller doch die Frage, für was sie die Chipfläche nutzen. Es könnte ja sein, dass der Trend auf Dauer wieder zu einfacheren Kernen geht. ...man schaue sich nur Intels "Tera-Scale Initiative" an: In dem dort realisierten Experimentalchip sind 80 sehr einfache Kerne zu finden.
-
Was derzeitig als Multicore angeboten wird und wie man derzeit Threads programmiert, geht imho eher in eine andere Richtung als das was man mit SIMD macht. Bei Threads trennt man ja eher die Daten auf, die von jedem Thread behandelt werden, während man bei SIMD eher die Daten zusammen fasst.
Cell/IA64 gehen da ja in eine andere Richtung. Dort lassen sich eben unabhängige Befehle beliebig verteilen, wenn man dem Prozessor einfach mehrfach die gleiche Komponente gibt.
-
mir waere es neu dass man matrix-transponieren so oft braeuchte, kenne noch niemanden der deswegen ein perofrmance-problem haette. was aber doch sehr peinlich ist, ist dass es bis heute kein dot-product gibt. das ist schon recht albern.
erstmal steht SSE128 bei amd an, damit schafft man es doch tatsaechlich nicht nur mit 64bit performance zu arbeiten
und dann in 2jahren (wohl eher 3) SSE5, und schwubs hat man es nach ewigkeiten geschaft die grundfaehigkeiten in SSE hinein zu bekommen die jede andere SIMD cpu hat (siehe powerPC, Mips, Nec, etc.).von anfang an ist SSE sowas von unnuetz. die grundlegensten dinge fehlen, MMX war um laengen besser.
wenn ihr euch mal ne schoene vector-cpu anschauen wollt: http://mrmrice.fx-world.org/vfpu.html
[edit]
kleiner ausschnit aus der featurelist* 128 32bit IEEE float registers, with support for Nvidia halffloats, integer, and pixel format conversions (like 4444, 5650)
* 4x4, 3x3 and 2x2 matrix operations, with room to hold 8 4x4 matrices
* Vector and SIMD (single instruction, multiple data) instructions on 2, 3 or 4 values
* quaternion multiply
* Supports various functions ..reciprocal (1/x), one's complement, reciprocal square root
* Built in constants for common mathematical values like e, pi, 2/pi. pi/2
* Supports many common vector operations like scaling, dot product, cross product, transform by matrix
* Has a random number generator that can return integer and floating point values
* Prefix instructions that allow you to perform absolute value, change order of vector components, etc while performing vector operations
...