CS-343 Assignment 2

Due Date and Submission

This assignment is due by midnight, February 9 Submit it by sending email to me at the address, vickery@babbage.cs.qc.edu. Be sure to put "CS-343 Assignment 2" in the subject of your email and to put your name/ID in the message body.

I prefer it if you put your answers inline in the body of your message instead of as an attachment. And I prefer plain text over HTML or word processor documents.

The Assignment

1. Computer A is twice as fast as computer B. Computer A takes ten seconds to run a program. How long will computer B take to run the same program?

   Twice as long, 20 sec.

2. Computer A is 60% faster than computer B. Computer A takes ten seconds to run a program. How long will computer B take to run the same program?

   If A is 60% faster, it is 1.6 times faster. That means that the execution time for B divided by the execution time for A is 1.6. Since the time for A is 10, the time for B will be 1.6 / 1 = B / 10, and B = 16 seconds

3. Computer B is 60% slower than computer A. Computer A takes ten seconds to run a program. How long will computer B take to run the same program?

   The wording is arguably ambiguous. Presumably the statement means that B is 40% finished with the program when A finishes all of it. So B's execution time is given by 0.4*B = 10, which means B's execution time will be 25 sec.

4. Computer B is twice as slow as computer A. Computer A takes ten seconds to run a program. How long will computer B take to run the same program?

   This is another example of awkward wording. Presumably twice as slow means half as fast. So B will take 2 * 10 = 20 sec to complete the program.

5. A particular Instruction Set Architecture (ISA) has four classes of instruction: load/store, fixed-point, floating-point, and branching. Load/store instructions all require 2 clock cycles to execute, fixed-point instructions all execute in one clock cycle, floating-point instructions all require 8 clock cycles to execute, and branch instructions take one clock cycle if the branch is successful and two clock cycles if the branch fails. A program is run on a processor with this ISA and measurements show that 20% of the instructions executed are load/store, 50% are fixed-point, 5% are floating-point, and the remainder are branches. Just 15% of the branches fail. What is the average number of clock cycles per instruction?

   This is a weighted average problem. The weights are 0.2 for load/store, 0.5 for fixed-point, and 0.05 for floating point. Since the weights have to sum to 1.0, the weight for branches is 0.25. Therefore failed branches account for 0.25 * 0.15 = 0.0375 and the weight for successful branches is 0.25 - 0.0375 = 0.2125. So the average is (0.2*2)+(0.5*1)+(0.05*8)+(0.2125*1)+(0.0375*2) = 1.5875 clock cycles per instruction.

6. For the previous question, the processor operates with a 2 GHz clock, and the program executes 3 million instructions. How long does it take the program to execute?

   Execution time S/P = S/C * C/I * I/P (Seconds, Clocks, Instructions, Program). The period (S/C) is 1/(2*10⁹) sec (0.5 nsec or 500 psec), so the total execution time is 0.5*10^-9 * 1.5875 * 3000000 = 0.002379 sec, or 2.379 msec.

7. A 1.5 GHz clock is used to synchronize the inputs to a logic network that has 7 levels. What is the maximum allowable propagation delay per gate?

   The period of a 1.5GHz clock is 1/(1.5*10⁹) = 1/1.5 * 10^-9 = 0.667 * 10^-9 = 667 * 10^-12, which is 667 psec. Dividing 667 by 7, the maximum delay per gate is 95.286 psec.

8. A logic network has a 5 levels and the gates have a maximum propagation delay of 12 psec. What is the maximum clock rate that can be used to synchronize the inputs to this network?

   There would be 5 * 12 = 60 psec delay time in the logic network, so the inputs could be driven by a clock with a period of 60 psec or more. The frequency of a 60 psec clock is 1/60*10^-12, which is 1/60 * 10¹² = 0.016 * 10¹² = 16 * 10⁹. So the maximum frequency would be 16GHz.

9. A computer has 1,024 registers (numbered 0 to 1,023). Arithmetic instructions for this computer hold three register numbers. How many bits are needed to hold the register numbers?

   log₂(1024) is 10, so each register number requires ten bits, for a total of 30 bits.

10. A byte-addressable memory is one that assigns a unique binary number as the address of each byte. How many bits are needed for the addresses of a 1GB (gigabyte) byte-addressable memory?

    1G is 2⁰ * 2³⁰, or 2³⁰. And log₂(2³⁰) is 30. So 30 bits are needed.

11. How many bits are needed for the addresses of a 16MB byte-addressable memory?

    16M is 2⁴ * 2²⁰, or 2²⁴. And log₂(2²⁴) is 24. So 24 bits are needed.