NASA NTRS2004
This paper discusses the problem of increased programming time for intrinsic evolvable hardware (EM) as the complexity of the circuit grows. As the circuit becomes more complex, then more components will be required and a longer programming string, L, is required. We develop equations for the size of the population, n, and the number of generations required for the population to converge, based on L. Our analytical results show that even though the design search space grows as 2L (assuming a binary programming string), the number of circuit evaluations, n*ngen, only grows as O(Lg3), or slightly less than O(L). This makes evolvable techniques a good tool for exploring large design spaces. The major hurdle for intrinsic EHW is evaluation time for each possible circuit. The evaluation time involves downloading the bit string to the device, updating the device configuration, measuring the output and then transferring the output data to the control processor. Each of these steps must be done for each member of the population. The processing time of the computer becomes negligible since the selection/crossover/mutation steps are only done once per generation. Evaluation time presently limits intrinsic evolvable hardware techniques to designing only small or medium-sized circuits. To evolve large or complicated circuits, several researchers have proposed using hierarchical design or reuse techniques where submodules are combined together to form complex circuits. However, these practical approaches limit the search space of available designs and preclude utilizing parasitic coupling or other effects within the programmable device. The practical approaches also raise the issue of why intrinsic EHW techniques do not easily apply to large design spaces, since the analytical results show only an O(L) complexity growth.