GaS : Genetic Algorithm Synthesis

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

  • Mee 5085 Machinery Acoustics

    Mee 5085 Machinery Acoustics

    R, Rayleigh, Surface waves, Long waves, Ground roll Love waves exist because of the Earth's surface. They are largest at the surface and decrease in amplitude with depth. Love waves are dispersive, that is, the wave velocity is dependent on...
  • Challenges and Opportunities: Setting the Agenda for Climate

    Challenges and Opportunities: Setting the Agenda for Climate

    Migration As Adaptation to Crisis in Asia. Can take many forms. Sending out some family members to live elsewhere. Deploying some family members to work elsewhere. Circular migration and commuting 'Calling in' remittances from other diaspora. Total displacement


    for customers that do not have a SCE generator output meter. Standby Demand (SB) kW = the load that the generator regularly serves and SCE is expected to instantaneously provide when the generator goes down, excluding any SCC . SB...
  • Claremont School Assessment Data

    Claremont School Assessment Data

    Claremont School Assessment Data. 2015 - 2016 . Context . All students are assessed against Individual Learning Plan targets (ILP's). The ILP's follow long term outcomes from Education, Health, Care Plans and objectives in Statements of SEN.
  • Emergency Response Kit 2016 - Allen County Public Library

    Emergency Response Kit 2016 - Allen County Public Library

    Emergency Response Kit (ERK) intended for mobile use. has double the amount of supplies as the first aid kit. includes tools. contains larger items which don't fit in a first aid kit. First Aid Kit . mounted to wall in...
  • FASI: Where can we go from here? Brandi

    FASI: Where can we go from here? Brandi

    SATP. 7/13/2013. A student's attendance pattern information is accessible from FASI. NASU. 7/13/2013. Detailing on Appls will allow you to go to the NASU Screen to view ISIR data, Budget, etc. Budgets. 7/13/2013.
  • A History of Mesquite Management in Southeast Arizona

    A History of Mesquite Management in Southeast Arizona

    Mesquite thought to be spreading as early as the 1890s, David Griffiths, J.J. Thornber. Mesquite recognized as a problem plant for the range livestock industry in the 1930s. Investigations begin in the 1940s and 50s in the Southwest. Research results...
  • Multiscale Geometric Analysis

    Multiscale Geometric Analysis

    Setting Replace samples by more general measurements based on a few linear projections (inner products) Signal Model Signal entry Xn= BnUn iid Bn» Bernoulli( ) sparse iid Un» PU Measurement Noise Measurement process is typically analog Analog systems add noise,...