改进量子多目标进化算法用于SOC软硬件划分*

采用量子多目标进化算法对从任务级进行抽象建模所得到的系统模型进行软硬件划分,并针对SOC系统设计中存在的特点,对量子多目标进化算法进行改进。采用量子个体编码方案,避免个体编/解码的冗余。并将Pareto最优概念与多目标优化相结合,从而实现了兼顾系统面积、功耗、时间等参数的软硬件划分方法。仿真对比实验结果表明,该算法一次运行可以获得多个Pareto最优解,为各个目标函数之间权衡分析提供了有效的工具,提高了设计效率。在满足系统性能要求下,可为复杂SOC系统提供多个设计目标的全局优化方案。     

具有初始信息素的蚂蚁寻优软硬件划分算法

面向基于平台的系统芯片设计,提出具有初始信息素的蚂蚁寻优软硬件划分算法AOwIP．基本思想是：①利用基于平台的设计方法中已有参考设计的软硬件划分结果作为初始划分解,进行适当变换后生成初始信息素分布．②在所生成初始信息素分布的基础上,利用蚂蚁算法正反馈、高效收敛的优势寻求最优划分解．该算法利用基于平台的设计方法强调系统重用的优势,克服蚂蚁算法在求解软硬件划分问题时缺乏初始信息素的不足．实验表明,AOwIP算法有效提高了蚂蚁算法的最优解搜索效率．     

基于量子粒子群算法的可重构系统软硬件划分

针对软硬件协同设计中软硬件划分的这个关键问题,提出了一种基于量子粒子群算法的动态可重构系统软硬件划分的算法;首先使用有向无环图对嵌入式系统建模,得到软硬件划分优化系统的目标函数;然后通过采用自适应的量子旋转角调整策略以及引入量子变异操作,有效避免搜索过程陷入局部最优,提高搜索效率;对比实验结果表明本文算法对解决软硬件划分问题的有效性;文章算法不但能够以更快的搜索速度得到软硬件划分结果,并且得到划分结果更优,是一种具有较高性能的划分方法.     

SOC软硬件划分系统中的关键算法

设计并实现了SOC软硬件划分系统,搭建了软硬件协同设计的平台并描述了软硬件协同设计的流程。运用多目标遗传算法对目标系统的价格、功耗、速度进行优化,采用了基于Pareto支配的适应值赋值、精英保持和密度计算截断操作的方法进行多目标寻优。针对单任务图描述多CPU系统结构的不足,提出采用多任务图来描述的方法,并提出了MTLS性能评估算法,验证系统软硬件划分的优劣。在对比实验中将NSGA2算法运用到本系统中,结果证明论文的多目标寻优算法获得的非支配解80%比NSGA2的非支配解优。     

一种基于DQCGA算法的软硬件动态划分方法

软硬件划分是嵌入式系统设计的高层抽象环节中最重要的关键步骤之一.在某些数据相关的应用领域中,划分环境是动态变化的,因此我们提出了一种解决动态软硬件划分的方法.这种方法基于一种名为DQCGA的演化算法.DQCGA算法受自然界中对称和互补机制的启发,操纵一对互补的概率向量来适应动态变化的环境.我们系统地完成了建模,动态环境定义等环节,然后通过和已有方法的比较,有针对性地设计了实验.试验结果很好地证明了该方法对于解决软硬件划分问题的可行性和有效性,并且较之以往的方法有着更好的表现.     

一种基于SoC平台设计的AVS解码器软硬件分区结构

视频解码芯片的结构因硬件强大的处理能力和软件灵活的可编程功能从硬件转向软硬件分区结构。该文针对AVS标准的算法和解码实现复杂程度,根据软硬件协同设计思想提出了一种结构划分合理的AVS高清视频解码器软硬件分区结构。根据AVS算法的特点该结构将宏块层以上部分的元素解析划归到软件解码中,将宏块层解码划为硬件处理。经验证,该结构设计可实现AVS高清码流解码,并在C语言编写的硬件平台仿真程序中得以实现。     

一种有效的面向多目标软硬件划分的遗传算法

软硬件划分是软硬件协同设计的关键技术之一,划分结果对最终的设计方案有非常重要的影响。软硬件划分根据优化目标的数量,可分为单目标划分和多目标划分。多目标划分问题是一个NP-hard问题,一般不存在传统意义上的“最优解”,而是存在一组互不支配的Pareto最优解。遗传算法因其具有并行、群体搜索的特点而非常适于求解多目标优化问题。通过抽象描述将一个实际SOC设计问题转化为多目标软硬件划分问题,采用遗传算法便可获得最优设计方案。为克服过早收敛及加快搜索速度,改进了适应度函数的定义,通过自适应参数调整,加入惩罚函数的适应度定义,提高了进化速度,从而有效地获得了Pareto最优解集。在实际问题的应用中,多目标软硬件划分遗传算法是能有效求取平衡系统成本、硬件面积、功耗和时间特性的最优化方案。     

基于组合算法的嵌入式系统软硬件划分方法

嵌入式系统软硬件划分是一个多约束条件、多目标的组合优化问题,单一算法难以找到最优设计方案,为此,提出一种遗传算法和粒子群算法组合的嵌入式系统软硬件划分方法。首先建立嵌入式系统软硬件划分问题的数学模型,然后利用遗传算法找到问题的可行解,最后采用粒子群算法找到最优方案,并采用仿真实验测试算法的性能。仿真结果表明,该方法提高了嵌入式系统软硬件划分问题的求解效率,可以快速找到更优的软硬件划分方案。     

一种嵌入式系统软硬件划分算法

软硬件划分是嵌入式系统软硬件协同设计中的一个关键问题.传统划分算法具有局部最优,收敛速度慢的缺陷.为使组成系统性能达到最优化,提出一种新的嵌入式系统软硬件划分算法.先采用嵌入式系统转化成有向无环图,可将嵌入式系统软硬件划分问题转换成一个多条件约束问题,用蚂蚁放置于有向无环图顶点上,对系统软硬件的划分准确率作为蚁群算法优化目标,通过蚁群算法搜索最优目标函数值,有效避免传统划分算法搜索陷入局部最小,大幅度降低搜索时间.实验结果表明,采用蚁群算法能够高效、快速获得准确地划分结果,为嵌入式系统设计提供了依据.     

基于多代理系统的软硬件协同设计

为使软硬件协同设计过程更具分布性、自主性及并行性,在软硬件协同设计中引入多代理(MAS)技术,提出软硬件协同设计的MAS模型,包括系统描述Agent、软硬件划分及映射Agent、软硬件设计Agent、协同通信Agent、性能评估Agent和硬件系统测试Agent的构建和应用。采用多个目标代理映射、协商的方法协调整个协同设计过程。实际应用表明,该方法能优化系统级芯片设计方案、软硬件结构和功能,并提高系统整体性能。     

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

软硬件划分是嵌入式系统协同设计中的关键问题,已经被证明是一个NP问题。模拟退火算法是解决该问题常用的启发式算法,但是其存在收敛速度过慢的问题。通过改进算法的扰动模型和退火进度,提出一种新的代价函数计算方法来提高它的收敛速度。实验结果表明,相对于基于经典的模拟退火算法和已有改进的算法,新算法运行时间大大减少,并且增大了找到近似最优解的概率。     

Hardware-software co-synthesis of hard real-time systems with reconfigurable FPGAs

Real-time systems cover a wide application domain. This paper presents an efficient heuristic algorithm for enforcing the schedulability of aperiodic hard real-time tasks arriving simultaneously with precedence constraints and individual deadlines. The proposed co-synthesis algorithm integrates partitioning and non-preemptive scheduling. Reconfigurable FPGAs are incrementally added when schedulability suffers in a uniprocessor system. Initially, a schedule that minimizes the maximum lateness and satisfies the precedence constraints is made. If individual timing constraints are not met in this schedule, some tasks are selected and transferred to dynamically reconfigured FPGAs. The proposed algorithm was implemented and tested with a large number of task graphs with task size as high as 700 nodes. The algorithm could not only achieve schedulability but also could reduce the total completion time of the task graph. Moreover, incremental addition of reconfigurable FPGAs yielded a cost effective solution.     

A hardware/software partitioning algorithm based on artificial immune principles

Hardware/software codesign is the main approach to designing the embedded systems. One of the primary steps of the hardware/software codesign is the hardware/software partitioning. A good partitioning scheme is a tradeoff of some constraints, such as power, size, performance, and so on. Inspired by both negative selection model and evolutionary mechanism of the biological immune system, an evolutionary negative selection algorithm for hardware/software partitioning, namely ENSA-HSP, is proposed in this paper. This ENSA-HSP algorithm is proved to be convergent, and its ability to escape from the local optimum is also analyzed. The experimental results demonstrate that ENSA-HSP is more efficient than traditional evolutionary algorithm.     

基于NSGA-II的嵌入式系统软硬件划分方法

软硬件划分是软硬件协同设计中的一个关键问题。针对单处理器嵌入式系统,提出将NSGA-II应用于软硬件划分中,该算法一次运行可以获得多个Pareto最优解,为各个目标函数之间权衡分析提供了有效的工具,提高了设计效率。结果表明,通过该划分方法,在满足系统性能要求下,可为复杂嵌入式系统提供多个设计目标的全局优化方案。     

Hierarchical discrete-event simulation on hypercube architectures

The simulation of systems that include components at varying levels of abstraction is addressed. A performance model of a hierarchical discrete-event simulation algorithm running on a hypercube architecture is presented. The model allows the performance impact of decisions made in the design of the parallel processor as well as in the design of the simulation algorithm to be examined. Three static component partitioning strategies are considered: random partitioning, heuristic partitioning, and simulated annealing. The performance model is applied to digital system simulation     

一种基于层次平台SoC设计中的软硬件划分方法

软硬件划分是SoC设计中的一个关键问题，合理的划分结果对最终生成的芯片在成本、性能、可扩展性等方面有重要影响。提出了在基于层次平台的SoC设计中，采用遗传算法进行软硬件划分的方法，并通过实验验证了其在SoC设计中的可行性。     

On delay adjustment for dynamic load balancing in distributed virtual environments

Distributed virtual environments (DVEs) are becoming very popular in recent years, due to the rapid growing of applications, such as massive multiplayer online games (MMOGs). As the number of concurrent users increases, scalability becomes one of the major challenges in designing an interactive DVE system. One solution to address this scalability problem is to adopt a multi-server architecture. While some methods focus on the quality of partitioning the load among the servers, others focus on the efficiency of the partitioning process itself. However, all these methods neglect the effect of network delay among the servers on the accuracy of the load balancing solutions. As we show in this paper, the change in the load of the servers due to network delay would affect the performance of the load balancing algorithm. In this work, we conduct a formal analysis of this problem and discuss two efficient delay adjustment schemes to address the problem. Our experimental results show that our proposed schemes can significantly improve the performance of the load balancing algorithm with neglectable computation overhead.     

基于主动消息与LogP模型的并行程序设计

主动消息将通信和计算集成为一体，是一种相当有效和高适应性的通信体系结构。ＬｏｇＰ模型是一种面向实际的并行算法设计模型?较好地反映了当前ＭＰＰ的关键性能参数。本文讨论了它的特点，在此基础上着重分析了它在并行程序设计上的互补性。     

Matrix partitioning on a virtual shared memory parallel machine

The general problem considered in the paper is partitioning of a matrix operation between processors of a parallel system in an optimum load-balanced way without potential memory contention. The considered parallel system is defined by several features the main of which is availability of a virtual shared memory divided into segments. If partitioning of a matrix operation causes parallel access to the same memory segment with writing data to the segment by at least one processor, then contention between processors arises which implies performance degradation. To eliminate such situation, a restriction is imposed on a class of possible partitionings, so that no two processors would write data to the same segment. On the resulting class of contention-free partitionings, a load-balanced optimum partitioning is defined as satisfying independent minimax criteria. The main result of the paper is an algorithm for finding the optimum partitioning by means of analytical solution of respective minimax problems. The paper also discusses implementation and performance issues related to the algorithm, on the basis of experience at Kendall Square Research Corporation, where the partitioning algorithm was used for creating high-performance parallel matrix libraries