Multitasking abschalten

[BA_Byte]

Hallo allerseits.

Ich habe ein Frage zum Thema Multitasking bei Betriebssystemen.

Meine Aufgabe ist es die Laufzeit eines Codes zu analysieren, um diese korrekt zu bestimmen, muss jedoch kurzzeitig das Multitasking des Betriebssystems abgeschaltet werden.

Konkreter:

Der PC bekommt über einen I/O Port (Parallel, Seriel oder USB, ist an sich egal) ein Signal, das heisst ein bestimmtes Bit wird auf 1 gesetzt. Solange dieses Bit auf 1 ist, muss mein Code ausgeführt werden die 100%ige Aufmerksamkeit des Prozessors kriegen, um so die Laufzeit genau bestimmen zu können.

Diese zu messende Codepassage ist in Assembler geschrieben, alles drumherum in C.

So nun bräuchte ich ein paar Denkanstöße wie das realisierbar wäre.

Kann man unter Windows das Multitasking kurz unterbingen?

Wie sieht das mit Linux oder anderen Betriebssystemen aus?

Gruß

[flashpixx]

Mir wäre nicht bekannt, dass man das Multitaskingsystem deaktivieren kann, denn es ist im Code des OS kompiliert und somit unumgänglich.

Du kannst ein Echtzeitbetriebssystem wie QNX verwenden, aber selbst dann ist Deine Annahme falsch, denn Du wirst nie 100% Aufmerksamkeit für Deinen Code haben können, das ist real nicht möglich ( Echtzeit ).

Echtzeit bedeutet, dass Dir für eine Instruktion eine maximale Zeitdauer der Bearbeitung nicht überschritten wird.

Zusätzlich hast Du in jedem OS Systemprozesse, die laufen müssen, damit die Infrastruktur des OS überhaupt funktioniert, z.B. wenn Deine Daten an die Hardware des Rechners ankommen, würde Dein Programm, wenn es in Echtzeit liefe, gar nicht mitbekommen, denn die Hardware löst bei eingehenden Signalen einen Interrupt aus, der vom OS dedektiert wird, das dann die Daten holt und an eine definierte Schnittstelle liefert. Dein Programm setzt erst auf OS Seite an, wenn es also 100% CPU Leistung hätte, dann würdest Du gar nicht wissen, dass Daten ankommen, denn die OS Zugriffe würden nicht statt finden.

Ich gehe davon aus, dass Du hier einen völlig falsche Vorstellung hast. Wenn Du Die worst-case Laufzeit Deines Algorithmus wissen willst, dann kann man diese berechnen Landau-Symbole wenn Du die reale Laufzeit im System haben willst, dann kann man z.B. die Anzahl der CPU Zyklen zwischen zwei Punkten im Programm messen und aufgrund dessen die Laufzeit bestimmen.

Generell gilt aber, dass meist handgeschriebener Assemblercode oft schlechter läuft als compilierter Code einer Hochsprache, denn die heutigen Compiler erzeugen so optimierten Code, dass dieser in den meisten Fällen besser ist als handgeschriebener. Es ist ein Trugschluss zu glauben, dass man damit eine bessere Performance erreichen kann. Wenn Dein Code "zu langsam" läuft, dann ist es oft ein Problem des Algorithmus und nicht des Systems.

[Guybrush Threepwood]

Ich würde auch behaupten das man Multitasking nicht abschalten kann, warum hat flashpixx ja schon sehr schön beschrieben.

Man kann die Priorität von Prozessen erhöhen, zumindest unter Windows bis zur Priorität Echtzeit. Das das aber auch nicht wirklich Echtzeit ist, zumindest nicht so wie du dir das anscheinend vorstellst sollte nach flashs Erklärung auch klar sein.

Da damit außerdem auch einige Tücken auftreten können bis hin zur Blockade des Systems sollte man das auch nur machen wenn man wirklich weiß was man tut.

Am Besten erklärst du mal das Ursprungsproblem, da gibt es bestimmt bessere und sinnvollere Lösungen für.

[flashpixx]

Der PC bekommt über einen I/O Port (Parallel, Seriel oder USB, ist an sich egal) ein Signal, das heisst ein bestimmtes Bit wird auf 1 gesetzt. Solange dieses Bit auf 1 ist, muss mein Code ausgeführt werden die 100%ige Aufmerksamkeit des Prozessors kriegen, um so die Laufzeit genau bestimmen zu können.

Aufgrund dessen schließe ich, dass Du eine Bitsequenz bekommst. Man würde hier i. Allgm. das Nyquist-Shannon-Abtasttheorem verwenden, d.h. Du musst mehr als doppelt so häufig das Signal abtasten, als es real übertragen wird, damit Du zuverlässig einen Signalwechsel dedektieren kannst. Weiterhin würde man hier aber auch nicht z.b. mehrere binäre 1er übertragen sondern, man würde generell Signalflanke verwenden, d.h. den Übergang von 0 nach 1 (vice versa), um das Signal zu finden. Denn wenn Du mehrere 1er oder 0er überträgst und das sendende System nicht im identischen Takt schwingt wie das empfangende wirst Du niemals die korrekte Anzahl an Bits erfassen können. Da technische Systeme niemals absolut identisch schwingen, ist dies somit nicht möglich ( Schwingquarz ).

[BA_Byte]

Hallo,

danke schonmal für die Antworten.

Ich beschreibe mal die Aufgabenstellung genauer da das ganze doch ziemlich allg. formuliert war.

Im Rahmen einer Bachelorarbeit, soll AES in Assembler nachprogrammiert werden, einmal mit und einmal ohne den neuen AES-NI Befehlssatz( der beinhaltet ein paar neue Befehle die AES beschleunigen).

Dann sollen die beiden Versionen auf Geschwindigkeit geprüft werden, um so die Effizienz herauszufinden.

Das ganz soll so ablaufen dass ein C Programm geschrieben werden soll, das auf ein Signal auf einem I/O Port wartet, also USB Parallel oder Seriell, kann ich mir aussuchen. Das Signal sieht einfach so aus dass bei einem bestimmten Pin eine 1 angelegt wird.

Solange diese 1 anliegt. Soll AES laufen, und möglichst alles andere gestoppt werden, um die reine AES Laufzeit zu bestimmen, ohne dass der Scheduler dazwischenfunkt.

So, mein Betreuer will das so unterbrechungsfrei wie möglich.

Ansätze waren:

-Das ganze in MSDOS zu schreiben, wo es noch kein Multitasking gibt -> gehts nicht da, da die neuen ASM Befehle anscheinend nicht untersützt werden.

-Alles ausser den AES Thread auf einem anderen Prozessorkern laufen lassen. -> wäre der Betreuer nicht so begeistert von

-Dem AES Thread eine sehr hohe Priorität geben -> sind ihm immernoch zu viele Unterbrechnungen.

So, jetzt bräuchte ich ein paar Ideen von euch. OS kann ich mir aussuchen, aber es muss halt ein C Compiler und Assembler der den neuen Befehlssatz versteht, dabei sein.

Danke schonmal

[flashpixx]

Dann sollen die beiden Versionen auf Geschwindigkeit geprüft werden, um so die Effizienz herauszufinden.

Effizienz != Laufzeit

Amdahlsches Gesetz

Gustafsons Gesetz

Speedup

Das schon mal ein völlig falscher Ansatz, denn Du vergisst z.B. das Prefetching des CPUs.

Das ganz soll so ablaufen dass ein C Programm geschrieben werden soll, das auf ein Signal auf einem I/O Port wartet, also USB Parallel oder Seriell, kann ich mir aussuchen. Das Signal sieht einfach so aus dass bei einem bestimmten Pin eine 1 angelegt wird.

Solange diese 1 anliegt. Soll AES laufen, und möglichst alles andere gestoppt werden, um die reine AES Laufzeit zu bestimmen, ohne dass der Scheduler dazwischenfunkt.

Das geht nicht, außerdem warum soll es von außen getriggert werden? Weiterhin wenn ich dann z.B. die Eingabe auf 0 lege, wird nicht automatisch die Messung gestoppt. Siehe Abtasttheorem und das Programm muss auch auf die Signaländerung reagieren, d.h. bei so etwas

   while true 

  { 

       check Pin

       for 

       {

       }

  }

Wäre die Messung falsch, denn die Überprüfung ob das Signal anliegt müsste innerhalb der for Schleife sein, um es zu dedektieren. Aber setzt man nun diese Überprüfung in die for Schleife wird die Messung ungenau, weil bei jeder Iteration die Überprüfung statt findet

-Das ganze in MSDOS zu schreiben, wo es noch kein Multitasking gibt -> gehts nicht da, da die neuen ASM Befehle anscheinend nicht untersützt werden.

-Alles ausser den AES Thread auf einem anderen Prozessorkern laufen lassen. -> wäre der Betreuer nicht so begeistert von

-Dem AES Thread eine sehr hohe Priorität geben -> sind ihm immernoch zu viele Unterbrechnungen.

Das was gemacht werden soll, ist fachlich Mist, denn weder der Aufbau dieser Messung der Laufzeit, noch der Einsatz von einem speziellen Befehlssatz führt zu einem aussagekräftigen Ergebnis. Ich empfehle zuerst einmal, dass Du Dir die grundlegende Theorie zur Leistungsbeurteilung von Computersystemen anschaust.

Z.B. wenn ich die Daten des Algorithmus so anlegen, dass der CPU sinnvoll Prefetching einsetzen kann und dann erhalte ich natürlich eine bessere Performance, als wenn der CPU kein Prefetching machen kann. Dies ist aber zum Teil abhängig von den Eingabedaten und deren Organisation.

Wenn es Dir darum geht die Laufzeit eines Algorithmus zu betrachten, dann mache einen ordentlichen Induktionsbeweis für die Laufzeit und berücksichtige den Unterschied der Befehlssätze. Dann musst Du das nicht mit irgendeiner komischen Methode das ganze messen.

Wenn Du dann dieses Ergebnis praktisch überprüfen willst, dann mache ein ordentliches Benchmarking nach den genannten Gesetzen und nimm z.B. nicht die Zeit, sondern die Anzahl der Instruktionen zur Messung, wie ich es schon beschrieben hatte. Denn die Zeit ist nicht hinreichend genau genug und kann von CPU Reihe zu CPU Reihe variieren.

Sorry, aber in diesem Ansatz sind einige richtig große fachliche Fehler drin

[BA_Byte]

Danke schonmal für die kritik, vor allem an flashpixx.

Okay, ich habe mich wohl etwas unklar ausgedrückt.

Also wenn das Signal kommt, soll der ASM Code gestartet werden und einmal durchlaufen. Er soll nicht so lange laufen, wie die 1 anliegt.

Gemessen werden soll die Zeit, wie lange der Algorithmus mit und ohne den neuen Befehlssatz läuft. Das ist meine Vorgabe. Beides auf dem selben Rechner. Parallelisert soll auch nichts werden.

Das soll genau der selbe Code sein, nur dass die Stellen, die den neuen Befehlen entsprechen mit Diesen ersetzt werden. Das Grundgerüst ( ob das jetzt effizient programmiert wurde oder nicht) ist egal da ja die differenz ermittelt werden soll.

Das ganze soll übrigens praktisch ermittelt werden.

Das heisst, es wäre möglich wenn ich die Anzahl der Takte, die der ASM Teil braucht, herausfinde und diese Werte als Geschwindigkeit nehme?

Wäre es auch möglich die Laufzeit zu berechnen wenn ich die Anz. der Takte so wie die Prozessorgeschwindigkeit habe? Wenn ich 1/Prozessortakt * Anzahl der verbrauchten Takte rechne, müsste ich doch die Laufzeit in einem 100%ig Echtzeitsystem ermittelt haben.

Die Anz. der Takte müsste sich ja sehr leicht mithilfe von Ollydbg oder Visualstudio auslesen lassen nehme ich an.

Zudem spielt das CPU Prefetching auch keine Rolle mehr wenn man nach der Taktzahl geht, richtig?

Gruß

[flashpixx]

Also wenn das Signal kommt, soll der ASM Code gestartet werden und einmal durchlaufen. Er soll nicht so lange laufen, wie die 1 anliegt.

Wofür soll der externe Trigger sein !? Das ist doch sinnfrei. Ich kann doch auch die Messung starten, wenn das Programm startet oder bevor eine Funktion ausgeführt wird.

Das soll genau der selbe Code sein, nur dass die Stellen, die den neuen Befehlen entsprechen mit Diesen ersetzt werden. Das Grundgerüst ( ob das jetzt effizient programmiert wurde oder nicht) ist egal da ja die differenz ermittelt werden soll.

Die Parallelisierung ist der Hinweis, dass hinter dem Benchmark entsprechende Gesetze liegen und diese sind hier sogar gleich, denn der CPU parallelisiert intern z.B. via Hyper-Threading

D.h. wenn Du dieses nicht beachtest, kannst Du Deine Messung nicht interpretieren

Das heisst, es wäre möglich wenn ich die Anzahl der Takte, die der ASM Teil braucht, herausfinde und diese Werte als Geschwindigkeit nehme?

Wäre es auch möglich die Laufzeit zu berechnen wenn ich die Anz. der Takte so wie die Prozessorgeschwindigkeit habe? Wenn ich 1/Prozessortakt * Anzahl der verbrauchten Takte rechne, müsste ich doch die Laufzeit in einem 100%ig Echtzeitsystem ermittelt haben.

nicht zwingend, wenn der CPU parallelisiert, also klassisch ein Reduced Instruction Set Computer ist, können pro Takt auch mehr Befehle ausgeführt werden, z.B. weil sie auf zwei Cores verteilt werden.

Die Anz. der Takte müsste sich ja sehr leicht mithilfe von Ollydbg oder Visualstudio auslesen lassen nehme ich an.

Was willst Du mit einem Debugger ( OllyDbg ) ?

Zudem spielt das CPU Prefetching auch keine Rolle mehr wenn man nach der Taktzahl geht, richtig?

Prefetching ist eine Heuristik und diese wird heute immer angewendet.

Sorry, aber Dir fehlen massiv fachliche Grundlagen.

[Pointerman]

Wie flashpixx und Guybrush schrieben ist eine Messung, so wie Du sie Dir vorstellst weder moeglich noch sinnvoll.

Wenn Du wirklich mit Assemblercode arbeiten und Takte zaehlen willst, wuerde ich an Deiner Stelle auf "echte Messungen" verzichten und mir die Dokumentation der verwendeten CPU anschauen. Dort kannst Du sehen welcher Befehl wieviele Takte benoetigt und auch sehen, ob die Befehle auf verschiedene Pipelines verteilt werden koennen. Dann brauchst Du Dir keine Sorgen um den Compiler und das Betriebssystem machen.

Der Wert der Ergebnisse waere mehr als Fraglich, aber vielleicht macht es Deinen Betreuer gluecklich...

[Bubble]

Eine ungewöhnliche Anforderung, theoretisch (unter Umständen mit gewissen Einschränkungen) machbar, es bedeutet allerdings (viel) Aufwand.

Wozu das Ganze? Eine reale Implementierung ist auch den üblichen Unterbrechungen unterworfen, diese völlig zu vermeiden wäre in gewisser Weise sogar unrealistisch.

[metux]

Für die Praxis ist das doch ohnehin nur für größere Datenmengen relevant. Also warum mißt Du das Ganze nicht auch mit hinreichend großen Datenmengen, sodaß sich die Rechenzeit im Rahmen von Minuten oder länger bewegt ?

[flashpixx]

Für die Praxis ist das doch ohnehin nur für größere Datenmengen relevant.

Das ist Grundvoraussetzung und zusätzlich sollten die Daten iid sein

[Wodar Hospur]

Mir wäre nicht bekannt, dass man das Multitaskingsystem deaktivieren kann, denn es ist im Code des OS kompiliert und somit unumgänglich.

Naja, mit wenigen Anpassungen auf jeden fall. Unter linux könntest du einen kernel Module schreiben, welches einfach alle Interrupt Handler ändert.

Du kannst ein Echtzeitbetriebssystem wie QNX verwenden, aber selbst dann ist Deine Annahme falsch, denn Du wirst nie 100% Aufmerksamkeit für Deinen Code haben können, das ist real nicht möglich ( Echtzeit ).

Echtzeit bedeutet, dass Dir für eine Instruktion eine maximale Zeitdauer der Bearbeitung nicht überschritten wird.

Bin gerade zu faul dies nachzuschlagen, aber afaik bedeutet Echtzeit nur das dein Programm in einem festvorgegebenen Zeitrahmen drangekommen sein muss. Wie lange es arbeitet unter welchen Umständen ist davon noch nicht berührt, es hat nur Auswirkungen auf den Scheduler.

Aber Echtzeit ist auch nicht was der TE haben will, es klingt eher nach dem Unterschied zwischen präemptiv und nicht präemptiv.

Zusätzlich hast Du in jedem OS Systemprozesse, die laufen müssen, damit die Infrastruktur des OS überhaupt funktioniert, z.B. wenn Deine Daten an die Hardware des Rechners ankommen, würde Dein Programm, wenn es in Echtzeit liefe, gar nicht mitbekommen, denn die Hardware löst bei eingehenden Signalen einen Interrupt aus, der vom OS dedektiert wird, das dann die Daten holt und an eine definierte Schnittstelle liefert. Dein Programm setzt erst auf OS Seite an, wenn es also 100% CPU Leistung hätte, dann würdest Du gar nicht wissen, dass Daten ankommen, denn die OS Zugriffe würden nicht statt finden.

Halb, wenn er das OS ersetzt, ersetzt er auch mit deren Interrupt Handler also wird selber informiert das es losgeht. Schwieriger wird es wenn er es nicht tut, denn dann würde afaik auch bei einem nicht-präemptiven OS ein Sprung ins OS erfolgen, aber solche Feinheiten kann man nachschlagen.

Generell gilt aber, dass meist handgeschriebener Assemblercode oft schlechter läuft als compilierter Code einer Hochsprache, denn die heutigen Compiler erzeugen so optimierten Code, dass dieser in den meisten Fällen besser ist als handgeschriebener. Es ist ein Trugschluss zu glauben, dass man damit eine bessere Performance erreichen kann. Wenn Dein Code "zu langsam" läuft, dann ist es oft ein Problem des Algorithmus und nicht des Systems.

Können optimierten Code erzeugen, aber gerade bei komplex mathematischen Algorithmen kann das Wissen um die genaue Architektur (Cacheline größe, vector und andere Operationen) da dem Compiler doch ein Schnippchen schlagen.

Ich würde auch behaupten das man Multitasking nicht abschalten kann, warum hat flashpixx ja schon sehr schön beschrieben.

Man kann die Priorität von Prozessen erhöhen, zumindest unter Windows bis zur Priorität Echtzeit.

MLFS war es glaub ich, gibt es auch als Implementierungen unter anderen Betriebssystemen. Aber unter Windows wird das austauschen des Interrupt Handler ein Problem.

Hallo,

danke schonmal für die Antworten.

Ich beschreibe mal die Aufgabenstellung genauer da das ganze doch ziemlich allg. formuliert war.

Im Rahmen einer Bachelorarbeit, soll AES in Assembler nachprogrammiert werden, einmal mit und einmal ohne den neuen AES-NI Befehlssatz( der beinhaltet ein paar neue Befehle die AES beschleunigen).

Dann sollen die beiden Versionen auf Geschwindigkeit geprüft werden, um so die Effizienz herauszufinden.

Das ganz soll so ablaufen dass ein C Programm geschrieben werden soll, das auf ein Signal auf einem I/O Port wartet, also USB Parallel oder Seriell, kann ich mir aussuchen. Das Signal sieht einfach so aus dass bei einem bestimmten Pin eine 1 angelegt wird.

Solange diese 1 anliegt. Soll AES laufen, und möglichst alles andere gestoppt werden, um die reine AES Laufzeit zu bestimmen, ohne dass der Scheduler dazwischenfunkt.

Dein Problem ist nicht nur der Scheduler, ich kann mir vorstellen für deine Aufgabe könnte es fast leichter sein einen minimalen Bootloader zu verwenden der dann dein Programm startet (wer braucht schon IO, Paging und sowas ).

So, mein Betreuer will das so unterbrechungsfrei wie möglich.

Ansätze waren:

-Das ganze in MSDOS zu schreiben, wo es noch kein Multitasking gibt -> gehts nicht da, da die neuen ASM Befehle anscheinend nicht untersützt werden.

Quatsch! Welche Bedeutung hat MS-DOS auf das Instruction Set. Du kannst nur ein anderes Problem bekommen, moderne CPUs (x86) müssen in einen speziellen Modus versetzt werden um ihre kompletten Fähigkeiten zu offenbaren.

-Alles ausser den AES Thread auf einem anderen Prozessorkern laufen lassen. -> wäre der Betreuer nicht so begeistert von

Ginge, Thread pinning, aber hier hast du das Problem mit dem Interrupt, ab wann läuft dein Programm wirklich?

-Dem AES Thread eine sehr hohe Priorität geben -> sind ihm immernoch zu viele Unterbrechnungen.

Joah, dein Programm wird von jedem Pups unterbrochen...

So, jetzt bräuchte ich ein paar Ideen von euch. OS kann ich mir aussuchen, aber es muss halt ein C Compiler und Assembler der den neuen Befehlssatz versteht, dabei sein.

Danke schonmal

Schreib dir selber was

Effizienz != Laufzeit

Amdahlsches Gesetz

Es geht um die Leistungsbewertung einer Instruktion, bzw. einer Realisierung einer Funktion mit dieser Instruktion, da trifft Amdahl wohl nicht wirklich oder?

Gustafsons Gesetz

Es geht allerdings nicht um eine Paralleliserung, vielleicht ist auch keine gewünscht.

Das schon mal ein völlig falscher Ansatz, denn Du vergisst z.B. das Prefetching des CPUs.

Auch die Branch Prediction, hat allerdings keine Auswirkungen, wenn beide Programme sonst gleich sind und sich nur in der Instruktion unterscheiden...

Das geht nicht, außerdem warum soll es von außen getriggert werden? Weiterhin wenn ich dann z.B. die Eingabe auf 0 lege, wird nicht automatisch die Messung gestoppt. Siehe Abtasttheorem und das Programm muss auch auf die Signaländerung reagieren, d.h. bei so etwas

   while true 

  { 

       check Pin

       for 

       {

       }

  }

Wäre die Messung falsch, denn die Überprüfung ob das Signal anliegt müsste innerhalb der for Schleife sein, um es zu dedektieren. Aber setzt man nun diese Überprüfung in die for Schleife wird die Messung ungenau, weil bei jeder Iteration die Überprüfung statt findet

Interrupts... davon gehört?

Das was gemacht werden soll, ist fachlich Mist, denn weder der Aufbau dieser Messung der Laufzeit, noch der Einsatz von einem speziellen Befehlssatz führt zu einem aussagekräftigen Ergebnis. Ich empfehle zuerst einmal, dass Du Dir die grundlegende Theorie zur Leistungsbeurteilung von Computersystemen anschaust.

Autsch. Mutig solche Aussagen zu treffen...

Z.B. wenn ich die Daten des Algorithmus so anlegen, dass der CPU sinnvoll Prefetching einsetzen kann und dann erhalte ich natürlich eine bessere Performance, als wenn der CPU kein Prefetching machen kann. Dies ist aber zum Teil abhängig von den Eingabedaten und deren Organisation.

Er hat den gleichen Code, einmal mit dieser super coolen Instruktion, einmal ohne... Da ändert sich nichts am Algorithmus, auch am Caching denk ich nicht....

Wenn es Dir darum geht die Laufzeit eines Algorithmus zu betrachten, dann mache einen ordentlichen Induktionsbeweis für die Laufzeit und berücksichtige den Unterschied der Befehlssätze.

Ich kenne die Instruktion nicht, aber wie genau willst du die theoretisch vergleichen, falls die Instruktionen, GENAU das gleiche machen? Die Transistoren auf dem Chip zählen . Ein Induktionsbeweis oder irgendeine Komplexitätsabschätzung ist nur bei veränderten Algorithmen möglich.

Dann musst Du das nicht mit irgendeiner komischen Methode das ganze messen.

Wenn Du dann dieses Ergebnis praktisch überprüfen willst, dann mache ein ordentliches Benchmarking nach den genannten Gesetzen und nimm z.B. nicht die Zeit, sondern die Anzahl der Instruktionen zur Messung, wie ich es schon beschrieben hatte. Denn die Zeit ist nicht hinreichend genau genug und kann von CPU Reihe zu CPU Reihe variieren.

Sorry, aber in diesem Ansatz sind einige richtig große fachliche Fehler drin

Glaub ich nicht...

Das heisst, es wäre möglich wenn ich die Anzahl der Takte, die der ASM Teil braucht, herausfinde und diese Werte als Geschwindigkeit nehme?

Wäre es auch möglich die Laufzeit zu berechnen wenn ich die Anz. der Takte so wie die Prozessorgeschwindigkeit habe? Wenn ich 1/Prozessortakt * Anzahl der verbrauchten Takte rechne, müsste ich doch die Laufzeit in einem 100%ig Echtzeitsystem ermittelt haben.

Die Anz. der Takte müsste sich ja sehr leicht mithilfe von Ollydbg oder Visualstudio auslesen lassen nehme ich an.

Ja die Anzahl der Takte ist schonmal eine gute Idee, du musst dir halt überlegen wie du das ermittelst, wer zählt die Takte, was machst du mit Stall Zyklen? Laufzeit wäre halt die Alternative, du nimmst halt einen anderen PIN der wird auf 1 gesetzt wenn das Programm fertig ist. Die Gegenseite muss halt genau genug messen, dann ziehst du davon die Übertragungsgeschwindigkeit * 2 ab und du hast ein ordentliches Ergebnis.

Wofür soll der externe Trigger sein !? Das ist doch sinnfrei. Ich kann doch auch die Messung starten, wenn das Programm startet oder bevor eine Funktion ausgeführt wird.

Nein, der externe Trigger könnte das Messgerät sein.

Die Parallelisierung ist der Hinweis, dass hinter dem Benchmark entsprechende Gesetze liegen und diese sind hier sogar gleich, denn der CPU parallelisiert intern z.B. via Hyper-Threading

D.h. wenn Du dieses nicht beachtest, kannst Du Deine Messung nicht interpretieren

Hyper-Threading musste afaik explizit eingeschaltet werden und hat nicht wirkliche Auswirkungen.

nicht zwingend, wenn der CPU parallelisiert, also klassisch ein Reduced Instruction Set Computer ist, können pro Takt auch mehr Befehle ausgeführt werden, z.B. weil sie auf zwei Cores verteilt werden.

So funktioniert das nicht...

Prefetching ist eine Heuristik und diese wird heute immer angewendet.

Sorry, aber Dir fehlen massiv fachliche Grundlagen.

Das ist egal, wenn er 2x den gleichen Code hat, bis auf eine Instruktion...

Wie flashpixx und Guybrush schrieben ist eine Messung, so wie Du sie Dir vorstellst weder moeglich noch sinnvoll.

Wenn Du wirklich mit Assemblercode arbeiten und Takte zaehlen willst, wuerde ich an Deiner Stelle auf "echte Messungen" verzichten und mir die Dokumentation der verwendeten CPU anschauen. Dort kannst Du sehen welcher Befehl wieviele Takte benoetigt und auch sehen, ob die Befehle auf verschiedene Pipelines verteilt werden koennen. Dann brauchst Du Dir keine Sorgen um den Compiler und das Betriebssystem machen.

Ich glaube da werden keine stall Zyklen eingerechnet.

Der Wert der Ergebnisse waere mehr als Fraglich, aber vielleicht macht es Deinen Betreuer gluecklich...

Es geht, imho kann man klar sagen, die Instruktion XYZ ist schneller als die Instruktion ABC. Schwieriger wird es wenn die Instruktionen nicht den gleichen Zweck haben (weiß ich nicht). Dann kann man aber sich an der Referenz Impl. von (wenn vorhanden) Intel halten und sagen die neue AES Funktion ist schneller als die alte Ref. Impl. von Intel.

Eine ungewöhnliche Anforderung, theoretisch (unter Umständen mit gewissen Einschränkungen) machbar, es bedeutet allerdings (viel) Aufwand.

Es geht, eine Aufgabe aus der Rechnerarchitektur mit starken Bezügen zu den Betriebssystemen.

Wozu das Ganze? Eine reale Implementierung ist auch den üblichen Unterbrechungen unterworfen, diese völlig zu vermeiden wäre in gewisser Weise sogar unrealistisch.

Naja, mit den Unterbrechungen müsstest du den Versuch sehr oft wiederholen um Schwankungen im Scheduling ausschließen zu können.

Das ist Grundvoraussetzung und zusätzlich sollten die Daten iid sein

Mich würde es wundern wenn die Daten irgendeine Bedeutung bei dieser Aufgabe hätten. Der Algorithmus ist immer der gleiche und ich würde sogar glauben die CPU wird immer gleich lange brauchen...

Effektiv, lade von einem Bootloader direkt dein Programm.

Setze in deinem Programm den Interrupt Handler und wenn möglich entferne jegliche Entropy.

Das Messgerät sollte konfiguriert sein (ähnliche Probleme wie hier):

Das Messgerät startet die Uhr und setzt den Pin.

Lass dein Progamm beim Interrupt anlaufen, sobald es fertig ist schickst du auf einem anderen Pin die antwort.

Als Interrupt auf dem Messgerät stoppst du die Uhr, ziehst Senden und Empfangen ab und hast ein Ergebnis.

Bearbeitet 15. August 2012 von Wodar Hospur

[flashpixx]

Können optimierten Code erzeugen, aber gerade bei komplex mathematischen Algorithmen kann das Wissen um die genaue Architektur (Cacheline größe, vector und andere Operationen) da dem Compiler doch ein Schnippchen schlagen.

Definiere "mathematische" Algorithmen? Wenn wir über QR, LU, Cholesky Zerlegung o.ä. reden, dann ja. Aber wenn ich simple arithmetische Operationen ausführe, dann sicherlich nicht.

Es geht um die Leistungsbewertung einer Instruktion, bzw. einer Realisierung einer Funktion mit dieser Instruktion, da trifft Amdahl wohl nicht wirklich oder?

Es geht allerdings nicht um eine Paralleliserung, vielleicht ist auch keine gewünscht.

Bitte einmal die Gesetze (Formeln) lesen und überlegen, was die einzelnen Komponenten des Gesetzes bedeuten. Die Gesetze von Amdahl, Gustafson und auch von Little sind Gesetze letztendlich um eine Leistungsbeurteilung zu machen. Die Kernaussage in den Gesetzen kann hier angewendet werden. Ich habe aber jetzt ehrlich keine Lust meine ganze Literatur über diesen Themenkomplex hier aufzuführen, denn wenn man eine Leistungsbeurteilung von einem Algorithmus macht, dann sollte man diese Gesetze präsent haben und verstanden haben

Auch die Branch Prediction, hat allerdings keine Auswirkungen, wenn beide Programme sonst gleich sind und sich nur in der Instruktion unterscheiden...

Das ist nicht ganz korrekt, denn wenn diese eine Instruktion bezüglich des Datenflusses eine andere Laufzeit hat, dann entscheidet letztendlich der Datenblock ob und wie es angewendet werden kann. Wenn z.B. ein Sprung nicht ausgeführt wird, weil durch den Datenfluss dieses eben nicht statt findet, dann können hier durchaus Unterschiede auftreten.

Interrupts... davon gehört?

Und wer verarbeitet den Interrupt, wenn man von dem theoretischen Fall ausgeht, dass kein Multitasking existiert. Der Interrupt kommt am System an und dann?

Er hat den gleichen Code, einmal mit dieser super coolen Instruktion, einmal ohne... Da ändert sich nichts am Algorithmus, auch am Caching denk ich nicht....

Nein das ist falsch, denn wie oben gesagt kann sich dadurch der Datenfluss ändern

Ich kenne die Instruktion nicht, aber wie genau willst du die theoretisch vergleichen, falls die Instruktionen, GENAU das gleiche machen? Die Transistoren auf dem Chip zählen . Ein Induktionsbeweis oder irgendeine Komplexitätsabschätzung ist nur bei veränderten Algorithmen möglich.

Du weisst wie eine Laufzeitabschätzung (worst-case Abschätzung) per Induktion durchgeführt wird? Mit dem Einsatz eines anderen Befehls verändert sich der Algorithmus, somit sollte sich auch die Abschätzung ändern, zwar nicht die Funktionsklasse aber der Skalar der Abschätzung. Dieses wird z.B. bei der Cholesky versus LU Zerlegung ausgenutzt.

Ja die Anzahl der Takte ist schonmal eine gute Idee, du musst dir halt überlegen wie du das ermittelst, wer zählt die Takte, was machst du mit Stall Zyklen? Laufzeit wäre halt die Alternative, du nimmst halt einen anderen PIN der wird auf 1 gesetzt wenn das Programm fertig ist. Die Gegenseite muss halt genau genug messen, dann ziehst du davon die Übertragungsgeschwindigkeit * 2 ab und du hast ein ordentliches Ergebnis.

Nein, der externe Trigger könnte das Messgerät sein.

Nein das ist falsch, rein formal hat er (Laufzeit + Delta_i)*2 als Reaktionszeit zwischen eingehendem Signal und Start des Programms. Und das Delta ist nicht bekannt. Wobei generell anzunehmen ist Delta_i != Delta_j

Es geht, imho kann man klar sagen, die Instruktion XYZ ist schneller als die Instruktion ABC. Schwieriger wird es wenn die Instruktionen nicht den gleichen Zweck haben (weiß ich nicht). Dann kann man aber sich an der Referenz Impl. von (wenn vorhanden) Intel halten und sagen die neue AES Funktion ist schneller als die alte Ref. Impl. von Intel.

http://de.wikipedia.org/wiki/AES_(Befehlssatzerweiterung)

Der Befehlssatz führt letztendlich mehrere Instruktionen auf Hardwareebene aus, somit könnte man salopp sagen es sind Funktionen speziell für AES.

Mich würde es wundern wenn die Daten irgendeine Bedeutung bei dieser Aufgabe hätten. Der Algorithmus ist immer der gleiche und ich würde sogar glauben die CPU wird immer gleich lange brauchen...

AES initialisiert ebenso wie andere Algorithmen mit einer Heuristik, d.h. hier können Unterschiede auftreten, sofern man das nicht deaktiviert.

Effektiv, lade von einem Bootloader direkt dein Programm.

Setze in deinem Programm den Interrupt Handler und wenn möglich entferne jegliche Entropy.

Das Messgerät sollte konfiguriert sein (ähnliche Probleme wie hier):

Das Messgerät startet die Uhr und setzt den Pin.

Lass dein Progamm beim Interrupt anlaufen, sobald es fertig ist schickst du auf einem anderen Pin die antwort.

Als Interrupt auf dem Messgerät stoppst du die Uhr, ziehst Senden und Empfangen ab und hast ein Ergebnis.

Wie oben geschrieben ist dieses nicht korrekt, es fehlt die Reaktionszeit des Systems nach anliegen der Binären 1. Des weiteren wäre die lediglich zu messen, dass Programm a langsamer läuft als b, aber daraus lässt sich nicht der generelle Schluss ableiten, dass der neue AES Befehlssatz generell effizienter ist als der alte, denn hier wurde ein einzelnes explizites System betrachtet. Man kann aus einem Einzelfall nicht auf eine allgemeine Aussage schließen. Das wäre ungefähr das gleiche als würde ich sagen, dass Pi eine transzendente Zahl ist und alle anderen Zahlen sind somit auch transzendent.

Letztendlich ist die Vorgehensweise hier fachlich nicht haltbar, da ein Einzelfall betrachtet wird (von der Art und Weise der Implementierung und ob diese fehlerfrei ist, sehe ich jetzt mal ab)

Bearbeitet 15. August 2012 von flashpixx

[Wodar Hospur]

Definiere "mathematische" Algorithmen? Wenn wir über QR, LU, Cholesky Zerlegung o.ä. reden, dann ja. Aber wenn ich simple arithmetische Operationen ausführe, dann sicherlich nicht.

Alleine ob du die Substitutionsbox im Cache behälst, berechnest oder teuer per Load zugreifst macht einen riesigen Unterschied. So könnte es abhängig von der Implementierung sinnvoll sein die reinen Daten im Cache zu halten und die S-Box zu berechnen, da du weniger Zeit verschwendest als bei einem richtigen Memory Access. Simple arithmetische Operationen sagen nichts darüber aus wie deine Daten wo liegen.

Bitte einmal die Gesetze (Formeln) lesen und überlegen, was die einzelnen Komponenten des Gesetzes bedeuten. Die Gesetze von Amdahl, Gustafson und auch von Little sind Gesetze letztendlich um eine Leistungsbeurteilung zu machen. Die Kernaussage in den Gesetzen kann hier angewendet werden. Ich habe aber jetzt ehrlich keine Lust meine ganze Literatur über diesen Themenkomplex hier aufzuführen, denn wenn man eine Leistungsbeurteilung von einem Algorithmus macht, dann sollte man diese Gesetze präsent haben und verstanden haben

Das ist der fundamentale Fehler, es ist kein Nagel, es ist keine Leistungsbewertung eines Algorithmus, es ist die Leistungsbewertung eines Prozessor(Features), welche man z.B. mit Benchmarks macht (RA uni-siegen Leistungsbewertung).

Du hast aber recht, ich hab mich nur aus meiner PV Vorlesung an Amdahls Gesetz erinnert (wo explizit nur auf die Parallelisierung mit dem Overhead eingegangen wurde). Aber ja es muss auch da berücksichtigt werden. Aber implizit tut er ja genau das wenn er die alte gegen durch die neue Ausführungszeit teilt.

Das ist nicht ganz korrekt, denn wenn diese eine Instruktion bezüglich des Datenflusses eine andere Laufzeit hat, dann entscheidet letztendlich der Datenblock ob und wie es angewendet werden kann. Wenn z.B. ein Sprung nicht ausgeführt wird, weil durch den Datenfluss dieses eben nicht statt findet, dann können hier durchaus Unterschiede auftreten.

Wenn diese Instruktion Einfluss auf den Programmablauf hat ist es eine Änderung des Algorithmus. Aber ja diese Unterschiede könnten, abhängig zur Instruktion, deren Implementierung auftreten.

Und wer verarbeitet den Interrupt, wenn man von dem theoretischen Fall ausgeht, dass kein Multitasking existiert. Der Interrupt kommt am System an und dann?

Der hinterlegte Interrupt Handler. BS 1 es ist klar geregelt wie jetzt der Ablauf erfolgt. Wenn die letzte Handlung des IH dann ist unseren Code anzuspringen?

Nein das ist falsch, denn wie oben gesagt kann sich dadurch der Datenfluss ändern

Wenn ich es mir richtig vorstelle sieht es irgendwie so aus:

ld .... # zeug in register laden

aes... # führt dann aus

vs

ld ... # daten in register laden

mul ..

shl .. # als eigentliche implementierung

xor ..

...

bne ....

Dann sehe ich kein Problem damit eine "Referenz"-Implementierung als Vergleich für diese Hardwarefunktion zu verwenden. Natürlich wird die CPU dann wohl irgendwelche Pipeline out-of-order Magie einsetzen um mehr Performance zu erreichen, dafür ist ja dann gerade der Befehl da. Er soll optimieren. Deswegen würde die ISA angefasst.

Du weisst wie eine Laufzeitabschätzung (worst-case Abschätzung) per Induktion durchgeführt wird? Mit dem Einsatz eines anderen Befehls verändert sich der Algorithmus, somit sollte sich auch die Abschätzung ändern, zwar nicht die Funktionsklasse aber der Skalar der Abschätzung. Dieses wird z.B. bei der Cholesky versus LU Zerlegung ausgenutzt.

Mir reichen Komplexitätsklassen in Landau-Notation. Skalare davor interessieren mich dabei nicht wirklich, muss aber auch zugeben das ich mich mit dem Thema nie vertiefend befasst habe. Aber da es hier nicht um eine Analyse sondern ein Benchmarking geht... nur aus Interesse wie legst du für die einzelnen Befehle denn Skalare und Werte fest, vor allem compiler/system/architektur/sprachen unabhängig?

Nein das ist falsch, rein formal hat er (Laufzeit + Delta_i)*2 als Reaktionszeit zwischen eingehendem Signal und Start des Programms. Und das Delta ist nicht bekannt. Wobei generell anzunehmen ist Delta_i != Delta_j

Okay, er hat cell(Laufzeit + Zeit von io <-> cpu) + Interrupt Handler Davon sind die Zeit von io <-> cpu schätzbar und der Interrupt Handler definierbar. Das Delta_j lässt sich ähnlich betrachten.

AES initialisiert ebenso wie andere Algorithmen mit einer Heuristik, d.h. hier können Unterschiede auftreten, sofern man das nicht deaktiviert.

Quelle bitte, habe danach gesucht, aber die Verbindung AES und Heuristik macht nur zum knacken Sinn.

Wie oben geschrieben ist dieses nicht korrekt, es fehlt die Reaktionszeit des Systems nach anliegen der Binären 1. Des weiteren wäre die lediglich zu messen, dass Programm a langsamer läuft als b, aber daraus lässt sich nicht der generelle Schluss ableiten, dass der neue AES Befehlssatz generell effizienter ist als der alte, denn hier wurde ein einzelnes explizites System betrachtet. Man kann aus einem Einzelfall nicht auf eine allgemeine Aussage schließen. Das wäre ungefähr das gleiche als würde ich sagen, dass Pi eine transzendente Zahl ist und alle anderen Zahlen sind somit auch transzendent.

Letztendlich ist die Vorgehensweise hier fachlich nicht haltbar, da ein Einzelfall betrachtet wird (von der Art und Weise der Implementierung und ob diese fehlerfrei ist, sehe ich jetzt mal ab)

Wir können uns darauf einigen das die zu verschlüsselnden Daten keinen Einfluss auf die Dauer der Verschlüsselung haben? "Hans" zu verschlüsseln dauert genauso lang wie "Karl".

Gut, wenn er dann zeigen kann das die Verwendung von AES-NI im Vergleich zu der üblichen Implementierung (am besten Ref) einen Speedup von X erreicht...

Dann hat er damit natürlich nicht gezeigt das es nicht eine noch schneller Lösung in Software gibt.

Aber es geht wohl auch nicht darum ein lokales oder globales Optimum zu finden, sondern nur die beiden Implementierungen zu benchmarken. In Abhängigkeit zu X kann dann auch der Messaufwand als zu vernachlässigen beschrieben werden.

Die Interpretation der Daten hast du übrigens vorgenommen. Natürlich darf er nicht allgemein darauf auf Gott und die Welt schließen. Aber hier und heute, auf der Architektur ist die Implementierung mit AES-NI Faktor X schneller. (Kernel-Benchmarking nannte der Dozent es...). Natürlich kann das Verhalten innerhalb eines größeren Kontextes sich noch weiter verschieben. Als Bachelorarbeit vielleicht etwas "einfach", das hängt von den Rahmenbedingungen ab. Aber fachlich unhaltbar, der Untergang vom Abendland oder so halt ich für übertrieben.

Bearbeitet 15. August 2012 von Wodar Hospur

[flashpixx]

Simple arithmetische Operationen sagen nichts darüber aus wie deine Daten wo liegen.

Natürlich, da müsste ich mich jetzt bezüglich AES einlesen, wie, was, wo und wie viele Daten er während der Ausführung hat. Denn je nachdem ob ich als Bsp zwei Vektoren per Schleife zu einem Skalar umrechne oder das via Pipelining oder vielleicht sogar in einer Operation machen kann, wäre ja dann durchaus extrem für die Messung.

Das ist der fundamentale Fehler, es ist kein Nagel, es ist keine Leistungsbewertung eines Algorithmus, es ist die Leistungsbewertung eines Prozessor(Features), welche man z.B. mit Benchmarks macht (RA uni-siegen Leistungsbewertung).

Das sehe ich nicht so, denn im ersten Posting stand:

Meine Aufgabe ist es die Laufzeit eines Codes zu analysieren, um diese korrekt zu bestimmen, muss jedoch kurzzeitig das Multitasking des Betriebssystems abgeschaltet werden.

Laufzeit ist unabhängig vom konkreten System.

Du hast aber recht, ich hab mich nur aus meiner PV Vorlesung an Amdahls Gesetz erinnert (wo explizit nur auf die Parallelisierung mit dem Overhead eingegangen wurde). Aber ja es muss auch da berücksichtigt werden. Aber implizit tut er ja genau das wenn er die alte gegen durch die neue Ausführungszeit teilt.

Ich habe dazu gerade ein Paper von Intel (vom letzten Jahr), da wurde Amdahl bezüglich der Performance bei Hyperthreading benutzt. Da wäre ich vorsichtig, denn so wie ich jetzt beim Überfliegen der AES Befehlssätze gesehen habe, sind dieses ja "Funktionen" evtl müsste man dabei berücksichtigen, dass sie intern doch hardwareseitig parallelisieren. Gerade bei Summen- / Multiplikationsketten wird das definitiv gemacht.

Wenn ich es mir richtig vorstelle sieht es irgendwie so aus:

ld .... # zeug in register laden

aes... # führt dann aus

vs

ld ... # daten in register laden

mul ..

shl .. # als eigentliche implementierung

xor ..

...

bne ....

Dann sehe ich kein Problem damit eine "Referenz"-Implementierung als Vergleich für diese Hardwarefunktion zu verwenden. Natürlich wird die CPU dann wohl irgendwelche Pipeline out-of-order Magie einsetzen um mehr Performance zu erreichen, dafür ist ja dann gerade der Befehl da. Er soll optimieren. Deswegen würde die ISA angefasst.

So würde ich das auch sehen, natürlich könnte man hier auch argumentieren, dass man diesen Unterschied beim Pipelining evtl als "vernachlässigbar klein" setzt, aber ohne da konkrete Infos zu haben, würde ich davon nicht ausgehen.

Mir reichen Komplexitätsklassen in Landau-Notation. Skalare davor interessieren mich dabei nicht wirklich, muss aber auch zugeben das ich mich mit dem Thema nie vertiefend befasst habe. Aber da es hier nicht um eine Analyse sondern ein Benchmarking geht... nur aus Interesse wie legst du für die einzelnen Befehle denn Skalare und Werte fest, vor allem compiler/system/architektur/sprachen unabhängig?

Gibt es, gibt es bei den CPU Herstellern Tabellen zu, wenn man es sehr genau machen will (gerade im Embedded Bereich). Ansonsten schätze ich ab, a+b wäre O(1), wobei dann eben sum(a_i) = n*O(1) wäre. Das mit den Skalaren ist aber wirklich zu beachten, ganz klassisch beim Lösen eines LGS: Gauß-Algorithmus ist O(n^3), man bekommt zwar nicht aus dem n^3 raus, aber mit numerischen Verfahren kann man bis zu O(1/6 * n^3) kommen, was ja durchaus schon bemerkbar ist.

Ich denke in Bezug auf den Thread wird genau das der Punkt sein, d.h. AES an sich wird von der Laufzeit fix sein, d.h. der Faktor wird sich durch den Befehlssatz verändern.

Quelle bitte, habe danach gesucht, aber die Verbindung AES und Heuristik macht nur zum knacken Sinn.

AES benutzt einen symmetrischen Key, der letztendlich auf einem Pseudozufallsgenerator basiert

Symmetric-key algorithm - Wikipedia, the free encyclopedia

Sollte aber generell aus der Messung heraus genommen werden, gerade Verfahren wie z.B. Mersenne-Twister sind durchaus rechenintensiv.

Wir können uns darauf einigen das die zu verschlüsselnden Daten keinen Einfluss auf die Dauer der Verschlüsselung haben? "Hans" zu verschlüsseln dauert genauso lang wie "Karl".

Ja

Dann hat er damit natürlich nicht gezeigt das es nicht eine noch schneller Lösung in Software gibt.

Das ist klar. Die Frage ist nur, wenn man jetzt AES selbst in den genannten Varianten implementiert, dann wäre ja direkt die Frage sind diese beiden Codes nachher überhaupt gleich !? Denn nur weil sie das gleiche liefern, müssen sie nicht gleich sein (Stichwort Halteproblem)

Außerdem halte ich AES zu implementieren für nicht trivial, so dass hier sicherlich ein "großer Ungenauigkeitsfaktor" hinzu kommt.

Aber es geht wohl auch nicht darum ein lokales oder globales Optimum zu finden, sondern nur die beiden Implementierungen zu benchmarken.

Er benchmarket/d "seine" Implementierung auf "einem" System. Worst-case Szenario die AES Implementierung ohne neuen Befehlssatz läuft schneller als mit dem neuen Satz (weil evtl Übergaben / Rückgaben ändern muss). Ich denke nämlich nicht, dass es einfach mit dem Austausch von einzelnen Befehlen getan ist.

Die Interpretation der Daten hast du übrigens vorgenommen. Natürlich darf er nicht allgemein darauf auf Gott und die Welt schließen. Aber hier und heute, auf der Architektur ist die Implementierung mit AES-NI Faktor X schneller. (Kernel-Benchmarking nannte der Dozent es...). Natürlich kann das Verhalten innerhalb eines größeren Kontextes sich noch weiter verschieben. Als Bachelorarbeit vielleicht etwas "einfach", das hängt von den Rahmenbedingungen ab. Aber fachlich unhaltbar, der Untergang vom Abendland oder so halt ich für übertrieben.

Gerade den letzten Punkt sehe ich da durchaus, denn es ist a) nicht sichergestellt wie der Code aufgebaut ist (gerade einem Programmieranfänger unterlaufen da oft sehr viele Probleme, d.h. die Implementierung ist nicht repräsentativ) und welchen fachlichen Schluss kann ich aus den gemessen Daten ziehen!? Die Aussage "es läuft mit dem neuen Befehlssatz schneller" kann man so nicht ziehen, denn neben dem Befehlssatz muss sicher gestellt sein, dass die Codes "hinreichend identisch" sind.

DIe zentralen Fragen, die ich stellen würde, wären:

- Wie repräsentativ ist der Code z.B. zu gängigen Implementierungen

- Wie kann sichergestellt werden, dass die Codes gleich sind

- Wie kann sichergestellt werden, dass die gemessenen Daten korrekt sind

Natürlich kann man abschließend Messdaten bereinigen, aber dann ist die Frage "wie" man das macht. Wenn die Bsc Arbeit heisst "schreibe einmal AES mit und einmal ohne neuen Befehlssatz", dann ist das kein Problem. Wenn es hier aber um einen Benchmark geht und daraus ein Ergebnis abzuleiten, da sehe ich doch wirklich große Probleme (wobei ich nicht zwingend etwas allgm. gültiges erwarten würde).

[Bubble]

Es geht, eine Aufgabe aus der Rechnerarchitektur mit starken Bezügen zu den Betriebssystemen.

Wie ich schon sagte geht es, unter Umständen mit gewissen Einschränkungen, die von der Leidensfähigkeit des Umsetzenden und gegebenfalls hardwareabhängig sind.

Letztlich muss er aber nicht zwingend ein eigenes OS schreiben, es kommen existierende Betriebssysteme (bzw. -versionen) in Betracht, wenn es zunächst nur darum geht Unterbrechungen durch den Task-Scheduler zu verhindern.

Naja, mit den Unterbrechungen müsstest du den Versuch sehr oft wiederholen um Schwankungen im Scheduling ausschließen zu können.

Na und? Wenn man jedes Detail betrachten will, kämen noch andere Ursachen für (minimalste) Laufzeitschwankungen in Betracht, von der Schwierigkeit eine kurze Zeitspanne exakt zu messen einmal abgesehen.

[Wodar Hospur]

Natürlich, da müsste ich mich jetzt bezüglich AES einlesen, wie, was, wo und wie viele Daten er während der Ausführung hat. Denn je nachdem ob ich als Bsp zwei Vektoren per Schleife zu einem Skalar umrechne oder das via Pipelining oder vielleicht sogar in einer Operation machen kann, wäre ja dann durchaus extrem für die Messung.

Genau mein Punkt, der Compiler optimiert für den allgemeinen Fall, nicht für den speziellen. Daher kann in so einem Fall, Hand erzeugter Assembler sehr wohl schneller sein.

Das sehe ich nicht so, denn im ersten Posting stand:

Laufzeit ist unabhängig vom konkreten System.

Kommt auf deine Betrachtung an, willst du die Laufzeit in Zyklen wissen oder interessiert dich eine Laufzeitklasse, bzw. Güte. Nach seinen Antworten hier zu schließen geht es wohl weniger um die Klasse und Güte als um wirkliches Benchmarking.

Ich habe dazu gerade ein Paper von Intel (vom letzten Jahr), da wurde Amdahl bezüglich der Performance bei Hyperthreading benutzt. Da wäre ich vorsichtig, denn so wie ich jetzt beim Überfliegen der AES Befehlssätze gesehen habe, sind dieses ja "Funktionen" evtl müsste man dabei berücksichtigen, dass sie intern doch hardwareseitig parallelisieren. Gerade bei Summen- / Multiplikationsketten wird das definitiv gemacht.

Puh, schwer zu beurteilen, immerhin ist ja HT doch mehr was da aufgesetzt wird, wahrscheinlich mit verschiedenen PSW und so... aber naja, das kann und muss in so einer Arbeit natürlich versucht werden zu beleuchten.

So würde ich das auch sehen, natürlich könnte man hier auch argumentieren, dass man diesen Unterschied beim Pipelining evtl als "vernachlässigbar klein" setzt, aber ohne da konkrete Infos zu haben, würde ich davon nicht ausgehen.

Das meinte ich nicht, denn ich glaube gerade bei AES kann durch forwarding und das vermeiden von Stall Zyklen besondere Effekte aufs Pipelining passieren, die wirklich Performanz bringen. Aber das ist ja gewollt.

Gibt es, gibt es bei den CPU Herstellern Tabellen zu, wenn man es sehr genau machen will (gerade im Embedded Bereich). Ansonsten schätze ich ab, a+b wäre O(1), wobei dann eben sum(a_i) = n*O(1) wäre. Das mit den Skalaren ist aber wirklich zu beachten, ganz klassisch beim Lösen eines LGS: Gauß-Algorithmus ist O(n^3), man bekommt zwar nicht aus dem n^3 raus, aber mit numerischen Verfahren kann man bis zu O(1/6 * n^3) kommen, was ja durchaus schon bemerkbar ist.

Kommt auf deine n an, würde ich behaupten, Ob etwas 160 Jahre oder 10 Jahre läuft, beides ist nicht i.O. Wobei ich dachte für Gauß gäbe es was besseres, aber Numerik war nicht mein stärkstes Fach.

Ich denke in Bezug auf den Thread wird genau das der Punkt sein, d.h. AES an sich wird von der Laufzeit fix sein, d.h. der Faktor wird sich durch den Befehlssatz verändern.

Was ja für Kernel Benchmarking GENAU das ist was du willst.

AES benutzt einen symmetrischen Key, der letztendlich auf einem Pseudozufallsgenerator basiert

Symmetric-key algorithm - Wikipedia, the free encyclopedia

Sollte aber generell aus der Messung heraus genommen werden, gerade Verfahren wie z.B. Mersenne-Twister sind durchaus rechenintensiv.

Und haben mit der eigentlich Aufgabe der Funktionen, ver- und entschlüsseln nichts zu tun .

Das ist klar. Die Frage ist nur, wenn man jetzt AES selbst in den genannten Varianten implementiert, dann wäre ja direkt die Frage sind diese beiden Codes nachher überhaupt gleich !? Denn nur weil sie das gleiche liefern, müssen sie nicht gleich sein (Stichwort Halteproblem)

Außerdem halte ich AES zu implementieren für nicht trivial, so dass hier sicherlich ein "großer Ungenauigkeitsfaktor" hinzu kommt.

Ausreichend viele Tests sollten das verifizieren können, gerne mit Äquivalenzklassen. Meiner Meinung liegt in dieser Arbeit eine Ingenieurleistung vor. Weniger der Versuch eine bestimmte theoretische Eigenheit zu beweisen..

Die Implementierung von AES ist glaub ich recht trivial (es gab einen Artikel auf heise wie du es embedded machen kannst). Die kryptographischen Bedeutungen da mal rausgelassen.

Er benchmarket/d "seine" Implementierung auf "einem" System. Worst-case Szenario die AES Implementierung ohne neuen Befehlssatz läuft schneller als mit dem neuen Satz (weil evtl Übergaben / Rückgaben ändern muss). Ich denke nämlich nicht, dass es einfach mit dem Austausch von einzelnen Befehlen getan ist.

Naja, wenn er alle Faktoren rausnimmt die das "eine" System besonders machen. Es geht darum die Funktion einer CPU zu benchmarken.

Wenn die Implementierung wirklich langsamer sein sollte ist es nur ein Zeichen, dass er nicht in der Lage war die Dokumentation richtig zu lesen.

Gerade den letzten Punkt sehe ich da durchaus, denn es ist a) nicht sichergestellt wie der Code aufgebaut ist (gerade einem Programmieranfänger unterlaufen da oft sehr viele Probleme, d.h. die Implementierung ist nicht repräsentativ) und welchen fachlichen Schluss kann ich aus den gemessen Daten ziehen!? Die Aussage "es läuft mit dem neuen Befehlssatz schneller" kann man so nicht ziehen, denn neben dem Befehlssatz muss sicher gestellt sein, dass die Codes "hinreichend identisch" sind.

Er ist kein Anfänger, er ist beim Abschließen seines Studiums und wird sich nicht ohne Grund diese Bachelorarbeit gesucht haben.

Aus den Daten kannst du sagen: die Referenzimplementierung von AES ist gegenüber einer Implementierung mit den neuen Funktionen von Intel Faktor x langsamer. Dies gilt für den isolierten Versuch und sollte vielleicht unter moderater Last eines Betriebssystems wiederholt werden. Um einen Alltagswert zu erreichen, mehr siehe unten.

DIe zentralen Fragen, die ich stellen würde, wären:

- Wie repräsentativ ist der Code z.B. zu gängigen Implementierungen

- Wie kann sichergestellt werden, dass die Codes gleich sind

- Wie kann sichergestellt werden, dass die gemessenen Daten korrekt sind

- Deswegen soll er es ja nicht komplett selbst entwickeln (AES gibt es bestimmt mit ner Referenz)

- Tests, Daten überprüfen (Software-engineering)

- Darstellen des Versuchaufbaus mit genauer Beschreibung der Messungen. So können dann andere den Versuch nachstellen oder fundamentale Fehler in der Berechnung finden.

Natürlich kann man abschließend Messdaten bereinigen, aber dann ist die Frage "wie" man das macht. Wenn die Bsc Arbeit heisst "schreibe einmal AES mit und einmal ohne neuen Befehlssatz", dann ist das kein Problem. Wenn es hier aber um einen Benchmark geht und daraus ein Ergebnis abzuleiten, da sehe ich doch wirklich große Probleme (wobei ich nicht zwingend etwas allgm. gültiges erwarten würde).

Ich nicht, du suchst einen Korrektheitsbeweis den es bei sowas imho nicht geben kann. Bzw der bei der Betrachtung aller Faktoren den Rahmen sprengt.

Wie ich schon sagte geht es, unter Umständen mit gewissen Einschränkungen, die von der Leidensfähigkeit des Umsetzenden und gegebenfalls hardwareabhängig sind.

Natürlich hardwareabhängig, er testet/benchmarkt eine Funktion der CPU. Ich glaube so aufwendig wird diese Arbeit nicht, eine durchschnittliche Bachelorarbeit ist mit 360 Std. angesetzt.

Was mich daran erinnert, ich sollte noch was tun .

Letztlich muss er aber nicht zwingend ein eigenes OS schreiben, es kommen existierende Betriebssysteme (bzw. -versionen) in Betracht, wenn es zunächst nur darum geht Unterbrechungen durch den Task-Scheduler zu verhindern.

Er braucht kein Paging und keine komplexe IO und Schedulen will er gar nicht. Bei einem bestehenden OS muss er alle Interrupt Handler austauschen um sicher gehen zu können, das nichts seine Messung kaputt macht.

Na und? Wenn man jedes Detail betrachten will, kämen noch andere Ursachen für (minimalste) Laufzeitschwankungen in Betracht, von der Schwierigkeit eine kurze Zeitspanne exakt zu messen einmal abgesehen.

Das muss er natürlich in seinem Testsetup berücksichtigen, z.b. in dem er genügend Runden AES macht. Natürlich soll er jedes Detail betrachten, auch z.B. den Initalaufwand der bei beiden Implementierungen vorhanden ist, (Daten vom Speicher in die Caches bewegen z.B.). Das kann aber durch viele Verzögerungen sich verändern. Außerdem könnten die Verzörgerungen dafür sorgen dass ein komplett anderes Ergebnis rauskommt:

- AES-NI Funktion lässt sich nicht unterbrechen sondern rechnet die Runde immer fertig

- Die Variante ohne wird mittendrin unterbrochen vom Scheduler/IO/ der Uhr... was auch immer

Wenn jetzt die Unterbrechung dafür sorgt das Daten aus den Caches vertrieben werden, könnte die Variante ohne der Zusatzfunktion um mehrere Größenordnungen schlechter sein, obwohl, rein technisch gesehen der Performancevorteil nur minimal wäre.

Bearbeitet 16. August 2012 von Wodar Hospur

[flashpixx]

Genau mein Punkt, der Compiler optimiert für den allgemeinen Fall, nicht für den speziellen. Daher kann in so einem Fall, Hand erzeugter Assembler sehr wohl schneller sein.

Du implizierst, dass Programmierer das entsprechend umsetzt.

Kommt auf deine Betrachtung an, willst du die Laufzeit in Zyklen wissen oder interessiert dich eine Laufzeitklasse, bzw. Güte.

Du hast beim Benchmarking eine Güte, nämlich ist der eine Algo schneller als der andere, das ist ein Gütemaß, denn es impliziert Ti < Tj (Stichwort Cauchy-Schwarzschen Ungleichung bzw Dreiecksungleichung)

Kommt auf deine n an, würde ich behaupten, Ob etwas 160 Jahre oder 10 Jahre läuft, beides ist nicht i.O. Wobei ich dachte für Gauß gäbe es was besseres, aber Numerik war nicht mein stärkstes Fach.

Gaußsches Eliminationsverfahren

Mein Fehler, Gauß ist O(n^3) und LU O(2/3 * n^3). Also nach Deiner Meinung ist das irrelevant !? In diesem Fall würde ich Dich bitten einmal zu überlegen, wenn Du eine DGL mit Hilfe von FEM löst, wie groß die Gleichungssysteme werden können z.B. bei einer Navier-Stokes-Gleichungen.

Der Faktor spielt real eine erhebliche Rolle und genau dieser soll ja hier bei AES durch eine Messung ermittelt werden

Was ja für Kernel Benchmarking GENAU das ist was du willst.

In diesem Fall interessiert der oben genannte Faktor und die daraus resultierende Güte

Meiner Meinung liegt in dieser Arbeit eine Ingenieurleistung vor. Weniger der Versuch eine bestimmte theoretische Eigenheit zu beweisen..

Der theoretische Teil wäre die entsprechende Äquivalenzklasse, die Praxis der konstante Faktor, denn aufgrund dessen kann man dann den Schluss auf die Güte für diesen Testfall ziehen.

Es geht darum die Funktion einer CPU zu benchmarken.

Nein geht es nicht! Es geht darum zu überprüfen ob die AES Befehlssätze einen Performanceboost bringen und wenn ja welchen. Wenn man "nur" einen CPU benchmarken will, dann nehme ich die Dokumentation des Herstellers, denn der macht so etwas.

Er ist kein Anfänger, er ist beim Abschließen seines Studiums und wird sich nicht ohne Grund diese Bachelorarbeit gesucht haben.

Bsc sind 6 Semester, evtl mit 1-2 Veranstaltungen zum Programmieren, aufgrund von vielleicht 2 Veranstaltungen zu sagen "man kann programmieren", ist wohl doch etwas gewagt.

Ich nicht, du suchst einen Korrektheitsbeweis den es bei sowas imho nicht geben kann. Bzw der bei der Betrachtung aller Faktoren den Rahmen sprengt.

Man braucht ein Maß, um beurteilen zu können, ansonsten ist das Ergebnis nicht interpretierbar, denn ich kann nicht sagen, nur weil z.B. Implementierung a 4sek braucht und die andere 8sek, dass die eine Implementierung halb so schnell ist wie die andere. Hier wird ein realer Testfall konstruiert und da sollte man dann doch für die Messung die DIN 1319 beachten und vor allem das Normal

Nur weil ich zwei Codes habe, wobei der eine in praktischen Test schneller läuft als der andere, kann ich keine entsprechenden Aussagen ziehen. Die Komplexitätsklasse von AES ist bekannt, d.h. ich kann durch eine entsprechende Messung den konstanten Faktor ermitteln. Natürlich sollte man zuvor eine Abschätzung machen, in welcher Größenordnung dieser Faktor liegt. Wenn ich die AES Implementierung ohne neuen Befehlssatz als 1 ansetze, dann sollte ja die mit dem Befehlssatz < 1 sein.

Zweitens muss ich aber auch betrachten wie stark sich die Quellcodes unterscheiden z.B.

for i in 1 to 10

     x += a(i)

unterscheidet sich deutlich von

   x = a(1)

   x = x+a(2)

   ...

   x = x+a(10)

Wenn ich also zwei Quellcodes benchmarken will, dann muss ich auch in irgendeiner Weise festlegen, wie unterschiedlich diese Codes sind ( Softwaremetrik ).

[Wodar Hospur]

Du implizierst, dass Programmierer das entsprechend umsetzt.

Warum sollten sie es sonst mit Assembler umsetzen? Ist irgendwie ein Henne-Ei Problem oder? Aber deine Kernaussage war, es wäre Unsinn das mit Assembler zu schreiben.

Du hast beim Benchmarking eine Güte, nämlich ist der eine Algo schneller als der andere, das ist ein Gütemaß, denn es impliziert Ti < Tj (Stichwort Cauchy-Schwarzschen Ungleichung bzw Dreiecksungleichung)

Du hast sogar ne Metrik dadrauf, worum es mir geht ist das er keine Komplexität/Laufzeitklassen Analyse macht!

Gaußsches Eliminationsverfahren

Mein Fehler, Gauß ist O(n^3) und LU O(2/3 * n^3). Also nach Deiner Meinung ist das irrelevant !? In diesem Fall würde ich Dich bitten einmal zu überlegen, wenn Du eine DGL mit Hilfe von FEM löst, wie groß die Gleichungssysteme werden können z.B. bei einer Navier-Stokes-Gleichungen.

Der Faktor spielt real eine erhebliche Rolle und genau dieser soll ja hier bei AES durch eine Messung ermittelt werden

Naja, es gibt doch hier die Möglichkeit per Konditionierung ein Gleichungssystem vorzubereiten und afaik konntest du doch auch auf LGS das Newton-verfahren anwenden und was weiß ich nicht alles . Ich würde ja im Stummel-Hummel Buch reinschauen, aber neee..

Ja, also bei n=100 000

heißt n^3 = 100000 * 100000 * 100000 und ob es jetzt 100000 * 100000 * 10000 heißt macht einen Unterschied. Aber n^2 wäre wohl besser .

In diesem Fall interessiert der oben genannte Faktor und die daraus resultierende Güte

Natürlich interessiert mich die Geschwindkeitsveränderung. Aber nicht vom Modell sondern von der Realisierung.

Der theoretische Teil wäre die entsprechende Äquivalenzklasse, die Praxis der konstante Faktor, denn aufgrund dessen kann man dann den Schluss auf die Güte für diesen Testfall ziehen.

Okay, schon eher, wobei ich nicht davon ausgehe das die Klasse sich durch die Instruktion ändern wird.

Nein geht es nicht! Es geht darum zu überprüfen ob die AES Befehlssätze einen Performanceboost bringen und wenn ja welchen. Wenn man "nur" einen CPU benchmarken will, dann nehme ich die Dokumentation des Herstellers, denn der macht so etwas.

Genau du benchmarkst die AES Instruktionen. Vorsicht, liegt zwischen Kernelbenchmark und synthetischen Benchmark. Funktion -> Instruktionssatz...

Bsc sind 6 Semester, evtl mit 1-2 Veranstaltungen zum Programmieren, aufgrund von vielleicht 2 Veranstaltungen zu sagen "man kann programmieren", ist wohl doch etwas gewagt.

Abhängig der Hochschule. Aber ich erwarte das jemand in seiner Bachelorarbeit eine Referenzimplementierung runterarbeiten kann. Um ehrlich zu sein, ein guter FIAE sollte das können.

Man braucht ein Maß, um beurteilen zu können, ansonsten ist das Ergebnis nicht interpretierbar, denn ich kann nicht sagen, nur weil z.B. Implementierung a 4sek braucht und die andere 8sek, dass die eine Implementierung halb so schnell ist wie die andere. Hier wird ein realer Testfall konstruiert und da sollte man dann doch für die Messung die DIN 1319 beachten und vor allem das Normal

Deswegen wäre der Benchmark wahrscheinlich auch synthetisch, denk ich. Naja, du kannst R nehmen und einfach den Abstand. Metrik und so . Du kannst auch R^2 nehmen und den Euklid, weil du Zeit und Speicher nimmst, ... du könntest auch R^3 nehmen und den Energieverbrauch und Manhatten. Was er da macht ist spezifisch und für uns unwichtig.

Zweitens muss ich aber auch betrachten wie stark sich die Quellcodes unterscheiden z.B.

for i in 1 to 10

     x += a(i)

unterscheidet sich deutlich von

   x = a(1)

   x = x+a(2)

   ...

   x = x+a(10)

Wenn ich also zwei Quellcodes benchmarken will, dann muss ich auch in irgendeiner Weise festlegen, wie unterschiedlich diese Codes sind ( Softwaremetrik ).

.. Ja kannst du, wenn es dir um eine Leistungsbewertung geht musst du es aber auch nicht machen. Es ist immer schön das gesamte Bild im Auge zu haben, aber wenn er nur zeigen soll X schneller als Y braucht er auch keine Softwaremetrik.

Übrigens ich glaube wir sind weit vom eigentlichen Thema abgekommen . Wenn du willst führen wir das fort, aber dem TE hilft es nicht wirklich.