Hardware/software (HW/SW) partitioning is one of the crucial steps of co-design systems. It determines which components of the systems are implemented in hardware and which ones are in software. In this paper the computing model is extended to cater for the path-based HW/SW partitioning with the fine granularity in which communication penalties between system components must be considered. On the new computing model an efficient heuristic algorithm is developed, in which both speedup in hardware and communication penalty are taken into account. In addition, an efficient tabu search algorithm is also customized in this paper to refine the approximate solutions produced by the heuristic algorithm. Simulation results show that the heuristic algorithm runs fast and is able to produce high-quality approximate solutions. Moreover, the tabu search algorithm can further refine them to nearly optimal solutions within an acceptable runtime. The difference between the approximate solutions and the optimal ones is bounded by 0.5%, and it hardly increases with the increase of the problem size.
Hardware/software (HW/SW) co-design has become one of the primary applications of electronic system level tools and methodologies. It provides new opportunities for the development of high speed, low power electronic products such as embedded, communication, multimedia, and intelligent transport systems. Traditional approaches for the design of simple systems were carried out manually. However, as the systems to design have become more and more complex, manual approaches have become infeasible. Thus, it is now imperative to involve design automation at the highest possible level, in order to deal with the high complexity, increased time-to-market pressures and a set of possibly conflicting constraints.
In hardware/software (HW/SW) co-design systems, application-specific hardware is usually much faster than software, but it is significantly more expensive. Software on the other hand is cheaper to create and to maintain, but slow. Hence, performance-critical components of the system should be realized in hardware and non-critical components in software. HW/SW partitioning is to decide which components of the system should be implemented in hardware and which ones in software. It has been shown that efficient techniques for HW/SW partitioning can achieve results in performance, power or energy superior to software-only solution.
There are many different academic approaches to solve the HW/SW partitioning. The traditional approaches include hardware-oriented and software-oriented. The former starts with a complete hardware solution and iteratively moves parts of the system to the software as long as the performance constraints are fulfilled [1], [2] and [3], while the latter starts with a software program moving pieces to hardware to improve speed until the performance of the final system meets the given constraint [4], [5] and [6]. It has been shown that the HW/SW partitioning is NP-hard for most cases. Thus, in algorithmic aspect, simulated annealing algorithms [4], [7] and [8], dynamic programming algorithm [9] and [10], integer programming approaches [11] and [12] and genetic algorithms [13] and [14] are generally utilized to perform the system partitioning and hardware exploration. All these approaches can work perfectly within their own co-design environments, but it is impossible to compare them, because of the large differences in their co-design environments and the lack of benchmarks [15].
Advanced profiling techniques provide us a ‘hot path’, such as the body of a loop, that consists of the executed components with high frequency in a given application. The HW/SW partitioning for the whole application thus can be approximately solved by efficiently partitioning the selected hot path. This paper focuses on the efficient heuristic algorithms for the HW/SW partitioning on the selected hot path. Initially, we extend the computing model such that all possible communications between the neighboring components are taken into account, in order to better reflect real applications. Then we propose a fast heuristic algorithm on the new computing model to generate an approximate solution with good quality. In order to get nearly optimal solutions, we also customize a tabu search algorithm for the HW/SW partitioning to further refine the approximate solutions. Simulation results show that the proposed tabu search algorithm can refine the approximate solutions, so that the solution error to the optimal ones is no more than 0.5% for the cases considered in this paper, even if the partitioning problem is of fine granularity.
This paper is organized as follows. In Section 2, we present the computing models and formal description of the HW/SW partitioning problem. In Section 3, we describe the proposed heuristic algorithm followed by the tabu search algorithm. In Section 4, we provide the simulation results to highlight the solution quality of the proposed algorithms, by comparing them with the exact solutions. Finally, we conclude our work in Section 5.
We have proposed a heuristic algorithm for path-based HW/SW partitioning on an extended computing model in which communication penalties between neighboring components are considered. The proposed heuristic algorithm is able to produce nearly optimal solutions for the case of coarse granularity, it also can generate high-quality approximate solutions for the fine granularity. On the other hand, we have proposed an efficient algorithm based on tabu search. The tabu search algorithm is able to refine the heuristic solutions to the nearly optimal ones in acceptable runtime, both for the coarse granularity and for the fine granularity.
