Saturday, 2 June 2007
CSA_第二章节
移位指令(shift)将一个word里面的所有位都往右或往左移, 并在空出来的位上填上0。
我们可以通过使用左移动2位来达到乘4的效果。
slt, 当地一个寄存器中的小于第二个寄存器的值时, 将第三个寄存器中的内容设置为1; 反之为0。
$sp上的栈通过保证被调用者不会再$sp以上来进行保存; $sp本身的保存是通过被调用者将其减去的值从新加上,其他寄存器则通过将他们保存到栈, 再从栈中恢复他们来京星保存。这种动作也保证了调用者在退栈能取到与压栈时存入的相同的值, 因为被调用者能够保证保护了$sp并且因为被调用者还保证不修改栈中的调用者的入口地址, 这些在过程调用时均保存在$sp以上的区域。
mips指令集包括指令load upper immediate(lui)专门用于给寄存器中的常量设置高16位, 允许后续指令设定常量的低16 位。
如果我们使用pc赖作为增加地址的寄存器。 几乎所有的循环和if语句都比216个字符小的多, 所以pc是一个不错的训责
寄存器$at是味汇编器处理大常熟而保留的。
动态连接库(dybamically linked library, DLL), 如果程序不运行, 库历程就不会被连接和加载。
Friday, 25 May 2007
Towers of Hanoi
The puzzle is well known to students of Computer Science since it appears in virtually any introductory text on data structures or algorithms. Its solution touches on two important topics discussed later on:
recursive functions and stacks
recurrence relations
The applet has several controls that allow one to select the number of disks and observe the solution in a Fast or Slow manner. To solve the puzzle drag disks from one peg to another following the rules. You can drop a disk on to a peg when its center is sufficiently close to the center of the peg. The applet expects you to move disks from the leftmost peg to the rightmost peg.
Recursive solution
Let call the three pegs Src (Source), Aux (Auxiliary) and Dst (Destination). To better understand and appreciate the following solution you should try solving the puzzle for small number of disks, say, 2,3, and, perhaps, 4. However one solves the problem, sooner or later the bottom disk will have to be moved from Src to Dst. At this point in time all the remaining disks will have to be stacked in decreasing size order on Aux. After moving the bottom disk from Src to Dst these disks will have to be moved from Aux to Dst. Therefore, for a given number N of disks, the problem appears to be solved if we know how to accomplish the following tasks:
Move the top N-1 disks from Src to Aux (using Dst as an intermediary peg)
Move the bottom disk from Src to Dst
Move N-1 disks from Aux to Dst (using Src as an intermediary peg) Assume there is a function Solve with four arguments - number of disks and three pegs (source, intermediary and destination - in this order). Then the body of the function might look like
>Solve(N, Src, Aux, Dst)
if N is 0
exit
else
Solve(N-1, Src, Dst, Aux)
Move from Src to Dst
Solve(N-1, Aux, Src, Dst)
This actually serves as the definition of the function Solve. The function is recursive in that it calls itself repeatedly with decreasing values of N until a terminating condition (in our case N=0) has been met. To me the sheer simplicity of the solution is breathtaking. For N=3 it translates into
Move from Src to Dst
Move from Src to Aux
Move from Dst to Aux
Move from Src to Dst
Move from Aux to Src
Move from Aux to Dst
Move from Src to Dst
Of course "Move" means moving the topmost disk. For N=4 we get the following sequence
Move from Src to Aux
Move from Src to Dst
Move from Aux to Dst
Move from Src to Aux
Move from Dst to Src
Move from Dst to Aux
Move from Src to Aux
Move from Src to Dst
Move from Aux to Dst
Move from Aux to Src
Move from Dst to Src
Move from Aux to Dst
Move from Src to Aux
Move from Src to Dst
Move from Aux to Dst
Recurrence relations
Let TN be the minimum number of moves needed to solve the puzzle with N disks. From the previous section T3=7 and T4=15. One can easily convince oneself that T2=3 and T1=1. A trained mathematician would also note that T0=0. Now let us try to derive a general formula.
The recursive solution above involves moving twice (N-1) disks from one peg to another and making one additional move in between. It then follows that
TNTN-1+1+TN-1 = 2TN-1+1
The inequality suggests that it might be possible to move N disks with fewer than 2TN-1+1 moves. Which is actually not the case. Indeed, when the time comes to move the bottom disk (N-1) disks will have been moved from Src to Aux in at least TN-1 moves. Since we are trying to use as few steps as possible, we may assume that that portion of the task took exactly TN-1 moves. It takes just one move to move the biggest disk from Src to Dst. One then needs exactly TN-1 more steps to finish the task. Therefore the minimum number of moves needed to solve the puzzle with N disks equals TN-1 + 1 + TN-1 = 2TN-1 + 1 moves.
In other words,
TN = 2TN-1 + 1
Thus we can define the quantity TN as
T0 = 0
TN = 2TN-1 + 1 for N>0
Thus we may compute T1 = 2T0 + 1 = 1, T2 = 2T1 + 1= 3, T3 = 2T2 + 1 = 7 and so on sequentially.
The above expression is known as a recurrence relation which, as you might have noticed, is but a recursive function. TN is defined in terms of only one of its preceding values. Other recurrence relations may be more complicated, for example, f(N) = 2f(N-1) + 3f(N-2). Recurrence relations appear under various guises in numerous branches of Mathematics and applications.
Returning to the definition of TN, define SN = TN + 1. Then S0 = 1 and SN = TN + 1 = (2TN-1 + 1) + 1 = 2TN-1 + 2 = 2(TN-1 + 1) = 2SN-1. Which is to say that SN could be defined as
S0 = 1
SN = 2SN-1 for N>0
The latter is solved easily in the closed (non-recurrent) form SN=2N. Wherefrom
TN = 2N-1 for N0.
Remark 1
The latest implementation of the applet sports a "Suggest move" button that exploits an algorithm devised by Romek Zylla who graciously put up on the Web an explanation of his algorithm. The algorithm actually provides another, a non-recursive solution to the puzzle.
Remark 2
There are quite a few variations on the puzzle. For example, you may want to experiment with its bicolor or 3 colors versions.
Reference
A. Beck, M.N. Bleicher, D. W. Crowe, Excursions into Mathematics, A K Peters, 2000
Thursday, 24 May 2007
dynamic memory allocation
The source code declares a fixed amount of memory. But often as a program runs it requests more memory for data. The operating system finds a block of available memory and allocates it to the program. This is dynamic memory allocation.
Dynamic memory allocation is used in assembly language and high level languages for building data structures. In object oriented languages it is used to get the memory used to construct objects.
there are 232 bytes available in main memory, each one with its own address. Most of these bytes are virtual. They are implemented by the virtual memory system and do not directly correspond to bytes in RAM chips. But to executing programs it looks if all the bytes are present.
Usually, with a multitasking system, the processor is shared among many executing programs. But the operating system makes it appear to each executing program as if it is the only one running on the system. Also, the operating system makes it look to each program as if 231 bytes are there for it alone. (The other half of memory is for the operating system.)
a program running in the bottom half of memory and the operating system in the top half. The operating system divides the memory available to a program into sections. This is not required by hardware, but makes managing computer operations easier. The Text Segment holds the machine language of the program. The Data Segment holds the memory that has been allocated to the program just as it starts. The Stack Segment is for the run-time stack.
Between the data segment and the stack segment there is unallocated memory that is used for growing the stack (shown as the downward-pointing arrow at the top) or for creating dynamic data structures (shown as the upward-pointing arrow at the bottom). Both of these activities occur as the program is running.
The portion of memory above the data segment that has been allocated to data structures is called the heap
Dynamic memory allocation is when an executing program requests that the operating system give it a block of main memory. The program then uses this memory for some purpose. Usually the purpose is to add a node to a data structure. In object oriented languages, dynamic memory allocation is used to get the memory for a new object.
The memory comes from above the static part of the data segment. Programs may request memory and may also return previously dynamically allocated memory. Memory may be returned whenever it is no longer needed. Memory can be returned in any order without any relation to the order in which it was allocated. The heap may develop "holes" where previously allocated memory has been returned between blocks of memory still in use.
A new dynamic request for memory might return a range of addresses out of one of the holes. But it might not use up all the hole, so further dynamic requests might be satisfied out of the original hole. Keeping track of allocated and deallocated memory is complicated. A modern operating system does all this.
A stack is an easily managed structure. Only a few memory addresses are needed to keep track of it. (Some of these addresses are in the stack pointer and in the frame pointer registers.) As a program executes, the stack grows and shrinks as subroutines are called and exited.
The heap is more like a book shelf. Books are constantly being taken off the shelf from various locations, leaving gaps, and then later returned, filling the gaps.
Here is how a SPIM program requests a block of memory from SPIM's heap:
li $a0,xxx # $a0 contains the number of bytes you need.
# This must be a multiple of four.
li $v0,9 # code 9 == allocate memory
syscall # call the service.
# $v0 <-- the address of the first byte
# of the dynamically allocated block
You don't know in advance what range of addresses you will get back for the allocate memory request. The SPIM service returns the first address of a contiguous block with as many bytes as you requested in $a0. (This is similar to a call to malloc() in "C".)
A record is a block of memory that contains several data items. The data may be of several types, say an int followed by a float followed by a short. The language "C" calls this idea a struct (short for "structure"). An big extension of this idea is called an "object". Records are frequently stored in dynamically allocated memory. Say that you had hundreds of data that look like this:
struct
{
int age;
int pay;
int class;
};
This just says that each data item consists of three integers, the age of a person, their pay rate, and their job classification.
Warning: C and C++ compilers are free to rearrange the order of items inside a struct and to do other things for optimization or hardware compatibility. Worse yet, different compilers may do different things. Do not write C programs that make assumptions about the internal structure of a struct.
Here is a program that allocates memory for a struct, then puts data in each field. It then makes a copy of the struct by allocating another block of memory and copying corresponding fields from the first struct to the second struct.
# StructPrint.asm
#
# Allocate memory for a stuct and then initialize it.
# Allocate memory for a second strct and copy data
# from the first into it. Print both structs
.text
.globl main
main:
# create the first stuct
li $v0,9 # allocate memory
li $a0,12 # 12 bytes
syscall # $v0 <-- address
move $s1,$v0 # $s1 first struct
# initialize the first stuct
li $t0,34 # store 34
sw $t0,0($s1) # in age
lw $t0,pay # store 24000
sw $t0,4($s1) # in pay
li $t0,12 # store 12
sw $t0,8($s1) # in class
# create the second stuct
li $v0,9 # allocate memory
li $a0,12 # 12 bytes
syscall # $v0 <-- address
move $s2,$v0 # $s2 second struct
# copy data from first struct to second
lw $t0,0($s1) # copy age from first
sw $t0,0($s2) # to second struct
lw $t0,4($s1) # copy pay from first
sw $t0,4($s2) # to second struct
lw $t0,8($s1) # copy class from first
sw $t0,8($s2) # to second struct
# write out the first struct
move $a0,$s1
jal PStruct
# write out the second struct
move $a0,$s2
jal PStruct
li $v0,10 # return to OS
syscall
.data
pay: .word 24000 # rate of pay, in static memory
.text
# Subroutine PStruct: print a struct
#
# Registers: $a0 --- address of the struct
# $ra --- return address
PStruct:
sub $sp,$sp,4 # push $s0
sw $s0,($sp) # onto the stack
move $s0,$a0 # safe copy of struct address
la $a0,agest # print "age:"
li $v0,4
syscall
lw $a0,0($s0) # print age
li $v0,1
syscall
la $a0,payst # print " pay: "
li $v0,4
syscall
lw $a0,4($s0) # print pay
li $v0,1
syscall
la $a0,classt # print " class: "
li $v0,4
syscall
lw $a0,8($s0) # print class
li $v0,1
syscall
la $a0,lf # end the line
li $v0,4
syscall
add $sp,$sp,4 # restore $s0 of caller
lw $s0,($sp)
jr $ra # return to caller
.data
agest: .asciiz "age: "
payst: .asciiz " pay: "
classt: .asciiz " class: "
lf: .asciiz "\n"
## end of file
Tuesday, 15 May 2007
Lecture 12: Interrupts, Exceptions and I/O
Integer arithmetic overflow – result outside [−231, +231)
Division by zero
Illegal instruction – machine code doesn’t make sense
Address error – access to unaligned address
Bus error – access to non-existent address
syscall instruction – when we need an OS request
brk (breakpoint) instruction – used by debuggers
Can be thought of as a synchronous software interrupt. . .
Interrupts arise from external devices:
Disk read complete (via DMA, say)
Memory error (but only with EEC RAM)
User pressed a key on console
Console ready to display another character
Hardware timer expired
Can be thought of as asynchronous hardware exception
Exception Handlers
Hardware saves current PC in a special register
CPU jumps to an exception handler, which
Saves the current processor state
Take appropriate internal action for an exception, or
Deal with the external source of the interrupt
Restores the previous processor state
Resumes user program execution, if possible
BadVAddr $8 offending memory reference
Count $9 current timer; incremented every 10ms
Compare $11 interrupt when Count = Compare
Status $12 controls which interrupts are enabled
Cause $13 exception type, and pending interrupts
EPC $14 PC where exception/interrupt occured
Interrupt mask which of the 8 interrupts are allowed
User mode not simulated by SPIM; always 1
Exception level automatically set during an exception; prevents handler itself being interrupted
Interrupt enable global interrupt enable (or disable)
Monday, 14 May 2007
Pointers and References, Arrays and Strings,Heap and Memory Management
A reference is essentially an object’s memory address
Variables containing address are often termed ‘pointers’
A pointer can be thought of as a low-level reference
‘Pointer arithmetic’ – e.g. add offsets, indexing
A pointer is just another type, like an int or a float
Everything stored in memory, pointers included, has an
address: another pointer can even point to it
Arrays
Usually a block of consecutive elements in memory
All same size (s bytes); same offset from one to the next
The i th element is at offset i × s bytes from beginning
Looking up an element of the array is termed ‘indexing’
Assembly equivalent of an int[] in Java would be. . .
a consecutive block of word-sized signed integers
represented by its starting address and length
static data: Contents may change, but size and location doesn’t
In Java, "hello" + "world" contatenates two strings, But neither of the original strings are modified. Instead a new string is created on the heap
The heap is a much larger pool of memory than the stack
Java allocates storage on the heap with the new keyword
All Java objects live on the heap; only primitive types –ints, floats, doubles and references – on the stack
Storage allocated on the heap persist across procedures. Caller can’t access stack storage//-----?????????????
Lecture 10: MIPS Procedure Calling Convention and Recursion
procedures or subroutines in imperative languages like C
methods in OO languages like Java
and functions in functional languages such as Haskell
Functions usually return a value; procedures don’t
Procedures can call other procedures; even themselves
What happens when we call a procedure?
Control hands over to the callee; the caller is suspended
Callee performs requested task
Callee returns control to the caller
Calling Procedures in MIPS Assembly
jal label – jump and link
$ra := PC + 4; PC := [label]-----??????????
Calls procedure at address label
jr src – jump register
PC := src
Issuing j $ra is the assembly equivalent of return
Register $ra contains the return address of the caller
Arguments are passed in registers $a0 to $a3
Results are left in registers $v0 and $v1
The Stack
The stack provides last-in, first out (LIFO) storage
Register $sp points to the topmost word on the stack
By convention, the stack grows downwards
Placing words onto the stack is termed pushing
Taking words off the stack is called popping
Calling Convention
Caller
Push any of $a0-3, $v0-1 and $t0-9 needed later
Place arguments in $a0 to $a3, and stack if necessary
Make the call using jal callee; result in $v0 and $v1
Pop saved registers and/or extra arguments off stack
Callee
Push any of $ra, $s0-$s1 that may be overwritten
Perform desired task; place result in $v0 and $v1
Pop above registers off the stack
Return to caller with jr $ra
The main label is just another procedure
Local Variables
Solution: save initial value of $sp in $fp //---------?????????
Hence local variables always have the same $fp-offset
Note callee must preserve previous value of $fp!
Wednesday, 25 April 2007
lecture 7;8;9
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 &amp;amp;amp;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 ))
Monday, 23 April 2007
mips_arithmetic
CHAPTER 8 — Binary Addition and Two's Complement
Here are some details:
usually the operands and the result have a fixed number of bits (usually 8, 16, 32, or 64). These are the sizes that processors use to represent integers.
1. to keep the result the same size as the operands, you may have to include zero bits in some of the leftmost columns.
2. compute the carry-out of the leftmost column, but don't write it as part of the answer (because there is no room if you have a fixed number of bits.)
3. when the operands are represented using the unsigned binary scheme (the base two representation scheme discussed in the last two chapters) a carry-out of 1 from the leftmost column means the sum does not fit into the fixed number of bits. This is called Overflow.
4. when the operands are represented using the two's complement scheme (which will be described at the end of this chapter), then a carry-out of 1 from the leftmost column is not necessarily overflow.
Overflow Detection
The electronic circuits of a computer can easily detect overflow by checking if the carry-out of the leftmost column is a zero or a one. A program might branch to an error handling routine when overflow is detected.
when the "Binary Addition Algorithm" is used with unsigned binary integer representation:The result is CORRECT only if the CARRY OUT of the high order column is ZERO.
Sign-Magnitude Representation
It uses one bit (usually the leftmost) to indicate the sign. "0" indicates a positive integer, and "1" indicates a negative integer. The rest of the bits are used for the magnitude of the number
One pattern corresponds to "minus zero", 1000 0000. Another corresponds to "plus zero", 0000 0000.
This is what is wrong with Roman Numerals: they can represent any positive integer you want, but they are very, very poor when used in computation.
Two's Complement
Start with an N-bit representation of an integer.
To calculate the N-bit representation of the negative integer:
1. Reflect each bit of the bit pattern (change 0 to 1, and 1 to 0).
2. Add one.
here is what is going on: When each bit of a pattern is reflected then the two patterns added together make all 1's.
adding one to this pattern creates a pattern of all zero's:
Three patterns added together result in a zero. If one pattern represents an integer, then the sum of the other two patterns represents the negative of the integer.
pattern + pattern reflected + one = all zeros
pattern + (pattern reflected + one ) = all zeros
pattern + (two's complement of pattern) = all zeros
it looks like +128 and - 128 are represented by the same pattern. This is not good. A non-zero integer and its negative can't both be represented by the same pattern. So +128 can not be represented in eight bits. The maximum positive integer that can be represented in eight bits is 12710. The negative integers -1 .. -12710 also can be represented.Eight bits can represent the numbers
-12810 ... 0 ... +12710.
it is by happy coincidence that the high order bit of a two's complement integer is 0 for positive and 1 for negative. But, to create the two's complement representation of the negative of a number you must "reflect, add one".
to convert N bits of two's complement representation into decimal representation:
1. If the integer is negative, complement it to get a positive integer.
2. Convert (positive) integer to decimal (as usual).
3. If the integer was originally negative, put "-" in front of the decimal representation.
with two's complement representation the result of addition is correct if the carry into the high order column is the same as the carry out of the high order column. The carry can be one or zero. Overflow is detected by comparing two bits, an easy thing to do with electronics
CHAPTER 9 — First SPIM Program
1. Register Display: This shows the contents (bit patterns in hex) of all 32 general purpose registers, the floating point registers, and a few others.
2. Text Display: This shows the assembly language program source, the machine instructions (bit patterns in hex) they correspond to, and the addresses of their memory locations.
3. Data and Stack Display: This shows the sections of MIPS memory that hold ordinary data and data which has been pushed onto a stack.
4. SPIM Messages: This shows messages from the simulator (often error messages).
Text is the name for machine language bit patterns intended for eventual execution. The word "program" is often ambiguous, so "text" is used. "Text" is a machine language program waiting to become part of an executing process.
Character output from the simulated computer is in the SPIM console window, shown as an icon in the picture.
.text is a directive. A directive is a statement that tells the assembler something about what the programmer wants, but does not itself result in any machine instructions. This directive tells the assembler that the following lines are ".text" -- source code for the program.
.globl main is another directive. It says that the identifier main will be used outside of this source file (that is, used "globally") as the label of a particular location in main memory.
The line main: defines a symbolic address (sometimes called a statement label). A symbolic address is a symbol (an identifier) that is the source code name for a location in memory. In this program, main stands for the address of the first machine instruction (which turns out to be 0x00400000). Using a symbolic address is much easier than using a numerical address. With a symbolic address, the programmer refers to memory locations by name and lets the assembler figure out the numerical address.
CHAPTER 10 — A MIPS Programming Model
Memory Model
modern computer systems nearly always use cache and virtual. But our abstract view of memory does not include them. The purpose of virtual memory is to make it appear as if a program has the full address space available. So our programming model has the full address space. The purpose of cache is to transparently speed up memory access. So our programming model does not include cache. Memory in the programming model is as follows:
data:
MIPS memory is an array of 232 bytes. Each byte has a 32-bit address. Each byte can hold an 8-bit pattern, one of the 256 possible 8-bit patterns. The addresses of MIPS main memory range from 0x00000000 to 0xFFFFFFFF.
However, user programs and data are restricted to the first 231 bytes. The last half of the address space is used for the operating system and for specialized purposes.
operation:
The processor chip contains registers, which are electronic components that can store bit patterns. The processor interacts with memory by moving bit patterns between memory and its registers.
• Load: a bit pattern starting at a designated address in memory is copied into a register inside the processor.
• Store: a bit pattern is copied from a processor register to memory at a designated address.
Bit patterns are copied between the memory and the processor in groups of one, two, four, or eight contiguous bytes. When several bytes of memory are used in an operation, only the address of the first byte of the group is specified.
Memory Layout
though the address space is 32 bits, the top addresses from 0x80000000 to 0xFFFFFFFF are not available to user programs. They are used for the operating system and for ROM. When a MIPS chip is used in an embedded controller the control program exists in ROM in this upper half of the address space.
The parts of address space accessible to a user program are divided as follows:
Text Segment: Thisholds the machine language of the user program (the text).
Data Segment: This holds the data that the program operates on. Part of the data is static. This is data that is allocated by the assembler and whose size does not change as a program executes. Values in it do change; "static" means the size in bytes does not change during execution. On top of the static data is the dynamic data. This is data that is allocated and deallocated as the program executes. In "C" dynamic allocation and deallocation is done with malloc() and free().
Stack Segment: At the top of user address space is the stack. With high level languages, local variables and parameters are pushed and popped on the stack as procedures are activated and deactivated.
Registers:
often data consist of several contiguous bytes. Each computer manufacturer has its own idea of what to call groupings larger than a byte. The following is used for MIPS chips.
• byte — eight bits.
• word — four bytes, 32 bits.
• double word — eight bytes, 64 bits.
A block of contiguous memory is referred to by the address of its first byte (ie. the byte with the lowest address.) Most MIPS instructions involve a fixed number of bytes.
Often you need a number of bits other than one of the standard amounts. Use the next largest standard amount, and remember to be careful. Attempting to use the very minimum number of bits is more complicated than it is worth and is a rich source of errors in assembly language programming.
register is a part of the processor that can hold a bit pattern. On the MIPS, a register holds 32 bits. There are many registers in the processor, but only some of them are visible in assembly language. The others are used by the processor in carrying out its operations.
• A load operation copies a bit pattern from memory into a register.
• A store operation copies a bit pattern from a register into memory.
The registers that are visible in assembly language are called general purpose registers and floating point registers. There are 32 general purpose registers. Each general purpose register holds a 32 bit pattern. In assembly language, these registers are named $0, $1, $2, ... , $31. There are 32 floating point registers. These are discussed in a later chapter.
One of the general purpose registers is hard-wired to always contain the value 0x00000000 (all zero bits).
the arithmetic/logic unit (ALU) of a processor performs integer arithmetic and logical operations. For example, one of its operations is to add two 32-bit integers. An integer used as input to an operation is called an operand. One operand for the ALU is always contained in a register. The other operand may be in a register or may be part of the machine instruction itself. The result of the operation is put into a general purpose register.
Machine instructions that use the ALU specify four things:
As execution proceeds through a list of instructions, a special register, the program counter, points at the instruction that is next in line to execute.
Fetch the next Instruction. The program counter contains the address of the next machine instruction. The instruction is fetched from memory.
Increment the PC. The address in the program counter is incremented by four.
Execute the Instruction. The machine operation specified by the instruction is performed.
CHAPTER 11 — Immediate Operands and Bitwise Logic
General OR Immediate Instruction
here is a description of the ori instruction used as a bitwise OR instruction:
ori d,s,const # register d <-- bitwise OR of const
# with the contents of register $s
# const is 16-bits, so
# 0x0000 ... const ... 0xFFFF
The parts of the instruction must appear in the correct order, and const must be within the specified range. If the immediate operand in the assembly language shows less than 16 bits (as does 0x2 in the previous example) then the assembler expands it to the required sixteen bits. If the assembly language specifies more than sixteen bits, then the assembler writes an error
message.
CHAPTER 12 — Shift Instructions and Logic Instructions
Shifting in Place
hen an ALU operation is performed: (1) data is copied from the register(s) into the ALU. Then (2), the ALU does the operation. Next (3) the result is written to the designated result register. There is no problem when an operand register is also the result register because the operand data was transferred to the ALU in the first step, leaving the register open to receive the result.
No-Op
A machine instruction that does nothing is called (in official computer science jargon) a no-op. The no operation instruction is surprisingly useful, especially for MIPS.
CHAPTER 14 — Integer Multiplication, Division and Arithmetic Shift Instructions
he product of two N-place decimal integers may need 2N places. This is true for numbers expressed in any base. In particular, the product of two integers expressed with N-bit binary may need 2N bits.
MIPS Multiply Unit
he multiply unit of MIPS contains two 32-bit registers called hi and lo. These are not general purpose registers. When two 32-bit operands are multiplied, hi and lo hold the 64 bits of the result. Bits 32 through 63 are in hi and bits 0 through 31 are in lo.
mult s,t # hilo <-- $s * $t. two's comp operands multu s,t # hilo <-- $s * $t. unsigned operands add and addu perform the same operation. The "u" means "don't trap overflow". With mult and multu, different operations are carried out. Neither instruction ever causes a trap.
The significant bits in a positive or unsigned number represented in binary are the most significant 1 bit (the leftmost 1 bit) and all bits to the right of it. For example, the following has 23 significant bits: 0000 0000 0100 0011 0101 0110 1101 1110
The significant bits in a negative number represented in two's complement are the most significant 0 bit (the leftmost 0 bit) and all bits to the right of it. For example, the following has 23 significant bits: 1111 1111 1011 1100 1010 1001 0010 0010
To ensure that a product has no more than 32 significant bits, ensure that the sum of the number of significant bits in each operand is 32 or less. For the programming in this course you will not need to be careful about this.
The mfhi and mflo Instructions
here are two instructions that move the result of a multiplication into a general purpose register: mfhi d # d <-- hi. Move From Hi mflo d # d <-- lo. Move From Lo The hi and lo registers cannot be used with any of the other arithmetic or logic instructions. If you want to do something with a product, it must first be moved to a general purpose register. However there is a further complication on MIPS hardware:
Rule: Do not use a multiply or a divide instruction within two instructions after mflo or mfhi. The reason for this involves the way the MIPS pipeline works. On the SPIM simulator this rule does not matter.
The div and the divu Instructions
ith N-digit integer division there are two results, an N-digit quotient and an N-digit remainder. With 32-bit operands there will be (in general) two 32-bit results. MIPS uses the hi and lo registers for the results:
The sra Instruction
Sometimes you need to divide by two. This instruction is faster and more convenient than the div instruction.
CHAPTER 15 — Memory Access Instructions
he operands for all arithmetic and logic operations are contained in registers. To operate on data in main memory, the data is first copied into registers. A load operation copies data from main memory into a register. A store operation copies data from a register into main memory .
When a word (4-bytes) is loaded or stored the memory address must be a multiple of four. This is called an alignment restriction. Addresses that are a multiple of four are called word aligned. This restriction makes the hardware simpler and faster.
Big Endian and Little Endian
load word or store word instruction uses only one memory address. The lowest address of the four bytes is used for the address of a block of four contiguous bytes.
Big Endian Byte Order: The most significant byte (the "big end") of the data is placed at the byte with the lowest address. The rest of the data is placed in order in the next three bytes in memory.
Little Endian Byte Order: The least significant byte (the "little end") of the data is placed at the byte with the lowest address. The rest of the data is placed in order in the next three bytes in memory.
Intel 80x86: little-endian.
Macintosh: big-endian.
MIPS Addresses
An instruction that refers to memory uses a base register and an offset. The base register is a general purpose register that contains a 32-bit address. The offset is a 16-bit signed integer contained in the instruction. The sum of the address in the base register with the (sign-extended) offset forms the memory address.
CHAPTER 16 — More Memory Access
CHAPTER 29 — Binary Fractions
Limited Precision
The important point of all this is that on the number line from zero to 15.9375 not all real numbers can be represented. This is called a limit in precision. Floating point representation has the same problem.
Converting Representation from Decimal to Binary
To convert a decimal fraction to Base 2: Repeatedly multiply the decimal fraction by two. After each multiplication, copy the bit (0 or 1) that moves into the one's place (the place just left of the radix point) to the right of the binary fraction, then erase it from the decimal fraction. Stop when the decimal fraction is zero. (Note: if this never happens, stop when you have enough bits in the binary fraction.)
CHAPTER 30 — IEEE 754 Floating Point
Scientific Notation
10+n means move the decimal point n places right.
10-n means move the decimal point n places left.
IEEE 754 Floating Point
Bits 0 through 22 are for the mantissa; bits 23 through 30 are for the exponent; and bit 31 is the sign bit. The mantissa and exponent fields work like the similar parts in scientific notation (details follow). The sign bit gives the sign of the entire expression: a 0 bit means positive and a 1 bit means negative.
Very tricky: The mantissa represents the 23-bit binary fraction part of a 24-bit number that starts with a "1". The 20 place (the one's place) is presumed to contain a 1 and is not present in the mantissa. This trick gives us 24 bits of precision with only 23 bits.
The Exponent
The exponent is expressed using a biased integer. The true exponent is added to +12710 resulting in an unsigned binary integer. The biased integer is encoded using 8-bit unsigned binary.
A biased exponent of +127 represents the actual exponent 0.
A biased exponent of +128 represents the actual exponent 1.
A biased exponent of +126 represents the actual exponent -1.
Exceptions: (1) A floating point value of 0.0 is represented with a mantissa of 23 zero bits and an exponent of 8 zero bits. It is not legal to have an exponent of zero with a non-zero mantissa. (2) The exponent 25510 (1111 1111) is used to signal various problems, such as division by zero.
Float Formula
ere is a formula that summarizes the past several pages. In it, s is the sign bit (0 or 1), M is the mantissa (000...000 to 1111...111) and E is the biased exponent. value = (-1)s × 1.M × 2E-127
To convert a paper-and-pencil number into IEEE floating point, fill in each piece of the picture. Let us represent 1.0 as a 32-bit IEEE 754 float.
CHAPTER 31 — Floating Point Arithmetic on MIPS
MIPS Floating Point
Floating point on MIPS was originally done in a separate chip called coprocessor 1 (also called the FPA for Floating Point Accelerator). Modern MIPS chips include floating point operations on the main processor chip. But the instructions sometimes act as if there were still a separate chip.
MIPS has 32 single precision (32 bit) floating point registers.
The registers are named $f0 – $f31
$f0 is not special (it can hold any bit pattern, not just zero).
Single precision floating point load, store, arithmetic, and other instructions work with these registers.
Because floating point zero has the same representation as integer zero, 32 zero-bits. Register $0 works as a floating point zero as well as an integer zero.
Double Precision
MIPS also has hardware for double precision (64 bit) floating point operations. For this, it uses pairs of single precision registers to hold operands. There are 16 pairs, named $f0, $f2, — $f30. Only the even numbered register is specified in a double precision instruction; the odd numbered register of the pair is included automatically.
Some MIPS processors allow only even-numbered registers ($f0, $f2,...) for single precision instructions. However SPIM allows all 32 registers in single precision instructions. These notes follow that usage.
Full-Word Aligned
However, if you want to perform floating point arithmetic, then the floating point number must be in a floating point register
Floating Point Services
To print a floating point value to the SPIM monitor, use service 2 (for single precision) or service 3 (for double precision). To read a floating point value from the user, use service 6 (for single precision) or service 7 (for double precision). These notes deal mostly with single precision.
Compilers that keep track of the data types of values and that make sure that the correct types are used as arguments do strong type checking. Java is strongly typed. In assembly language type checking is largely absent.
Data Movement
CHAPTER 32 — Floating Point Comparison Instructions
Comparison Instructions
Testing if two floating point numbers are exactly equal is sometimes NOT a good idea. Floating point calculations are not exact. Sometimes values are not equal even though mathematically they should be. It is best to use "less than" or "less than or equal" instead of testing for exact equality. Here are some MIPS comparison instructions for single precision floating point:
Branch Instructions
The floating point branch instructions inspect the condition bit in the coprocessor. The bc1t instruction takes the branch if the bit is true (==1). The bc1f instruction takes the branch if the bit is false (==0). These are the only two floating point branch instructions.
The branch instructions have a one instruction branch delay. Hardware requires a nop instruction after each branch instruction. For this chapter, let us not bother with this. When running the programs with SPIM, disable branch delays in the settings menu
Newton's Method
Newton's method is a common way to compute the square root of a number. Say that n is the number and that x is an approximation to the square root of n. Then: x' =(1/2)(x + n/x)
x' is an even better approximation to the square root. The reasons for this are buried in your calculus book (which you, perhaps, have buried in the darkest corner of your basement). But, to make the formula plausible, look what happens if the approximation x happens to be exactly the square root. In other words, what if x = n0.5. Then: x' = (1/2)(x + n/x) = (1/2)( n0.5 + n/n0.5 )
= (1/2)(n0.5 + n0.5) = n0.5
If x gets the exact value, it stays fixed at that value.
Ending Test
But, due to the lack of precision with floating point, the best we can hope for is to calculate an x such that: 0.999999 <>The left and the right bound in the above have 6 decimal digits of precision. If 1.00000 is subtracted from this value the result is: -0.000001 <>To be safe, terminate the loop when: n/x*x - 1 <>
Monday, 16 April 2007
convention_c_code_and_mips_code
Cconvention_c_code_and_mips_code.doc