1、1,Chapter 11: Design Technology,2,Outline,Automation: synthesis Verification: hardware/software co-simulation Reuse: intellectual property cores Design process models,3,Design task Define system functionality Convert functionality to physical implementation while Satisfying constrained metrics Optim
2、izing other design metrics Designing embedded systems is hard Complex functionality Millions of possible environment scenarios Competing, tightly constrained metrics Productivity gap As low as 10 lines of code or 100 transistors produced per day,Introduction,4,Improving productivity,Design technolog
3、ies developed to improve productivity We focus on technologies advancing hardware/software unified view Automation Program replaces manual design Synthesis Reuse Predesigned components Cores General-purpose and single-purpose processors on single IC Verification Ensuring correctness/completeness of
4、each design step Hardware/software co-simulation,5,Automation: synthesis,Early design mostly hardware Software complexity increased with advent of general-purpose processor Different techniques for software design and hardware design Caused division of the two fields Design tools evolve for higher l
5、evels of abstraction Different rate in each field Hardware/software design fields rejoining Both can start from behavioral description in sequential program model 30 years longer for hardware design to reach this step in the ladder Many more design dimensions Optimization critical,6,Hardware/softwar
6、e parallel evolution,Software design evolution Machine instructions Assemblers convert assembly programs into machine instructions Compilers translate sequential programs into assembly Hardware design evolution Interconnected logic gates Logic synthesis converts logic equations or FSMs into gates Re
7、gister-transfer (RT) synthesis converts FSMDs into FSMs, logic equations, predesigned RT components (registers, adders, etc.) Behavioral synthesis converts sequential programs into FSMDs,7,Increasing abstraction level,Higher abstraction level focus of hardware/software design evolution Description s
8、maller/easier to capture E.g., Line of sequential program code can translate to 1000 gates Many more possible implementations available (a) Like flashlight, the higher above the ground, the more ground illuminated Sequential program designs may differ in performance/transistor count by orders of mag
9、nitude Logic-level designs may differ by only power of 2 (b) Design process proceeds to lower abstraction level, narrowing in on single implementation,8,Synthesis,Automatically converting systems behavioral description to a structural implementation Complex whole formed by parts Structural implement
10、ation must optimize design metrics More expensive, complex than compilers Cost = $100s to $10,000s User controls 100s of synthesis options Optimization critical Otherwise could use software Optimizations different for each user Run time = hours, days,9,Gajskis Y-chart,Each axis represents type of de
11、scription Behavioral Defines outputs as function of inputs Algorithms but no implementation Structural Implements behavior by connecting components with known behavior Physical Gives size/locations of components and wires on chip/board Synthesis converts behavior at given level to structure at same
12、level or lower E.g., FSM gates, flip-flops (same level) FSM transistors (lower level) FSM X registers, FUs (higher level) FSM X processors, memories (higher level),10,Logic synthesis,Logic-level behavior to structural implementation Logic equations and/or FSM to connected gates Combinational logic s
13、ynthesis Two-level minimization (Sum of products/product of sums) Best possible performance Longest path = 2 gates (AND gate + OR gate/OR gate + AND gate) Minimize size Minimum cover Minimum cover that is prime Heuristics Multilevel minimization Trade performance for size Pareto-optimal solution Heu
14、ristics FSM synthesis State minimization State encoding,11,Two-level minimization,Represent logic function as sum of products (or product of sums) AND gate for each product OR gate for each sum Gives best possible performance At most 2 gate delay Goal: minimize size Minimum cover Minimum # of AND ga
15、tes (sum of products) Minimum cover that is prime Minimum # of inputs to each AND gate (sum of products),12,Minimum cover,Minimum # of AND gates (sum of products) Literal: variable or its complement a or a, b or b, etc. Minterm: product of literals Each literal appears exactly once abcd, abcd, abcd,
16、 etc. Implicant: product of literals Each literal appears no more than once abcd, acd, etc. Covers 1 or more minterms acd covers abcd and abcd Cover: set of implicants that covers all minterms of function Minimum cover: cover with minimum # of implicants,13,Minimum cover: K-map approach,Karnaugh map
17、 (K-map) 1 represents minterm Circle represents implicant Minimum cover Covering all 1s with min # of circles Example: direct vs. min cover Less gates 4 vs. 5 Less transistors 28 vs. 40,F=abcd + acd + abcd,2 4-input AND gate 1 3-input AND gates 1 4 input OR gate 28 transistors,K-map: sum of products
18、,K-map: minimum cover,Minimum cover,Minimum cover implementation,14,Minimum cover that is prime,Minimum # of inputs to AND gates Prime implicant Implicant not covered by any other implicant Max-sized circle in K-map Minimum cover that is prime Covering with min # of prime implicants Min # of max-siz
19、ed circles Example: prime cover vs. min cover Same # of gates 4 vs. 4 Less transistors 26 vs. 28,15,Minimum cover: heuristics,K-maps give optimal solution every time Functions with 6 inputs too complicated Use computer-based tabular method Finds all prime implicants Finds min cover that is prime Als
20、o optimal solution every time Problem: 2n minterms for n inputs 32 inputs = 4 billion minterms Exponential complexity Heuristic Solution technique where optimal solution not guaranteed Hopefully comes close,16,Heuristics: iterative improvement,Start with initial solution i.e., original logic equatio
21、n Repeatedly make modifications toward better solution Common modifications Expand Replace each nonprime implicant with a prime implicant covering it Delete all implicants covered by new prime implicant Reduce Opposite of expand Reshape Expands one implicant while reducing another Maintains total #
22、of implicants Irredundant Selects min # of implicants that cover from existing implicants Synthesis tools differ in modifications used and the order they are used,17,Multilevel logic minimization,Trade performance for size Increase delay for lower # of gates Gray area represents all possible solutio
23、ns Circle with X represents ideal solution Generally not possible 2-level gives best performance max delay = 2 gates Solve for smallest size Multilevel gives pareto-optimal solution Minimum delay for a given size Minimum size for a given delay,size,delay,multi-level minim.,2-level minim.,18,Example,
24、Minimized 2-level logic function: F = adef + bdef + cdef + gh Requires 5 gates with 18 total gate inputs 4 ANDS and 1 OR After algebraic manipulation: F = (a + b + c)def + gh Requires only 4 gates with 11 total gate inputs 2 ANDS and 2 ORs Less inputs per gate Assume gate inputs = 2 transistors Redu
25、ced by 14 transistors 36 (18 * 2) down to 22 (11 * 2) Sacrifices performance for size Inputs a, b, and c now have 3-gate delay Iterative improvement heuristic commonly used,19,FSM synthesis,FSM to gates State minimization Reduce # of states Identify and merge equivalent states Outputs, next states s
26、ame for all possible inputs Tabular method gives exact solution Table of all possible state pairs If n states, n2 table entries Thus, heuristics used with large # of states State encoding Unique bit sequence for each state If n states, log2(n) bits n! possible encodings Thus, heuristics common,20,Te
27、chnology mapping,Library of gates available for implementation Simple only 2-input AND,OR gates Complex various-input AND,OR,NAND,NOR,etc. gates Efficiently implemented meta-gates (i.e., AND-OR-INVERT,MUX) Final structure consists of specified librarys components only If technology mapping integrate
28、d with logic synthesis More efficient circuit More complex problem Heuristics required,21,Complexity impact on user,As complexity grows, heuristics used Heuristics differ tremendously among synthesis tools Computationally expensive Higher quality results Variable optimization effort settings Long ru
29、n times (hours, days) Requires huge amounts of memory Typically needs to run on servers, workstations Fast heuristics Lower quality results Shorter run times (minutes, hours) Smaller amount of memory required Could run on PC Super-linear-time (i.e. n3) heuristics usually used User can partition larg
30、e systems to reduce run times/size 1003 503 + 503 (1,000,000 250,000),22,Integrating logic design and physical design,Past Gate delay much greater than wire delay Thus, performance evaluated as # of levels of gates only Today Gate delay shrinking as feature size shrinking Wire delay increasing Perfo
31、rmance evaluation needs wire length Transistor placement (needed for wire length) domain of physical design Thus, simultaneous logic synthesis and physical design required for efficient circuits,23,Register-transfer synthesis,Converts FSMD to custom single-purpose processor Datapath Register units t
32、o store variables Complex data types Functional units Arithmetic operations Connection units Buses, MUXs FSM controller Controls datapath Key sub problems: Allocation Instantiate storage, functional, connection units Binding Mapping FSMD operations to specific units,24,Behavioral synthesis,High-leve
33、l synthesis Converts single sequential program to single-purpose processor Does not require the program to schedule states Key sub problems Allocation Binding Scheduling Assign sequential programs operations to states Conversion template given in Ch. 2 Optimizations important Compiler Constant propa
34、gation, dead-code elimination, loop unrolling Advanced techniques for allocation, binding, scheduling,25,System synthesis,Convert 1 or more processes into 1 or more processors (system) For complex embedded systems Multiple processes may provide better performance/power May be better described using
35、concurrent sequential programs Tasks Transformation Can merge 2 exclusive processes into 1 process Can break 1 large process into separate processes Procedure inlining Loop unrolling Allocation Essentially design of system architecture Select processors to implement processes Also select memories an
36、d busses,26,System synthesis,Tasks (cont.) Partitioning Mapping 1 or more processes to 1 or more processors Variables among memories Communications among buses Scheduling Multiple processes on a single processor Memory accesses Bus communications Tasks performed in variety of orders Iteration among
37、tasks common,27,System synthesis,Synthesis driven by constraints E.g., Meet performance requirements at minimum cost Allocate as much behavior as possible to general-purpose processor Low-cost/flexible implementation Minimum # of SPPs used to meet performance System synthesis for GPP only (software)
38、 Common for decades Multiprocessing Parallel processing Real-time scheduling Hardware/software codesign Simultaneous consideration of GPPs/SPPs during synthesis Made possible by maturation of behavioral synthesis in 1990s,28,Temporal vs. spatial thinking,Design thought process changed by evolution o
39、f synthesis Before synthesis Designers worked primarily in structural domain Connecting simpler components to build more complex systems Connecting logic gates to build controller Connecting registers, MUXs, ALUs to build datapath “capture and simulate” era Capture using CAD tools Simulate to verify
40、 correctness before fabricating Spatial thinking Structural diagrams Data sheets,29,Temporal vs. spatial thinking,After synthesis “describe-and-synthesize” era Designers work primarily in behavioral domain “describe and synthesize” era Describe FSMDs or sequential programs Synthesize into structure
41、Temporal thinking States or sequential statements have relationship over time Strong understanding of hardware structure still important Behavioral description must synthesize to efficient structural implementation,30,Verification,Ensuring design is correct and complete Correct Implements specificat
42、ion accurately Complete Describes appropriate output to all relevant input Formal verification Hard For small designs or verifying certain key properties only Simulation Most common verification method,31,Formal verification,Analyze design to prove or disprove certain properties Correctness example
43、Prove ALU structural implementation equivalent to behavioral description Derive Boolean equations for outputs Create truth table for equations Compare to truth table from original behavior Completeness example Formally prove elevator door can never open while elevator is moving Derive conditions for
44、 door being open Show conditions conflict with conditions for elevator moving,32,Simulation,Create computer model of design Provide sample input Check for acceptable output Correctness example ALU Provide all possible input combinations Check outputs for correct results Completeness example Elevator
45、 door closed when moving Provide all possible input sequences Check door always closed when elevator moving,33,Increases confidence,Simulating all possible input sequences impossible for most systems E.g., 32-bit ALU 232 * 232 = 264 possible input combinations At 1 million combinations/sec million y
46、ears to simulate Sequential circuits even worse Can only simulate tiny subset of possible inputs Typical values Known boundary conditions E.g., 32-bit ALU Both operands all 0s Both operands all 1s Increases confidence of correctness/completeness Does not prove,34,Advantages over physical implementat
47、ion,Controllability Control time Stop/start simulation at any time Control data values Inputs or internal values Observability Examine system/environment values at any time Debugging Can stop simulation at any point and: Observe internal values Modify system/environment values before restarting Can
48、step through small intervals (i.e., 500 nanoseconds),35,Disadvantages,Simulation setup time Often has complex external environments Could spend more time modeling environment than system Models likely incomplete Some environment behavior undocumented if complex environment May not model behavior cor
49、rectly Simulation speed much slower than actual execution Sequentializing parallel design IC: gates operate in parallel Simulation: analyze inputs, generate outputs for each gate 1 at time Several programs added between simulated system and real hardware 1 simulated operation: = 10 to 100 simulator operations = 100 to 10,000 operating system operations = 1,000 to 100,000 hardware operations,36,Simulation speed,Relative speeds of different types of simulation/emulation 1 hour actual execution of SOC = 1.2 years instruction-set simulation = 10,000,000 hours gate-level simulation,
