(m-,P1)约束规范的动态调度算法研究

(m,p1)有效解决了μ-pattern中第一个数字为0时部分约束规范失效的问题。在弱硬实时调度算法研究的基础上,针对(m,p1)约束规范,提出了一个动态弱硬实时调度算法,分析与仿真结果表明,算法效果良好。     

满足偏序约束的在线调度

具备偏序关系的实时调度要求调度算法产生的执行序列既要满足任务的实时约束,又要满足任务间执行的偏序约束。基于并行拓扑排序,提出一种新的在线调度算法,该算法通过同时考察任务间执行的串行性和并行性来进行优先级设置,能够处理释放时间任意的任务集。给出该算法的原理和设计,并通过示例分析和比较对算法进行验证。     

开销敏感的多处理器最优节能实时调度算法

嵌入式多处理器系统的能耗问题变得日益重要,如何减少能耗同时满足实时约束成为多处理器系统节能实时调度中的一个重要问题.目前绝大多数研究基于关键速度降低处理器的频率以减少动态能耗,采用关闭处理器的方法减少静态能耗.虽然这种方法可以实现节能,但是不能保证最小化能耗.而现有最优的节能实时调度未考虑处理器状态切换的时间和能量开销,因此在切换开销不可忽视的实际平台中不再是最优的.文中针对具有独立动态电压频率调节和动态功耗管理功能的多处理器系统,考虑处理器切换开销,提出一种基于帧任务模型的最优节能实时调度算法.该算法根据关键速度来判断系统负载情况,确定具有最低能耗值的活跃处理器个数,然后根据状态切换开销来确定最优调度序列.该算法允许实时任务在处理器之间任意迁移,计算复杂度小,易于实现.数学分析证明了该算法的最优性.     

多处理器环境中基于节能及容错的实时动态调度算法

当前处理器由于较高的能量消耗,导致处理器热量散发的提高及系统可靠性的降低,同时任务实际运行中的错误也降低了系统的可靠性.因此同时满足节能性及容错性已经成为目前计算机领域较为关心的问题.提出的调度算法针对实时多处理器计算环境,以执行时间最短的任务优先调度为基础,结合其他有效技术(共享空闲时间回收及检查点技术),使得实时任务在其截止期内完成的同时,能够动态地降低整个系统的能量消耗及动态容错.针对独立任务集及具有依赖关系的任务集,提出两种算法:STFBA1及STFBA2(shortest task first based algorithm).通过实验与目前所知的有效算法相比,算法具有更好的性能(调度长度及能量消耗)及较低的通信时间复杂度.     

SIMD-LA模型上的大整数乘法

本文提出了一种基于SIMD-LA模型的大整数乘法的算法,将分治策略与Karatsuba-Offman算法相结合改进了已有的算法.当使用p台处理器,大整数长度n＜=256p时,其时间复杂度为O(p);大整数长度n＞256p时,其时间复杂度为O(p[n]1.58/|p|+p).其时间复杂度比传统算法有了进一步的提高.     

最长公共子序列问题的改进快速算法

现在几个最常用的解决最长公共子序列(LCS)问题的算法的时间复杂度分别是O(pn),O(n(m-p)).这里m、n为两个待比较字符串的长度,p是最长公共子串的长度.给出一种时间复杂度为O(p(m-p)),空间复杂度为O(m+n)的算法.与以前的算法相比,不管在p<相似文献   

基于凸剖分的多边形窗口线裁剪算法

以不增加新点的方式将多边形剖分为一些凸多边形,并基于这些多边形的边建立二叉树进行管理.裁剪计算时,根据二叉树快速地找到与被裁剪线有相交的凸多边形,然后运用高效的凸多边形裁剪算法进行线裁剪.该方法能自适应地降低裁剪计算的复杂度,使其在O(logn)和O(n)之间变化,并在大多数情况下小于O(n),其中n是多边形边数.虽然该方法需要进行预处理,但在许多应用(如多边形窗口对多边形的裁剪)中,其总执行时间(包括预处理时间和裁剪时间)比已有的不需要预处理的裁剪算法少很多.     

通用调度框架的改进及其在Linux中的实现

在嵌入式Linux实时系统中,要求内核对不同时问约束的任务采用不同的调度算法.但目前Linux内核采用单一的实时调度模式,不能灵活地执行多种调度算法,也就无法满足实时系统中实时任务的时间约束.引入了一种能够在Linux内核调度中执行多种调度算法的框架,即通用调度框架(GSF),并改进了其中的多算法调用机制,从而更好地在Linux内核中实现GSF.     

一个调度Fork-Join任务图的新算法

对基于总线的机群系统,本文提出了一种基于任务复制的调度Fork-Join任务图的新算法。该算法通过任务集划分计算调度长度,并在不增加调度长度的同时将任务尽可能调度在已用处理器上,节省处理器数。新算法的时间复杂度高于现有算法,但其调度性能最优。     

基于网格与R-树空间索引的矢量线图任意简单多边形窗口裁剪算法

针对大规模矢量线与大量裁剪窗口同时出现的线裁剪算法存在的三个主要问题,减少线段求交次数、简化交点出入属性计算以及无交点矢量线的取舍,本文提出了一种基于双空间索引的大规模线图任意多边形裁剪算法。算法根据裁剪多边形的边分别建立R-树索引和均匀Cell索引,应用两种索引各自的优点大幅减少被裁剪线段与裁剪多边形上线段的求交次数。在此基础上,基于均匀网格索引,提出局部射线法,简化交点出入属性计算和无交点矢量线的取舍。本文在传统算法基础上提出三点改进:首先提出基于两种空间索引模型进行线段求交计算,保证算法在理论上具有较低的时间复杂度;其次,在射线法和网格索引基础上提出局部射线法,使得判断每个交点出入属性的时间复杂度为O(1)～ O(n~(1/2)),与参考文献中的算法相比,此方法的优点是避免判断多边形上顶点的方向;最后,算法中裁剪多边形可以是包含任意多个洞的任意简单多边形,克服传统算法中对裁剪多边形的特定约束条件。     

基于至少连续满足弱硬实时限制的调度算法

对至少连续满足弱硬实时限制的性质进行了扩充，提出并证明了任务不满足子序列长度与任务连续满足的截止期限数之间的关系.在此基础上提出了改进的弱硬实时限制调度算法：MRA．MRA用于在弱硬实时系统中保证任务满足至少连续满足限制，是一种高效、易于实现的调度算法,仿真实验的结果表明，MRA调度算法在提高任务对限制的满足率和保证任务实时性方面优于同类算法．     

Matching and scheduling algorithms for minimizing execution timeand failure probability of applications in heterogeneous computing

In a heterogeneous distributed computing system, machine and network failures are inevitable and can have an adverse effect on applications executing on the system. To reduce the effect of failures on an application executing on a failure-prone system, matching and scheduling algorithms which minimize not only the execution time but also the probability of failure of the application must be devised. However, because of the conflicting requirements, it is not possible to minimize both of the objectives at the same time. Thus, the goal of this paper is to develop matching and scheduling algorithms which account for both the execution time and the reliability of the application. This goal is achieved by modifying an existing matching and scheduling algorithm. The reliability of resources is taken into account using an incremental cost function proposed in this paper and the new algorithm is referred to as the reliable dynamic level scheduling algorithm. The incremental cost function can be defined based on one of the three cost functions developed here. These cost functions are unique in the sense that they are not restricted to tree-based networks and a specific matching and scheduling algorithm. The simulation results confirm that the proposed incremental cost function can be incorporated into matching and scheduling algorithms to produce schedules where the effect of failures of machines and network resources on the execution of the application is reduced and the execution time of the application is minimized as well     

用并行遗传算法解决带约束并行多机调度问题

遗传算法是一种全局优化的数值计算方法。它存在自然并行性。本文提出一种解带约束并行多机调度问题的主从式控制网络并行遗传算法,并在PVM环境下实现。计算结果表明,并行遗传算法是有效的,且能适用于大规模并行多机调度问题。     

用并行遗传算法解决带约束并行多机调度问题

遗传算法是一种全局优化的数值计算方法,它存在自然并行性,本文提出了一种解带约束并行多机调度问题的主从式控制网络并行遗传算法,并在PVM环境下实现。计算结果表明,并行遗传算法是有效的,且能适用于大规模并行多机调度问题。     

A hierarchical reliability-driven scheduling algorithm in grid systems

In a Grid computing system, many distributed scientific and engineering applications often require multi-institutional collaboration, large-scale resource sharing, wide-area communication, etc. Applications executing in such systems inevitably encounter different types of failures such as hardware failure, program failure, and storage failure. One way of taking failures into account is to employ a reliable scheduling algorithm. However, most existing Grid scheduling algorithms do not adequately consider the reliability requirements of an application. In recognition of this problem, we design a hierarchical reliability-driven scheduling architecture that includes both a local scheduler and a global scheduler. The local scheduler aims to effectively measure task reliability of an application in a Grid virtual node and incorporate the precedence constrained tasks’ reliability overhead into a heuristic scheduling algorithm. In the global scheduler, we propose a hierarchical reliability-driven scheduling algorithm based on quantitative evaluation of independent application reliability. Our experiments, based on both randomly generated graphs and the graphs of some real applications, show that our hierarchical scheduling algorithm performs much better than the existing scheduling algorithms in terms of system reliability, schedule length, and speedup.     

An improved particle swarm optimization algorithm for flowshop scheduling problem

The flowshop scheduling problem has been widely studied and many techniques have been applied to it, but few algorithms based on particle swarm optimization (PSO) have been proposed to solve it. In this paper, an improved PSO algorithm (IPSO) based on the “alldifferent” constraint is proposed to solve the flow shop scheduling problem with the objective of minimizing makespan. It combines the particle swarm optimization algorithm with genetic operators together effectively. When a particle is going to stagnate, the mutation operator is used to search its neighborhood. The proposed algorithm is tested on different scale benchmarks and compared with the recently proposed efficient algorithms. The results show that the proposed IPSO algorithm is more effective and better than the other compared algorithms. It can be used to solve large scale flow shop scheduling problem effectively.     

一种改进的基于任务复制的多核调度算法

在多核系统中,任务调度是决定系统性能的关键因素之一。为优化任务调度,基于一些典型的任务调度算法（如PPA,徐成提出的算法等）,提出了一种新的任务调度算法。该算法一方面合理确定前驱任务复制的先后顺序,而且进行两个阶段的复制,从而可以复制更多的前驱任务以减少调度长度和处理器上空余时间;另一方面,通过去除不影响任务系统调度长度的冗余簇,然后进行簇之间的合并,以减少处理机的数目和调度长度。实验表明,改进后的算法在任务调度的性能上优于典型算法。     

基于动态关键任务的多处理器任务分配算法

多处理器调度问题是影响系统性能的关键问题,基于任务复制的调度算法是解决多处理器调度问题较为有效的方法.文中分析了几个典型的基于任务复制算法,提出了基于动态关键任务(DCT)的多处理器任务分配算法.DCT算法以克服贪心算法不足为要点,调度过程中动态计算任务时间参数,准确确定处理器的关键任务,以关键任务为核心优化调度,逐步改善调度结果,最终取得最优的调度结果.分析和实验证明,DCT算法优于现有其它同类算法.     

基于多目标全局约束的任务分配和调度算法

针对嵌入式系统中大多数任务执行算法不考虑目标成本问题,提出了一种基于多目标全局约束的任务分配和调度算法。算法使用约束逻辑编程来对任务执行资源如处理单元、通信设备以及代码和数据存储量的使用进行多目标全局约束。算法假设ROM和RAM分别用于代码存储和数据存储,算法还考虑数据在数据存储器中的位置。实验结果表明,尽管在多个约束条件下,提出的任务分配和调度算法无论在代码存储和数据存储量使用方面,还是在对任务有效求解方面都能取得比普遍采用的贪婪调度算法更好的结果。     

基于云科学工作流调度的代价与能效优化算法

为了降低云环境中科学工作流调度的执行代价与数据中心能耗,提出了一种基于能效感知的工作流调度代价最优化算法CWCO-EA。算法在满足截止时间约束下,以最小化工作流执行代价与降低能耗为目标,将工作流的任务调度划分为四步执行。首先,通过代价效用的概念设计虚拟机选择策略,实现了子makespan约束下的任务与最优虚拟机间的映射;其次,通过串行与并行任务合并策略,同步降低了工作流的执行代价与能耗;然后,通过空闲虚拟机重用机制,改善了租用虚拟机的利用率,进一步提高了能效;最后,通过任务松驰策略实现了租用虚拟机的能力回收,节省了能耗。通过四种科学工作流的仿真实验,结果表明,CWCO-EA算法比较同类型算法,在满足截止时间的同时,可以同步降低工作流的执行代价与执行能耗。