textarchive.ru

Главная > Документ


Chapter 1

GENETIC PROGRAMMING WITH DESIGN REUSE FOR INDUSTRIALLY SCALABLE, NOVEL CIRCUIT DESIGN

Trent McConaghy, Pieter Palmers, Georges Gielen, Michiel Steyaert

Katholieke Universiteit Leuven, Leuven, Belgium

ABSTRACT

This paper shows how aggressive reuse of known designs brings a vast reduction in computational effort in GP applied to automated structural design, plus with a framework to handle trustworthiness.

A major application of GP research has been in search for structures in industrially relevant problem domains; in particular, design of analog circuit topologies has been pursued with interest. However, industrial use remains elusive because the GP-synthesized designs have not has the combination of sufficiently complexity and trustworthiness. Even worse, to address just some trustworthiness issues with the current GP approach would on a sufficiently complex problem would take 150 years on a thousand-CPU 1-GHz cluster. In this paper, we show how to synthesize 100% trustworthy circuits with industrially relevant complexity, in just 150 hourson a single CPU, with a system called MOJITO. We also describe the technique for novel design – MOJITO-N - and demonstrate it by automated re-innovation of a trustworthy design having industrially relevant complexity, taking just 25 additional hours on a single CPU. The key to both is in aggressive reuse of known designs. We created a means to capture the analog circuit structures by designing a parameterized generative representation. Using that representation, we captured structural analog design knowledge into a library of hierarchically organized building blocks, which define a space of 100% trustworthy circuit topologies. In creating novel designs, special mutation operators extended the library with novel parts. “Trustworthiness tradeoffs” ensure that only novel designs that actually give a payoff are rewarded; specifically, trust = -novelty; novelty = number of novel parts used; novelty is an additional objective to be minimized. We view our novelty-approach as “automated innovation” rather than “automated invention” because it builds on existing knowledge -- but note that patents are awarded for innovations too. The search algorithm is GP, with some “algorithm engineering”. The search algorithm’s operators give both a tree-based and a tree-based view of the search space. To avoid premature convergence and minimize sensitivity to population size setting, we employed the age-layered population structure (ALPS). We embedded NSGA-II into each age layer of ALPS to make it multiobjective. The techniques of this paper can be readily extended to other GP problem domains of interest, and are complementary with many other recent advances in GP.

Keywords: Genetic Programming, Synthesis, Industrial, Analog, Integrated Circuits, CAD

TRODUCTION

1.1.1GP and Automated Invention

A core reason that genetic programming (GP) [33] is interesting is its natural ability to handle search spaces with tree-like and graph-like structures. Accordingly, a longstanding goal in GP research has been to search for structures in industrially relevant problem domains, most notably “engineering design” style domains. In particular, design of analog circuit topologies has been pursued with interest by the GP community. In automated analog topology design, the aim is to automatically determine the circuit components, interconnections, and suggested component dimensions to meet a set of circuit design goals, i.e. a “sized topology”. Figure 1 left illustrates. In this domain, GP has evolved several patent-quality circuits [35] essentially “from scratch”, which is a remarkable success by almost any measure. It is an especially notable accomplishment from an artificial intelligence perspective because “patent-worthiness” is a good measure of success for testing techniques in automated “creative” design.

Figure 1: Current approaches to get sized topologies. Left: Status quo GP flow having no structural reuse – painful because topologies are untrustworthy, and huge computational burden. Middle: Current industrial flow using optimization (sizing) -- painful because topology selection is manual. Right: Earlier approaches to multi-topology sizing – painful because the libraries were small and inflexible, and therefore required designer setup and intervention

1.1.2The Trust Issue In Automated Topology Design

GP is not in use at allfor topology design in industry. This is because the GP-synthesized designs so far have not had the combination of sufficiently complexity and trustworthiness. It gets worse: addressing even just robustness (a subset of the trustworthiness issue) on a sufficiently complex problem would take 150 years on a thousand-CPU 1-GHz cluster; Moore’s Law [27] can’t help because the problem itself becomes more difficult as Moore’s Law progresses [45].

Let us briefly explain the source of the trust issue. The flow from design to real world use is:

  1. Designing the topology and device sizes (i.e. what GP is targeting)

  2. Creating a so-called “layout” from the netlist, which is basically instructions to on how to etch the silicon, so that the chip exhibits the desired electrical behavior

  3. Physically instantiating the layout as so-called “masks”

  4. Manufacturing the chip using the “masks”

  5. Using electronic measuring equipment to validate that it works as targeted

  6. Putting it into an overall system that ultimately gets into user’s hands; such as a cell phone.

But there are complications. If the circuit does not work as targeted, one needs to “re-spin” and go back to step 1 or 2. In an ultra-modern 45nm process, a single set of “masks” costs $8M dollars, and possibly hundreds of millions dollars in lost possible revenue. So one does not want to have to re-spin! Re-spins happen typically due to physics that were not properly accounted for. Digital designs are more tolerant to physics by their nature: by railing to positive or zero voltage, every transistor intrinsically has a safety margin. Analog designs don’t have that luxury, and thus it is analog circuitry that is the source of most respins.

A new analog topology significantly raises the chance of a re-spin due to lack of experience with that topology. Even if the best analog designer in the world has designed a new topology, it is a risk to manufacture. This is why one almost always tries to reuse existing ideas to the fullest extent possible. New topologies only come about if there is no other way, if idea has possible orders of magnitude payoff that it’s worth the money to try, or if there is some way to make trying it zero risk.

Now imagine if the design did not come from an experienced designer who based his design on logic and past knowledge, but instead from some black box. Imagine if the design looked nothing like anything that anyone has previously seen, no one could understand how it worked, and the black box did a poor job of explaining what it did. Would you be willing to commit $8M to try it out? That is precisely the issue that status quo GP has.

An industry with similar resistance to new structural ideas is aerospace, except there if the new design fails it means that the plane / rocket crashes! Conversely, fully novel design is acceptable where the risks are low, e.g. evolving robots for 3d worlds [23]. It’s also acceptable where humans have not figured out any meaningful structure to their design problem, so a black box’s design is just as acceptable as a human’s, such as antenna design [20] or quantum logic design [60]. Analog design (for chips) has neither of these characteristics: risk is high [45], and structured knowledge is available [50][53].

1.1.3A Path from Optimization to Automated Topology Design

If we are going to make an automated topology design tool that designers can use and trust, we have to understand what tools they currently use, and what the “logical next steps” from their perspective might be.

The tools in use which are closest to the problem of automated topology design are essentially optimizers [5][55] – the middle diagram of Figure 1. The search space a fixed-length vector-valued set of possible device sizes (e.g. width and length of transistors). The objectives and constraints are circuit performances, such as power consumption, area, and building-block-specific goals such as “gain”, and “slew rate”. These performances are estimated by using commercially available SPICE-like circuit simulators. More recent tools such as [54] actually have circuit the yield estimate as an objective: yield is the percentage of manufactured chips that meet all constraints. The algorithms perform local or global search, and sometimes multi-objective search.

The output of “automated topology design” is agreed upon: return a sized topology that meets the target goals and objectives. But there is a difference for what inputs are acceptable, based on research aims:

  • The main motivation for status quo GP approaches has been to demonstrate that GP can “invent”. This implied a “hands-off constraint” for inputs, i.e. don’t give GP any problem-specific hints of structural design knowledge. A measure of success is “are results patent-worthy?”

  • Our motivation to help analog designers in industry with selecting / designing their topologies. If that implies certain constraints, fine, but don’t impose extra arbitrary constraints. We have a bias (but not constraint) to use GP, because of its flexibility and natural application to the problem.

  • But there is therefore a common goal: to see GP-based automated topology design get industrial application!

Given its constraints, status quo GP has done a remarkable job -- for low-complexity circuits [8][35][42][57][63]. But efforts towards higher-complexity circuits have stalled because of issues with computational effort, even worse, trust and \robustness [45]. Up-front constraints such as current-mode analysis [63] and KVL constraints [8] can be added, but plugging such “holes in goals” is tedious, and impractical, especially when trying to scale up complexity.

Figure 2: Proposed approaches to get sized topologies. Left: MOJITO: Multi-topology sizing – specs-in, sized-circuit out; gives 100% trustworthy results, but not novel designs. Right: MOJITO-N: Multi-topology sizing with novelty – gives trustworthy results and designs with measurable novelty

Our definition of “automated topology design” comes from an industrial CAD perspective, and is more like a CAD tool specification. If a topology that is known to be 100% trustworthy will meet their goals, then the tool should return that. It should use inputs and outputs that make sense in the context of a CAD design flow; a useful guideline is “use those of industrial single-topology sizing tools, with exceptions only as needed”. It should draw on as much prior structural design knowledge as possible, as long as that knowledge is convenient to the user. (It doesn’t have to be convenient to the CAD developer.) Only if no existing known topology can meet their goals should the tool resort to adding novelty. (After all, why take a risk to use something you don’t trust, if you don’t have to?) If it does add novelty, it should be easy to track where and how that novelty is added, and what the payoff is.

We now classify “automated topology design” into the following sub-categories, and discuss which a designer would want:

  1. Lightweight multi-topology sizing: Search across predefined, 100% trusted topology space, but the topologies have to be designer-input. The trustworthiness is great because it means that there is less reliance on detailed measures to guarantee robustness and manufacturability, but it is too tedious to expect a designer to enter more than a few topologies. Even if the topology space is parameterized, it is hard to get beyond a few dozen possible topologies. Figure 1, right, illustrates.

  2. Multi-topology sizing: Search across predefined, 100% trusted topology space, where the number of topologies is sufficiently rich that the designer can consider it “complete enough” to not have to intervene in a typical design problem (i.e. hidden from view from the perspective of the designer). This is of great interest to them, because it means that it is the same input and outputs as their existing tools, yet now they don’t have to take the time to select a topology. It is simply “specs in, sized topology out”. Interestingly, if one does a (long) multi-topology sizing run with a huge number of goals set as objectives, the result itself is effectively a library of sized results; future queries for sized topologies of certain specifications are a computationally cheap lookup; i.e. it is “specs in, sized topology out, immediately.” Figure 2, left, illustrates.

  3. Multi-topology sizing with innovation: search across 100% trusted topology space, and add novelty if there is a performance payoff. That is, “innovate” as needed. This would be of great interest for a designer in exploring new design ideas, if that is what is truly desired or needed. It is especially useful if there is a mechanism to track the novelty, and therefore assess how much trust they have in the design. Figure 2, right, illustrates.

  4. Topology invention from scratch: no structural information is input (status quo GP). That is everything is “invented” (or reinvented) from scratch. Designers would question why this would ever be needed, if (3) exists. After all, why ever reinvent known structures? And they have no idea where the novelty may lie; it may be near-impossible to untangle the circuit to understand it. If they wanted extreme novelty, they would just let (2) run longer. If this field were automobile design, (4) would literally be reinventing the wheel! Incidentally, because such a methodology would require a tedious iterative looping of plugging “holes in goals” for each new problem, that makes it more “hands-on” than an approach that has structural reuse. Figure 1, left, illustrates.

In this paper, we demonstrate how GP can be used to build the industrially interesting categories (2) and (3). The key to (2) is to aggressively reuse existing structural knowledge. The key to (3) is trustworthiness tradeoffs to ensure that only novel designs that actually give a payoff are rewarded. One might be concerned that the problems (2) and (3) are trivially easy compared to (4). Our responses are that (4) is pointlessly hard, and that one should strive to “trivialize a problem” as much as possible to help ensure its use! And we will see that problems (2) and (3) are challenging in their own right, by no means trivial to solve effectively.

1.1.4Paper Organization

The rest of this paper is organized as follows. Section 2 describes the “MOJITO” system for multi-topology sizing. This includes how the library is defined, the GP search algorithm, and experimental results that output 100% trustworthy one- and two-stage operational amplifiers. Section 3 describes how we adapt MOJITO to perform innovation, along with an experimental result in which a known, trusted analog topology that was not in the library was re-innovated. Section 4 describes how the work relates to other GPTP work. Section 5 concludes.

2.MOJITO FOR MULTI-TOPOLOGY SIZING

MOJITO is a system for multi -objective and –topology sizing, with the flow of Figure 2 left. This section describes: how the library of structural design knowledge is defined, the GP search algorithm, and experimental results that output 100% trustworthy one- and two-stage operational amplifiers. Note: some parts of this section were reported in [47].

2.1Background on Multi-Topology Sizing

This section reviews other approaches to multi-topology sizing in the literature. Multi-topology sizing is not a new idea, but it has never been applied to giant topology spaces, nor with SPICE in the loop (both of which greatly increase the difficulty of the problem). The work typically comes out of the analog CAD field (as opposed to an EA field). OASYS [18], BLADES [14], and others [1][4][11][28][31][44][49][64][67] depend on rule-based reasoning or abstract models having transforms to structural descriptions, and therefore have an undesirable amount of up-front setup effort. DARWIN [38] and others [43][65] only require structural information, but rely on a sneaky definition of a flat combinatorial search space to define possible topologies; they do not show a clear path to generalize and are restricted to a few hundred topologies at most.

2.2MOJITO Inputs and Outputs

The core philosophy is to use the inputs and outputs that are acceptable for industrial single-topology multi-objective sizing tools (e.g. [56]), with the smallest possible amount of extra information in order to enable multi-topology sizing. Instead of a single topology, the tool takes in a set of hierarchically organized building blocks. Just like a single topology, these building blocks can be specified in an industrial circuit schematic editor. Getting such inputs is not unreasonable: such blocks do not appear as anything special to the designer as they are merely based on well-known building blocks that one can find in any analog design textbook [50][53]. And in fact since we have already designed an example library (see upcoming sections), the designers can use that! This makes it is straightforward to switch technologies, or add new building blocks.

MOJITO uses off-the-shelf simulators (e.g. SPICE) rather than specially designed performance estimators. Its output is a tradeoff of sized circuits, for selection by a designer or within a hierarchical methodology like MOBU [13]. MOJITO can be seen as a pragmatic fusion of knowledge-based and optimization-based analog CAD [52].

2.3Search Space Framework

This section describes a topology space that is: specified by structural information only, searchable, trustworthy, and flexible. Its flexibility is due to an intrinsically hierarchical nature which includes parameter mappings; the parameter mappings can choose sub-block implementations.

Creating a representation for circuits is a design challenge in its own right. We choose to adopt a strongly hierarchical approach, because a flat representation is not conducive to the construction of a library or to larger designs. Analog circuit hierarchies be represented by analog hardware description languages (HDLs) [1][39], analog circuit database representations like Cadence DFII, and those used in multi-topology sizing research [18].

With these options already existing in the analog domain, why not just use one of them? The problem is: if a designer makes a small conceptual change to a circuit that corresponds to a small change in performance, there may be a drastic change in the netlist. While this complicates the design of an appropriate search representation, it is needed for changes like folding an input or flipping all NMOS transistors to PMOS. Myriad examples can be found in any analog design textbook. The structural-only op amp approaches [38][43] do cover some of these examples, but are designed into a flat space, need special heuristics just to work in their small spaces, and do not readily generalize. An example limitation: [43] had a single parameter to choose whether NMOS vs. PMOS inputs, but did not reconcile that with folded vs. cascode which can flip the load being NMOS vs. PMOS.

A technique from artificial life called GENRE [22][23] provided inspiration. It used a generative representation, which unlike direct representations distinguishes the space that the search algorithm traverses (“genotypes” – the conceptual representations) from the space of implemented designs (“phenotypes” – the netlists). A generative representation transforms a genotype to a phenotype by executing the genotype commands as if they were a program. Reference [21] convinced us that an effective representation would need to support modularity, regularity and hierarchy (MR&H); removing any one makes effectiveness plummet. It defined MR&H as follows: Modularity is an encapsulated group of elements that can be manipulated as a unit. It also helps enable both regularity and hierarchy. Regularityis a repetition or similarity in a design. (Note: differential analog structures would be considered a specialization of regularity - symmetry.) Hierarchy is the number of layers of encapsulated modules in the structure of a design. GENRE attained MR&H by allowing algorithmic combination, control-flow, and abstraction to occur during the execution of its genotypes. Unfortunately, it does not readily allow one to easily embed known trusted building blocks, and is overly flexible in allowing the addition and removal of ports on substructures during search. So while inspiring, we had to move to our own generative representation.

MOJITO’s representation is generative too; it overcomes the limitations of GENRE for analog circuits, yet still attains MR&H. It is composed of three simply-defined “Part” types, which we now describe. Our starting point is a direct \. We define a “Part” as merely a circuit block at any level of the hierarchy. It has a fixed set of arguments in its interface: “port arguments” (nodes available to the outside world) and “number arguments” (parameters which affect its behavior, e.g. a device size). Arguments to a Part’s embedded Parts are a function of arguments above. To fully netlist a given Part, the only extra information needed is values for the arguments to that Part. This is akin to analog hardware description languages such as Verilog-AMS or VHDL-AMS. Direct-representation Part types are:

  • Atomic Part Type. Parts of this type are the leaf nodes in the hierarchy (tree) of Parts. They do not contain any embedded parts.

  • Compound Part Type. These have one or more sub-Parts embedded. Sub-parts can have internal connections among themselves and to the Part’s external ports. All sub-parts get netlisted.

We add the following generative Part type. It netlists by executing the Part as a function of a third type of argument in its interface: “topological arguments”:

  • Flexible Part Type. These have the topological argument “choice_index”, which during netlisting, is used to select one of several candidate embedded parts and respective wirings. The argument values going into the chosen sub-part can be very particular to that sub-part if the mapping function has cases for different choice_index values. Example: a current mirror which may be simple or cascode (choice_index = 0 or 1).

We do not need the following generative part type for the experiments described in this paper, but it is useful to mention in order to underscore the representation’s generative abilities:

  • Repeating Part Type. These have the topological argument “num_stages.” During netlisting, that argument governs the number of copies that are made of an embedded part. Example: a ladder filter. Connections between the embedded parts are generated on-the-fly, based on the user’s specifications1. To allow refinement on a stage-by-stage basis, arguments going into the embedded part at stage_i are also a function of stage_i itself.

Despite the simplicity of Part types, the interactions allow a capture of MR&H found in analog building blocks. The generative Parts, especially Flexible Parts, are what turn a Part into its own IC libraryof possibilities rather than merely a representation of a single circuit design. Traversing the topology space merely means changing one or more of the “topological argument” input values. Because the MOJITO representation is generative enough to allow for MR&H yet direct enough to allow for reverse engineering, it means that MR&H knowledge specific to analog circuits can be captured - which we now proceed to do.

For space reasons, and to avoid inundating the reader with more analog domain information)\, we do not describe the whole MOJITO library. Instead, we will give the reader a feel via examples. Figure 3, Figure 4, and Figure 5 give examples of Atomic Parts, Compound Parts, and Flexible Parts respectively.

Figure 3: Example Atomic Parts: nmos4 transistor, pmos4 transistor, resistor, capacitor

Figure 4: Example Compound parts. mos3 is a wrapper for mos4, so that the mos4’s ‘B’ node is not seen at higher levels. mosDiode ties together two internal ports to only present two external ports. biasedMos uses a 1-port dcvs (dc-controlled voltage source) part to set its gate bias internally.

Figure 5: Example Flex part: mos4 turns the choice of NMOS vs. PMOS into a parameter “choice_index”. Note how parameters get assigned from mos4 to either of its sub-blocks. In this case both sub-blocks use the mos4’s W and L parameters as their own W and L values.

Warning: the rest of this section (2.3) is more specific to analog design; however we hope that readers with less knowledge in the field might find it to be a useful reference illustration of a parameterized generative representation to capture structural knowledge.

For cell level analog design, a specific challenge is to reconcile: PMOS vs. NMOS inputs, PMOS vs. NMOS loads, stacked vs. folded cascode inputs. The MOJITO resolution is: at very top level of the amplifier, have a “choice block” which chooses between sub-blocks, where each sub-block is identical except for whether “load rail” and “opposite-to-load rail” are attached to Vdd and Vss, or vice versa. In a 1-stage amplifier there are two options, and in a 2-stage amplifier there are four options. The choice parameter’s value guides the setting of each sub-block’s value for the Boolean parameters of “loadrail_is_vdd?” and “input_is_pmos?” Lower in the hierarchy, the input implementation is chosen to be folded vs. cascode via: is_folded = “input_is_PMOS == loadrail_is_vdd”. At the third-lowest level of the hierarchy is a “mos3” block, plus a parameter “is_pmos” which has been set depending on its context, to choose between one of two second-level blocks “nmos3” or “pmos3.” “Nmos3” and “pmos3” each transform into “nmos4” or “pmos4” respectively, with the extra (bulk) node tied to the appropriate spot. Figure 6 and Figure 7 show the four combinations of input_is_pmos=T/F x loadrail_is_vdd=T/F, and the implications for folding vs. cascoding, nmos vs. pmos transistors, and bias circuitry as needed.

Figure 6: ddViAmp1: input_is_PMOS=False, loadrail_is_vdd=True. The next three figures show the other three cascode input settings, including how folding vs stacking “falls out” of these parameters.

Figure 7: Left: ddViAmp1: input=PMOS, loadrail=gnd. Middle: ddViAmp1: input=NMOS, loadrail=gnd . Right: ddViAmp1: input=PMOS, loadrail=vdd

Figure 8 provides an example of how a full 2-stage op amp design is broken into sub-blocks. The top-level block is a block called dsViAmp2-VddGndPorts, where dsVi means differential in, single-ended out, voltage in, current (i) out, Amp2 means two-stage amplifier, and VddGndPorts means that the rails have been resolved to connect to Vdd and Ground. It has a parameter loadrail_is_vdd which tells its subblock dsViAmp2 which rail got Vdd and which rail got ground. This illustrates how the choice of ports can turn into parameters which ultimately govern folded vs. cascode, etc.

The block dsViAmp2 can instantiate into either dsViAmp2-singleEndedMiddle or dsViAmp2-differentialMiddle. The single-ended version is shown here, which has sub-blocks dsViAmp1 for the first stage, ssViAmp1 for the second stage, viFeedback for voltage-current feedback, and levelShifter. The level shifting is a wire in this case (there were other level shifting options). dsViAmp2-differentialMiddle’s subblocks include ddViAmp1 and dsViAmp1.

The first stage’s input ddViInput has differential-voltage in and differential current out, which then gets converted to single-ended current via dsIiLoad. The ddViInput block instantiates into ddViInput-Stacked (an alternative was ddViInput-Folded), which has a biasedMos to set up the virtual ground for the ddViInputNoBias, which has two ssViInput blocks. Each ssViInput is instantiated into an inputCascodeStage, which has subblocks of cascodeDeviceOrWire, mos3, and sourceDegen. Both the cascodeDeviceOrWire and sourceDegen instantiate into wires here. The first stage’s dsIiLoad converts a differential input signal into single-ended signal, which means it instantiates into none other than a currentMirror subblock. That has further subblock choices of simple-CurrentMirror, Wilson-CurrentMirror, cascode-CurrentMirror, etc.

The second stage’s load is ssIiLoad, which has instantiated into a transistor. Other options, not shown, included cascoding and resistor loads. The second stage’s driver is ssViInput, which has instantiated into a single device. Other options included adding cascoding and / or source degeneration.

Remember, that for all these subblocks, instantiation into sets of nmos vs. pmos devices is deferred until the very leaf block, based on the parameters that flow through the circuit. This sort of flexibility allows for a large number of topologies at the top level, without having an excess number of building blocks. It also means that many parameters are shared in the conversion from one block to subblocks, which keeps the overall variable count lower than it might have been; this is crucial to the locality of the space and thus the ultimate success of the search algorithm.

The library also includes: 4 current mirror choices, 2 level shifter choices (one choice is a wire); 2 choices of how to allocate Vdd/Gnd ports for a 1-stage amplifier and 4 for a 2-stage amplifier; 3 source-degeneration choices; 3 single-ended load choices; and more.

Figure 8: Example of MOJITO Building Blocks on a PMOS-input Miller OTA

2.4Size of Op Amp Search Space

The major question of this subsection is: can the size of the space be sufficiently rich that the designer can consider it “complete enough” to not have to intervene in a typical design problem? (That is, in the flow of Figure 2 left, can we make the “building blocks library” sufficiently large to keep it inside the box rather than treat it as an input from designer perspective?)

To calculate that: the count for an atomic block is one; for a flexible block, it's the sum of the counts of each choice block; for a compound block, it's the product of the counts of each of its sub-blocks; but there are subtleties. Subtlety: for a given choice of flexible block, other choice parameters at that level may not matter. Example: if a one-stage amplifier is chosen, do not count choices related to second stage. Subtlety: one higher-level choice might govern >1 lower-level choices, so don't overcount. Example: a two-transistor current mirror should have two choices (nmos vs. pmos), not four (nmos vs. pmos x 2).

Table 1 shows that MOJITO increases the op amp count by 50x compared to the other trustworthy techniques.

Table 1: Size of Op Amp Topology Spaces

Technique

# topologies

Trustworthy?

GP without reuse, e.g. [35]

>>billions

NO

DARWIN [38]

24

YES

MINLP [43]

64

YES

GP with reuse: MOJITO (this work)

3528

YES

Later on, we will describe how the fully-trustworthy space actually have 102212 (!) trustworthy designs or more, if one adds more analog design techniques (including recursion), and one proceeds to system level design (rather than just the lowest level of op amps).

2.5MOJITO Search Algorithm

We now proceed to describe an algorithm that traverses the MOJITO search space to produce a set of topologies that collectively trade off performances.

Such a flow places great demands on the effectiveness of the search algorithm. The search space is gigantic and diverse, because there can be thousands of possible topologies plus associated sizings. This means a mix of hierarchy and parameters which can be continuous-, discrete-, or integer-valued. SPICE-accurate performance estimation adds computational demand too, compared to the simplified performance estimators that most previous multi-topology sizing approaches used.

  • An evolutionary search algorithm that balances exploration with exploitation by grouping individuals by genetic age (ALPS [22]), and at a nested level achieves multiobjective search by grouping individuals by degree of nondomination (NSGA-II [10]).

  • Special operators that are designed to exploit the nature of the search space. The crossover operator respects the parameters that should be held together within building blocks, yet still allows sibling building blocks to share parameters (i.e. a mix between vector and tree search spaces). The mutation operator has tactics to avoid stealth mutations [51] on “turned-off” building blocks.

2.5.1Structure of Search Space from Search Algorithm’s Perspective

Each building block has its own parameters, which fully describe how to implement it and its sub-blocks. As we build up the hierarchy of building blocks, we eventually reach the level of the block we want to search for, such as the amplifier block. Thus, the search space for the circuit type (e.g. fully differential amplifier) is merely the possible values that each of the block’s parameters can take. Since these parameters can be continuous, discrete, or integer-valued, one could view the problem as a mixed-integer nonlinear programming problem, which one could solve with an off-the-shelf algorithm whether it be a classical MINLP solver or an evolutionary algorithm (EA) operating on vectors. But a vector-oriented view does not recognize the hierarchy, and so operations on it may have issues. One issue is that a change to variable(s) may not change the resulting netlist at all, because those variables are in sub-blocks that are turned off. From the perspective of a search algorithm, this means that there are vast regions of neutrality [26]; or alternatively the representation is non-uniformly redundant and runs the risk of stealth mutations [51]. For EAs, another issue is that an n-point or uniform crossover operator could readily disrupt the values of the building blocks in the hierarchy, e.g. the sizes of some sub-blocks’ transistors change while others stay the same, thereby hurting the resulting topology’s likelihood of having decent behavior. From an EA perspective this means that the “building block mixing” is poor [17]. What if we reconcile the hierarchy? We cannot apply a hierarchical design methodology such as [7][13], because there are no goals on the sub-blocks, just the highest-level blocks (we could, however, still apply hierarchal methodology to the results). Neither can we treat it as a tree induction problem (to be solved, for example, by grammar-based genetic programming [33][70]) because some sibling sub-blocks share the same parent blocks’ parameters.

So, the search algorithm’s perspective of the space has both tree-based and vector-based aspects. We design novel operators that reconcile both aspects, for use within an EA. First, we have a mutation operator which chooses one or more parameters to mutate. Continuous-valued parameters follow Cauchy mutation [69] which allows for both tuning and exploration. Integer-valued “part choice” parameters follow a discrete uniform distribution. Other integer and discrete parameters follow discretized Cauchy mutations. To avoid stealth mutations on “turned-off” building blocks, mutations are only kept if the netlist changes; mutation attempts are repeated until this happens. Though “neutral wanderings” of the space has been shown to help exploration in some applications [69][46], results are mixed and in general make performance more unpredictable [51]. We prefer predictability, and rely on ALPS to enhance exploration. The second operator is crossover. It works as follows: given two parent individuals, randomly choose a sub-block in parent A, identify all the parameters associated with that sub-block, and swap those parameters between parent A and parent B. This will preserve the parameters in the sub-blocks. There will still be some crosstalk because sibling blocks may use those parameters as well, but the crosstalk is relatively small compared to the 100% crosstalk that we’d have if we used standard vector-based crossover. This effectively makes the search a hybrid between tree-based and string-based search (i.e. a cross between a GA and GP).

To generate random individuals, we merely randomly choose a value for each parameter using a uniform distribution.

2.5.2The Search Algorithm

Even with a search space / operators that are as well-behaved as possible, there is a need for an highly competent search algorithm because the space is so large (there is such a large set of possible topologies and associated sizings), and the performance estimation time for an individual can be up to the order of minutes (using SPICE to maintain industrial relevance). We also need multi-objective results. The blow is softened a bit because some degree of parallel computing is allowed (industrial setups for automated sizing typically have 5-30 CPUs).

A popular, competent EA for multiobjective is NSGA-II [10] which sorts individuals by nondomination layer. NSGA-II provides a reasonable starting point for us in the design of our multiobjective EA. We use the constraint-handling approach of NSGA-II as well: a feasible individual always dominates an infeasible one, and for two infeasible individuals the one that dominates is the one with the least total constraint violation (a sum across all constraints’ violations).

One key issue with NSGA-II, and most EAs, is that they can converge prematurely. To fix this, one needs to ensure an adequate supply of building blocks [17]. Tactics include massive population sizes [35], restarting, or diversity measures such as crowding [10]. All tactics are all either painful or inadequate. Random injection of individuals might help, except they get killed off too quickly during selection. To fix that, HFC [24] segregates individuals into similar fitness layers, and restricts competition to within layers. This gives random individuals a reasonable chance. Unfortunately, the choice of fitness thresholds is complicated in practice. Moreover, near-stagnation may occur at some fitness levels because the best individuals per level have no competition.

The age-layered population structure, ALPS [22], builds on HFC, but rather than segregate individuals by fitness, it segregates by genetic age levels. The age distinction overcomes the issues of HFC. By example, age level 0 might allow individuals with age 0-19; level 1 allows age 0-39, level 2 allows age 0-59, and so on until the top level (e.g. level 9) which allows individuals of any age. Genetic age is the number of generations of an individual’s oldest genetic material: the age of a randomly generated individual is 0; the age of a child is the maximum of its parents’ ages; age is incremented by 1 each generation. If an individual gets too old for a fitness level, it gets kicked out of that level and given one last chance to compete at the next higher level. Selection at one age level uses the individuals at that level and at one level below as candidates.

Even with a search space / operators that are as well-behaved as possible, there is a need for an highly competent search

Only a single-objective, single-CPU ALPS exists in the literature. In this paper, we make it multi-objective for the first time. There are many conceivable ways to make ALPS multi-objective. We chose a pragmatic approach which is shown in Figure 9: there is canonical NSGA-II evolution at each age level, with one difference: for selection at a level l, the individuals at level l and level l-1 are candidates (rather than just at level l). In this fashion, younger high-fitness individuals can propagate to higher levels.

Figure 9: Multi-objective ALPS

2.5.3Domain Knowledge to Reshape the Space: Operating-Point Driven Formulation

This section is an example of using designer knowledge to further shape the design space; this tine at the level of parameters (not structure). It has the effect of reducing coupling among the independent design variables.

The rest of this sub-section (2.5.3) is specific to analog design, but readers from other fields may find it to be a useful reference example.

When an analog designer does manual sizing, a common approach is: pre-set the device lengths and overdrive voltages, heuristically allocate the current for each branch based on expected power consumption, then successively resolve the remaining variables by adding first- and second- order equations that relate performance constraints with design variables. Device widths “fall out” of this process [53]. This is a very reasonable approach from a designer perspective because the bias variables are more intuitive to work with, and have fewer nonlinear couplings. In contrast, by treating widths and lengths as independent variables, there are tight couplings, beginning with performance dependencies on device aspect ratio (Wi/Li) and device area (Wi*Li) and building up to even larger variable interactions at the circuit level. This leads to vast regions of the W, L search space that are completely useless (e.g. low chance of devices being saturated). Reference [40] formalizes the usefulness of having an operating-point driven formulation for automated sizing. So, we use such a space.

In the context of the MOJITO building blocks library, this means that rather than having many W’s and L’s as independent variables at the top block which propagate down to set W’s and L’s at the bottom, we instead have currents, voltages and L’s at the top, which propagate almost to the bottom. Right before instantiation into a (sized) nmos4 or pmos4 block, the incoming variables are used to compute W. In early experiments, we used first- or second- order equations to calculate W, but were unsatisfied with the accuracy. So, we switched to using a lookup table to compute W. We sampled 10,000 points in the space {L, Ids, Vbs, Vds, Vgs} and simulated both an NMOS device and a PMOS device. For each device model, we use linear-interpolation lookup table to compute W. The end result improves the searchability of the space because there is less nonlinear coupling between the independent search variables for their effect on performances. Furthermore, there actually turn out to be fewer variables because in the context of a hierarchical library, it is readily apparent how to propagate current variables to subblocks (simple example: all devices in a stack get the same current).

Finally, because we know the bias values, we can improve efficiency by pruning candidate designs that do not meet device operating constraints (DOCs), without even needing simulation.

2.6
MOJITO Multi-Topology Sizing: Experimental Results

This section describes application of MOJITO to two multi-objective multi-op-amp topology sizing problems.

2.6.1Problem Setup

The problems were set up as follows. The search space had 50 variables (topology selection variables and sizing variables). EA settings were: 100 individuals per age layer; 10 age layers, maximum age per layer: 9, 19, …, 79, 89, infinity. Each run took approximately 150 hours on a single-core 2.0 GHz Linux machine, covering 100,000 search points. Search objectives: maximize GBW, minimize power, maximize DC Gain (Experiment Set 2). Constraints: phase margin > 65°, all DOCs, DC Gain > 30dB (Experiment Set 1). Simulator was HSPICE. Technology was 0.18μ CMOS; supply voltage 1.8V; load capacitance 1pF.

2.6.2Experiment Set 1

These runs were to verify the algorithm’s ability to traverse the search space and select different topologies. The problem was set up such that the optimization end result was known a priori. Three experiments were run, the only difference between them being the common mode voltage (Vcmm,in) at the input. We know that for Vcmm,in = 1.5V, topologies must have an NMOS input pair. For Vcmm,in = 0.3V, topologies must have PMOS inputs. At Vcmm,in = 0.9V, there is no restriction between NMOS and PMOS inputs. Figure 4 illustrates the outcome of the experiments. It contains the combined results of three optimization runs. Result (a) has Vcmm,in = 1.5V, and has only topologies with NMOS inputs. It chose to use 1-stage and 2-stage amplifiers, depending on the power-GBW tradeoff. Result (b) has Vcmm,in = 0.3V, and MOJITO only returns PMOS input pairs. Note that result (a) is a result before convergence in order to retain the 2-stage amplifier in the result set. Older generations eliminate the 2-stage amplifier in favor of the folded cascode amplifier, as in result (b). For result (c) a Vcmm,in = 0.9V has been specified. Though both NMOS and PMOS input pairs might have arisen, the optimization preferred NMOS inputs. The curve clearly shows the switch in topology around GBW=1.9GHz, moving from a folded cascode input to a simple current-mirror amp. Interestingly, the search retained a stacked current-mirror load for about 250MHz GBW. Thus, Experiment 1 validated that MOJITO did find the topologies that we had expected a priori.

2.6.3Experiment Set 2

The second set of experiments was performed to verify that MOJITO could get interesting groups of topologies in a tradeoff of two or more objectives. The motivation is as follows: whereas a single-objective multi-topology optimization can only return one topology, the more objectives that one has in a multi-topology search, the more opportunity there is for many topologies to be returned, because different topologies naturally lie in different regions of performance space. In this experiment, a single run was performed, having three objectives: area, GBW, and gain. The results are shown in Figure 5. We can see that MOJITO determined (as expected): folded-cascode op amps gave high gain-bandwidth but with high area, 2-stage amps give high gain but at the cost of high area, the low-voltage current mirror load is a 1-stage with high gain, and there are many other 1 stage topologies which give a broad performance tradeoff.

Incidentally, problems of comparative complexity took status quo GP (i.e. no reuse) 100 million or more individuals [34][35], and the results were not trustworthy; it was estimated that to get to get a reasonable degree of robustness would take 150 years on a 1,000 node 1-Ghz cluster [45]. That is, it would have taken ((150 years * 365 days / year * 24 hours / day) * 1000 CPUS * 1Ghz ) / ((150 hours) * 1 CPU * 2 Ghz) = 4.4 million times more computational effort than MOJITO to get comparable results. There’s a lot to be said for topology reuse!

2.7How Far Can Reuse-Only Go? (With No Novelty)

How big can the space of possible trustworthy topologies for an industrially relevant application get, anyway? Compared to what we have just established, we can make the space even larger in many ways: new techniques, recursion, and system-level design:

  • Add more analog design techniques. The field of analog design is a research field in its own right, with its own conferences, journals, etc. Core advances in that field are precisely: new topologies and techniques! One can think of that design effort as (manual) co-evolution of building block topologies. Re-use means that you get to harness the brainpower of all the analog engineers in the world for your evolution efforts. This is not unlike how Celera used the publicly-available genome data to enhance its own genome efforts. Design opportunities and challenges arise due to new applications, different target specifications, and the steady advance of Moore’s Law. Moore’s Law alone means smaller devices, faster switching ability, more statistical variation per device, different leakage behavior (it has been getting worse until the high-k dielectrics at 45nm), new effects such as proximity [12], and often smaller supply voltages. Now that transistors are so small, one can use digital logic with thousands or millions of really tiny transistors to tune analog designs having 20-200 comparatively bigger transistors – this is a qualitative change to analog design techniques. So even op amp design has interesting new designs. Each design technique advance would increase the size of the space by at least 2x, so if we merely took the top 10 advances in op amp design, we would increase the space by at least 210=103, bringing the count to 3.5 x 106. And that is a lowball estimate: more realistically one would consider dozens hundreds of advances, and some advances could be used in multiple places in the design; if we had 10 advances which doubled, 10 which tripled, and 10 which quadrupled, then the space increases by 210 x 310 x 410 = 6 x 1013 , to total 2 x 1017 trustworthy op amp designs. Novel analog building blocks are continually designed in industry, and they can ultimately be used in the MOJITO system too.

  • Recursion. If we add the technique called gain boosting, it means that you have op amps embedded within your op amps, i.e. recursion. One level of recursion (i.e. using gain boosting) brings the count to (2 x 1017)2 = 4 x 1034, and two levels of recursion (i.e. gain boosted amps using gain boosted amps) brings the count to (4 x 1034)2 = 1.6 x 1069 trustworthy op amp designs. Yes, designers in industry do actually use two levels of gain boosting, in combination with the latest design techniques.

  • System-level design. So far we have just talked about an op amp space which is a circuit at lowest level of the design hierarchy (cell level), but higher levels exist too. The next-highest level includes circuits such as data converters (A/Ds, D/As), active filters, and more. These circuits use lower-level blocks like op amps. The level above that is typically the whole analog system, e.g. a radio transceiver like a Bluetooth or Wi-Fi implementation. The level above that would typically combine the analog and digital parts into a mixed-signal system. Each level can have many sub-blocks, and each of those sub-blocks can be any of its combinations. E.g. an A/D might have 8 different op amps. If each op amp had 1.6 x 1069 possible topologies and even if there was no other topological variation at the A/D level, it means (1.6 x 1069)8 = 4.2 x 10553 possible A/D topologies. Let’s say the system at one level higher up had an A/D, a D/A, and a couple other parts all with about the same number of topologies; then its size would be (4.2 x 10553)4 = 3.1 x 102214 possible topologies. (For reference, if just 3528 designs at the cell level, that leads to ((3528)8)4 = 10113 designs.)

Combinatorial explosion is your friend: the more possibilities of any part type, the more possible trustworthy designs you can have.

Why would one try to reinvent designs with full novelty, covering perhaps a billion designs (109) when the size of the already-invented space is 10113 designs, 102212 designs, or more? (Actually, there is good reason, as we will discuss later, but the motivations should be well-placed.)

Is search tractable? The answer is yes, and the key is to have goals within the hierarchy to decompose the search problem. We have actually described hierarchy for two uses: to describe a building block library (where there is one overall set of goals), and to describe larger and larger designs (where each higher-level design has its own goals). Then one can apply a “hierarchical design methodology” of their choice, such as a top-down constraint-driven methodology or a bottom-up multiobjective methodology. Then the difficulty of the overall problem is <= K * H where K is the number of decomposed subproblems and H is the difficulty of the hardest subproblem. The hardest sub-problem is usually the one with the largest search space, and in analog design that is the cell-level designs.

Therefore:

  1. assuming one can decompose their design into sub-problems (where each sub-problem has its own goals),

  2. assuming that one has a competent hierarchical design methodology,

  3. then if the problem of “massively multi-topology” cell-level sizing design can be cracked

  4. then one can ultimately do system-level 100% trustworthy topology design in spaces with 10113 designs, 10832 designs, or more

We can assume (1) because the decomposition is obvious in circuit design, and the names of sub-blocks are well-established (op amps, bias generators, A/Ds, D/As, filters, phase-locked loops, etc) [50][53]. We can assume (2) because competent hierarchical design methodologies have been demonstrated; and recently it has been demonstrated that they can choose from among different candidate topologies [14]. This paper has demonstrated (3). Therefore we know we can ultimately get to 10113 designs, 10832 designs, or more.

3.MULTI-TOPOLOGY SIZING WITH NOVELTY

Because of the costs of fabricating a design, the motivation for a new topology has to be strong. New topologies only come about if there is no other way, if idea has possible orders of magnitude payoff that it’s worth the money to try, or if there is some way to make trying it zero risk. That said, sometimes these motivations exist, and therefore it is of interest to see what sort of effective algorithms can be created.

This section describes MOJITO-N, a system for multi -objective and –topology sizing, that adds novelty as needed, with the flow of Figure 2, right.

3.1.1The Search Algorithm

The specifications for such a system, above and beyond (non-novelty) MOJITO, are:

  • If a topology that is known to be 100% trustworthy will meet their goals, then the tool should return that.

  • Only if no existing known topology can meet their goals should the tool resort to adding novelty.

  • If it does add novelty, it should be easy to track where and how that novelty is added, and what the payoff is.

These specifications are resolved in MOJITO-N as follows:

  • Use trustworthy designs as the structural starting points. In fact, do a long 100% trustworthy run first; then add novelty in a follow-on run.

  • Create novel designs by: copying an existing part within the parts library, mutating the copy, and then getting a new individual to use that mutated copy. In order to track novelty, remember which parts and choices are novel, and what sort of novelty-mutating operator is used. These altered libraries can be subsequently reused in future runs, therefore closing the loop in the style of run-transferable-libraries [30].

  • Have a multi-objective framework to manage trustworthiness tradeoffs: trust = -novelty, novelty = number of times that a novel part is used, and a novel part is one that has had random structural mutations. Therefore, if novelty does not actually help, it will not show up in the Pareto optimal front (but it will not necessarily be kicked out of the population; that is up to the multiobjective algorithm).

  • A novel design will almost certainly be initially worse off than a non-novel design, until it has been sized well enough to be competitive. If not handled explicitly in the EA framework, the novel design will almost certainly die off before its benefit is discovered (if it has a benefit). So that novel designs have a fighting chance: only create novel designs for the easiest-competition age layer 0. Rather than randomly generating the whole individual from a uniform distribution, choose a parent from any age layer, and novelty-mutate it for placement in layer 0. (Note: a plethora of other possible schemes exist here too, but a key enabler is the ALPS structure.)

3.1.2Experiment

The experimental setup was the same as for the non-novelty MOJITO, except for the following differences. The 100% trustworthy results from the MOJITO “Experiment Set 2” run were used as the inputs to the MOJITO-N run. MOJITO-N was run for 15 more generations (15 * 10 * 100 = 15000 more individuals), which took about 25 hours. The novelty-mutating operators were: add two-port series, add two-port parallel, add n-port parallel. The two-port parts available for add were: capacitors, resistors, nmos/pmos diodes, and biased nmos/pmos devices (a biased mos is merely transistor with a pre-set voltage bias). One more search objective was added: minimize novelty.

With the results, we output the nondominated set, and first examined if any novel individuals existed. Some did. With each novel individual, we queried its data structure to find which parts were novel, and how they were than their original part. It turns out that so far in this run, they all had the same change: the feedback capacitor Cc had been mutated to include a resistor in series. Figure 10 illustrates. This is actually a well-known design technique that one can find in many analog design textbooks: what it does is increase the effective gain from feedback; it does not help the feedforward gain as much because the feedforward path does not get its gain amplified.

Figure 10: Circuit which MOJITO-N successfully re-innovated. The circled resistor in the feedback path was not in the library; MOJITO-N added it; this is a well-known design technique.

4.RELATION TO OTHER GP WORK

This section describes the relation of this work to other work in GP, with emphasis on GPTP work.

4.1.1Automated Invention, and Analog Topology Design

The work of Koza et. al in [34][35][36][37] is focused on automated invention, and in many cases is in exactly the same problem domain (analog topology design). The work was moving towards industrial-sized circuits [37]. The work of Hu and Goodman in [25][26] was also on analog topology synthesis, though they were only doing simple linear RC circuits, which is less industrially interesting than CMOS. [26] had a useful extension to handle robustness issues due to random variation. Others’ circuit topology synthesis work includes [35][42][57][63]. McConaghy and Gielen [45] discussed the vast challenge of getting to industrially scalable novel topology design in analog circuits; the two key problems were computational effort and trust.

In [20], Hornby and Lohn evolved a design - an antenna for NASA - which was successfully deployed in the field (in space, actually!). The key difference is that though the new design was also impossible to understand, designers didn’t understand their designs before either; so there was no trustworthiness to lose. In several works including [60], Spector has evolved quantum circuits. Several groups have used GP as a means to suggest a “design” in the form of a mathematical equation. These designs get manually filtered and tweaked, then deployed in the field. Some GPTP ones include: chemical sensors [58][59], geological exploration [72], and financial markets [3][32].

4.1.2Using Prior Data, and Libraries

The work of Keijzer in [30] showed how libraries that got reused gave a tremendous speed payoff in GP evolution. In his case, the libraries were auto-discovered from previous GP runs. In our case, the first-pass libraries are pre-supplied (which reduces the initial computational effort, and brings trust). They are complementary: one can readily have a flow that starts with manually-set libraries, and each subsequent run can be used to add to the library, though for circuits there would probably be manual filtering.

Many GP schemes automatically discover functions, modules, etc. but those are typically discovered on-the-fly; which means they are not intrinsically trustworthy and have to be re-learned each time (though they give some speed payoff too).

In [29] Keijzer showed how a GP population could be stored as one giant data structure. This could be viewed as a highly homogenous library.

In [32], Korns first created a library of promising subblocks, by having one GP run per variable. He then used those as an “input library” for a second round of evolution which considered all the input variables.

4.1.3Population Management

In [61][62], Spector investigated the use of tagging and related schemes to speed GP convergence. Hu and Goodman [24][25] described the hierarchical fair competition (HFC) scheme as a framework to inject randomness in order to avoid premature stagnation. Hornby’s age-layered population structure (ALPS) [22] built on that, by segregating by age instead of fitness.

5.CONCLUSION

This paper showed how aggressive reuse of known designs brings a vast reduction in computational effort in GP applied to automated structural design. It presented a complementary pair of approaches that incorporate reuse:

  • MOJITO automatically designs 100% trustworthy structures of industrially relevant complexity, with commercially reasonable computational effort. MOJITO’s effectiveness was demonstrated in two separate experiments, showing how it hit the target designs as expected, from a library of more than 3000 possible topologies.

  • MOJITO-N adds novelty to the trustworthy designs, and returns circuits that trade off novelty with performance, also with commercially reasonable computational effort. The novelty is fully trackable, so all changes can be readily understood. MOJITO-N successfully re-innovated a known design of industrially relevant complexity.

To properly capture the relevant knowledge to reuse, we designed a parameterized generative representation [23], and then used the representation to encode a library of building blocks for the specific problem (in our case, operational amplifier design). The key to manage trustworthiness in the presence of novelty was to add an extra objective of “minimize novelty” within a multi-objective optimization framework, which results in trustworthiness tradeoffs. “Novelty” is the number of structural mutation steps taken from a 100% trustworthy design. We view our novelty-approach as “automated innovation” rather than “automated invention” because it builds on existing knowledge -- but note that patents are awarded for innovations too.

This work also used state-of-the-art ideas in EA design. It had a hybridized tree / vector view of the search space, implemented as operators having those two perspectives. It was guided by recent advances in theory of representations [51]. To avoid premature convergence and minimize sensitivity to population size setting, we employed the age-layered population structure (ALPS) [22], and embedded NSGA-II [10] into each age layer of ALPS to make it multiobjective.

These techniques can be readily extended to other GP problem domains of interest, and are complementary with many other recent advances in GP.

6.REFERENCES

  1. B.A.A. Antao, A.J. Brodersen, “ARCHGEN: Automated Synthesis of Analog Systems”, IEEE Trans. VLSI 3(2), June 1995, pp. 231-244

  2. P.J. Ashenden et al., The System Designer's Guide to VHDL-AMS, Morgan Kaufmann, 2002

  3. Y. Becker, “FIXME Symbolic Regression in Financial Markets”, Genetic Programming Theory and Practice IV, 2006

  4. E. Berkcan et al., “Analog Compilation Based on Successive Decompositions,” Proc. Design Automation Conference, 1988, pp. 369-375

  5. Cadence (2007). NeoCircuit product. Website of Cadence Design Systems Inc.

  6. E. Cantu-Paz and D.E. Goldberg, “Parallel Genetic Algorithms: Theory and Practice,” Computer Methods in Applied Mechanics and Engineering, Elsevier, 2000

  7. H. Chang, et al. A Top–Down, Constraint–Driven Design Methodology for Analog Integrated Circuits. Kluwer, 1997

  8. T.R. Dastidar et al, “A Synthesis System for Analog Circuits Based on Evolutionary Search and Topological Reuse,” IEEE Trans. Ev. Comp. 9(2), April 2005, pp. 211-224

  9. B. De Smedt and G. Gielen, “WATSON: Design Space Boundary Exploration and Model Generation for Analog and RFIC Design,” IEEE Trans. CAD 22(2), 2003, pp. 213-224

  10. K. Deb et al., “A Fast and Elitist Multi-Objective Genetic Algorithm: NSGA-II,” IEEE Trans. Ev. Comp. 6(2), April 2002, pp. 182-197

  11. A. Doboli, R. Vemuri, “Exploration-Based High-Level Synthesis of Linear Analog Systems Operating at Low/Medium Frequencies”, IEEE Trans. CAD 22(11), 2003.

  12. P. Drennan et al., “Implications of Proximity Effects for Analog Design”, Proc. CICC, 2006

  13. T. Eeckelaert et al., “Efficient Multiobjective Synthesis of Analog Circuits using Hierarchical Pareto–optimal Performance Hypersurfaces,” Proc. Design Automation and Test Europe, 2005.

  14. T. Eeckelaert et al, “An Efficient Methodology for Hierarchical Synthesis of Mixed-Signal Systems with Fully Integrated Building Block Topology Selection,” Proc. Design Automation and Test Europe, 2007

  15. F.M. E1-Turky, R.A. Nordin, “BLADES: An Expert System For Analog Circuit Design,” Proc. ISCAS, 1986, pp.552- 555

  16. G. G. E. Gielen, T. McConaghy and T. Eeckelaert, “Performance Space Modeling for Hierarchical Synthesis of Analog Integrated Circuits”, Proc. Design Automation Conference, 2005, pp. 881-886

  17. D.E. Goldberg. The Design of Innovation. Springer, 2002.

  18. H.E. Graeb et al, “The Sizing Rules Method for Analog Integrated Circuit Design”, Proc. ICCAD, 2001, pp. 343-349

  19. R. Harjani et al., “OASYS: A Framework for Analog Circuit Synthesis,” IEEE Trans. CAD 8(12), pp. 1247-1266, 1992

  20. G. S. Hornby and J. Lohn, “Automatically Evolved Antenna (FIXME)”, Genetic Programming Theory and Practice III, 2005

  21. G.S. Hornby. “Measuring, Enabling and Comparing Modularity, Regularity and Hierarchy in Evolutionary Design”, Proc. Genetic and Evolutionary Computation Conference, Springer-Verlag, 2005

  22. G.S. Hornby, “ALPS: The Age-Layered Population Structure for Reducing the Problem of Premature Convergence,” Proc. Genetic and Ev. Comp. Conf. (GECCO), 2006, pp. 815-822

  23. G.S. Hornby. Generative Representations for Evolutionary Design Automation. Brandeis University, Dept. of Computer Science, Ph.D. Dissertation. 2003

  24. J. Hu and E. Goodman, “The Hierarchical Fair Competition Framework for Sustainable Evolutionary Algorithms,” Evolutionary Computation 13(2), summer 2005, pp. 241-277

  25. Hu, Jianjun and Goodman, Erik (2004b). Topological synthesis of robust dynamic systems by sustainable genetic programming. In O’Reilly, Una-May, Yu, Tina, Riolo, Rick L., and Worzel, Bill, editors, Genetic ProgrammingTheory and Practice II, chapter 9. Kluwer, Ann Arbor.

  26. M.A. Huynen et al., “Smoothness within ruggedness: The role of neutrality in adaptation”, Proc. Natl. Acad. Sci. USA (93), 1996, pp. 397-401

  27. International Technology Roadmap for Semiconductors (ITRS), http://

  28. J. Kampe, “A New Approach for the Structural Synthesis of Analog Subsystems“, Intl. Workshop on Symbolic Methods and Applications in Circuit Design, 2000, pp. 33-38

  29. M. Keijzer, “FIXME GP Population as One Big Data Structure”, Advances in Genetic Programming II, ??

  30. M. Keijzer, “Run Transferable Libraries”, Genetic Programming Theory and Practice III, 2005

  31. H.Y. Koh et al., “OPASYN: A Compiler for CMOS Operational Amplifiers,” IEEE Trans. CAD vol. 9, Feb 1990, pp. 113-125

  32. M. Korns, “FIXME”, Genetic Programming Theory and Practice IV, 2006

  33. J.R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, 1992

  34. Koza, John R., Keane, Martin A., Streeter, Matthew J., Mydlowec, William, Yu, Jessen, and Lanza, Guido (2003). Genetic Programming IV: Routine Human-Competitive Machine Intelligence. Kluwer Academic Publishers.

  35. J.R. Koza et al. Genetic Programming IV. Kluwer, 2003

  36. Koza, John R., Jones, Lee W., Keane, Martin A., and Streeter, Matthew J. (2004a). Towards industrial strength automated design of analog electrical circuits by means of genetic programming. In O’Reilly, Una-May, Yu, Tina, Riolo, Rick L., and Worzel, Bill, editors, Genetic Programming Theory and Practice II, chapter 8. Kluwer, Ann Arbor.

  37. Koza, John R., Keane, Martin A., and Streeter, Matthew J. (2004b). Routine high-return human-competitive evolvable hardware. In Zebulum, Ricardo S., Gwaltney, David, Hornby, Gregory, Keymeulen, Didier, Lohn, Jason, and Stoica, Adrian, editors, Proceedings of the 2004 NASA/DoD Conference on Evolvable Hardware, pages 3–17, Seattle. IEEE Press.

  38. W. Kruiskamp and D. Leenaerts, “DARWIN: CMOS Opamp Synthesis by Means of a Genetic Algorithm”, Proc. Design Automation Conference, 1995

  39. K. Kundert and O. Zinke. The Designer's Guide to Verilog-AMS, Kluwer, Boston, May 2004

  40. F. Leyn et al., “An Efficient DC Root Solving Algorithm with Guaranteed Convergence for Analog Integrated CMOS Circuits”, Proc. ICCAD, 1998, pp. 304-307

  41. J.M. Liang et al., “Intelligent Systems for Analog Circuit Design Automation: A Survey,” Proc. World Multiconf. on Systems, Cybernetics and Informatics, Orlando, USA, 2001

  42. J.D. Lohn and S.P. Colombano, “Automated Analog Circuit Synthesis using a Linear Representation”, Proc. ICES, 1998, pp. 125-133

  43. P.C. Maulik et al., “Integer Programming Based Topology Selection of Cell Level Analog Circuits”, IEEE Trans. CAD 14(4), April 1995

  44. E. Martens and G. Gielen, “Top-down Heterogeneous Synthesis of Analog and Mixed-Signal Systems,” Proc. Design Automation and Test Europe, 2006. pp. 275-280

  45. T. McConaghy and G. Gielen, “Genetic Programming in Industrial Analog CAD: Applications and Challenges”, Genetic Programming Theory and Practice III, ch. 19, 2005

  46. T. McConaghy and G. Gielen, “Double-Strength CAFFEINE: Fast Template-Free Symbolic Modeling of Analog Circuits via Implicit Canonical Form functions and Explicit Introns,” Proc. Design Automation and Test Europe, 2006

  47. T. McConaghy, P. Palmers, G. Gielen, and M. Steyaert, “Simultaneous Multi-Topology Multi-Objective Sizing Across Thousands of Analog Circuit Topologies”, Proc. Design Automation Conference, 2007

  48. S. R. Nassif, “Modeling and Analysis of Manufacturing Variations,” Proc. CICC, 2001, pp. 223-228

  49. Z. Ning et al., "SEAS: A Simulated Evolution Approach for Analog Circuit Synthesis," Proc. CICC, 1991

  50. B. Razavi, Design of Analog CMOS Integrated Circuits. McGraw-Hill, 2000

  51. F. Rothlauf, Representations in Genetic and Evolutionary Algorithms, 2nd Ed. Springer, 2006

  52. R.A. Rutenbar, G.E. Gielen, and B.A. Antao, eds., Computer-Aided Design of Analog Integrated Circuits and Systems, IEEE Press, Piscataway, 2002

  53. W. Sansen, Analog Design Essentials. Springer, 2006

  54. Solido Design Automation Inc, Inc. (2007). SolidoSTAT Design Enhancer product. Website of Solido Design Automation Inc.

  55. Synopsys (2007). Circuit explorer product. Website of Synopsys Inc.

  56. A.H. Shah et al., “High-Performance CMOS-Amplifier Design Uses Front-To-Back Analog Flow,” EDN, Oct 31, 2002

  57. H. Shibata et al, “Automated design of analog circuits using cell-based structure,” Proc. Nasa/DoD Conf. Evolvable Hardware, 2002

  58. G. Smits, A. Kordon, and M. Kotanchek, “FIXME Chemical Sensor Symbolic Regression”, Genetic Programming Theory and Practice II, 2004

  59. G. Smits, A. Kordon, and M. Kotanchek, “FIXME Chemical Sensor Symbolic Regression”, Genetic Programming Theory and Practice III, 2005

  60. L. Spector, “FIXME Quantum Design with GP”, Genetic Programming Theory and Practice I?, 2003

  61. L. Spector, “FIXME Pre-Tagging Population Management”, Genetic Programming Theory and Practice III, 2005

  62. L. Spector, “FIXME Tagging Population Management”, Genetic Programming Theory and Practice IV 2006

  63. T. Sripramong and C. Toumazou, “The Invention of CMOS Amplifiers Using Genetic Programming and Current-Flow Analysis,” IEEE Trans. CAD 21(11), 2002, pp. 1237-1252

  64. K. Swings et al., “HECTOR: a Hierarchical Topology-Construction Program for Analog Circuits Based on a Declarative Approach to Circuit Modeling,” Proc. CICC, 1991

  65. H. Tang and A. Doboli, “High-Level Synthesis of Delta-Sigma Modulator Topologies Optimized for Complexity, Sensitivity, and Power Consumption,” IEEE Trans. CAD 25(3), March 2006, pp. 597-607

  66. S. Tiwary et al., “Generation of Yield-Aware Pareto Surfaces for Hierarchical Circuit Design Space Exploration,” Proc. Design Automation Conference, 2006, pp. 31-56

  67. C. Toumazou et al, “ISAID - A Methodology for Automated Analog IC Design,” Proc. ISCAS, vol. 1, 1990, pp. 531-555.

  68. G. Van der Plas et al., "AMGIE-A Synthesis Environment for CMOS Analog Integrated Circuits", IEEE Trans. CAD 20(9), Sept. 2001, pp. 1037-1058

  69. V. Vassilev, J. Miller, “The Advantages of Landscape Neutrality in Digital Circuit Evolution,” Proc. ICES, 2000, pp. 252-263

  70. P. A. Whigham, “Grammatically-based Genetic Programming,” Proc. Workshop on GP: From Theory to Real-World Applications, J.R. Rosca, ed., 1995.

  71. X. Yao et al., “Evolutionary Programming Made Faster,” IEEE Trans. Ev. Comp. 3(2), July 1999

  72. T. Yu, “FIXME Symbolic Regression for Geological Exploration”, Genetic Programming Theory and Practice III, 2005

1Each port of the embedded part is allocated to either the “parallel ports” list or “series-ABpairs” list. For parallel: stage[i].portA = base_portA for all i. For series: stage[i].portA = {base_portA if stage_i == 0, else stage[i-1].portB}, and stage[i].portB = {base_portB if stage_i == (num_stages-1), else <<new_port>>}. Example for a passive RC ladder filter: “parallel_ports” would be [GND] and “series-ABpairs” would be [(IN, OUT)].



Скачать документ

Похожие документы:

  1. 2001 strategic partnerships with industry – research and training (spirt) grants by institution - contents

    Документ
    ... be a scalabledesign of paravane ... Texture Using GeneticProgramming Summary: ... Industry (APAI) awarded : 1 RFCD: 2908 - CIVIL ENGINEERING Improved design provisions forwide ... for Promoting Reuse in Process Design and Modelling Summary: The project is novel ...
  2. 2001 Strategic Partnerships with Industry – Research and Training (SPIRT) Grants by classified to 4 digit level RFCD - contents

    Документ
    ... crust. ... GeneticProgramming ... for Promoting Reuse in Process Design and Modelling Summary: The project is novel ... Industry (APAI) awarded : 1 Administering Institution: Central Queensland University Improved design provisions forwide ... a scalabledesign of ...
  3. ECE FYP Proposals for EE and CPE Students

    Документ
    ... Novel magnetic materials for data storage applications Synopsis Data storage industry ... in the design process. In this project, an existing GeneticProgramming (GP) ... -requisite Matlab or C programmingwith Fundamental Circuit Suitable for CPE no Num of ...
  4. Crest coe 2002-2007 final report (draft)

    Документ
    ... Handbook forCorrect Systems Construction. In EU-project MATISSE: Methodologies and Technologies forIndustrial ... Programming, 55 (2005), pp. 259-288. Elsevier. [8] J. Plosila, K. Sere and M. Waldén, Designwith ...
  5. Title Agent based framework for emergency rescue and assistance planning

    Документ
    ... , reuse opportunities ... Industrial Wastes - 408 Structural Design - 723.1 Computer Programming ... forscalable ... Function evaluation - Genetic algorithms - ... withcorrect ... programmingwith polynomial constraints for black and white ... Laboratory forNovel Software ...

Другие похожие документы..