Research On Low Power Hardware/Software Partitioning Algorithms

Portable embedded mobile equipments, for example, mobile phones or PDAs, are widely used, which promote embedded systems from being embedded into other instruments and not known by common user to being touched and accepted by them. Facing the strict constraints about energy usage of portable embedded mobile equipments powered by batteries and the current status that the development speed of battery technology is behind the development of integrated circuits, low power embedded systems design has been emphasized by academes and industries.Whereas hardware/software partitioning affects system cost and performance enormously, we developped research about optimization algorithms and related techniques for solving low power hardware/software partitioning problems. Low power hardware/software partitioning is combinatorial optimization problem with NP-Hard complexity. By reviewing forgone related work, we found that ascertained algorithm, for instance, integer programming or branch and bound, only solve problems in miniature with accurate solutions. A majority of complicated problems need rely on heuristic algorithms, for instance, genetic algorithm or simulated annealing algorithm, to find approximate optimal solutions. But the absence of low power formal model of hardware/software partitioning in accord with actual problems results in that most of forgone related work only solves low power hardware/software partitioning problems of special occasions, and these algorithms and techniques are not general, besides it is difficult to contrast different algorithms and techniques. As another point of view, current intelligent optimization algorithms go ahead fast, on the one hand new algorithms are designed by absorbing respective advantage of different algorithms, and so these hybrid algorithms usually exhibit better global optimization capabality and faster speed of exploring design space; on the another hand after continually observing the process of substance transforming and organism evolving, researchers brought forward some new intelligent optimization algorithms, and then it is worth thorough research that use them to solve low power hardware/software partitioning problems.As the research foundation of hardware/software partitioning algorithms, we define the formalized low power model of system level hardware/software partitioning, whose target system architecture is embedded multi-processors, and the optimization objective is power, at the same time the constraints are the memory size of every processor, the area of every specific integrated circuit and system execution time. Some assumptions are the foundation of the formal model, which properly simplify the hardware/software partitioning problem and seperate it from other interrelated problems, so the model can represent large numbers of practical design instances.Although heuristic algorithms, for example, constructive algorithm, genetic algorithm or simulated annealing algorithm have been used to solve low power hardware/software partitioning problem, while they usually exhibit slow execution speed and easily fall into local optimization. In view of fine"climb mountains"ability of tabu search algorithm and excellent behavior of neural network for solving other combination optimization problems, we design the tabu search algorithm based on neural network, which contains the fine characteristic of neural network and tabu search. The basic idea of it is: the refractory effect of inhibiting repetitive firing is one of the characteristics of real biological neurons, which is similar to the tabu effect of tabu search, so tabu search can be realized by a neural network in which neurons inhibited by the refractory effect correspond to the tabu moves. The simulation result for several real task graphs indicates that the algorithm outperforms genetic algorithm with better global exploring speed and exploiting ability for design space.For hardware/software partitioning problems of more large size, the tabu search based on neural network still easily falls into local optimization. For promoting the global optimization ability for large size problems, we introduce chaotic dynamic into neural network and get tabu search based on chaotic neural network, and these characters that chaotic can go over all the design space with exquisite inner order make it be capable of leading exploration to break through local optimization. The simulation result for GSM encoder task graph indicates that it exhibits excellent global convergence and nice speed for large size task graph, and the hardware/software partitioning results gotten exceed those from genetic algorithm. For solving low power hardware/software partitioning problems, we designed hybrid intelligent optimization algorithms by absorbing respective advantage of neural network, chaotic optimization and tabu search, while these two hybrid algorithms can also be used to solve other combination optimization problems.Quantum computation sprang up in recent years, and it introduces concept and theory of quantum mechanics into arithmetic scopes by utilizing superposition and coherence of quantum state along with entanglement between quantum bits. Intrinsic parallel characteristic of quantum computation is the essential difference with classical computing meithods, and therefore if quantum computation and genetic algorithm is connected to get quantum genetic algorithm, which will be able to find optimal solutions in less time and smaller genome. For target system architecture containing several processing elements, we designed quantum genetic algorithm to solve low power hardware/software partitioning problems, which utilizes chromosome to represent the mapping from system design task to processing element, then use quantum bit encoding to represent chromosome, and unique probability amplitude of quantum bit encoding makes each chromosome represent many mappings, and then update the evoluation exploration by quantum rotated gate, which guarantee the diversity of the genosome. The simulation result for MP3 decoder and GSM decoder indicates that the quantum genetic algorithm can produce smaller mean and variance of power than genetic algorithm, with steady evolution progress and excellent capability to escape from local optimum. Our work is the first time of using quantum genetic algorithm to solve low power hardware/software problem, and it expands the application scopes of quantum genetic algorithm.For target system architecture of embedded multi-precessors, the low power hardware/software partitioning problem, whose optimization objective is power and constraints are the area of every specific integrated circuit, the memory size of every processor and system execution time, belongs to single objective optimization, which can meets a majority of design requirements. While some system design requires simultaneous optimization of power and other design objectives, for example, system execution time. For such hardware/software partitioning problem of multiobjective optimization, we designed multiobjective evolution algorithm based on Pareto archive population evolution and individual integration, and simultaneously optimized system execution time and power under constraints of the area of every specific integrated circuit and the memory size of every processor. That the co-evolution mechanism of elitist population and single objective population along with tournament selection rule of migrating fine individuals from elitist population to single objective population, improve the convergence speed and the precision of non-dominated solutions. For the multiobjective hardware/software partitioning simulation of mapping GSM decoder task graph into one general processor and two special integrated circuits, it can obtain a set of non-dominated solutions that uniformly distribute in the Pareto front, and the evolution of elitist population and individual integration has important influence for convergence speed and precision of solutions. The multiobjective optimization of hardware/software partitioning meets different design requirements, and eventually the designers may select one of hardware/software partitioning results according to practical design requirements. The multiobjective evolution algorithm based on Pareto archive population evolution and individual integration outperforms NSGA-II and PAES algorithm for solving hardware/software partitioning problem, and when properly design optimization objectives and constraints, it also can be used to solve multiobjective function optimization problems.