滤光片表面缺陷视觉检测系统多处理器调度优化

针对滤光片表面缺陷视觉检测系统中在线检测实时性需求对检测速度要求较高,研究一种有效利用可用硬件资源并行处理实时工作提高处理速度的调度优化策略。基于AOE图对滤光片表面缺陷视觉检测系统进行任务级分析,优化事件、活动拓扑关系与任务间冗余的数据相关性、资源相关性,建立并行任务模型;采用关联处理器调度算法(arbitrary processor affinities,APAs)进行并行多处理器调度,指定任务只能被某个处理器集合执行,将期限紧迫、缓存敏感的任务限制在单一处理器,提高资源利用率,改进检测系统实时性。试验结果表明:在尺寸为1.20mm×1.20mm、26×28个滤光片组成滤光片面板上,采用多处理器调度可使检测速度极大提升,采用APAs调度算法后,平均缺陷识别完成时间为常规检测系统时间的36.5%,可以满足在线实时要求,证明应用多处理器调度方法,可以极大提升检测仪器实时性能的有效性。

可编程路由器中基于缓冲队列长度阈值的处理器调度

可编程路由器除了转发IP分组之外 ,还需要执行计算任务 .如何调度可编程路由器中CPU的处理能力是一个需要解决的重要问题 .本文首先建立了一种通用的可编程路由器软件体系结构 ,在此基础上 ,提出了一种基于缓冲队列长度阈值的CPU调度算法 ,采用随机Petri网对算法进行了模型分析和计算 .结果表明 ,该调度算法可以同时保证可编程路由器中的尽力发送流和QoS流的计算需求 .

基于Intel网络处理器的微处理器调度算法

针对网络处理器的核心问题—微处理器并行调度,以IntelIXP2400网络处理器为例,提出并实现了一种基于线程池的两阶段微处理器调度算法TS-MPSBPT。该算法将IPv4转发系统分成两个阶段,阶段内微处理器采用线程池工作模式,既解决了微指令空间不足问题,又可以充分发挥系统并行处理特性;该算法通过判断微处理器的空闲线程数和已处理数据包字节数,将数据包分配给线程池中负载最轻的微处理器,实现算法的负载均衡原则;通过将同类型m包或同一个流IP包分配给同一个微处理器,提高cache命中率和局部内存利用率,实现算法的局部性原则。实验结果表明,采用TS-MPSBPT算法的IPv4转发系统负载均衡,与Radisys公司原IPv4转发程序相比,新系统包转发速率有较大提高,在包长度较小时效果尤其显著。

基于I/O受限进程识别的虚拟处理器调度机制

针对多核平台的虚拟化环境中客户机与虚拟机管理器(virtual machine monitor,VMM)之间语义缝隙造成客户机I/O性能下降的问题,提出了一种基于I/O受限进程识别的虚拟处理器(virtual CPU,vCPU)调度机制。该机制在客户机内部利用推断技术识别I/O受限进程,通过客户机与VMM的协作实现I/O事件与I/O受限进程的关联,利用保证客户机之间公平性的虚拟对称多核处理器(virtual symmetric multi-core processor,vSMP)Internal调度算法,优先调度与I/O事件关联的I/O受限进程所在的vCPU来桥接客户机与VMM之间的语义缝隙,提高拥有vSMP的客户机中I/O负载性能。测试结果表明,相比于KVM虚拟化环境的CFS调度机制,该机制可以在保证客户机CPU公平性的前提下,有效提升运行混合负载的vSMP客户机中I/O负载性能,同时只增加较小的客户机额外开销,可以应用在负载多样性和不可预测性的虚拟桌面和云计算环境中。

Windows NT中的处理器调度及改进方法

本文首先描述了WindowsNT操作系统的调度。然后针对其不足，介绍一种新的处理器调度方法──处理器继承调度。WindowsNT操作系统若能够在今后的版本中采用此框架，将大大提高其系统的灵活性。

一种基于数据质量的多处理器平台实时更新事务调度算法

提出一种多处理器平台上基于数据质量的实时更新事务全局调度算法(MU-DA)。数据质量根据时态对象的无效程度来定义。算法通过合理地预分配各事务执行所需处理器资源以及动态控制更新实例的接纳和执行使系统数据质量最大化。研究结果表明:MU-DA算法在各种事务集负载下均能保证较高的数据质量;在高负载设置下,MU-DA算法的系统数据质量与用户事务质量均远比基准算法MU-D与MU-SA的高,能够很好地满足用户事务在数据实时性方面的要求。

一种多处理器平台上的传感器事务调度算法

如何有效地调度传感器事务以维护数据的时态一致性是信息物理融合系统研究中的一个重要问题。已有的调度算法基本上都是针对单处理器平台来设计的。提出一种多处理器平台上的传感器事务调度算法,算法通过合理地分配和调整事务实例执行所需处理器资源来保证数据的时态一致性约束,通过预先计算出全局重复调度序列来降低运行开销,给出了算法的可调度性分析。实验结果表明,该算法具有较高的调度成功率,其产生的更新负载也较低。

单处理器最少延误问题的双逆向调度算法

单处理器最少延误问题实际上是对任务集中每一个任务如何分配执行时间使得延误任务数量最少的问题,该问题是处理器调度问题中一类重要的基础问题.本文主要对该问题的调度算法进行研究,提出了一种基于排序的双逆向分配任务执行时间的调度算法,称为双逆向调度算法,该算法时间复杂度为O(n2),通过验证该算法是可行的.另外,还对任务关系进行了分析,并提出了任务固有冲突、任务临界冲突时刻、任务时间窗口中心点、任务间接冲突、任务冲突度等概念.

多处理器任务调度算法TDS的建模与验证

在多处理器系统中,一个应用所要完成的任务可以分配给同一个处理器处理,也可以分配给多个处理器处理,所以传统的测试方法难以满足多处理器任务调度算法的验证。在此,提出一个基于扩展Büchi自动机的形式化模型,并用该模型来描述多处理器任务调度算法TDS(Task Duplication based Scheduling);用线性时序逻辑描述出算法TDS期望的一些性质;最后在该模型上验证了这些性质。该方法有效地克服了传统测试的局限性,保证了多处理器任务调度的可靠性。

一种面向非对称多核处理器的虚拟机集成调度算法

在计算机体系结构领域,非对称多核处理器将成为未来的主流.对于非对称多核处理器上的虚拟处理器调度问题,现有研究缺乏理论分析,且没有考虑虚拟处理器的同步特性.针对该问题,文中首先建立非线性规划模型,分析得出全面考虑虚拟处理器同步特性、核心非对称性以及核心负载的调度原则.然后,基于调度原则提出一个集成调度算法,该算法定义了效用因子、比例系数、比例资源的概念,结合虚拟处理器的同步特性和核心的非对称性对资源和负载进行全面度量;同时通过运行队列分解降低调度开销.提出的算法是第一个在非对称多核处理器上利用虚拟处理器同步特性的调度算法.实际平台上的实验表明：该算法实现了公平调度,并且性能比其他同类算法提高19％～48％.

一种有到达时间的多处理器混合流水车间调度的遗传算法(英文)

有到达时间的多处理器混合流水车间调度问题在实时机器视觉系统等领域有广泛的应用。这一问题是NP-困难的。鉴于以上原因,给出一种遗传算法。对不同的交叉算子和变异算子以及涉及的参数的不同取值进行试验,并对试验的结果进行分析和讨论,从而给出最好的参数组合。

考虑运输的柔性流水车间多处理器任务调度的混合遗传优化算法

多处理器任务调度在制造业有着较广泛的应用,为了解决实际柔性流水车间环境下的多处理器任务调度优化问题,研究了考虑运输时间和释放时间的多阶段柔性流水车间多处理器任务调度问题,该问题为NP-hard问题,以最小化最大完工时间为目标建立了柔性流水车间多处理器任务调度整数规划模型。为有效求解该问题,首先研究了工件加工机器流生成机制、单工件加工机器流矩阵编码方案和批量工件加工机器流编码方案。进而设计了基于机器空闲随机筛选的工件安排机制,产生该规划的初始解生成方法,以最小化最大完工时间原则进行新解筛选。然后构建基于工件顺序与加工机器流同步交叉的新解更新过程、基于工件顺序与加工机器流同步变异的新解调整过程,并利用迭代贪婪算法完成调整和重建操作,产生全新方案以改善求解质量,最终形成结合迭代贪婪算法的混合遗传融合优化策略。仿真实验利用解的下界得出偏差百分比,分别用遗传算法、迭代贪婪算法和混合遗传融合优化算法对不同规模的问题进行测试,结果表明,混合遗传融合优化算法能够获得较好的近优解。

带多处理器混合流水车间调度问题的混合鱼群算法

针对带多处理器的混合流水车间调度问题(hybrid flow shop scheduling with multiprocessor task problems),以最小化所有工件的最大完成时间(makespan)为优化目标,提出一种融合了改进的人工鱼群算法和禁忌搜索算法的混合算法。首先改进人工鱼群算法相关行为及实验优选算法参数,提高了人工鱼群算法收敛速度和精度;然后结合人工鱼群算法收敛快和禁忌算法局部搜索能力强的特点,利用改进的人工鱼群算法进行全局搜索,获得较好的优化解域,再通过禁忌算法在优化解域内进行局部寻优,得到一个最终满意的优化解。基于180个标准算例,算法实验结果表明混合算法的优化性能明显优于禁忌算法和粒子群算法,并且很接近改进的遗传算法。

多处理器系统实时任务限制抢占调度算法

针对多处理器平台完全可抢占调度(Fully Preemptive Scheduling,F-PS)可能造成低优先级任务的响应时间超出截止期限的问题,提出了两种基于固定抢占点模型的限制抢占调度算法:一种是常规延迟(Regular Deferrable Scheduling,RDS),即高优先级任务抢占正在运行的执行到最近抢占点的低优先级任务,被抢占的任务可能不具有最低优先级;另一种是自适应延迟(Adaptive Deferrable Scheduling,ADS),即高优先级任务等待正在运行的最低优先级任务执行到最近的可抢占点位置,并抢占。搭建了一个仿真实验平台,并在该平台上进行一系列的仿真实验来探究两种算法的性能表现。实验结果表明:在动态和静态优先级调度下,任务抢占次数大小顺序为F-PS>RDS>ADS;当抢占时间消耗大于临界值时,RDS和ADS的任务可调度率与F-PS接近。

HFS多处理器任务调度的改进拉格朗日松弛

针对带多处理器任务的混合流水车间调度问题,以总加权完成时间为目标函数,考虑加工阶段间运输时间和工件动态到达的生产特征,提出了一种基于代理次梯度法的改进拉格朗日松弛算法。算法采用每次迭代只最优求解几个拉格朗日子问题的异步迭代策略,利用代理次梯度获得合适的乘子更新方向。分别应用所提出的改进算法和常规的基于次梯度法的拉格朗日松弛算法对多达150个工件的问题进行仿真测试,结果表明,所提出的改进算法比常规拉格朗日松弛算法表现出更好的求解能力,尤其是求解大规模问题。

基于任务紧迫度的多处理器任务调度算法

调度算法是多核处理器操作系统设计的核心所在,如何合理地将众多任务分配给不同的资源以使整个多核处理器系统达到最佳性能,是调度要解决的首要问题。在经典多处理器任务调度算法———ONERT算法的基础上,提出一种基于任务紧迫度的改进算法,较好地弥补了ONERT算法在处理器轻载时负载不均衡的不足。通过python程序实现了该算法,并通过实验验证了该方法在处理器轻载时实现比ONERT算法更好的负载均衡。

基于模型检测的多处理器实时系统可调度性自动化分析

近年来,模型检测技术获得快速的发展,已有学者将模型检测技术用于多处理器实时系统可调度性分析。但如果对每个实际系统都手工建立模型进行可调度性验证,过程繁琐且模型不可重复利用。针对此,开发一个工具用于自动完成可调度性检测,并可视化显示结果。

一种基于CPU占用率的嵌入式系统网络处理调度算法

物联网、云计算飞速发展,众多嵌入式设备需要接入网络,但是嵌入式设备性能和资源有限,过多的注意网络数据的处理,往往占用处理器过多,降低系统整体性能。为了实现终端IP通信和合理调度网络处理对系统中CPU的占用,采用Xilinx公司的FPGA系统平台,移植了瑞士计算机科学院发布的μIPv6协议栈,并提出了基于CPU占用率的嵌入式系统网络处理调度算法,进行验证,可以优化实验平台的嵌入式系统性能。

一种基于复制的高效任务调度算法

近年来,对于拥有高性能计算功能的多处理器(包括多核处理器)系统的研究已逐渐成熟,并且在很多并行系统中已经开始采用多处理器架构。但是现在针对多处理器平台的任务调度算法尚未成熟,在满足最大化并行执行各个任务时难以兼顾任务间的通信延迟。基于此,提出了一个新的算法,采用选择复制特定任务的方法来减少任务间的通信时间并提高处理器的利用率,以达到使整个任务的执行时间最短的目标。算法的核心是基于待调度任务,分别计算其在有限个处理器下复制与不复制关键父任务的完成时间,并在之中找到符合条件的完成时间,基于该完成时间,将待调度任务调度到相应的处理器上。该调度算法采用了选择复制的方式进行调度,在增加了处理器利用率的同时,有效地减少了任务之间的通信时间,使整个任务的调度时间变短,调度时间相比对比算法平均缩短2%。这对于结构复杂、参数随机的有向无环图(Directed Acyclic Graph,DAG)任务模型来说,具有高效的调度性能。

基于GA的分布式任务调度算法的研究

任务调度问题是一个强NP难题,算法研究是它的一个重要研究方向,智能Agent技术研究和应用开发在AI领域和分布环境下更具研究价值。分析了实时智能监控系统作业调度问题的特点,提出了结合GA和MAS技术的新的调度策略及算法。应用表明,该算法具有很好的可扩展性、适应性和稳定性。