Arab Academy for Science and Technology and Maritime Transport College of Engineering and Technology Computer Engineering Department
FPGA IMPLEMENTATION of a PARALLEL PIPELINED HARDWARE GENETIC ALGORITHM (PPHGA) and ITS APPLICATIONS in FUNCTION INTERPOLATION
Thesis Work Submitted in Partial Fulfilment of the Requirements for the Degree of Master of Science in Computer Engineering
Submitted by : Eng. Ahmed I. Kbadragi Supervised by: Dr. Vasser Y. Hanafi Dr. Hossam E. Mostafa
Alexandria November, 2003
DECLARATIOl'I We certify that we have read the present work and lhal in our opinion it is full~ adequate in scope and quality as a dissertation lowards the partial
fulfillment of the Master degree
req~lirements i~ GmruIey 6&1~~ .en":)
from the Arab AcadeIllY for SClence and fcchnology and Manlune Transport.
Supervisors: Nal1le
··
Position
·• Signature
-:=--~--
])" Hoc;som L&4/~ (VVrJt7~
Name
Position
<---
••
fA 5si'~/c~r fhf~Jj c.'Y ) LL de,l. l--:~'~!J!-0 4&---x ~1-1 • 1-------
Sig/lature .j.k,)S-- .I'~.{
. _ - ----------
&~
--------
Exanziners:
Naltle Position
NlIllle Positioll
: ~,,~ f{1'2-1~ .. ASc. fvu Ie 5. 5" v J fZ}2 C(,(IV'f,H eJ-
11
f -t x'
Sigllature
C)./vv~.
"-
~ V\. i . V
d.,"'-~,--- {
f
V\
J
I I
~ ~_.
._ _ _ __
/ZL.:
, -
,V.D.
22.08.99
j
ABSTRACT
In this thesis the research work that is directed regards the implementation and synthesis of a parallel-pipelined hardware genetic algorithm (PPHGA) utilizing Very High Speed Integrated circuit Hardware Description Language(VHDL) for programming Field Programmable Gate Arrays(FPGA) is proposed. This implementation is then tested in the field of interpolating equations by applying the proposed design to several applications from which the superiority of the proposed design is deducted. The main design is divided into several modules. The first module is the random number generator module that is used mainly in supplying the system with all the random numbers it requires. The second module is the sequencer module which is used to draw population members in sequence from memory. The third module is the selection module which in turn is used to select members that are subjected to the genetic operations of reproduction, mutation, and crossover. Now starting the genetic processes comes the fourth module named the crossover and mutation module that is designated with the job of performing genetic operations. The fifth module is the fitness module that measures the fitness of the members and decides whether or not the end of the run has been reached. This module has an embedded floating point module to perform floating point arithmetic. Finally is the memory interface and control that organizes the work between all the modules and the memory. All modules communicate through handshaking protocol. Three applications are then experimented using our PPHGA. These are the linear interpolation, thermistor data processing, and lateral acceleration calculation.
I
Acknowledgment
I would like to express my deepest and gracious thanks to my respected supervisors, Dr. Yasser Y. Hanafi and Dr. Hossam el Deen Mostafa for their great help and support all through this research work. This help, that was the main factor to transform all the work in this thesis from abstract thoughts and ideas to real and tangible explorations in the field of research. I also want to dedicate my intimate thanks to my parents who were very caring and supportive during all the steps of this achievement.
II
Table of Contents Chapter 1: Introduction
1
Chapter 2: Genetic Algorithms
5
2.1: An overview to the world of Genetic Algorithms. 2.1.1: The genetic structure from the biological point of view. 2.1.2: The basic principles of genetic algorithms. 2.1.3: The genetic algorithm cycle layout. 2.1.4: Searching the global maximum point. 2.2: Hierarchical genetic algorithms. 2.2.1: Regulatory Sequences and Structural Genes. 2.2.2: Architecture formation of the hierarchical chromosome. 2.3: Hierarchical genetic algorithms trained neural networks. 2.3.1: An introduction to neural networks. 2.3.2: Optimizing neural networks through the application of HGA. 2.4: Microcontroller based genetic algorithms. 2.4.1: Mapping the genetic algorithm to the microcontroller. 2.4.2: Path Planning.
6 6 14 17 19 21 22 24 27 27 30 32 34
Chapter 3: Programmable Logic Devices
38
3.1: An inlet through the world of Programmable logic devices. 3.1.1: Programmable logic generations. 3.1.2: Basic programmable Logic devices. 3.1.3: More integration in programmable Logic devices. 3.1.4: Programming and design schemes. 3.1.5: Comparing different technologies in hardware design. 3.2: Field Programmable Gate Arrays. 3.2.1: FPGA internal structure. 3.2.2: FPGA basic architectural classification. 3.2.3: Different models of programming technologies. 3.2.3.1: Static RAM programming technologies. 3.2.3.2: Antifuse programming technologies. 3.2.3.3: SRAM versus Antifuse programming technologies. 3.2.4: Different FPGA families and manufacturers. 3.2.4.1: The Atmel FPGA family. 3.2.4.2: The Actel FPGA family.
39 39 39
III
36
40 45 48
51 51 53 59 60 60 63
65 65 67
Chapter 4: Software and Hardware Tools Used
72
4.1: Introduction. 4.2: Mentor Graphics FPGA Advantage.
73
4.2.1: HDL design flow with FPGA Advantage. 4.2.2: A look at HDL Designer. 4.2.3: HDL Designer series packages. 4.2.4: A look at ModelSim. 4.2.5: A look at LeonardoSpectrum. 4.2.6: Libraries in FPGA Advantage. 4.2.6.1: Library mapping. 4.2.7: Data organization. 4.2.7.1: HDL Designer design data. 4.2.7.2: FPGA Advantage design data storage. 4.2.7.3: HDL Designer design data structure.
74 74 76 76 78 79 80 81 82 83 84
85
86
4.3: The XSA-I00 Spartan-ll. 4.3.1: Applying power to the XSA board. 4.3.2: Some external connections to the XSA board. 4.3.3: Testing the XSA board. 4.3.4: Setting the XSA board clock oscillator frequency. 4.3.5: Downloading designs to FPGA and CPLD of the XSA board. 4.3.6: Downloading designs to FPGA and CPLD of the XSA board.
88
89 91 92 93
96 97
Chapter 5: Proposed Work 5.1: Introduction. 5.2: Hardware genetic algorithm structure. 5.2.1: The random number generator module. 5.2.2: The population sequencer module. 5.2.3: The selection module. 5.2.4: The crossover and mutation module. 5.2.5: The fitness module. 5.2.6: The memory interface and control module. 5.2.7: The memory module. 5.2.8: Floating point arithmetic unit. 5.2.8.1: Floating point register configuration. 5.2.8.2: Multiplication of floating point numbers. 5.2.8.3: Addition and Subtraction of floating point number. 5.2.9: The whole system.
IV
98 99 100 101 102 102 103 104 105 105 106 107 108 110
5.3: Implementation and synthesis results.
110
5.3.1: The random number generator module. 5.3.2: The population sequencer module. 5.3.3: The selection module. 5.3.4: The crossover and mutation module. 5.3.5: The fitness module. 5.3.6: The memory interface and control module. 5.3.7: The whole system.
112 113 114 115 116 117 118
5.4: The register level circuits.
120
Chapter 6: Function Interpolation Using PPHGA
121
6.1: Introduction. 6.2: Linear interpolation using PPHGA.
122 124
6.2.1: Linear interpolation methodology. 6.2.2: Linear interpolation results.
124
6.3: Thermistor data processing using PPHGA.
131
128
6.3.1: Thermistor data processing methodology. 6.3.2: Thermistor data processing results.
6.4: Computation of vehicle lateral acceleration using PPHGA. 6.4.1: Computation of vehicle lateral acceleration methodology. 6.4.2: Computation of vehicle lateral acceleration using results.
Chapter 7: Conclusion and Future Work
132 134
136 136 140
142 143 146
7.1: Discussion and conclusion. 7.2: Future work.
References
147
Appendix A
153
v
Ust of Figures
Fig.2.1. Pyrimidine-Purine pairs as a complementary structure of double-stranded DNA.
8
Fig.2.2. Nucleotides, Codons, Genes and DNA.
9
Fig.2.3. The flow from DNA to Proteins.
10
Fig.2.4. Crick's hypothesis on tRNA.
11
Fig.2.5. Holliday model for homologous genetic recombination.
12
Fig.2.6. Types and variations of mutation.
14
Fig.2.7. Roulette Wheel Selection.
17
Fig.2.8. The genetic algorithm cycle.
18
Fig.2.9. The genetic algorithm structure.
18
Fig.2.10. A 3-D objective function.
19
Fig.2.11. Generation creation.
20
Fig.2.12. Global optimal searching using GA.
21
Fig.2.13. Objective value versus generations.
21
Fig.2.14. Trans-acting factor bound on promoter for the initiation of transcription.
23
Fig.2.15. Splicing process.
24
Fig.2.16. Hierarchical chromosome structure.
24
Fig.2.17. HGA chromosome representation.
26
Fig.2.18. A three-level gene-structured chromosome.
26
VI
Fig.2.19. A multilayer feed forward back propagation network.
29
Fig.2.20. A single neuron (perceptron).
29
Fig.2.21. Hierarchical chromosome structure in HGANN.
30
Fig.2.22. Hierarchical genetic algorithm for neural network learning topology.
32
Fig.2.23. Two prototype autonomous guided vehicles.
33
Fig.2.24. Mapping of the genetic algorithm memory resources.
35
Fig.2.25. An obstacle map.
36
Fig.2.26. Visual representation of the database.
37
Fig.2.27. The member string decoding scheme.
37
Fig.3.1. (a) Simple PLD vs. complex PLD performance history and forecast by lattice and semiconductor and (b) low-density vs. high density CMOS programmable logic growth projections provided by Dataquest.
42
Fig.3.2. Block diagrams showing connectiviy differences between (a) segniet:Ited and (b) nonsegmented CPLD architecture.
43
Fig.3.3. (a) a chart showing the projected market growth for HCPLDs vs. 45 CMOS gate arrays and (b) the technology migration path for minimum feature size and growth in usable gates. Fig.3.4. Typical design flow methodology.
48
Fig.3.5. FPGA architectures block diagram of (a) row-based and (b) symmetrical FPGA.
54
Fig.3.6. compromising in segmented routing channel architecture.
56
Fig.3.7. (a) Truth table for a certain logic function. (b) Programmable interconnect point (pass transistor controlled by a memory cell). (c) Multiplexer controlled by a memory cell.
58
VII
Fig.3.B. (a) A PLICE antifuse structure cross section [78] and (b) an array 61 of antifuses [79].
Fig.3.9. (a) a three-layer metal ViaLink structure, (b) an unprogrammed ViaLink element, and (c) a programmed ViaLink element.
63
Fig.3.10. Atmel AT6000 family: (a) busing network, (b) cell-to-cell and bus-to-bus connections and (c) cell structure.
66
Fig.3.1l. ACT 1 family: (a) logic module and (b) logic module layout and basic interconnect structure.
68
Fig.3.12. Actel ACf 2 family (a) combinational logic C-module and (b) sequential logic S-module.
69
Fig.3.13.Actel ACf 2 family: (a) clock networks.
70
Fig.4.l. HDL design flow with FPGA.
75
Fig.4.2. FPGA Advantage tools.
76
Fig.4.3. HDL Designer series packages.
78
Fig.4.4. Gate-level HDL support-Design Flow.
80
Fig.4.5. Library Mapping menus.
81
Fig.4.6. Data organization.
83
Fig.4.7. HDL Designer design data.
84
Fig.4.8. The whereabouts of FPGA Advantage design data.
85
Fig.4.9. HDL Designer Design data structure.
86
Fig.4.10. An illustrative picture of the Spartan-II XSA-100 board.
88
Fig.4.1l. External connections to the Spartan-II XSA-100 board.
89
Fig.4.12. Arrangement of components on the XSA-100 board.
90
VIII
Fig.4.13. An XSA-100 board mounted on an Xstend board.
91
Fig.4.14. The TEST popup menu.
91
Fig.4.15. Setting the XSA board clock oscillator frequency menu.
93
Fig.4.16. Downloading files menu.
94
Fig.4.17. Downloading files procedure.
94
Fig.4.18. A summary to the whole design process.
96
Fig.5.1. Register organization of the floating point unit.
106
Fig.5.2. Floating point mUltiplication flow chart.
108
Fig.5.3. Floating point addition and subtraction flowchart.
109
Fig.5.4. Mentor Graphics block diagram of the system.
110
Fig.S.S. A simulation screen shot of simulating the random number generator module VHDL code.
111
Fig.S.6. The Register Level schematics.
120
Fig.S.7. The Critical path of the system.
120
Fig.6.1. Examples of interpolating polynomials: (a) first-order (linear) connecting two points, (b) second-order (quadratic or parabolic) connecting three points, and (c) third-order (cubic) connecting four points.
123
Fig.6.2. A graph showing the average fitness nourishment vs the number 131 of generations. Fig.6.3. Using PPHGA to find the optimal coefficient set.
132
Fig.6.4. Stages in Sensor data processing.
133
Fig.6.S. Normal GA error.
135
IX
Fig.6.6. MATLAB rounded floating point error.
135
Fig.6.7. PPHGA extended floating point error.
136
Fig.6.8. Lateral acceleration equation.
137
Fig.6.9. Typical parameter ranges.
137
Fig.6.10. Characteristic vehicle parameters.
138
Fig.6.11. Lateral acceleration vs Speed.
139
Fig.6.12. Steering angel multiplier vs speed.
140
Fig.6.13. Quadratic interpolation method error vs training points.
141
Fig.6.14. Hardware genetic algorithm error vs training points.
141
x
List of Tables
Table.2.1. The genetic code-from codon to amino acid.
9
Table.3.1. selection criteria for various logic options such as standard components, PLDs. Gate arrays, standard cells, and full-custom approach for relative comparison.
50
Table~6.1.
Data set through which a line fit is required.
127
Table.6.2. Linear interpolation data (First Generation).
128
Table.6.3. Linear interpolation data (Second Generation).
129
Table.6.4. Linear interpolation data (Final Generation).
130
Table.6.5. Measured resistance vs temperature vs NO counts.
134
XI
