Transcript GaS : Genetic Algorithm Synthesis - School of Electrical Engineering

GaS : Genetic Algorithm
University
of Ottawa
Synthesis
Rami Abielmona ([email protected])
Dr. Voicu Groza ([email protected])
School of Information Technology
Engineering
Technology Mapping Evolved
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;
•
Evolve the logical circuits of simple structures;
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
5. GAs fair well in large search space problems, as
better solutions tend to “grow old with time”
What is evolvable hardware?
1. 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) “rewires” a potential solution in a very short time step
5. First major breakthrough accomplished by Adrian
Thompson’s tone discriminator in 1996
6. Intrinsic vs. extrinsic evolware
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 LUT-based
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)
5. The goal here is to minimize the number of LUTs
used in the implementation of the Boolean logic
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
•
Test bed for “evolutionary agents” concept
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
•
Figure 2
Where the chromosomes
are evaluated for fitness
assignment
3. hcache
•
Common DB for future
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
•
Shared memory – provides a common storage space
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
•
The host was implemented in the Java language
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 Virtual
Computer Corporation (VCC) as the optimizer
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 interCLB 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 ensuring
the absence of asynchronous feedback loops and
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 complexity
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 function
into 16 CLBs, but only selected functions of greater
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 (worst-case) is
1 Mb (Stage 5 evolution, 16 outputs, 64k truth table
outputs)
•
Maximum longword transfers (worst-case) is 58
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
•
The chromosomes determine how the circuit is
mapped and routed, while evolving with each
Novelties (9)
hcache
•
Hardware cache stores the solutions of the alreadyencountered 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-andplay” feature
•
Aids in SOC design, by supplying a firm
representation of a virtual component (VC)
•
Provisions for a massively-parallel system
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
7. Speaking of comparison: other GAs and minimization
algorithms
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
•
•
•
Project URL :
http://www.site.uottawa.ca/~rabielmo/g
as
Tools :
•
Hardware involved:
•
2 VCC H.O.T. platforms
•
1 PC for design and
testing
•
Xilinx Alliance (v3.1)
•
1 PC for synthesis
•
Cadence NC-VHDL Analyzer
•
•
Synopsys VHDL Analyzer,
Simulator
1 workstation for
functional simulation
•
1 PC for evolutionary
runs and observations
•
Synopsys Design Analyzer
•
Synopsys Design Checker
Languages :
•
Java (JDK 1.2.2)
•
C++ (Visual C++ 6.0, g++ 2.7.2)
•
VHDL (’87 and ’93)
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 project’s 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 view to a functional one
Contact Information Members
•
Dr. Voicu Groza
•
Rami Abielmona
•
SITE
•
SITE
•
[email protected]
•
[email protected]
•
Research interests:
•
Research interests:
•
Distributed computing
•
Evolvable hardware
•
Multimedia
communication
•
VLSI design
•
Artificial intelligence
•
Virtual Instrumentation
Questions / Comments