Comparing Three Heuristic Search Methods for Functional Partitioning in Hardware–Software Codesign

This paper compares three heuristic search algorithms: genetic algorithm (GA), simulated annealing (SA) and tabu search (TS), for hardware–software partitioning. The algorithms operate on functional blocks for designs represented as directed acyclic graphs, with the objective of minimising processing time under various hardware area constraints. Thecomparison involves a model for calculating processing time based on a non-increasing first-fit algorithm to schedule tasks, given that shared resource conflicts do not occur. The results show that TS is superior to SA and GA in terms of both search time and quality of solutions. In addition, we have implemented an intensification strategy in TS called penalty reward, which can further improve the quality of results.     

An Algorithm for Hardware/Software Partitioning Using Mixed Integer Linear Programming

One of the key problems in hardware/software codesign is hardware/software partitioning. This paper describes a new approach to hardware/software partitioning using integer programming (IP). The advantage of using IP is that optimal results are calculated for a chosen objective function. The partitioning approach works fully automatic and supports multi-processor systems, interfacing and hardware sharing. In contrast to other approaches where special estimators are used, we use compilation and synthesis tools for cost estimation. The increased time for calculating values for the cost metrics is compensated by an improved quality of the values. Therefore, fewer iteration steps for partitioning are needed. The paper presents an algorithm using integer programming for solving the hardware/software partitioning problem leading to promising results.     

Design and evaluation of data allocation algorithms for distributedmultimedia database systems

A major cost in retrieving multimedia data from multiple sites is the cost incurred in transferring multimedia data objects (MDOs) from different sites to the site where the query is initiated. The objective of a data allocation algorithm is to locate the MDOs at different sites so as to minimize the total data transfer cost incurred in executing a given set of queries. The optimal allocation of MDOs depends on the query execution strategy employed by a distributed multimedia system while the query execution strategy optimizes a query based on this allocation. We fix the query execution strategy and develop a site-independent MDO dependency graph representation to model the dependencies among the MDOs accessed by a query. Given the MDO dependency graphs as well as the set of multimedia database sites, data transfer costs between the sites, the allocation limit on the number of MDOs that can be allocated at a site, and the query execution frequencies from the sites, an allocation scheme is generated. We formulate the data allocation problem as an optimization problem. We solve this problem with a number of techniques that broadly belong to three classes: max-flow min-cut, state-space search, and graph partitioning heuristics. The max-flow min-cut technique formulates the data allocation problem as a network-flow problem, and uses a hill-climbing approach to try to find the optimal solution. For the state-space search approach, the problem is solved using a best-first search algorithm. The graph partitioning approach uses two clustering heuristics, the agglomerative clustering and divisive clustering. We evaluate and compare these approaches, and assess their cost-performance trade-offs. All algorithms are also compared with optimal solutions obtained through exhaustive search. Conclusions are also made on the suitability of these approaches to different scenarios     

基于ARM9的数字对讲机基带SoC设计

数字化是对讲机领域的发展趋势。采用软硬件协同设计的思想,提出了1种基于ARM946E-S内核的数字对讲机基带SoC结构,并给出各处理单元的功能,从技术和成本两方面考虑进行软硬件划分,给出具体的设计方法和软硬件验证方法。     

基于改进禁止搜索算法的矢量量化码书设计

本文提出了基于改进禁止搜索(TS)算法的矢量量化(VQ)码书设计方法.禁止搜索算法的关键是如何定义一个解以及如何在当前解的基础上生成邻域解.由于码书设计的两个优化准则是最邻近条件和聚类质心条件,本文提出了两种禁止搜索算法的解描述方案,其相应算法分别叫基于码书的禁止搜索(CB-TS)算法和基于聚类划分的禁止搜索(PB-TS)算法.为了提高禁止搜索算法的性能,文中在禁止搜索算法中融入了模拟退火(SA)机制.为了进一步提高码书性能,文中还将码书设计的传统LBG算法融入禁止搜索算法中.结果表明,基于禁止搜索的两种码书设计方案所生成的码书性能都比LBG算法有明显提高.     

基于程序执行轨迹的SoC硬件加速模块提取方法

程序执行轨迹（Program executions trace，以下简称trace）是程序执行过程的指令流信息的记录，trace完整地记录了程序执行过程中所执行指令的内容和顺序。对于大多数程序，少数几个较短的热trace决定了系统的总体性能。本文提出了基于程序执行轨迹提取加速模块的软硬件划分方法。利用热trace提取算法划分系统中关键的trace到硬件，使用分支断言构造原子执行单位，以较小的硬件代价获得较高的加速比。在本文实验中，与采用模拟退火算法的指令级细粒度划分相比，获得的性能平均高9．6％，最终结果硬件面积小29％。     

Effect of artificial-intelligence planning-procedures on systemreliability

For an embedded real-time process-control system incorporating artificial-intelligence programs, the system reliability is determined by both the software-driven response computation time and the hardware-driven response execution time. A general model, based on the probability that the system can accomplish its mission under a time constraint without incurring failure, is proposed to estimate the software/hardware reliability of such a system. The factors which influence the proposed reliability measure are identified, and the effects of mission time, heuristics and real-time constraints on the system reliability with artificial-intelligence planning procedures are illustrated. An optimal search procedure might not always yield a higher reliability than that of a nonoptimal search procedure. Hence, design parameters and conditions under which one search procedure is preferred over another, in terms of improved software/hardware reliability, are identified     

An approach to automated hardware/software partitioning using aflexible granularity that is driven by high-level estimation techniques

Hardware/software partitioning is a key issue in the design of embedded systems when performance constraints have to be met and chip area and/or power dissipation are critical. For that reason, diverse approaches to automatic hardware/software partitioning have been proposed since the early 1990s. In all approaches so far, the granularity during partitioning is fixed, i.e., either small system parts (e.g., base blocks) or large system parts (e.g., whole functions/processes) can be swapped at once during partitioning in order to find the best hardware/software tradeoff. Since the deployment of a fixed granularity is likely to result in suboptimum solutions, we present the first approach that features a flexible granularity during hardware/software partitioning. Our approach is comprehensive in so far that the estimation techniques, our multigranularity performance estimation technique described here in detail, that control partitioning, are adapted to the flexible partitioning granularity. In addition, our multilevel objective function is described. It allows us to tradeoff various design constraints/goals (performance/hardware area) against each other. As a result, our approach is applicable to a wider range of applications than approaches with a fixed granularity. We also show that our approach is fast and that the obtained hardware/software partitions are much more efficient (in terms of hardware effort, for example) than in cases where a fixed granularity is deployed     

A Tabu Search Algorithm for Cluster Building in Wireless Sensor Networks

The main challenge in wireless sensor network deployment pertains to optimizing energy consumption when collecting data from sensor nodes. This paper proposes a new centralized clustering method for a data collection mechanism in wireless sensor networks, which is based on network energy maps and Quality-of-Service (QoS) requirements. The clustering problem is modeled as a hypergraph partitioning and its resolution is based on a tabu search heuristic. Our approach defines moves using largest size cliques in a feasibility cluster graph. Compared to other methods (CPLEX-based method, distributed method, simulated annealing-based method), the results show that our tabu search-based approach returns high-quality solutions in terms of cluster cost and execution time. As a result, this approach is suitable for handling network extensibility in a satisfactory manner.     

Affectation heuristique de cellules à des commutateurs dans les réseaux cellulaires pour mobiles

The problem of assigning of cells to switches in a cellular network is a NP-hard problem which cannot be solved in an exact way in reasonable calculating times. In this article, we propose a compromise based on the tabu search heuristics to obtain acceptable solutions with little processing effort. The method essentially consists in modifying in an iterative way an initial solution while hoping to reach a final solution which respects the constraints of the problem. The results obtained confirm the effectiveness and the robustness of the tabu search method particularly to solve problems with a certain number of cells and switches.