Spring 2003 EECS150 - Lec21-HLD1Page 1EECS150 - Digital DesignLecture 21 - High-level Design and OptimizationApril 8, 2003John WawrzynekSpring 2003 EECS150 - Lec21-HLD1Page 2Introduction• High-level Design Specifies:– How data is moved around and operated on.– The architecture (sometimes called micro-architecture):• The organization of state elements and combinational logic blocks• Functional specification of combinational logic blocks• Optimization– Deals with the task of modifying an architecture and data movement procedure to meet some particular design requirement:• performance, cost, power, or some combination.• Most designers spend most of their time on high-level organization and optimization– modern CAD tools help fill in the low-level details and optimization• gate-level minimization, state-assignment, etc.– A great deal of the leverage on effecting performance, cost, andpower comes at the high-level.Spring 2003 EECS150 - Lec21-HLD1Page 3A Standard High-level Organization•Controller– accepts external and control input, generates control and external output and sequences the movement of data in the datapath.• Datapath– is responsible for data manipulation. Usually includes a limited amount of storage.•Memory– optional block used for long term storage of data structures.• Standard model for CPUs, micro-controllers, many other digital sub-systems.• Usually not nested.• Often cascaded:Spring 2003 EECS150 - Lec21-HLD1Page 4Register Transfer Level Descriptions• A standard high-level representation for describing systems.• It follows from the fact that all synchronous digital system can be described as a set of state elements connected by combination logic (CL) blocks:• RTL comprises a set of register transfers with optional operators as part of the transfer.•Example:regA ← regBregC ← regA + regBif (start==1) regA ← regC• My personal style:– use “;” to separate transfers that occur on separate cycles.– Use “,” to separate transfers that occur on the same cycle.• Example (2 cycles):regA ← regB, regB ← 0;regC ← regA;reg regCL CLclock inputoutputoption feedbackinputoutputSpring 2003 EECS150 - Lec21-HLD1Page 5Example of Using RTLACC ← ACC + R0, R1 ← R0;ACC ← ACC + R1, R0 ← R1;R0 ← ACC;•••• In this case: RTL description is used to sequence the operations on the datapath (dp).• It becomes the high-level specification for the controller.• Design of the FSM controller follows directly from the RTL sequence. FSM controls movement of data by controlling the multiplexor control signals.010 10 101R0R1ACC+S0S1S2S3Spring 2003 EECS150 - Lec21-HLD1Page 6Example of Using RTL• Sometimes RTL is used as a starting point for designing boththe dp and the control:•example:regA ← IN;regB ← IN;regC ← regA + regB;regB ← regC;• From this we can deduce:– IN must fanout to both regA and regB– regA and regB must output to an adder– the adder must output to regC– regB must take its input from amux that selects between IN and regC• What does the datapath look like:• The controller:Spring 2003 EECS150 - Lec21-HLD1Page 7List Processor Example• RTL gives us a framework for making high-level optimizations.• General design procedure outline:1. Problem, Constraints, and Component Library Spec.2. “Algorithm” Selection3. Micro-architecture Specification4. Analysis of Cost, Performance, Power5. Optimizations, Variations6. Detailed DesignSpring 2003 EECS150 - Lec21-HLD1Page 81. Problem Specification• Design a circuit that forms the sum of all the 2's complements integers stored in a linked-list structure starting at memory address 0:• All integers and pointers are 8-bit. The link-list is stored in a memory block with an 8-bit address port and 8-bit data port, as shown below. The pointer from the last element in the list is 0. At least one node in list.I/Os:– START resets to head of list and starts addition process.– DONE signals completion– R, Bus that holds the final resultSpring 2003 EECS150 - Lec21-HLD1Page 91. Other Specifications• Design Constraints:– Usually the design specification puts a restriction on cost, performance, power or all. We will leave this unspecified for now and return to it later.• Component Library:component delaysimple logic gates 0.5nsn-bit register clk-to-Q=0.5nssetup=0.5nsn-bit 2-1 multiplexor 1nsn-bit adder (2 log(n) + 2)nsmemory 10ns read (asynchronous read)zero compare 0.5 log(n)(single ported memory)Are these reasonable?Spring 2003 EECS150 - Lec21-HLD1Page 10New Component• Register with Load Enable:• Allows register to be either be loaded on selected clock posedge or to retain its previous value.• Assume both data and LD require setup time = 0.5ns.• Assume no reset input.Functional description only. Transistor level circuit has lower input delay.Spring 2003 EECS150 - Lec21-HLD1Page 112. Algorithm Specification• In this case the memory only allows one access per cycle, so the algorithm is limited to sequential execution. If in another case more input data is available at once, then a more parallel solution may be possible.• Assume datapath state registers NEXT and SUM.– NEXT holds a pointer to the node in memory.– SUM holds the result of adding the node values to this point.If (START==1) NEXTÅ0, SUMÅ0;repeat {SUMÅSUM + Memory[NEXT+1];NEXTÅMemory[NEXT];} until (NEXT==0);RÅSUM, DONEÅ1;Spring 2003 EECS150 - Lec21-HLD1Page 123. Architecture #1Direct implementation of RTL description:DatapathControllerIf (START==1) NEXTÅ0, SUMÅ0;repeat {SUMÅSUM + Memory[NEXT+1];NEXTÅMemory[NEXT];} until (NEXT==0);RÅSUM, DONEÅ1; A_SEL01NEXT01+MemoryDA==0+01SUMNEXT_SELLD_NEXTNEXT_ZEROSUM_SELLD_SUM010Spring 2003 EECS150 - Lec21-HLD1Page 134. Analysis of Cost, Performance, and Power• Skip Power for now.•Cost:– How do we measure it? # of transistors? # of gates? # of CLBs?– Depends on implementation technology. Usually we are interestedin comparing the relative cost of two competing implementations. (Save this for later)• Performance:– 2 clock cycles per number added.– What is the minimum clock period?– The controller might be on the critical path. Therefore we need to know the implementation, and controller input and output delay.Spring 2003 EECS150 - Lec21-HLD1Page 14Possible Controller ImplementationSTARTCOMPSUMGETNEXTDONELD_SUMSUM_SELLD_NEXTNEXT_SELDONEA_SELSTARTSTARTSTARTNEXT_ZERO• Based on this, what is
View Full Document
Unlocking...