Automated Flat Circuit-Level Topology Generation Circuit Synthesis using Genetic Algorithms

Abstract

Digital and analog circuit design for integrated circuits classically has three distinct stages: topology choice, component sizing and layout generation. In the Electronic Design Au- tomation (EDA) field, the automatic topology synthesis stage is the least developed stage, particularly for analog circuits. Analog circuit design is still essentially based on human expert designers and is generally geared toward the reuse of well-known topologies in new circuit functions or to improve existing circuit topologies and, less often, to create new circuit topologies. Generation of circuit topologies can be seen as a search and optimization problem and, therefore, it can be performed with Genetic Algorithms (GAs). What is presently unclear is to what extent this can be accomplished by a GA, particularly when handled at flat circuit- level, and in concrete for the case of MOS integrated amplifiers. Boosted by the current submicron technologies used in today’s integrated circuits, MOS integrated amplifiers have high efficiencies and very optimized specifications compared to the not-so-distant past. Eventually, an automatically generated topology could not only meet such specifications, but achieve it being a novelty, that is, potentially a GA can generate new topologies different from the traditional ones. The work described in this thesis concerns the use of GAs in automatic circuit synthesis at flat circuit-level, and tries to understand its merits and its limitations, i.e., what are the capabilities of a GA in producing useful circuits and what is the relevance of additional enhancement techniques in its overall performance. In this work a GA kernel has been de- veloped using parallelism in some stages of the algorithm, namely where it is most relevant which is in the fitness evaluation stage. In this stage, fitness evaluation is accomplished by a spice-like circuit simulator run using thread-level parallelism. Part of the difficulty of obtaining good results with GAs is the choice of the codification scheme of the problem. Several coding schemes can be used for electric circuits and in this work there was a first attempt to use a codification technique for circuits that applies the classic bit strings used by the canonic (or original) GA to represent a circuit. In this representation there is a fixed number of components available to the GA and the evolution takes place by changing the nodes to which each component terminal is connected to. In several experimental results obtained with this coding simple circuits were synthesized, such as NAND gates with MOS transistors. But scaling to more complex topologies was not possible. Hence, another codification technique was attempted, and variable-length chromosomes (VLCs) were tested. Using VLCs and an encoding scheme in which a chromosome is a circuit descriptor and each gene is a component descriptor, circuits of higher complexity were synthesized by the GA, like other logic gates never successfully generated before (e.g., XOR gate and half-adder) and analog circuits (such as amplifiers of gain up to 40 dB and GBW ≈ 70 MHz ). In addition, a few techniques have been developed and incorporated in the GA which contribute to its robustness, leading to better and faster results. Robustness is enhanced because the GA has less sensitivity to initial pseudo-random generator seed and to some parameters. Better results are obtained since circuits are produced with less redundant or useless components. Also, faster results are obtained because less time is spent in circuit simulation (since the number of components in intermediate circuits is high only during a set of iterations strictly necessary). One enhancement technique presented is a heuristic that implements an adaptive proba- bility of acceptance of mutated chromosomes according to a measure of the quality of the solutions obtained. This technique enhances local exploration capabilities of the GA and reduces sensitivity to mutation probability. Another improvement technique is a “circuit cleaning” technique that eliminates redundant components in the circuit in which we dy- namically adapt the weight of a constraint to steer the algorithm towards the sub-objective of minimizing the number of components. In addition to this technique, a segmentation procedure of the GA evolution was presented, where several phases are used, each with different parametrization, which is a valuable technique to extend the steering of the GA towards sub-objectives. Circuits synthesized by the GA were shown using all the techniques described.

O projeto de circuitos digitais ou analógicos para circuito integrado tem classicamente vários estágios distintos: a escolha da topologia, o dimensionamento dos componentes e a geração do layout. Na área de “Electronic Design Automation”, o estágio da síntese automática da topologia é o menos desenvolvido, principalmente para o caso dos circuitos analógicos. O projeto de circuitos analógicos ainda ´e essencialmente baseado em projetistas (humanos) especializados, sendo muito voltado para a reutilização de topologias conhecidas em novas funções ou para o melhoramento das topologias já existentes, sendo com menos frequência orientado para a criação de novas topologias. A geração de topologias de circuitos pode ser vista como um problema de pesquisa e otimização e, portanto, pode ser realizada com Algoritmos Genéticos (AGs). O que não é claro atualmente é até que ponto isto pode ser realizado por um AG, particularmente com síntese ao nível do componente e não de subcircuitos ou de topologias preexistentes, e em concreto para o caso de amplificadores integrados MOS. Impulsionados pelas tecnologias submicrométricas atualmente usadas no fabrico de circui- tos integrados, os amplificadores integrados MOS têm hoje elevada eficiência e especificações muito otimizadas em comparação com um passado não muito distante. Eventualmente, uma topologia gerada automaticamente por um AG poderia não apenas conseguir cumprir as mesmas especificações, ou mesmo melhorá-las, e poderia até constituir uma novidade, ou seja, potencialmente um AG pode gerar novas topologias. O trabalho descrito nesta tese ´e sobre o uso de AGs na síntese automática de circuitos ao nível do componente. Nele tenta-se conhecer os méritos e as limitações dos AGs neste contexto, ou seja, tenta-se conhecer quais são as capacidades de um AG de produzir circuitos úteis e qual a relevância de algumas técnicas adicionais de melhoramento, desenvolvidas neste trabalho, no seu desempenho geral. Para este efeito foi desenvolvido um programa que realiza um AG, utilizando paralelismo em alguns estágios do algoritmo, nomeadamente onde é mais relevante que é no estágio de avaliação de desempenho de cada circuito. Neste estágio, a avaliação de desempenho é realizada por um simulador de circuitos baseado em SPICE, executado usando paralelismo ao nível da thread. Parte da dificuldade na obtenção de bons resultados com AGs está na escolha da codificação do problema. Várias formas de codificação podem ser usadas para a síntese de circui- tos elétricos e neste trabalho houve uma primeira tentativa de se usar uma técnica de codificação que aplica as sequências de bits clássicas usadas no AG canónico (ou original). Nesta representação existe um número fixo de componentes disponíveis para o AG realizar o circuito e a evolução ocorre por alteração dos nós aos quais cada terminal de um com- ponente está conectado. Em vários resultados experimentais obtidos com esta codificação foram sintetizados circuitos simples, como portas NAND com transístores MOS. Mas o escalamento para topologias mais complexas não foi conseguido. Consequentemente, foi tentada outra técnica de codificação, tendo sido escolhida e depois testada a utilização de cromossomas de tamanho variável (CTVs). Usando CTVs e um esquema de codificação em que cada cromossoma é um descritor de circuito e cada gene é um descritor de componente, foram sintetizados com sucesso pelo AG circuitos de maior complexidade, tais como portas lógicas nunca antes geradas com sucesso (por exemplo, uma porta XOR e um half-adder de duas entradas) e circuitos analógicos (como amplificadores de ganho até 40 dB e GBW ≈ 70 MHz ). Além disso, algumas técnicas foram desenvolvidas e incorporadas no AG, contribuindo para a sua robustez e levando a resultados melhores e mais rápidos. A robustez ´e melhorada porque o AG fica com menos sensibilidade não só à semente inicial do gerador pseudo-aleatório mas também a alguns parâmetros do próprio AG. Como consequência são obtidos melhores resultados porque os circuitos são produzidos com menos componentes redundantes ou inúteis. Acresce ainda que passa a haver maior rapidez na obtenção de resultados porque o tempo total gasto na simulação de circuitos diminui (uma vez que o número de componentes existente nos circuitos intermédios ´e em média menor, sendo elevado apenas durante um conjunto de iterações em que tal ´e estritamente necessário). Uma técnica de melhoramento de desempenho do AG apresentada neste trabalho é uma heurística que implementa uma probabilidade adaptativa de aceitação de cromossomas mutados de acordo com uma medida da qualidade das soluções obtidas. Esta técnica aumenta as capacidades de exploração local do AG e reduz a sensibilidade à probabilidade de mutação. Outra técnica de melhoramento ´e uma técnica de “limpeza de circuito” que elimina componentes redundantes ou inúteis no circuito, na qual se adapta dinamicamente o peso de uma restrição para se direcionar o algoritmo para o subobjetivo de minimizar o número de componentes usados no circuito. Além desta técnica, foi apresentado um procedimento de segmentação da evolução do AG onde são utilizadas várias fases, com parametrizações diferentes, o que constitui uma técnica que permite direcionar o AG para vários sub-objetivos. Usando estas técnicas, descritas e desenvolvidas neste trabalho, vários circuitos sintetizados pelo AG foram apresentados e discutidos nesta tese.