A Prototype of FPGA Based on Genetic Algorithm Core Connected to a Cluster ()
1. Introduction
Presently, the need for fast, high-performance computing is pressing since most computational problems require an excessive amount of computing time [1]. Although FPGA speed and capacity have increased under Moore’s Law, there has been no increase in design productivity, creating a large gap between the ability of FPGAs and the ability to use them effectively. This gap increases the cost of market development time for FPGA-based designs, with insufficient design tools being one of the main factors [2]. In my research, I applied the fitness function calculation to the parallel genetic algorithm (PGA) to take advantage of the high speed of FPGA. EA are population-based metaheuristic optimization algorithms that use biology-inspired mechanisms and “survival of the fittest” theory to refine a set of solutions iteratively. GAs are a subclass of EAs where the elements of the search space are binary strings or arrays of other elementary types [3]. Tabassum et al. found that GAs have many advantages that make them one of the most preferred and widespread algorithms in Artificial Intelligence [4]. GAs have many applications; for instance, Metawa et al. proposed an intelligent model based on the GA to organize bank lending decisions in a highly competitive environment with a credit crunch constraint [5]. Cerrada et al. built up a durable system for the multi-class fault diagnosis in spur gear by selecting the best set of condition parameters on frequency and time-frequency domains, which are extracted from vibration signals by using a GA based on the k-means algorithm [6]. Deng et al. developed a new strategy to improve the genetic algorithm for solving the traditional combinatorial optimization problem, the traveling salesman problem [7]. Qiu et al. presented a GA-based optimization algorithm for a chip multiprocessor equipped with Phase-change memory (PCM) in green clouds [8]. Paul Graham et al. described a Splash 2 GA, a parallel genetic algorithm that improved symmetrical traveling salesman problems using Splash 2. In this study, each processor consisted of four FPGAs and associated memories that performed 6.8 to 10.6 times the speed of equivalent software [9]. Tang et al. implemented a GA using the domain programming gate FPGA array, which improved the speed of the genetic algorithm in parallel with the devices [10]. Finally, Torquato et al. proposed full implementation of optimized parallel GA based on FPGA to minimize system processing time, which is the main objective of this project. Torquato’s results showed that the full parallel GA implementation yielded about 16 million generations per second and acceleration between 17 and 170,000 m/s3 as supported by several works in the literature [11].
2. Theory
A GA is a heuristic search and optimization technique that uses algorithms to mimic the process of natural evolution [12]. Drawing from the theory of evolution by natural selection [13], GAs have important applications for problems related to optimization, ma-chine learning, game theory, design automation, evolvable hardware, distributed sys-terms, network security, and bioinformatics. A GA is an iterative procedure that works on groups of solution representations called chromosomes. Each chromosome consists of smaller segments of data called genes and a set of chromosomes forms a population. Genes are usually initialized randomly in each chromosome. The basic iterative work of the GA is an evolution from one population, (k), to the next population, (k+1). The solution of the optimization problem evolves toward a better solution [14]. Usually, a simple GA consists of three operations: selection, crossover, and mutation. Figure 1 below shows a flowchart of the genetic algorithm. The GA follows 6 steps:
1) Initialization: the initial population of candidate solutions is usually generated randomly across the search space.
2) Evaluation: once the population is initialized or an offspring population is created. Then, the fitness function is calculated for each element created.
3) Selection: the algorithm creates more copies of those solutions with higher fitness values, thus imposing a “survival of the fittest” mechanism on the candidate solutions.
4) Crossover: parts of two or more parent chromosomes are combined to create new solutions.
5) Mutation: while recombination operates on two or more parental chromosomes, mutation acts locally to randomly modify a solution.
6) Replacement: the offspring population created by selection, recombination, and mutation replaces the original parental population [15].
3. System Model
The system consists of five parts which are shown in Figure 2. This system includes FPGA, Arduino, a server PC, a router, and three client PCs.
1) FPGA used Xilinx Spartan 6 (SP 601). In this part of the model, we used 24 numbers from a random number generator (RAD) to increase the population in the genetic algorithm and we can use the Equation (1), is to generate these numbers.
(1)
where RAD is random number generator, NOT is inverse gate and XOR is deferential gate.
2) Arduino (UNO), an open-source platform used for constructing and programming electronics [16], was used to transfer the RAD and the constructor in FPGA by connected warring in the J13 Hader in SP601 and pin 4 in Arduino.
3) The PC server has the following specifications: CORE i5, RAM 8 G, CPU 2.5MHZ. The PC server was used to redirect the RAD to several PC clients using JAVA software.
4) The router is a local area network using router type TP _link and was used to send and receive between the server and client’s PC.
5) The client PCs had the following specifications: 1) CORE i3, RAM 4 G, CPU 2.5MHZ, 2) CORE i5, RAM 6 G, CPU 2.4MHZ, and 3) CORE i7, RAM 8 G, CPU 2.6MHZ. These PCs were used to receive the RNG and calculate the fitness function and send the result to the server.
In the following Figure 3, a flowchart for all the stages of the proposed work system.
![]()
Figure 1. Flowchart of the genetic algorithm [15].
![]()
Figure 2. Proposed system schematic diagram.
4. Result
Through this study, 24 RAD is generated inside the FPGA, as shown in Figure 4 below.
After creating random numbers within the FPGA, a 10-bit header was attached to inform the server computer to prepare to receive the beginning of the
![]()
Figure 4. The 24 random numbers generated inside the board.
packet. In addition, 2 bits were attached to the beginning of each of the three random numbers as shown in Table 1. After receiving the frame completely from the server computer, the header or the 2-bit that is used for identifying each group is ignored and each group is sent to the client computer after converting all numbers from binary to integers, using the following Equation (2):
(2)
In the following Figure 5, the numbers are sent after creating the frame to be sent to the Board of Arduino. Figures 6-8 below show the results of the values obtained from all client computers.
In the following Figure 9, the results are re-sent to the FPGA board. For comparison purposes, we note that there is a difference between the work proposed by us and the research done by researchers [17], where we note their suggestion of a parallel method for the genetic algorithm by proposing the same numbers and taking a specific set of these numbers while we suggest different groups of numbers be in one and thus the process of obtaining the correct solution or The closest solution to the correct more quickly compared to the research referred to above.
5. Conclusion
This work contributes to the implementation on FPGA and this paper proposed
![]()
Table 1. Header and indication of each group.
![]()
Figure 5. Send data to the Arduino board.
system to calculate and solve complex equations, such as high order equations in less time than other systems and with high accuracy, using PCs with only medium specifications. The proposed system adopted an enhanced genetic algorithm based on an FPGA board. The proposed system used a microcontroller based on Arduino (Uno), PCs, a Wi-Fi module, and an FPGA board. The experiments were conducted to calculate values for non-linear equations of the second order. The experiments’ results indicate that the proposed genetic algorithm can calculate the value of the equation with 100% accuracy.