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

  1. Please write the machine code, the execution of which would increase the value in address 8 by 1.

    Ans:

    machine.py

    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)

  2. 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:

    machine.py

    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)

  3. 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:

    machine.py

      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?