M A S S A C H U S E T T S I N S T I T U T E O F T E C H N O L O G YDEPARTMENT OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCE6.375 Complex Digital SystemsSpring 2008 - Quiz - March 21, 200880 MinutesNAME: SCORE:Please write your name on every page of the quiz.Not all questions are of equal difficulty, so look over the entire quiz and budget your time carefully.Please carefully state any assumptions you make.Enter your answers in the spaces provided below. If you need extra room for an answer or forscratch work, you may use the back of each page but please clearly indicate where your answer islocated.You must not discuss the quiz’s contents with other students who have not yet takenthe quiz. If, prior to taking it, you are inadvertently exposed to material in a quiz —by whatever means — you must immediately inform the instructor or a TA.Points ScoreProblem 1 20Problem 225Problem 3 25Problem 4 10Problem 5 206.375 Quiz, Spring 2008 Name: 2Problem 1 : Throughput (20 total points)Ben Bitdiddle made a dual upcounter:using the following code:module temp();Reg#(Bit#(1)) stage <- mkReg(0);FIFO#(int) fifoA <- mkFIFO1();FIFO#(int) fifoB <- mkFIFO1();rule init (stage == 0);fifoA.enq(1);fifoB.enq(1);stage <= 1;endrulerule inc1 (stage == 1);let temp = fifoA.first();fifoA.deq();$display("Inc1: %d", temp);fifoB.enq(temp+1);endrulerule inc2 (stage == 1);let temp = fifoB.first();fifoB.deq();$display("Inc2: %d", temp);fifoA.enq(temp+1);endrulerule exit ((fifoA.first() == 6) || (fifoB.first() == 6));$finish();endruleendmoduleHe was expecting to see the following display:Inc1: 1 Inc2: 1 Inc1: 2 Inc2: 2 Inc1: 3 Inc2: 3 Inc1: 4 Inc2: 4 Inc1: 5 Inc2: 56.375 Quiz, Spring 2008 Name: 31.1 (10 poi nts)The code compiled, but on simulation, he did not see any display statements. Why is the code notexecuting correctly?Solution:Since fifoA and fifoB are single element FIFOs, they are full after rule init. Rule inc1 andinc2 have implicit predicates of fifoA.notFull and fifoB.notFull. This leads to a deadlockwhere neither rule fires.1.2 (10 poi nts)Modify the code to get the desired execution. You can use library elements such as those used inthe labs.Solution:Making fifoA and fifoB 2-element FIFOs resolves the deadlock.FIFO#(int) fifoA <- mkFIFO();FIFO#(int) fifoB <- mkFIFO();6.375 Quiz, Spring 2008 Name: 4Problem 2 : Bluespec Semantics (25 total points)Consider the code given below:module sem();Reg#(int) count <- mkReg(1);Reg#(int) a <- mkReg(1);Reg#(int) b <- mkReg(2);Reg#(int) c <- mkReg(3);rule counter (True);count <= count + 1;endrulerule mod1 (True);a <= b + c;endrulerule mod2 (True);b <= c + count;endrulerule mod3 (True);c <= b + count;endrulerule exit (count >= 4);$finish();endruleendmodule2.1 (6 poi nts)What are the sequential composability conditions deduced by the compiler?Solution:The following composability relations are seen:exit < countermod2 or mod3 < countermod1 < mod2 or mod3mod2 C mod32.2 (9 poi nts)Using the above conditions, assume an overall order and determine the values of all the stateelements at finish.Solution:Any order which satisfies the above conditions is valid. Assuming the following order ofexecution:exit < mod1 < mod2 < counterValue of state elelments:Cycle 0 : a = 1; b = 2; c = 3; count = 1Cycle 1 : a = 5; b = 4; c = 3; count = 2Cycle 2 : a = 7; b = 5; c = 3; count = 3Cycle 3 : a = 8; b = 6; c = 3; count = 46.375 Quiz, Spring 2008 Name: 52.3 (10 poi nts)Modify the code such that all the rules fire every cycle in the following order:counter | mod1 < mod2 < mod3 < exitYou can use EHRs of any order.Solution:Use EHR components:EHR3_Reg#(int) count <- mkEHR3_Reg(1);Reg#(int) a <- mkReg(1);EHR2_Reg#(int) b <- mkEHR2_Reg(2);EHR2_Reg#(int) c <- mkEHR2_Reg(3);rule counter (True);count.write_0(count.read_0 + 1);endrulerule mod1 (True);a <= (b.read_0 + c.read_0);endrulerule mod2 (True);b.write_0(c.read_1 + count.read_1);endrulerule mod3 (True);c.write_1(b.read_1() + count.read_1());endrulerule exit (count.read_2 == 4);$finish();endrule6.375 Quiz, Spring 2008 Name: 6Problem 3 : Bluespec Synthesis (25 total points)Consider the code shown below:module mkMultBySixDyn(Foo#(int));Reg#(int) a <- mkReg(0);Reg#(int) x <- mkReg(0);Reg#(int) count <- mkReg(0);rule mulDyn (count>0 && count<6);count <= count+1;a <= a+x;endrulemethod Action put (int y) if (count==0);a <= y; x <= y;count <= 1;endmethodmethod ActionValue#(int) get if (count==6);count <= 0;return a;endmethodendmodule3.1: 15 pointsSketch the hardware produced on compiling this code. Label the interface signals, scheduling logicand signals corresponding to CANFIRE mulDyn and WILL FIRE mulDyn.6.375 Quiz, Spring 2008 Name: 73.2: 10 pointsThe rule mulDyn is replaced by the following rule:rule mulStat (count>0 && count<6);for(int i = 1; i<6; i++)if(count==i)begincount <= i+1; a <= a+x;endendruleHow does this change affect the hardware generated? Which implementation mulDyn or mulStathas more adders? More muxes? Compare the overall area and critical paths of the implementations.Solution:a) The for loop in MultByStat is statically elaborated to generate a sequence of addstatements each gated by the value of count. Assuming no optimization, MultbySixStat hasmore adders, more muxes, larger area and a longer critical path.Bluespec actually optimizes number of adders, and MultByStat actually has just one addercompared to 2 adders for MultByDyn. Other answers remain the same. No points deductedfor missing the optimization.b) In the hardware sketch, the following are important:Update logic for state variables, adders, can fire and will fire signals, methods’ rdy andenable signals.6.375 Quiz, Spring 2008 Name: 8Problem 4 : RC Delay (10 points)Assume you have an inverter (nmos width = 1 µm, pmos width = 2 µm) driving an interconnectof length 0.2 mm as shown in the figure. The interconnect has an inverter (nmos width = 5 µm,pmos width = 10 µm) at the other end which drives a flipflop whose input capacitance is 20 fF.Calculate the delay of the circuit from point A to point B (see figure). You can use a π model (asshown in the attached slide) for the bitline and assume that the transistors turn on after one RCtime constant. The process parameters are given in the table below.Process Parameters ValuePMOS gate capacitance per µm of transistor width 1.5fF/µmNMOS gate capacitance per µm of transistor width 1.5fF/µmPMOS drain capacitance p e r µm of transistor width 0.3fF/µmNMOS drain capacitance per µm of transistor width 0.3fF/µmPMOS
View Full Document
Unlocking...