A Study on Processor Architecture Dedicated for Adaptive Genetic Algorithms

遗传算法（GAs）是已知的鲁棒和有效的搜索算法大规模，复杂的优化问题。在本研究中，我们提出了一种新的RISC处理器，其指令集是为高效执行GAs而量身定制的。所提出的RISC处理器是基于DLX指令集设计的，我们增加了一些特殊的指令，有效地实现了GAs的高速执行。新增的指令可以分为三类。第一组由面向位的指令组成，因为像交叉这样的GA操作通常需要面向位的操作。第二组由与随机数有关的指令组成。由于遗传算法经常使用随机数，因此生成伪随机数的计算时间对遗传算法的执行性能有很大影响。该处理器具有伪随机数生成电路，在每个时钟周期内生成一个伪随机数。处理器中有多条使用随机数的指令，可以有效地缩短选择、交叉和变异的计算时间。最后，添加到建议处理器的第三组指令由SIMD指令组成，主要用于实现交叉操作。由于遗传算法是在所提出的处理器上以软件的形式实现的，因此可以实现任何类型的遗传算法。仿真实验表明，使用该处理器的指令集，可将执行2点交叉等GA操作的时钟数量减少90%以上。该处理器采用Verilog硬件描述语言设计，并采用0.35μm标准单元技术实现VLSI芯片。对所制备的LSI芯片进行了测试，结果表明所提出的处理器的所有指令都能正确执行。

Genetic algorithms (GAs) are known to be robust and effective search algorithms for large-scale, complex optimization problems. In this research, we propose a new RISC processor, whose instruction set is tailored to the efficient execution of GAs. The proposed RISC Processor is designed based on the DLX instruction set, and we add several special instructions, which are effective to high-speed execution of GAs. Newly added instructions can be classified into three groups. The first group consists of bit-oriented instructions, because GA operators such as crossover often require bit-oriented operations. The second group consists of instructions concerning with random numbers. Since a GA frequently uses random numbers, the computation time for generating a pseudo-random number has a heavy effect on the performance of GA execution. The proposed processor has a pseudo-random number generation circuit, and in each clock cycle, a pseudo-random number is generated. The processor has several instructions using random numbers, which are very effective to shorten the computation time of selection, crossover, and mutation. Finally, the third group of instructions added to the proposed processor consists of SIMD instructions, which are mainly used to implement a crossover operation.Since a GA is implemented as software on the proposed processor, any kind of GA can be realized. Simulation experiments show that, using the instruction set of the proposed processor, more than 90% reduction of the number of clocks to execute GA operators such as 2-point crossover can be achieved. The processor has been designed with the Verilog Hardware Description Language, and implemented as a VLSI chip with a 0.35μm standard cell technology. The fabricated LSI chip was tested to show all the instructions of the proposed processor were executed correctly.