Forum
 
Fragen
 
Suchen
 
Über Uns
 
 

Anweisung auf eine Stackmaschine implementieren
Neue Frage »

03.01.2016, 13:32 Auf diesen Beitrag antworten »
Shizmo Anweisung auf eine Stackmaschine implementieren

Hallo Wink

Zitat:
Implementieren Sie die Anweisung e = (a + b)(c + (a + b) d) auf einer Stackmaschine.
  1. Sie haben die Befehle push (3 Taktzyklen), pop (3), add (1), mult (5) zur Verfügung.
  2. 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.
 
 
03.01.2016, 14:06 Auf diesen Beitrag antworten »
eulerscheZahl

Passt fürs erste, in der b) wird optimiert.
03.01.2016, 14:35 Auf diesen Beitrag antworten »
Shizmo

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?).
03.01.2016, 14:42 Auf diesen Beitrag antworten »
eulerscheZahl

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
 Anzeige
 
03.01.2016, 15:06 Auf diesen Beitrag antworten »
Shizmo

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 ????
03.01.2016, 15:22 Auf diesen Beitrag antworten »
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.

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.
03.01.2016, 22:51 Auf diesen Beitrag antworten »
Shizmo

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
04.01.2016, 07:53 Auf diesen Beitrag antworten »
eulerscheZahl

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.
04.01.2016, 10:48 Auf diesen Beitrag antworten »
Shizmo

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.
04.01.2016, 10:56 Auf diesen Beitrag antworten »
eulerscheZahl

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.
23.01.2016, 02:04 Auf diesen Beitrag antworten »
Shizmo

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 [latex](a+b)[/latex] was ja eigentlich nicht richtig ist.

Wo liegt mein Fehler? Zunge raus
23.01.2016, 06:58 Auf diesen Beitrag antworten »
eulerscheZahl

Du hast in der polnischen Notation ein fünftes a dazubekommen. Nimm das mal wieder weg.
23.01.2016, 10:06 Auf diesen Beitrag antworten »
Shizmo

Hoppala, war ein Fehler beim Abtippen:

[latex]ab+a/b+a/b+a/[/latex]
23.01.2016, 10:36 Auf diesen Beitrag antworten »
eulerscheZahl

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
23.01.2016, 10:48 Auf diesen Beitrag antworten »
Shizmo

Hmmm, eigenartig. Aber die a) passt soweit?
23.01.2016, 10:50 Auf diesen Beitrag antworten »
eulerscheZahl

Ja, die a) passt.
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »


Informatiker Board » Themengebiete » Theoretische Informatik » Anweisung auf eine Stackmaschine implementieren

 
© 2005-2019 bei Informatikerboard.de | Archiv, alt, neueste | Kontakt | Jugendschutz | Nutzungsbedingungen