lecture 6
Memory-Mapped Input and Output
Within SPIM: console and keyboard are using by CPU to communicate with external devices.
Some MIPS addresses are actually device registers
- Console I/O in SPIM
- SPIM emulates MMIO
- Must select ‘Mapped I/O’ in PCSpim settings
- Receiver – keyboard
- Transmitter – display
- Can still use syscalls
Keyboard Input
- Receiver control (at FFFF000016) consists of 2 bits
- Bit 0 is the ‘ready’ bit – unread input from keyboard
- Receiver data (at FFFF000416) contains last pressed key
- Reading data register resets ‘ready’ bit
- Read from control register
- AND off the ‘ready’ bit
- If zero, no keypress
- Keep waiting
- Else read data register
- li $t0, 0xffff0000
- rd poll:
- lw $v0, 0($t0)
- andi $v0, $v0, 0x01
- beq $v0, $zero, rd poll
- lw $v0, 4($t0)
- # last key code in $v0
Character Display
- Transmitter control (at FFFF000816) consists of 2 bits
- Bit 0 is the ‘ready’ bit – display accepting new character
- Transmitter data (at FFFF000C16) takes ASCII character
- Writing data register resets ‘ready’ bit
- Read from control register
- AND off the ‘ready’ bit
- If zero, not ready
- Keep waiting
- Else send to data register
- # character in $a0
- li $t0, 0xffff0008
- wr poll:
- lw $v0, 0($t0)
- andi $v0, $v0, 0x01
- beq $v0, $zero, wr poll
- sw $a0, 4($t0)
half-adder
- S = A &B
- C = A ^ B
Full-Adder
- S = A &B& Cin
- Cout = (A^B)&(B^Cin)&(A^Cin)
Ripple Carry Adder
- A chain of full-adders can sum as many bits as needed
- The Cout of each adder is wired to the Cin of the next
- Present the nth bit of inputs A and B to the nth adder
- Set C0 to 0; carry out C4 indicates overflow
- Calculates S = A + B, where Sn is the nth bit of S. . .
- The carry bits ripples across the full adders
- Simplest, but not the fastest (c.f. carry look-ahead)
Representing Negative Numbers
- Sign and Magnitude :What we use in decimal notation: +/− and 0, 1, 2, · · ·, becide the sign bit, other bits are same for a pair of positive and negative number.
- Ones’ Complement : Represent −x by its bitwise inverse (NOT). the bits are revise between positve and negative number, +0 and -0 are special.
- Excess-n :Zero represented by binary n: 02 is thus −n
- Two’s Complement :For an n-bit number, represent −x by 2n − x
Method of Complements :Subtract each digit of x from b − 1, then add 1 to result
Two’s Complements :In base 2 with n bits, represent −x using 2n − x
But there’s a quicker way to calculate 2n − x:
- Take the bitwise inverse (NOT) of x, then add 1 to result
- Addition as for unsigned numbers; just ignore carry bit
- Conventionally we take the MSB to represent the sign 0 for positive, 1 for negative
Thus n bits can represent from −2n−1 up to 2n−1 − 1
All modern processors primarily use two’s complement
lecture 7
Sign Extension :For a signed byte, copy the MSB (bit 7) 24 times:
lb and lh performs sign extension;
However, add and addi also check for overflow
Overflow when result exceeds −231 _ x <>On overflow, trigger an error exception Try
- li $t0, 0x7fffffff
- addi $t0, $t0, 1
- Checking for Overflow
- addu $s0, $s1, $s2
- xor $t0, $s1, $s2
- blt $t0, $zero, no overflow
- xor $t0, $s0, $s1
- bge $t0, $zero, no overflow
- # we have overflow!
- no overflow: # rest of program
Multiplication Product of m- and n-digit numbers requires m + n digits
n-Bit Binary Multiplication
Slow compared to e.g. addition; takes many cycles Would stall the next instructions in the pipeline Independent unit (from main ALU) for muln and divn Source operands come from the usual register file Results written to two special registers HI and LO
lecture 8
Shifting the Point What is 0.110 in binary? 0.110 = 0.0001001001 . . .2 Digits repeat forever – no exact finite representation!
Use binary scaling: e.g.
- let one increment represent 1/16th Hence,
- 0000.00012 = 1 _= 1/16 = 0.0625
- 0001.10002 = 24 _= 24/16 = 1.5 Fixed Point Arithmetic
Fixed position for binary point Addition same as integers: a/c + b/c = (a + b)/c
Multiplication mostly unchanged, but must scale after
a b
- * - =(a × b)/c
c c
e.g. 1.5 × 2.5 = 3.75
0001.10002 × 0010.10002 = 0011.1100 00002
Scientific Notation
- General form ±m × be where
- The mantissa contains a decimal point
- The exponent is an integer e 2 Z
- The base can be any positive integer b 2 N_
- A number is normalised when 1 _ m < 0016 =" 0" 6=" 0" ff16 =" 0" 6=" 0"> largest representable number
- Alternative is to give a wrong value, or raise an exception
- Overflow gives ±1 (underflow gives denormalised)
- In long computations, only a few results may be wrong
- Raising exceptions would abort entire process
- Giving a misleading result is just plain dangerous
- Infinities and NaN propagate through calculations, e.g. 1 + (1 ÷ 0) = 1 +1 = 1 ; (0 ÷ 0) + 1 = NaN + 1 = NaN
lecture 9
Floating Point Addition
- Suppose f0 = m0 × 2e0 and f1 = m1 × 2e1
- Then f0 × f1 = m0 × m1 × 2e0+e1
- Shift the smaller number right until exponents match
- Add/subtract the mantissas, depending on sign
- Normalise the sum by adjusting exponent
- Check for overflow
- Round to available bits
- Result may need further normalisation; if so, goto step 3
- 1 Add the exponents (be careful, excess-n encoding!)
- 2 Multiply the mantissas, setting the sign of the product
- 3 Normalise the product by adjusting exponent
- 4 Check for overflow
- 5 Round to available bits
- 6 Result may need further normalisation; if so, goto step 3
IEEE 754 Rounding
Hardware needs two extra bits (round, guard) for rounding
IEEE 754 defines four rounding modes
- Round Up Always toward +1 Round Down Always toward −1 Towards Zero Round
- down if positive, up if negative
- Round to Even Rounds to nearest even value: in a tie, pick the closest ‘even’ number: e.g. 1.5 rounds to 2.0, but 4.5 rounds to 4.0
Here be Dragons
Cannot rely on e.g. (a + b) + c = a + (b + c)
e.g. calculate 1 + 1020 − 1020 on a computer
Absolute and Relative Error
- We wish to represent some given some number m
- Its IEEE 754 representation is n – an approximation
- The absolute error is defined to be
- a = |m − n|
- The relative error is defined as
- r = |m − n|/n
- m The true value of n lies within the ranges
- n ± a = [n − a, n + a], or
- n(1 ± r ) = [n(1 − r ), n(1 + r )]
Error Propagation
- Addition or subtraction sums absolute error of operands (x ± ax ) + (y ± ay ) = (x + y) ± (ax + ay )
- When x _ −y, the error can be as large as the result
- Multiplication or division sums relative error of operands : x(1 ± rx ) × y(1 ± ry ) = (x × y)(1 ± (rx + ry ) ± rx*ry ) We can ignore the much smaller rx*ry term
Example: given the relative error of x, y and z,
- what is the absolute error in the expression y2 − 4xz?
- y2(1 ± 2ry ) − 4xz(1 ± (rx + rz )) = (y2 − 4xz) ± (2y2ry + 4xz(rx + rz ))
No comments:
Post a Comment