Effiziente Programme Aufgabe 2020w

Sie können sich eine beliebige Aufgabe suchen. Wenn Sie das nicht wollen, ist die vorgegebene Aufgabe dieses Jahr, einen Teil eines Codegenerators für einen JIT-Compiler zu optimieren.

Dateien und Aufrufe

Sie finden alle nötigen Dateien verpackt in effizienz-aufgabe20.tar.xz, und können das auf der g0 einfach mit 
tar xfJ /nfs/unsafe/httpd/ftp/pub/anton/lvas/effizienz-aufgabe20/effizienz-aufgabe20.tar.xz
auspacken. Mit make test (bzw. einfach make) können Sie das Programm gforth9 und die Test-Eingabe brew-sequences.bin erzeugen.

Das Programm gforth9 wird wie folgt aufgerufen: 

    gforth9 infile rulesfile costsfile [0-8]
Wobei infile die Eingabe in einem Binärformat ist, und rulesfile und costsfiles die Ausgaben, ebenfalls in einem Binärformat. [0-8] ist noch ein weiterer Parameter, den wir dazu verwenden, um beim Testen ein bisschen mehr Breite zu bekommen (weil wir nur eine Eingabedatei verwenden).

Weiters lässt make test das Programm mit verschiedenen Parametern laufen, und prüft, ob das Ergebnis bezüglich der optimalen Kosten mit dem gegebenen Programm übereinstimmt. Da es oft mehrere optimale (und damit gültige) Lösungen gibt, bei denen sich dann die rulesfile-Ausgabe unterscheidet, wird das rulesfile nicht mit der Ausgabe des Ursprungsprogramms verglichen.

Mit 

    make perf
erhalten Sie Performance-Resultate für den Vergleich mit der vorgegebenen Lösung. Die vorgegebene Lösung braucht 125M cycles:u auf der g0. Bitte beziehen Sie sich in Ihren Vergleichen auf diese Zahl und machen Sie Ihre Messungen auch auf der g0, um die Vergleichbarkeit zu gewaehrleisten. Wenn Ihre Optimierung den Platzbedarf (statisch im Programm und/oder den dynamisch allokierten Speicher) nennenswert ändert, präsentieren Sie bitte auch Messungen dazu (mit objdump -h oder readelf -S sehen Sie die Größe diverser Sections im Binary; size zählt leider z.B. .rodata nicht zu data).

Mit 

    make clean
können Sie die erzeugten Dateien löschen. Beachten Sie, dass Sie dann zum Neubauen iburg brauchen (ist auf der g0 installiert).

Hintergrund

Sie können sich direkt in die Optimierung stürzen, aber vermutlich finden Sie sich mit folgenden Informationen etwas besser zurecht:

gforth9 ist von der optimalen Codeauswahl für Gforth (aus dem Jahr 2007 für die PowerPC-Architektur) abgeleitet. Und zwar gibt es 355 primitive Wörter in Gforth, die in gforth9.burg die Namen op0-op354 haben (die Forth-Namen sind mit iburg und C nicht kompatibel und wurden deswegen durch diese wenig sprechenden Namen ersetzt).

Die Wörter arbeiten auf einem Stack. Im einfachsten Fall gibt es eine Darstellung des Stacks, und jedes Forth-Wort erwartet den Stack am Anfang in dieser Form und hinterlässt den Stack am Schluss in dieser Form; diese kanonische Darstellung wird in gforth9.burg durch das Nonterminal S0 repräsentiert. Eine typische Regel ist: 

    S0: op53(S0) = 54 (16);
Das bedeutet, dass der Stack in S0 beginnt und S0 endet, das Wort op53 aufgerufen wird, und der Code dafür 16 Bytes kostet. Die Regel hat die eindeutige Nummer 54 (und das sagt dem Codegenerator auch, welcher Code erzeugt werden muss; die eigentliche Codeerzeugung kommt aber in diesem Beispiel nicht vor, es endet mit der Ausgabe der Regeln).

Jetzt kann man aber noch andere Stack-Darstellungen einführen, z.B. eine, in der die obersten drei Elemente des Stacks in Registern (und nicht im Speicher) sind. Es kann billiger sein, wenn ein Wort den Stack nicht im kanonischen Zustand hinterlässt und das nächste Wort dann in diesem Zustand weitermacht. Zum Beispiel gibt es für op53 noch eine Reihe anderer Regeln, z.B.: 

    S2: op53(S0) = 441 (8);
Hier hat ist der Stack vor dem Wort im Zustand S2, und nach dem Wort in S0 und der Code dafür kostet nur 8 Bytes. [Leute, die sich mit burg/iburg besser auskenen, werden sich fragen, warum der Zustand vorher auf der linken Seite der Regel ist und der Zustand danach auf der rechten Seite; ja, man könnte es auch genausogut umgekehrt machen, hier wurde eben diese Richtung gewählt.]

Man kann auch Code einfügen, um direkt von einem Stackzustand in den anderen überzugehen, z.B. repräsentiert durch diese Regel: 

    S0: S2 = 1137 (8);

Damit eine Sequenz enden kann, brauchen wir auch noch ein Terminal bzw. Blatt (Terminal aus der Grammatiksicht und Blatt aus der Baumsicht). Dazu haben wir ein Blatt s0 und die Regel 

    S0: s0 = 1200;
(mit Kosten 0), die aber beide dazu da sind, um in den Baumgrammatik-Formalismus hineinzupassen.

Es kann also für eine Sequenz von Wörtern auf verschiedenste Weise Code erzeugt werden, mit beliebigen Stack-Zuständen am Anfang und Ende jedes Wortes, und dann noch direkte Übergänge zwischen Stack-Zuständen.

Am besten wählen wir den Code mit den geringsten Kosten aus. Für die optimale Codeerzeugung mit solchen Regeln gibt es die Werkzeuge iburg und burg, wobei iburg mittels dynamic programming zur Laufzeit von gforth9 arbeitet (siehe auch Kapitel 9.1 des Übersetzerbau-Skriptums), während bei Verwendung von burg gforth9 nur mehr einen Baumautomaten abarbeitet und damit deutlich schneller ist. Allerdings schafft burg es nicht, den Automaten für gforth9.burg zu erzeugen (der Automat wird so groß, dass burg bei seiner Erzeugung abstürzt), deswegen verwenden wir iburg und deswegen gibt es dieses Beispiel.

Dokumentation zu iburg gibt es hier und hier, und mittels man iburg.

In brew-sequences.bin gibt es ca. 28000 Sequenzen mit zusammen 62000 Wörtern. Jede Wort ist durch eine 16-bit-Zahl (short) dargestellt, jede Sequenz wird durch die Zahl 0 abgeschlossen. Die rules-Ausgabe enthält einfach die angewendeten Regeln (als 16-bit-Zahlen) ohne Separation zwischen den Sequenzen. Die costs-Ausgabe enthält die Kosten für jede Sequenz als 16-bit-Zahl.

Im Normalfall fängt jede Sequenz im Zustand S0 and und endet im Zustand S0 (und für das Programm gforth9 übergibt man dann 0 als letzten Parameter). Um das Testen ein bisschen breiter zu machen, gibt es noch die Möglichkeit, einen anderen Zustand als Normalzustand zwischen den Sequenzen einzustellen (letzter Parameter von gforth9, darf 0-8 sein).

Ist es praktisch relevant, schneller zu sein als die von iburg produzierte Codeauswahl? Da bei Gforth (wie auch bei JIT-Compilern allgemein) der Code jedes mal beim Starten erzeugt wird, spielt das schon eine wichtige Rolle, vor allem wenn man das System in einem Shell-Script eingesetzt wird, wo es vielleicht in einer Schleife aufgerufen wird.

Hinweise

Sie können nach einfachen lokalen Verbesserungen Ausschau halten, es gibt aber noch andere Möglichkeiten.

Zunächst einmal ist iburg auf Bäume ausgelegt (mit Knoten mit mehr als einem Kind), während in diesem Beispiel nur Knoten mit einem (bzw. bei Blattknoten keinem) Kind vorkommen.

Wir können zwar keinen Automaten mit burg bauen, aber es gibt die Möglichkeit, die Zustände eines Automaten bei Bedarf zu erzeugen (siehe Fast and Flexible Instruction Selection with On-Demand Tree-Parsing Automata), einen Teil des Automaten schon im vorhinein zu erzeugen, oder für Gesamtsequenzen das Ergebnis (z.B. mittels Memoization oder compile-time initialization) nachzuschauen statt neu zu berechnen.

Das sind nur ein paar Vorschläge, die gedacht sind, Ihre Phantasie anzuregen; wenn Ihnen noch etwas anderes einfällt, umso besser.

Es ist natürlich leicht, eine Version zu machen, die genau für diese Eingabe schnell ist (und für alle anderen so langsam wie vorher), aber damit würden Sie das Lehrziel verfehlen. Es geht also darum, eine Version zu produzieren, bei der man auch für andere Eingaben ähnliche Beschleunigungen erwarten würde.
[ICO]NameLast modifiedSizeDescription
[PARENTDIR]Parent Directory  -  
[DIR]effizienz-aufgabe20/2020-12-07 18:56 -  
[ ]Makefile2020-12-07 11:24 1.1K 
[TXT]main.c2020-12-07 10:12 4.1K 
[TXT]gforth9.h2020-12-07 09:35 5.8K 
[ ]main.o2020-12-07 11:24 6.9K 
[ ]gforth9.burg2020-12-07 08:54 35K 
[ ]brew-sequences0.costs2020-12-07 18:56 55K 
[ ]brew-sequences1.costs2020-12-07 18:56 55K 
[ ]brew-sequences2.costs2020-12-07 18:56 55K 
[ ]brew-sequences3.costs2020-12-07 18:56 55K 
[ ]brew-sequences4.costs2020-12-07 18:56 55K 
[ ]brew-sequences5.costs2020-12-07 18:56 55K 
[ ]brew-sequences6.costs2020-12-07 18:56 55K 
[ ]brew-sequences7.costs2020-12-07 18:56 55K 
[ ]brew-sequences8.costs2020-12-07 18:56 55K 
[ ]test.costs2020-12-07 14:11 55K 
[ ]brew-sequences.bin2020-12-07 11:24 175K 
[ ]perf.data2020-12-07 10:41 177K 
[ ]brew-sequences2020-12-07 11:24 184K 
[ ]effizienz-aufgabe20.tar.xz2020-12-07 18:56 193K 
[ ]brew-sequences0.rules2020-12-07 18:56 198K 
[ ]test.rules2020-12-07 14:11 198K 
[ ]gforth92020-12-07 11:24 213K 
[ ]gforth9.o2020-12-07 11:24 248K 
[ ]brew-sequences2.rules2020-12-07 18:56 277K 
[ ]brew-sequences3.rules2020-12-07 18:56 277K 
[ ]brew-sequences1.rules2020-12-07 18:56 279K 
[ ]brew-sequences4.rules2020-12-07 18:56 279K 
[ ]brew-sequences5.rules2020-12-07 18:56 279K 
[ ]brew-sequences6.rules2020-12-07 18:56 279K 
[ ]brew-sequences7.rules2020-12-07 18:56 283K 
[ ]brew-sequences8.rules2020-12-07 18:56 289K 
[TXT]brew-sequences.txt2020-12-06 17:04 372K 
[TXT]gforth9.c2020-12-07 11:24 401K 
[ ]perf.data.old2020-12-07 10:40 414K 
[TXT]brew-sequences.c2020-12-07 08:48 493K 

This is a variant of the burg grammar for Gforth created for a newer
version of Gforth.

You also find the file brew-sequences that contains the basic blocks
present in Gforth with the brew benchmark.  Using these sequences with
the grammar: The leftmost operator is the root, the rightmost operator
is the immediate parent of the leaf, and the leaf is s0.  Ignore empty
basic blocks.

These sequences were generated with a Gforth compiled with
-DBURG_FORMAT and the following command:

gforth --print-sequences -e "warnings off create startup-bench" ~/forth-bench/brew-transit_38/brew.fs 2>brew-sequences

- anton