Reconfigurable computing
Small Embedded Systems
Unit 2.4
Arithmetic Logic Unit Operations
Introduction
ALU operations
Status flags
Overflow and underflow
Arithmetic Logic Unit (ALU)
The basic device used to perform computations is the ALU
It has two operand inputs x, y
There are a range of operations that can be performed (e.g. add, subtract, …) to produce a result z
The operation that will be performed is determined by the opcode
Integer operand
Integer operand
Status
Status
Opcode
Integer result
x
y
z
Arithmetic Logic Unit (ALU)
A typical (simplified) set of operations might be
So if we set
opcode=1, then z=x+y
opcode=3, then z=x-y
and so on …
Opcode
x
y
z
Status
Status
Opcode Operation
1 Add
2 Add with carry
3 Subtract
4 Subtract with carry
5 Bitwise NOT x
6 Bitwise NOT y
7 Bitwise x AND y
8 Bitwise x OR y
9 Bitwise x XOR y
Status Flags
The status register records information about the result
Each bit in the status register records a particular piece of information about the ALU result.
These bits are normally known as “flags”
Every processor is slightly different, but almost all contain the following flags:
C: the last computation produced a carry output
V: the last computation caused a signed overflow
Z: the result of the last computation was zero
N: the result of the last computation was negative
For some operations, a status flag of the previous operation will be an input to the subsequent operation
Opcode
x
y
z
Status
Status
ALU Operations
Some of these operations are obvious in their effect
Suppose set opcode=7
Result z is bitwise AND of x, y
Other operations are more complicated
We’ll have a look in detail at addition
Opcode Operation
1 Add
2 Add with carry
3 Subtract
4 Subtract with carry
5 Bitwise NOT x
6 Bitwise NOT y
7 Bitwise x AND y
8 Bitwise x OR y
9 Bitwise x XOR y
1 0 0 0 0 0 0 1
0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 1
x=
y=
z=
Unsigned Binary Addition
Example: let’s use 8-bit integer variables x=129 and y=3
We’ll form the sum z=x+y;
Binary columns represent 1s, 2s, 4s, 8s etc.
Add columns together to get answer
If answer in one column becomes greater than 1, we generate a carry into the next column
1
1 0 0 0 0 0 0 1
+ 0 0 0 0 0 0 1 1
1 0 0 0 0 1 0 0
1
1
2
8
16
4
32
64
128
x=129
y=3
z=132
Signed Binary Addition
For signed addition, the circuit is exactly the same
However, the interpretation of the bits is different (most significant bit has negative weight)
The interpretation is determined by the way we declare our variables:
1
1 0 0 0 0 0 0 1
+ 0 0 0 0 0 0 1 1
1 0 0 0 0 1 0 0
1
1
2
8
16
4
32
64
128
1
1 0 0 0 0 0 0 1
+ 0 0 0 0 0 0 1 1
1 0 0 0 0 1 0 0
1
1
2
8
16
4
32
64
-128
Unsigned
Signed
x=129
y=3
z=132
x=-127
y=3
z=-124
uint8_t x, y, z;
int8_t x, y, z;
Overflow
8-bit unsigned data can’t hold numbers bigger than 255
Say we add 129 and 131 (answer should be 260)
The answer is 4 (obviously wrong)
A carry has been generated that has nowhere to go
This is one of our status flags (the C flag)
This flag can be used to indicate an error condition
1
1 0 0 0 0 0 0 1
+ 1 0 0 0 0 0 1 1
0 0 0 0 0 1 0 0
1
1
2
8
16
4
32
64
128
Unsigned
x=129
y=131
z=4
C
1
1
Add-with-carry
Suppose we want to use an 8-bit device to add 16-bit numbers
x= 641 = 0b0000001010000001
y=1155 = 0b0000010010000011
The C flag will help us to correctly complete an operation that is too big to fit our ALU in one go
We would first add the bits 7-0
This sets our C status flag to 1
1
1 0 0 0 0 0 0 1
+ 1 0 0 0 0 0 1 1
0 0 0 0 0 1 0 0
1
x[7-0]
y[7-0]
z[7-0]
C
1
Add-with-carry
Suppose we want to use an 8-bit device to two 16-bit numbers
x= 641 = 0b0000001010000001
y=1155 = 0b0000010010000011
Then we use an operation called add-with-carry to add bits 15-8
This operation uses our C status flag as an input
After completion the C flag is overwritten by the carry output of the new addition (in this case zero)
0 0 0 0 0 0 1 0
+ 0 0 0 0 0 1 0 0
0 0 0 0 0 1 1 1
x[15-8]
y[15-8]
z[15-8]
C
1
1
Add-with-carry
Suppose we want to use an 8-bit device to two 16-bit numbers
x= 641 = 0b0000001010000001
y=1155 = 0b0000010010000011
Then we use an operation called add-with-carry to add bits 15-8
This operation uses our C status flag as an input
After completion the C flag is overwritten by the carry output of the new addition (in this case zero)
0 0 0 0 0 0 1 0
+ 0 0 0 0 0 1 0 0
0 0 0 0 0 1 1 1
x[15-8]
y[15-8]
z[15-8]
C
0
Overall answer
=0b000011100000100
=1796
16 bit addition using an 8-bit adder
Interpreting the C-Flag
C flag has two possible purposes:
If we are adding 8-bit numbers the flag gives us a way to check if an error has been made and a result is wrong
If we are adding 8-bit slices of a 16 or 32-bit number, the C flag feeds information between the slices to enable us to computer the correct result
0 0 0 0 0 0 1 0
+ 0 0 0 0 0 1 0 0
0 0 0 0 0 1 1 1
x[15-8]
y[15-8]
z[15-8]
C
0
1
Overall answer
=0b000011100000100
=1796
16 bit addition using an 8-bit adder
Overflow for Signed Numbers
Overflow occurs when a number cannot be represented in the available bits
8-bit unsigned data can represent range 0 to 255
8-bit signed data can represent range -128 to +127
Their overflow conditions are different
Here is an example:
x=254
y=6
z=4
1 1 1 1 1 1 1 0
+ 0 0 0 0 0 1 1 0
0 0 0 0 0 1 0 0
1
2
8
16
4
32
64
128
Unsigned
C
1
x= -2
y=+6
z=+4
1 1 1 1 1 1 1 0
+ 0 0 0 0 0 1 1 0
0 0 0 0 0 1 0 0
1
2
8
16
4
32
64
-128
Signed
C
1
Overflow for Signed Numbers
The C-flag is 1
This shows the result is wrong if x, y, z are declared as uint8_t
However, if x, y, z are declared as int8_t int the result is fine
1 1 1 1 1 1 1 0
+ 0 0 0 0 0 1 1 0
0 0 0 0 0 1 0 0
1
2
8
16
4
32
64
128
Unsigned
x=254
y=6
z=4
C
1
1 1 1 1 1 1 1 0
+ 0 0 0 0 0 1 1 0
0 0 0 0 0 1 0 0
1
2
8
16
4
32
64
-128
Signed
x= -2
y=+6
z=+4
C
1
Overflow for Signed Numbers
Here is an example that is OK for unsigned int
It will cause a problem for signed int
The problem manifests when
Both inputs are positive and the result is negative
Both inputs are negative and the result is positive
x=127
y=1
z=128
x=+127
y=+1
z=-128
0 1 1 1 1 1 1 1
+ 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0
1
2
8
16
4
32
64
-128
Signed
C
0
0 1 1 1 1 1 1 1
+ 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0
1
2
8
16
4
32
64
128
Unsigned
C
0
Overflow for Signed Numbers
Here is an example that is OK for unsigned int
It will cause a problem for signed int
The problem manifests when
Both inputs are positive and the result is negative
Both inputs are negative and the result is positive
This result is another status flag
The V flag (signed oVerflow)
0 1 1 1 1 1 1 1
+ 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0
1
2
8
16
4
32
64
-128
Signed
x=+127
y=+1
z=-128
C
0
1
1
1
1
1
1
1
Status Flags
For this example, the resulting status flags would be
C=0 (the computation did not generate a carry)
V=1 (the correct 2s complement result was unrepresentable)
N=1 (the result had a 1 in its most-significant bit)
Z=0 (the result was non-zero)
0 1 1 1 1 1 1 1
+ 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0
1
2
8
16
4
32
64
-128
Signed
x=+127
y=+1
z=-128
C
0
1
1
1
1
1
1
1
Summary
ALU performs arithmetic and logical operations
Status flags give us information about the result of the last ALU operation:
Can be used to detect overflow/underflow error conditions
Can be used to permit operations on numbers that have more bits than the ALU can process in one go
/docProps/thumbnail.jpeg