Algorithmic aspects of area-efficient hardware/software partitioning

Area efficiency is one of the major considerations in constraint aware hardware/software partitioning process. This paper focuses on the algorithmic aspects for hardware/software partitioning with the objective of minimizing area utilization under the constraints of execution time and power consumption. An efficient heuristic algorithm running in O(n log n) is proposed by extending the method devised for solving the 0-1 knapsack problem. Also, an exact algorithm based on dynamic programming is proposed to produce the optimal solution for small-sized problems. Simulation results show that the proposed heuristic algorithm yields very good approximate solutions while dramatically reducing the execution time.     

Performance Improvements from Partitioning Applications to FPGA Hardware in Embedded SoCs

A hardware/software partitioning methodology for improving performance in single-chip systems composed by processor and Field Programmable Gate Array reconfigurable logic is presented. Speedups are achieved by executing critical software parts on the reconfigurable logic. A hybrid System-on-Chip platform, which can model the majority of existing processor-FPGA systems, is considered by the methodology. The partitioning method uses an automated kernel identification process at the basic-block level for detecting critical kernels in applications. Three different instances of the generic platform and two sets of benchmarks are used in the experimentation. The analysis on five real-life applications showed that these applications spend an average of 69% of their instruction count in 11% on average of their code. The extensive experiments illustrate that for the systems composed by 32-bit processors the improvements of five applications ranges from 1.3 to 3.7 relative to an all software solution. For a platform composed by an 8-bit processor, the performance gains of eight DSP algorithms are considerably greater, as the average speedup equals 28.     

Exploring optimal solution to hardware/software partitioning for synchronous model

Computer aided hardware/software partitioning is one of the key challenges in hardware/software co-design. This paper describes a new approach to hardware/software partitioning for a synchronous communication model including multiple hardware devices. We transform the partitioning into a reachability problem of timed automata. By means of an optimal reachability algorithm, the optimal solution can be obtained with limited resources in hardware. To relax the initial condition of the partitioning for optimization, two algorithms are designed to explore the dependency relations among processes in the sequential specification. Moreover, we propose a scheduling algorithm to improve the synchronous communication efficiency further after partitioning stage. Some experiments are conducted with the model checker UPPAAL to show our approach is both effective and efficient. Jifeng He: On leave from East China Normal University. The work is partially supported by the 973 project 2002CB312001 of the ministry of science and technology, and the 211 project of the ministry of Education of China. Partially Supported by National Natural Science Foundation of China (No.60173003) Received November 2004 Revised July 2005 Accepted August 2005 by Eerke A. Boiten, John Derrick, Graeme Smith and Ian Hayes     

Improving Software Performance with Configurable Logic

We examine the energy and performance benefits that can be obtained by re-mapping frequently executed loops from a microprocessor to reconfigurable logic. We present a design flow that finds critical software loops automatically and manually re-implements these inconfigurable logic by implementing them in SA-C, a C language variation supportinga dataflow computation model and designed to specify and map DSP applicationsonto reconfigurable logic. We apply this design flow on several examples fromthe MediaBench benchmark suite and report the energy and performance improvements.     

基于关键路径和面积预测的软硬件划分方法

 本文提出了一种基于关键路径和面积预测的软硬件划分方法,这种划分方法将软硬件映射和任务调度合而为一,在调度过程中同时完成软硬件的映射,充分发挥了任务调度的作用.在实验过程中,我们对比了基于模拟退火算法的软硬件划分方法(SA)和基于路径分析的软硬件划分方法(PA).实验结果表明,我们提出的方法在成功率以及结果的优化程度上都能取得更好的效果.     

An Algebraic Hardware/Software Partitioning Algorithm

Hardware and software co-design is a design technique which delivers computer systems comprising hardware and software components.A critical phase of the co-design process is to decompose a program into hardware and software .This paper proposes an algebraic partitioning algorithm whose correctness is verified in program algebra.The authors inroduce a program analysis phase before program partitioning and deveop a collection of syntax-based splitting rules.The former provides the information for moving operations from software to hardware and reducing the interaction between compoents,and th latter supports a compositional approach to program partitioning.     

An Iterative Algorithm for Hardware-Software Partitioning, Hardware Design Space Exploration and Scheduling

The paper proposes a novel heuristic technique for integrated hardware-software partitioning, hardware design space exploration and scheduling. The technique maps an application specified as a task graph on a heterogeneous architecture with an objective to minimize the latency of the task graph subject to the area constraint on the hardware coprocessor. The technique uses an iterative approach where the partitioner decides the processor mapping and HW design points of some tasks. The scheduler then simultaneously decides the processor mapping, HW design point and schedule time of the remaining tasks. There exists a tight coupling between the two design stages allowing them to produce superior quality designs in fewer iterations. The technique accounts for the time overheads due to inter-processor /intra-processor communication and shared memory access conflicts. It can therefore be used for both communication intensive and computation intensive applications. The technique also considers dynamic reconfiguration capability of the hardware coprocessor. The technique performs tradeoff analysis and maps hardware tasks to mutually exclusive temporal segments if this results in lower latency. The effectiveness of the technique is demonstrated by a case study of the JPEG image compression algorithm, comparison with an optimal ILP based approach and experimentation with synthetic graphs.     

采用启发式分支定界的软硬件划分

提出一种以任务图为描述方法的软硬件划分方法．首先分别计算芯片所需面积／时间／通信软硬件倾向度，并结合各节点的比重因子获得启发参数；然后采用启发式的分支定界法对系统进行划分，以获得可行解和最优解．通过对文中算法和RECOD和UNRET的划分算法进行编码，并在同一平台上分别计算节点数为10，15，20，25，30的系统的启动间距、最小启动间距及其所需时间，比较各算法之间的性能．文中算法适用于划分粒度较粗和中小规模的系统．