一种基于改进模拟退火算法的软硬件划分技术

提出一种应用于嵌入式系统软硬件划分的改进模拟退火算法.算法通过使用基于Cauchy分布的扰动模型和Tsallis接收准则来提高模拟退火算法的性能.通过对比经典的模拟退火软硬件划分技术以及实验结果的验证表明,使用改进模拟退火算法能加快划分的收敛,并且找到目标函数的最优值的概率也更大.     

基于扩展背包问题的的软硬件划分算法

软硬件划分问题常以时间为约束对硬件面积进行优化。随着嵌入式的发展，功耗这一因素也越来越重要，故在约束条件中加入了功耗的约束。贪婪算法是解决0-1背包问题的一种简单有效的方法，因此建立多约束的软硬件划分问题与0-1背包问题之间的联系，采用扩展的贪婪算法解决多性能指标的软硬件划分问题。利用仿真与动态规划方法的对比，进行了有效性验证。     

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

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

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

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

Extending the Kernighan/Lin Heuristic for Hardware and Software Functional Partitioning

The Kernighan/Lin graph partitioning heuristic, also known as min-cut or group migration, has been extended over several decades very successfully for circuit partitioning. Those extensions customized the heuristic and its associated data structure to rapidly compute the minimum-cut metric central to circuit partitioning; as such, those extensions are not directly applicable to other problems. In this paper, we extend the heuristic for functional partitioning, which in turn can solve the much investigated codesign problem of partitioning a system's coarse-grained functions among hardware and software components. The key extension customizes the heuristic and data structure to rapidly compute execution-time and communication metrics, crucial to hardware and software partitioning, and leads to near-linear time-complexity and excellent resulting quality. Another extension uses a new criteria for terminating the heuristic, eliminating time-consuming and unnecessary fine-tuning of a partition. Our experiments demonstrate extremely fast execution times (just a few seconds) with results matched only by the slower simulated annealing heuristic, meaning that the extended Kernighan/Lin heuristic will likely prove hard to beat for hardware and software functional partitioning.     

Functional Validation of Mixed Hardware/Software Systems based on Specification, Partitioning, and Simulation of Test Cases

Tecs is a test case development methodology for the functional validation of large electronic systems, typically consisting of several custom hardware and software components. The methodology determines a hierarchical top-down test case development process including test case specification, validation, partitioning and implementation. The test case development process addresses the functional validation of the system and its components such as ASICs, boards, HW and software modules; it does not facilitate timing or performance verification. The system functions are used to define test cases at the system level and to derive sub-functions for the system components. Test cases are specified, using a special purpose formalism, and validated before they are applied to the system under test. Furthermore, we propose a technique to partition test cases corresponding to the partitioning of the system into sub-systems and components. This technique can significantly reduce system simulation time because it allows the full validation of system functions by simulation at the sub-system and component level. The system model need only be simulated with a reduced set of stimuli to validate the interfaces between sub-systems. We present a test case specification language and tools that support the proposed methodology. The validation of a switching function illustrates methodology, language, and tools.     

System Level Hardware/Software Partitioning Based on Simulated Annealing and Tabu Search

This paper presents two heuristics for automatic hardware/software partitioning of system level specifications. Partitioning is performed at the granularity of blocks, loops, subprograms, and processes with the objective of performance optimization with a limited hardware and software cost. We define the metric values for partitioning and develop a cost function that guides partitioning towards the desired objective. We consider minimization of communication cost and improvement of the overall parallelism as essential criteria during partitioning. Two heuristics for hardware/software partitioning, formulated as a graph partitioning problem, are presented: one based on simulated annealing and the other on tabu search. Results of extensive experiments, including real-life examples, show the clear superiority of the tabu search based algorithm.     

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.     

基于改进的NSGA遗传算法的SOC软硬件划分方法

在遗传算法中引入精英保持策略构造非支配集和生成新群体,并用排除法构造非支配集,本文得到了一种改进的非支配集分类遗传算法,该算法具有全局收敛特性,并简化了计算复杂性.本文将此算法应用于SOC设计的软硬件划分.针对SOC系统设计中存在多个IP核的特点,采用整数向量的个体编码方案,避免了个体编码解码的冗余.本文给出了仿真实验结果,验证了该划分方法的有效性.     

高效关键路径粒子群的软硬件划分算法

软硬件划分是在满足系统约束条件下,将系统中部分功能模块由硬件实现,部分功能模块由软件实现,使系统整体性能达到最优.本文采用有向无环图对划分问题建模,提出采用关键路径调度、自适应性的高效粒子群软硬件划分算法.实验结果表明,采用本文算法,所得结果明显优于采用先来先服务的调度方法.     

改进混洗蛙跳算法的软硬件划分方法研究

本文将混洗蛙跳算法应用于软硬件划分,提出一种新型的软硬件划分方法。针对混洗蛙跳算法应用于离散型问题时普遍存在的种群更新过慢、算法寻优方向盲目等问题,本文采用随机步长来改进青蛙种群的迁移行为,采用子种群内进化与全局混洗进化相结合的策略改进盲目全局寻优的情况,并根据无效迭代次数来提前终止迭代以提高算法效率。在划分实验中,改进后的算法的平均最优解比原始算法减小了17.4%～73.3%,平均硬件面积比原始算法大对不同结点数的随机DAG图4.32%～5.81%,平均仿真执行时间只有原算法的42.7%～64.0%。改进后算法在寻优能力和收敛速度上均优于原始算法,可更高效地完成软硬件划分任务。      

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.     

A Compositional Framework for Hardware/Software Co-Design

We describe a compositional framework, together with its supporting toolset, for hardware/software co-design. Our framework is an integration of a formal approach within a traditional design flow. The formal approach is based on Interval Temporal Logic and its executable subset, Tempura. Refinement is the key element in our framework because it will derivefrom a single formal specification of the system the software and hardware parts of the implementation, while preserving all properties of the system specification. During refinement simulation is used to choose the appropriate refinement rules, which are applied automatically in the HOL system. The framework is illustrated with two case studies. The work presented is part of a UK collaborative research project between the Software Technology Research Laboratory at the De Montfort University and the Oxford University Computing Laboratory.     

System C:一种软/硬件协同设计语言

集成电路制造技术的迅速发展,已经可以把一个完整的电子系统集成到一个芯片上,即所谓的系统芯片（SOC：System on Chip)。在系统芯片中一般包含有嵌入式微处理器（或信号处理器）,总线,存储器,输入／输出口,专用集成电路（ASCC）等硬件,还包含有控制微处理器（或信号处理器）工作的软件。传统的设计方法是将硬件和软件分开来设计的,在硬件设计完成并生产出样片后才能调试软件。本文在介绍了传统设计方法后,指出了这种设计方法存在缺陷,介绍了目前国外在硬／软件协同设计方面正在进行的各种研究工作。本文最后着重介绍了一种软／硬件协同设计语言System C,利用SystemC可望解决系统芯片设计中软／硬件协同设计的问题。     

一种基于SystemC的软硬件协同设计方法

随着集成电路工艺的飞速发展,传统的设计方法已不能满足设计高集成度的复杂数字系统的要求。软硬件协同设计成为嵌入式系统设计的新方法。SystemC是一种兼容C++的系统建模语言,它同时支持RTL级、行为级和系统级描述,使其成为软硬件协同设计平台的基础。     

A Hardware/Software Co-Design of MP3 Audio Decoder

The Moving Picture Experts Group (MPEG) audio coding standard offers three levels of compression algorithms where the MPEG Layer III (MP3) has the best quality but with the most complexity. There are several complex coding techniques involved in MP3 audio decoding algorithm, therefore, it is difficult to make an efficient architecture design. This paper presents a hardware/software co-design method for the implementation of MP3 audio decoder, which meets the real-time requirement of MP3 standard. The software and hardware part of this decoder is partitioned into a pre-processing and a post-processing unit respectively. The pre-processing unit with a programmable parser processor is developed for the implementation of intensive decision making operations needed for audio bitstreams. The post-processing unit with a dedicated hardware of modified fast algorithm is designed for the regular and computation-intensive operations in MP3 audio decoding flow. The architecture achieves a high throughput with a reduced memory requirement and hardware complexity. With a two-level pipeline approach, it allows a high hardware utilization and is suitable to low power implementation. The proposed decoder system has been designed and implemented using VLSI cell-based approach. The die size is 3.5 × 4.45 mm² with the maximum operation frequency of 20 MHz.Tsung-Han Tsai was born in Chunghua, Taiwan, R.O.C. He received the B.S., M.S., and Ph.D. degrees in electrical engineering from National Taiwan University, Taipei, Taiwan, in 1990, 1994, and 1998 respectively. Dr. Tsai was an Instructor (1994–1998) and an Associate Professor (1998–1999) of the department of electrical engineering at Hwa Hsia College of Technology and Commerce. From 1999 to 2000, he was an Associate Professor of electronic engineering at Fu Jen University. Currently, he is an Assistant Professor in the department of electrical engineering at National Central University. He is also a member of IEEE and Audio Engineering Society (AES). Dr. Tsai has been awarded 8 patents and more than 70 refereed papers published in international journals and conferences. His research interests include VLSI signal processing, video/audio coding algorithms, DSP architecture design, wireless communication and System-On-Chip design.Ya-Chau Yang was born in Tainan, ROC in 1976. He received the B.S. and M.S. degrees both in electrical engineering from Fu-Jen University in 1999 and 2001, respectively. In 2002, he was as software engineer of Foundry Access in Cadence Design Systems. Currently he is a design engineer at ActVision Technology Inc, where he works on MPEG audio decoder IP design. His interests include MPEG audio coding algorithms, VLSI signal processing/architecture and computer architecture.Chun-Nan Liu was born in Taichung, Taiwan, R.O.C., in 1978. He received the B.S. degrees in electrical engineering from National Central University, Taiwan, in 2000. He is currently pursuing the Ph.D. degree from the Department of Electrical Engineering, National Central University, Taiwan. His area of interests are audio signal processing and VLSI signal processing.     

基于改进的遗传算法软硬件划分方法研究

随着芯片集成度的飞速发展,集成电路的设计已经进入了片上系统（Soc,Systemonchip）的时代。传统的软硬件分开设计的方法已经不在适合Soc设计的需要,而软硬件协同设计技术很好解决了传统设计方法所不能解决的问题。软硬件划分方法是软硬件协同设计中的一个关键问题,从基于多目标的遗传算法出发,主要做了两方面的改进：一方面引入小生境技术,进一步优化了算法;另一方面是引入精英保持策略,保证了算法的收敛性。     

Hardware/Software co-design with the HMS framework

Hardware/Software co-design is an increasingly common design style for integrated circuits. It allows the majority of a system to designed quickly with standardized parts, while special purpose hardware is used for the time critical portions of the system. The framework considered in this paper performs Hardware/Multi-Software (HMS) co-design for iterative loops, given an input specification that includes the system to be built, the number of available processors, the total chip area, and the required response time. Originally, all operations are done in software. The system then substitutes hardware (adder, multiplier, bus) for software based on theneedability of each type of hardware unit. After a new hardware unit is introduced the system is rescheduled using a variation of rotation scheduling in which operations may be moved between processors. Experimental results are shown that illustrate the efficiency of the algorithms as well as the savings achieved.