Informatiker Board | Druckvorschau: Akku- und Speichermaschine

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- Akku- und Speichermaschine (http://www.informatikerboard.de/board/thread.php?threadid=2723)

Geschrieben von Shizmo am 04.01.2016 um 22:20:

Akku- und Speichermaschine

So, eine habe ich noch großes Grinsen

Zitat:

Für zwei vorzeichenlose Zahlen $[latex]Z1 = A*2^{16}+B, Z2 = C*2^{16}+D[/latex]$
soll der mathematische Ausdruck $[latex]E = A*C*2^{32} + (B*C+A*D)*2^{16} + B*D[/latex]$

mit einer Akku-Maschine: LOAD x, STORE x, ADD x, MULT x, SHL i
mit einer Speicher-Maschine: ADD x, y, z, MULT x, y, z, SHL x, y, i

unter ausschließlicher Verwendung der jeweils angegebenen Opcodes berechnet werden.

i ist ein Immediate-Wert (z.B. 16).
Wir nehmen an, dass die Speicherstellen (A - E) und der Akku alle Ergebnisse aufnehmen können. Zwischenergebnisse können in zusätzlichen Speicherstellen ab F gespeichert werden. Sie sollten die Anzahl der Stores jedoch minimal halten.

Geben Sie jeweils den Assembler Code zur Berechnung obigen Ausdruckes an. Vergleichen Sie die Anzahl der Instruktionen und der notwendigen Speicherzugriffe.

Schritt für Schritt.
Erstmal nur die Akku-Maschine.

SHL ist soweit ich weiß Shift-Left, was kann ich damit bewirken?

Kann ich damit die "Zahlen" aufteilen oder so?

LG

Geschrieben von eulerscheZahl am 05.01.2016 um 07:20:

Wenn du eine Zahl um 16 nach links shiftest, ist das das selbe wie sie mit $[latex]2^{16}[/latex]$ zu multiplizieren.

Geschrieben von Shizmo am 05.01.2016 um 22:12:

Aha verwirrt

Was bringt mir das? geschockt

Geschrieben von eulerscheZahl am 06.01.2016 um 06:40:

LOAD A
LOAD C
MULT //A*C
SHL 32 //A*C*2^32 - das ist der erste Summand von E

Geschrieben von Shizmo am 06.01.2016 um 23:29:

Ah okay, Großartig großes Grinsen

- Aber laut meinen Unterlagen würde bei dir A durch C überschrieben werden, da man nur einmal loaden darf, aber ich denke so dürfte dass dann hinkommen oder?

LOAD A
MULT C
SHL 32
STORE F

LOAD B
MULT C
STORE G

LOAD A
MULT D
ADD G
SHL 16
STORE G

LOAD B
MULT D
ADD G
ADD F
STORE F

Anzahl der Instruktionen wären es 17 und Speicherzugriffe 4.

Also das wäre jetzt [latex]E[/latex]

- für was brauche ich Z1 und Z2??

Geschrieben von eulerscheZahl am 07.01.2016 um 06:57:

Sieht gut aus.
Z1 und Z2 ist die Eingabe, darüber musst du dir keine Gedanken machen.

Je nach Kosten für Addition und Multiplikation kannst du es auch mit 3 Multiplikationen lösen. Siehe Karatsuba.

Geschrieben von Shizmo am 09.01.2016 um 20:38:

Okay super, morgen mach ich weiter mit der Speichermaschine.

Wieso steht Z1 und Z2 dann überhaupt in der Angabe?
Also wir müssen solche Aufgaben immer an der Tafel vortragen und dann auch erklären, deshalb die Frage Zunge raus

Geschrieben von eulerscheZahl am 10.01.2016 um 09:23:

Stelle dir einfach vor, du hast 32Bit große Zahlen, aber der Prozessor kann nur 16Bit auf einmal rechnen. Da musst du die Rechnung aufteilen.

Geschrieben von Shizmo am 10.01.2016 um 10:53:

Alles klar okay danke, ich habs jetzt mal aufgeteilt und Z1 mit Z2 multipliziert und spare mir dadurch 8 Instruktionen, so sollte es doch auch passen oder? (Immer noch Akkumaschine)

LOAD A
SHL 16
ADD B
STORE F

LOAD C
SHL 16
ADD D

MULT F
STORE F

Wären dann nur 9 Instruktionen und 2 Speicherzugriffe.

Geschrieben von eulerscheZahl am 10.01.2016 um 13:20:

Bleibt eben die Frage, ob deine Zielarchitektur die Multiplikation zweier 32Bit Zahlen unterstützt.
Wenn sie das tut, geht das.

Geschrieben von Shizmo am 10.01.2016 um 17:24:

So jetzt musst du mir aber trotzdem noch helfen mit der Speicher-Maschine. Also da ich da ja keinen LOAD und STORE befehl habe, brauche ich es nicht laden und die Speicher-Maschine kann es wahrscheinlich zwischenspeichern.
Aber wie gehe ich da vor?