Microsoft PowerPoint – L3 2021
Week 3
Outline
• Encoding
• Addition of 2’s complement numbers
• Fixed vs floating‐point
• Why floating‐point is a challenging.
• More on encoding symbols
• Memory basics
Two’s complement
• Easy to compute
• Invert all bits and add 1
• Has a direct understanding
• Simpler addition still
Worksheet Q2
28
26
Floating vs Fixed‐point
• Do we need floating‐point to encode real numbers?
• Can we represent natural numbers with fixed point?
• Can we represent integer numbers with fixed point?
Floating vs Fixed‐point
• You have 8 bits. How do you represent numbers between 0 and 63?
• You have 8 bits. How do you numbers between 0 and 126?
• Is 8‐bits sufficient to represent numbers between 0 and 63?
Floating vs Fixed‐point
• You want to represent a wide range with a fixed number of bits?
• Do you need fixed or float?
• What numbers does 8‐bit fixed‐point represent?
Floating vs Fixed‐point
• You want to represent a wide range with a fixed number of bits?
• Do you need fixed or float?
• What numbers does 8‐bit fixed‐point represent?
• Suppose I represent an 8‐bit number that lies in the range [‐2, 2] in fixed‐
point. What does that mean?
Floating‐point
• Reason: You want to represent a variable range with a fixed number
of bits
Floating‐point (example)
• Reason: You want to represent a variable range with a fixed number
of bits
• Example:
• Your memory can store 16 bits.
• Your algorithm involves some calculations with many variables
• Variables include numbers as large as 30000.
• Your algorithm has an exit condition var1‐var2>1e‐6
• You need more fixed‐point bits than you can handle
Bisection algorithm
Fixed vs Float
Overflow
5 bit fixed point, 2 bits integer, 3 bits fractional
Roundoff
Number system must not overflow (error unbounded)
Accumulation of round‐off errors must lie below tolerable region
5 bit floating point, 2 bits exponent, 3 bits mantissa
m
e bbbx ….02 21 }1,0{, ib
Fixed vs floating point
• Fixed point:
• Number system must not overflow (error unbounded)
• Accumulation of round‐off errors must lie below tolerable region
• Floating‐point similarities:
• Number system must not overflow
• Accumulation of round‐off errors must lie below tolerable region
• Differences:
• Bigger dynamic range
• Underflow
• Size of roundoff errors vary relative to the representable value
• Floating point is not associative
Is floating‐point good?
Important to remember
• Floating point needs its representation defined
• E.g. IEEE Floating‐point does not correspond to majority of notes
• Need to be able to be flexible
Notes vs IEEE 754 Standard Floating Point
• Single precision:
• Double precision
Notes vs IEEE 754 Standard Floating Point
• Single precision:
• Half precision
Notes vs IEEE 754 Standard Floating Point
• IEEE standard
• Implicit leading 1
• Special codes:
• NaN (0/0, sqrt(‐10))
• Infinity (100/0, ‐100/0)
• Exponent subtract a bias (127 for single gives range ‐126 to +127)
Why should I learn custom floating‐point?
Floating‐point practice
• Worksheet Q3
Floating‐point
range/precision/underflow/overflow
• How do you increase range?
• How do you increase precision?
• What is overflow?
• What is underflow?
• Worksheet Q4
Floating‐point games
Floating point is not associative
Which answer is correct?
71
1
e
i
i
Floating point is not associative
How do you add numbers in FP
• Compute 3+0.625
• 3 is 22×0.110
• 0.625 is 20×0.101
• Align exponents
• 3 is 22×0.110
• 0.625 is 22×0.00101
• Perform addition
• 22×0.11101
• Re‐normalise to 5 bits
• 22×0.111 = 3.5
• Roundoff error of 0.125
• Compute 3.5+0.875.
• 3.5is 22×0.111
• 0.875 is 20×0.111
• Align exponents
• 3.5 is 22×0.111
• 0.875 is 22×0.00111
• Perform addition
• 22×1.00011
• Re‐normalise to 5 bits
• 23×0.100 = 4
• Roundoff error of 0.375
m
e bbbx ….02 21
Evaluate 3+0.625+0.875, with 3 bit mantissa
How do you add numbers in FP
• Compute 0.625+0.875
• 0.625 is 20×0.101
• 0.875 is 20×0.111
• Align exponents
• 0.625 is 20×0.101
• 0.875 is 20×0.111
• Perform addition
• 20×1.100
• Re‐normalise to 5 bits
• 21×0.110 = 1.5
• No roundoff error
• Compute 1.5+3
• Result is 21×0.110
• 3 is 22×0.110
• Align exponents
• 3 is 22×0.110
• 0.875 is 22×0.0110
• Perform addition
• 22×1.001
• Re‐normalise to 5 bits
• 23×0.101 = 5
• Roundoff error of 0.5
m
e bbbx ….02 21
Evaluate 0.625+0.875+3, with 3 bit mantissa
Not just round‐off errors can go wrong
12
252
1
25
i
Floating point games
12
252
1
25
i
Encoding symbols
• Why?
• Computers cannot only work with numbers
• How do you encode any set of symbols?
• Need to make a link between binary and a symbol
• First define set
• Work out minimum number of bits
Activity 1
• Benefits of RGB coding
• What is 1110 0010 1101 0100 0000 0101?
• Note: Order matter
Activity 2
Activity 2
• How many combinations can we encode?
Activity 2
• How many combinations can we encode?
• 23 bits ‐> how many: 8million
Activity 2
• How many combinations can we encode?
• 23 bits ‐> how many: 8million
• How many do we need:
• 360*100*100 = 3.6 million
Activity 2
• How many combinations can we encode?
• 23 bits ‐> how many: 8million
• How many do we need:
• 360*100*100 = 3.6 million
• Could we just use 22 bits?
Activity 2
• How many combinations can we encode?
• 23 bits ‐> how many: 8million
• How many do we need:
• 360*100*100 = 3.6 million
• Could we just use 22 bits?
• Hard look‐up table
• Fast encoding/decoding
Activity 2
• How many combinations can we encode?
• 23 bits ‐> how many: 8million
• How many do we need: 360*100*100 = 3.6 million
• Could we just use 22 bits?
Activity 2
• How many combinations can we encode?
• 23 bits ‐> how many: 8million
• How many do we need: 360*100*100 = 3.6 million
• Could we just use 22 bits?
• Why would we not?
• Hard look‐up table
• Simple rules vs efficient rules
• Fast encoding/decoding
Memory
Memory
• Every computer has memory
• What operations does a memory perform
What does a memory conceptually look like
• Cells/number of cells
Memory notation
• What is a Byte?
General notation
• How many grams in a kilogram?
General notation
• How many grams in a kilogram?
• How many metres in a kilometre?
General notation
• How many grams in a kilogram?
• How many metres in a kilometre?
• How many bytes in a kilobyte?
Memory notation
• KB: 2^10 Bytes,
• MB: 2^20 Bytes,
• GB: 2^30 Bytes,
Memory visualisation
• How many cells in a 2GB memory, where each cell is 1 Byte.
Memory visualisation
• How many cells in a 2GB memory, where each cell is 1 Byte.
• 2^30 *2 = 2^31
Memory visualisation
• How many cells in a 2GB memory, where each cell is 2 Bytes.
Memory visualisation
• How many cells in a 2GB memory, where each cell is 2 Bytes.
• 2^30
Memory Read/Write
• If write cell it stays
• If read it, you get it back
Memory Read/Write
• If I write to a cell which already has a value, what happens to that
value
Memory Read/Write
• If I write to a cell which already has a value, what happens to that
value
• Write means overwrite
Memory Read/Write
• Write 4 bits into 8‐bit cell. What happens?
Memory Read/Write
• Write 4 bits into 8‐bit cell. What happens?
• What if you don’t pad the 4‐bits.
• Overwrite 4, keep other
• Remaining 4 unchanged
• Doesn’t write at all
Address
• Every cell in memory must have an address
How does a memory (ROM) work
decoder
0 n-1
Address
2 -1n
0
1 1 1 1
word[i] = 0011
word[j] = 1010
bit lines (normally pulled to 1 through
resistor – selectively connected to 0
by word line controlled switches)
j
i
word lines (only one
is active – decoder is
just right for this)
Address Questions
• How many bytes does a memory with addresses 10 bits, where each
cell is 1 byte have?
Address Questions
• 4GB memory, 2 byte cells. How many cells?
• 2^31
• 10 bit address, 16 bit cell. How many cells?
Address Questions
• 10 bit address, 16 bit cell. How many cells?
Activity 2
How do we store things in memory
• What if I want to store a big thing in memory
How do we store things in memory
• What if I want to store a big thing in memory
• Use cells in consecutive locations (bytes)
• Which order?
• Can a big endian architecture share memory with a little endian
memory
Activity 3
How to store arrays
• What is an array?
How to store arrays
• Suppose it is an array of integers
• A[] = {10, 267, 39, 40}
• How many bits?
• Suppose you have a memory with 1 byte cells. What does it look like?
How to store arrays
• Memory has no notion of size
• It does not know how many bits are the integers
• It does not know they are storing integers
• How to know size of array if stored in memory?
How to store arrays
• Memory has no notion of size
• It does not know how many bits are the integers
• It does not know they are storing integers
• How to know size of array if stored in memory?
• Create a symbol to say end of array
• Typically used for strings (null character)
• Not great for integers (already have a 0)
• Store the size
• First put a number
• Do nothing…
• c
How to find elements in memory
• Address base
• + bytes encoding size
• +3* size of element
• E.g. look up A[5]
• What if look up A[7] in a array declared of size 6.
• First check it legal
• Error message arrayindexoutofbounds
• Does this happen at run‐time or compile time?
How to find elements in memory
• Address base
• + bytes encoding size
• +3* size of element
• E.g. look up A[5]
• What if look up A[7] in a array declared of size 6.
• First check it legal
• Error message arrayindexoutofbounds
• Does this happen at run‐time or compile time?
Activity 4
• Store in little endian
• Assume not storing size
Manipulating addresses ‐ Indirection
• Most commonly used for dynamic memory allocation/call‐by‐
reference or call by value
Why indirection is confusing…
• Multiple indirection. Why?