Transcript Instructions and Stacks

About Instructions
Based in part on material from
Chapters 4 & 5 in Computer
Architecture by Nicholas Carter
PHY 201 (Blum)
1
Instruction Set
• One aspect of processor design is to
determine what instructions will be
supported.
• There must be rules (syntax) for how
instructions are expressed so that the code
can be parsed, one instruction distinguished
from the next, the data (operand) separated
from the action (operator).
PHY 201 (Blum)
2
Number of operands
• An example of syntax would be whether an
operator is binary or unary
• Binary operators take two operands
– e.g. the boolean operator AND
– (x<y) AND (i=j)
• Unary operator take one operand
– E.g. the boolean operator NOT
– NOT(x<y)
• Some ops are context dependent
– - 5 (unary) versus 4-5 (binary)
PHY 201 (Blum)
3
Operation versus Instruction
• An operation such as addition, which is
binary (takes two operands), can be coded
using instructions that are unary (one
operand) if there is a default location implied
such as Accumulator A.
• 5 + 6 becomes
– Load 5 (places data in acc. A)
– Add 6 (adds number in Acc. A to new number)
PHY 201 (Blum)
4
Where does the answer go?
• Whether it’s 5 + 6 or (Load 5, Add 6),
there’s the question of what to do with the
result.
• We can again use the default location of
Accumulator A to place the answer in or we
can include a third operand that indicates
where the result should be placed.
PHY 201 (Blum)
5
Store
• Placing the result of an operation in memory is
known as storing it. Thus with unary instructions,
we would have
– Load 5
– Add 6
– Store 7
• The operand of the store is an address indicating
where to store the answer, which is held in
Accumulator A.
• Or one might have three operands
– Add 7, 5, 6
PHY 201 (Blum)
6
Addressing Modes
• But this raises the question as to what were
the operands in the two previous
instructions (Load and Add).
• For those instructions, the operand might
have been the actual numbers one wanted
added or the addresses of numbers one
wanted added.
PHY 201 (Blum)
7
More than one kind of add
• By Add one typically means the latter case
on the previous slide. The operand is not
the number to be added but the address of
the number to be added.
• A designer can include a distinct add
instruction, Add Immediate, in which the
operand is the actual number to be added.
PHY 201 (Blum)
8
Add Indirect
• In another version of addition, the operand
is an address, and the data at that address is
also an address, and the actual number to
added is located at the second address.
PHY 201 (Blum)
9
A short program
Address
Value
0
LOAD 4
1
ADD INDIRECT 5
2
ADD IMMEDIATE 6
3
STOP
4
5
5
6
6
7
7
8
PHY 201 (Blum)
Acc. A: XXX
The arrow indicates the
program counter, we
assume it has not
executed the statement it
points to.
10
A short program
Address
Value
0
LOAD 4
1
ADD INDIRECT 5
2
ADD IMMEDIATE 6
3
STOP
4
5
5
6
6
7
7
8
PHY 201 (Blum)
Acc. A: 5
The Load 4 instruction
has been executed.
The value at location 4
(which is a 5) has
been loaded into the
accumulator.
11
A short program
Address
Value
0
LOAD 4
1
ADD INDIRECT 5
2
ADD IMMEDIATE 6
3
STOP
4
5
5
6
6
7
7
8
PHY 201 (Blum)
Acc. A: 12
The Add Indirect 5 instruction
has been executed. One goes
to location 5 to find a value of
6. That 6 is an address, thus
one goes to location 6 to find a
value of 7 and that is added to
the 5 waiting in the
accumulator. The result of 12
is placed in the accumulator.
12
A short program
Address
Value
0
LOAD 4
1
ADD INDIRECT 5
2
ADD IMMEDIATE 6
3
STOP
4
5
5
6
6
7
7
8
PHY 201 (Blum)
Acc. A: 18
The Add Immediate 6
instruction has been
executed. The value 6 is
data which is added to the
12 waiting in the
accumulator. The result of
18 is placed in the
accumulator.
13
The Stop Instruction
• Recall that in what is actually executed (machine
code) the instructions themselves numbers.
• Thus it is crucial to know within an instruction
which numbers correspond to an operation and
which numbers are operands.
• Similarly on the level of the program itself, the
processor needs to know where the program ends
as there may be data stored after it.
• In a machine with an operating system, it is more
a notion of returning (control) than of stopping or
halting.
PHY 201 (Blum)
14
Recap so far
• So there were issues about the number of
operands.
– Recall that we have a fetch-execute cycle – first an
instruction is retrieved from memory and then acted
upon.
– With unary instructions adding two numbers and
storing the result required three instructions, that’s three
fetches and three executions.
– With ternary instructions it can be done with one
instruction, one fetch and one execute. The execution is
now more complicated but we have saved time on
fetches.
PHY 201 (Blum)
15
Recap so far (Cont.)
• More operators means more complicated
circuitry, the load and store aspects of the
instruction would have to built into each
separate instruction.
• There is a speed versus complexity issue.
And complexity also brings the issue of cost
along with it.
PHY 201 (Blum)
16
Recap so far (Cont.)
• After determining the number of operands came
the issue of what the operands mean.
– Are they data, addresses of data or addresses of
addresses of data?
• Either we can decide to support all of these and
choose complexity. Or we can choose to support
only some of them and sacrifice efficiency.
– For example, you can eliminate Add Immediate if you
always store the values you want to add.
PHY 201 (Blum)
17
Data Types
• Apart from addressing, another issue is the type of
data the operation is acting on.
– The process for adding integers is different from the
process for adding floating point numbers.
– So one may have separate instructions: ADD for
addition of integers and FADD for the addition floats.
– Furthermore, one may need to include instructions to
convert from one type to another.
• To add an integer to a float, convert the integer to a float and
then add the floats.
PHY 201 (Blum)
18
Ordering of opcodes and operands
• Another example of syntax is the ordering of
opcode and operand(s).
• Postfix: operand(s) then opcode
– 45+
– Works well with stacks
• Prefix: opcode then operand(s)
– +45
• Infix: operand opcode operand
– 4+5
PHY 201 (Blum)
19
Precedence (aka Order of Operations)
• Precedence is the order in which operations occur
when an expression contains more than one
operation.
• Operations with higher precedence are performed
before operators with lower precedence.
– 1+2*3-4
– 1+6-4
(multiplication has higher precedence)
– 7-4
(start on the left when operators have the same precedence)
– 3
PHY 201 (Blum)
20
Infix to postfix
• To convert 1+2*3-4, put in parentheses even
though they’re not strictly necessary for this
expression
– ((1+(2*3))-4)
• Convert the innermost parentheses to postfix: 2*3
becomes 2 3 *
– ((1+(2 3 *))-4)
• Convert the next set of parentheses
– ((1 2 3 * +)-4)
PHY 201 (Blum)
21
Infix to postfix
• The last step eliminated the innermost set of
parentheses. Continue to convert from infix
to postfix from the innermost to outermost
parentheses.
– (1 2 3 * + 4 -)
• Note there is one overall set of parentheses
that can be thrown away. Also note that the
order of the numbers has not changed.
PHY 201 (Blum)
22
Another example
• 1+ (2+3) * 4 + (5 + 6) * ((7 + 8) * 9)
– Add parentheses
• 1+ ((2+3) * 4) + ((5 + 6) * ((7 + 8) * 9))
– Add parentheses
• (1+ ((2+3) * 4)) + ((5 + 6) * ((7 + 8) * 9))
– Add parentheses
• ((1+ ((2+3) * 4)) + ((5 + 6) * ((7 + 8) * 9)))
– Convert innermost to postfix
• ((1+ ((2 3 +) * 4)) + ((5 6 +) * ((7 8 +) * 9)))
PHY 201 (Blum)
23
Another Example (Cont.)
•
•
•
•
((1+ ((2 3 +) * 4)) + ((5 6 +) * ((7 8 +) * 9)))
((1+ (2 3 + 4 * )) + ((5 6 +) * (7 8 + 9 * )))
((1 2 3 + 4 * +) + (5 6 + 7 8 + 9 * *))
(12 3+4*+56+78+9**+)
PHY 201 (Blum)
24
Postfix good for Hardware
• Postfix order is better suited for hardware
since one must prepare the inputs (a.k.a. the
data or operands) before operating on them
to get an output.
• Postfix is particularly well suited for
architectures that use a stack to perform
computations.
PHY 201 (Blum)
25
The stack
• A stack is a data structure (which may be
implemented in hardware or in software)
that holds a sequence of data but limits the
way in which data is accessed.
• A stack obeys the Last-In-First-Out (LIFO)
protocol, the last item written (pushed) is
the first item to be read (popped).
PHY 201 (Blum)
26
Stack
2 is pushed 2 is popped
onto the
off of the
stack
stack
1
PHY 201 (Blum)
2
1
1
3
1
4
3
1
27
Stack Pointer: don’t move all the
data just change the pointer
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
x
X
X
4
X
2
2
3
3
1
1
1
1
1
PHY 201 (Blum)
28
Infix Evaluation
•
•
•
•
•
•
1+ (2+3) * 4 + (5 + 6) * ((7 + 8) * 9)
1+(5)*4 + (11)*((15)*9)
1 + 20 + 11*135
1 + 20 + 1485
21 + 1485
1506
PHY 201 (Blum)
29
Evaluating a postfix expression using a stack (1)
Enter the postfix
expression and click Step
PHY 201 (Blum)
30
Evaluating a postfix expression using a stack (2)
PHY 201 (Blum)
31
Evaluating a postfix expression using a stack (3)
PHY 201 (Blum)
32
Evaluating a postfix expression using a stack (4)
PHY 201 (Blum)
33
Evaluating a postfix expression using a stack (5)
PHY 201 (Blum)
34
Evaluating a postfix expression using a stack (6)
PHY 201 (Blum)
35
Evaluating a postfix expression using a stack (7)
PHY 201 (Blum)
36
Evaluating a postfix expression using a stack (8)
PHY 201 (Blum)
37
Evaluating a postfix expression using a stack (9)
PHY 201 (Blum)
38
Evaluating a postfix expression using a stack (10)
PHY 201 (Blum)
39
Evaluating a postfix expression using a stack (11)
PHY 201 (Blum)
40
Evaluating a postfix expression using a stack
(12)
PHY 201 (Blum)
41
Evaluating a postfix expression using a stack
(13)
PHY 201 (Blum)
42
Evaluating a postfix expression using a stack
(14)
PHY 201 (Blum)
43
Evaluating a postfix expression using a stack
(15)
PHY 201 (Blum)
44
Evaluating a postfix expression using a stack
(16)
PHY 201 (Blum)
45
Evaluating a postfix expression using a stack
(17)
PHY 201 (Blum)
46
Evaluating a postfix expression using a stack
(18)
PHY 201 (Blum)
47
Evaluating a postfix expression using a stack
(19)
PHY 201 (Blum)
48
Evaluating a postfix expression using a stack
(20)
PHY 201 (Blum)
49
Evaluating a postfix expression using a stack
(21)
PHY 201 (Blum)
50
Evaluating a postfix expression using a stack
(22)
PHY 201 (Blum)
51
Evaluating a postfix expression using a stack
(23)
PHY 201 (Blum)
52
Evaluating a postfix expression using a stack
(24)
PHY 201 (Blum)
53
Evaluating a postfix expression using a stack
(25)
PHY 201 (Blum)
54
Evaluating a postfix expression using a stack
(26)
PHY 201 (Blum)
55
Evaluating a postfix expression using a stack
(27)
PHY 201 (Blum)
56
Evaluating a postfix expression using a stack
(28)
PHY 201 (Blum)
57
Evaluating a postfix expression using a stack
(29)
PHY 201 (Blum)
58
Evaluating a postfix expression using a stack
(30)
PHY 201 (Blum)
59
Evaluating a postfix expression using a stack
(31)
PHY 201 (Blum)
60
Evaluating a postfix expression using a stack
(32)
PHY 201 (Blum)
61
Evaluating a postfix expression using a stack
(33)
PHY 201 (Blum)
62
Evaluating a postfix expression using a stack
(34)
PHY 201 (Blum)
63
References
• Computer Architecture, Nicholas Carter
• Computers Systems: Organization and
Architecture, John Carpinelli
• http://www.cs.orst.edu/~minoura/cs261/java
Progs/stack/Polish.html
PHY 201 (Blum)
64