基于粒子群算法的多核处理器线程调度研究

为有效解决多核处理器的线程调度问题,提出了一种基于粒子群算法框架上的线程调度算法.该算法依据设计的调度模型,在线程DAG图上通过复制不在同一处理器上且存在相关性的线程,生成相互独立的子DAG图,并采用改进的粒子群优化算法对其进行合理调度,由此提高线程调度效率.仿真实现了该算法,并通过实验数据验证了该算法的优越性.     

基于遗传蚁群算法的CMP线程调度方法

为提高多核处理器系统的调度效率,充分发挥多核处理器的性能,提出了一种新的线程调度算法。该方法利用遗传算法的快速随机全局搜索能力,生成蚁群算法所需的信息素分布,利用蚁群算法的正反馈性,并将其应用到CMP的线程调度中,以提高线程调度的效率。通过两种算法的结合,弥补了遗传算法随着求解范围增大而效率降低,蚁群算法需要信息素浓度的增加才能提高效率的不足,更好地发挥它们的优势,提升求解速度。实验结果表明,该算法能够很好地降低任务的执行时间,充分发挥多核处理器系统的优势。     

云环境中基于混合多目标粒子群的科学工作流调度算法

为了更高效地实现科学工作流任务的调度,研究了云环境中的工作流调度多目标优化问题,提出了一种基于非占优排序的混合多目标粒子群优化的工作流调度算法HPSO。首先,建立了截止时间与预算约束下工作流调度的多目标优化模型,模型引入三目标最优化,包括工作流执行跨度、执行代价及执行能耗;其次,设计了一种混合粒子群算法对相互冲突的三目标最优化进行求解,算法通过非占优排序的形式可以得到满足Pareto最优的工作流调度解集合;最后,通过3种科学工作流案例的仿真实验,与同类多目标调度算法NSGA-II,MOPSO和ε-Fuzzy进行了性能比较。实验结果表明,HPSO得到的调度解不仅收敛性更好,而且调度解的空间分布更加一致,更符合云环境中的工作流调度优化。     

融合遗传和粒子群算法的云工作流调度算法

针对云工作流调度问题,提出一种融合遗传算法和粒子群优化算法的工作流调度负载均衡算法.充分利用多元启发式方法融合的优势,避免遗传算法的收敛过慢和粒子群算法易于陷入局部最优的缺陷,有效将工作流任务映射至虚拟机资源,实现全局工作流执行跨度最小化和虚拟机分配的负载均衡.以算例详细说明算法实现思路,在现实科学工作流条件下进行仿真测试,验证算法性能.与几种单一元启发式调度方法相比,验证该算法拥有更高执行效率和负载均衡度.     

一种混合粒子群与蚁群算法在多处理机调度中的应用研究

提出了一种基于蚁群优化和粒子群优化的混合算法以解决多处理机调度问题。这种混合算法利用蚁群算法和粒子群优化算法的特性,可以显著提高计算效率,具有较大的实用价值。     

模糊云资源调度问题的RIOPSO算法

针对时间-成本约束下的云资源调度问题,使用三角模糊数表示不确定的任务执行时间,建立了模糊云资源调度模型,调度的目标是降低任务总的执行时间和总的成本消耗,决策变量是任务和虚拟机的映射关系.使用混合粒子群优化算法(RIOPSO)对模糊云资源调度进行求解.该算法使用了正交初始化粒子群的方法,提升粒子初始探索最优调度方案的质量,在粒子搜索过程中使用重新随机化控制粒子的搜索范围,使用实时更新惯性权重的方式控制粒子在搜索中的速度,从而得到最优的调度方案.在Cloudsim仿真平台上使用随机生成的仿真数据,对提出的问题模型和优化算法进行验证,证明了模型的可靠性,实验结果表明使用提出的优化算法,可以达到使云资源调度中总执行时间和总执行成本降低的目的,并且在收敛速度、求解能力方面具有良好的性能.     

基于自适应线程束的GPU并行粒子群优化算法

基于统一计算设备架构（CUDA）对图形处理器（GPU）下的并行粒子群优化（PSO）算法作改进研究。根据CUDA的硬件体系结构特点,可知Block是串行执行的,线程束（Warp）才是流多处理器（SM）调度和执行的基本单位。为了充分利用Block中线程的并行性,提出基于自适应线程束的GPU并行PSO算法：将粒子的维度和线程相对应;利用GPU的Warp级并行,根据维度的不同自适应地将每个粒子与一个或多个Warp相对应;自适应地将一个或多个粒子与每个Block相对应。与已有的粗粒度并行方法（将每个粒子和线程相对应）以及细粒度并行方法（将每个粒子和Block相对应）进行了对比分析,实验结果表明,所提出的并行方法相对前两种并行方法,CPU加速比最多提高了40。     

改进混合粒子群算法的立体车库存取调度

为了进一步提高立体车库存取效率，提出一种改进混合粒子群算法，应用于立体车库存取策略时间模型，寻找存取车最优时间和最优排序。该算法主要在粒子群算法前期引入遗传算法，改善全局搜索能力，后期引入模拟退火算法弥补其局部搜索能力弱的特点。与目前应用于立体车库存取车调度的遗传算法相比，改进混合粒子群算法存取效率提高了24.5%~36.07%，并优于其他车库调度算法，提高了车库运营效率。     

基于混合粒子群算法的网格任务调度

减少分布式程序的执行时间是网格调度系统需要解决的重要问题。因分布式程序常建模为DAG图,故该问题又称异构DAG调度问题。在研究网格环境下的任务调度的基础上,提出了一种用于解决DAG任务调度问题的通用混合粒子群优化算法(Common Hybrid Particle Swarm Optimization),简称为CHPSO。该算法将问题的解(粒子)表示为任务的调度优先权向量,采用混合粒子群优化算法探索解空间。实验结果表明,在求解不含孤立点的单个DAG调度问题时,该算法所得解的调度长度仅为HEFT的90%～92%,求解质量与PSGA相当;在多张DAG图(含孤立节点)并发执行的网格环境中,该算法的调度性能明显优于PSGA及文中列出的其它演化计算方法。     

柔性制造系统的改进粒子群无死锁调度算法

基于柔性制造系统的Petri网模型,以制造期最小为优化目标,将死锁避免策略嵌入粒子群算法中,提出一种无死锁改进粒子群调度算法.该算法将粒子与工件的工序序列相对应,以位置数值的大小表示对应工件工序在执行顺序中的优先级.采用一步向前看的死锁避免策略方法对序列的可行性进行验证,提出一种跳出局部极值的策略.实例仿真结果表明了粒子群调度算法的可行性和有效性,以及改进粒子群调度算法的优越性.     

A non-preemptive scheduling algorithm for soft real-time systems

Real-time systems are often designed using preemptive scheduling and worst-case execution time estimates to guarantee the execution of high priority tasks. There is, however, an interest in exploring non-preemptive scheduling models for real-time systems, particularly for soft real-time multimedia applications. In this paper, we propose a new algorithm that uses multiple scheduling strategies for efficient non-preemptive scheduling of tasks. Our goal is to improve the success ratio of the well-known Earliest Deadline First (EDF) approach when the load on the system is very high and to improve the overall performance in both underloaded and overloaded conditions. Our approach, known as group-EDF (gEDF) is based on dynamic grouping of tasks with deadlines that are very close to each other, and using Shortest Job First (SJF) technique to schedule tasks within the group. We will present results comparing gEDF with other real-time algorithms including, EDF, Best-effort, and Guarantee, by using randomly generated tasks with varying execution times, release times, deadlines and tolerance to missing deadlines, under varying workloads. We believe that grouping tasks dynamically with similar deadlines and utilizing a secondary criteria, such as minimizing the total execution time (or other metrics such as power or resource availability) for scheduling tasks within a group, can lead to new and more efficient real-time scheduling algorithms.     

信号实时采集系统的最佳并行线程数的研究

为解决多核环境下,信号采集系统的数据处理实时性问题,提高波形数据采集和数据显示速度,提出使用裸线程构建数据采集模块和数据处理模块的最佳线程分配数量的最优线程分配算法,其目的在于合理分配线程给各个模块,达到系统的最佳性能。该算法基于生产者-消费者模式、操作系统多线程时间片轮转调度策略,根据各模块的工作量酌情调节线程比例,使应用程序达到最高加速比。实验表明,在双核环境下,该最佳线程数算法计算出最佳线程组合,使采集波形数据和数据显示合理并行化,相对于其他的线程组合分配方式完成程序花费的时间更少,提高了系统加速比、运算性能以及实时性。通过最优线程分配算法,提供了最优的线程数量分配方案,提高并行程序执行效率,减少了不必要的线程开销,提高了波形信号采集实时性。     

非对称多核处理器上的操作系统集成调度

相对于对称多核处理器,非对称多核处理器具有更高的效能,将成为未来并行操作系统中的主流体系结构.对于非对称多核处理器上操作系统的并行任务调度问题,现有的研究假设所有核心频率恒定,缺乏理论分析,也没有考虑算法的效能和通用性.针对该问题,该文首先建立非线性规划模型,分析得出全面考虑并行任务同步特性、核心非对称性以及核心负载的调度原则.然后,基于调度原则提出一个集成调度算法,该算法通过集成线程调度和动态电压频率调整来提高效能,并通过参数调整机制实现了算法的通用性.提出的算法是第一个在非对称多核处理器上结合线程调度和动态电压频率调整的调度算法.实际平台上的实验表明:该算法可适用于多种环境,且效能比其他同类算法高24%～50%.     

基于优先级的访存调度算法研究

文章研究了存储控制器中的访存调度策略,提出了基于优先级的访存调度算法。首先使用遗传算法建立有效的数据源,然后对得到数据源应用统计进行调度优先级挖掘,共获取三个优先级别,这样仅使用这三个优先级构造调度算法进行访存序列调度。实验结果表明,提出的算法很好地降低了访存序列的运行时间,优化效果接近于文献[4]中提出的贪婪访存调度算法,但算法运行时间却远小于后者。     

一种双匹配动态调度算法

提出了适于异构环境独立任务调度的双匹配动态调度算法（BM算法）．BM算法将任务与处理机实现双匹配，使大部分任务在执行时间最短而且完成时间最早的处理机上执行．对于无法实现双匹配的任务，采用最早完成时间最小者优先的策略进行调度．BM算法可以同时满足负载均衡和高吞吐率两个目标．BM算法与通常用作评测基准的Min-min算法的比较结果表明，BM算法的运行时间远少于Min-min算法，其调度跨度比Min-min算法减少约9％．     

基于池技术的高效N层Web应用体系研究

对线程、内存、数据连接等宝贵资源的低效使用已成为B/S体系结构应用软件的主要性能瓶颈。而池技术正是解决这一问题的有效途径。介绍了基于池技术扩展而来的线程池、实例池、连接池的基本原理,阐述了如何将其运用于N层构架体系中相应层,优化整体的系统性能,并对存在的问题提出了改进算法。最后针对现有的池中突发的资源管理调度方法的不足,提出了基于最高效益的调度算法。     

军事网格工作流调度算法研究

针对军事网格应用及工作流的特点,提出一种基于网格工作流分割的调度算法。采用基于有向无环图的工作流建模方法,对网格工作流的相关概念进行形式化定义。在确定基本工作流之间的复合关系后,对网格工作流中的任务实施调度。实例结果表明,该算法能减少网格工作流的任务执行时间,具有较好的调度性能。     

云环境下基于强化学习的多目标任务调度算法

针对云计算环境下的多目标任务调度问题,提出一种新的基于Q学习的多目标优化任务调度算法(Multi-objective Task Scheduling Algorithm based on Q-learning,QM TS).该算法的主要思想是:首先,在任务排序阶段利用Q-learning算法中的自学习过程得到更加合理的任务序列;然后,在虚拟机分配阶段使用线性加权法综合考虑任务最早完成时间和计算节点的计算成本,达到同时优化多目标问题的目的;最后,以产生更小的makespan和总成本为目标函数对任务进行调度,得到任务完成后的实验结果.实验结果表明,QMTS算法在使用Q-learning对任务进行排序后可以得到比HEFT算法更小的makespan;并且根据优化多目标调度策略在任务执行过程中减少了makespan和总成本,是一种有效的多目标优化任务调度算法.     

基于延迟调度策略的Reduce调度优化算法

在大规模的Hadoop集群中,良好的任务调度策略对提高数据本地性、减小网络传输开销、减少作业执行时间以及提高集群的作业吞吐量都有着重要的影响。本文针对Hadoop架构中Reduce任务的数据本地性较低问题,提出了一种基于延迟调度策略的Reduce任务调度优化算法,通过提高Reduce任务的数据本地性来减少作业执行时间以及提高作业吞吐量,该算法在Hadoop架构的Early Shuffle阶段,使用多级延迟调度策略来提高Reduce任务的数据本地性。最后重写原生公平调度器代码实现了该调度算法,并与原生公平调度器进行了对比实验分析,实验结果表明该算法明显减少了作业执行时间,提高了集群的作业吞吐量。     

一种针对结构化并行控制机制的任务调度算法

缩短程序的执行时间是并行处理的首要目标,有效的任务分配算法是实现这一目标的关键,对机群系统来说更是如此.研究机群系统上针对结构化并行控制机制的任务调度问题,并基于贪心算法、粒度控制、反馈式分派的原则,提出近优的任务调度算法SSA(sub-optimal scheduling algorithm).实验结果表明,在机群环境下,该算法的并行计算性能与其他算法相比均有所提高.