1EE141Interconnect EffectsInput-OutputEE141- Spring 2003Lecture 25EE141Schedule for the rest of thesemesterFuture perspectivesProject posters(1:30-5pm)Memory 2Week 15Memory 1midterm 2 resultshw 10 duehw 11 (not graded)NO LECTURE(Faculty retreat)Week 14Interconnect (cntd)hw 9 duehw 10InterconnectLaunch Project 2Week 13ThTu2EE141TodayShortoverviewoflastlectureLaunch project 2 – discussion ofdividersStart discussion of “Coping withinterconnect – Chapter 9)EE141Longest Logic Path inEdge-Triggered SystemsClkTTSUTClk-QTLMLatest pointof launchingEarliest arrivalof next cycleTJI+δ3EE141Clock Constraints inEdge-Triggered SystemsIf launching edge is late and receiving edge is early, the data will not be too late if:Minimum cycle time is determined by the maximum delays through the logicTc-q+TLM+TSU<T–TJI,1–TJI,2+δδδδTc-q+TLM+TSU-δδδδ+2TJI<TSkew can be either positive or negativeEE141Shortest PathClkTClk-QTLmEarliest pointof launchingData must not arrivebefore this timeClkTHNominalclock edge4EE141Clock Constraintsin Edge-Triggered SystemsMinimumlogic delayIf launching edge is early and receiving edge is late:Tc-q+TLM<TH+δδδδTc-q+TLM<TH+δδδδEE141SummaryJitter always works against you. Shouldminimize it.Clock skew can work for or against you.Overall strategy: deliver clock to thedifferent nodes in the network withminimum skew!5EE141DividerEE141- Spring 2003Project 2With contributions of J. Kubiatowicz (CS152)EE141 - Project 2Divide: Paper & Pencil1001 QuotientDivisor 1000 1001010 Dividend–1000101011010–100010 Remainder (or Modulo result)See how big a number can be subtracted, creating quotientbitoneachstepBinary => 1 * divisor or 0 * divisorDividend = Quotient x Divisor + Remainder=>|Dividend|=|Quotient|+|Divisor|6EE141 - Project 2DIVIDE HARDWARE Version 1° 64-bit Divisor reg, 64-bit ALU, 64-bit Remainder reg,32-bit Quotient regRemainderQuotientDivisor64-bit A/SShift RightShift LeftWriteControl32 bits64 bits64 bitsEE141 - Project 22b. Restore the original value by adding theDivisor register to the Remainder register, &place the sum in the Remainder register. Alsoshift the Quotient register to the left, settingthe new least significant bit to 0.Divide Algorithm Version 1°Takes n+1 steps for n-bit Quotient & Rem.Remainder Quotient Divisor0000 0111 0000 0010 0000TestRemainderRemainder < 0Remainder ≥ ≥ ≥ ≥ 01. Subtract the Divisor register from theRemainder register, and place the resultin the Remainder register.2a. Shift theQuotient registerto theleft settingthe new rightmostbit to 1.3. Shift the Divisor register right1 bit.DoneYes: n+1 repetitions (n = 4 here)Start: Place Dividend in Remaindern+1repetition?No: < n+1 repetitions7EE141 - Project 2Divide Algorithm I example (7 / 2)Remainder Quotient Divisor0000 0111 00000 0010 00001: 1110 0111 00000 0010 00002: 0000 0111 00000 0010 00003: 0000 0111 00000 0001 00001: 1111 0111 00000 0001 00002: 0000 0111 00000 0001 00003: 0000 0111 00000 0000 10001: 1111 1111 00000 0000 10002: 0000 0111 00000 0000 10003: 0000 0111 00000 0000 01001: 0000 0011 00000 0000 01002: 0000 0011 00001 0000 01003: 0000 0011 00001 0000 00101: 0000 0001 00001 0000 00102: 0000 0001 00011 0000 00103: 0000 0001 00011 0000 0001Answer:Quotient = 3Remainder = 1EE141 - Project 2Observations on Divide Version 1° 1/2 bits in divisor always 0=> 1/2 of 64-bit adder is wasted=> 1/2 of divisor is wasted° Instead of shifting divisor to right,shift remainder to left?8EE141 - Project 2Divide Algorithm I example: wasted spaceRemainder Quotient Divisor0000 0111 00000 0010 00001: 1110 0111 00000 0010 00002: 0000 0111 00000 0010 00003: 0000 0111 00000 0001 00001: 1111 0111 00000 0001 00002: 0000 0111 00000 0001 00003: 0000 0111 00000 0000 10001: 1111 1111 00000 0000 10002: 0000 0111 00000 0000 10003: 0000 0111 00000 0000 01001: 0000 0011 00000 0000 01002: 0000 0011 00001 0000 01003: 0000 0011 00001 0000 00101: 0000 0001 00001 0000 00102: 0000 0001 00011 0000 00103: 0000 0001 00011 0000 0010EE141 - Project 2DIVIDE HARDWARE Version 2° 32-bit Divisor reg, 32-bit ALU, 64-bit Remainder reg,32-bit Quotient regRemainderQuotientDivisor32-bit ALUShift LeftWriteControl32 bits32 bits64 bitsShift Left9EE141 - Project 2Divide Algorithm Version 2Remainder Quotient Divisor0000 0111 0000 00103b. Restore the original value by adding the Divisorregister to the left half of theRemainderregister,&place the sum in the left half of theRemainderregister. Also shift the Quotient register to the left,setting the new least significant bit to 0.TestRemainderRemainder < 0Remainder ≥≥≥≥ 02.Subtract the Divisor register from theleft half of theRemainder register, & place theresult in the left half of theRemainder register.3a. Shift theQuotient registerto theleft settingthe new rightmostbit to 1.1. Shift the Remainder register left 1bit.DoneYes: nrepetitions (n = 4 here)nthrepetition?No: < n repetitionsStart: Place Dividend in RemainderEE141 - Project 2Divide Algorithm I version 2 (shift remainder)Remainder Quotient Divisor0000 0111 00000 00101: 1110 0111 00000 00102: 0000 0111 00000 00103: 0000 1110 00000 00101: 1110 1110 00000 00102: 0000 1110 00000 00103: 0001 1100 00000 00101: 1111 1100 00000 00102: 0001 1100 00000 00103: 0011 1000 00000 00101: 0001 1000 00001 00102: 0001 1000 00001 00103: 0011 0000 00001 00101: 0001 0000 00011 00102: 0001 0000 00011 001010EE141 - Project 2Divide: Revisited1001010-100000010-1000110101+1000111010+100000010Remainder (or Modulo result)Dividend1001 QuotientDivisor 1000Non-restoring dividerAvoids extra step of “restoration” when partial result is negative.Instead of subtract, adds divisor on next iterationEE141 - Project 2Divide Algorithm I example: non-restoringRemainder Quotient Divisor0000 0111 00000 00101: 1110 0111 00000 00102: 1100 1110 00000 00101: 1110 1110 00000 00102: 1101 1100 00000 00101: 1111 1100 00000 00102: 1111 1000 00000 00101: 0001 1000 00001 00102: 0011 0000 00001 00101: 0001 0000 00011 001011EE141Project 2Goal: Design Divider with Minimum ClockFrequency» Supply voltage fixed at 2 V, 0.25 µmCMOS» 4 bit divident, divisor, quotient, remainder» Two’s complement, all words positive» Choice of static and/or pass-transistor logic» Given register schematics» Given output loads, input waveforms, clockwaveformsEE141Design PhasesDetermine block diagram of divider that willlead to minimum clock-cycle (be inspired!)Design schematics of basic cellsDemonstrate functionality of
View Full Document