Victor's CS Site [ CDA3100 ]

MIPS Quick Tutorial
MIPS32 Reference Sheet
MIPS and SPIM Tutorial (University of Arizona)
MIPS Instruction Format Reference
MIPS Programming Guide
MIPS Comprehensive Reference Sheet (University of Massachusetts)
Translating C to MIPS Examples
MIPS Code Examples
MIPS Arrays and Bubble Sort Examples
MIPS Pipelining Intro (University of Iowa)
Assemblers, Linkers, and SPIM Tutorial (HP)
Procedure Call Explanation
Sample Procedure Call Assembly
MIPS Instruction Reference

Intro to Logic Gates and Functions
Digital Logic Design Slides (Nanyang Tech)
Intro to Combinational Circtuits
Intro to Sequential Circtuits
Boolean Algebra Examples

The CPU's primary purpose is executing machine instructions.

Control Unit: The control unit is a component of a computer's central processing unit (CPU) that directs operation of the processor. It tells the computer's memory, arithmetic/logic unit and input and output devices how to respond to a program's instructions.

Datapath: The datapath is a collection of functional units, such as arithmetic logic units or multipliers, that perform data processing operations.

A compiler.

They usually translate higher level languages into lower level languages, like C++ to MIPS assembly code.

Clock rate and clock period are inverses of one another. So we're converting cycles/seconds to seconds/cycle.

1/(1.7*10⁹) = 588*10^-12 = 588 ps

1. Execution Time = instruction_count * CPI * clock period

2. 10,000 * 2 * (1/(2*10⁹))
  = 10,000 * 2 * 0.5/10⁹
  = 10⁴/10⁹
  = 10^-5 seconds
  = 10 microseconds

1. Speedup = T_old/T_new

T represents the amount of time to execute some program.

2. 20/5 = 4 times faster

1. Parallel Speedup = T₁/T_P, where P is the number of processors.

2. Amdahl's Law states that the maximum speedup attainable by improvement in the execution of a program is limited by the fraction of the program that doesn't benefit from the improvement.

It is formulated as:

  Speedup = T_old/T_new
  T_old/T_new = 1/(Fraction_unimproved + (Fraction_improved/Speedup_improved))

3. No. In terms of improvement from parallelization, Amdahl's Law states that speedup is limited by the sequential component of the program. So if a program executes in 3 hours, and 1 hour is spent executing sequential code, whereas the other 2 are spent executing code that can be parallelized, then we can't reduce the execution time of the program below 1 hour by adding more processors to the task.

1. 123₁₀ can be converted to binary by repeated division by two and noting the remainder at each step:

  123/2 = 61 R1
  61/2 = 30 R1
  30/2 = 15 R0
  15/2 = 7 R1
  7/2 = 3 R1
  3/2 = 1 R1
  1/2 = 0 R1

Then place the remainder of each division step, starting at the top, into a binary digit, starting at the least significant position. If we're using a Little Endian 8-bit representation and assuming byte addresses increase to the left, this would be:

  0111 1011 = 123₁₀

2. 100111001101₂ to decimal:

  2⁰ = 1
  2² = 4
  2³ = 8
  2⁶ = 64
  2⁷ = 128
  2⁸ = 256
  2¹¹ = 2048

Add them together to get:

  100111001101₂ = 2509

3. 345₈ = 3*8² + 4*8¹ + 5*8⁰ = 229

4. F1C4₁₆ = 15*16³ + 1*16² + 12*16¹ + 4*16⁰ = 61892₁₀.

5. To convert ABCD₁₆ to binary note that 4 bits are required to represent each hex digit:

  ABCD₁₆ = 1010 1011 1100 1101

1. Basically, it simplifies the work the hardware has to do when handling operations involving signed integers.

For an example of this, consider using a simple binary magnitude representation:

Then an operation like 4+(-2) in binary would yield:

  0100 + 1010 = 1110 = -6

So the hardware would actually have to check for signed integers and handle them in a different way.

However, using the two's complement version of -2 we get:

  0100 + 1110 = 0010 = 2

which is what we expect for 4+(-2).

Also, consider that extending an integer in binary to fill more bits is easier using two's complement, since we merely extend the sign bit to fill the new bit locations, whereas using binary magnitude representation would have required that only the left-most bit match the sign bit.

2. It is called “two’s complement” because to negate an integer, you subtract it from 2^N. It's actually a radix complement where the radix is 2.

  For example, to get -2 in two's complement using 4 bits:

    2⁴ - 2 = 14 = 1110 = -2 in two's complement

Note: The radix is the number of unique digits, including zero, used to represent numbers in a positional numeral system.

3 = 0000 0011

1. Set the sign bit to get:

  -3 = 1000 0011

2. Take the complement of the number (i.e., flip all the bits) to get:

  -3 = 1111 1100

3. To get the two's complement, add 1 to the one's complement:

  -3 = 1111 1100 + 1 = 1111 1101

x = 2 = 0000 0010
x = ~2 = 1111 1101 = -3 (in two's complement)

y = 2 = 0000 0010
y = ~2 = 1111 1101 = 253 since y is unsigned

In two steps:

 1011
+1001
-----
10100

10100
+0110
-----
11010

Alternatively, you could just add them all together at the same time. Just remember to carry a 1 for each pair of 1's in a column. If there's an odd number of 1's, there should be a 1 placed in that column as well.

For example, in binary: 1 + 1 + 1 = 11

10101
-1110
-----
0111

Remember, when subtracting 1 from 0, you borrow a 1 from the next column. Also, note that, when borrowing, the subtraction will result in a 1.

For example, in binary: 10 - 1 = 1

This makes sense, since you're borrowing twice the amount the current column represents from the next column. This is because shifting left by one in binary is the same as doubling. After the subtraction, you're left with half the value, which is what the current column represents.

Basically, remember that when borrowing: 0 - 1 = 1.

  1011
  *101
  ----
  1011
 0000
1011
------
110111

		    101
		10|1010
		   10
		    010
		     10
		      0
		

      ---------------------------------------------------
      |  sign  |  exponent  |         mantissa          |
      ---------------------------------------------------
         1 bit      8 bits              23 bits
		

Computed as: sign * 2^exponent * mantissa

The offset of the exponent field is +127. This is to allow for the representation of negative exponents.

For example, if the exponent field contains 100001010, then the exponent is actually:

10001010₂ = 137₁₀
137 - 127 = 10₁₀

So the number would be computed as: sign * 2¹⁰ * mantissa.

First, convert 0xC0EB0000 to binary:

  1100 0000 1110 1011 0000 0000 0000 0000

We know that the IEEE floating point representation uses 1 bit to indicate sign, 8 bits for the exponent, and 23 bits for the mantissa:

  1 10000001 11010110000000000000000

We convert this to decimal by interpreting each field:

• The sign is negative since the sign field is 1.
• The exponent for the binary scientific notation is 2.
• Remember, the exponent field is offset by 127 to accomodate negative values. Since 10000001 = 129 and 129 - 127 = 2, the exponent will be 2.
• We append the mantissa to 1, which is implied in the notation.

Then the final result is:

  -1.1101011 * 2²
  = -(2⁰+2^-1+2^-2+2^-4+2^-6+2^-7)*2²
  = -(2²+2¹+2⁰+2^-2+2^-4+2^-5)
  = -(7+0.34375)
  = -7.34375

First, convert 8.625 to binary:

  8 = 1000

  Convert 0.625:

    0.625 * 2 = 1.25
    0.25 * 2 = 0.50
    0.50 * 2 = 1.0

    Use the whole number part of each result after multiplying by 2:

      0.101 = 0.625

Then 8.625 in binary is:

  1000.101

Convert this number into the mantissa and exponent:

  1000.101 = 1.000101 * 2³

The mantissa is 23 bits long, so we add 17 0's onto the end of the fractional part of 1.000101:

  mantissa = 00010100000000000000000

The exponent is 8 bits long and is offset by +127. So we must add 127 to 3 and that's the number we'll put in the exponent field:

   130 = 10000010

We set the sign bit to 1, since the number is negative.

So, our final result is:

  1 10000010 00010100000000000000000

Program Counter
Register File
Arithmetic-Logic Unit (ALU)

* ALU instructions *

- These instructions take either two registers or a register and a sign-extended immediate (called ALU immediate instructions, they have a 16-bit offset in MIPS), operate on them, and store the result into a third register.

* Loads and Stores *

- These instructions store data from a register to memory, or load data from memory into a register.

- They both take a register source, called the base register, and an immediate field (16-bit in MIPS), called the offset, as operands.

- The sum (called the effective address) of the contents of the base register and the sign-extended offset is used as a memory address.

* Branches and Jumps *

- Branches are conditional transfers of control.

- Jumps are unconditional transfers of control.

- In all RISC architectures, the branch destination is obtained by adding a sign-extended offset (16 bits in MIPS) to the current PC.

		----------------------------------------------
		|  op  |  rs  |  rt  |  rd  | shamnt | funct |
		----------------------------------------------
		  31-26  25-21  20-16  15-11   10-6     5-0
		

		----------------------------------------------
		|  op  |  rs  |  rt  |  rd  | shamnt | funct |
		----------------------------------------------
		  31-26  25-21  20-16  15-11   10-6     5-0
		

The opcode for an ALU operation is 0 in 6 bits: 000000

The three operand fields will be filled by:

  rs: 6 = 00110
  rt: 7 = 00111
  rd: 5 = 00101

The shift amount is 0 in 5 bits: 00000

The funct field for an add is 32: 100000

So altogether the instruction in MIPS binary is:

  000000 00110 00111 00101 00000 100000

32 words, 128 bytes, 1024 bits.

1. The clock period is defined by the longest stage: 305 ps in the IF stage.

   The clock rate is the inverse of the period: 1/(3.05*10^-10) = 3.28 GHz.

2. 1 instruction would need to proceed through all 5 stages of the pipeline:

  305 ps x 5 stages = 1,525 ps or 1.525 x 10^-9 s.

		      slti $t0, $s0, 15
		      beq $t0, $zero, else
		      add $s0, $s0, $s1
		      beq $zero, $zero, exit
		else: sub $s0, $s0, $s1
		exit: addi $s0, $s0, 1
		

7 in binary is 0111.

We need parity bits for each position that is a power of two:

  _ _ 0 _ 1 1 1

Each parity bit calculates the parity for some of the bits in the code word.
The position of the parity bit determines the sequence of bits that it alternately checks and skips:

  Position 1: check 1 bit, skip 1 bit, check 1 bit, skip 1 bit, etc.
    (1,3,5,7,9,11,13,15,...)
  
  Position 2: check 2 bits, skip 2 bits, check 2 bits, skip 2 bits, etc.
    (2,3,6,7,10,11,14,15,...)
  
  Position 4: check 4 bits, skip 4 bits, check 4 bits, skip 4 bits, etc.
    (4,5,6,7,12,13,14,15,20,21,22,23,...)
  
  Position 8: check 8 bits, skip 8 bits, check 8 bits, skip 8 bits, etc.
    (8-15,24-31,40-47,...)

For example, the check for bit position 4 would yield: 1 + 1 + 1 = 3

Since 3 is odd, we must add 1 to make it even, so we put a 1 in position 4:

  _ _ 0 1 1 1 1

Proceeding in like fashion according to the above rules for bit checking we get the following Hamming code:

  0 0 0 1 1 1 1

Let's check the parity bit sums:

  P1: 0 + 1 + 1 + 1 = 3
  P2: 0 + 1 + 1 + 1 = 3
  P4: 1 + 1 + 1 + 1 = 4

Positions 1 and 2 are not even.

We add the positions together to find the bit in error: 1 + 2 = 3

So, if we invert the bit in position 3 we will have a valid code word:

  0001111

The output of a combinational logic circuit depends solely on its inputs. It has no memory.

The output of a sequential logic circuit depends on inputs and the current state. It has memory.

The three inputs are: the first operand bit, the second operand bit, and the carry-in.

The two outputs are: carry-out and sum.

Start at the leftmost input and combine them as you read the circuit from left to right.

We first have an input of B which enters a NOT gate, giving us: ~B

We then OR this with A, giving us: A + ~B

Next we have B and C at the bottom of the circuit. They both enter an OR gate giving us: C + B

Finally, the inputs from the two OR gates enter an AND gate, giving us the expression that represents the circuit:

(A + ~B)(C + B)

~(AB)(~A + B)1  Complement Law
~(AB)(~A + B)  Identity Law
(~A + ~B)(~A + B)  DeMorgan's Law
~A + (~BB)  Distributive Law
~A1  Complement Law
~A  Identity Law