Minimization of Transitions by Complementation and Resequencing using Evolutionary Algorithms

R. Drechsler and N. Drechsler (Germany)


Evolutionary Algorithms, Digital Circuit Design, Low Power, Data Ordering Problem, Transition Minimization


Power consumption of digital circuits is closely related to the switching activity. With more and more battery driven devices, as PDAs or laptops, the low power aspect is be coming one of the main issues in circuit design. In this context, the Data Ordering Problem with Inversion (DOPI) is of importance. Data words have to be ordered and (even tually) negated such that a minimal number of transitions occurs. This problem has several applications, like instruc tion scheduling, sequencing of test patterns, or cache write back. We present an Evolutionary Algorithm (EA) for the DOPI. The EA is compared to the best previously published methods. Using EAs results of the same quality as the exact method have been determined, but with much lower run times. In contrast to the exact algorithm, the EA can also be applied to larger examples and furthermore outperforms former heuristic approaches.

Important Links:

Go Back