In Proceedings of the 1995 ACM/SIGDA Third International Symposium on Field-Programmable Gate Arrays, pages 53-59, Monterey, CA, Februrary 1995. Also in WSC1: The 1st Online Workshop on Soft Computing in the Special Session on Evolutionary Electronics.
Please see the copyright notice.
Also available are a compressed PostScript version, VHDL source code, and other (newer) HGA-related papers.
next up previous
Next: Introduction

HGA: A Hardware-Based Genetic Algorithm

Stephen D. Scottgif
Dept. of Computer Science
Washington University
St. Louis, MO 63130-4899
sscott@cse.unl.edu

Ashok Samal and Sharad Seth
Dept. of Computer Science and Engineering
University of Nebraska-Lincoln
Lincoln, NE 68588-0115
samal@cse.unl.edu and seth@cse.unl.edu

Abstract

A genetic algorithm (GA) is a robust problem-solving method based on natural selection. Hardware's speed advantage and its ability to parallelize offer great rewards to genetic algorithms. Speedups of 1-3 orders of magnitude have been observed when frequently used software routines were implemented in hardware by way of reprogrammable field-programmable gate arrays (FPGAs). Reprogrammability is essential in a general-purpose GA engine because certain GA modules require changeability (e.g. the function to be optimized by the GA). Thus a hardware-based GA is both feasible and desirable. A fully functional hardware-based genetic algorithm (the HGA) is presented here as a proof-of-concept system. It was designed using VHDL to allow for easy scalability. It is designed to act as a coprocessor with the CPU of a PC. The user programs the FPGAs which implement the function to be optimized. Other GA parameters may also be specified by the user. Simulation results and performance analyses of the HGA are presented. A prototype HGA is described and compared to a similar GA implemented in software. In the simple tests, the prototype took about 6% as many clock cycles to run as the software-based GA. Further suggested improvements could realistically make the HGA 2-3 orders of magnitude faster than the software-based GA.

Keywords: Parallel Genetic Algorithms, Function Optimization, Field Programmable Gate Arrays (FPGAs), Performance Acceleration, Performance Evaluation.


  1. Introduction
  2. Background on Genetic Algorithms
  3. The HGA System
    3.1.
    The Overall HGA Design
    3.2.
    The Modules and Their Functions
    3.3.
    Design Pipelining and Parallelization
  4. Design Verification and Analysis
    4.1.
    Verification of Correct Functionality
    4.2.
    Performance Analysis
    4.3.
    Design Improvements
    4.4.
    Prototype of the HGA System
  5. Conclusion
    5.1.
    Hardware Extensions
    5.2.
    Genetic Algorithm Extensions
Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission.

FPGA '95, Monterey, CA, USA

Copyright (C) 1995 ACM 0-89791-743-x/95/0002..\$3.50

next up previous
Next: Introduction

Last modified 29 January 2007.