Discussion Session 5¶
Computer Architecture¶
In computer engineering, computer architecture is a set of disciplines that describes the functionality, the organization and the implementation of computer systems; that is, it defines the capabilities of a computer and its programming model in an abstract way, and how the internal organization of the system is designed and implemented to meet the specified capabilities. [wikiarch]
The following emulator describes the architecture in an abstract way.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | #####################################################################
#
# CAS CS 320, Spring 2015
# Assignment 3 (skeleton code)
# machine.py
#
def simulate(s):
instructions = s if type(s) == list else s.split("\n")
instructions = [l.strip().split(" ") for l in instructions]
mem = {0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: -1, 6: 0}
control = 0
outputs = []
while control < len(instructions):
# Update the memory address for control.
mem[6] = control
# Retrieve the current instruction.
inst = instructions[control]
# print control
# print("memory: "+str(mem))
# print "ins is", inst
# Handle the instruction.
if inst[0] == 'label':
pass
if inst[0] == 'goto':
control = instructions.index(['label', inst[1]])
continue
if inst[0] == 'branch' and mem[int(inst[2])]:
control = instructions.index(['label', inst[1]])
continue
if inst[0] == 'jump':
control = mem[int(inst[1])]
continue
if inst[0] == 'set':
mem[int(inst[1])] = int(inst[2])
if inst[0] == 'copy':
mem[mem[4]] = mem[mem[3]]
if inst[0] == 'add':
mem[0] = mem[1] + mem[2]
# Push the output address's content to the output.
if mem[5] > -1:
outputs.append(mem[5])
mem[5] = -1
# Move control to the next instruction.
control = control + 1
print("memory: "+str(mem))
return outputs
# Examples of useful helper functions from lecture.
def copy(frm, to):
return [\
'set 3 ' + str(frm),\
'set 4 ' + str(to),\
'copy'\
]
# eof
|
Instruction Set¶
- goto label
- branch label [addr]
- jump [addr]
- set [addr] val
- copy [addr_from] [addr_to]
- add
Memory Model¶
The range of memory address spans from negative infinity to positive infinity. (We have infinite amount of memory, which is not possible in real case.)
Memory addresses with special functionalites: 0, 1, 2, 3, 4, 5, 6:
- 0, 1, 2 are used by add instruction.
- 3, 4 are used by copy instruction.
- 5 is used for output.
- 6 contains the current value of the program counter (instruction pointer).
Manual division of memory area:
- Stack: <= -1
- 7 is used to store the address of the top of the stack.
- Heap: > 8
Program Examples¶
Please write the machine code, the execution of which would increase the value in address 8 by 1.
Ans:
from machine import * init1 = ["set 8 100"] ans1 = ["set 3 8", \ "set 4 1", \ "copy", \ "set 2 1", \ "add", \ "set 3 0", \ "set 4 8", \ "copy"] def copy(src, dst): return ["set 3 " + str(src), \ "set 4 " + str(dst), \ "copy"] ans1a = copy(8, 1) + \ ["set 2 1", \ "add" ] + \ copy(0, 8) print simulate(init1 + ans1) print simulate(init1 + ans1a)
Please write the machine code, the execution of which have the following property:
Assume in the initial state, memory 8 stores a natural number n, after the execution memory 9 should store the summation of all the natural numbers less than or equal to n. For instance, if memory 8 stores 10 initially, then memory 9 should store 55 after the execution.
Ans:
from machine import * def copy(src, dst): return ["set 3 " + str(src), \ "set 4 " + str(dst), \ "copy"] def decrement(addr): return copy(addr, 1) + \ ["set 2 -1", \ "add" ] + \ copy(0, addr) def addto(src, dst): return copy(src, 1) + \ copy(dst, 2) + \ ["add"] + \ copy(0, dst) ans2 = ["set 9 0"] + \ copy(8, 10) + \ ["label start", \ "branch loop 10", \ "goto end", \ "label loop"] + \ addto(10, 9) + \ decrement(10) + \ ["goto start", \ "label end"] init2 = ["set 8 100"] print simulate(init2 + ans2)
Please write the machine code for the defintion of a recursive function, which can output 100 several times according to the value stored in memory 8. Please also write the code for invoking such function.
Ans:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140
from machine import * init1 = ["set 8 100"] ans1 = ["set 3 8", \ "set 4 1", \ "copy", \ "set 2 1", \ "add", \ "set 3 0", \ "set 4 8", \ "copy"] def copy(src, dst): return ["set 3 " + str(src), \ "set 4 " + str(dst), \ "copy"] ans1a = copy(8, 1) + \ ["set 2 1", \ "add" ] + \ copy(0, 8) def increment(addr): return copy(addr, 1) + \ ["set 2 1", \ "add" ] + \ copy(0, addr) def decrement(addr): return copy(addr, 1) + \ ["set 2 -1", \ "add" ] + \ copy(0, addr) def addto(src, dst): return copy(src, 1) + \ copy(dst, 2) + \ ["add"] + \ copy(0, dst) print simulate(init1 + ans1) print simulate(init1 + ans1a) print simulate(init1 + decrement(8)) ans2 = ["set 9 0"] + \ copy(8, 10) + \ ["label start", \ "branch loop 10", \ "goto end", \ "label loop"] + \ addto(10, 9) + \ decrement(10) + \ ["goto start", \ "label end"] init2 = ["set 8 100"] print simulate(init2 + ans2) init3 = ["set 7 -1", \ "set 8 5"] ans3 = [ "goto printx_end", \ "label printx_start", \ "branch printx_skip 8", \ "goto printx_return", \ "label printx_skip", "set 5 100"] + \ decrement(8) + \ decrement(7) + \ ["set 3 6", \ "set 4 1", \ "copy", \ "set 2 9", \ "add"] + \ copy(7, 4) + \ ["set 3 0", \ "copy"] + \ ["goto printx_start"] + \ increment(7) + \ ["label printx_return"] + \ copy(7, 3) + \ ["set 4 4", \ "copy", \ "jump 4", \ "label printx_end"] + \ \ decrement(7) + \ ["set 3 6", \ "set 4 1", \ "copy", \ "set 2 9", \ "add"] + \ copy(7, 4) + \ ["set 3 0", \ "copy"] + \ ["goto printx_start"] + \ increment(7) print simulate(init3 + ans3) def procedure(name, body): return [ "goto " + name + "_end", \ "label " + name + "_start"] + \ body + \ copy(7, 3) + \ ["set 4 4", \ "copy", \ "jump 4", \ "label " + name + "_end"] def call(name): return decrement(7) + \ ["set 3 6", \ "set 4 1", \ "copy", \ "set 2 9", \ "add"] + \ copy(7, 4) + \ ["set 3 0", \ "copy"] + \ ["goto " + name + "_start"] + \ increment(7) body = ["branch printx_skip 8", \ "goto printx_return", \ "label printx_skip", "set 5 100"] + \ decrement(8) + \ call("printx") + \ ["label printx_return"] init4 = ["set 7 -1", \ "set 8 5"] ans4 = procedure("printx", body) + call("printx") print simulate(init4 + ans4)
Tail Call Optimization¶
While loop and recursive tail call are equivalent.
Discussion
What’s the benefit?