A genetic algorithm methodology to find the maximum datapath coverage for combinational logic circuits

Abstract

In this paper, we present a genetic algorithm (GA) based methodology for vector generation that maximizes the metric of datapath coverage for a given combinational logic circuit, and compare it with a standard greedy algorithm. The search of maximum coverage vectors is a complex optimization of a satisfiability problem. The GA deals with the optimization problem, whilst an external satisfiability solver is invoked to deal with the coverage problem. Experimental results and performance comparisons based on the large set of MCNC'91 suite of benchmark circuits are presented. They show significant speedups of the GA methodology against a greedy algorithm for large circuits.