一种作业弹性与截止时间感知的作业调度算法

针对采用MapReduce模型的大数据分析作业的调度问题进行深入研究，并分析现有任务调度算法的缺陷，现有算法没有考虑资源分配对于作业截止时间的影响，也未考虑不同类型作业截止时间的敏感性问题。因作业的完成时间随着分配资源的不同而改变，故称之为弹性作业，截止时间敏感性是指不同类型作业对截止时间要求的严格程度不同。针对以上问题，提出一种截止时间感知的弹性作业调度算法（DA）。该算法将作业依据截止时间敏感程度进行分类，在基于作业整体执行时间预测的基础上，通过调控不同的资源分配策略来改变作业完成时间，同时结合用户对于截止时间的需求及作业预执行的收益来提前规划作业的资源分配及调度次序使得整体收益最大化。将算法在仿真拥有210个物理节点的集群中进行实验，实验表明该算法满足了截止时间的限制并使得作业整体收益值平均提高了2.37倍。     

TEMPEST: a new Test EnvironMent for Performance Evaluation of the Scheduling of packeTs

The packet scheduling problem has been deeply studied for lot of years by researchers in the computer science and telecommunications fields as an important solution that decides the order in which packets are sent over a link in order to provide QoS on a network. Recently, the packet scheduling has become again a challenging topic due to the massive use of wireless technologies (e.g. WiFi, LTE, 4G/5G) with which to provide high QoS guarantees is still an open problem. Unfortunately, it is difficult to compare different solutions and actually test them in order to select the most proper packet scheduler for each particular environment. In this paper we present TEMPEST, a new Test EnvironMent for Performance Evaluation of the Scheduling of packeTs, which is a novel tool able to help the research in the packet scheduling field. TEMPEST is able to measure the actual performance of a packet scheduler in several environments, both wired or wireless, like the execution time, QoS metrics and throughput, giving prompt feedback about the quality of the solution studied. The goal of this paper is to present in detail the current features of TEMPEST, showing how it is easy to add, configure, test and evaluate several scheduling solutions in multiple scenarios.     

一类链路调度器的统一随机服务曲线研究

随着基于通信网络的业务应用不断的增加,已有的通信网络因所需负载的业务流种类的增加而需改进或提升服务性能。新设计出来的通信网络需为其所负载的业务数据流提供新的Qos服务保证．这要求寻找某种方法对计算机通信网络中的网络构成单元或其组合进行建模与性能保证分析。通信链路调度器网络构成单元对通信网络所能提供的Qos保证影响尤其突出．基于网络演算对这类通信网络构成单元及其组合进行服务保证分析,首先便是寻找这类网络构成单元的紧致性服务曲线。     

输入队列交换的公平可扩展调度系统

提出了一种基于输入队列交换的公平可扩展网络调度系统FSSA.通过将若干个容量较小的调度器合理连接并使其协同工作,构成多端口大容量网络交换调度系统,解决了单个调度器容量和端口数受集成电路工艺限制的问题.FSSA不仅速度高、规模可扩展而且易于硬件实现.环型连接、管线工作及公平调度技术的采用使FSSA在性能方面得到了进一步优化.仿真结果显示,FSSA的性能可与基于iSLIP、DSRR等算法的单片调度器相比拟,尤其在流量较大时,FSSA的性能明显优于单调度器性能.     

基于多目标优化的复本分布及任务调度算法

为了提高分布式并行服务器的系统效率,并保证数据可用性,提出了基于多目标优化的复本分布及任务调度算法,文章针对分布式并行服务器的特点研究了多目标优化模型,并以此模型为基础设计了复本分布策略和相应的任务调度策略,系统根据任务需求周期性地调整数据复本数量和驻留节点．它不仅保证了数据的可用性要求,而且大幅度减少了所有任务耗费的系统资源．分析和测试表明：在相同条件下完成相同任务,该算法耗费的系统资源小于常用的三模冗余．     

On the efficiency of cautious schedulers for database concurrency control—Why insist on two-phase locking?

Thecautious scheduler, recently proposed for the concurrency control of database systems, never resorts to abortions or rollbacks for the purpose of concurrency control. The comprehensive performance evaluation study among different cautious schedulers and conventional non-cautious schedulers, however, has not yet been attempted. In this paper, we consider five scheduling algorithms and investigate their performance by means of simulation studies. Two of these algorithms are non-cautious; that is, thetwo-phase locking algorithm (2PL) (the most popular transaction scheduling algorithm in practical systems) and theconflict serializable algorithm (CSR) (a typical scheduling algorithm among those not using a locking mechanism; also calledD-serializable algorithm, conflict preserving serializable algorithm, orWW-serializable algorithm). The others are cautious scheduling algorithms modified from the above2PL andCSR; that is,cautious two-phase locking algorithm (C2PL), exclusive preclaimed two-phase locking algorithm (EP2PL), andcautious conflict serializable algoritm (CCSR). The results demonstrate the superiority of the cautious conflict serializable algorithm over the conventional two-phase locking algorithm, especially in the on-line system environment.This work was supported in part by the Ministry of Education, Science and Culture of Japan under Scientific Research Grant-in-Aid and in part by the Advancd Systems Foundations of British Columbia, Canada.     

Putting it all together – Formal verification of the VAMP

In the verified architecture microprocessor (VAMP) project we have designed, functionally verified, and synthesized a processor with full DLX instruction set, delayed branch, Tomasulo scheduler, maskable nested precise interrupts, pipelined fully IEEE compatible dual precision floating point unit with variable latency, and separate instruction and data caches. The verification has been carried out in the theorem proving system PVS. The processor has been implemented on a Xilinx FPGA. A shorter version of this article with the title “Instantiating uninterpreted functional units and memory system: functional verification of the VAMP” appeared in [8]. The work reported here was done while all the authors were with Saarland University.     

Analysis of Distributed DDQ for QoS Router

In a packet switching network, congestion is unavoidable and affects the quality of real‐time traffic with such problems as delay and packet loss. Packet fair queuing (PFQ) algorithms are well‐known solutions for quality‐of‐service (QoS) guarantee by packet scheduling. Our approach is different from previous algorithms in that it uses hardware time achieved by sampling a counter triggered by a periodic clock signal. This clock signal can be provided to all the modules of a routing system to get synchronization. In this architecture, a variant of the PFQ algorithm, called digitized delay queuing (DDQ), can be distributed on many line interface modules. We derive the delay bounds in a single processor system and in a distributed architecture. The definition of traffic contribution improves the simplicity of the mathematical models. The effect of different time between modules in a distributed architecture is the key idea for understanding the delay behavior of a routing system. The number of bins required for the DDQ algorithm is also derived to make the system configuration clear. The analytical models developed in this paper form the basis of improvement and application to a combined input and output queuing (CIOQ) router architecture for a higher speed QoS network.     

提高用户满意率的服务器主动调度算法

在集群环境中,为了实现多台计算机协同工作,充分利用服务器的计算能力,需要选用恰当的负载均衡策略.目前常用的服务器调度策略只是从服务器角度出发,实现硬件负载的均衡,而忽略了服务质量.本文算法定义了用户满意率(即“用户期望的任务完成时间“与“任务实际完成时间”的比值)指标来评价服务质量.算法综合用户权值,任务所属类别历史平均计算时间,用户期望计算时问,任务添加时间等四个因子,计算任务权值,然后由服务器主动按照任务权值高低进行调度.试验结果表明,该算法能够有效提高用户的满意率,充分利用服务器的计算资源.     

Theorem Proving Guided Development of Formal Assertions in a Resource-Constrained Scheduler for High-Level Synthesis

This paper presents a formal specification and a proof of correctness for the widely-used Force-Directed List Scheduling (FDLS) algorithm for resource-constrained scheduling of data flow graphs in high-level synthesis systems. The proof effort is conducted using a higher-order logic theorem prover. During the proof effort many interesting properties of the FDLS algorithm are discovered. These properties are formally stated and proved in a higher-order logic theorem proving environment. These properties constitute a detailed set of formal assertions and invariants that should hold at various steps in the FDLS algorithm. They are then inserted as programming assertions in the implementation of the FDLS algorithm in a production-strength high-level synthesis system. When turned on, the programming assertions (1) certify whether a specific run of the FDLS algorithm produced correct schedules and, (2) in the event of failure, help discover and isolate programming errors in the FDLS implementation.We present a detailed example and several experiments to demonstrate the effectiveness of these assertions in discovering and isolating errors. Based on this experience, we discuss the role of the formal theorem proving exercise in developing a useful set of assertions for embedding in the scheduler code and argue that in the absence of such a formal proof checking effort, discovering such a useful set of assertions would have been an arduous if not impossible task.