to be continued
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, 23 April 2007
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment