An Improved Two-dimension Enhanced Greedy Hardware/Software Partitioning Algorithm

Embedded system is composed by software and hard ware. So, software/hardware partition is a critical step among software/hardware co-design. The definition of software/hardware partition is that map function blocks to software or hardware. The purpose of SW/HW partition is to obtain optimal performance satisfying multiple performance constraints. Such as hardware area A, power cost P and the memory cost M, and so on. The most existing HW/SW partitioning algorithms use orient-HW or orient-SW as initial state and use the method of iteration mapping every functional block to hard ware or soft ware.This paper intends to minimize runtime satisfying A, P, M and solve Hardware/software problem. using two-dimension enhanced greedy algorithm The algorithm can obtain the purpose of minimizing runtime of system and satisfying A, P, M.This paper proposes a method about creating initial state, which converts the partition problem P to two child partition problem and deduces the problem complexity and time complexity. When the scale n of partition problem P become bigger, the complexity of the problem deduces one order of magnitude, searching space will reduce half and time complexity will reduce greatly. HW/SW partition problem can use many directed acyclic graph as task model, such as data flow graph (DFG), control flow graph (CFG) and signal flow graph (SFG), and so on. This paper uses coarse granularity CFG witch the node of represent the task block or functional block as partitioning problem model.This paper analysis detailed each performance indexes which affect the embedded system's performances. Propose an improved enhanced greedy hardware/software partitioning algorithm. By using the reusable characteristics of SoC, introduces IP kernel reusing and software architecture reusing to HW/SW partition problem algorithm. By abstracting the functional block level, maps the complex embedded system to DAG.Finally, this paper proves that the convergence speed of the algorithm is much more superior.