CDA4101, Problem Set 1

A high-speed 8088 might have acheived 1 MIPS. An earlier Core i7 might have acheived 100,000 MIPS. Refer to Instructions Per Second for a discussion on MIPS.
- Assume that an ISA level instrcution on the 8088 is interpreted to 3 instructions at the hardware level, on average.
- Assume that an ISA level instrcution on the Core i7 is interpreted to 5 instructions at the hardware level, on average.
The Core i7 can simulate the 8088 instruction set. Assume that each ISA level instruction from the 8088 can be interpreted to 2 ISA level instructions on the Core i7.
1. How many milliseconds would it take to run 1,000,000 8088-ISA level instructions on this 8088?
2. How many milliseconds would it take to run 1,000,000 Core i7 instructions on this Core i7?
3. How many milliseconds would it take to run 1,000,000 8088-ISA level instructions on this Core i7?
4. The 8088 was a dedicated machine for its ISA. The Core i7 can interpret the 8088 ISA. Is a hardware implementation always faster than a software implementation?
Identify the computer:
1. First Intel computer with a single, five-stage pipeline
2. First Intel computer with a dual, five-stage pipeline
3. First Intel computer with a superscalar pipeline
4. First product line developed as a family.
5. Computer that marked the start of modern computer history.
6. First vector computer.
7. First commercial RISC machine
8. First computer with a bus for I/O
9. First dual-core chip.
Implement the Interp function from class. The main program has been given already, write all the missing routines. I have modified the code a little from the example from class. The find_data returns the location of the data, not the data. This allows more flexibility.
```
    int PC;
    int ACC;
    int instr;
    int instr_type;
    int data_loc;
    int data;
    boolean run_bit = true;
    
    public void Interp(int starting_address) {
        PC = starting_address;
        while (run_bit) {
            instr = memory[PC];
            PC = (int) (PC + 1);
            instr_type = get_instr_type(instr);
            data_loc = find_data(instr, instr_type);
            execute(instr_type, data_loc);
        }
    }
```
If you already have an idea of how to implement this, then use your idea. If you are stuck, here are a few suggestions for a simple architecture.
- Have a limited number of instructions, like: ADD, SUB, LOAD, STORE, LOAD_CONSTANT, HALT.
- Use bit patterns for each instruction, not symbols like above.
- Decide on an 8-bit instruction.
- With six instructions, you will need three bits to represent all the above operations. You could add two more instructions and not need an additional bit for the operation part of the instruction.
- Use the remaining number of bits to address memory. So, memory will 32 bytes, since five bits are left in the instruction to address memory.
- Most instructions use the accumulator. The only ones that don't are HALT and LOAD_CONSTANT.
  - The add instruction adds a value from a memory location to the accumulator.
  - The sub instruction subtracts a value from a memory location from the accumulator.
  - The load instruction reads a memory location and places it in the accumulator.
  - The store instruction saves the accumulator to a memory location.
  - The load_constant instruction treats the address portion of the instruction as a constant to be loaded into the accumulator. It does not access memory.
  - The halt instruction sets the run bit to false and should be the last instruction in a program.
A program can be as simple as:
- load a constant into the accumulator
- store the accumulator to a memory location
- load another constant into the accumulator
- add the stored memory location to the accumulator
- store the accumulator to another memory location
- halt
After the program is interpretted, display the contents of the 32 bytes of memory, to see if your program worked.
Each stage in a five-stage pipleline executes in one cycle. How many cycles will it take to process 100 instructions from the moment that the first instruction enters the pipeline to the moment the last instruction leaves the pipeline?
Suppose it takes 100 nsec to access RAM, 60 nsec to access L2 cache, and 10 nsec to access L1 cache. If L1 cache has a hit rate of 60% and L2 has a hit rate of 80%, what is the average access time to retrieve data from memory?
Consider a student record with name, age, and major number. The name is Pat Adams, the age is 19, the major number is 2022. Show how the data would be stored in a memory system that has 4-byte words as follows. Draw the memory as a linear array of bytes, not as a table. Store numbers in hex.
1. Store the data using Big Endian
2. Store the data using Little Endian
An array has 100 integers. Addition takes one cycle.
1. How many cycles are needed to add seven to each element in the array on a multiprocessor with four cores?
2. The partial-sum array for an array is another array that contains the sum of the elements in the array, up to each index. The first element is the first element of the original array, the second element is the sum of the first two elements in the original array, etc. How many cycles are needed to create the partial-sum array on a multiprocessor with four cores?
Here are two Boolean formulas.
```
      A OR B
      (A OR B)C OR (A OR B)(NOT C)
```
1. Prove whether or not these equations are equivalent by using truth tables. Do not simplify the expressions.
2. Prove whether or not these equations are equivalent by using Boolean logic to simplify one formula to the other.
Truth tables and Boolean formulas.
1. Create a truth table for a circuit that is one when the parity of its three inputs is even.
2. Write a Boolean formula as a sum of products that represents the truth table for the circuit.
Consider the three input boolean function that is a 1 if the binary equivalent of the inputs is 0, 2, 3, 6, 7.
- Draw a circuit diagram for this function using only 2-input NOR gates.
- Draw a circuit diagram for this function using the MSI multiplexer chip in the Multiplexers section of the book. Do not draw the inside of the multiplexer.
A 2-bit encoder is a circuit with four input lines, exactly one of which is high at every instant, and two output lines whose 2-bit binary value tells which input is high. Only one of the input lines will ever be active at the same time. You do not have to consider the cases if more than one is active.
1. Draw the truth table for a 2-bit encoder. There will be four input variables and two output variables. Only one of the input variables can be 1 at a given time, so there are only 4 possible combinations for valid input variables.
2. Draw the circuit for the 2-bit encoder.
3. Draw the circuit for a 3-bit encoder. There will be 8 input lines and 3 output lines.
A 2-bit demultiplexer is a circuit with one input line, two control lines and four output lines. The input line will appear on one of the output lines based on the control lines. Draw the circuit for a 2-bit demultiplexer.
The shifter from the book only has two functions: logical shift right and logical shift left. Create a new circuit that implements a 4-bit shifter with four functions: arithmetic shift right, don't shift, logical shift left, logical shift right. The shifting done in the book is logical shifting: a 0 is placed into the S0 or S7 bit, depending on which way the shift goes. An arithmetic shift right places D0 into both S0 and S1: it is duplicating the sign bit. A don't shift operation would send each data bit to the corresponding output: D0 to S0, D1 to S1, etc. Be sure that only one of these functions is enabled at a time.
The book shows how to create an adder from two half-adders. A subtractor can be created in a similar fashion.
1. Draw the truth table for a half-subtractor.
2. Draw the circuit for a half-subtractor.
3. Draw the truth table for a full subtractor.
4. Draw the circuit for a full subtractor.
List all 6 control signals for the ALU to generate the following. Do not use any question marks.
1. A OR B
2. The constant 1
3. The constant -1
4. B - A
Draw the SR latch using NAND gates instead of NOR gates. Label all input and output lines.
Answer these questions about this circuit diagram.
1. In terms of the input values for clock and data,
  1. when will Latch A be in a nondeterministic state (both input lines are 1)?
  2. when will Latch B be in a nondeterministic state?
  3. when does Latch C change its state?
  4. if Output 1 is 0, when does it change to 1?
  5. if Output 2 is 0, when does it change to 1?
2. In ten words or less, what is this circuit?
I have created a running example of this circuit using digital works. Download digital works and my example to run it
On many CPUs there are condition codes to test if the answer was zero, and to test if there was signed overflow: Z and O. An 8-bit ALU is constructed from 8 1-bit ALUs in Fig. 3-19. How would each of these condition codes be wired to such an ALU? Draw the circuits for each. (The O bit is set when the carry into the highest ALU is different from the carry out of the highest ALU). Fig. 3-19 is difficult to read. Please refer to my lecture when I explained the diagram.
14. Calculate the bus bandwidth to display 1280x1024 full-color video at 30 frames/sec. Assume that the data must pass over the bus twice, once from the CD-ROM to the memory and once from the memory to the screen.
15. The new FIU-PCI Express system has 10 Gbps lanes (gross capacity), in one direction. How many signal wires (not including ground) are needed in one direction for x32 operation? What is the gross capacity for x32 operation, one way (GBps)? What is the net capacity one way, assuming 8/10b? What would be the net capacity if 128/130b is used?

Bus Speed
- DDR3 runs at 166.67MHz. How many nanoseconds are in one cycle?
- If a cycle is 4 nanoseconds. How many cycles are in one second?
Memory Chips
- What is the maximum number of addresses for a chip that has 12 address lines, 3 bank lines, RAS and CAS?
- What is the number address lines that are used for CAS in a 1Mx8 chip that has 10 address lines, 2 bank lines, RAS and CAS? Assume that RAS uses all available address lines.
The 4 X 3 memory of Figure 3-28 uses 22 AND gates and three OR gates. It also has 11 input, output, and control lines.
1. Suppose the circuit were expanded to 64 x 16.
  1. How many AND gates would be needed?
  2. How many OR gates would be needed?
  3. How many pins would be coming into and out of the chip?
2. Suppose the circuit were expanded to 16 x 64.
  1. How many AND gates would be needed?
  2. How many OR gates would be needed?
  3. How many pins would be coming into and out of the chip?