Research Of Hardware/software Partitioning Method Based On Enhanced Particle Swarm Optimization

Hardware/software(HW/SW)partitioning is the key step HW/SW co-design,with the increasement of the task complexity and design scale in embedded systems,HW/SW partitioning becomes a challenging optimization problem.Particle Swarm Optimization(PSO)is widely used in HW/SW partitioning as its simple concept,easy implementation and fast convergence speed.However,there is no a general algorithm that is suitable for solving all types of HW/SW partitioning problems.There are many difficulties for PSO to solve the HW/SW partitioning.PSO has premature convergence,long runtime and may easily get trapped into local optimum.In order to solve the problems,this paper proposes HW/SW partitioning method based on enhanced PSO.On one hand,we analyze the improved strateges to enhance the solution quality of PSO.We combine the biology intelligent behavior and other optimization algorithms,and keep both searching diversification and searching intensification.On the other hand,we analyze the time complexity of HW/SW partitioning method based on PSO.And the muti-core and GPU parallel techniques are used to accelerate the most time-consuming process.The work and major contributions are as follows:(1)Particle Swarm Optimization based on prey behavior of Fish Schooling(FSPSO)PSO may easily get trapped in a local optimum when solving complex nonlinear problems.This paper proposes an efficient improved PSO based on prey behavior of fish schooling.The fish find better place to prey according to the heuristic water wave which other fish provide,and the heuristic information can be used to enhance the global search ability in PSO.Therefore,the global best particle searches randomly towards several best positions that other particles have experienced.According to the darwin's theory of evolution,the weak fish that cannot move quickly are eaten when the fish schooling are attacked.The decimation of the weak fish can be simulated in PSO to increase the diversity of the population and prevent premature convergence.Hence,the particles in the immediate vicinity of the global worst particle are replaced by new particles.(2)HW/SW partitioning method based on Conformity Particle Swarm Optimization with Harmony Search(CPSO-HS)PSO has premature convergence,may easily get trapped into local optimum and the runtime is too long to solve the HW/SW partitioning.A HW/SW partitioning method based on CPSO-HS is presented in this paper.The particles have the psychological conformist and tend to move toward a security point,where there are lots of particles and is less possibility to be attacked by predator.By simulating the conformist mentality in CPSO-HS,the searching population can remain varied and the algorithm avoids local optimums.To improve the initialization strategy,the Harmony Search(HS)is integrated to search better position,by which the global best position is updated.Hence,the searching precision and solution quality can be enhanced.To reduce the runtime,we adopt the multi-core parallel technique to accelerate the HW/SW communication cost computing.(3)HW/SW partitioning method based on Position Disturbed Particle Swarm Optimization with Invasive Weed Optimization(PDPSO-IWO)To further enhance the performance of PSO,a HW/SW partitioning method based on PDPSO-IWO is presented in this paper.It is found by biologists that the ground squirrels produce alarm calls that warn their peers to move away when there is potential predatory threat.Here,we present PDPSO algorithm,in each iteration of which the squirrel behavior of escaping from the global worst particle can be simulated to increase population diversity and avoid local optimum.We also present new initialization and reproduction strategies to improve IWO algorithm for searching a better position,with which the global best position can be updated.Then the search accuracy and the solution quality can be enhanced.Furthermore,a Hybrid NodeRank(HNodeRank)algorithm is proposed to initialize the population of PDPSO-IWO,and the solution quality can be enhanced further.Since the HW/SW communication cost computing is the most time-consuming process for HW/SW partitioning algorithm,we adopt the GPU parallel technique to accelerate the computing.(4)Large-scale HW/SW partitioning method based on Explosion Particle Swarm Optimization(EPSO)To solve the large-scale HW/SW partitioning problem in modern embedded systems,HW/SW partitioning method based on EPSO is proposed.PSO and explosion operation in fireworks algorithm are merged.And we improve the explosion operation,the explosion positions are the personal best positions.The searching density and intensification can be increased to update the personal best positions using the explosion operation.Explosion operation is the non-iterative algorithm.The search accuracy and solution quality can be enhanced while the additional calculation amount is small.The designed large-scale HW/SW partitioning tasks demonstrate the efficiency of the proposed algorithm.