Effects of Parallelization on Genetic Algorithms in Programmable Logic: Implementing a Solution to the Traveling Salesman Problem

EFFECTS OF PARALLELIZATION ON GENETIC ALGORITHMS IN PROGRAMMABLE LOGIC: IMPLEMENTING A SOLUTION TO THE TRAVELING SALESMAN PROBLEM by David J. Powers Master of Science in Electrical and Computer Engineering Electronic Engineering Option California State University, Chico Fall 2011 As the capabilities of embedded devices increase, new challenges start to arise that cannot be overcome by conventional programming means. One example of these challenges is dealing with devices capable of performing operations in parallel, either through design or across multiple cores. The task becomes not only to write an efficient program, but to also utilize the full ability of the device at hand. A Field Programmable Gate Array, through its ability to build flexible hardware designs, can perform multiple tasks at the same time. This gives the design a boost to both speed and performance, and thanks to the modular design capabilities of Hardware Description Languages, multiple copies can be instantiated of a single part of an algorithm to increase computing. capabilities. This study will take an algorithm and analyze it to find places where parallelizing the design would lead to an improvement in the system while not taking away from the end result. The algorithm in question will be a Genetic Algorithm that was designed to run on a PC, this algorithm will be analyzed to find the places where the maximum effect of parallelization can be applied inside the Field Programmable Gate Array and then compare those results with the original program. The expectation is to see an increase in speed from the PC to the Field Programmable Gate Array version, but more importantly to analyze the changes in execution as more pieces are added in parallel