高实时性异构多核处理器任务调度算法

在异构多核处理器条件下,Min-Min算法调度性能较好但在系统实时响应方面存在不足。最小空闲时间优先调度算法(LSF)、最早截止时间优先调度算法(EDF)和最大价值优先调度算法(HVF)虽然在系统任务调度响应实时性方面表现优异,但却不适用于异构多核处理器环境。为此,提出一种高实时性任务调度算法HRSA。在Min-Min调度算法的基础上融合LSF,EDF,HVF算法的调度策略,将任务能耗、任务完成价值和任务响应比相结合,在实现异构多核处理器任务动态调度的同时缩短系统对高实时性任务的响应时间。实验结果表明,相对于EDF算法和Min-Min算法,HRSA算法消耗单位能量所带来的价值较高,对高实时性任务处理的响应时间较短。     

S-Bridge:性能非对称多核处理器下负载均衡代理机制

近年来,在移动计算环境中,异构多核处理器已经逐渐成为主流.与传统同构的处理器设计相比,此类异构多核处理器以更低的功耗成本满足设备的计算需求.但是异构环境下CPU核之间的微架构差异,也为操作系统中的一些基本方法提出了新的挑战.面向性能非对称异构多核环境下调度的负载均衡问题,从系统层面提出了一种负载均衡机制S-Bridge,可以减少处理器微架构差异以及任务执行需求差异对传统负载均衡带来的影响.S-Bridge的主要贡献是从系统层提供了通用的、适配异构性的负载均衡相关接口,使任意调度器都能方便地与异构多核处理器系统进行适配.基于CFS和HMP调度器在ARM平台上进行实验,同时在X86平台上进行S-Bridge通用性的验证,结果表明：S-Bridge可以支持不同真实平台和内核版本的快速实现,平均性能提升超过15%,部分情况下可达65%.     

一种改进的优先级列表任务调度算法

异构多核处理器任务调度是高性能计算领域的重要问题。针对优先级列表调度算法中存在的优先级排序方法失当、调度结果不理想的问题,提出一种改进的优先级列表任务调度算法。该算法对传统优先级列表任务调度中以任务执行时间平均值作为参数的优先级计算方式进行优化,提出一种基于异构核性能差异性、依赖任务特征加权优先级的排序方式。在此基础上,以当前格局下每个任务的向后关键路径执行时间为权值作为任务分配到处理器内核的依据,克服贪心思想在内核选择中带来的局部最优解问题。此外,在任务分配阶段利用任务复制和区间插入技术,缩短任务最早开始时间,提高处理器利用率。实例分析和模拟实验结果表明,该算法可有效降低任务的执行时间,能发挥异构多核处理器优势。     

基于异构感知静态调度与动态迁移的异构多核调度机制

异构多核处理器体系结构可以有效减少功效开销,是处理器发展的趋势,负载不平衡问题会造成处理器执行的不稳定。提出一种基于异构感知的静态调度和动态线程迁移相结合的异构多核调度机制,解决了不同核之间的负载平衡问题,提高了吞吐量。仿真实验通过将此调度机制与静态调度策略（SS）比较,表明该机制提高了异构多核处理器的性能并保证了执行过程的稳定性。     

异构多核下兼顾应用公平性和能耗的调度方法研究

异构多核处理器通常由高性能的大核和低能耗的小核组成,在其上进行合理的线程调度可以有效地提高资源利用率,节省能耗。之前论文提出的大小核上的公平性调度并没有考虑核上有不同频率/电压状态的情况,而现在支持DVFS调节的处理器越来越普遍,因此很有必要将线程间公平度的计算进行扩展和改进。提出在每个核有若干种不同的DVFS状态时异构多核处理器上线程公平度的计算方法,对已有的性能预测模型进行改进,采用自适应算法调整模型中的系数,并在此基础上提出了一种调度策略,维持各线程之间的公平度和处理器功率满足提前设定的阈值,同时选取能效最优化的配置,实现减小应用运行能耗的目的。实验结果表明,与所提出的调度策略相比,采用static、DVFS-only、swap-only三种调度方法时,在总的运行时间几乎相同的情况下,平均要多产生20%以上能耗,对于有些应用甚至达到了50%。     

混合粒子群算法的异构多核处理器间任务调度

针对异构多核处理器间的任务调度问题,为了更好地发挥异构多核处理器间的平台优势,提出一种基于将有关联的且不在同一处理器上的任务进行复制的思想,从而使每个异构多核的处理器能独立执行任务,来减少不同处理器之间的通信开销,并且通过混合粒子群算法(HPSO)来调度异构多核处理器中的任务,避免由于当任意一个异构多核处理器由于任务分配过多而导致计算机不能及时且准确地得出结果.最后实验证明,对比传统的启发式分配方案和常见的遗传算法(GA),基于任务复制思想分配方案和混合粒子群算法(HPSO)具有更好的求解能力,并且可以提供执行时间更少的调度分配方案,具有较好的应用价值.     

基于机器学习的异构感知多核调度方法

异构多核处理器已成为现代嵌入式系统的主流解决方案,而好的在线映射或调度方法对其充分发挥高性能和低功耗的优势起着至关重要的作用。针对异构多核处理系统上的应用程序动态映射和调度问题,提出一种基于机器学习、能快速准确评估程序性能和程序行为阶段变化的检测技术来有效确定重映射时机从而最大化系统性能的映射和调度解决方案。该方案一方面通过合理选择处理核和程序运行时的静态和动态特征来有效感知异构处理所带来的计算能力和工作负载运行行为的差异,从而能够构建更加准确的预测模型;另一方面通过引入阶段检测来尽可能减少在线映射计算的次数,从而能够提供更加高效的调度方案。最后,在SPLASH-2数据集上验证了所提出调度方案的有效性。实验结果表明,与Linux默认的完全公平调度（CFS）方法相比,所提出的方法在系统计算性能方面提高了52%,在CPU资源利用率上提高了9.4%。这表明所提方法在系统计算性能和CPU资源利用率方面具备优良的性能,可以有效提升异构多核系统的应用动态映射和调度效果。     

异构实时多处理器系统的动态调度算法研究

实时多处理器系统的动态调度算法一直是实时系统中的重要研究课题.根据异构实时多处理器的特点,提出了一种新的异构实时动态调度算法P_IEFT.该算法采用了一个新的处理器分配策略——将任务分配到能最早完成任务的处理器上.该策略能够缩短调度长度,提高后继任务被接受的可能性,从而能够提高成功调度率.模拟结果表明,该调度算法的成功调度率高于近视算法和节约算法的成功调度率.     

基于机器学习的异构感知多核调度方法

异构多核处理器已成为现代嵌入式系统的主流解决方案，而好的在线映射或调度方法对其充分发挥高性能和低功耗的优势起着至关重要的作用。针对异构多核处理系统上的应用程序动态映射和调度问题，提出一种基于机器学习、能快速准确评估程序性能和程序行为阶段变化的检测技术来有效确定重映射时机从而最大化系统性能的映射和调度解决方案。该方案一方面通过合理选择处理核和程序运行时的静态和动态特征来有效感知异构处理所带来的计算能力和工作负载运行行为的差异，从而能够构建更加准确的预测模型；另一方面通过引入阶段检测来尽可能减少在线映射计算的次数，从而能够提供更加高效的调度方案。最后，在SPLASH-2数据集上验证了所提出调度方案的有效性。实验结果表明，与Linux默认的完全公平调度（CFS）方法相比，所提出的方法在系统计算性能方面提高了52%，在CPU资源利用率上提高了9.4%。这表明所提方法在系统计算性能和CPU资源利用率方面具备优良的性能，可以有效提升异构多核系统的应用动态映射和调度效果。     

基于缓存层级结构的多核Web服务器动态请求调度算法

针对Web服务器中传统的动态请求调度算法,如先到先服务算法等,不能充分利用多核处理器的并行性的问题,根据多核Web服务器缓存结构的特点提出了基于缓存层级结构的多核Web服务器动态请求调度算法。该算法从处理器核心间的负载均衡和多核处理器的缓存层级结构特点两个方面对动态请求进行调度。基于此算法进行了仿真实验,实验结果表明该算法可保持多核处理器核心间的负载均衡,并能有效缓解多核Web服务器的“乒乓”效应。     

Multi-Dimensional Scheduling for Real-Time Tasks on Heterogeneous Clusters

Multiple performance requirements need to be guaranteed in some real-time applications such as multimedia data processing and real-time signal processing in addition to timing constraints.Unfortunately,most conventional scheduling algorithms only take one or two dimensions of them into account.Motivated by this fact,this paper investigates the problem of providing multiple performance guarantees including timeliness,QoS,throughput,QoS fairness and load balancing for a set of independent tasks by dynamic ...     

Distributed fair DRAM scheduling in network-on-chips architecture

Memory access scheduling is an effective manner to improve performance of Chip Multi-Processors (CMPs) by taking advantage of the timing characteristics of a DRAM. A memory access scheduler can subdivide resources utilization (banks and rows) to increase throughput by accessing different DRAM banks in parallel. However, different threads running on different cores may exhibit different performance. One thread may experience starvation while the others are serviced normally. Therefore, designing a scheduler which reduces the unfairness in the DRAM system, while also improving system throughput on a variety of workloads and systems, is necessary. In this paper, a distributed fair DRAM scheduling for two-dimensional mesh network-on-chips (NoCs), called DFDS, is presented. The key design points in DFDS are: (i) assessing the total waiting cycles of a memory request in NoC and considering it as a metric in arbitration. For this purpose waiting cycles of a memory request are put in an additional flit in a packet and are updated while traversing the NoC, and (ii) proposing a semi-dynamic virtual channel allocation to provide in-order memory requests to memory controllers (MCs). Consequently, we use a simple scheduling algorithm in MCs, instead of complex algorithms. To validate our approach, we apply synthetic and real workload from Parsec benchmark suite. The results show effectiveness of our approach, as we reduce the waiting time of memory requests by up to 15%.     

图书馆多媒体业务流的短时公平分组反馈调度方法

研究了一种新的基于短时公平的分组调度算法的问题. 基于短时公平性的分组反馈调度算法改进了WF2Q＋算法在短期内无法为新加入客户端提供公平服务的缺陷,增强了调度算法的适应性和公平性. 在本算法中,调度器中的各个客户端权值能够根据其获得的实际服务量状况在线调整,增强了系统的鲁棒性和自适应性,同时提高了系统实现短期公平性的能力,对各个客户端提供更为公平的服务质量（Quality of Service,QoS）.     

Analysis of temporal and throughput fair scheduling in multirate WLANs

The IEEE 802.11e Wireless Local Area Network (WLAN) provides controlled access features that can be used in conjunction with scheduling algorithms to provide guaranteed per-session services. However, the multirate operation of the WLAN complicates the design of scheduling and Quality of Service (QoS) provisioning algorithms. We propose a new solution based on Controlled Access Phase Scheduling (CAPS) framework, introduced for fixed rate WLANs in our earlier works, and employ a new fair central scheduler to achieve guaranteed fair services in a WLAN. We examine the fairness issues involved in designing such an algorithm and study several fair scheduling algorithms that can be used with CAPS. We present a modified start time fair queuing based scheduler as our choice and analyze its performance under dynamic and static multirate operation. The algorithm is then evaluated through several simulation experiments. We show that the enhanced CAPS is able to adapt to multirate environments and provide both temporal and throughput fair services in 802.11e WLANs.     

Anchored opportunity queueing: a low-latency scheduler for fair arbitration among virtual channels

Many wormhole interconnection networks for parallel systems, and more recently system area networks, implement virtual channels to provide a number of services including improved link utilization and lower latencies. The forwarding of flits from the virtual channels on to the physical channel is typically accomplished using flit-based round-robin (FBRR) scheduling. This paper presents a novel scheduling strategy, anchored opportunity queueing (AOQ), which preserves the throughput and fairness characteristics of FBRR while significantly reducing the average delay experienced by packets. The AOQ scheduler achieves lower average latencies by trying, as far as possible, to complete the transmission of a complete packet before beginning the transmission of flits from another packet. The AOQ scheduler achieves provable fairness in the number of opportunities it offers to each of the virtual channels for transmissions of flits over the physical channel. We prove this by showing that the relative fairness bound, a popular measure of fairness, is a small finite constant in the case of the AOQ scheduler. Finally, we present simulation results comparing the delay characteristics of AOQ with other schedulers for virtual channels. The AOQ scheduler is simple to implement in hardware, and also offers a practical solution in other contexts such as in scheduling ATM cells in Internet backbone switches.     

Partition oriented frame based fair scheduler

Proportionate fair schedulers provide an effective methodology for scheduling recurrent real-time tasks on multiprocessors. However, a drawback in these schedulers is that they ignore a task’s affinity towards the processor where it was executed last, causing frequent inter-processor task migrations which ultimately results in increased execution times. This paper presents Partition Oriented Frame Based Fair Scheduler (POFBFS), an efficient proportional fair scheduler for periodic firm and soft real-time tasks that ensures a bounded number of task migrations. Experimental results reveal that POFBFS can achieve 3 to 100 times reduction in the number of migrations suffered with respect to the General-ERfair algorithm (for a set of 25 to 100 tasks running on 2 to 8 processors) while simultaneously maintaining high fairness accuracy.     

Job scheduling in mesh multicomputers

A new approach for dynamic job scheduling in mesh-connected multiprocessor systems, which supports a multiuser environment, is proposed in this paper. Our approach combines a submesh reservation policy with a priority-based scheduling policy to obtain high performance in terms of high throughput, high utilization, and low turn-around times for jobs. This high performance is achieved at the expense of scheduling jobs in a strictly fair, FCFS fashion; in fact, the algorithm is parameterized to allow trade-offs between performance and (short-term) POPS fairness. The proposed scheduler can be used with any submesh allocation policy. A fast and efficient implementation of the proposed scheduler has also been presented. The performance of the proposed scheme has been compared with the FCFS policy, the only existing scheduling strategy for meshes, to demonstrate the effectiveness of the proposed approach. Simulation results indicate that our scheduling strategy outperforms the FCFS policy significantly. Specifically, our strategy significantly reduces the average waiting delay of jobs over the FCFS policy. The fast implementation of the proposed scheduler results in low allocation and deallocation time overhead, as well as low space overhead     

基于任务分类的虚拟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%,并且保证了整个系统的资源共享公平性。     

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

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

Design, Analysis, and Implementation of a Novel Low Complexity Scheduler for Joint Resource Allocation

Over the past decade, the problem of fair bandwidth allocation among contending traffic flows on a link has been extensively researched. However, as these flows traverse a computer network, they share different kinds of resources (e.g., links, buffers, router CPU). The ultimate goal should hence be overall fairness in the allocation of multiple resources rather than a specific resource. Moreover, conventional resource scheduling algorithms depend strongly upon the assumption of prior knowledge of network parameters and cannot handle variations or lack of information about these parameters. In this paper, we present a novel scheduler called the composite bandwidth and CPU scheduler (CBCS), which jointly allocates the fair share of the link bandwidth as well as processing resource to all competing flows. CBCS also uses a simple and adaptive online prediction scheme for reliably estimating the processing times of the incoming data packets. Analytically, we prove that CBCS is efficient, with a per-packet work complexity of O(1). Finally, we present simulation results and experimental outcomes from a real-world implementation of CBCS on an Intel IXP 2400 network processor. Our results highlight the improved performance achieved by CBCS and demonstrate the ease with which it can be implemented on off-the-shelf hardware