CS61C Fall 2013 Homework 6

Due Sunday, November 10, 2013 @ 11:59pm

Updates

Changed hold time in problem 2 from 2ns to 0.5ns.

Goals

This assignment will check your understanding of synchronous digital systems, state elements, combinational logic, and CPU control and datapath.

Starter Files and Submission

To copy the hw6 files into your homework directory, go to your hw directory (type git init if it's not already in a git repository) and then type:

$ git pull ~cs61c/hw/06 master

Submit your solution by going into your directory that contains your completed hw6.txt. From within that directory, type submit hw6. You must work alone on this assignment. (File names are case-sensitive and the submission program will not accept your submission if your file names differ at all from those specified).

Exercises

Problem 1: Pipelining

Suppose we had the following "silly accumulator." It makes use of an XOR'er, an adder, and a subtracter.

Component specs:

propogation delay of XOR'er = 20 ns
propogation delay of adder = 15 ns
propogation delay of subtracter = 15 ns
clk-to-q delay of a register = 5 ns
negligible register setup and hold times (~0 ns)

Assume that the input changes on every rising edge of the clock (i.e. its value updates at the same time as the clock trigger).

Calculate the maximum clock rate in MHz at which this circuit can operate before pipelining.
Calculate the maximum clock rate in MHz for the three-stage pipelined version of the circuit.
What is the delay (latency) in nanoseconds in the non-pipelined version? What about the pipelined version? (i.e. Calculate the amount of time it takes for the output to change after the first input arrives.)
What is the least number of inputs required to achieve higher throughput with the pipelined version?

Problem 2: Waveform Diagrams

Consider the circuit of Flip-Flops (FF) shown here. Assume that input X alternates between 1 and 0, 1ns after every rising edge. Initially, X is 0 (so 1ns after the first rising edge it should be 1) while A, B, C, and D are unknown from the start. Assume one clock cycle is 4 ns. Given the clock signal, draw the wave for input X, and the signals at points A, B, C, and D in the circuit for the first 6 clock cycles. Assume that the clk-to-q delay is 1ns, the setup time is negligible (~0 ns), and the hold time is 0.5ns. Assume that Flip-Flops take their new value on the rising edge of the clock cycle. Assume time = 0 on the first rising edge. Note the NOT gate that precedes B (you may ignore propagation delay for this problem).

Answer the following questions. You would want to fill out the waveform diagram below to help though you don't have to submit it. Consider six clock cycles (so six rising edges) as shown in the diagram. The diagram ends 1ns after the 6th rising edge, and you only need to consider from t=0 to t=21 ns, so you can ignore everything before the first rising edge in the diagram and anything that happens after the end of the diagram.

How many times does the value at B change (changing from undetermined to 1 or 0 counts as one)?
How many times does the value at D change (changing from undetermined to 1 or 0 counts as one)?
At which time(s) does the value at A becomes stable at 0?
At which time(s) does the value at C becomes stable at 1?

Problem 3: Clock Frequency

Consider this circuit. It accumulates two arguments at a time, arriving at each clock period. You are given the following: the adder propagation delay is 2 ns, the register setup time is 2 ns, the register hold time is 3 ns, the register clk-to-q delay is 4 ns, and the clock frequency is 50 MHz.

Explain why this accumulator will not work correctly.
Now assume that the arguments arrive 2 ns after each clock period. Give the critical path delay and the maximum clock frequency at which the circuit will work.
Describe a way to rearrange the accumulator so that the maximum clock frequency will be greater. You may only use the components already present in the circuit.

Problem 4: Simple FSM and Truth Tables

Design an FSM that would take an infinite stream of bits and output 1 twice if it sees two consecutive 1's. In other words, given some input X_i, if X_i-2 = X_i-1 = 1 or X_i-1 = X_i = 1, then it will output 1. Then convert it into a truth table mapping each state and input to a next state and an output. Name the states meaningfully so that it is easily understandable (for example, Seen1 and Seen11). You should have three states only. You only need to submit the truth table; you do not need to submit your drawing of the FSM.

Problem 5: Truth Tables, Boolean Algebra, FSMs, Logic Circuits

Consider the following finite state machine.

Come up with the MOST simplified boolean expressions for determining bits for the next state and the output bit given the current state and the input bit. You should have 3 expressions, one for each digit of the next state as well as one for output. (You might want to first construct a truth table.)

fsmCompute takes one bit at a time as input. Fill in the blank below so that it returns the same bits as what the FSM would output given a series of input bits. Hint: the output value can be determined by the last 3 bits of numState, which are A, B and C.

/*
	Called once per "clock cycle."
	Assume input x is 0 or 1.
	Outputs FSM output (0 or 1).
*/
int fsmCompute(int x) {
	static unsigned int numState = 0x00000000;
	numState = (numState << 1) + x;   // update state
	unsigned int A = numState & 1;
	unsigned int B = numState & 2;
	unsigned int C = numState & 4;
	return ________________________;
}