BACKGROUND OF THE INVENTION
Simulating the behavior of a proposed or actual design reduces the effort required to realize and maintain the design. Before expending the time and resources to realize a design, designers may compare the desired and predicted behavior of a design using simulation. After realizing the system into dedicated hardware and software and throughout the design's lifecycle, simulation facilitates understanding of unexpected design behaviors and subsequent evaluation of proposed design modifications.
When designers employ a general purpose computer or special purpose simulation accelerator to conduct simulation, the simulated design behavior is usually many times slower than the realized design. Using simulation to predict the design's behavior over lengthy periods of simulated time generally requires undesirably long periods of actual or wallclock time, perhaps consuming days to simulate a mere second in the lifetime of the realized design. Delays before simulation results are available incur an expense in time, an expense in computing resources and delay initial design realization or modification. Therefore methods for improving simulation speed and accuracy, such as those taught in the present invention, are useful and valuable.
Design behavior may be simulated at many different levels of detail. Abstract models of design behavior, with comparatively little detail generally simulate comparatively fast. By adding more detail to the model of a design, the predicted and actual design behavior generally converge while the rate of simulated and actual design behavior diverge. Equivalently, simulation generally becomes increasingly slower as the accuracy of detail increases.
The most abstract simulations, and thus faster simulations, generally approximate the design's state to discrete values in both value and time. Such simulations are commonly known as “digital”. Simulations with more accurate detail represent a design using continuous values and time. Such continuous simulations are known as “analog”. Due to the speed penalty associated with analog simulation, large system simulations typically utilize a mixture of digital and analog simulation techniques, known as mixedsignal simulation. Simulations using a mixture of digital and analog detail are known as “mixed signal”. The most accurate simulations represent a design using physically continuous fields and wave propagation, such as electronic and magnetic fields embodied in Maxwell's equations (and continuity equations). Such accurate but slow simulations are often known as “full-wave” simulations.
More detailed simulations are not only slower, they impose a significant effort on the design team in order to accurately “model” a system's behavior so that it can be simulated. Designers or model extraction tools typically represent a design's behavior using one or more modeling languages. Structure modeling languages, such as SPICE, represent a system in terms of flat or hierarchically connected components. A structural modeling language represents terminal components using behavioral models described using a conventional programming language, such as C or Fortran, or a behavioral modeling language, such as VHDL or Verilog (digital), VHDL-AMS or Verilog-AMS (mixed signal). Radio frequency and microwave (RF/MW) languages, perhaps augmenting a base language such as VHDL-AMS or Verilog-AMS, typically add modeling language features such as means for modeling distributed (rather than lumped) parameter components, means for component modeling in the frequency domain (rather than just the time domain) and means of effectively modeling noise and parasitic interactions.
A conventional programming language or behavioral modeling language represents system behavior using terminals, branches and equations representing an implicit relationship between quantities (the implicit relationship embodied as Kirchoff's laws for the analog and mixed signal or Maxwell's and continuity equations for full-wave modeling). Terminals, sometimes known as “nodes”, represent the connection point between two or more branches. The network formed by terminals connected by branches may be represented as one or more disconnected graphs embodying terminals and branches with associated across quantities, such as voltage, and through quantities or contributions, such as current.
FIG. 1 represents the relationship between terminals (such as 152, 154, 156, 159, 162, 164, 166 and 168), branches (such as 153, 155, 157, 158, 163, 165, 167, 169) and implied quantities such as through quantity Q2 (172) or across quantity Q1 (151). Well known techniques provide for partitioning analog models which do not share terminals, branches or quantities, such as the partitions marked 150 and 169 in FIG. 1. Recognizing such partitions early in the compilation process will become useful in the present invention; means for recognizing such disconnected partitions are well-known.
Beyond a structural view embodied in terminals, branches and quantities, analog modeling languages enable declaration and reference to continuously valued state variable quantities representing physical properties, such as voltage or current, and quantities implicitly or explicitly derived from such quantities. Mixed signal modeling languages enable reference to digital objects such as signals, shared variables, registers and comparable, discretely-valued objects. Such digital objects may be contained in a distinct digital partition, such as 170 in FIG. 1 and referenced from both the digital partition and zero or more analog partitions, such as 150 or 169 in FIG. 1.
Source code references in a model using a mixed signal language, such as VHDL-AMS, Verilog-AMS or MAST, typically take the form of one or more constraints relating left and right hand side expressions at a specific instant in time to within an implicit or explicit tolerance. Sets of such equations referencing common quantities and digital objects (a partition) are commonly known as systems of equations, characteristic equations, simultaneous equations or constraint equations. Without loss of generality we will refer to these as equation systems in the following.
Many designs of practical interest build on algebraic differential equations by using integrals and differentials of quantities with respect to time (ordinary differential equations) or other state variables (partial differential equations). Three examples will help to illustrate the key differences. An idealized voltage source and resistor tree used as a voltage divider can readily be described using an algebraic equation system. A perfect capacitor integrates change over time, requiring an ordinary differential equation to describe an idealized voltage source driving a resistor and capacitor design. A pair of conductors in close proximity, driven by distinct signal sources generally requires a partial differential equation to model the voltage induced by one conductor on the second conductor.
The behavior of an analog partition may be modeled in the time domain (primary independent variable is time) or in the frequency domain (primary independent variable is frequency). For example the behavior of a voltage-controlled oscillator may be most conveniently modeled in the time domain whereas the transfer function of a filter or amplifier may be most easily and compactly captured in the frequency domain. The prior art effectively addresses many aspects of modeling in either domain, however prior art does not effectively address tight integration of digital inputs, analog time domain behavior and analog frequency domain behavior into a common analog partition or partitions.
Techniques are well-known to convert structural representations, such as commonly evolve from use of the SPICE modeling language using terminals and branches, into systems of equations. With this well-accepted transformation in mind, further discussion will speak of equation systems with the understanding that these systems may originate in many forms, including structural and graph-oriented languages.
The left or right hand side of inequalities within an equation system may result from evaluation of substantially complex expressions involving constructs such as procedural control flow, conditional statements and analog events. Without loss of generality, such notations may be compiled into a variety of equivalent forms corresponding to sets of equation systems where an expression and evolving state may be evaluated to identify an active equation system at any instant in time from among the set of equation systems potentially modeling an analog, mixed-signal or full-wave partition's behavior. Each such equation includes one or more language-defined means for evaluating an identifiable value or range of values on the left and right side of each inequality within the equation system. Such values are generally known to have either scalar or composite type.
From one instant in time to another, both quantity values and the equation system which is active within a set of equations systems describing an analog partition may change. The change may be implicit in the set of equations and therefore must be detected during simulation or may be explicitly denoted, as with a “break” statement denoting an expected discontinuity. For example, the model of a digital to analog converter commonly has such instantaneous discontinuities explicitly corresponding to changes in the digital value which is to be converted by the design into an analog value.
Behavioral, mixed-signal modeling languages, such as VHDL-AMS and Verilog-AMS, interleave or alternate simulation of analog and digital design partitions, increasing the opportunity for discontinuities between quantity values at two successive points in time. Digital values may be referenced in an analog partition by direct reference (such as VHDL-AMS) or by explicit interface mechanisms (such as Verilog-AMS). Analog quantities may be referenced in a digital partition directly, via threshold language mechanisms (such as VHDL-AMS) or via more complex interface mechanisms (such as Verilog-AMS).
Although common mixed signal modeling languages provide a wide variety of lexical and syntactic abbreviations which expand during analysis into equivalent sets of equation systems or sequential, imperative processes, the case of physically distributed terminals represent a very important exception. Modeling detail required to accurately represent such constructs depends critically on the operating frequency and other context generally only known during simulation. For example, accurate models of a transmission line expand at low frequency from a lumped parameter to a complex distributed parameter model at higher operating frequencies. In a like manner, an antenna's radiation pattern expands from a trivial, open-circuit static model at DC to a complex finite element model within interactions described by Maxwell's equations and continuity at more interesting frequencies.
From the standpoint of modeling practicality and accuracy, it is very useful for a design team to employ an incremental evolution of partition modeling detail, based on the design and thus simulation's actual operating domain, from a digital view, through an analog lumped parameter component model view, through a distributed parameter component model view, into a full-wave model view. Knowledge of the changing implementation internal to the component is then primarily modeled by a technology specialist associated with the design effort. Such a technology encapsulation and encapsulated continuity of views is not found in prior art. Anticipating this innovative modeling language step, we will thus consider the definition of analog partitions to embrace components of the partition which are lumped, distributed or full-wave in detail without loss of generality.
While representational languages and simulators exist to capture and simulate high-frequency phenomena, simulation delivers greater utility to a designer when high-frequency phenomena (lumped, analog and full-wave views) are transparently, selectively and semi-automatically conditionally introduced into the design representation in which the remainder of the system has been represented, using languages such as VHDL, VHDL-AMS, Verilog and Verilog-AMS. VHDL already provides a descriptive language mechanism by which physical phenomena such digital phenomena as tri-state and open-collector/emitter interconnect technology may be semi-transparently introduced into simulation while being ignored during uses such as the synthesis of hardware. The mechanisms are known as “resolution” functions.
VHDL resolution functions for digital interconnects, well-known prior art, may be associated with an existing type to form a new, resolved, subtype. The new, resolved subtype may then be used to define a “resolved signal”. At a specific point in time, the signal may appear on the left hand side (assignment target) of digital equations. After all assignments have taken place at each identifiable point in time at which any equations assign to the specific resolved signal, the resolution function originally associated with the signals subtype conceptually executes. Execution of this resolution function takes specific assigned values to the signal as inputs and returns a resolved value representing the tri-state, open-collector or other resolution behavior. The array of inputs and resolution function return value may either be an array of scalar types resolved to a scalar type or may hierarchically resolve a composite type consisting of zero or more composite scalar types.
The number of distinct inputs to a resolution function may not be known until after a system begins simulation. Some inputs to a resolution function may not actually be assigned at all or may not be assigned during a specific period of time. Conversely, during simulation additional drivers may be added which assign to a signal. Addition may occur as a result of executing the mixed signal design representation or more commonly through execution of a programming language fragment introduced through a programming language interface (PLI) to the system representation. In the prior art, code generated to perform simulation must accommodate the worst case resolution context and thus is less efficient than if code was generated for the actual number of active inputs to the resolution functions. Commonly resolved signals are driven by an expression's left hand side (or functionally equivalent left hand sides within a process) via the process equivalent's driver. Often the resolution function call for such signals may be eliminated or significantly simplified, for example if there is only one driver, thus improving performance.
During elaboration of a design hierarchy, the worst case number of drivers to a signal will be known in the absence of programming language interface calls creating a new driver. During a particular instant of simulation time, the exact number of drivers will be known. Unfortunately in the prior art, code implementing the resolution is commonly fixed prior to elaboration or at best prior to simulation. Thus the code implementing resolution embodies efficiencies associated with the more general case rather than the actual use. In the average case, this flexibility slows simulation.
Most analog design partitions of practical interest are non-linear. Non-linear systems include terms within their system of equations which depend on quantities or expressions involving quantities taken to powers other than one. For example, a non-linear component model may depend on the square of the voltage across a pair of terminals. Systems comprising non-linear components are computationally more complex to simulate and thus slower than linear system simulations.
Thus without loss of generality, in the following we may consider designs to be modeled using zero or more analog partitions and zero or more digital partitions. Each partition may refer to digital objects (such as signals or shared variables), analog objects (such as quantities or terminals) or values derived from these objects. Generally analog partitions and full wave partitions (subset of analog partitions) set the value of analog objects. Digital partitions set the value of digital objects. Sets of equation systems, of which one is identifiably active at any instant in time, represent behavior of each analog partition. Sets of concurrent processes, each conceptually having a sequential and imperative behavior, represent behavior of each digital partition. So as to focus on the innovations offered herein, the following will focus on this generalized representation of the design's model without implying exclusion of various equivalent design representations.
The set of all objects (analog and digital) referenced by a partition forms an operating space, such as the example shown in FIG. 2. The domain of values which a given object may assume (based on its subtype) forms an axis of the operating space (such as 50, 51 or 52 in FIG. 2). A partition's operating space has one dimension for each scalar element of each object. The three dimensions shown in the example of FIG. 2 correspond to two analog quantities A (50) and B (51) and open digital object, perhaps a signal (52).
Each dimension of the partition's operating space may be divided. When combined with divisions of other dimensions, this forms a subspace of the operating space or an operating context (by which it will be subsequently known). Operating points contained within a single context have closely related values.
During intervals time during simulation of a design's behavior, the observed object values can be contained within an operating context. Within the operating context, the non-linear system of characteristic equations can be approximated by a linear model. Techniques for deriving such approximations, known as “linearization” techniques, are well-known in the literature. At any point in a simulation, the analog partition is operating in a single, identifiable operating context with a corresponding linearization of an equation system (currently) representing the analog partition's behavioral model.
For the models of most designs, over time the analog partition will evolve during simulation through multiple operating contexts, corresponding to multiple linearizations of equation system(s). However as simulation continues, the total set of operating contexts being traversed typically develops a working set of operating contexts which encountered repeatedly, generally to the exclusion of new operating contexts.
Prior art commonly transforms equation systems, prior to the onset of simulation, into various implementations relating across and through quantity vectors by a sparse matrix. A sparse matrix implementation takes advantage of many zero-valued “conductance” matrix values to achieve substantially more compact representations than the square of the array dimensions would imply. Prior art teaches a variety of transformations on the sparse matrix representations which reduce the magnitude of off-diagonal elements (toward zero) and thus accelerate simulation. However for designs of practical interest, the off-diagonal elements of the conductance matrix are seldom all zero.
During simulation, software commonly known as an “analog-solver” iterates through an interpretation of the sparse matrix so as to identify across and through quantity values immediately consistent with the system of equations compiled into the sparse matrix formulation (and thus representing the analog partition's immediate model behavior). Integration and differentiation techniques for handling equation terms which are the time differential (such as an inductor model) or time integral of quantities (such as a capacitor model) are a well-documented aspect of the prior art.
Numerous techniques for approximating equivalence between left and right hand sides of a transformed characteristic equation by adjusting quantity values are another well-documented aspect of the prior art central to implementation of an analog solver. If transformed sides of a characteristic equation were required to match exactly at the end of each successful analog solver cycle, many simulations would fail to converge and thus terminate after reaching an iteration or time limit. At the possible expense of long-term simulation accuracy, most analog and mixed-signal modeling languages and simulators accept a tolerance within which left and right hand sides are considered to match.
In prior art, models implemented in programming languages, such as C or Fortran, are commonly compiled before execution. Compilation results in compiled assembly or binary machine code common to all operating points and across all discontinuities. Compiled code may refer to multiple lookup tables representing the relationship between across and through quantities. However in prior art, compilation completes before simulation begins and thus cannot benefit from any contextual information know only during and after simulation, thus decreasing simulation performance.
Prior art also teaches techniques by which the current and voltage relationships within an operating context may be approximated by one or more tables. Such tables are constructed prior to simulation, then interpreted by machine instructions common to more than one operating context. Significantly, the innovations taught here allow optimization of the machine instruction sequences for a specific operating context.
If an analog solver is split across more than one processor (multiprocessor), the lack of contextual information encountered when practicing prior art has an even more severe performance impact than with a single processor. In a sparse matrix implementation, it is difficult or impossible to predict and schedule reference patterns so as to effectively schedule multiple processors or functional units to execution distinct portions of the same analog solver, to avoid cache to cache conflicts or to avoid locking of data structures (and thus performance degradation due to contention). As a result, speed-ups in the analog solver resulting from additional processors are generally accepted in the prior art as significantly below the idealized (and desirable) linear speed-up curve. For example, with the prior art, four processors execute an analog simulation at significantly slower than one quarter the rate of a single processor.
Electronically re-configurable logic devices, such as field programmable gate arrays (FPGAs), are often used to accelerate simulation designs at digital levels of abstraction, either in the form of emulators or simulation accelerators. The parallelism available inside of such devices results in substantial speedups relative sequential simulation execution through the execution pipeline of a single processor or a modest number of processors within a multiprocessor. Prior art does not teach any efficient means for utilizing the parallelism of electronically re-configurable logic devices for the simulation of analog, mixed-signal or full-wave abstraction levels.
At least one electronically re-configurable logic device has been fabricated with electronically re-configurable analog modules, such as amplifiers and filters. From the standpoint of simulation use, this device substantially lacks accuracy, noise-immunity, dynamic range, capacity and flexibility required for effective simulation of analog, mixed-signal or full-wave abstractions. Fundamentally it represents quantity values as actual analog values rather than as their sampled digital equivalents.
For ease of reading following current common use, the following will refer to FPGA devices although the references are understood to generalize to the broader class of electronically re-configurable logic devices (no matter what their architecture or market positioning). The references to FPGA are understood to embrace electronically re-configurable interconnects, memory arrays and various configurations of logic cells from fully programmable gates to large logic blocks where only selective interconnect and functionality aspects are electronically programmable.
Large designs, especially when modeled at analog, mixed-signal or full-wave levels of abstraction may readily become too large to fit on a single electronically re-configurable logic device or FPGA, requiring partitioning of a single design across more than one such device to efficiently perform simulation. As device density increases the number of logic gates and storage elements inside FPGA, the number of gates and elements on the device increases as the square whereas the number of pins or ports available to communicate on and off the device increase linearly. As a result, pins on and off the device become an increasingly limiting resource. Efforts to form and bond pads away from the FPGA's periphery help to reduce this problem at the cost of internal logic and memory functionality. However, off-chip interconnects are still more power-intensive than on-chip interconnects, resulting in an increasing incentive to reduce the number of off-chip interconnects required to fulfill a given functionality.
Prior art either maps digital signals directly to pins and traces connecting the pins of various devices or time-multiplexes several signals on the same pins. Commonly the value of a quantity at one time step numerically differs relatively little from the value at the next time step. This is especially true for analog, mixed-signal and full-wave quantities, however the same observation can be made to a lesser degree in the context of digital values. Inefficient use of scarce interconnect resources, as prior art does, results in less effective use of electronically re-configurable logic devices, requiring more devices to partition a design. Dividing a design into additional devices increases cost and slows simulation.
Although the pins of electronically re-configurable logic devices are becoming a limiting factor to effective design size and cost, it is also difficult to implement many arithmetic operators with both high precision and wide dynamic range on a given electronically re-configurable logic array. Frequently designs must accommodate the worst-case precision and range requirements in an operating specification. If the configured device in operation operates outside this specification, overflow, underflow or loss of precision may lead deviations between behavior of a design model and a realized design, ultimately having the potential to cause design failure.
Quantity values in the prior art rely almost exclusively on floating point representations (consisting of a mantissa, implied base and exponent). Since general purpose processors efficiently execute a small number of numeric representations (corresponding to those defined into the processor's instruction set and realization), use of floating point representations are the easiest way to gain increased range. However use of floating point representations has several significant drawbacks, especially in the context of FPGA implementations designed for maximum performance. Even serial implementations of floating point operators are significantly larger and more complex than integer representations, putting FPGA logic at a premium. Normalization and related floating point operations inherently require more time to execute than equivalent integer implementations. Numerical precision is much more difficult to formulate than for integer operations since precision changes as floating point values deviate from a central value, typically 1.0. Finally the flexibility of FPGA logic enables fabrication of almost arbitrary precision integer arithmetic logic, providing alternatives to floating point representation in order to increase usable numerical dynamic range.
Failure associated with overflow, underflow or loss of precision may only be avoided in the prior art through over-design of the specifications or careful and tedious exception handling. Given finite implementation resources, over-design must come at the expense of both decreased functionality and increased power consumption. Over-design throughout a design generally results in a significant decrease to both the design's user functionality and power, yet it only delays the potential for failure due to overflow, underflow or loss of precision.
Designs typically embody existing intellectual property, such as cell libraries or even entire microprocessors. For business reasons, owners of this intellectual property want to export models representing the behavior of these components while restricting the level of implementation or realization detail exposed. Previously such models either used code compiled into assembly language, such as the Synopsys Smart Model or inserted actual devices into the simulation, as in the Logic Modeling Real Chip product.
Compiling component models into an assembly code format is only useful when executing simulation on a general purpose processor for which a compiled representation exists. Such models must be decrypted before simulation begins, leading to the potential for disassembly of the model's assembly code representation and thus compromise of the owner's intellectual property. As an alternative to an assembly code model, prior art describes how to insert actual devices into a simulation.
Inserting actual devices requires an expensive test set in order to operate the isolated device with a suitable speed, timing, power and cooling. Prior art capable of introducing an actual device into a simulation do not address simulation at the analog, mixed-signal or full-wave abstraction levels. Prior art implies substantial time and therefore cost resulting from the need to maintain the chip's specific operating environment. These are important disadvantages to wide-spread use.
Development of accurate analog, mixed-signal, and full-wave models of a design or design component is time consuming and error-prone. In the prior art, such models tend to evolve manually, with ever-increasing complexity attempting to adapt existing models to new requirements or operating conditions. Even the evolution of such models requires specialized designer skill, a skill which is often in short supply.
Accurate analog, mixed-signal and full-wave models are essential to the synthesis of new analog designs, the retro-fit of existing designs and the modeling of complex designs with one or more missing component models. The prior art offers techniques for manually fitting a model around characterization of operating specifications, however both the gathering of such specifications and the effective fitting of data to achieve a new model is a slow, manual process in the prior art. The cost and time expenditure implicit in such a manual process are a significant disadvantage of the prior art.
Effective comparison techniques are a significant intermediate step in enabling the effective, semiautomatic generation of analog, mixed-signal and full wave component models. Such comparison provides an essential calibration in the process of semiautomatically developing a new analog, mixed-signal or full-wave model corresponding to an existing simulation or actual device. The most powerful prior art available to compare analog, mixed-signal or full-wave models relies on exhaustive simulation of a reference and comparison model under a wide variety of operating conditions.
Comparison of analog, mixed-signal or full-wave models via exhaustive simulation is both time consuming and ultimately fragile. Since it is not possible to simulate all operating modes in a bounded time, the risk of missing a key difference in the behavior of reference and comparison model must remain. Even the time required to conduct enough simulation to approach a given confidence level increases beyond practical limits as the complexity of devices being compared increases.
Textual comparisons of reference and comparison models are especially fragile. Models with closely related lexical and syntactic constructs may exhibit radically different behaviors. For example, a function which approaches positive infinity from one side of a critical value and negative infinity on the other side of the critical value will be extremely sensitive to behavior around this critical value. Conversely a trignometric function and its Taylor expansion can be lexically and syntactically very different, yet yield acceptably equivalent values over an interesting operating range. Therefore prior art based on textual comparison, such as the common available textual differencing utilities are of little practical value in the problem of analog, mixed-signal or full-wave model comparison.
SUMMARY OF THE INVENTION
An incremental compilation and execution method is taught for the optimized simulation of digital, analog, mixed-signal and full-wave components comprising designs using a combination of Programmable Processors, Multi-Port Memories and Electronically Re-configurable Logic (FPGA) Devices. Prior art using FPGA devices for emulation or simulation exclusively teaches a means of simulating digital (not analog, mixed-signal or full-wave component models). The innovative method taught herein implements a compilation mode and simulation mode resulting in faster simulation of analog, mixed-signal and full-wave component models within an overall design.
Compilation divides models of a design into Digital Partitions, Analog Partitions and Full-Wave Partitions, as shown in FIG. 9. The compiler maintains a representation of logical Digital Partitions, Analog Partitions and Full-Wave partitions (450) resulting from incremental changes to the Post-Analysis Representation (2), The Elaborated Representation (4) or Designer-Iinitiated Design Changes (such as a Breakpoint Insertion). Pseudo-static Technology Binding and Scheduling (451) allocates logical partitions for execution on Programmable Processors or Electronically Re-Configurable Logic (FPGA) devices, then for each Programmable Processor or Electronically Re-Configurable Logic (FPGA) device, it constructs a Schedule.
FIG. 24 illustrates aggregation of logical partitions into two Embedded Schedules (900 and 920). Each schedule is bound to a specific Programmable Processor or Electronically Re-Configurable Logic (FPGA) device. The processor iteratively executes each partition on its schedule using one of three operating modes. For Programmable Processors the Digital Operating Mode has previously been taught by the present inventor [Willis, 91]. The Analog Operating Mode is taught in an associated patent application entitled “Incremental Compilation Method for Optimized Simulation of Analog and Mixed Signal Designs Using Programmable Processors”.
Given sufficient logic capacity, Electronically Re-configurable Logic Devices may execute more than one partition in parallel. FIG. 14 shows the innovative Analog Operating Mode for an Electronically Re-configurable Logic Device. FIG. 17 shows the innovative Full-Wave Operating Mode for an Electronically Re-configurable Logic Device. Digital Operating Mode for an Electronically Re-Configurable Logic Device corresponds to logic emulation and behavioral synthesis techniques which are well-known to those skilled in the related arts.
The Analog Operating Mode for Electronically Re-Configurable Logic Devices, illustrated in FIG. 14, consists of the following primary steps applied to each Analog Partition:
1. Copy values of imported Analog Objects and Digital Objects from external memory to storage internal to an Electronically Re-Configurable Logic Device (such as an FPGA) (600)
2. Duplicate Object Values (if needed) to enable simultaneous computation of all expressions referencing Object Value (610)
3. Evaluate expressions corresponding to the left and right hand side of each Inequality in the synthesized equation system (602)
4. Compare values resulting from the left and right hand side of each Inequality to determine if the Inequality is within tolerance (603). If within tolerance, go to Step 5, otherwise go to Step 8.
5. Update integrals and differentials derived from quantity values while copying exported quantity and derivative quantity values to external memory (606); synchronize (632) to avoid copying a derivative before it is updated.
6. Execute the next partition (609)
7. Iterate with Step 1 (600)
8. Compute the Global Delta for each Quantity
9. Apply the Global Delta to each Quantity
10. Evaluate the Operating Context and update the Context-Specific Analog Solver
11. If the Context-Specific Analog Solver is not converging or there is an explicit break, copy exported Quantity and derived Quantity Values to external memories, trap to a more conventional analog solver, then continue with the Digital Simulation Cycle, Step 6.
12. If the Context-Specific Analog Solver is converging, continue with Step 2.
The Full-Wave Operating Mode for Electronically Re-Configurable Logic Devices, illustrated in FIG. 17, consists of the following primary steps applied to each Full-Wave Partition:
1. Copy values of imported Analog Objects and Digital Objects from external memory to storage internal to an Electronically Re-Configurable Logic Device (such as an FPGA) (751)
2. Duplicate Object Values to enable simultaneous computation of all expressions referencing Object Value (753)
3. Evaluate expressions corresponding to each expression referenced within Maxwell's field equations for each infintesimal volume contained within the regions of integration (756, 757)
4. Compare finite elements of the field equations against convergence and continuity criteria (758). If within tolerance, go to Step 5, otherwise go to Step 7.
5. Update integrals and differentials derived from quantity values while copying exported quantity and derivative quantity values to external memory (768 and 769); synchronize (781) to avoid copying a derivative before it is updated.
6. Execute the next partition (774)
7. Compute the Global Delta for each Quantity (770)
8. Apply the Global Delta to each Quantity (775)
9. Evaluate the Operating Context and update the Context-Specific Full-Wave Solver (778)
10. If the Context-Specific Analog Solver is not converging or there is an explicit break, copy exported Quantity and derived Quantity Values to external memories, trap to a more conventional analog solver, then continue with the Next Partition.
11. If the Context-Specific Full-Wave Solver is converging, continue with Step 2.
Common Breakpoints include failure to approach tolerances during successive simulation cycles (failure to converge), failure to converge after a specified number of analog solver cycles at the same time point, reaching a specific time point or matching a specific data access pattern. Other sources of Breakpoints are commonly known from the simulator or program debugging literature and are known to those skilled in the art of programming language interface or debugger design.
FIG. 6 illustrates the set of software components typically employed to implement this method. A Source Code Analyzer (1) compiles textual or graphical models of a design to a Post-Analysis Representation (2). A Static Elaborator and Inliner (3) compiles the Post-Analysis Representation (2) into an Elaborated Representation (4). An Incremental Compiler/Assembler/Loader (5) then generates General Purpose Processor Instructions (508 and 509) used to implement Context-Specific Analog Solvers (7), Executable Digital Partitions (8) and Embedded Scheduling Executables (1000 of FIG. 24) needed to schedule the execution of Context-Specific Analog Solvers (7) and Executable Digital Partitions (8).
For one embodiment, an apparatus is disclosed providing for the optimized simulation of analog and mixed-signal designs using a combination of Programmable Processors, Multi-Port Memories and Electronically Re-configurable Logic (FPGA) Devices. Prior art using FPGA devices for emulation or simulation exclusively teaches a means of simulating digital designs and hardware/software co-design. The innovative method taught herein supports an innovative compilation and simulation mode (disclosed separately), resulting in faster simulation of analog, mixed-signal and full-wave component models within an overall design.
FIG. 12 shows one instance of the apparatus, an Accelerator Card (268). The Accelerator Card may be combined with additional instances of the Accelerator Card (268) via a Host Processor Bus (261) such as the PCI bus, commonly used with contemporary workstations and servers, or via high speed interconnection fabric, such as the Scalable Coherent Interface (IEEE Std. 1596).
The apparatus consists of a General Purpose Processor (264) with direct access to one or more Multiport Memories (262). Each Multi-Port Memory (262) is directly attached to one or more Electronically Re-configurable Logic Devices, such as an FPGA (260). Conventional Dynamic Memory (272), Timer and I/O Device (266) and a System Controller (265) provide the General Purpose Processor with resources required for local operation. The Interconnect Controller (263) provides for communication with other Accelerator Cards (268) using an Architecture such as that taught by U.S. Pat. No. 5,999,734. A Peripheral Controller, such as a Universal Serial Bus (USB) or FireWire (IEEE Std. 1394) provide for optional attachment of storage devices for logging simulation activity and attachment of secure encapsulated models using the apparatus disclosed in the Patent Application “Apparatus for Secure Distribution and Simulation of Digital, Analog and Mixed Signal Components”.
The apparatus using a Compilation and Simulation Method disclosed in Patent Application “Incremental Compilation Method for Optimized Simulation of Analog and Mixed Signal Designs” on the General Purpose Processor (264) and “Incremental Compilation Method for Optimized Simulation of Analog, Mixed Signal and Full-Wave Designs Using Programmable Processors and Electronically-Reconfigurable Logic Arrays”.
In order to make more efficient use of interconnects into and out of Electronically Re-configurable Logic Devices, all interconnects into or out of these devices use a Delta encoding as shown in FIG. 16 except for loading and unloading operations between Electronically Re-Comfigurable Logc Devices and Multi-Port Memory at the beginning and end of partition evaluation.
As shown in FIG. 16, Delta encodings represent either the transfer of fundamental units, such as Electrical Charge (701), the signed change in object value (703 through 705) or the time-division multiplexed change in object value (706 through 708). These encodings across pins of the Electronically Re-configurable Logic Device both mimimize scarce pin resources and power associated with changing the driving state of a pin. Relative to prior art which encoded Object value on the pins, it can require additional on-chip logic to generate and apply Delta values. Techniques for implementing and optimizing logic for generating and applying Delta values within an Electronically Re-configurable Logic Device or General Purpose Processor are well-known to those skilled in the art of logic design and optimization.
In one embodiment, an innovative method is taught for the efficient modeling and simulation of electronic interconnects within the context of a more complex model. The modeling technique encapsulates lumped parameter, distributed parameter and full-wave interconnect modeling techniques within a common abstract visible to designers of the overall model. Technologist may then use context available at the time of analysis, elaboration, code generation or simulation to choose a specific technology for simulating interconnect detail. Using context available at analysis or elaboration time enables re-emitting models using conventional analog and mixed signal modeling constructs with some loss of eventual simulation performance. Using context available during code generation or simulation enables an innovative optimization technique disclosed. This additional optimization also accelerates performance of conventional digital interconnect models.
The method consists of three innovative steps:
1. Means for modeling interconnect behavior using lumped, distributed or full-wave detail
2. Optional means for incrementally choosing the most appropriate model during simulation
3. Optional means for efficiently implementing the most appropriate model during simulation
The first step associates sequential or simultaneous statements with the declaration of each terminal. The modeling language defines any change in the across or through quantities associated with the terminal as a trigger for the evaluation of sequential or simultaneous statements associated with the terminal. These sequential or simultaneous statements model analog or full-wave interconnect technology, analogous to VHDL's resolution functions modeling digital interconnect technology.
Since many interconnects may share the same interconnect technology, it is more efficient to associate the sequential or simultaneous statements defining interconnect technology with the terminal's subtype or subnature, analogous to the association of a resolution function within a VHDL subtype indication.
FIG. 4 shows an example of such a modeling construction using VHDL-AMS as a base. Lines 210 and 211 form a conventional VHDL-AMS base nature declaration (tap). Line 213 defines an unconstrained array of taps. Line 214 begins declaration of a procedure modeling transmission line behavior using a procedure containing sequential statements. Alternatively transmission line behavior might be encapsulated in a sequence of simultaneous statements, such as a VHDL-AMS simultaneous procedural statement. The procedure or procedural, known as a “Distribution Procedure” or “Distribution Procedural”, may then be used in the definition of a sub-nature (Line 218) or a sub-type in other AMS languages. This sub-nature or sub-type with associated procedure or procedural may then be used to declare a terminal declaration.
Analogous to the single argument of a VHDL resolution function, the first parameter of a Distribution Procedure or Distribution Procedural must be a terminal interface declaration of unconstrained array sub-nature (sub-type) having an element nature (element type) which corresponds to the sub-nature (sub-type) of the terminal to which the Distribution Procedure or Distribution Procedural is associated (such as Line 219).
Some means to constrain the dimensionality of this interface declaration must be established to reflect the degree of distribution required each time the procedure or procedural is dynamically elaborated. During elaboration, if the dimensionality is zero (VHDL null array) then the terminal is effectively an open circuit. If the dimensionality is one, the terminal is a lumped parameter (default VHDL-AMS behavior for a terminal). If the dimensionality is greater than one, then the Distribution Procedure or Distribution Procedural represents a distributed interconnect model. A large array would support a finite element model used to implement a full-wave model of the interconnect technology. In VHDL, the most intuitive means to establish the dimensionality is a function associated with the interface declaration and syntactically equivalent to a VHDL type conversion function; other modeling languages will suggest other means to achieve the same goal.
Technologists may provide additional (more than one) interface declaration for the procedure or procedural used to model interconnect behavior. These parameters may be associated (actual to formal) at the point where the procedure or procedural is associated with a sub-nature (sub-type) to form a Distributed Sub-Nature (Distributed Sub-Type) such as Line 218 of FIG. 4 or at the point of terminal declaration such as Line 219 in FIG. 4. For example, a three dimensional lattice of terminals may be constructed to represent the parasitic quantities within an integration volume. The lattice may be passed as a parameter to a Distribution Procedure or Distribution Procedural within the integration volume. Other parameters may locate the terminal being declared within the parasitic lattice. Interconnect technology implemented within the Distribution Procedure or Distribution Procedural may then use contributions from the parasitic lattice of terminals to influence the interconnect model, such as superimposing parasitic contributions (from the parasitic lattice) to the interconnect model.
The appropriate model to use for an interconnect usually depends on the usage context. For example, an interconnect model which very adequately reflects interconnect at one cycle per second may be entirely inaccurate at one billion cycles per second. Both procedures (used as Distribution Procedures) and procedurals (used as Distribution Procedurals) may include conditional constructions, such as VHDL-AMS case statements or conditional case statements. The expression choosing among exclusive alternatives may include (for example) dimensionality of the first parameter, a global frequency parameter or even a function of the parasitic noise lattice passed as an additional parameter. Branches of the conditional may implement lumped, distributed or even full-wave models (perhaps using a finite element technique).
While the a compiler may emit executable fragments implementing the full generality of a digital resolution function (VHDL), a Distribution Procedure or a Distribution Procedural, the same basic control flow is often taken by frequent invocations of such subprograms. A digital resolution function with one driver on the first call often has one driver on subsequent calls. A Distribution Procedure or Distribution Procedural using a high-frequency model will usually employ the same model repeatedly. Therefore when a resolution function, procedure or procedural is first used as a resolution function, Distribution Procedure or Distribution Procedural, an innovative analysis may be taken of data flow internal to the function or procedure (directly or via subsequent in-lining) so as to determine which global objects, interface declarations or attributes determine control flow and are likely to remain constant during a call or over many calls. Such objects, declarations or attributes become a part of the enclosing partition's Operating Context.
The code generator may then generate executables, such as instructions for an instruction set processor or an Electronically Re-Configurable Logic Device used for simulation, which validates the assumed Operating Context then executes an implementation which incorporates the Operating Context as a constant. Well known compiler techniques for inlining and constant propagation may be used, potentially to the extent of eliminating the resolution function, Distribution Procedure or Distribution Procedural call completely (such as a interconnect model which identically distributes the assigned value at the same instant in simulation time throughout the interconnect model).
FIG. 5 illustrates this innovative optimization technique. During analysis, elaboration or code generation configurations of signals, quantities, terminals and shared variables are predicted (if possible) using the criteria described above (225). During code generation, generate code to assert Operating Context assumed in the generated code to form a Context-Specific Partition (226). Trap to the incremental compiler if the assumed Operating Context values change (230), resulting in compilation of a new Context-Specific implementation of the partition or reuse of a suitable executable cached from a previous incremental compilation.
Use of global or local state to represent debugging levels, assertion checking levels or assertion classes can be incorporated in interconnect (and other models) with less concern for possible performance impacts. When not required, the additional debugging, assertion or related code ceases to degrade performance. Removal of assertion checking code can even be included directly in the emitted code, such as code for text case evaluation or profiling which triggers recompilation need to remove the assertion checking code from the effective executable by changing control flow variables whenever particular criteria are met, such as a path through the HDL code being executed.
Modeling language innovation provides a powerful language representation capability; incremental compiler and execution innovation helps to insure that only the interconnect modeling detail actually required by the simulation context need be evaluated. This innovative combination allows a technologist to create generalized interconnect models with a wide range of possible modeling detail, however the detail only impacts simulation speed when conditions determined by the technologist actually occur. Designers can use these encapsulated interconnect abstractions with less concern for possible simulation performance penalties or inaccuracies.
In one embodiment, an innovative apparatus is taught to facilitate the secure distribution of component models for rapid insertion into a simulation. The method avoids the need to meet the integration requirements of actual devices (such as power, speed or cooling requirements) and can be inserted into a running apparatus.
The apparatus, shown in FIG. 13, uses Electronically Re-configurable Logic Devices (260), such as Field Programmable Gate Arrays (FPGA), in three operating modes: digital, analog and full-wave simulation of the component model or models. Executable logic configurations for each Operating Context which can be simulated by the apparatus are previously compiled and loaded into the Non-Volatile Configuration Memory (600) or directly into the Electronically Re-Configurable Logic Device (260).
Models stored in the Electronically Re-configurable Devices (260) or Non-Volatile Configuration Memory (600) model behavior using the Method disclosed in Patent Application “Incremental Compilation Method for Optimized Simulation of Analog, Mixed-Signal and Full Wave Designs Using Programmable Processors and Electronically Re-Configurable Logic Arrays”.
Peripheral Controller (271) interfaces to the Apparatus Disclosed in “Apparatus for Optimized Simulation of Mixed Signal Systems Using Hybrid Programmable Processors and Electronically Re-Configurable Logic Arrays” via live-insertion protocols such as the Universal Serial Bus (USB) or Firewire (IEEE Std. 1394). Messages transmitted via the Peripheral Controller (271) include:
Means of identifying models incorporated in the apparatus
Means of initializing the apparatus
Means of transmitting interface values to models contained in the apparatus
Means of receiving interface values from models contained in the apparatus
Means of running models contained in the apparatus for some period of time
Means of saving state embedded in the models
Means of restoring state embedded in the models
Means of encoding such messages are well-known to those familiar with simulator implementation.
Significantly the messages transmitted do not enable access to the model definition beyond the behavioral observations which are commonly available via monitoring an actual device during its operation; model security is maintained.
Interfaces between Electronically Re-configurable Logic Devices (605) and/or with Multiport Memory (603) to 262 encode delta change in object value, as shown in FIG. 16, except for the beginning and end of a simulation run, when full values must be saved or restored to or from the Multiport Memory (262). Delta changes in object value reduce both pin utilization and power consumption by transmitting only the change in object values partitioned between two or more Electronically Re-Configurable Logic Devices (262) contained within the same apparatus.
Furthermore the memory may be partitioned to contain the intermediate state of several distinct simulation runs or use of the same component model as an instance in multiple enclosing models. In such a multi-user or multi-model operating mode, message sent via the Peripheral Controller (271) must identify the model instance implied by each message.
The Simulation Controller (602) and Operating Memory (602) provide operating modes including initialization on power application, interface between the Peripheral Controller (271) message above and the Multi-Port Memory (262) as well as controlling addressing and transfer operations between the Multi-Port Memory (262) and each Electronically Re-Configurable Logic Device (603).
The apparatus of FIG. 13 may be encapsulated with tamper-resistent shielding such that any effort to probe internal connection points (other than the Peripheral Connection (271) port) will result in erasure of the models. Means for such controlled erasure by interrupting power or active erasure using an internal power source are well-known to those skilled in the art.
In one embodiment, an innovative method is disclosed which reduces the impact of overflow, underflow and loss-of-precision for arithmetic operations implemented using Electronically Re-configurable Logic Devices (such as FPGA). Prior art suffers from lower density and power efficiency (resulting from use of floating point representations, an integer domain intended to handle worst-case arithmetic range or extended precision software implementation).
The method consists of five steps:
1. When hardware implementing an arithmetic operation produces a result outside the representation range of subsequent logic or storage, trap to an Incremental Compiler functionality (such as that shown in portions of FIG. 9). State needed to re-run the failed operation must be saved during the trap.
2. Incrementally re-compile related state and logic (803) with increased numerical range or shifted range, incrementally place and route modified state (804)
3. Incrementally load new logic into the Electronically Re-Configurable Logic Device, merging previous state (805 and 806)
4. Either re-run the failed operation or achieve the same result within the re-compilation trap
5. Continue operation
On-going operation of the Electronically Re-Configurable Logic Device will eventually deplete available logic, interconnect, memory and pin resources. If an incremental compilation trap occurs when no suitable resources are available, logic and state may be reduced in range provided the current value associated with all resources are representable.
However to reduce the probability of the reduction in range requried to complete re-compilation triggering a subsequent re-compilation trap, a general purpose processor or dedicated logic may periodically sample the values at various points in the logic to identify resources which are likely candidates for reduction. Techniques, such as shadow registers and serial scan changes well known to logic designers and already incorporated in logic designs for other purposes may be used for sampling. This sampling a subsequent re-compilation with lower or shifted range is analogous to garbage collection and memory compaction techniques well known to those who implement programming systems with explicit storage management.
Arithmetic operations, such as iterative division, may continue to add many more significant bits to the logic design than numeric stability actually requires. To eliminate the potential for unbounded logic growth, the trap handler and Incremental Compilation step may use one of more of the following strategies:
Designer-directed software and hard limits for each range of a data type
Balancing resource consumption so that all growing representations share approximately equal resources
While trapping and iterative re-compilation requires substantial time and power consumption relative to logic operation, it can reduce the probability of a design failure without the need to implement specialized exception handlers (thereby reducing time required to achieve a reliable system design). Designs may evolve so as to correctly operate in environments which deviate substantially from the design's initial operating specifications.
Designs eventually intended for hard logic (such as an Application Specific Integrated Circuit) may be operated “in-circuit” as an evolvable Electronically Re-Configurable Logic Device in order to capture actual operating requirements. The design which evolves may be extracted from the Elaborated Representation as a Post-Analysis form or saved directly as textual source code. Alternatively the Elaborated Representation or Post-Analysis form may be compared directly with the originally design as one form of input for candidate design modifications.
In one embodiment, using techniques previously developed and disclosed in 1988 through 1995 by the current inventor as “Embedded Scheduling, once control transfer to a partition, execution of the partition may be made conditional on the evaluation of arbitrary expressions. Commonly such expressions include the partition's local clock having a value less than or equal to the global value.
Unlike prior art, where the actual object reference by a Context-Specific Analog Solver are not known until the solver executes, the innovation disclosed here enables static dependency analysis and thus pseudo-static scheduling. Pseudo-static scheduling means that the sequence in which partitions execute and the processor on which they execute varies slowly over time. As a result, processor instructions intended to prefetch and flush data may be inserted into the instruction stream so as to minimize processor idle time resulting from cache misses and cache to cache transfers. Techniques for formatting and using such instructions are evident to those skilled in the art of multiprocessor software design once the innovative technique taught here for static scheduling is used.
The Pseudo-Static Technology Binding and Scheduling (451) software monitors the relative idle time for each processor during both the analog and digital phases of simulation. The Pseudo-Static Technology and Scheduling functionality alters the scheduler data structures or instructions so as to move execution of partitions from one processor to another in order to more effectively balance simulation load.
FIG. 24 illustrates the integration of Executable Digital Partitions (such as 901 and 902) and Context-Specific Analog Partitions (such as 904, 905 and 906) into a parallel Embedded Processor Schedule. Each processor has a schedule of such partitions as managed by a means of Pseudo-Static technology Binding and Scheduling (451) included within the Incremental Compiler/Assembler/Loader (5). When a partition completes executing, it transfers control (manifest as the processor's program counter) directly to another partition or indirectly via an embedded scheduler data structure. Depending on data flow within a partition (such as 901), control may transfer to one of several subsequent partitions (such as 903 via 930 or 902 via 931). Semaphores are set when an Executable Digital Partition updates the last Digital Object (such as 910) or by a Context-Specific Analog Partition when it updates the last Analog Object Value.