A Scheduling Algorithm for Flexible Manufacturing Cell

In this paper, a new scheduling algorithm for the flexible manufacturing cell is presented, which is a discrete time control method with fixed length control period combining with event interruption. At the flow control level we determine simultaneously the production mix and the proportion of parts to be processed through each route. The simulation results for a hypothetical manufacturing cell are presented.

OpenMP循环调度算法及SpMV多核并行化研究

OpenMP是一种支持Fortran，C/C++的共享存储并行编程标准。它基于fork-join的并行执行模型，将程序划分为并行区和串行区。近几年来，OpenMP在SMP(Symmetric Multi-Processing)和多核体系结构的并行编程中得到了广泛的应用。随着多核处理器的发展，实际的应用程序如何充分利用多个处理器核来提高运算效率也成为研究的热点。 在科学计算中，循环结构是最核心的并行对象之一。考虑到负载平衡、调度开销、同步开销等多方面因素，OpenMP标准制定了Static调度、Dynamic调度、Guided调度和Runtime调度等不同策略。针对Guided调度策略不适合递减型循环结构的缺点，本文提出了一种改进的new_guided调度策略，并在OMPi编译器上加以实现。New_guided调度策略的主要思想是对前半部分的循环采用Static调度，后半部分的循环采用Guided调度。此外，本文针对不同的循环结构，在多核处理器上对不同的调度策略进行了评测。测试结果表明，在一般情况下，OpenMP默认的Static策略的调度性能最差；对于规则的循环结构和递增的循环结构，Dynamic调度策略、Guided调度策略和new_guided策略的性能差别不大；对于递减型的循环结构，Dynamic调度策略和new_guided策略的性能相当，要优于Guided调度策略；对于求解Mandelbrot集合这类计算量集中在中间的随机循环结构，Dynamic调度策略优于其它策略，new_guided策略的性能介于Dynamic调度和Guided调度之间。 随着多核处理器的问世和发展，多线程程序设计也已经成为一个不可回避的问题。稀疏矩阵向量乘(SpMV, Sparse Matrix-Vector Multiplication)是一个十分重要且经常被大量调用的科学计算内核。SpMV的存储访问一般都极不规则，导致现有的SpMV算法效率都比较低。目前，多核处理器芯片上的内核数量正在逐步增加。这使得在多核处理器上对SpMV进行并行化加速变得非常重要。本文介绍了稀疏矩阵的两种常用的存储格式CSR和BCSR，并采用OpenMP实现了SpMV的多核并行化。此外，本文还讨论了寄存器分块算法、压缩列索引等优化技术，以及不同调度策略对多线程并行后的SpMV的影响。在曙光天阔服务器S4800A1上的测试表明，大部分矩阵都取得了可扩展、甚至是超线性的加速比，但是对于部分规模较大的矩阵，加速效果并不明显。在我们的测试中，与基于CSR实现的多线程SpMV相比，采用寄存器分块算法优化后的SpMV运算速度平均提高了28.09%。在基于CSR实现的多线程SpMV中，采用列索引优化技术后的程序比优化前的速度平均提高了13.05%。此外，本文实现了一种基于非零元个数的调度策略。在该策略中，每个线程处理几乎相同数量的非零元。我们将它和OpenMP标准提供的三种调度策略进行了测试和分析。测试结果表明：与OpenMP提供的调度策略相比，基于非零元个数的调度策略能取得更好的负载平衡；Dynamic调度和Guided调度在多线程SpMV中的性能基本相当，均优于Static调度策略。

一种改进的OpenMP指导调度策略研究

在科学计算中,循环结构是最重要的并行对象之一.考虑到负载平衡、调度开销等多方面因素,OpenMP标准提供静态调度、动态调度、指导调度和运行时调度等不同策略.针对指导调度策略不适合递减型循环结构的问题,提出一种改进的new_guided指导调度策略,并在OMPi编译器上加以实现.New_guided调度策略的主要思想是对前半部分的循环采用静态调度,后半部分的循环采用指导调度.针对不同循环结构,在多核处理器上对不同调度策略进行评测.结果表明,在一般情况下,OpenMP默认的静态策略的调度性能最差;对于规则的循环结构和递增的循环结构,动态调度、指导调度和new_guided策略的性能差别不大;对于递减型的循环结构,动态调度和new_guided策略的性能相当,要优于指导调度策略;对于某些极不规则的随机循环结构,动态调度明显优于其他策略,new_guided策略的性能介于动态调度和指导调度之间.

一种任务类型敏感的J2EE事务调度算法

J2EE(Java 2 platform enterprise edition)是构建分布式企业应用的基础中间件平台,当前的J2EE事务对资源的访问调度仍然是简单的先来先服务策略,导致服务器负载很重时,次要任务和关键任务争夺有限的资源,降低了关键任务的性能与成功率.为此,有必要识别任务类型,在资源不足时优先保证关键任务事务的执行.但提交给J2EE的事务基于交互方式执行,且缺乏必要的调度信息,因而不能简单地沿用已有的优先级驱动调度算法.提出一种新的事务调度算法TMPBP(threaded multi-queue priority-based protocol),该算法能够安全、有效地提高系统重负载情况下关键事务的服务质量,防止饥饿和优先级倒置.TMPBP包含了一种新的启发式优先级分派算法HRS(heuristic resource statistics),可以在调度信息缺乏的J2EE环境下动态识别关键事务.结果表明,通过合理地选择参数,TMPBP算法能够显著地提高关键事务的服务质量.

一种开放混合实时系统的开放自适应调度算法

开放计算环境下的实时与非实时任务不确定并发,以及多种实时约束混合的复杂约束系统,即开放混合实时系统的需求越来越广泛.通过引入接收控制、调度服务器、自适应调节机制,提出一种开放环境下的自适应实时系统调度架构——OARtS(open adaptive real-time scheduling).它能适应开放计算环境的不确定性,有控制地接受实时任务运行;可根据系统空闲计算带宽变化,自适应地调节任务的实时等级,使得系统运行在最优的实时性能上;对于软实时任务,可根据其计算带宽需求变化,自适应地调节其计算带宽分配,以适应任务执行时间时变引起的实时不确定性.

一种基于PID反馈控制的分时调度算法

近年来 ,在实时操作系统的研究中 ,已开始将反馈控制融入操作系统的任务调度 将这一想法与分时操作系统相结合 ,提出一种基于PID反馈控制的分时调度算法 它能根据任务对CPU带宽的个性化需求 ,并考虑开放的分时系统中CPU占用率的不确定动态变化特性 ,动态地分配CPU带宽 ,使CPU对任务集的处理效果始终处于最佳状态 性能分析实验结果表明 ,它不仅兼容传统的分时调度架构 ,还具有良好的动态、静态特性及鲁棒性 ,且引入的调度费用较低

一种基于强可有序化标准的长事务调度算法

现有的长事务并发机制在解决并发冲突和回滚时往往需要依赖于人工干预，且故障恢复的代价较高．提出了一种面向长事务的调度正确性标准——强可有序化标准，并提出了基于该标准的长事务调度算法．该算法利用事务的语义知识以提高事务的并发效率，同时使得长事务的恢复机制大为简化，且回滚代价大大降低．实验结果表明该算法对长事务具有较好的并发处理效果和恢复效率．

RM及其扩展可调度性判定算法性能分析

可调度性判定是实时调度算法的关键问题．单调速率算法RM（rate monotonic）及其扩展是应用广泛的实时调度算法，大量文献讨论了实时任务在这些算法下的可调度性判定，给出了相应的判定算法．但迄今为止，对这些判定算法的性能分析都是理论上的定性分析或者只是少数几种判定算法之间的简单比较，这不利于实时系统的开发．归纳了RM及其扩展的可调度性判定算法，通过测试平台，系统地测试和分析了各算法的性能和适用场合，讨论了各种条件和实现方式对算法性能和可调度性的影响．

一种新的基于优先级表的实时调度算法

本文提出了一种新的基于优先级表的实时调度算法 ,称作截止期—价值密度优先 (Deadline ValueDen sityFirst)算法 ,简称DVDF算法 .DVDF算法综合考虑了实时任务的截止期和价值密度两个参数 ,能够更好地适应不同的负载情况 .通过使用正常负载和过载情况下的典型数据对算法进行仿真研究表明 ,这种算法比单纯考虑截止期的EDF(EarliestDeadlineFirst)算法在性能方面有明显的改进 ,特别是在系统过载的情况下 ,能够优雅地降级

基于优先级表的实时调度算法及其实现

讨论了综合考虑任务的截止期和价值两个特征参数的优先级表设计方法,提出了EDV(earliestdeadlinevalue)与VED(valueearliestdeadline)两种不同的基于优先级表的实时任务调度算法,并且利用多重链表给出了这两种算法的实现,包括任务接收策略与任务完成/夭折策略的算法实现.这种优先级表设计方法及其基于多重链表的实现方法也适用于对任务的其他两种甚至3种不同特征参数之间的综合.基于累积实现价值率、加权截止期保证率与差分截止期保证率3个方面,分析了VED算法与EDV算法的性能,实验结果表明,在所有负载条件下VED算法与EDV算法相对于EDF(earliestdeadlinefirst)算法与HVF(highestvaluefirst)算法都有很大的性能改进.

实时异构系统的动态调度算法研究

实时多处理器系统是解决复杂实时应用的有效手段.然而,目前对实时多处理器调度算法的研究却大多集中在同构系统上,对实时异构系统的调度则研究得比较少.提出了一种新的实时异构系统的动态调度算法.该算法采用了集中式的调度方案,同时,引入了一个新的任务分配策略,从而通过提高任务可行性而提高了算法的调度成功率.此外,为了评估该算法的性能,还进行了大量的模拟研究.由于近视算法经简单修改便可以被应用到实时异构系统的动态调度中,因此,在模拟研究中,以近视算法作为基准,将其应用于实时异构系统动态调度时的性能与新算法进行了比较.模拟结果显示,在多种任务参数的取值下,新算法的调度成功率均高于近视算法.

改进的最小空闲时间优先调度算法

最小空闲时间优先(least slack first,简称LSF)算法结合任务执行的缓急程度来给任务分配优先级.任务所剩的空闲时间越少,就越需要尽快执行.然而,LSF算法造成任务之间的频繁切换或严重的颠簸现象,增大了系统开销,并限制了其应用.在调度策略中设置抢占阈值可以减少任务之间的切换,但现有的抢占阈值设置方法因受到固定优先级的限制而不适用于LSF算法.为了减轻LSF算法的颠簸现象,基于抢占阈值的思想,提出适用于LSF算法的抢占阈值分配方法,动态地给每个任务配置抢占阈值.任务的抢占阈值是随着任务执行的缓急程度不同而动态地变化的,而且不受任务个数的限制.仿真结果表明,通过对LSF算法的改进,任务之间的切换大大减少,同时降低了任务截止期错失率.该改进型算法对设计和实现实时操作系统具有一定的参考价值.

一种新的实时多处理器系统的动态调度算法

实时多处理器系统的动态调度算法一直是实时系统研究中的重要课题,而评价实时调度算法性能的一个最重要的指标是调度成功率.在近视算法的基础上提出了一种新的实时多处理器系统的动态调度算法——节约算法.在该算法中,提出了一个新的处理器选择策略,从而提高了算法的调度成功率.同时,为了研究节约算法的有效性,对其进行了大量的模拟,分析了一些任务参数的变化对算法调度成功率的影响,并与近视算法的调度成功率进行了比较.模拟结果显示,节约算法的调度成功率要优于近视算法.

模糊反馈控制实时调度算法

为了解决模糊不确定任务集在不可预测环境下的动态抢占调度问题,应用模糊规则和模糊调度理论,提出一个基于模糊反馈控制的调度算法,并建立相应的调度架构.该架构由基本调度器和模糊反馈控制两部分组成.用模糊调度算法作为基本调度器的调度算法,将任务集按不同优先级等级进行划分,优先级等级高的任务优先调度,从而使得更多的重要任务得到调度;模糊控制器与任务流调节策略一起构成模糊反馈控制部分.仿真结果表明,模糊反馈控制调度可以很好地控制任务的截止期错失率,解决任务特征可能是模糊不确定或不可预测民政部下的调度问题,提高重要任务的调度成功率.