FB18 - Das Forum für Informatik

fb18.de / Diplom Informatik / Unterbereich Grundstudium / Technische Informatik

T3 - Aufgabenblatt 5

T3 - Aufgabenblatt 5 2002-11-30 10:45
Spacelord
Ich habe mir erst mal mit gcc den Assemblercode erzeugen lassen, aber ich finde irgendwie nicht so richtig ne Möglichkeit, das zu optimieren. Kann man da kleine Teile ersetzen oder muss man praktisch die ganze Streufunktion neu schreiben?
Über ein paar kleine Optimierungshinweise würde ich mich echt freuen.

Re: T3 - Aufgabenblatt 5 2002-11-30 10:56
Faleiro
Ja, die Aufgabe ist das Neuschreiben, nicht das Optimieren der maschinell erzeugten Version :-)

Bei uns wird ausserdem cc statt gcc verwendet, vielleicht ist das in deiner Gruppe anders.

Bei der durch 'cc -S weinberger.c' erzeugten Version faellt auch gleich auf, dass z.B. die for-Bedingung an zwei verschiedenen Stellen geprueft wird, das kann man kuerzer machen. Allerdings wird es bei der Ausfuehrungsgeschwindigkeit wohl keinen Unterschied machen, dennoch sind dies die Stellen, woran dein Uebungsgruppenleiter sieht, dass du nicht allein gearbeitet hast ;-)

Es gibt da noch ein paar st-Befehle, deren Sinn ich nicht erkennen kann und die in unserer funktionierenden fertigen Neuversion nicht vorkommen; ausserdem wird mehrmals das Ergebnis einer Operation in z.B. %o2 geschrieben und dann gleich ins "richtige" Zielregister umkopiert, ebenfalls ohne erkennbaren Zweck.

Re: T3 - Aufgabenblatt 5 2002-11-30 10:59
Faleiro
Zum Vorgehen: Funktion streuw im C-Programm nur als Kopf behalten, den Rest loeschen. Dann streuw.s neu schreiben und alles zusammenschmeissen mit
cc [-o uebung5] weinberger.c streuw.s
Viel Spaß! :-)


Re: T3 - Aufgabenblatt 5 2002-11-30 11:17
TriPhoenix
Bei uns wird ausserdem cc statt gcc verwendet, vielleicht ist das in deiner Gruppe anders.
Soll eiegntlich jede Gruppe nach meinem Wissen.
@Spacelord, ich hoffe du jagst das aufm Uni-Rechner durch den (g)cc ? Weil zuhause bekommst du (solange ud keinen Sparc hast) ja auch keinen Sparc-Code :)

Es gibt da noch ein paar st-Befehle, deren Sinn ich nicht erkennen kann und die in unserer funktionierenden fertigen Neuversion nicht vorkommen; ausserdem wird mehrmals das Ergebnis einer Operation in z.B. %o2 geschrieben und dann gleich ins "richtige" Zielregister umkopiert, ebenfalls ohne erkennbaren Zweck.
Genau das sind die Dinge weswegen ich denke es ist imemrnoch viel einfacher das einmal neu zu schreiben als den cc-generierten Code abzuändern. Der cc macht einfach zuviele Dinge, die ein Mensch nicht machen würde. Wenn man schon anfängt, welche Register der cc benutzt…ein Mensch benutzt wahrscheinlich l0-l7 oder o0-o7 oder so, aber nicht kreuz und quer, mal o0, o1 dann mal i4 i5 und dann nochmal g1 (wobei ich es nach wie vor suspekt finde, dass der Compiler das g1-Benutzt wo das doch von so vielen geteilt wird…)

Fazit:
Druck dir das generierte durchaus mal aus, fang dann aber neu an, schreib dir vielelicht auf, für welche C-Variable du welches Register benutzt. Wenn du eine Stelle mal nicht so gut weißt, kannst du imemrnoch abgucken, aber immer nur den Befehl, nicht die ganze Zeile ansich. So kommt man meiner Meinung am schnellsten durch und lernt dabei noch am meisten davon [img]http://www.sternenvolk.de/symb/28.gif[/img]

Re: T3 - Aufgabenblatt 5 2002-11-30 12:20
Spacelord
Danke für die Hilfe. Der Anfang funktioniert jetzt schon mal.

@TriPhoenix: Keine Sorge, ich mach das schon auf dem Uni-Rechner. (Mein eigener würde auch mit den Befehlen wenig anfangen können.)[img]http://www.sternenvolk.de/symb/22.gif[/img]

Dann versuch ich mich erst mal am Neuschreiben, aber ob das wirklich einfacher ist und schneller geht, als die cc-erzeugte Version abzuändern, bezweifel ich noch stark.

Re: T3 - Aufgabenblatt 5 2002-11-30 14:15
Fred
Dann versuch ich mich erst mal am Neuschreiben, aber ob das wirklich einfacher ist und schneller geht, als die cc-erzeugte Version abzuändern, bezweifel ich noch stark.
Ich schliesse mich der Meinung von TriPhoenix an, die merkwuerdige Wahl der Register erschwert das Umschreiben erheblich. Das Neuschreiben ist viel weniger fehleranfaellig, und man macht sich auch automatisch mehr Gedanken (z.B. ueber das if in der Schleife… hint!).

Bei einem Assemblerprogramm kannst Du allerdings nicht einfach so drauflos programmieren, wie man es vielleicht manchmal in Java tut. Du musst Dir von vornherein klarmachen, welche Variablen in dem C-Programm in welchen Registern landen sollen bzw. welche Register dann noch fuer Zwischenergebnisse herhalten koennen (Wie lange brauchen wir das Zwischenergebnis noch? Meist kann man das Register nach wenigen Zeilen Code bereits wieder fuer etwas anderes verwenden).

Z.B. habe ich fuer folgende Variablen lokale Register von %l0-%l3 reserviert: p, g, h, (*p). Und die Konstante 0xF0000000, welche man ja staendig braucht, steht in %l7. Das schoene an der Sparc-Architektur ist, dass Du Quellregister nie zerstoerst (es sei denn, Du moechtest das). Bei intel muesste man immer umstaendlich "Sicherheitskopien" anlegen, bevor man z.B. h um 4 nach links schiebt, weil das Original-h sonst weg waere.

Also ueberlege Dir auch immer gut, welches Zielregister Du bei den Operationen verwendest. Bei der letzten Subtraktion z.B. ist es sinnvoll, die Differenz gleich in %i0 zu speichern, denn diese soll ja zurueckgegeben werden und muss daher in %i0 stehen. Und ueberlege Dir auch mal, wie Du die drei NOPs nach dem Loeschen des y-Registers wegbekommen kannst (dazu muss man natuerlich wissen, warum die ueberhaupt notwendig sind).

Wie gesagt wuerde mich mal von anderen Leuten interessieren, wie viele Befehle letzten Endes noch bei Euch uebrig geblieben sind. Da ich das erst in dem Thread zum Zettel 4 geschrieben hatte hier nochmal mein Ergebnis:

Richtige Befehle: 21 (innerhalb von save… und jmp…/restore)
NOPs: 2 (die kann man auch weglassen, weil der jeweils nachstehende Befehl nicht gefaehrlich ist, ich habe sie aber dringelassen, damit der Uebungsgruppenleiter nicht denkt, ich sei mir nicht ueber die verzoegerte Sprungausfuehrung im klaren)
Labels: 2 (ohne das Label der Funktion selbst)
Bedingte Spruenge: 2

Die Schleifenbedingung pruefe ich in meinem Code einmal vor Eintritt der Schleife (um den Fall abzufangen, dass ein Null-String uebergeben wird) sowie nach jedem Iterationsschritt. Da kann man noch zwei Befehle sparen, indem man wieder per BA nach oben springt, aber das ist langsamer.

Theoretisch ergibt sich so ein Minimum von 19 Befehlen (mit Einsatz des BA und weglassen der NOPs), zwei Labels, einem bedingten Sprung und einem unbedingten. Oder hat jemand noch kompakteren Code?

P.S.: haettest Du nicht spaetestens gestern abgeben muessen??



Re: T3 - Aufgabenblatt 5 2002-11-30 14:25
Slater
Labels: 2 (ohne das Label der Funktion selbst)
wie klappt das denn?,
ich brauch eins für schleifenanfang, schleifenende und beim if innerhalb der schleife


Re: T3 - Aufgabenblatt 5 2002-11-30 14:46
Slater
noch mal zum if in der schleife, wie geht das ohne sprung?
oder alternativ, wie geht die schleife mit nur einem sprung, wenn du insgesamt nur 2 sprünge hast (und 2 labels)

andcc %l1,%l4,%l2 !g = h & 0xf0000000, cc aktualisiert be .nachif ! if-block überspringen wenn g == 0 nop srl %l2,24,%l5 ! if block xor %l5,%l2,%l5 ! .. xor %l5,%l1,%l1 ! .. .nachif: ...



Re: T3 - Aufgabenblatt 5 2002-11-30 15:53
Fred
noch mal zum if in der schleife, wie geht das ohne sprung?
Als kleiner Tip zwei aequivalente Addier-Funktionen.

public int add1(int a, int b)
{
if (b) return a+b; else return a;
}

public int add2(int a, int b)
{
return a+b;
}

Ist der Groschen gefallen? [img]http://www.sternenvolk.de/symb/25.gif[/img]




Re: T3 - Aufgabenblatt 5 2002-11-30 15:59
Slater
wenn du damit meinst, dass bei 0 der schleifendurchlauf nicht schadet,

na gut, hab ich nicht durchgerechnet mit den ganzen xor, ist das dann nicht so langsam wie die sache mit unbedingenten sprung? [img]http://www.sternenvolk.de/symb/24.gif[/img]

edit
man spart wohl einen haufen vergleiche, ok ist schöner [img]http://www.sternenvolk.de/symb/23.gif[/img]

Re: T3 - Aufgabenblatt 5 2002-11-30 16:04
Fred
wenn du damit meinst, dass bei 0 der schleifendurchlauf nicht schadet
<pling>
na gut, hab ich nicht durchgerechnet mit den ganzen xor,
Na ist doch nicht so schwer, a xor 0 = a.
ist das dann nicht so langsam wie die sache mit unbedingenten sprung? [img]http://www.sternenvolk.de/symb/24.gif[/img]
das schlimmste, was du einer cpu vorwerfen kannst, sind bedingte spruenge.
man spart wohl einen haufen vergleiche, ok ist schöner [img]http://www.sternenvolk.de/symb/23.gif[/img]
Jupp… und das IF ist z.B. definitiv etwas, was kein Compiler wegoptimieren kann. Mal schauen, wie viele Leute in ihrer Loesung noch das IF stehen haben, weil sie stur C nach ASM uebersetzt haben…


Re: T3 - Aufgabenblatt 5 2002-11-30 19:39
Fred
Eine sehr einfache Optimierung am Rande: das wr %g0, %g0, %y kann man direkt an den Anfang stellen, dann spart man sich spaeter die drei NOPs vor dem DIV.

Edit: oh ich habe schon lange keine Links mehr gepostet, http://www.sparc.com/standards/V8.pdf



Re: T3 - Aufgabenblatt 5 2002-11-30 19:48
Spacelord
Eine sehr einfache Optimierung am Rande: das wr %g0, %g0, %y kann man direkt an den Anfang stellen, dann spart man sich spaeter die drei NOPs vor dem DIV.

Ist das eigentlich ein bedeutender Unterschied wenn ich statt wr ein mov %g0,%y gemacht habe?

Re: T3 - Aufgabenblatt 5 2002-11-30 19:49
Fred
Ist das eigentlich ein bedeutender Unterschied wenn ich statt wr ein mov %g0,%y gemacht habe?
mov ist ein synthetischer Befehl, ich gehe mal davon aus, dass der Compiler das in wr %g0, %g0, %y umwandelt.

Edit: jupp, hab nochmal im Sparc Manual nachgeschaut, so ist es.


Re: T3 - Aufgabenblatt 5 2002-11-30 22:20
TriPhoenix
Eine sehr einfache Optimierung am Rande: das wr %g0, %g0, %y kann man direkt an den Anfang stellen, dann spart man sich spaeter die drei NOPs vor dem DIV.

Wozu sind die drei NOPs gut? Funzt bei mir auch ohne bestens


Re: T3 - Aufgabenblatt 5 2002-11-30 22:27
Fred
Eine sehr einfache Optimierung am Rande: das wr %g0, %g0, %y kann man direkt an den Anfang stellen, dann spart man sich spaeter die drei NOPs vor dem DIV.
Wozu sind die drei NOPs gut? Funzt bei mir auch ohne bestens
Was habt ihr fuer komische Uebungsgruppenleiter? :-)
Nach dem Ausfuehren des wr Befehls ist der gewuenschte Wert noch nicht sofort im y-Register, sondern erst nach drei Taktzyklen. Deswegen muss man warten. Wenn das bei Dir auch so funktioniert ist das hoechstwahrscheinlich purer Zufall.

Edit: Most processors have certain idiosyncratic instructions, and the SPARC is no exception. The most troublesome are the mul and div instructions. The product of two 32-bit numbers can take 64 bits to express; conversely, it makes sense to provide a 64 bit dividend (first argument) to a 32-bit division. The SPARC uses a special register called %y to hold the high-order 32 bits of the result of a multiply, and the high-order 32 bits of the dividend of a divide. You can just ignore this after the multiply, since, like most high-level languages, PCAT quietly throws away the high-order part of the result. But it is essential to clear the %y register before doing a divide, because the results of a previous multiply may be sitting around in it. This is done via an explicit wr instruction, which is documented as requiring up to three extra cycles to complete. Hence the complete sequence for a DIV is:

wr %g0,0,%y; nop; nop; nop; udiv r1,r2,r3

Was sagt dies? Es kann durchaus sein, dass Eure Programme auch ohne die drei NOPs auf dem jeweiligen Rechner funktionieren. Aber dann kann es passieren, dass sie auf einem anderen Rechner versagen. Klar?


Re: T3 - Aufgabenblatt 5 2002-11-30 22:58
Fred
na gut, hab ich nicht durchgerechnet mit den ganzen xor, ist das dann nicht so langsam wie die sache mit unbedingenten sprung? [img]http://www.sternenvolk.de/symb/24.gif[/img]
Ueberleg Dir ruhig mal, wie wahrscheinlich es ist, dass g & 0xF0000000 null ist (so dass der Sprung was bringt). Na? :-)

Ah noch was zum Platzsparen, man kann natuerlich auch das save und restore weglassen, dann hat man zwar nur noch 6 Register frei, aber das sollte gerade ausreichen. Naja zu spaet ich hab meins schon abgegeben.


Re: T3 - Aufgabenblatt 5 2002-11-30 23:11
TriPhoenix
Was habt ihr fuer komische Uebungsgruppenleiter? :-)
Einen ders nicht erwähnt hat oder ich hab geschlafen [img]http://www.sternenvolk.de/symb/28.gif[/img]

Was sagt dies? Es kann durchaus sein, dass Eure Programme auch ohne die drei NOPs auf dem jeweiligen Rechner funktionieren. Aber dann kann es passieren, dass sie auf einem anderen Rechner versagen. Klar?
Steht da dass das Programm auf ALLEN Sparc-Rechnern laufen muss? ;) Egal, ist sowieso zu spät, ist abgeschickt und im Zweifelsfall gebe ich dem Ü-Leiter die Schuld [img]http://www.sternenvolk.de/symb/22.gif[/img]

Re: T3 - Aufgabenblatt 5 2002-11-30 23:19
Fred
Was sagt dies? Es kann durchaus sein, dass Eure Programme auch ohne die drei NOPs auf dem jeweiligen Rechner funktionieren. Aber dann kann es passieren, dass sie auf einem anderen Rechner versagen. Klar?
Steht da dass das Programm auf ALLEN Sparc-Rechnern laufen muss? ;) Egal, ist sowieso zu spät, ist abgeschickt und im Zweifelsfall gebe ich dem Ü-Leiter die Schuld [img]http://www.sternenvolk.de/symb/22.gif[/img]
Schick doch einfach ne neue Version mit den NOPs bzw. mit dem wr ganz am Anfang mit der Entschuldigung, Du haettest aus Versehen eine fruehrere Version aus nem Backup Verzeichnis geschickt gehabt.