共查询到20条相似文献,搜索用时 9 毫秒
1.
相关任务图的均衡动态关键路径调度算法 总被引:9,自引:2,他引:9
表调度(list scheduling)法是解决任务调度问题的较为有效的方法,该文对两个典型的表调度算法-MCP算法和ETF算法进行了分析,发现它们均存在着一定的不足,文中提出了一个更好的表调度算法BDCP,它采用动态关键路径技术并均衡考虑关键路径结点和非关键路径结点,使得对相关任务图调度长度影响最大的就绪结点能够被优先调度,从而极大地缩短了任务图的调度长度,分析和实验结果表明,BDCP算法要优于MCP和ETF算法。 相似文献
2.
3.
4.
近年来,图数据模型被广泛地用于刻画现实世界中各种各样的实体间的复杂关系.最短路径查询是图研究领域中一类非常重要的查询并有着广泛的应用.然而,目前大多数关于最短路径的查询都是定义在单代价(权重)图模型下的.现实世界中,基于单一代价所选择的最短路径并不明智,比如路程最短的路径需要花费极高的费用.该文中,作者介绍了多维代价图模型的概念,并给出了多维代价图模型下基于函数的最优路径的定义.现有的计算最短路径的方法都利用了最短路径的子路径最优的性质:最短路径上的任意两点间的子路径是这两点的最短路径.因此,在计算最短路径的过程中,对访问过的每个顶点,只需保留起点到该点的最短路径即可.不幸的是,多维代价图模型下,当评分函数是非线性的时候,子路径最优的性质并不成立.因此,目前的方法均不能应用于多维代价图模型下基于函数的最优路径查询问题.该文给出了一个best-first search分支界限法并给出3种优化策略.进一步,给出了一个顶点过滤算法,该算法能从图中过滤掉大部分不属于最优路径的顶点.最后,用真实数据集上的实验验证了算法的有效性. 相似文献
5.
提出了一种基于导频的OFDM信道估计算法,该算法利用最小平方误差准则搜索时域信道的多径时延,通过最小二乘算法计算路径增益,经傅里叶变换得到频域信道估计.提出了一种串行路径搜索算法,能够大大减少路径搜索的计算量.仿真结果表明在低信噪比条件下路径搜索算法仍然能够有效地工作,并指出搜索路径数量应当设置为等于或者大于实际信道的多径数. 相似文献
6.
The UTS benchmark is used to evaluate the expression and performance of task parallelism in OpenMP 3.0 as implemented in a number of recently released compilers and run-time systems. UTS performs parallel search of an irregular and unpredictable search space, as arises, e.g., in combinatorial optimization problems. As such UTS presents a highly unbalanced task graph that challenges scheduling, load balancing, termination detection, and task coarsening strategies. Expressiveness and scalability are compared for OpenMP 3.0, Cilk, Cilk++, Intel Thread Building Blocks, as well as an OpenMP implementation of the benchmark without tasks that performs all scheduling, load balancing, and termination detection explicitly. Current OpenMP 3.0 run time implementations generally exhibit poor behavior on the UTS benchmark. We identify inadequate load balancing strategies and overhead costs as primary factors contributing to poor performance and scalability. 相似文献
7.
利用自主式水下航行器(Autonomous Underwater Vehicle,AUV)对水下多目标进行协同探测是目前海洋技术领域的研究热点.主要研究在水下三维区间内的多AUV任务分配与协作探测路径规划机制,建立了以每个AUV能量耗费与能耗均衡为约束条件的水下三维空间中的多旅行商MTSP(Multiple Traveling Salesman Problem)问题模型,利用遗传算法GA(Genetic Algorithm)对该NP-Complete问题进行启发式求解,同时设计了考虑巡航总路径及访问目标数的适应度函数以提高多AUV间的能耗均衡性,实现多个AUV对多个水下目标的优化协同探测.最后本文利用MATLAB R2014a软件对多AUV任务协作与多目标探测路径规划机制进行了仿真,仿真结果验证了本文方法能均衡多AUV多目标探测问题的能量消耗,进而提高巡航速度和生命周期. 相似文献
8.
9.
10.
11.
We propose an original, complete and efficient approach to the allocation and scheduling of Conditional Task Graphs (CTGs). In CTGs, nodes represent activities, some of them are branches and are labeled with a condition, arcs rooted in branch nodes are labeled with condition outcomes and a corresponding probability. A task is executed at run time if the condition outcomes that label the arcs in the path to the task hold at schedule execution time; this can be captured off-line by adopting a stochastic model. Tasks need for their execution either unary or cumulative resources and some tasks can be executed on alternative resources. The solution to the problem is a single assignment of a resource and of a start time to each task so that the allocation and schedule is feasible in each scenario and the expected value of a given objective function is optimized. For this problem we need to extend traditional constraint-based scheduling techniques in two directions: (i) compute the probability of sets of scenarios in polynomial time, in order to get the expected value of the objective function; (ii) define conditional constraints that ensure feasibility in all scenarios. We show the application of this framework on problems with objective functions depending either on the allocation of resources to tasks or on the scheduling part. Also, we present the conditional extension to the timetable global constraint. Experimental results show the effectiveness of the approach on a set of benchmarks taken from the field of embedded system design. Comparing our solver with a scenario based solver proposed in the literature, we show the advantages of our approach both in terms of execution time and solution quality. 相似文献
12.
13.
An instance of the path hitting problem consists of two families of paths,
and ℋ, in a common undirected graph, where each path in ℋ is associated with a non-negative cost. We refer to
and ℋ as the sets of demand and hitting paths, respectively. When p∈ℋ and
share at least one mutual edge, we say that p
hits q. The objective is to find a minimum cost subset of ℋ whose members collectively hit those of
. In this paper we provide constant factor approximation algorithms for path hitting, confined to instances in which the underlying
graph is a tree, a spider, or a star. Although such restricted settings may appear to be very simple, we demonstrate that
they still capture some of the most basic covering problems in graphs. Our approach combines several novel ideas: We extend
the algorithm of Garg, Vazirani and Yannakakis (Algorithmica, 18:3–20, 1997) for approximate multicuts and multicommodity flows in trees to prove new integrality properties; we present a reduction
that involves multiple calls to this extended algorithm; and we introduce a polynomial-time solvable variant of the edge cover
problem, which may be of independent interest.
An extended abstract of this paper appeared in Proceedings of the 14th Annual European Symposium on Algorithms, 2006.
This work is part of D. Segev’s Ph.D. thesis prepared at Tel-Aviv University under the supervision of Prof. Refael Hassin. 相似文献
14.
Path Problems in Structured Graphs 总被引:1,自引:0,他引:1
15.
针对Trace驱动的并行性能模拟问题,提出基于Trace信息指导的映射方法CO-LP3M。CO-LP3M利用从Trace中提取的目标应用程序的通信特征,以宿主机物理进程间通信次数最小化为目标,兼顾计算负载均衡,生成并行模拟任务到宿主机的映射。对Jacobi3D和HPL两个程序进行实验改为:对HPL程序进行实验(注:此处本来是两个程序的,后来为了缩减篇幅就删掉了其中的一个),结果表明CO-LP3M可有效提高并行模拟性能,相对于常见的映射方式,模拟性能最多提高14.7%。在此基础上给出CO-LP3M的扩展技术SCO-LP3M。 相似文献
16.
基于完成时间的任务分配方案与性能分析 总被引:4,自引:0,他引:4
网络计算的迅速发展对网络资源的调度问题提出了新的挑战,用户对于服务质量的要求越来越高.大规模的复杂系统,如何能在现有硬件资源的基础之上提高整个系统的响应时间和吞吐量是当前的一个研究热点.基于完成时间的任务分配方案(SEF,OSEF),以多服务器多队列模型为基础,通过这种方案与现有方案之间的性能比较和分析,利用随机Petri网进行模拟实验,结果表明这种方案是高效可行的. 相似文献
17.
网络路径的端到端性能直接决定了为用户提供服务的质量,网络路径性能的测量是网络运营和SLA(ServiceLevelAgreement)验证的重要组成部分。文章在描述端到端路径性能检测的一般性问题的基础上,提出了延时差平稳系数和绝对平稳系数作为测量检测网络路径性能的几个评价指标,作为已有的测量标准化工作的补充和利用网络测量进行端到端性能管理的参考方法。 相似文献
18.
DAG任务图的一种调度算法 总被引:1,自引:1,他引:1
并行程序的调度技术是开发并行计算机系统的计算潜能的关键问题。本文讨论了4种典型的调度算法的缺陷,提出了一种新的调度算法CPFMBF,它采用的策略是:优先调度关键路径节点,其次调度b-level值大的节点,再次调度节点的关键路径影响度大的节点。对照分析及在几种具代表性的工程应用任务图上的实验结果证明CPFMBF算法的调度性能普遍好于其它算法。 相似文献
19.
网格服务资源多维性能聚类任务调度 总被引:1,自引:0,他引:1
网格计算是当前一个重要的研究领域,其中任务调度是一个基本组成部分,其性能直接影响到网格服务质量.为了缩短任务调度完成时间,提高任务调度性能,提出了一种网格资源多维性能聚类任务调度算法MPCGSR (task scheduling algorithm based on multidimensional performance clustering of grid service resources).该算法根据网格环境下服务资源数量庞大、异构、多样的特点,预先以构建的网格服务资源超图模型为基础,结合小世界理论对服务资源进行多维性能聚类,将任务与聚类资源相匹配并实施调度.模拟实验结果表明,算法较之同类算法具有优越性,是一种有效的网格任务调度算法. 相似文献
20.
Programming and Computer Software - Graph data models are widely employed in different areas of computer science, e.g., graph databases, bioinformatics, social network analysis, and static code... 相似文献