Paper Info
Title
Efficient evolutionary approaches for the data ordering problem with inversion
Abstract
An important aim of circuit design is the reduction of the power dissipation. Power consumption of digital circuits is closely related to switching activity. Due to the increase in the usage of battery driven devices (e.g. PDAs, laptops), the low power aspect became one of the main issues in circuit design in recent years. In this context, the Data Ordering Problem with and without Inversion is very important. Data words have to be ordered and (eventually) negated in order to minimize the total number of bit transitions. These problems have several applications, like instruction scheduling, compiler optimization, sequencing of test patterns, or cache write-back. This paper describes two evolutionary algorithms for the Data Ordering Problem with Inversion (DOPI). The first one sensibly improves the Greedy Min solution (the best known related polynomial heuristic) by a small amount of time, by successively applying mutation operators. The second one is a hybrid genetic algorithm, where a part of the population is initialized using greedy techniques. Greedy Min and Lower Bound algorithms are used for verifying the performance of the presented Evolutionary Algorithms (EAs) on a large set of experiments. A comparison of our results to previous approaches proves the efficiency of our second approach. It is able to cope with data sets which are much larger than those handled by the best known EAs. This improvement comes from the synchronized strategy of applying the genetic operators (algorithm design) as well as from the compact representation of the data (algorithm implementation).
Year
DOI
Venue
2006
10.1007/11732242_29
EvoWorkshops
Keywords
Field
DocType
circuit design,low power aspect,algorithm implementation,data word,algorithm design,efficient evolutionary approach,hybrid genetic algorithm,evolutionary algorithm,lower bound algorithm,data ordering problem,genetic operator,compiler optimization,power dissipation,graph theory,digital circuits,instruction scheduling,lower bound
Population,Heuristic,Algorithm design,Evolutionary algorithm,Instruction scheduling,Computer science,Algorithm,Greedy algorithm,Optimizing compiler,Genetic algorithm
Conference
Volume
ISSN
ISBN
3907
0302-9743
3-540-33237-5
Citations 
PageRank 
References 
4
0.48
16
Authors
2
Name
Order
Citations
PageRank
Doina Logofatu11716.74
Rolf Drechsler23707351.36