Lab 11 - Microcode and more

Goal

In the last lab we programmed all the microcode EXCEPT for two instructions, the MUL and DIV. We will complete and test those instructions, and also add the ability to have indexed addressing for the LOAD and STORE instructions.

Step 1 - Multiply.

Last week we wrote a multiply in machine code, now we need to write it in micro-code. A tricky aspect is that we must only use resources in the processor, we cannot modify memory in any way.

Consider the following algorithm for multiply:

// Compute ACC <- ACC * MEM(n)
    MAR <-MEM(n)
    B<-ACC
    ACC<-0
    WHILE (MAR > 0) {
          ACC = ACC + B
          MAR--
    }

This skips some of the details, but the idea is to use B and MAR at local temporary registers to store values for the process. Now it may seem odd to use the MAR, but it is in fact just another register, and can be used for something else if we don't need it to access memory.

To Do
  1. Write and test microcode for the multiply instruction.
  2. Include the commented microcode in your lab report
  3. Write and test a program in assembly (and machine code) to compute factorials. Include the source and machine code for this in your lab report.

// Find the Factorial(n)
   ans = 1
   for i = n down to 2 {
     ans = ans * i
   }

Step 2 - Divide.

Next we need to do the divide. This one is a little tricky. It can probably be done in less, but I used 16 micro-instrucitons, and that included branching into the code of some other instructions. For example, you can branch to the end of another instruction, usings it's (PC)++ followed by a fetch, thus using one instruction to get the effect of two. But you are increasing the number of cycles required by adding in the branch.

Since there are only 8 available locations in the ROM set aside for the DIV instruction, we will need to use some of the space not used by other instructions. Also - you may notice that addresses 0x078-0x07F are unused because we are mapping the type 2 instructions (which start with 1111) to addresses at 0x080+. These locations are free for the taking (I used them in my solution)

The general solution for divide is simple, and is shown below:

// Compute Q,R<-X/Y
    Q <- 0                          // Counter for number of subtracts
    Dividend <- X
    IF (Y == 0) {
         R <- 0
         Done
    }
    WHILE ( Dividend > 0) {         // Keep subtracting Y until Dividend <= 0
         Dividend = Dividend - Y     
         Q++
    }
    if (Dividend < 0) {             // If Dividend < 0, Remainder is previous dividend
       R = Dividend + Y
       Q--
    } else {
        R <- 0                      // If Dividend == 0, then remainder is 0
   }

To Do
  1. Write and test microcode for the divide instruction.
  2. Include the commented microcode in your lab report
  3. Write and test a program in assembly (and machine code) to compute the GCD (Greatest Common Denominator) function. Include the source and machine code for this in your lab report. You should have two memory locations that will hold a and b before the program is executed, and and third where the results is placed.

function gcd(a, b)
    while b ≠ 0 {
       t := b
       b := a mod b
       a := t
    }
    return a

Step 3 - Indirect Mode.

This machine lacks an indirect addressing mode. Review what indirect addressing mode is. Your goal is to design, program, and test new versions of LOAD and STORE that can read memory indirectly. Show your microcode. You can call your new instructions LOADI and STOREI.

There are two ways to do this, and each has advantages an disadvantages. You choose!

Register Indirect. In register indirect we use a register as a pointer into memory. We only really have one register that is available, B. So we could have LOADI and STOREI simply use the value in register B as a pointer into memory. Now register B will need to be setup first (using the SWAP instruction, since that is the only way to get to B). So we will need to read an address from memory in to the ACC, then SWAP it into B. Example:

// Code using B as a pointer. 
    LOAD 20 // Mem(20) contains a pointer (an address)  
    SWAP // Put Pointer in B 
N: LOADI // Put indirect value into ACC. (This is just Mem(Mem(20)) = Mem(B) ) 
    .... // Do Stuff
    B++ // point to next value
    BR N // Next 

Memory Indirect. In this case we use a memory location as a point to another location.

N:  LOADI 20 // ACC <-Mem(Mem(20))
     .... // Do Stuff 
     LOAD 20 // Get pointer 
     ACC++ // point to next value 
     STORE 20 // Save back updated pointer 
     BR N // Next 

To Do
  1. Write and test microcode for the LOADI and STOREI instruction.
  2. Include the commented microcode in your lab report
  3. Write and test a program in assembly (and machine code) to compute the sum of an array. Let the first location be the length of the array, and the following words the values to be summed. Include the source and machine code for this in your lab report.
Example Arrays:
7 3 4 0 4 2 6 12

3 4 33 21

Step 4 - Performance enhancement proposal.

This final step is experiment oriented, and is targeted for use in next weeks lab.

Your goal is to propose three distinct modifications to improve the performance of your machine. Your proposed solutions should have the following characteristics:

  1. Be something you can actually implement and test next week.
  2. Have measurable improvement in performance. This should be calculable in terms numbers of machine cycles saved.
The sort of modifications you can consider include:
  1. Modifications to the actual hardware for the machine to speed up existing instructions.
  2. Modifications to the microcode to speed up existing instructions.
  3. Addition of new instructions that will decrease the number of instructions (and thus cycle) needed for typical program.

To Do
  1. Write up an explanation of your proposal. Include a description of the hardware/software changes.
  2. Give an estimate of the improvement the changes will provide.
  3. Prepare a brief (2 minute) presentation on your ideas for presentation in the next Lab.
The must be enough detail in the proposal to demonstrate that the idea has been thoroughly considered, and that there is enough detail to demonstrate that the idea is feasible, and within the scope of complexity to be completable within this course.

*

Topic revision: r9 - 2014-11-19 - JimSkon
 
This site is powered by the TWiki collaboration platformCopyright &© by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback