《电子工程师手册》学习资料（英文版）chapter 34 Digital and Analog Electronic Design Automation.pdf_大学文库

34 Digital and analog Electronic Design Automation 34.1 Introduction 34.2 Design Entry ming Analysis. Simulation. Analog Simulation. Emulation 34.6 Test Allen Dewey Fault Modeling.Fault Testing Duke University 34.1 Introduction The field of design automation(DA)technology, also commonly called computer-aided design(CAD)or mputer-aided engineering(CAE), involves developing computer programs to conduct portions of product design and manufacturing on behalf of the designer. Competitive pressures to produce more efficiently new generations of products having improved function and performance are motivating the growing importance of DA. The increasing complexities of microelectronic technology, shown in Fig 34. 1, illustrate the importance of relegating portions of product development to computer automation [Barbe, 1980] Advances in microelectronic technology enable over 1 million devices to be manufactured on an integrated circuit that is smaller than a postage stamp; yet the ability to exploit this capability remains a challenge. Manual design techniques are unable to keep pace with product design cycle demands and are being replaced by automated design techniques [ Saprio, 1986; Dillinger, 1988] Figure 34.2 rizes the historical development of DA technology. DA computer programs are often imply called applications or tools. DA efforts started in the early 1960s as academic research projects and captive industrial programs; these efforts focused on tools for physical and logical design. Follow-on developments extended logic simulation to more-detailed circuit and device simulation and more-abstract functional simula tion. Starting in the mid to late 1970s, new areas of test and synthesis emerged and vendors started offering commercial DA products. Today, the electronic design automation(EDA)industry is an international business with a well-established and expanding technical base [Trimberger, 1990]. EDA will be examined by presenting an overview of the following area Verification Physical design, and c 2000 by CRC Press LLC

© 2000 by CRC Press LLC 34 Digital and Analog Electronic Design Automation 34.1 Introduction 34.2 Design Entry 34.3 Synthesis 34.4 Verification Timing Analysis • Simulation • Analog Simulation • Emulation 34.5 Physical Design 34.6 Test Fault Modeling • Fault Testing 34.7 Summary 34.1 Introduction The field of design automation (DA) technology, also commonly called computer-aided design (CAD) or computer-aided engineering (CAE), involves developing computer programs to conduct portions of product design and manufacturing on behalf of the designer. Competitive pressures to produce more efficiently new generations of products having improved function and performance are motivating the growing importance of DA. The increasing complexities of microelectronic technology, shown in Fig. 34.1, illustrate the importance of relegating portions of product development to computer automation [Barbe, 1980]. Advances in microelectronic technology enable over 1 million devices to be manufactured on an integrated circuit that is smaller than a postage stamp; yet the ability to exploit this capability remains a challenge. Manual design techniques are unable to keep pace with product design cycle demands and are being replaced by automated design techniques [Saprio, 1986; Dillinger, 1988]. Figure 34.2 summarizes the historical development of DA technology. DA computer programs are often simply called applications or tools. DA efforts started in the early 1960s as academic research projects and captive industrial programs; these efforts focused on tools for physical and logical design. Follow-on developments extended logic simulation to more-detailed circuit and device simulation and more-abstract functional simulation. Starting in the mid to late 1970s, new areas of test and synthesis emerged and vendors started offering commercial DA products. Today, the electronic design automation (EDA) industry is an international business with a well-established and expanding technical base [Trimberger, 1990]. EDA will be examined by presenting an overview of the following areas: • Design entry, • Synthesis, • Verification, • Physical design, and • Test. Allen Dewey Duke University

Digital System Block Diagram FIGURE 34.7 State diagram. Design entry mechanisms for electrical and logical abstractions are collectively called schematic cap chniques. Schematic capture defines hierarchical structures, commonly called netlists, of components. A designer creates instances of components supplied from a library of predefined components and connects component pins or ports via wires [Douglas-Young, 1988; Pechet 1991 The functional level abstracts logical elements into corresponding computational units, such as registers, multiplexers, and arithmetic logic units(ALUs). The architectural level abstracts functional information into computational algorithms or paradigms. Examples of common computational paradigms are listed below State diagrams Petri nets, Control/data flow graphs, Function tables sion diagrams. These higher levels of abstraction support a more expressive, higher-bandwidth"communication interface between engineers and DA programs. Engineers can focus their creative, cognitive skills on concept and ehavior, rather than on the complexities of detailed implementation. Associated design entry mechanisms typically use hardware description languages with a combination of textual and graphic techniques [ Birtwistle and Subrahmanyan, 1988] Figure 34.7 shows an example of a simple state diagram. The state diagram defines three states, denoted by circles. State-to-state transitions are denoted by labeled arcs; state transitions depend on the present state and the input X. The output, Z, per state is given within each state. Since the output is dependent on only the present state, the digital system is classified as a Moore finite state machine. If the output is dependent on the present state and input, then the digital system is classified as a Mealy finite state machine A hardware description language model written in VHDL of the Moore finite state machine is given in Fig. 34.8. The VHDL model, called a design entity, uses a"data flow"description style to describe the state machine[Dewey, 1983, 1992, 1997]. The entity statement defines the interface, i. e, the ports. The ports include two input signals, X and CLK, and an output signal Z. The ports are of type BiT, which specifies that the signals may only carry the values 0 or 1. The architecture statement defines the input/output transform via two concurrent signal assignment statements. The internal signal STATE holds the finite state information and is driven by a guarded, conditional concurrent signal assignment statement that executes when the associated (CLK='I and not CLKSTABLE is true, which is only on the rising edge of the signal CLK STABLE is a predefined attribute of the signal CLK CLK'STABLE is true if CLK has not changed value. Thus, if"not CLK'STABLE" is true, meaning that CLK has

© 2000 by CRC Press LLC Design entry mechanisms for electrical and logical abstractions are collectively called schematic capture techniques. Schematic capture defines hierarchical structures, commonly called netlists, of components. A designer creates instances of components supplied from a library of predefined components and connects component pins or ports via wires [Douglas-Young, 1988; Pechet, 1991]. The functional level abstracts logical elements into corresponding computational units, such as registers, multiplexers, and arithmetic logic units (ALUs). The architectural level abstracts functional information into computational algorithms or paradigms. Examples of common computational paradigms are listed below: • State diagrams, • Petri nets, • Control/data flow graphs, • Function tables, • Spreadsheets, and • Binary decision diagrams. These higher levels of abstraction support a more expressive, “higher-bandwidth” communication interface between engineers and DA programs. Engineers can focus their creative, cognitive skills on concept and behavior, rather than on the complexities of detailed implementation. Associated design entry mechanisms typically use hardware description languages with a combination of textual and graphic techniques [Birtwistle and Subrahmanyan, 1988]. Figure 34.7 shows an example of a simple state diagram. The state diagram defines three states, denoted by circles. State-to-state transitions are denoted by labeled arcs; state transitions depend on the present state and the input X. The output, Z, per state is given within each state. Since the output is dependent on only the present state, the digital system is classified as a Moore finite state machine. If the output is dependent on the present state and input, then the digital system is classified as a Mealy finite state machine. A hardware description language model written in VHDL of the Moore finite state machine is given in Fig. 34.8. The VHDL model, called a design entity, uses a “data flow” description style to describe the state machine [Dewey, 1983, 1992, 1997]. The entity statement defines the interface, i.e., the ports. The ports include two input signals, X and CLK, and an output signal Z. The ports are of type BIT, which specifies that the signals may only carry the values 0 or 1. The architecture statement defines the input/output transform via two concurrent signal assignment statements. The internal signal STATE holds the finite state information and is driven by a guarded, conditional concurrent signal assignment statement that executes when the associated block expression (CLK=’1’ and not CLK’STABLE) is true, which is only on the rising edge of the signal CLK. STABLE is a predefined attribute of the signal CLK; CLK’STABLE is true if CLK has not changed value. Thus, if “not CLK’STABLE” is true, meaning that CLK has FIGURE 34.7 State diagram

entity statement entity MOORE MAChine port(X, CLK: in BIT; Z: out BIT); end MOORE MACHINE architecture statement architecture fsm of moore machine is type STATE_TYPE is(A, B, C) signal STATE: STATE_TYPE: =A; beg NEXT STATE block(CLK='1 and not CLKSTABLE) guarded conditional concurrent signal assignment statement STATE<=guarded B when(STATE=A and X='1 )else C when (STATE=B and X=0)else A when(STATE=C)else STATE; end block NEXT state unguarded selected concurrent signal assignment statement with STATE select Z<=°0 when a, °0 when B, 1 when C: end FSM: FIGURE 34. 8 VHDL model just changed value, and"CLK=, " then a rising transition has occurred on CLK. The output signal Z is driven by a nonguarded, selected concurrent signal assignment statement that executes any time STATE changes value. 34.3 Synthesis Figure 34.9 shows that the synthesis task generally follows the design entry task. After describing the desired system via design entry, synthesis Da programs are invoked to assist generating the required detailed design. of abstraction to another, more-detailed level of abstraction The more-detailed level of abstraction may be only an inter- Synthesis mediate step in the entire design process, or it may be the final implementation. Synthesis programs that yield a final that yield a final FIGURE 34.9 Design process - synthesis. implementation are sometimes called silicon compilers because the programs generate sufficient detail to proceed directly to silicon fabrication[Ayres, 1983; Gajski, 1988] Like design abstractions, synthesis techniques can be hierarchically categorized, as shown in Fig. 34.10. The higher levels of synthesis offer the advantage of less complexity, but also the disadvantage of less control over the final design. Algorithmic synthesis, also called behavioral synthesis, addresses"multicycle"behavior, which means behavior ore than one control step. A control step equates to a clock cycle of a synchronous, sequential digital ystem, i.e., a state in a finite-state machine controller or a microprogram step in a microprogrammed controller. c 2000 by CRC Press LLC

© 2000 by CRC Press LLC just changed value, and “CLK=’1’,” then a rising transition has occurred on CLK. The output signal Z is driven by a nonguarded, selected concurrent signal assignment statement that executes any time STATE changes value. 34.3 Synthesis Figure 34.9 shows that the synthesis task generally follows the design entry task. After describing the desired system via design entry, synthesis DA programs are invoked to assist generating the required detailed design. Synthesis translates or transforms a design from one level of abstraction to another, more-detailed level of abstraction. The more-detailed level of abstraction may be only an intermediate step in the entire design process, or it may be the final implementation. Synthesis programs that yield a final implementation are sometimes called silicon compilers because the programs generate sufficient detail to proceed directly to silicon fabrication [Ayres, 1983; Gajski, 1988]. Like design abstractions, synthesis techniques can be hierarchically categorized, as shown in Fig. 34.10. The higher levels of synthesis offer the advantage of less complexity, but also the disadvantage of less control over the final design. Algorithmic synthesis, also called behavioral synthesis, addresses “multicycle” behavior, which means behavior that spans more than one control step. A control step equates to a clock cycle of a synchronous, sequential digital system, i.e., a state in a finite-state machine controller or a microprogram step in a microprogrammed controller. -- entity statement entity MOORE_MACHINE is port (X, CLK : in BIT; Z : out BIT); end MOORE_MACHINE; -- architecture statement architecture FSM of MOORE_MACHINE is type STATE_TYPE is (A, B, C); signal STATE : STATE_TYPE := A; begin NEXT_STATE: block (CLK=’1’ and not CLK’STABLE) begin -- guarded conditional concurrent signal assignment statement STATE <= guarded B when (STATE=A and X=’1’) else C when (STATE=B and X=’0’) else A when (STATE=C) else STATE; end block NEXT_STATE; -- unguarded selected concurrent signal assignment statement with STATE select Z <= ‘0’ when A, ‘0’ when B, ‘1’ when C; end FSM; FIGURE 34.8 VHDL model. FIGURE 34.9 Design process — synthesis

Register Transfer Register Allocation Finite State Machine Synthesis Redundancy Removal Technology Mapping FIGURE 34.10 Taxonomy of synthesis techniques. Algorithmic synthesis typically accepts sequential design descriptions that define an input/output transform, but provide little information about the parallelism of the final design [Camposano and wolfe, 1991; Gajski etal,1992] Partitioning decomposes the design description into smaller behaviors. Partitioning is an example of a high level transformation. High-level transformations include common software programming compiler optimiz tions,such as loop unrolling, subprogram in-line expansion, constant propagation, and common subexpression Resource allocation associates behaviors with hardware computational units, and scheduling determines the order in which behaviors execute. Behaviors that are mutually exclusive can potentially share computational performed using a variety of graph clique coverin Allocation and scheduling are interdependent, and different synthesis strategies perform allocation and sched uling different ways. Sometimes scheduling is performed first, followed by allocation; sometimes allocation is performed first, followed by scheduling; and sometimes allocation and scheduling are interleaved Scheduling assigns computational units to control steps, thereby determining which behaviors execute in which clock cycles. At one extreme, all computational units can be assigned to a single control step, exploiting maximum concurrency. At the other extreme, computational units can be assigned to individual control steps, exploiting maximum sequentiality. Several popular scheduling algorithms are listed below As-soon-as-p List scheduling Force-directed scheduling, and Control step splitting/merging. ASAP and ALAP scheduling algorithms order computational units based on data dependencies List schedulin is based on ASAP and ALAP scheduling, but considers additional, more-global constraints, such as maximum number of control steps. Force-directed scheduling computes the probabilities of computational units assigned to control steps and attempts to evenly distribute computation activity among all control steps Control step splitting starts with all computational units assigned to one control step and generates a schedule by splitting the computational units into multiple control steps Control step merging starts with all computational units assigned to individual control steps and generates a schedule by merging or combining units and steps [ Paulin and Knight, 1989; Camposano and Wolfe, 1991 Register transfer synthesis takes as input the results of algorithmic synthesis and addresses "per-cycle behavior, which means the behavior during one clock cycle. Register transfer synthesis selects logic to realize the hardware computational units generated during algorithmic synthesis, such as realizing an addition oper ation with a carry-save adder or realizing addition and subtraction operations with an arithmetic logic unit

© 2000 by CRC Press LLC Algorithmic synthesis typically accepts sequential design descriptions that define an input/output transform, but provide little information about the parallelism of the final design [Camposano and Wolfe, 1991; Gajski et al., 1992]. Partitioning decomposes the design description into smaller behaviors. Partitioning is an example of a highlevel transformation. High-level transformations include common software programming compiler optimizations, such as loop unrolling, subprogram in-line expansion, constant propagation, and common subexpression elimination. Resource allocation associates behaviors with hardware computational units, and scheduling determines the order in which behaviors execute. Behaviors that are mutually exclusive can potentially share computational resources. Allocation is performed using a variety of graph clique covering or node coloring algorithms. Allocation and scheduling are interdependent, and different synthesis strategies perform allocation and scheduling different ways. Sometimes scheduling is performed first, followed by allocation; sometimes allocation is performed first, followed by scheduling; and sometimes allocation and scheduling are interleaved. Scheduling assigns computational units to control steps, thereby determining which behaviors execute in which clock cycles. At one extreme, all computational units can be assigned to a single control step, exploiting maximum concurrency. At the other extreme, computational units can be assigned to individual control steps, exploiting maximum sequentiality. Several popular scheduling algorithms are listed below: • As-soon-as-possible (ASAP), • As-late-as-possible (ALAP), • List scheduling, • Force-directed scheduling, and • Control step splitting/merging. ASAP and ALAP scheduling algorithms order computational units based on data dependencies. List scheduling is based on ASAP and ALAP scheduling, but considers additional, more-global constraints, such as maximum number of control steps. Force-directed scheduling computes the probabilities of computational units being assigned to control steps and attempts to evenly distribute computation activity among all control steps. Control step splitting starts with all computational units assigned to one control step and generates a schedule by splitting the computational units into multiple control steps. Control step merging starts with all computational units assigned to individual control steps and generates a schedule by merging or combining units and steps [Paulin and Knight, 1989; Camposano and Wolfe, 1991]. Register transfer synthesis takes as input the results of algorithmic synthesis and addresses “per-cycle” behavior, which means the behavior during one clock cycle. Register transfer synthesis selects logic to realize the hardware computational units generated during algorithmic synthesis, such as realizing an addition operation with a carry–save adder or realizing addition and subtraction operations with an arithmetic logic unit. FIGURE 34.10 Taxonomy of synthesis techniques

ata that must be retained across multiple clock cycles are identified, and registers are allocated to hold the data. Finally, finite-state machine synthesis involves state minimization and state assignment State minimization seeks to eliminate redundant or equivalent states, and state assignment assigns binary encodings for states to minimize combinational logic [Brayton et al., 1992; Sasao, 1993] Logic synthesis optimizes the logic generated by register transfer synthesis and maps the optimized logic operations onto physical gates supported by the target fabrication technology. Technology mapping considers the foundry cell library and associated electrical restrictions, such as fan-in/fan-out limitations 34. 4 Verification Figure 34.11 shows that the verification task generally follows the synthesis task. The verification task checks the correctness of the function and performance of a design to ensure that an intermediate or final de faithfully realizes the initial, desired specification. Three major types of verification are listed below: Timing analysis, Simulation, an Timing analysis Timing analysis checks that the overall design satisfies operating speed requirements and that individual sig nals within a design satisfy transition requirements. Common signal transition requirements, also called Design Entry timing hazards, include rise and fall times, propagation delays, clock periods, race conditions, glitch detection, nd setup and hold times. For instance, setup and hold times specify relationships between data and control ignals to ensure that memory devices(level latches or edge-sensitive flip-flops)correctly and reli ably store desired data. The data signal carrying the information to be stored in the memory device must FIGURE 34.11 Design process-verification be stable for a period equal to the setup time prior to ne control signal transition to ensure that the correct value is sensed by the memory device. Also, the data signal must be stable for a period equal to the hold time after the control signal transition to ensure that the memory device has enough time to store the sensed value Another class of timing transition requirements, commonly called signal integrity checks, include reflection crosstalk, ground bounce, and electromagnetic interference. Signal integrity checks are typically required for gh-speed designs operating at clock frequencies above 75 MHz. At such high frequencies, the transmission line behavior of wires must be analyzed. A wire should be properly terminated, i. e, connected, to a port having an impedance matching the wire characteristic impedance to prevent signal reflections. Signal reflections are portions of an emanating signal that"bounce back " from the destination to the source Signal reflections reduce the power of the emanating signal and can damage the source. Crosstalk refers to unwanted reactive coupling tween physically adjacent signals, providing a connection between signals that are supposed to be electrically isolated. Ground bounce is another signal integrity problem. Since all conductive material has a finite pedance, a ground signal network does not in practice offer the exact same electrical potential throughout n entire design. These potential differences are usually negligible because the distributive impedance of the ground signal network is small compared with other finite-component impedances. However, when many ignals switch value simultaneously, a substantial current can flow through the ground signal network. High intermittent currents yield proportionately high intermittent potential drops, i.e., ground bounces, which can c 2000 by CRC Press LLC

© 2000 by CRC Press LLC Data that must be retained across multiple clock cycles are identified, and registers are allocated to hold the data. Finally, finite-state machine synthesis involves state minimization and state assignment. State minimization seeks to eliminate redundant or equivalent states, and state assignment assigns binary encodings for states to minimize combinational logic [Brayton et al., 1992; Sasao, 1993]. Logic synthesis optimizes the logic generated by register transfer synthesis and maps the optimized logic operations onto physical gates supported by the target fabrication technology. Technology mapping considers the foundry cell library and associated electrical restrictions, such as fan-in/fan-out limitations. 34.4 Verification Figure 34.11 shows that the verification task generally follows the synthesis task. The verification task checks the correctness of the function and performance of a design to ensure that an intermediate or final design faithfully realizes the initial, desired specification. Three major types of verification are listed below: • Timing analysis, • Simulation, and • Emulation. Timing Analysis Timing analysis checks that the overall design satisfies operating speed requirements and that individual signals within a design satisfy transition requirements. Common signal transition requirements, also called timing hazards, include rise and fall times, propagation delays, clock periods, race conditions, glitch detection, and setup and hold times. For instance, setup and hold times specify relationships between data and control signals to ensure that memory devices (level-sensitive latches or edge-sensitive flip-flops) correctly and reliably store desired data. The data signal carrying the information to be stored in the memory device must be stable for a period equal to the setup time prior to the control signal transition to ensure that the correct value is sensed by the memory device. Also, the data signal must be stable for a period equal to the hold time after the control signal transition to ensure that the memory device has enough time to store the sensed value. Another class of timing transition requirements, commonly called signal integrity checks, include reflections, crosstalk, ground bounce, and electromagnetic interference. Signal integrity checks are typically required for high-speed designs operating at clock frequencies above 75 MHz. At such high frequencies, the transmission line behavior of wires must be analyzed. A wire should be properly terminated, i.e., connected, to a port having an impedance matching the wire characteristic impedance to prevent signal reflections. Signal reflections are portions of an emanating signal that “bounce back” from the destination to the source. Signal reflections reduce the power of the emanating signal and can damage the source. Crosstalk refers to unwanted reactive coupling between physically adjacent signals, providing a connection between signals that are supposed to be electrically isolated. Ground bounce is another signal integrity problem. Since all conductive material has a finite impedance, a ground signal network does not in practice offer the exact same electrical potential throughout an entire design. These potential differences are usually negligible because the distributive impedance of the ground signal network is small compared with other finite-component impedances. However, when many signals switch value simultaneously, a substantial current can flow through the ground signal network. High intermittent currents yield proportionately high intermittent potential drops, i.e., ground bounces, which can FIGURE 34.11 Design process — verification

5+4+2+1=1 B->C->F→>I B→>C->H>J 15+1=6 FIGURE 34 12 Block-oriented cause unwanted circuit behavior. Finally, electromagnetic interference refers to signal harmonics radiating from design components and interconnects. This harmonic radiation may interfere with other electronic equipment or may exceed applicable environmental safety regulatory limits [McHaney, 1991] iming analysis can be performed dynamically or statically. Dynamic timing analysis exercises the desig via simulation or emulation for a period of time with a set of input stimuli and records the timing behavior Static timing analysis does not exercise the design via simulation or emulation. Rather, static analysis records timing behavior based on the timing behavior, e.g., propagation delay, of the design components and their InterconnectIo Static timing analysis techniques are primarily block oriented or path oriented. Block-oriented timing analysis generates design input(also called primary input)to design output(also called primary output), and propa gation delays by analyzing the design"stage-by-stage"and by summing up the individual stage delays. All devices driven by primary inputs constitute stage 1, all devices driven by the outputs of stage 1 constitute stage 2, and so on. Starting with the first stage, all devices associated with a stage are annotated with worst case delays. A worst-case delay is the propagation delay of the device plus the delay of the last input to arrive at the device, ie,, the signal path with the longest delay leading up to the device inputs. For example, the device labeled"H" in stage 3 in Fig. 34.12 is annotated with the worst-case delay of 13, representing the device propagation delay of 4 and the delay of the last input to arrive through devices"B"and"C"of 9[Mcwilliams and Widdoes, 1978]. When the devices associated with the last stage, i. e, the devices driving the primary utputs, are processed, the accumulated worst-case delays record the longest delay from primary inputs to primary outputs, also call the critical paths. The critical path for each primary output is highlighted in Fig. 34.12. Path-oriented timing analysis generates primary input to primary output propagation delays by traversing all possible signal paths one at a time. Thus, finding the critical path via path-oriented timing analysis is equivalent to finding the longest path through a directed acyclic graph, where devices are graph vertices and interconnections are graph edges [Sasiki et al., 1978] To account for realistic variances in component timing due to manufacturing tolerances, aging, or environ- mental effects, timing analysis often provides stochastic or statistical checking capabilities. Statistical timing analysis uses random-number generators based on empirically observed probabilistic distributions to determine component timing behavior. Thus, statistical timing analysis describes design performance and the likelihood of the design performance. Simulation Simulation exercises a design over a period of time by applying a series of input stimuli and generating the associated output responses. The general event-driven, also called schedule-driven, simulation algorithm is diagrammed in Fig. 34.13. An event is a change in signal value. Simulation starts by initializing the design c 2000 by CRC Press LLC

© 2000 by CRC Press LLC cause unwanted circuit behavior. Finally, electromagnetic interference refers to signal harmonics radiating from design components and interconnects. This harmonic radiation may interfere with other electronic equipment or may exceed applicable environmental safety regulatory limits [McHaney, 1991]. Timing analysis can be performed dynamically or statically. Dynamic timing analysis exercises the design via simulation or emulation for a period of time with a set of input stimuli and records the timing behavior. Static timing analysis does not exercise the design via simulation or emulation. Rather, static analysis records timing behavior based on the timing behavior, e.g., propagation delay, of the design components and their interconnection. Static timing analysis techniques are primarily block oriented or path oriented. Block-oriented timing analysis generates design input (also called primary input) to design output (also called primary output), and propagation delays by analyzing the design “stage-by-stage” and by summing up the individual stage delays. All devices driven by primary inputs constitute stage 1, all devices driven by the outputs of stage 1 constitute stage 2, and so on. Starting with the first stage, all devices associated with a stage are annotated with worstcase delays. A worst-case delay is the propagation delay of the device plus the delay of the last input to arrive at the device, i.e., the signal path with the longest delay leading up to the device inputs. For example, the device labeled “H” in stage 3 in Fig. 34.12 is annotated with the worst-case delay of 13, representing the device propagation delay of 4 and the delay of the last input to arrive through devices “B” and “C” of 9 [McWilliams and Widdoes, 1978]. When the devices associated with the last stage, i.e., the devices driving the primary outputs, are processed, the accumulated worst-case delays record the longest delay from primary inputs to primary outputs, also call the critical paths. The critical path for each primary output is highlighted in Fig. 34.12. Path-oriented timing analysis generates primary input to primary output propagation delays by traversing all possible signal paths one at a time. Thus, finding the critical path via path-oriented timing analysis is equivalent to finding the longest path through a directed acyclic graph, where devices are graph vertices and interconnections are graph edges [Sasiki et al., 1978]. To account for realistic variances in component timing due to manufacturing tolerances, aging, or environmental effects, timing analysis often provides stochastic or statistical checking capabilities. Statistical timing analysis uses random-number generators based on empirically observed probabilistic distributions to determine component timing behavior. Thus, statistical timing analysis describes design performance and the likelihood of the design performance. Simulation Simulation exercises a design over a period of time by applying a series of input stimuli and generating the associated output responses. The general event-driven, also called schedule-driven, simulation algorithm is diagrammed in Fig. 34.13. An event is a change in signal value. Simulation starts by initializing the design; FIGURE 34.12 Block-oriented static timing analysis

Advance Time To Next event Update Pending More Events?> Evaluate All Sensitized models FIGURE 34.13 General event-driven simulation algorithm. initial values are assigned to all signals. Initial values include starting values and pending values that constitute future events. Simulation time is advanced to the next pending event(s), signals are updated, and sensitized models are evaluated [Pooch, 1993]. The process of evaluating the sensitized models yields new, potentially different, values for signals, ie, a new set of pending events. These new events are added to the list of pending events, time is advanced to the next pending event(s), and the simulation algorithm repeats. Each pass through he loop in Fig. 34.13 of evaluating sensitized models at a particular time step is called a simulation cycle. Simulation ends when the design yields no further activity, i.e., when there are no more pending events to large, complex designs I s of a 200K-gate, 20-MHz processor design. By assuming that, on average, only 10%of the total 200K gates are active or sensitized on each processor clock cycle, Eq. 34. 1 shows that simulating 1 s of actual processor time equates to 400 billion events 400 billion events =(20 million clock cycles )(200K gates)(10% activity) (341) 140 h =(400 billion) /-oInstructions )(50 million instructions event Assuming that, on average, a simulation program executes 50 computer instructions per event on a computer capable of processing 50 million instructions per second (MIP),Eq 34.1 also shows that processing 400 billion events requires 140 h or just short of 6 days. Fig 34.14 shows how simulation computation generally scales with design complexity To address the growing computational demands of simulation, several simulation acceleration techniques have been introduced Schedule-driven simulation, explained above, can be accelerated by removing layers of interpretation and running a simulation as a native executable image; such an approach is called complied scheduled-driven simulation As an alternative to schedule-driven simulation, cycle-driven simulation avoids the overhead of ever processing by evaluating all devices at regular intervals of time. Cycle-driven simulation is efficient design exhibits a high degree of concurrency, i.e., when a large percentage of the devices are active per sin cycle Based on the staging of devices, devices are rank-ordered to determine the order in which they are evaluated at each time step to ensure the correct causal behavior yielding the proper ordering of events. For functional verification, logic devices are often assigned zero-delay and memory devices are assigned unit-delay. Thus, any number of stages of logic devices may execute between system clock periods In another simulation acceleration technique, message-driven simulation, also called parallel or distributed simulation, device execution is divided among several processors and the device simulations communicate c 2000 by CRC Press LLC

© 2000 by CRC Press LLC initial values are assigned to all signals. Initial values include starting values and pending values that constitute future events. Simulation time is advanced to the next pending event(s), signals are updated, and sensitized models are evaluated [Pooch, 1993]. The process of evaluating the sensitized models yields new, potentially different, values for signals, i.e., a new set of pending events. These new events are added to the list of pending events, time is advanced to the next pending event(s), and the simulation algorithm repeats. Each pass through the loop in Fig. 34.13 of evaluating sensitized models at a particular time step is called a simulation cycle. Simulation ends when the design yields no further activity, i.e., when there are no more pending events to process. Logic simulation is computationally intensive for large, complex designs. As an example, consider simulating 1 s of a 200K-gate, 20-MHz processor design. By assuming that, on average, only 10% of the total 200K gates are active or sensitized on each processor clock cycle, Eq. 34.1 shows that simulating 1 s of actual processor time equates to 400 billion events. (34.1) Assuming that, on average, a simulation program executes 50 computer instructions per event on a computer capable of processing 50 million instructions per second (MIP), Eq. 34.1 also shows that processing 400 billion events requires 140 h or just short of 6 days. Fig. 34.14 shows how simulation computation generally scales with design complexity. To address the growing computational demands of simulation, several simulation acceleration techniques have been introduced. Schedule-driven simulation, explained above, can be accelerated by removing layers of interpretation and running a simulation as a native executable image; such an approach is called complied, scheduled-driven simulation. As an alternative to schedule-driven simulation, cycle-driven simulation avoids the overhead of event queue processing by evaluating all devices at regular intervals of time. Cycle-driven simulation is efficient when a design exhibits a high degree of concurrency, i.e., when a large percentage of the devices are active per simulation cycle. Based on the staging of devices, devices are rank-ordered to determine the order in which they are evaluated at each time step to ensure the correct causal behavior yielding the proper ordering of events. For functional verification, logic devices are often assigned zero-delay and memory devices are assigned unit-delay. Thus, any number of stages of logic devices may execute between system clock periods. In another simulation acceleration technique, message-driven simulation, also called parallel or distributed simulation, device execution is divided among several processors and the device simulations communicate FIGURE 34.13 General event-driven simulation algorithm. 400 billion events = (20 million clock cycles)(200K gates)(10% activity) 140 h (400 billion events) 50 instructions event ----------------------------------- Ë ¯ Ê ˆ 50 million instructions s ----------------------------------------------------- Ë ¯ Ê ˆ =