首页 | 官方网站   微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 265 毫秒
1.
基于抽象体系结构模板的多路软硬件划分算法   总被引:3,自引:0,他引:3  
随着系统芯片技术在嵌入式系统中的应用,软硬件划分从传统的二划分问题转化为多划分问题.文中对此提出了一个由通信通道连接的处理单元网络的抽象模型来描述多处理模块结构,并利用模拟退火算法与启发式的调度算法分别完成多路软硬件划分与系统性能和代价的估算.初步的实验结果表明,该算法能有效地选择合适的体系结构,使系统的性能和代价得到优化.  相似文献   

2.
嵌入式系统的软硬件划分   总被引:2,自引:0,他引:2  
嵌入式系统软硬件协同设计中的关键步骤之一是软硬件划分。现有的许多软硬件划分方法都试图捕获太多有关划分问题和目标结构的细节,可扩展性差。本文提出了一种简化的软硬件划分问题模型,这种简化模型能分别对不同的划分问题进行形式化定义。在此模型的基础上,本文给出了基于ILP的算法和遗传算法。实验结果表明,我们的遗传算法能有效地解决千万个节点规模的划分问题,并获得近似最优解。  相似文献   

3.
嵌入式系统在资源争用条件下的软硬件划分   总被引:1,自引:1,他引:1  
以一种具有时间约束的数据流图DFG的可调度性分析为基础,提出一种软硬件划分算法.该算法将由共享资源争用引起的性能影响考虑在内,使得软硬件划分能依据更为精确的性能分析结果,由此将缩小软硬件划分中性能估计同实际运行状况之间的差异,提高划分的合理性,也使得目标系统的性能获得更可靠的保证.  相似文献   

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

5.
针对SOC软硬件协同设计中的软硬件划分问题,首先构建了软硬件划分的系统模型,讨论了影响SOC性能的价格、执行时间、功耗、面积等因素及其相互关系。在此基础上,提出了一个旨在实现最优性价比的目标函数,并结合软硬件划分问题自身的特点对传统遗传算法的遗传操作进行了改进,在Matlab中进行了软硬件划分方法的仿真,仿真实验获得的结果有力地证明了算法的稳定性和有效性。同时,该算法在MPEG-2视频解码芯片设计中得到了实际应用,芯片设计的结果良好地反映了设计目标,证明了算法的实用性。  相似文献   

6.
软硬件协同设计作为嵌入式系统开发的重要技术,随着嵌入式系统的广泛应用变得越来越重要。软硬件划分是软硬件协同设计的关键环节,是经典的组合优化问题,已被证明是NP完全问题。对于一个给定的任务而言,由于在硬件实现中存在并行执行的潜力,具有不同面积的硬件可以提供不同的执行速度。这样,一个任务根据可利用的硬件面积可以有多种硬件实现方式。现有的软硬件划分方法通常仅仅考虑单一的硬件实现方式,却忽略了多种选择的硬件实现方式。对于多选择的软硬件划分问题,分别使用模拟退火算法和遗传算法,提出了可行性的解决方案。并与禁忌搜索算法进行比较,寻找多选择软硬件划分问题的相对较好的启发式算法。实验结果表明,在求得的解的质量方面,禁忌搜索算法相比于其他两种算法而言是最好的;在获得较好解的速度方面,模拟退火算法和遗传算法要比禁忌搜索算法快得多。  相似文献   

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

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

9.
张良  徐成  田峥  李涛 《计算机应用》2013,33(7):1898-1902
软硬件划分是嵌入式系统设计过程中一个关键环节,已经被证明是一个NP问题。针对目前算法在进行大任务集下的软硬件划分时计算复杂度高、不能快速收敛,且找到的全局最优解的质量不佳等问题,提出一种基于贪心算法和模拟退火算法相融合的软硬件划分方法。首先将软硬件划分问题规约为变异的0-1背包问题,在求解背包问题的算法基础上用贪心算法构造出初始划分解;然后,对代价函数的解空间进行合理的区域划分,并基于划分的区间设计新的代价函数,采用改进的模拟退火算法对初始划分进行全局寻优。实验结果表明,与目前已有的类似改进算法相比,新算法在任务划分质量和算法运行时间两个方面的提升率最大可达到8%和17%左右,具有高效性和实用性。  相似文献   

10.
嵌入式系统软硬件划分方法探索   总被引:1,自引:0,他引:1  
袁爱平  傅明 《计算机应用》2008,28(9):2427-2429
提出了克隆选择算法在软硬件划分中的应用,讨论了目标函数、系统约束、抗体编码、克隆选择和变异等问题的处理。实验结果表明该算法具有较快的收敛速度,并获得了近似最优解。  相似文献   

11.
Analysis of a Heuristic for Code Partitioning   总被引:1,自引:0,他引:1  
In this paper, we analyze the time complexity and performance of a heuristic for code partitioning for Distributed Memory Multiprocessors (DMMs). The partitioning method is data-flow based where all levels of parallelism are exploited. Given a weighted Directed Acyclic Graph (DAG) representation of the program, our algorithm automatically determines the granularity of parallelism by partitioning the graph into tasks to be scheduled on the DMM. The granularity of parallelism depends only on the program to be executed and on the target machine parameters. The output of our algorithm is passed on as input to the scheduling phase. Finding an optimal solution to this problem is NP-complete. Due to the high cost of graph algorithms, it is nearly impossible to come up with close to optimal solutions that do not have very high cost (higher order polynomial). Our proposed heuristic gives good performance and has relatively low cost.  相似文献   

12.
对三种典型分布式任务分配算法的分析   总被引:2,自引:0,他引:2  
本文先分析了基于图论的分配算法,整数规划方法和试探法等几种典型的分布式任务分配算法的基本思想、特点,不足和算法复杂度,以及可进一步改进之处,然后给出了一种试探法的改进算法,并简单讨论了其特点和性能,最后指出了分布式任务分配的发展方向。  相似文献   

13.
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.  相似文献   

14.
This paper presents a study of graph partitioning schemes for parallel graph community detection on distributed memory machines. We investigate the relationship between graph structure and parallel clustering effectiveness, and develop a heuristic partitioning algorithm suitable for modularity-based algorithms. We demonstrate the accuracy and scalability of our approach using several real-world large graph datasets compared with state-of-the-art parallel algorithms on the Cray XK7 supercomputer at Oak Ridge National Laboratory. Given the ubiquitous graph model, we expect this high-performance solution will help lead to new insights in numerous fields.  相似文献   

15.
On parallelizing the multiprocessor scheduling problem   总被引:1,自引:0,他引:1  
Existing heuristics for scheduling a node and edge weighted directed task graph to multiple processors can produce satisfactory solutions but incur high time complexities, which tend to exacerbate in more realistic environments with relaxed assumptions. Consequently, these heuristics do not scale well and cannot handle problems of moderate sizes. A natural approach to reducing complexity, while aiming for a similar or potentially better solution, is to parallelize the scheduling algorithm. This can be done by partitioning the task graphs and concurrently generating partial schedules for the partitioned parts, which are then concatenated to obtain the final schedule. The problem, however, is nontrivial as there exists dependencies among the nodes of a task graph which must be preserved for generating a valid schedule. Moreover, the time clock for scheduling is global for all the processors (that are executing the parallel scheduling algorithm), making the inherent parallelism invisible. In this paper, we introduce a parallel algorithm that is guided by a systematic partitioning of the task graph to perform scheduling using multiple processors. The algorithm schedules both the tasks and messages, and is suitable for graphs with arbitrary computation and communication costs, and is applicable to systems with arbitrary network topologies using homogeneous or heterogeneous processors. We have implemented the algorithm on the Intel Paragon and compared it with three closely related algorithms. The experimental results indicate that our algorithm yields higher quality solutions while using an order of magnitude smaller scheduling times. The algorithm also exhibits an interesting trade-off between the solution quality and speedup while scaling well with the problem size  相似文献   

16.
Software project scheduling problem (SPSP) is one of the important and challenging problems faced by the software project managers in the highly competitive software industry. As the problem is becoming an NP-hard problem with the increasing numbers of employees and tasks, only a few algorithms exist and the performance is still not satisfying. To design an effective algorithm for SPSP, this paper proposes an ant colony optimization (ACO) approach which is called ACS-SPSP algorithm. Since a task in software projects involves several employees, in this paper, by splitting tasks and distributing dedications of employees to task nodes we get the construction graph for ACO. Six domain-based heuristics are designed to consider the factors of task efforts, allocated dedications of employees and task importance. Among these heuristic strategies, the heuristic of allocated dedications of employees to other tasks performs well. ACS-SPSP is compared with a genetic algorithm to solve the SPSP on 30 random instances. Experimental results show that the proposed algorithm is promising and can obtain higher hit rates with more accuracy compared to the previous genetic algorithm solution.  相似文献   

17.
This paper considers a location system where a number of deployed sensor nodes collaborate with objects that need to be localized. Unlike existing works, we focus on reducing the energy consumption of the sensor nodes, which are assumed to be static and run on limited battery power. To minimize the total wake-up time of the sensor nodes, we control the transmission schedule of each object. Because it is difficult to find an optimal solution to the considered optimization problem, we consider an approach to this problem that consists of two steps: (1) create an equivalent modified graph coloring subproblem, and (2) permute the coloring result to obtain a best possible solution. We adopt some existing graph coloring algorithms for step 1 and find two properties of optimal schedules that can be used to confine the search space for step 2. Additionally, we propose a heuristic algorithm that aims at significantly reducing the complexity for the case where the confined search space is still too large. The performance of our heuristic algorithm is evaluated through extensive simulations. It is shown that its performance is comparable to that of the simulated annealing algorithm, which gives a near-optimal solution.  相似文献   

18.
提出一种概率构造算法与遗传算法融合的算法,通过引入表示划分结果多样性的度量方法,利用概率构造算法产生具有多样性的较优的初始群体,并在此基础上利用遗传算法寻求最优解.实验结果表明,该算法能够获得比已有的基于列表的划分算法更优的划分结果,比采用完全随机初始群体的遗传算法缩短了运行时间.  相似文献   

19.
This paper shows that the uniform k-way partitioning problem can be transformed into the max-cut problem using a graph modification technique. An iterative algorith, based on Kernighan-Lin's (KL) method, for partitioning graphs is presented that exploits the problem equivalence property. The algorithm deals with nodes of various sizes without any performance degradation. The computing time per pass of the algorithm is O(itkN2), where N is the number of nodes in the given graph. In practice, only a small number of passes are typically needed, leading to a fast approximation algorithm for k-way partitioning. Experimental results show that the proposed algorithm outperforms the KL algorithm in the quality of solutions. The performance gap between the proposed and KL algorithms becomes much bigger as the amount of size differences between nodes increases.  相似文献   

20.
This paper proposes a scheduling algorithm to solve the problem of task scheduling in a cloud computing system with time‐varying communication conditions. This algorithm converts the scheduling problem with communication changes into a directed acyclic graph (DAG) scheduling problem for existing fuzzy communication task nodes, that is, the scheduling problem for a communication‐change DAG (CC‐DAG). The CC‐DAG contains both computation task nodes and communication task nodes. First, this paper proposes a weighted time‐series network bandwidth model to solve the indefinite processing time (cost) problem for a fuzzy communication task node. This model can accurately predict the processing time of a fuzzy communication task node. Second, to address the scheduling order problem for the computation task nodes, a dynamic pre‐scheduling search strategy (DPSS) is proposed. This strategy computes the essential paths for the pre‐scheduling of the computation task nodes based on the actual computation costs (times) of the computation task nodes and the predicted processing costs (times) of the fuzzy communication task nodes during the scheduling process. The computation task node with the longest essential path is scheduled first because its completion time directly influences the completion time of the task graph. Finally, we demonstrate the proposed algorithm via simulation experiments. The experimental results show that the proposed DPSS produced remarkable performance improvement rate on the total execution time that ranges between 11.5% and 21.2%. In view of the experimental results, the proposed algorithm provides better quality scheduling solution that is suitable for scientific application task execution in the cloud computing environment than HEFT, PEFT, and CEFT algorithms.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司    京ICP备09084417号-23

京公网安备 11010802026262号