University of California Berkeley College of Engineering Computer Science Division EECS Spring 2003 John Kubiatowicz Midterm I March 12 2003 CS152 Computer Architecture and Engineering Your Name SID Number Discussion Section Problem Possible 1 25 2 20 3 25 4 30 Total 1 Score This page left for 3 141592653589793238462643383279502884197169399375105820974944 2 Problem 1 Short Answer Problem 1a 3 pts What is Amdhal s law Give a formula and define the terms How is this useful Problem 1b 3 pts What are setup and hold time and how can they be violated in a synchronous circuit Can you still use a chip that is experiencing hold time violations How about setup violations Problem 1c 2 pts Is the multi cycle data path always faster than the single cycle data path Explain Problem 1d 3 pts What are precise interrupts and why is it easy to provide them for our multi cycle data path 3 Problem 1e 3 pts Suppose that you have analyzed a benchmark that runs on your company s processor This processor runs at 500MHz and has the following characteristics Instruction Type Arithmetic and logical Load and Store Branches Floating Point Frequency 40 30 20 10 Cycles 1 2 1 12 What is the CPI and MIPS rating of this processor running this benchmark Problem 1f 2 pts What is the technique used for a carry select adder and how can it be used in general to speed up hardware hint this is a very general technique to make a time space tradeoff Problem 1g 3pts What does it mean for a branch to have a delay slot and why does it complicate the servicing of interrupts 4 Problem 1h 3pts The Clark paper on testing talked about using randomness in at least two different ways during testing of the VAX What were they Problem 1i 3 pts The 1 bit Booth algorithm recodes one of the operands of a multiplier from binary into trinary logic with symbols 1 0 and 1 The transformation occurs one bit at a time as given in class Cur Prev Out 0 0 0 0 1 1 1 0 1 1 1 0 Suppose we encode 3 bits at a time Finish filling out the following transformation table Cur 000 000 001 001 010 010 011 011 100 100 101 101 110 110 111 111 Prev 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 5 Out 0 1 1 2 Problem 2 Delay For a Full Adder A key component of an ALU is a full adder A symbol for a full adder is A B Cout Full Adder Cin S Problem 2a 5pts Implement a full adder using as few 2 input AND OR and XOR gates as possible Keep in mind that the Carry In signal may arrive much later than the A or B inputs Thus optimize your design if possible to have as few gates between Carry In and the two outputs as possible 6 Assume the following characteristics for the gates AND Input load 100fF Propagation delay TPlh 0 4ns TPhl 0 4ns Load Dependent delay TPlhf 0020ns TPhlf 0021ns OR Input load 100fF Propagation delay TPlh 0 2ns TPhl 0 6ns Load Dependent delay TPlhf 0020ns TPhlf 0021ns XOR Input load 200fF Propagation delay TPlh 8ns TPhl 8ns Load Dependent delay TPlhf 0040ns TPhlf 0042ns Problem 2b 3pts Compute the input load for each of the 3 inputs to your full adder Problem 2c 4pts Identify two critical paths from the inputs to the Sum and the Carry Out signal Compute the propagation delays for these critical paths based on the information given above You will have 2 numbers for each of these two paths Problem 2d 2pts Compute the Load Dependent delay for your two outputs 7 Problem 2e 6pts Suppose we wish to build a fast adder One component might be a 4 bit adder with propagate and generate signals such as might be used for carry lookahead logic Construct this adder as a 4 bit ripple adder internally you can use your full adders with separate propagate and generate outputs Let the output carry be a function of the propagate and generate signals Draw a circuit for this component and compute the propagation delay for the slowest signal A 3 0 Cout B 3 0 4 BIT Adder Cin FAST S 3 0 8 G P Problem 3 Non Restoring Division Here is the pseudo code for an unsigned division algorithm It is the non restoring version of the last divider that we developed Assume that quotient and remainder are 32 bit global values As far as inputs are concerned dividend is 32 bits wide while divisor is no more than 31 bits divide dividend divisor int count Missing initialization instructions MOBIUS64 remainder quotient while count 0 count Low bit of quotient is inverted sign of remainder if quotient 0x1 remainder remainder divisor else remainder remainder divisor MOBIUS64 remainder quotient Missing trailing instructions The MOBIUS64 hi lo instruction rotates the 64 bit value hi lo around to the left 1 bit wrapping the top bit of hi back to the bottom of lo and inverting it in the process So for instance MOBIUS64 0xFFFFFFFF 0x000000FF 0xFFFFFFFE 0x000001FE And MOBIUS64 0x0FFFFFFF 0x000000FF 0x1FFFFFFE 0x000001FF Problem 3a 5pts Implement MOBIUS64 t1 t0 as 6 MIPS instructions Assume t2 contains the constant 0x80000000 Hint what can different flavors of slt sltu do to help Problem 3b 5pts The divide algorithm is incomplete It is missing some initialization and some final code What is missing Careful what if the remainder is negative 9 Problem 3c 11pts Assume that you have a MIPS processor that is missing the divide instruction Assume that dividend and divisor are in a0 and a1 respectively and that remainder and quotient are returned in registers v0 and v1 respectively You can use MOBIUS64 as a pseudo instruction that takes 3 registers don t forget the constant in t2 Make sure to adher to MIPS register conventions and optimize the loop as much as possible Problem 3d 4pts How will this algorithm have to change if the divisor is allowed to be 32 bits in size 10 Problem 4 New instructions for a multi cycle data path PCWr PCWrCond Zero RAdr WrAdr 32 Din Dout 32 32 5 Rt 0 Rd busA A Rb Reg File Mux Ideal Memory 1 Ra 5 32 Rt Mem Data Reg Mux 32 0 0 Mux 32 Rw busW busB 1 1 Mux 0 Imm 16 Extend ExtOp 2 32 0 Zero 32 1 4 B 1 32 32 0 1 32 ALU Out Rs ALUSelA RegWr ALU RegDst 32 PC 32 IRWr Mux MemWr Instruction Reg IorD PCSrc 32 2 3 32 ALU Control ALUOp MemtoReg ALUSelB The Multi Cycle datapath developed in class and the book is shown above In class we developed an assembly language for microcode It is included here for reference Field Name ALU SRC1 SRC2 ALU Dest Memory MemReg PC Write Sequence Values For Field Add Sub Func Or PC rs 4 rt Extend Extend0 ExtShft rd ALU rt ALU rt Mem Read PC Read …
View Full Document
Unlocking...