University of Central Florida STARS Electronic Theses and Dissertations, 2004-2019 2015 Self-Scaling Evolution of Analog Computation Circuits Steven Pyle University of Central Florida Part of the Engineering Commons Find similar works at: https://stars.edu/etd University of Central Florida Libraries http://library.edu This Masters Thesis (Open Access) is brought to you for free and open access by STARS. It has been accepted for inclusion in Electronic Theses and Dissertations, 2004-2019 by an authorized administrator of STARS. For more information, please contact STARS@ucf. STARS Citation Pyle, Steven, "Self-Scaling Evolution of Analog Computation Circuits" (2015).
Electronic Theses and Dissertations, 2004-2019.edu/etd/710 SELF-SCALING EVOLUTION OF ANALOG COMPUTATION CIRCUITS by STEVEN D. University of Central Florida 2013 A thesis submitted in partial fulfillment of the requirements for the degree of Master of Science in the Department of Electrical Engineering & Computer Science in the College of Engineering and Computer Science at the University of Central Florida Orlando, Florida Summer Term 2015 Major Professor: Ronald F. Pyle ii ABSTRACT Energy and performance improvements of continuous-time analog-based computation for selected applications offer an avenue to continue improving the computational ability of tomorrow’s electronic devices at current technology scaling limits. However, analog computation is plagued by the difficulty of designing complex computational circuits, programmability, as well as the inherent lack of accuracy and precision when compared to digital implementations.
In this thesis, evolutionary algorithm-based techniques are utilized within a reconfigurable analog fabric to realize an automated method of designing analog-based computational circuits while adapting the functional range to improve performance. A Self-Scaling Genetic Algorithm is proposed to adapt solutions to computationally- tractable ranges in hardware-constrained analog reconfigurable fabrics. It operates by utilizing a Particle Swarm Optimization (PSO) algorithm that operates synergistically with a Genetic Algorithm (GA) to adaptively scale and translate the functional range of computational circuits composed of high-level or low-level Computational Analog Elements to improve performance and realize functionality otherwise unobtainable on the intrinsic platform. The technique is demonstrated by evolving square, square-root, cube, and cube-root analog computational circuits on the Cypress PSoC-5LP System-on-Chip.
Results indicate that the Self-Scaling Genetic Algorithm improves our error metric on average 7.18-fold, up to 12.92-fold for computational circuits that produce outputs beyond device range. Results were also favorable compared to previous works, which utilized extrinsic evolution of circuits with much greater complexity than was possible on the PSoC-5LP. iii TABLE OF CONTENTS LIST OF FIGURES. viii LIST OF TABLES.
xi CHAPTER ONE: INTRODUCTION. 1 Need for Evolutionary Analog Computation. 1 Characteristics of Analog Computational Circuits. 3 Characteristics of Evolvable Analog Hardware.
5 Particle Swarm Optimization. 7 Summary of the Thesis. 8 Contributions of the Thesis. 9 CHAPTER TWO: RELATED WORK.
11 Hybrid Analog-Digital Computation. 13 Evolvable Hardware for Design. 14 Evolvable Hardware for Reliability. 20 CHAPTER THREE: EVOLUTION OF ANALOG CIRCUITS.
21 Delineation of Genetic Algorithms. 29 Analog Evolution Issues. 31 CHAPTER FOUR: SELF-SCALING GENETIC ALGORITHM SUITABLE FOR ANALOG CIRCUIT EVOLUTION. 33 Self-Scaling Parameters.
34 Delineation of Particle Swarm Optimization. 35 Alterations of the Fitness Function. 36 Genetic Operators Details. 37 Adaptive Mutation Rate.
38 v Alterations to the Genome. 38 Island-Like Genetic Algorithm. 39 Hypermutation Genetic Operator. 39 Self-Scaling Genetic Algorithm.
42 CHAPTER FIVE: SELF-SCALING GENETIC ALGORITHM PERFORMANCE ANALYSIS. 43 Standard Genetic Algorithm Setup. 45 Test Case Results. 45 Square-Root Computational Circuit.
46 Cube-Root Computational Circuit. 48 Square Computational Circuit. 50 Cube Computational Circuit. 52 Overall Results Including Differential Digital Correction.
57 vi CHAPTER SIX: CONCLUSION. 60 Technical Insights Gained. 61 Scope and Limitations. 65 vii LIST OF FIGURES Figure 1: Gene’s Law Curve Showing 20-year Leap in Performance of Analog SP Compared to Digital [9].
3 Figure 2: Characteristics of Analog Benefits and Challenges Explored Herein. 4 Figure 3: Extrinsic (left) and Intrinsic (right) Evolvable Hardware Techniques. 5 Figure 4: Cypress Semiconductor PSoC-5LP System Block Diagram. 7 Figure 5: Contributions of the thesis.
9 Figure 6: Analog Computation Taxonomy. 19 Figure 7: Genetic Algorithm Flow Chart. 22 Figure 8: Genes used to represent high-level and/or low-level circuit components. Their configuration is determined by a binary string as shown.
23 Figure 9: Eight different topologies possible for PSoC-5LP SC Opamp blocks. 24 Figure 10: Breakdown of individual genome, gene expression, and binary representation for SSGA. 25 Figure 11: Pictorial representation of Tournament Selection. 26 Figure 12: Pictorial Representation of the Crossover Genetic Operator.
Both Single-Point and Two-Point variations are shown. 28 Figure 13: Mutation operation showing 2 different bit flips. 28 Figure 14: Routing architecture for PSoC-5LP Switched-Capacitor Op-Amp Blocks showing left/right local and global analog buses. 30 viii Figure 15: Analog Cube CC Evolved with Unrefined GA Compared to Ideal Curve.
31 Figure 16: Scaling Evolutionary Refinement. 34 Figure 17: SSGA design flow. 35 Figure 18: Implementation of scaling (A) and translation (B) parameters into circuit output. 35 Figure 19: PSO particle forces (shown left) and cumulative velocity vectors (shown right).
36 Figure 20: Breakdown of individual genome, gene expression, and binary representation for SSGA. 39 Figure 21: SSGA Evolved Square-Root Circuit Compared to Ideal Curve. 46 Figure 22: Typical Fitness Over Time Graph for Square-root CC Evolution with SSGA. 47 Figure 23: SSGA Evolved Cube-Root Circuit Compared to Ideal Curve.
48 Figure 24: Typical Fitness Over Time Graph for Cube-root CC Evolution with SSGA. 49 Figure 25: SSGA Evolved Square Circuit Compared to Ideal Curve. 50 Figure 26: Typical Fitness Over Time Graph for Square CC Evolution with SSGA. 51 Figure 27: SSGA Evolved Cube Circuit Compared to Ideal Curve.
52 Figure 28: Typical Fitness Over Time Graph for Cube CC Evolution with SSGA. 53 Figure 29: Average total error (red) and best total error (blue) evolution shown for both SSGA (analog evolution phase) and DDC (Digital Refinement Phase). During the analog evolution phase, the multiple average and best fitness lines are for each of the islands. 54 Figure 30: Conclusions drawn from study herein.
59 Figure 31: Summary of Challenges Addressed With Techniques Developed Herein. 60 Figure 32: Analog-based computation benefits and challenges with the thesis scope outlined. 63 ix x LIST OF TABLES Table 1: Selected Previous Works. 16 Table 2: Computational Circuit test cases used in literature and herein.
45 Table 3: Standard GA and SSGA Evolved CC Fitness Results. 55 Table 4: Results compared to previous works. 57 xi CHAPTER ONE: INTRODUCTION The exponential improvement in the ability of computers that we’ve observed over the past decades has led to a booming technology market, improvements in scientific understanding, and greater globalization as individuals are more able to connect with one another regardless of distance. With upcoming challenges facing the current status quo of Moore’s Law, new and innovative strategies to continue improving computational performance are sought.
This chapter elucidates the significance of the problem, overviews current techniques for applying analog computation, and then delineates the proposed contributions in the Contribution of Thesis section. Need for Evolutionary Analog Computation As we continue to advance towards CMOS technology-scaling limits, new and innovative strategies to enhance computational performance at our current technology scaling limits are sought. One possible approach for such enhancements lies in addressing the fundamental inefficiency in today’s computational models that utilize discretized digital computation to solve continuous real-world phenomena [1], such as signal processing and differential equation computation. An intriguing way of alleviating this inefficiency is to utilize a “let the physics do the computing” approach by employing analog devices to perform continuous time computations where applicable [1].
According to Gene’s Law as shown in Figure 1, utilizing analog computation for applicable applications could provide a 20-year leap in performance versus their digital counterparts, which translates into a theoretical 1,000 to 10,000 fold improvement [2]. Approaches 1 presented in [2, 3] demonstrated that analog computation reduced energy consumption by 8-fold compared to the corresponding digital implementation. However, complex analog circuits can be both challenging to design and lack precision. Precise and efficient complex analog circuits typically requires an expert with many years of design expertise and experience [4].
In [4] it has been shown that it’s possible to evolve robust nonlinear analog circuits with GAs, demonstrating the strength of the technique. However, due to the stochastic nature of GAs, it can be challenging to determine how accurately the evolved analog circuits map to the desired function, especially on realistic commercial devices with constrained hardware. 2 Figure 1: Gene’s Law Curve Showing 20-year Leap in Performance of Analog SP Compared to Digital [9]. Characteristics of Analog Computational Circuits Continuous-time analog computational circuits (CC) as well as discretized digital computers co-existed during the early stages of electronic computer development, as each domain offered benefits over the other for different computational needs [10-14].
However, digital-based computational models eventually won out over just about all their analog counterparts due to the benefits of noise-resilience, easy and sustainability of memory operation, and ease of programmability and reproducibility [1]. This does not imply that the benefits of analog computational models cannot be utilized in an intelligent fashion to improve current digital-only models in some hybrid fashion [2, 3]. The primary characteristics of analog-based computation to be considered when developing hybrid computing methods is shown in Figure 2, and is delineated 3 by 1) low-power, 2) speed of solution convergence, 3) low-precision, 4) noise-intolerance, and 5) difficulty of programmability or design [1]. Figure 2: Characteristics of Analog Benefits and Challenges Explored Herein.
Characteristics of Evolvable Analog Hardware Evolvable Hardware (EHW) can generally be broadly classified into two different categories shown in Figure 3 whether the application is in either the digital or analog domain: 1) intrinsic evolution, which is the evolution of circuits evaluated on a physical platform, or 2) extrinsic evolution, which is where the evaluation is conducted in a simulation environment and then can be implemented onto a physical device if so desired and the evolved circuit is compatible [15]. The majority of analog EHW studies are implemented extrinsically as there are few reconfigurable analog platforms available [4-8, 16-18]. However, some groups have developed their own Field Programmable Transistor Array (FPTA) to implement EHW techniques in the analog domain intrinsically [19]. 4 Figure 3: Extrinsic (left) and Intrinsic (right) Evolvable Hardware Techniques.
EHW techniques are applicable to more than just evolutionary design, as they can be utilized for intrinsic repair due to system faults. Faults can come in the form of soft-errors, which are caused when a bit in a register or along a datapath is flipped, or hard-errors, which are caused by the shorting or opening of wires in the hardware [20-23]. EHW techniques are typically utilized for hard faults by allowing the system to search for configurations which still provide the desired functionality even with the hardware faults in place [20, 22, 24-26]. Genetic Algorithms GAs are a well-known class of metaheuristic EAs that emulate natural forms of survival- of-the-fittest Darwinian evolution [27].
GAs utilize a population of configurations, denoted as individuals, the relative quality of their solutions, called fitness, and various bio-inspired genetic 5 operators, such as crossover and mutation, to find solutions in large search spaces [28]. The individuals “compete” via the selection method and their relative fitness levels in order to combine their genetic material to produce new individuals for the next generation. This cycle of testing, selecting, and breeding gives rise to individuals that have a very high fitness, and based on the fitness function used for evaluation these individuals should be very adept at their application. The most important things to consider when developing a GA is the genetic representation of the circuit configuration, the choice of fitness function for the particular application, the selection mechanism for choosing which individuals undergo genetic operators to produce new individuals, and the mutation rate as too low of a mutation rate can lead to early solution convergence to local minima, and too high of a mutation rate will devolve the GA into random search [29].