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.     

Partitioning and pipelining for performance-constrainedhardware/software systems

In order to satisfy cost and performance requirements, digital signal processing and telecommunication systems are generally implemented with a combination of different components, from custom-designed chips to off-the-shelf processors. These components vary in their area, performance, programmability and so on, and the system functionality is partitioned amongst the components to best utilize this tradeoff. However, for performance critical designs, it is not sufficient to only implement the critical sections as custom-designed high-performance hardware, but it is also necessary to pipeline the system at several levels of granularity. We present a design flow and an algorithm to first allocate software and hardware components, and then partition and pipeline a throughput-constrained specification amongst the selected components. This is performed to best satisfy the throughput constraint at minimal application-specific integrated-circuit cost. Our ability to incorporate partitioning with pipelining at several levels of granularity enables us to attain high throughput designs, and also distinguishes this paper from previously proposed hardware/software partitioning algorithms     

Cell planning with capacity expansion in mobile communications: atabu search approach

The cell planning problem with capacity expansion is examined in wireless communications. The problem decides the location and capacity of each new base station to cover expanded and increased traffic demand. The objective is to minimize the cost of new base stations. The coverage by the new and existing base stations is constrained to satisfy a proper portion of traffic demands. The received signal power at the base station also has to meet the receiver sensitivity. The cell planning is formulated as an integer linear programming problem and solved by a tabu search algorithm. In the tabu search intensification by add and drop move is implemented by short-term memory embodied by two tabu lists. Diversification is designed to investigate proper capacities of new base stations and to restart the tabu search from new base station locations. Computational results show that the proposed tabu search is highly effective. A 10% cost reduction is obtained by the diversification strategies. The gap from the optimal solutions is approximately 1~5% in problems that can be handled in appropriate time limits. The proposed tabu search also outperforms the parallel genetic algorithm. The cost reduction by the tabu search approaches 10~20% in problems: with 2500 traffic demand areas (TDAs) in code division multiple access (CDMA)     

The Extended Partitioning Problem: Hardware/Software Mapping, Scheduling, and Implementation-bin Selection

In system-level design, applications are represented as task graphs where tasks (called nodes) have moderate to large granularity and each node has several implementation options differing in area and execution time. We define the extended partitioning problem as the joint determination of the mapping (hardware or software), the implementation option (called implementation bin), as well as the schedule, for each node, so that the overall area allocated to nodes in hardware is minimum and a deadline constraint is met. This problem is considerably harder (and richer) than the traditional binary partitioning problem that determines just the best mapping and schedule. Both binary and extended partitioning problems are constrained optimization problems and are NP-hard.We first present an efficient(O(N ²)) heuristic, called GCLP, to solve the binary partitioning problem. The heuristic reduces the greediness associated with traditional list-scheduling algorithms by formulating a global measure, called global criticality (GC). The GC measure also permits an adaptive selection of the optimization objective at each step of the algorithm; since the optimization problem is constrained by a deadline, either area or time is optimized at a given step based on the value of GC. The selected objective is used to determine the mapping of nodes that are normal, i.e. nodes that do not exhibit affinity for a particular mapping. To account for nodes that are not normal, we define extremities and repellers. Extremities consume disproportionate amounts of resources in hardware and software. Repellers are inherently unsuitable to either hardware or software based on certain structural properties. The mapping of extremities and repellers is determined jointly by GC and their local preference.We then present an efficient ( O(N ³ + N ² B), for N nodes and B bins per node) heuristic for extended partitioning, called MIBS, that alternately uses GCLP and an implementation-bin selection procedure. The implementation-bin selection procedure chooses, for a node with already determined mapping, an implementation bin that maximizes the area-reduction gradient of as-yet unmapped nodes. Solutions generated by both heuristics are shown to be reasonably close to optimal. Extended partitioning generates considerably smaller overall hardware as compared to binary partitioning.     

Float-to-fixed and fixed-to-float hardware converters for rapid hardware/software partitioning of floating point software applications to static and dynamic fixed point coprocessors

While hardware/software partitioning has been shown to provide significant performance gains, most hardware/software partitioning approaches are limited to partitioning computational kernels utilizing integers or fixed point implementations. Software developers often initially develop an application using floating point representations built-in to most programming languages and later convert the application to a fixed point representation—a potentially time consuming process. In this paper, we present the Arizona Float ⇔ Fixed Hardware Library (AFFHL) consisting of efficient, configurable floating point to fixed point and fixed point to floating point hardware converters. By utilizing these converters, a system’s hardware/software implementation can be separated into a floating point domain consisting of the microprocessor and memory subsystem and a fixed point domain consisting of one or more partitioned hardware coprocessors. This separation enables a rapid hardware/software partitioning approach in which floating point software kernels can be implemented using fixed point hardware coprocessors without the need for application developers to first rewrite software applications as fixed point implementations. We further present an overview of a basic hardware/software partitioning methodology for rapidly partitioning computational kernels within floating point software application to either statically determined fixed point hardware coprocessors or dynamically adaptable fixed point hardware coprocessors in which the required fixed point representation can be dynamically determined and adjusted at runtime.     

共孔径主被动高光谱三维成像实时处理框架

共孔径主被动高光谱三维成像技术是一种结合激光雷达主动探测和高光谱相机被动成像的新型遥感探测手段，通过共光路设计，降低了主被动数据配准难度，使得实时融合生成三维高光谱影像成为可能。三维高光谱成像实时处理兼具数据密集和运算密集的特点，可编程片上系统软硬件协同设计为其提供了解决方案。而目前软硬件划分多基于定性经验分析设计，难以实现定量化最优设计。针对该问题，提出了一种采用基于权重法的多目标规划模型的可编程片上系统处理框架。该处理框架利用图论模型Ncut准则开展高内聚度、低耦合度的单元分割，并对各单元的软件和硬件实现特性分别进行分析评估，最终面向应用需求，利用多目标规划模型求解最优的软硬件划分方案。利用该处理框架，针对速率优先和功耗优先两种高光谱三维实时成像应用场景，进行了软硬件划分方案的定量化求解与分析，结果表明，在速率优先设计中，相对于传统的设计，处理速率提升了43.4%，而功耗降低了53.5%。     

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

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

Dynamic Routing and Wavelength Assignment Using Cost Based Heuristics in WDM Optical Networks

Dynamic routing and wavelength assignment problem in optical networks is a two-step problem that is influenced by the choice of a successful optimal path selection and wavelength assignment. Proper selection techniques reduce the number of wavelengths required in the network and thereby improves traffic grooming. Heuristic algorithms and integer linear programming models help in selection of route and wavelength separately. Hence, the computation time is large which makes the system slow. A cost function is computed which uses independent parameters in the network for the selection of route and wavelength for a call. The heuristic reduces computation time by combining the search of route and wavelength to be assigned. In addition, the network performance is analyzed with and without alternate routing along with proposed heuristics. The selection of proper route and wavelength finding technique is very essential since it improves the grooming factor of the network thereby allowing more traffic support by the network. Our objective is to investigate and propose a cost based heuristics for dynamic traffic routing and wavelength Assignment in WDM optical networks. For this we plan to develop cost functions and heuristics to compute the route and wavelength assignment strategy. Here, our objective is to reduce the computation time for selection of route and wavelength assignment strategy by weighted cost function. The function has to include network parameters for its processing. Our work provides an overview about DRWA by applying cost based heuristics in WDM networks. This paper explains the proposed cost function and its applications in line with selection of independent parameters. The details of other functions like cost function formulation, hop-based route assignment, available wavelength based route assignment, mathematical analysis of proposed cost function are also explained. Results and discussions based on the findings are presented.

     

改进多路软硬件划分算法的筛选法

文章提出筛选法对基于抽象体系结构模板的多路软硬件划分算法进行了改进,从而使整个软硬件划分-任务调度过程的时间大大缩短。该方法在原算法的软硬件划分和任务调度过程之间加入了一个筛选步骤,对软硬件划分结果的硬件面积进行预估,依据预估的结果进行筛选,筛选后满足要求的划分方案才进行调度,从而大大减少了调度过程的工作量。实验结果表明,加入筛选步骤后,在最终结果性能基本不损失的前提下,整个软硬件划分-任务调度过程的速度有明显提高。     

Avalanche: an environment for design space exploration and optimization of low-power embedded systems

We present Avalanche, a prototyping framework that addresses the issues of power estimation and optimization for mixed hardware and software embedded systems. Avalanche is based on a generic embedded system architecture consisting of embedded CPU, custom hardware, and a memory hierarchy. For system-level power estimation, given various system parameters like cache sizes, cache policies, and bus width, etc., Avalanche is able to rapidly evaluate/estimate power and performance and thus facilitate comprehensive design space explorations. For system-level power optimization, Avalanche offers different modes reflecting various design scenarios: if no hardware/software partitioning or only partial partitioning has been conducted, Avalanche guides the designer in finding power-aware hardware/software partitioning; when a system has already been partitioned, Avalanche can optimize system parameters such as cache and memory size; if system parameters and partitioning are given, Avalanche applies additional optimizations for power including source-to-source compiler transformations. Avalanche has been deployed during the design phase of real-world applications including an MPEG II encoder in a set-top box design. Extensive design space explorations in terms of power and performance could be conducted within several hours and various optimization techniques led to power reductions of up to 94% without performance losses and only a slight increases in total chip size (i.e., transistor count).