A new window-based job scheduling scheme for 2D mesh multicomputers

Allocating submeshes to jobs in mesh-connected multicomputers in a FCFS fashion can lead to poor system performance (e.g., long job waiting delays) because the job at the head of the waiting queue can prevent the allocation of free submeshes to other waiting jobs with smaller submesh requirements. However, serving jobs aggressively out-of-order can lead to excessive waiting delays for jobs with large allocation requests. In this paper, we propose a scheduling scheme that uses a window of consecutive jobs from which it selects jobs for allocation and execution. This window starts with the current oldest waiting job and corresponds to the lookahead of the scheduler. The performance of the proposed window-based scheme has been compared to that of FCFS and other previous job scheduling schemes. Extensive simulation results based on synthetic workloads and real workload traces indicate that the new scheduling strategy exhibits good performance when the scheduling window size is large. In particular, it is substantially superior to FCFS in terms of system utilization, average job turnaround times, and maximum waiting delays under medium to heavy system loads. Also, it is superior to aggressive out-of-order scheduling in terms of maximum job waiting delays. Window-based job scheduling can improve both overall system performance and fairness (i.e., maximum job waiting delays) by adopting large lookahead job scheduling windows.     

A Fast and Efficient Processor Management Scheme fork-aryn-cubes

Job scheduling and processor allocation are two key components of processor management technique in a multiprocessor operating system. We propose a fast and efficient processor management technique, called virtual cube (VC), fork-aryn-cubes in this paper. The proposed scheme supports spatial allocation of jobs to the virtual cubes of the system and multiprograms the virtual cubes in a round-robin fashion. The objective here is to reduce job waiting time and fragmentation. The VC scheme uses a fast subcube allocation algorithm called enhancedk-ary buddy. A novel approach, called paging, is proposed for fast submesh allocation. When used with the first fit algorithm, the paging scheme is shown to be extremely fast and efficient compared to other contemporary submesh allocation algorithms fork-aryn-cubes. We also study the impact of page size on performance and illustrate a methodology to compute optimal page size. Simulation results show that the VC scheme with its multiprogramming capability can boost system performance considerably and outperforms all existing policies while incurring minimal run-time overhead.     

An adaptive job scheduling scheme for mesh-connected multicomputers

Allocating submeshes to jobs in mesh-connected multicomputers in an FCFS fashion leads to poor system performance because a large job at the head of the waiting queue can prevent the allocation of free submeshes to other smaller waiting jobs. However, serving jobs aggressively out-of-order can lead to excessive waiting delays for large jobs located at the head of the waiting queue. In this paper, we show that the ability of the job scheduling algorithm to bypass the head of the waiting queue should increase with the load, and we propose a scheduling scheme that can bypass the waiting queue head in a load-dependent adaptive fashion. Also, giving priority to large jobs because they are more difficult to accommodate is investigated. The performance of the proposed scheme has been compared to that of FCFS, aggressive out-of-order scheduling, and other previous job scheduling schemes. Extensive simulation results based on synthetic workloads and real workload traces indicate that our scheduling strategy is a good strategy when both average and maximum job waiting delays are considered. In particular, it is substantially superior to FCFS in terms of mean turnaround times, and to aggressive out-of-order scheduling in terms of maximum waiting delays.     

Comparative evaluation of contiguous allocation strategies on 3D mesh multicomputers

The performance of contiguous allocation strategies can be significantly affected by the type of the distribution adopted for job execution times. In this paper, the performance of the existing contiguous allocation strategies for 3D mesh multicomputers is re-visited in the context of heavy-tailed distributions (e.g., a Bounded Pareto distribution). The strategies are evaluated and compared using simulation experiments for both First-Come-First-Served (FCFS) and Shortest-Service-Demand (SSD) scheduling strategies under a variety of system loads and system sizes. The results show that the performance of the allocation strategies degrades considerably when job execution times follow a heavy-tailed distribution. Moreover, SSD copes much better than FCFS scheduling strategy in the presence of heavy-tailed job execution times. The results also reveal that allocation strategies that employ a list of allocated sub-meshes for both allocation and de-allocation exhibit low allocation overhead, and maintain good system performance in terms of average turnaround time and mean system utilization.     

Provably Efficient Online Nonclairvoyant Adaptive Scheduling

Multiprocessor scheduling in a shared multiprogramming environment can be structured in two levels, where a kernel-level job scheduler allots processors to jobs and a user-level thread scheduler maps the ready threads of a job onto the allotted processors. We present two provably-efficient two-level scheduling schemes called G-RAD and S-RAD respectively. Both schemes use the same job scheduler RAD for the processor allotments that ensures fair allocation under all levels of workload. In G-RAD, RAD is combined with a greedy thread scheduler suitable for centralized scheduling; in S-RAD, RAD is combined with a work-stealing thread scheduler more suitable for distributed settings. Both G-RAD and S-RAD are non-clairvoyant. Moreover, they provide effective control over the scheduling overhead and ensure efficient utilization of processors. We also analyze the competitiveness of both G-RAD and S-RAD with respect to an optimal clairvoyant scheduler. In terms of makespan, both schemes can achieve O(1)-competitiveness for any set of jobs with arbitrary release time. In terms of mean response time, both schemes are O(1)-competitive for arbitrary batched jobs. To the best of our knowledge, G-RAD and S-RAD are the first non-clairvoyant scheduling algorithms that guarantee provable efficiency, fairness and minimal overhead.     

Submesh Allocation in Mesh Multicomputers Using Busy-List: A Best-Fit Approach with Complete Recognition Capability

A new approach is proposed for dynamic submesh allocation in mesh-connected multicomputer system, which supports a multiuser environment. The proposed strategy effectively prunes the search space by searching for free submeshes on the corners of allocated (busy) submeshes along with the four corners of the mesh system. A submesh is selected with the potential of causing the least amount of fragmentation in the system. The proposed strategy possesses complete submesh recognition capability; it is a best-fit strategy, as well. Existing strategies do not provide this combination of capabilities. The deallocation time and memory overhead are shown to be constant in that they do not grow with the size of the mesh. To demonstrate effectiveness, the performance of the proposed strategy is compared against all existing schemes. Simulation results indicate that the proposed strategy outperforms existing ones in terms of parameters such as average delay in honoring a request, standard deviation of delay, average allocation time, average deallocation time, and amount of memory required. The proposed scheme achieves a 20 to 30% improvement in the average waiting delay over the best performing existing algorithm to date. Our scheme is shown to be applicable to torus-connected multicomputers as well, with only minor modifications. The scheme can also be used for submesh allocation with failures.     

异构Hadoop集群下的负载自适应反馈调度策略

随着基于Hadoop平台的大数据技术的不断发展和实践的深入,Hadoop YARN资源调度策略在异构集群中的不适用性越发明显。一方面,节点资源无法动态分配,导致优势节点的计算资源浪费、系统性能没有充分发挥;另一方面,现有的静态资源分配策略未考虑作业在不同执行阶段的差异,易产生大量资源碎片。基于以上问题,提出了一种负载自适应调度策略。监控集群执行节点和提交作业的性能信息,利用实时监控数据建模、量化节点的综合计算能力,结合节点和作业的性能信息在调度器上启动基于相似度评估的动态资源调度方案。优化后的系统能够有效识别集群节点的执行能力差异,并根据作业任务的实时需求进行细粒度的动态资源调度,在完善YARN现有调度语义的同时,可作为子级资源调度方案架构在上层调度器下。在Hadoop 2.0上实现并测试该策略,实验结果表明,作业的自适应资源调度策略显著提高了资源利用率,集群并发度提高了2到3倍,时间性能提升了近10%。     

Data Intensive and Network Aware (DIANA) Grid Scheduling

In Grids scheduling decisions are often made on the basis of jobs being either data or computation intensive: in data intensive situations jobs may be pushed to the data and in computation intensive situations data may be pulled to the jobs. This kind of scheduling, in which there is no consideration of network characteristics, can lead to performance degradation in a Grid environment and may result in large processing queues and job execution delays due to site overloads. In this paper we describe a Data Intensive and Network Aware (DIANA) meta-scheduling approach, which takes into account data, processing power and network characteristics when making scheduling decisions across multiple sites. Through a practical implementation on a Grid testbed, we demonstrate that queue and execution times of data-intensive jobs can be significantly improved when we introduce our proposed DIANA scheduler. The basic scheduling decisions are dictated by a weighting factor for each potential target location which is a calculated function of network characteristics, processing cycles and data location and size. The job scheduler provides a global ranking of the computing resources and then selects an optimal one on the basis of this overall access and execution cost. The DIANA approach considers the Grid as a combination of active network elements and takes network characteristics as a first class criterion in the scheduling decision matrix along with computations and data. The scheduler can then make informed decisions by taking into account the changing state of the network, locality and size of the data and the pool of available processing cycles.     

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

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

An efficient submesh allocation scheme for two-dimensional mesheswith little overhead

This paper presents a submesh allocation scheme for two-dimensional mesh systems. The submesh detection process considers only those available free submeshes that border from the left on some allocated submeshes or have their left boundaries aligned with that of the mesh. Fragmentation in the system can be reduced as a result. More importantly, we present an efficient approach to facilitate the detection of such available submeshes. The basic idea of the approach is to place the allocated submeshes of the busy set in a certain order so as to reduce the complexity of subtraction operations required for submesh detection. The method is simple and causes an amount of overhead which is only a fraction of that produced by previous algorithms. Extensive simulation has been conducted to evaluate the performance of the proposed scheme. The results show that when allocation overhead is considered, the proposed scheme may outperform previous methods     

Backfilling Using System-Generated Predictions Rather than User Runtime Estimates

The most commonly used scheduling algorithm for parallel supercomputers is FCFS with backfilling, as originally introduced in the EASY scheduler. Backfilling means that short jobs are allowed to run ahead of their time provided they do not delay previously queued jobs (or at least the first queued job). However, predictions have not been incorporated into production schedulers, partially due to a misconception (that we resolve) claiming inaccuracy actually improves performance, but mainly because underprediction is technically unacceptable: users will not tolerate jobs being killed just because system predictions were too short. We solve this problem by divorcing kill-time from the runtime prediction and correcting predictions adaptively as needed if they are proved wrong. The end result is a surprisingly simple scheduler, which requires minimal deviations from current practices (e.g., using FCFS as the basis) and behaves exactly like EASY as far as users are concerned; nevertheless, it achieves significant improvements in performance, predictability, and accuracy. Notably, this is based on a very simple runtime predictor that just averages the runtimes of the last two jobs by the same user; counter intuitively, our results indicate that using recent data is more important than mining the history for similar jobs. All the techniques suggested in this paper can be used to enhance any backfilling algorithm and are not limited to EASY     

On submesh allocation for mesh multicomputers: a best-fitallocation and a virtual submesh allocation for faulty meshes

The submesh allocation problem is to recognize and locate a free submesh that can accommodate a request for a submesh of a specified size. In this paper, we propose a new best-fit submesh allocation strategy for mesh-connected multiprocessor systems. The proposed strategy maintains and uses a free submesh list for an efficient allocation. For an allocation request, the strategy selects the best-fit submesh which causes the least amount of potential processor fragmentation. As many large free submeshes as possible are preserved for later allocations. For this purpose, we introduce a novel function quantifying the degree of potential fragmentation of submeshes. The proposed strategy has the capability of recognizing a complete submesh. We also propose an allocation strategy for faulty meshes which can maintain and allocate virtual submeshes derived from faulty submeshes. Extensive simulation is carried out to compare the proposed strategy with previous strategies. The proposed strategy has the best performance: a 6-50 percent improvement over the previous best strategy     

Design and implementation of an adaptive job allocation strategy for heterogeneous multi‐cluster computing systems

Cluster computing is an attractive approach to provide high‐performance computing for solving large‐scale applications. Owing to the advances in processor and networking technology, expanding clusters have resulted in the system heterogeneity; thus, it is crucial to dispatch jobs to heterogeneous computing resources for better resource utilization. In this paper, we propose a new job allocation system for heterogeneous multi‐cluster environments named the Adaptive Job Allocation Strategy (AJAS), in which a self‐scheduling scheme is applied in the scheduler to dispatch jobs to the most appropriate computing resources. Our strategy focuses on increasing resource utility by dispatching jobs to computing nodes with similar performance capacities. By doing so, execution times among all nodes can be equalized. The experimental results show that AJAS can improve the system performance. Copyright © 2011 John Wiley & Sons, Ltd.     

A Lazy Scheduling Scheme for Hypercube Computers

Processor allocation and job scheduling are two complementary techniques for improving the performance of multiprocessors. It has been observed that all the hypercube allocation policies with the FCFS scheduling provide only incremental performance improvement. A greater impact on the performance can be obtained by efficient job scheduling. This paper presents an effort in that direction by introducing a new scheduling algorithm called lazy scheduling for hypercubes, The motivation of this scheme is to eliminate the limitations of the FCFS scheduling. This is done by maintaining separate queues for different job sizes and delaying the allocation of a job if any other job(s) of the same dimension is(are) running in the system. Processor allocation is done using the buddy strategy. The scheduling and allocation complexity is O(n) for an n-cube. Simulation studies show that the performance is dramatically enhanced by using the lazy scheduling scheme as compared to the FCFS scheduling. Comparison with a recently proposed scheme called scan indicates that the lazy scheme performs better than the scan scheduling under a wide range of workloads.     

On construction of a well-balanced allocation strategy for heterogeneous multi-cluster computing environments

With the rapid increment of the heterogeneity of hardware devices, cluster computing has to encounter the problem of handling heterogeneous resources for exploiting the utilization of system resources. This paper introduces a new job allocation strategy based on multi-clusters in diskless environments. By adopting Ganglia as the resource monitor and Condor as the queue system, a heterogeneous multi-cluster system is also constructed with and without storage devices for evaluating the system performance. The proposed algorithm is called the Well-Balanced Allocation Strategy (WBAS) in which the scheduler dispatches MPI-based jobs to appropriate resources across multi-clusters. The strategy focuses on dispatching jobs to nodes with similar performance, thus equalizing execution times among all the required nodes. The WBAS is implemented on the constructed heterogeneous multi-cluster system to evaluate the performance of the scheduling strategy. The experimental results show that the proposed strategy performs well and could efficiently improve the system performance.     

Task migration in n-dimensional wormhole-routed mesh multicomputers

In a mesh multicomputer, performing jobs needs to schedule submeshes according to some processor allocation scheme. In order to assign the incoming jobs to a free submesh, a task compaction scheme is needed to generate a larger contiguous free region. The overhead of compaction depends on the efficiency of the task migration scheme. In this paper, two simple task migration schemes are first proposed in n-dimensional mesh multicomputers with supporting dimension-ordered wormhole routing in one-port communication model. Then, a hybrid scheme which combines advantages of the two schemes is discussed. Finally, we evaluate the performance of all of these proposed approaches.     

Adaptive hierarchical scheduling policy for enterprise grid computing systems

In an enterprise grid computing environments, users have access to multiple resources that may be distributed geographically. Thus, resource allocation and scheduling is a fundamental issue in achieving high performance on enterprise grid computing. Most of current job scheduling systems for enterprise grid computing provide batch queuing support and focused solely on the allocation of processors to jobs. However, since I/O is also a critical resource for many jobs, the allocation of processor and I/O resources must be coordinated to allow the system to operate most effectively. To this end, we present a hierarchical scheduling policy paying special attention to I/O and service-demands of parallel jobs in homogeneous and heterogeneous systems with background workload. The performance of the proposed scheduling policy is studied under various system and workload parameters through simulation. We also compare performance of the proposed policy with a static space–time sharing policy. The results show that the proposed policy performs substantially better than the static space–time sharing policy.     

面向移动机器人分布式计算的任务调度方法

针对移动机器人导航控制中信息处理量大、任务多的情况,提出了一个适用于移动机器人的分布式计算框架,并在此框架的基础上设计了一种任务调度方法——GMBSA,该方法以资源代理为基础,首先对任务执行时间进行预测,然后运用遗传算法结合多队列Backfilling方法进行任务调度,达到最小化任务执行时间的要求,最终实现资源的优化分配,满足了机器人导航控制中的实时性要求。该文采用实验室构建的分布式计算环境对GMBSA的性能进行了测试,并比较了轻重负载情况下GMBSA,多队列Backfilling和FCFS 3种调度方案的性能差异。     

Libra: a computational economy‐based job scheduling system for clusters

Clusters of computers have emerged as mainstream parallel and distributed platforms for high‐performance, high‐throughput and high‐availability computing. To enable effective resource management on clusters, numerous cluster management systems and schedulers have been designed. However, their focus has essentially been on maximizing CPU performance, but not on improving the value of utility delivered to the user and quality of services. This paper presents a new computational economy driven scheduling system called Libra, which has been designed to support allocation of resources based on the users' quality of service requirements. It is intended to work as an add‐on to the existing queuing and resource management system. The first version has been implemented as a plugin scheduler to the Portable Batch System. The scheduler offers market‐based economy driven service for managing batch jobs on clusters by scheduling CPU time according to user‐perceived value (utility), determined by their budget and deadline rather than system performance considerations. The Libra scheduler has been simulated using the GridSim toolkit to carry out a detailed performance analysis. Results show that the deadline and budget based proportional resource allocation strategy improves the utility of the system and user satisfaction as compared with system‐centric scheduling strategies. Copyright © 2004 John Wiley & Sons, Ltd.     

Allocating precise submeshes in mesh connected systems

We propose a new processor allocation strategy that applies to any mesh system and recognizes submeshes of arbitrary sizes at any locations in a mesh system. The proposed strategy allocates a submesh of exactly the size requested by an incoming task, completely avoiding internal fragmentation. Because of its efficient allocation, this strategy exhibits better performance than an earlier allocation strategy based on the buddy principle. An efficient implementation of this strategy is presented. Extensive simulation runs are carried out to collect experimental cost and performance measures of interest under different allocation schemes