GaS : Genetic Algorithm Synthesis

GaS : Genetic Algorithm University of Ottawa Synthesis Rami Abielmona ([email protected] Dr. Voicu Groza ([email protected] .ca) Technology Mapping School of Information Technology Presentation Outline (1) Some self-imposed Q&As

Research objectives Genetic algorithms Evolvable hardware Technology mapping If the shoe fits Project detailed description

System level Optimizer/Host subsystems Presentation Outline (2) System operation Novelties and applications LUT value and routing evolution Selection algorithm

Evolutionary stages hcache Limitations / Obstacles Future enhancements / Future work Contact information

Summary What are we trying to do? 1. Attempting to evolve the minimized logic solution of a defined Boolean input function 2. The evolution is done through a hardware implementation of a genetic algorithm (GA), while the minimization is one of FPGA look-up tables (LUTs) and logic levels 3. Proof of concept involves the comparison to other minimization techniques as well as human methods 4. The objectives of the research are as follows: Minimize the logic of simple Boolean functions;

1. What are genetic algorithms? Genetic algorithms are search techniques modeled after natural selection, including the associated genetic operators 2. GAs were developed by John Holland at the University of Michigan 3. GAs are stochastic algorithms with very simple operators that involve random number generation, and copying and exchanging string structures 4. The three major operators are : selection, mutation and crossover, with fitness evaluation acting as a control factor in the feedback path 1.

What is evolvable hardware? Evolware is a term coined by Hugo De Garis in 1992 2. Consists of reconfigurable hardware that can undergo a number of evolutionary cycles to produce a solution 3. The introduction of field-programmable gate arrays (FPGAs) has allowed for the birth of evolware 4. Powerful combination of evolutionary algorithms (EAs) and programmable logic devices (PLDs) re-wires a potential solution in a very short time step What is technology mapping? 1. Technology mapping is the process by which a circuit is realized on a target chip, after its

logic synthesis 2. For example, technology mapping involves the transformations needed to take a AND-OR logic circuit into a NAND-only circuit 3. Another example involves converting to a LUTbased target chip (used in our research) 4. We use functional decomposition (Roth-Karp) in order to map to LUT-based FPGA architectures (such as Xilinx) So, what is the problem? How will GaS benefit circuit synthesis ? Proven that GAs are very efficient in locating a solution in a large search space

The number of possible subfunctions exponentially increases as the number of inputs increases Unhelpful subfunctions are progressively eliminated through the evolutionary runs Yields numerous solutions which can be further studied for various other minimization factors Parallelism, adaptation & fault-tolerance

Project Details I. System architecture Introduces optimizer/host Shows intended functionality II. Optimizer module Introduces HIGA/ECLBs/hcache Shows breakdown of functionality III. Optimizer architecture Introduces project intricacies Shows implementation of functionality System Architecture Both optimizer and host are PLDs Optimizer is where

function is evolved Host is where circuit is tested Optimizer/Host = Server/ Client Multiple hosts can connect to one optimizer Multiple functions can be Figure 1 Optimizer Module 1. HIGA Much faster because done mostly in H/W Adds caveats on the std. GA 2. ECLBs Where the chromosomes are evaluated for fitness

assignment Figure 2 3. hcache Optimizer Architecture (1) Figure 3 Optimizer Architecture (2) HIGA details RNG produces pseudo-random numbers Selection uses a hybrid algorithm to select a member for the next generation

Mutover perform standard single-point crossover and single-bit mutation Fitness evaluates the fitness of each individual Input Instantiation provides stored ideal outputs Optimizer Architecture (3) Device driver details

Controls the execution of the HIGA through the CPU interface Allows for the communication path between the simulator and the HIGA, through the JNI (Java Native Interface) A Java Virtual Machine (JVM) is instantiated from the device driver in order to assemble the valid bitstream encoded in the chromosome Device drivers are implemented in the C++ language

Optimizer Architecture (4) Host details Currently being simulated through the use of an innovative set of APIs, developed at Xilinx Inc. called JBits Provides a fast and simple interface to the Xilinx Virtex family of FPGAs The Xilinx Hardware Interface (XHWIF) allows for the use of prototyping boards instead of the simulator as the need arrives

Receives candidate chromosome, proceeds to burn it into the simulator, apply input test vectors and send back the experimental outputs Optimizer Architecture (repeat) Figure 3 Optimizer Architecture (5) Implementation details HIGA was designed using the VHDL (RTL code), and all using the Algorithmic State Machine (ASM) design

Combination allows for a deep understanding of the actual implementation and consequent functionality of system A memory access module (MAM) allows for the communication with the on-board memory as well as the device drivers Inputs to system are GA parameters and input truth table Using the H.O.T. II prototyping platform from System Operation (1)

Figure 4 System Operation (2) Figure 5 Novelties (1) LUT value AND routing evolution Delon Levi and Steven Guccione of Xilinx Inc. have worked on GeneticFPGA, a Java based tool based on the HereBoy algorithm, which evolves the LUT values, but uses static routing GaS evolves BOTH the LUT values and the inter-CLB as well as the intra-CLB routing in order to find a correct solution to the input

function (first of its kind) GaS has many more solutions to search through, but does have a higher inclination to find a better (minimal) solution GaS guarantees synchronous designs, by Novelties (2) GA caveats A hybrid of the roulette wheel selection and tournament selection algorithms, as follows: 1. Select a member using roulette; 2. Select another member using roulette; 3. Compare a random number r to a preset

parameter k, and if r < k, then select the member with the higher fitness, otherwise select the member with the lower fitness 4. Repeat until the population is full Ensures a cast-type system is utilized This is also a VGA, in that the mean size of the chromosomes changes to match problem Novelties (3) Figure 6 Novelties (4) Evolutionary stages

There are 5 stages of evolution Stage 1 : 1 CLB & 1 potential subfunction Stage 2 : 2 CLBs & 2 potential subfunctions Stage 3 : 4 CLBs & 4 potential subfunctions Stage 4 : 8 CLBs & 8 potential subfunctions Stage 5 : 16 CLBs & 16 potential

subfunctions Only feed-forward paths are allowed, and LUT inputs are guaranteed to be registered outputs Currently, CAD tools can map any 8 input Figure 7 Novelties (6) Chromosome structure Number of bytes per chromosome per stage

Stage 1 : 8 bytes = 2 longword transfers Stage 2 : 12 bytes = 3 longword transfers Stage 3 : 20 bytes = 5 longword transfers Stage 4 : 48 bytes = 12 longword transfers Stage 5 : 116 bytes = 29 longword transfers Maximum amount of needed memory (worstcase) is 1 Mb (Stage 5 evolution, 16 outputs,

64k truth table outputs) Figure 8 Novelties (8) Chromosome encoding Chromosomes are made up of route bits and LUT bits The LUT bits are used to set the appropriate LUT The route bits are used to decide where the input to a LUT comes from (input variable or previous subfunction)

If a LUT input has been assigned to a previous subfunction, then no input variable can be routed to it Novelties (9) hcache Hardware cache stores the solutions of the already-encountered truth tables With parallelism, hcache will become a common storage facility that any host can use to decide whether to evolve the specific truth table or not

hcache allows for the integration of different structures within the overall system, by a plug-and-play feature Aids in SOC design, by supplying a firm representation of a virtual component (VC) Achievements 1. The HIGA has been designed, implemented and tested 2. It has been synthesized to fit on XC4062XLA target 3. The device drivers as well as the host have been implemented and tested 4. The communication path between the optimizer and the host is also successfully functioning

5. Preliminary simulation results have been obtained (see next slide) 6. A GA was designed and implemented in the C language for future comparison Limitations / Obstacles 1. No system simulations could be presented as our design PC and prototyping platform both have been recently diagnosed with hardware faults 2. We are working on resolving both issues in order to carry our evolutionary runs (more on this later) 3. Currently, only 1-16 variable input functions can be processed 4. Currently, only one input function can be placed on the evolutionary test bed 5. Currently, the host is simulated in software

Contact Information Project URL : Hardware involved: Project lmo/gas Tools : 2 VCC H.O.T. platforms 1 PC for design and

testing Xilinx Alliance (v3.1) Cadence NC-VHDL Analyzer 1 PC for synthesis Synopsys VHDL Analyzer, Simulator

1 workstation for functional simulation Synopsys Design Analyzer Synopsys Design Checker 1 PC for evolutionary runs and observations Languages : Java (JDK 1.2.2)

C++ (Visual C++ 6.0, g++ 2.7.2) Future Enhancements 1. The host will be ported (through the XHWIF) to a commercially available FPGA-based hardware 2. Evolutionary runs will be posted on the projects URL as they are being processed 3. A graphical user interface is being designed in order to simplify the internals and clearly present experimental results Future Work 1. More than one input function will be able to be processed simultaneously (parallelism) 2. Functions with more than 16 variables will be

able to be processed 3. GaS aids in the future evolution of complex circuitries 4. The concept of hcache Summary The objectives of this research is to implement minimized solutions of Boolean functions Simulations will be posted on the URL and in future reports in order to document the proof of concept GaS has many innovative ideas (LUT and routing evolution, evolutionary stages,

hcache) that allow for the fast and directed evolution of solutions GaS is the underlying foundation to the evolution of more complex circuitries and drives the shift of design from a structural Contact Information Members Dr. Voicu Groza Rami Abielmona

SITE SITE [email protected] Research interests: [email protected] .ca

Research interests: Distributed computing Multimedia communication Evolvable hardware VLSI design Artificial

Questions / Comments

Recently Viewed Presentations

  • Overview of IEEE 802.22 Standard

    Overview of IEEE 802.22 Standard

    1) TLS use of ECDHE or ECDSA as specified in RFC 4492 "Elliptic Curve Cryptography (ECC) Cipher Suites for Transport Layer Security (TLS)" is not unencumbered. Implementers of that RFC require a copy of IPR disclosure that Certicom filed with...
  • Financial Accounting and Accounting Standards

    Financial Accounting and Accounting Standards

    Effects of a liquidating dividend on the consolidated statements workpaper entries: Assume that P Company acquired an 80% interest in S Company on January 2, 2009, for $560,000. At the time of purchase, S Company had capital stock and retained...
  • Scavenger Hunt - Pc&#92;|Mac

    Scavenger Hunt - Pc\|Mac

    Blackboard Scavenger Hunt Advance to next slide to begin your Scavenger Hunt. Click on each Blackboard icon for Scavenger Hunt directions. Go to the Word documents in Lesson 1 to help you perform the activities. Email your instructor and let...
  • WAOL Advisory Group Monday, March 21, 2011 Title

    WAOL Advisory Group Monday, March 21, 2011 Title

    Take Aways: Remind faculty to back-up frequently. Check profiles in Elluminate. F-2-F Tegrity training April 28 and 29—info to be sent Wed. Elluminate -need to get off v10 and move to Gemini by December 2012—maybe allow Gemini as choice this...
  • Catálogo de crianza natural y ecológica para mamás y niños

    Catálogo de crianza natural y ecológica para mamás y niños

    Catálogo de productos para la crianza natural y ecológica. Primavera-Verano 2011 Portabebés Fulares y bandoleras Storchenwiege. Elaborados en algodón 100% natural y teñidos con colores libres de substancias químicas tóxicas.
  • Week 24: February 24-28, 2014 Unit IV: World War II &amp; early ...

    Week 24: February 24-28, 2014 Unit IV: World War II & early ...

    The General Assembly is the main deliberative, policymaking and representative organ of the United Nations. Comprising all . 193 Members of the United Nations, it provides a unique forum for multilateral discussion of the full spectrum of international issues covered...
  • To assess whether our patients with food allergy and asthma ...

    To assess whether our patients with food allergy and asthma ...

    A child is admitted to hospital every twenty minutes due to asthma exacerbation. We therefore need to ensure in conjunction with the NICE guidelines that our patients receive an allergy action plan, asthma management plan and receive training on how...
  • Course 7: Electronics

    Course 7: Electronics

    We know that the only differences between squirrel cage and slip-ring motors lie in the rotor, slip-rings and brush assembly. In this unit, we are going to look at the additional electrical and mechanical tests that must be conducted on...