基于Backfilling调度算法的“扩履适足”改进算法

在众多的并行作业调度算法中,Backfilling通常被广泛认为是有效提高CPU利用率的一种算法。该算法是在FCFS算法的基础上,将队列中较小的作业回填（Backfill）到空闲 CPU,以提高CPU利用率。但是,当空闲CPU数量仍然无法满足Backfilling算法中小作业的回填要求时,系统仍有部分CPU闲置,因而也难以达到更好地提高CPU利用率的目的。 。对于共享内存体系结构的并行计算机系统,本文提出了基于Backfilling算法的“扩履适足”的改进算法。该算法以正在运行的作业的CPU利用率为依据,通过动态调整正在运行作业的CPU数,扩大可供回填（backfill）的CPU空间,使得Backfilling算法无法回填的作业得到运行,弥补了Backfilling算法的不足,大大提高了共享内存体系结构并
并行计算机系统的CPU利用率。     

价值密度—截止期—回填的网格作业调度算法

在商业网格和云计算环境中,作业有到达时间、计算量、预算、截止期等属性,区分作业的重要性和紧迫性是调度系统的关键问题之一。现有的作业优先级只考虑作业的单个或部分属性。综合考虑以上提及的四个属性,定义了基于价值密度和相对截止期的作业优先级,提出了基于价值密度和相对截止期的网格作业调度算法,并结合回填算法(EASY backfilling)来提高资源的利用率。仿真结果显示,基于价值密度和相对截止期的作业优先级很好地体现了作业的重要性和紧迫性;而回填算法在提高资源利用率上对某些优先级策略效果显著,有些则效果不明显。     

基于LT-backfilling算法的集群作业调度系统

在胖节点集群系统中，目前的reservations, backfilling等主流调度算法未能充分考虑单节点过载情况。该文在传统backfilling算法基础上，充分考虑节点当前负载，将预约、回填策略相结合，提出了一种新的LT-backfilling调度算法。设计了基于XML业务流程模板的二层作业调度系统，用户不仅可以提交单个作业，而且可以提交一组具有数据相关性的作业流，使得作业调度系统更加实用化。 LT-backfilling；负载均衡；作业调度；XML；作业流     

RB-FIFT--一种结合Firstfit及预约回填策略的机群作业调度算法

机群作业管理是机群系统软件的重要组成部分,作业调度策略则是机群作业管理系统的核心．作业调度策略的选择不仅关系到机群系统的效率,还影响了用户作业的响应时间．目前,Firstfit调度算法已经相当成熟并且广泛应用于机群作业调度．传统的Firstfit算法虽然着眼于减少资源碎片,但未能解决作业饥饿问题．曙光超级服务器作业管理系统JMS改进了既有的结合Firstfit和优先级的作业调度算法P-FIFT,将预约和回填策略与Firstfit相结合,引入了新的RB-FIFT调度策略．实验结果表明,与传统Firstfit算法及P—FIFT算法比较,RB-FIFT调度策略不但能够消除系统中作业的饥饿现象,而且大大减少了资源碎片,提高了系统的吞吐率和资源利用率．     

一种简化的基于First-Fit的Backfilling调度策略——RB-FIFT

机群作业管理系统是机群系统的重要组成部分,而作业调度策略又是机群作业管理系统的核心内容。作业调度策略的选择不仅关系到机群系统的利用率,还决定用户作业的响应速度和平均执行时间。在节点分配基于空间共享策略(Space-Sharing)的机群系统中,传统的基于先来先服务的First-Fit调度策略虽然能够提高机群系统的利用率,却容易引起饥饿问题。文章基于传统的先来先服务的调度策略,提出了一种简化的Backfilling算法,简要叙述了该算法的设计和实现,最后根据模拟实验结果,从用户和系统的角度分析了该算法的性能。     

基于改进ESLA算法的可重构资源管理

针对动态可重构系统的空闲资源管理问题,改进基于最大空闲矩形的增强型扫描线算法(ESLA),采用一维数组作为辅助空间,同时搜索有效宽度与最大空闲矩形。改进算法能快速计算出可重构系统在运行过程中的所有最大空闲矩形,实现任务间资源的合理分配。实验结果表明,改进算法能减少运行时间开销和存储空间代价,提高可重构系统的资源利用率。     

基于CPU因子影响的二次调度算法

在航天器型号设计阶段需要利用高性能计算系统开展大量的仿真分析工作,昂贵的许可证资源使用极其紧张,作业计算效率低.针对高性能计算系统中现有作业派发机制未动态考虑高性能运算主机空闲状态的缺陷和不足开展研究,基于资源调度软件Platform LSF,结合航天器仿真分析特点,提出一种新的思路,设计并实现一种新的基于CPU因子（CPU Factor）影响的二次调度算法,CPU因子用于区分不同机器的相对运行速度,仿真结果表明算法能够有效提升作业计算效率,缩短许可证资源占用时间.实际案例说明算法具备推广应用的可能,一定程度的提高了许可证资源利用率,满足了航天器仿真分析过程中对于成本控制和资源精益化利用的实际需求.     

一种新型的实时调度算法

在嵌入式系统中,系统的实时性很大程度上取决于任务调度策略.对如何提高系统实时性的研究已经成为该领域的一大热点.文中针对传统的忽略了作业所能承受的等待时间的能力仅以等待时间的长短而来衡量优先级的先来先服务(FCFS)算法,和仅以任务的周期长短来设置优先级而导致那些周期长但急需要执行的任务无法被调度的速率单调(RM)算法的缺陷,提出一种新的动态设置优先级的方法-剩余时间法.该方法以任务的等待时间和周期共同来决定优先级.通过分析和实验表明该方法兼具RM和FCFS的优点.它不仅考虑到短周期任务应优先执行,而且同时也把任务等待时间作为评价优先级的重要因素,实验结果证实了该方法能更有效地提高实时任务的完成率和CPU的利用率.     

基于等待时间的多任务调度算法的研究与设计

文章介绍了几种常见的操作系统多任务调度算法,针对安防警报的任务特点,提出等待时间的多任务调度算法。该方法保证了高优先级的任务有充足的CPU运行时间,同时也不会让其他任务一直得不到运行而产生饥饿现象,满足安防警报系统任务调度的要求。     

GA-Sim:一种基于分类和实例学习相结合的作业运行时间预测算法

在高性能计算作业调度系统中,许多调度算法依赖于对作业运行时间的准确估计,尤其是以EASY为代表的回填算法,而使用用户提供的作业运行时间往往会降低调度性能。提出了一种基于分类和实例学习相结合的作业运行时间预测算法--GA-Sim,该算法在考虑预测准确性的同时考虑了低估问题。在两个实际调度日志上的数值实验结果表明,相较于IRPA和TRIP算法,GA-Sim在取得更高预测精度的同时降低了低估率。 对数值实验结果进行了深入分析,并给出了不同情形下选择恰当预测算法的建议。     

Backfilling with lookahead to optimize the packing of parallel jobs

The utilization of parallel computers depends on how jobs are packed together: if the jobs are not packed tightly, resources are lost due to fragmentation. The problem is that the goal of high utilization may conflict with goals of fairness or even progress for all jobs. The common solution is to use backfilling, which combines a reservation for the first job in the interest of progress with packing of later jobs to fill in holes and increase utilization. However, backfilling considers the queued jobs one at a time, and thus might miss better packing opportunities. We propose the use of dynamic programming to find the best packing possible given the current composition of the queue, thus maximizing the utilization on every scheduling step. Simulations of this algorithm, called lookahead optimizing scheduler (LOS), using trace files from several IBM SP parallel systems, show that LOS indeed improves utilization, and thereby reduces the mean response time and mean slowdown of all jobs. Moreover, it is actually possible to limit the lookahead depth to about 50 jobs and still achieve essentially the same results. Finally, we experimented with selecting among alternative sets of jobs that achieve the same utilization. Surprising results indicate that choosing the set at the head of the queue does not necessarily guarantee best performance. Instead, repeatedly selecting the set with the maximal overall expected slowdown boosts performance when compared to all other alternatives checked.     

基于任务分类的虚拟CPU调度模型

为了桥接语义鸿沟,提升I/O性能,需要对执行不同类型负载的虚拟CPU（vCPU）采取不同的调度策略,故而虚拟CPU调度算法亟需优化。基于KVM虚拟化平台提出一种基于任务分类的虚拟CPU调度模型STC（virtual CPU scheduler based on task classification）,它将虚拟CPU（vCPU）和物理CPU分别分为两个类型,分别为short vCPU和long vCPU,以及short CPU 和long CPU,不同类型的vCPU分配至对应类型的物理CPU上执行。同时,基于机器学习理论,STC构建分类器,通过提取任务行为特征将任务分为两类,I/O密集型的任务分配至short vCPU上,而计算密集型任务则分配至long vCPU上。STC在保证计算性能的基础上,提高了I/O的响应速度。实验结果表明,STC与系统默认的CFS相比,网络延时降低18%,网络吞吐率提高17%~25%,并且保证了整个系统的资源共享公平性。     

基于反馈控制的实时调度算法设计与实现

传统的实时调度算法在运行环境不可预测的嵌入式操作系统中应用时,要求系统预留大量的CPU资源,而且在稳定性和精确性等方面存在不足.文章为解决这些问题提出了基于反馈控制的实时调度算法,仿真表明该算法相对传统算法而言,提高了系统的CPU利用率,并降低了任务的截止期限错过率.     

Priority scheduling with consolidation based backfilling algorithm in cloud

In cloud computing, scheduling plays an eminent role while processing enormous jobs. The paralle jobs utmost need parallel processing capabilities which leads to CPU underutilization mainly due to synchronization and communication among parallel processes. Researchers introduced several algorithms for scheduleing parallel jobs namely, Conservative Migration Consolidation supported Backfilling (CMCBF) and Aggressive Migration Consolidation supported Backfilling (AMCBF). The greatest challenge of a existing scheduling algorithm is to improve the data center utilization without affecting job responsiveness. Hence, this work proposes an Effective Multiphase Scheduling Approach (EMSA) to process the jobs. In EMSA, the jobs are initially preprocessed and batched together to avoid starvation and to mitigate unwanted delay. Later, an Associate Priority Method has been proposed which prioritizes the batch jobs to minimize the number of migrations. Finally, the prioritized jobs are scheduled using Priority Scheduling with BackFilling algorithm to utilize the intermediate idle nodes. Moreover, the virtualization technology partitions the computing capacity of the Virtual Machine (VM) into two-tier VM as foreground VM (FVM) and Background VM (BVM) to improve node utilization. Hence, Priority Scheduling with Consolidation based BackFilling algorithm has been deployed in a two-tier VM that processes the jobs by utilizing the VMs effectively. Experimental results show that the performance of the proposed work performs better than other existing algorithms by increasing the resource utilization by 8%.     

具有空闲时间的云制造作业车间调度方法

针对云制造企业的剩余能力利用问题,研究具有空闲时间的车间调度方法.构建云制造作业车间的调度框架,以最小化工期为目标,考虑设备空闲时间,提出工序加工时间序列的确定方法和空闲时间段的更新策略,采用基于工件的精简编码和改进的二阶粒子群算法求解工件最优调度顺序.仿真结果验证了所提出调度方法的可行性.与已有算法的对比分析表明,改进算法具有良好的搜索性能.     

Cell Mapping for Nanohybrid Circuit Architecture Using Genetic Algorithm

Nanoelectronics constructed by nanoscale devices seems promising for the advanced development of integrated circuits (ICs). However, the lack of computer aided design (CAD) tools seriously hinders its development and applications. To investigate the cell mapping task in CAD flow, we present a genetic algorithm (GA) based method for Cmos/nanowire/MOLecular hybrid (CMOL), which is a nanohybrid circuit architecture. By designing several crossover operators and analyzing their performance, an effcient crossover operator is proposed. Combining a mutation operator, a GA based algorithm is presented and tested on the International Symposium on Circuits and Systems (ISCAS) benchmarks. The results show that the proposed method not only can obtain better area utilization and smaller delay, but also can handle larger benchmarks with CPU time improvement compared with the published methods.     

异构系统中的Web服务器软件框架研究

在服务器端加入GPU或MIC等协处理器可以提升性能。但是,传统Web服务器端软件不能充分发挥多核CPU+MIC协处理器异构硬件体系的性能。为解决该问题,针对该硬件体系提出了一种新的Web服务器软件框架。该软件框架基于分阶段事件驱动模型,将部分动态请求调度至MIC协处理器执行,并可在多核CPU和MIC协处理器上并行处理动态请求。同时,通过采用自适应调度算法兼顾了CPU和MIC协处理器间的负载均衡。仿真实验表明,该模型在平均响应时间、吞吐量等方面均优于传统的基于先到先服务(First Come First Served,FCFS)的Web服务器软件模型。     

Resource-efficient utilization of CPU/GPU-based heterogeneous supercomputers for Bayesian phylogenetic inference

Bayesian inference is one of the most important methods for estimating phylogenetic trees in bioinformatics. Due to the potentially huge computational requirements, several parallel algorithms of Bayesian inference have been implemented to run on CPU-based clusters, multicore CPUs, or small clusters of CPUs and GPUs. To the best of our knowledge, however, none of the existing methods is able to simultaneously and fully utilize both CPUs and GPUs for the computations, leaving idle either the CPU part or the GPU part of modern heterogeneous supercomputers. Aiming at an optimized utilization of heterogeneous computing resources, which is a promising hardware architecture for future bioinformatics applications, we present a new hybrid parallel algorithm and implementation of Bayesian phylogenetic inference, which combines MPI, OpenMP, and CUDA programming. The novelty of our algorithm, denoted as oMC³, is its ability of using CPU cores simultaneously with GPUs for the computations, while ensuring a fair work division between the two types of hardware components. We have implemented oMC³ based on MrBayes, which is one of the most popular software packages for Bayesian phylogenetic inference. Numerical experiments show that oMC³ obtains 2.5× speedup over nMC³, which is a cutting-edge GPU implementation of MrBayes, on a single server consisting of two GPUs and sixteen CPU cores. Moreover, oMC³ scales nicely when 128 GPUs and 1536 CPU cores are in use.     

Xen虚拟机的虚拟CPU松弛协同调度方法

目前,Xen虚拟机调度算法均采用独立调度虚拟CPU的方式,而没有考虑虚拟机各虚拟CPU之间的协同调度关系,这会使虚拟机各个虚拟CPU之间产生很大的时钟中断数量偏差等问题,从而导致系统不稳定.为了提高系统的稳定性,基于Credit算法提出了一种比RCS(relaxed co-scheduling)算法更松弛的协同调度算法MRCS(more relaxed co-scheduling).该算法采用非抢占式协同调整方法将各个虚拟CPU相对运行的时间间隔控制在同步时间检测的上限门限值Tmax之内,同时利用同步队列中虚拟CPU优化选择调度方法和Credit算法的虚拟CPU动态迁移方法,能够更加及时地协同处理虚拟CPU,并且保证了各个物理CPU的负载均衡,有效地减少客户操作系统与VMM的环境切换次数,降低了系统开销.实验结果证明该方法不但保证了系统的稳定性,而且使系统性能得到一定程度的提升.虚拟机调度算法不仅影响虚拟机的性能,更会影响虚拟机的稳定性,致力于虚拟机调度算法的研究是一项非常有意义的工作.