A Genetic Algorithm Accelerator Based on Memristive Crossbar Array for Massively Parallel Computation

Abstract

Genetic algorithm (GA) has been extensively used for solving complex problems. Due to a high computational burden of finding solutions using GA, acceleration with hardware support has been a choice. In this paper, a GA accelerator based on the processing-in-memory (PIM) methodology to address the computational issue of GA is proposed. The proposed GA accelerator has a memristive crossbar array that can support parallelism with memory and computation combined. For letting the crossover operation for GA exploit massive parallelism provided by the array, a novel crossover scheme called aligned hybrid crossover is proposed, in which multiple multi-point crossovers coexist whose crossover bit positions are aligned. By using the memristive array, the mutation operation can also be done simultaneously for all required chromosome bits. Moreover, the fitness for weighted-sum computation-based 0-1 knapsack and subset-sum problems is shown to be evaluated in full parallel for the entire chromosomes in a population. The effects of memristance variation in the array on the fitness evaluation and the read margin are investigated. According to performance evaluation, the proposed GA accelerator having a $64\times 64$ memristive crossbar array is found to reduce the clock cycles significantly for performing operations like crossover, mutation, selection, and fitness evaluation. Specifically, for executing the generational GA with a chromosome population size of 64 with each chromosome having 64 bits, the total number of clock cycles required per generation is at least 10 times reduced as compared to conventional designs.

Keywords

• Genetic algorithm
• crossbar array
• memristor
• processing-in-memory