Informatiker Board | Druckvorschau: Anweisung auf eine Stackmaschine implementieren

Geschrieben von Shizmo am 03.01.2016 um 13:32:

Anweisung auf eine Stackmaschine implementieren

Hallo Wink

Zitat:

Implementieren Sie die Anweisung e = (a + b)(c + (a + b) d) auf einer Stackmaschine.

Sie haben die Befehle push (3 Taktzyklen), pop (3), add (1), mult (5) zur Verfügung.
Sie haben zusätzlich den Befehl dup (1 Taktzyklus) zur Verfügung, der das oberste Stackelement dupliziert. Die Addition ist kommutativ (a + b = b + a).

Zählen Sie für beide Fälle die Anzahl der Befehle, die Anzahl der Speicherzugriffe (mit und ohne dem Einlesen der Befehlscodes) und
die Anzahl der Taktzyklen, die das Programm benötigt.

Ermitteln Sie auch, wie viele Bytes im Programmablauf zwischen Speicher und CPU transferiert werden, wenn ein Operationscode 1 Byte lang ist, Speicheradressen 2 Bytes und Operanden 4 Bytes. a, b, c und d stehen von Beginn an im Speicher.

Also als erstes würde ich die Anweisung (a + b)(c + (a + b) d) in die "polnische"-Notation bringen,
also ab + d * c + ab + * (ich hoffe das stimmt so), und dann die Befehle ausführen, also:

PUSH a
PUSH b
ADD
PUSH d
MULT
PUSH c
ADD
PUSH a
PUSH b
ADD
MULT
POP

Okay, also funktioniert das so oder muss ich das mehr aufteilen?

BLAU a) wäre dann also 12.

Geschrieben von eulerscheZahl am 03.01.2016 um 14:06:

Passt fürs erste, in der b) wird optimiert.

Geschrieben von Shizmo am 03.01.2016 um 14:35:

Okay super, danke.

Zitat:

Zählen Sie die Anzahl der Taktzyklen, die das Programm benötigt

Bei a) wäre dann für jedes Push 3, kommen sonst auch noch Taktzyklen vor?
Also 18 mMn.

Zitat:

Zählen Sie die Anzahl der Speicherzugriffe (mit und ohne dem Einlesen der Befehlscodes

Was wir denn alles unter einem Speicherzugriff verstanden? Sind das nicht nur die Push und Pop Befehle? Und die Befehlscodes sind die OP-Codes (also die, die in der Klammer danach stehen oder?).

Geschrieben von eulerscheZahl am 03.01.2016 um 14:42:

Du hast noch 2 MULT, 3 ADD und ein POP, also 18+2*5+3*1+1*3 = 34

Irgendwo muss ja auch die Informatin kommen, dass etwas addiert oder multipliziert werden soll. Ich denke du sollst hier für jeden Befehl ein pop rechnen, also 34+12*3 = 70

Geschrieben von Shizmo am 03.01.2016 um 15:06:

Ah okay und ohne Einlesen der Befehlscodes wäre es dann 34+7*3 = 55 ? Oder 18+12*3 = 54 ?

Zitat:

Ermitteln Sie auch, wie viele Bytes im Programmablauf zwischen Speicher und CPU transferiert werden, wenn ein Operationscode 1 Byte lang ist, Speicheradressen 2 Bytes und Operanden 4 Bytes. a, b, c und d stehen von Beginn an im Speicher.

12*1Byte (alle Codes) + 6*2Bytes (alle PUSH) + 5*4Bytes(alle ADD und MULT) = 44 Bytes ????

Geschrieben von eulerscheZahl am 03.01.2016 um 15:22:

Zitat:

Ah okay und ohne Einlesen der Befehlscodes wäre es dann 34+7*3 = 55 ? Oder 18+12*3 = 54 ?

Das musst du mir jetzt erklären.
Ich komme wir oben ausgerechnet auf 34 da waren deine ursprünglichen 6 pop ja schon mit dabei.

Beim letzten Teil denke ich, dass die Variablen noch vom Speicher in den Prozessor geladen werden müssen. Aber an der Stelle bin ich auch keine verlässliche Quelle.

Geschrieben von Shizmo am 03.01.2016 um 22:51:

Zitat:

Original von eulerscheZahl

Zitat:

Ah okay und ohne Einlesen der Befehlscodes wäre es dann 34+7*3 = 55 ? Oder 18+12*3 = 54 ?

Das musst du mir jetzt erklären.
Ich komme wir oben ausgerechnet auf 34 da waren deine ursprünglichen 6 pop ja schon mit dabei.

Laut Angabe gibt es die Anzahl der Speicherzugriffe mit und ohne dem Einlesen der Befehlscodes.

Mit wären ja: 34+12*3 = 70
Und bei ohne dachte ich mir ohne den (3 ADD und 2 MULT)-POPs, also 34+7*3 = 55

Dann noch zu b)
Würde das dann in etwa so aussehen?

PUSH a
PUSH b
ADD
DUP
PUSH d
MULT
PUSH c
ADD
MULT
POP

Geschrieben von eulerscheZahl am 04.01.2016 um 07:53:

Kosten für Befehl selbst und Befehlscode ohne Gewähr:
PUSH a 3 3
PUSH b 3 3
ADD 1 3
PUSH d 3 3
MULT 5 3
PUSH c 3 3
ADD 1 3
PUSH a 3 3
PUSH b 3 3
ADD 1 3
MULT 5 3
POP 3 3
gesamt: 34 36
Also 34 für die Befehle alleine. 34+36=70, wenn du den Code noch laden musst.

Die b) passt so.

Geschrieben von Shizmo am 04.01.2016 um 10:48:

Hmm okay, aber dann wäre

Zitat:

Zählen Sie die Anzahl der Taktzyklen, die das Programm benötigt

dasselbe wie die Anzahl der Speicherzugriffe ohne dem Einlesen der Befehlscodes.

Geschrieben von eulerscheZahl am 04.01.2016 um 10:56:

Ich habe die ganze Zeit von den Taktzyklen gesprochen.

Das einzige, was ich zum Speicherzugriff geschrieben habe:

Zitat:

Original von Shizrmo
12*1Byte (alle Codes) + 6*2Bytes (alle PUSH) + 5*4Bytes(alle ADD und MULT) = 44 Bytes ????

Zitat:

Original von eulerscheZahl
Beim letzten Teil denke ich, dass die Variablen noch vom Speicher in den Prozessor geladen werden müssen. Aber an der Stelle bin ich auch keine verlässliche Quelle.

Geschrieben von Shizmo am 23.01.2016 um 02:04:

Ich hätte hier noch ein Beispiel, wo ich mir nicht ganz sicher bin, die Angabe:

Zitat:

Implementieren Sie folgende Anweisung auf einer Stackmaschine:
$[latex]c=\frac{a}{b+\frac{a}{b+\frac{a}{b+a} } } [/latex]$

a) Sie haben die Befehle push, pop, add, div zur Verfügung.
b) Sie haben zusätzlich den Befehl dup zur Verfügung.

Also eh wieder sehr ähnlich:

Also erst einmal ordentlich hinschreiben: [latex]a/(b+a/(b+a/(b+a)))[/latex]

Dann polnische Notation: [latex]ab+a/b+a/b+a/[/latex]

Wenn das soweit passt ist a):
PUSH A
PUSH B
ADD
PUSH A
DIV
PUSH B
ADD
PUSH A
DIV
PUSH B
ADD
PUSH A
DIV
POP C

bei b) bin ich mir allerdings nicht ganz sicher:
PUSH A
PUSH B
ADD
PUSH A
DIV
DUP
PUSH B
ADD
DIV
POP C

Denn wenn ich das jetzt wieder auflöse, wäre das: [latex](((a+b)/a)+b) / (a+b)/a[/latex]

Wenn ich von rechts nach links gehe teile ich [latex]a[/latex]

durch

was ja eigentlich nicht richtig ist.

Wo liegt mein Fehler? Zunge raus

Geschrieben von eulerscheZahl am 23.01.2016 um 06:58:

Du hast in der polnischen Notation ein fünftes a dazubekommen. Nimm das mal wieder weg.

Geschrieben von Shizmo am 23.01.2016 um 10:06:

Hoppala, war ein Fehler beim Abtippen:

[latex]ab+a/b+a/b+a/[/latex]

Geschrieben von eulerscheZahl am 23.01.2016 um 10:36:

Ich komme bei deiner Rechnung auf $[latex]\frac{b+a/(a+b)}{a/(a+b)}[/latex]$ .
a/(b+a) zu kopieren macht denke ich keinen Sinn, weil man es nur einmal verwenden kann.
Ich würde erst mal schauen, dass ich die Doppelbrüche wegbekomme: $[latex]c=\frac{{\left({\left(a + b\right)} b + a\right)} a}{{\left(a + b\right)} a + {\left({\left(a + b\right)} b + a\right)} b}[/latex]$ .
Dadurch wird die Rechnung aber eher länger als kürzer verwirrt