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

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

编程型游戏的线程调度模型设计与实现

编程型游戏采用多线程技术实现对角色控制程序的执行和调度。阐述了编程型游戏的线程调度模型和基于.NET框架的实现技术,包括协作多线程调度模型、调度线程的算法、基于AutoResetEvent的线程同步技术、角色控制程序的基本结构和线程管理模块的构成。测试结果表明,采用所述线程调度模型和技术的线程管理模块能够对角色线程进行有序调度,性能良好。     

冗余多线程结构的重命名寄存器配对共享分配策略

同时多线程处理器允许多个线程同时执行,一方面提高了处理器的性能,另一方面也为通过线程冗余执行来容错提供了支持.冗余多线程结构将线程复制成两份,二者独立执行,并比较结果,从而实现检错或者容错.冗余多线程结构主要采用ICOUNT调度策略来解决线程间资源共享问题.然而这种策略有可能造成"饥饿"现象,并降低处理器吞吐率.提出一...     

嵌入式系统的细粒度多处理器实时抢占式调度算法

现有的嵌入式实时系统调度算法一般以任务级为调度单位,对此提出一种细粒度的线程级多处理器实时调度算法。采用DAG图描述实时系统的任务,并采用任务分解法将其分解为线程形式;为任务级调度采用基于干扰的可调度性分析,为线程级调度采用基于工作负载的可调度性分析;将线程的偏移、截止期与优先级作为三个调度目标,设计混合线程级调度算法。仿真实验结果表明,算法对于多线程任务的实时系统具有较好的性能。     

基于混合粒子群优化的CMP线程调度方法

为提高片上多核处理器(CMP)架构中线程调度的执行效率,发挥CMP的并行性能,提出一种基于混合粒子群优化算法的线程调度方法.根据设计的线程调度模型,利用有向无环图表述线程及线程间的相互依赖关系,并采用改进的混合粒子群算法对其进行合理调度.实验结果表明,该方法的执行效率优于现有的遗传算法,能有效地降低任务的执行时间,充分发挥多核架构的优势.     

缓解同时多线程结构中线程对关键资源的竞争

同时多线程处理器同时执行来自不同线程的指令,兼顾了线程内和线程间的指令并行,使处理器的性能得以大幅提升。然而这种对资源的共享方式,可能带来对关键资源(包括重命名寄存器、指令队列等)的恶性竞争,从而出现饿死现象,甚至影响处理器的吞吐率。这主要是由于某些线程遇到长延迟指令,并长期占据关键资源,从而导致其他线程对资源的需求无法得到满足,同时这也降低了资源的利用率。降低竞争带来的负面影响,主要有3种方法:线程调度——在取指段,决定从哪些线程取指令;指令调度——决定哪些指令进入关键资源;关键资源划分——为每个线程分配独立的关键资源。主要对这些调度策略进行综述。     

基于Java多线程的演示程序设计

介绍了用Java多线程开发的一个操作系统演示程序,该程序动态演示操作系统中多线程的调度过程.学生通过该演示程序更直观地了解线程的调度原理,加深对线程概念的理解.     

基于线程流水线的多核线程调度策略

针对多核环境中操作系统的线程调度问题,提出一种基于线程流水线的线程调度策略。基于片上多线程处理器,借鉴流水线技术的并行优势,引入线程流水线的概念。通过确定线程特征指标,计算线程流水线的聚合度及对应线程的吻合度,从而完成线程调度,并在此基础上对其进行嵌入式方向的优化。模拟真实环境的实验结果表明,与基于静态优先级的调度策略相比,该策略消耗时间较少。     

Windoiws 2000/XP的线程调度

Windows2000／XP的处理器调度的调度对象是线程,本文剖析了Windows2000／XP线程的调度特征、优先级、时间配额及调度策略。     

分布式实时嵌入式系统任务调度研究

本文把分布式系统调度分为全局调度和本地调度两个调度层次；为了满足实时性能。把线程分为非时间片线程以及时间片线程两类。本文同时指出了分布式嵌入操作系统的任务调度略。同时在Linux开放代码的基础上修改Linux内核的调度策略，初步实现了分布式实时调度策略并进行了测试。     

Lesser Bear: A lightweight process library for SMP computers—scheduling mechanism without a lock operation

We have designed and implemented a lightweight process (thread) library called ‘Lesser Bear’ for SMP computers. Lesser Bear has thread‐level parallelism and high portability. Lesser Bear executes threads in parallel by creating UNIX processes as virtual processors and a memory‐mapped file as a huge shared‐memory space. To schedule thread in parallel, the shared‐memory space has been divided into working spaces for each virtual processor, and a ready queue has been distributed. However the previous version of Lesser Bear sometimes requires a lock operation for dequeueing. We therefore proposed a scheduling mechanism that does not require a lock operation. To achieve this, each divided space forms a link topology through the queues, and we use a lock‐free algorithm for the queue operation. This mechanism is applied to Lesser Bear and evaluated by experimental results. Copyright © 2002 John Wiley & Sons, Ltd.     

Lesser Bear—a light‐weight process library for SMP computers

We have designed and implemented a light‐weight process (thread) library called ‘Lesser Bear’ for SMP computers. Lesser Bear has high portability and thread‐level parallelism. Creating UNIX processes as virtual processors and a memory‐mapped file as a huge shared‐memory space enables Lesser Bear to execute threads in parallel. Lesser Bear requires exclusive operation between peer virtual processors, and treats a shared‐memory space as a critical section for synchronization of threads. Therefore, thread functions of the previous Lesser Bear are serialized. In this paper, we present a scheduling mechanism to execute thread functions in parallel. In the design of the proposed mechanism, we divide the entire shared‐memory space into partial spaces for virtual processors, and prepare two queues (Protect Queue and Waiver Queue) for each partial space. We adopt an algorithm in which lock operations are not necessary for enqueueing. This algorithm allows us to propose a scheduling mechanism that can reduce the scheduling overhead. The mechanism is applied to Lesser Bear and evaluated by experimental results. Copyright © 2001 John Wiley & Sons, Ltd.     

一种不影响任务集合可调度性的优先级映射算法

采用静态优先级调度的实时系统中,当任务个数多于优先级个数时,只能给多个任务分配相同的优先级·现有分配算法增大了高优先级任务的最坏情况响应时间,可能造成任务集合不可调度·利用抢占阈值的调度算法,能在提高任务集合可调度性的同时,使用较少的线程·但所用优先级个数没有减少·提出了一种优先级映射算法———阈值段间映射法(threshold segment mapping,TSM),以及与之配合的事件驱动线程框架·证明了TSM是严格排序的·仿真结果表明,在保证任务集合可调度的前提下,TSM使用了比现有映射算法更少的优先级·     

Scheduling Threads for Low Space Requirement and Good Locality

The running time and memory requirement of a parallel program with dynamic, lightweight threads depends heavily on the underlying thread scheduler. In this paper we present a new asynchronous, space-efficient scheduling algorithm for shared memory machines that combines the low scheduling overheads and good locality of work stealing with the low space requirements of depth-first schedulers. For a nested-parallel program with depth D and serial space requirement S ₁ , we show that the expected space requirement is S ₁ + O(K⋅ p⋅ D) on p processors. Here, K is a user-adjustable runtime parameter, which provides a tradeoff between running time and space requirement. Our algorithm achieves good locality and low scheduling overheads by automatically increasing the granularity of the work scheduled on each processor. We have implemented the new scheduling algorithm in the context of a native, user-level implementation of Posix standard threads or Pthreads, and evaluated its performance using a set of C-based benchmarks that have dynamic or irregular parallelism. We compare the performance of our scheduler with that of two previous schedulers: the thread library's original scheduler (which uses a FIFO queue), and a provably space-efficient depth-first scheduler. At a fine thread granularity, our scheduler outperforms both these previous schedulers, but requires marginally more memory than the depth-first scheduler. We also present simulation results on synthetic benchmarks to compare our scheduler with space-efficient versions of both a work-stealing scheduler and a depth-first scheduler. The results indicate that unlike these previous approaches, the new algorithm covers a range of scheduling granularities and space requirements, and allows the user to trade the space requirement of a program with the scheduling granularity. Received June 11, 2000, and in revised form March 19, 2001, and in final form August 7, 2001. Online publication April 5, 2002.     

异构计算环境下基于优先队列划分的调度算法

人工智能的飞速发展对高性能计算提出了更高的要求,异构计算环境下任务调度问题一直是高性能计算中的关键问题.本文提出一种基于优先队列划分的调度算法(PQDSA),该算法根据DAG(有向无循环图)任务集的入口节点数量确定优先队列数,通过任务的通信开销和计算开销划分任务队列,进而将关键节点任务分配给合适的队列,以产生效果较佳的任务调度队列,从而提高任务间的并行性,降低任务集的完工时间.与此同时,进一步基于插入策略将任务调度到处理器上,使任务调度更加高效地执行.PQDSA算法可以减少任务间的时间消耗,提高处理器的调度效率.通过与两个经典算法的性能对比,实验结果表明本文提出的PQDSA算法在任务完工时间和调度效率方面都要明显优于对比的算法.     

一种资源优化的双最小均衡Web集群区分服务调度算法

在一种新的Web集群体系结构的基础上,提出了一种资源优化的双最小均衡区分服务调度算法：首先在前端调度器按资源均衡度将Web请求分配到各后台服务器．然后将Web请求的优先级与资源均衡度两个特征参数结合起来,综合设计后台服务器的Web请求调度顺序,为了评估该算法的性能,进行了大量的模拟实验．在与其他著名调度策略如分离式调度的对比结果显示：双最小均衡调度算法使Web请求的效率提高了11％,同时很好地实现了区分服务．证实了资源优化调度策略具有一定的普遍意义．     

一种分布式共享存储系统的线程分配算法

讨论了软件实现了多线程ＤＳＭ 的通信开销和线程分配问题,给出了一种基于线程关系图的调度模型,并在此基础上提出了一种基于迭代的线程分配算法,通过大量的线程关系图对算法进行了评价,并且在一个软件ＤＳＭ系统中实现了该算法,同时给出了算法的评价结果和应用程序的性能数据。     

一种求解输运方程的并行调度算法

高效并行扫描问题是调度问题的子集,调度问题是NP完全问题.针对输运问题的特点,如何按特定的计算次序调度本地网格单元,以保证最佳的计算与通信性能是一个难度很大的问题.文中设计了一种基于局部深度优先的优先级(PDFDS)算法,该算法具有局部性、通信量小、优先级队列好等特点.将PDFDS算法应用到求解二维粒子输运方程的程序中,与现有的调度算法相比,新算法具有更好的并行计算效果,对于大规模计算问题,可以扩展到1024个处理器,相对于64个处理器的并行效率达到了96%.