1University of California, Berkeley College of Engineering Computer Science Division EECS Spring 2003 John KubiatowiczMidterm I March 12, 2003 CS152 Computer Architecture and Engineering Your Name: SID Number: Discussion Section: Problem Possible Score 1 25 2 20 3 25 4 30 Total2 [ This page left for π ] 3.1415926535897932384626433832795028841971693993751058209749443 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?4Problem 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 Frequency (%) Cycles Arithmetic and logical 40 1 Load and Store 30 2 Branches 20 1 Floating Point 10 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?5Problem 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: Suppose we encode 3 bits at a time. Finish filling out the following transformation table: Cur Prev Out 0 0 0 0 1 1 1 0 1 1 1 0 Cur Prev Out 000 0 0 000 1 1 001 0 1 001 1 2 010 0 010 1 011 0 011 1 100 0 100 1 101 0 101 1 110 0 110 1 111 0 111 16 Problem 2: Delay For a Full Adder A key component of an ALU is a full adder. A symbol for a full adder is: 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: Full AdderA BSCinCout7Assume 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.8Problem 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. 4-BIT AdderA[3:0] B[3:0]S[3:0]CinCout[FAST]G P9Problem 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?)10Problem 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?11Problem 4: New instructions for a multi-cycle data path 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 Values For Field Function of Field Add
View Full Document
Unlocking...