The Effects of Precedence and Priority Constraints on the Performance of Scan Scheduling for Hypercube Multiprocessors

In the absence of scheduling constraints, Scan scheduling has been shown to considerably improve performance in hypercube multiprocessors relative to previously studied job scheduling disciplines. In practice, jobs may have properties that constrain the choices a job scheduler can make, potentially limiting the scheduler's ability to affect performance. Two common types of job scheduling constraints are precedence and priority constraints. We examine the effects of these constraints on the ability of Scan to improve performance in hypercube systems. We find that, even under severe constraints, Scan scheduling retains its large performance advantage.     

Job scheduling and processor allocation for grid computing on metacomputers

Scheduling is a fundamental issue in achieving high performance on metacomputers and computational grids. For the first time, the job scheduling problem for grid computing on metacomputers is studied as a combinatorial optimization problem. A cost model is proposed for modeling communication heterogeneity on computational grids. A processor allocation algorithm is developed which always finds an optimal processor allocation that minimizes the effective execution time of a job when the job is being scheduled. It is proven that the list scheduling (LS) algorithm can achieve reasonable worst-case performance bound in grid environments supporting distributed supercomputing with large applications. We compare the performance of various job scheduling and processor allocation algorithms for grid computing on metacomputers. We evaluate the performance of 128 combinations of two job scheduling algorithms, four initial job ordering strategies, four processor allocation algorithms, and four metacomputers by extensive simulation. It is found that the combination of largest job first (LJF) initial job ordering and minimum effective execution time (MEET) or largest machine first (LMF) processor allocation algorithm yields the best average-case performance, and the choice of FCFS and LS depends on the range of job sizes. It is also observed that communication heterogeneity does have significant impact on schedule lengths.     

Job Allocation Strategies with User Run Time Estimates for Online Scheduling in Hierarchical Grids

We address non-preemptive non-clairvoyant online scheduling of parallel jobs on a Grid. We consider a Grid scheduling model with two stages. At the first stage, jobs are allocated to a suitable Grid site, while at the second stage, local scheduling is independently applied to each site. We analyze allocation strategies depending on the type and amount of information they require. We conduct a comprehensive performance evaluation study using simulation and demonstrate that our strategies perform well with respect to several metrics that reflect both user- and system-centric goals. Unfortunately, user run time estimates and information on local schedules does not help to significantly improve the outcome of the allocation strategies. When examining the overall Grid performance based on real data, we determined that an appropriate distribution of job processor requirements over the Grid has a higher performance than an allocation of jobs based on user run time estimates and information on local schedules. In general, our experiments showed that rather simple schedulers with minimal information requirements can provide a good performance.     

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.     

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.     

利用作业可塑性改进结合回填FCFS策略的性能

结合回填的FCFS策略是超级计算机上使用最为普遍的调度策略,针对该策略在响应时间和系统利用率等方面的不足,提出了改进其性能的DGA方法。该方法利用并行作业的可塑性,通过调度时对作业平均响应时间的预测来选择适合的作业请求规模,并利用遗传算法来解决最优作业资源请求的搜索问题。模拟器上实际作业流的模拟结果表明：该方法可以显著地改进结合回填的FCFS策略的调度效果,也优于已有的可塑性作业调度策略。     

Processor allocation in hypercube multicomputers: fast andefficient strategies for cubic and noncubic allocation

A new approach for dynamic processor allocation in hypercube multicomputers which supports a multi-user environment is proposed. A dynamic binary tree is used for processor allocation along with an array of free lists. Two algorithms are proposed based on this approach, capable of efficiently handling cubic as well as noncubic allocation. Time complexities for both allocation and deallocation are shown to be polynomial, a significant improvement over the existing exponential and even super-exponential algorithms. Unlike existing schemes, the proposed strategies are best-fit strategies within their search space. Simulation results indicate that the proposed strategies outperform the existing ones in terms of parameters such as average delay in honoring a request, average allocation time, average deallocation time, and memory overhead     

Static processor allocation in a soft real-time multiprocessorenvironment

Soft real-time environments consist of jobs that must receive service within a particular time interval. If service for a specific job is not completed by the end of its time interval, it is said to be lost; in addition, the computation time expended on the job is wasted, and any further computation for the job is discontinued. The goal of a system designer is to provide an environment that minimizes the number of jobs that are lost. If a parallel environment is available, the system designer has two options: Allow each processor to execute a job individually, or let multiple processors cooperate in executing a job. This article shows, for two classes of static allocation policies, that simple comparative analytical models may be used to indicate which option minimizes the number of lost jobs, as a function of workload intensity. The first class of policies, called equal partitions, statically decomposes the system into equal-size sets of processors and executes one job per partition. These policies are frequently employed in other contexts. The second class of policies, called two partitions, statically partitions the processors into two sets, not necessarily of the same size. Surprisingly, it is observed mathematically that even for statistically identical jobs, this class of policies is superior to equal partitions under certain loadings. The analysis is validated experimentally with a workload executed on a 16-node iPSC/2 hypercube     

Cloud data analysis using a genetic algorithm‐based job scheduling process

Data analysis plays a major role in different research applications that require a large volume of data. Cloud computing can provide computer processing resources and device‐to‐device data sharing based on user requirements. The main goal of cloud computing is to allow users and enterprise of varying capabilities to store and process data in an efficient way and to access and distribute resources. However, a crucial problem in cloud computing is job scheduling for numerous users. Prior to the implementation of job scheduling, jobs must be categorized according to degree of criticalness, privacy and time required. Based on the experimental results, the combination of tasks was successfully determined by the processor. In heterogeneous multiprocessor systems, customized job scheduling is highly critical for obtaining optimal job performance. In this paper, an evolutionary genetic algorithm was used for obtaining better results in job scheduling, thereby improving performance in the cloud system in this regard. The genetic algorithm‐based job scheduling process introduced minimizes the investment in time through effective allocation of user requests in order to enhance the overall efficiency of the system.     

Incomplete hypercubes: Algorithms and embeddings

The hypercube, though a popular and versatile architecture, has a major drawback in that its size must be a power of two. In order to alleviate this drawback, Katseff [1988] defined theincomplete hypercube, which allows a hypercube-like architecture to be defined for any number of nodes. In this paper we generalize this definition and introduce the namecomposite hypercube. The main result of our work shows that these incomplete architectures can be used effectively and without the size penalty. In particular, we show how to efficiently implement Fully Normal Algorithms on composite hypercubes. Development of these types of algorithms on composite hypercubes allows us to efficiently execute several algorithms concurrently on a complete hypercube. We also show that many host architectures, such as binary trees, arrays and butterflies, can be optimally embedded into composite hypercubes. These results imply that algorithms originally designed for any such host can be optimally mapped to composite hypercubes. Finally, we show that composite hypercubes exhibit many graph theoretic properties that are common with complete hypercubes. We also present results on efficient representations of composite hypercubes within a complete hypercube. These results are crucial in task allocation and job scheduling problems.This research was supported in part by the National Science Foundation under grant USE-90-52346. A preliminary version of this work appeared in the5th International Parallel Processing Symnposium, May 1991.     

Extra Processors versus Future Information in Optimal Deadline Scheduling

This paper is concerned with the design of online scheduling algorithms that exploit extra resources. In particular, it studies how to make use of multiple processors to counteract the lack of future information in online deadline scheduling. Our results extend the previous work that are primarily based on using a faster processor to obtain a performance guarantee. The challenge arises from the fact that jobs are sequential in nature and cannot be executed on more than one processor at the same time. Thus, a faster processor can speed up a job while multiple unit-speed processors cannot.     

超立方体网络中任务调度的一个新近似算法

本文研究超立方体中的多处理器任务调度问题,我们研究LDLPT算法并指出为什么这种算法对一些实例具有最差的逼近度,然后提出一种类似装箱算法的新算法-BPA算法,证明该算法和LDLPT算法在相互最差逼近度中具有互补性质,最后,组合这两种算法的基本方法提出了一种求解问题的新算法-CBPA算法,并证明新算法具有比LDLPT算法更好的逼近度。     

Noncontiguous processor allocation algorithms for mesh-connectedmulticomputers

Current processor allocation techniques for highly parallel systems are typically restricted to contiguous allocation strategies for which performance suffers significantly due to the inherent problem of fragmentation. As a result, message-passing systems have yet to achieve the high utilization levels exhibited by traditional vector supercomputers. We are investigating processor allocation algorithms which lift the restriction on contiguity of processors in order to address the problem of fragmentation. Three noncontiguous processor allocation strategies-paging allocation, random allocation, and the Multiple Buddy Strategy (MBS)-are proposed and studied in this paper. Simulations compare the performance of the noncontiguous strategies with that of several well-known contiguous algorithms. We show that noncontiguous allocation algorithms perform better overall than the contiguous ones, even when message-passing contention is considered. We also present the results of experiments on an Intel Paragon XP/S-15 with 208 nodes that show noncontiguous allocation is feasible with current technologies     

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.     

Scheduling Policies for Processor Coallocation in Multicluster Systems

Building multicluster systems out of multiple, geographically distributed clusters interconnected by high-speed wide-area networks can provide access to a larger computational power and to a wider range of resources. Jobs running on multiclusters and, more generally, in grids, may require (processor) coallocation, i.e., the simultaneous allocation of resources (processors) in different clusters or subsystems of a grid. In this paper, we propose four scheduling policies for processor coallocation in multiclusters, and we assess with simulations their performance under a wide variety of parameter settings. In particular, in our simulations we use synthetic workloads and workloads derived from the logs of actual systems and from runtime measurements. We conclude that although coallocation makes scheduling more difficult and the wide-area communication critically impacts the performance, there is a wide range of realistic applications that may benefit from coallocation. However, unrestricted coallocation is not recommended: Limiting the total job size or the number or the sizes of their components improves performance.     

The rejection rate for tasks with random arrivals, deadlines, andpreemptive scheduling

A means of approximating light-traffic performance of RAD (random-arrivals-with-deadlines) systems for four basic preemptive scheduling policies is presented. The design goal is to keep congestion low enough to make the probability of rejection acceptably small. These designs must have low processor utilization. The study analyzes rejection probabilities at utilizations up to 20% and rejection probabilities up to about 10% for various well-known preemptive scheduling disciplines (shortest job first, earliest due date, and least laxity first), as well as first-come, first-served. Good approximations for the rejection probability and for a number of other properties, such as the distribution of time-to-go at rejection, are found     

云计算中多QoS调度机制研究

云计算的作为分布式系统中的一种新的服务配置模式,鼓励研究人员在科学应用时探讨其利弊.云资源的动态变化给资源管理带来了很大的困难.在云计算环境中的调度工作中使用一个分割负载理论（DLT）设计有效的策略来最小化总的处理时间,处理器是负载均衡的,推导出一个封闭形式的解决方案将负载分段分配给每个处理器.以这种方式进行工作调度使得云提供商可以获得最大的服务效益并满足客户的服务质量（QoS）需求.最后,通过严格的仿真研究量化该策略的性能.     

Analysis of fork-join program response times on multiprocessors

Models for two processor sharing policies called task scheduling processor sharing and job scheduling processor sharing are developed and analyzed. The first policy schedules each task independently and allows parallel execution of an individual program, whereas the second policy schedules each job as a unit, thereby not allowing parallel execution of an individual program. It is found that task scheduling performs better than job scheduling for most system parameter values. The performance of the task scheduling processor sharing is compared to a first come first serve policy. First come first serve performs better than processor sharing over a wide range of system parameters. Processor sharing performs best when the task service time variability is high. The performance of processor sharing and first come first serve is studied with two classes of jobs, and for when a specific number of processors is statically assigned to each of the classes     

Comparing Processor Allocation Strategies in Multiprogrammed Shared-Memory Multiprocessors

Small-scale shared-memory multiprocessors are commonly used in a workgroup environment where multiple applications, both parallel and sequential, are executed concurrently while sharing the processors and other system resources. To utilize the processors efficiently, an effective allocation strategy is required. In this paper, we use performance data obtained from an SGI multiprocessor to evaluate several processor allocation strategies when running two parallel programs simultaneously. We examine gang scheduling (coscheduling), static space-sharing (space partitioning), and a dynamic allocation scheme called loop-level process control (LLPC) with three different dynamic allocation heuristics. We use regression analysis to quantify the measured data and thereby explore the relationship between the degree of parallelism of the application, specific system parameters (such as the size of the system), the processor allocation strategy, and the resulting performance. This study shows that dynamically partitioning the system using LLPC or similar heuristics provides better performance for applications with a high degree of parallelism than either gang scheduling or static space-sharing.     

Mesh网均等分区策略

在大规模并行计算机系统中，处理机资源可能被多个用户作业竞争，操作系统必须采用一种处理机分配策略确定多少和哪些处理机分配给一个作业。文中针对大规模、消息通信并行计算机提出了矩形和非矩形两种处理机分配策略，这两种策略均满足对每个用户所分配处理机数的公平性以及处理机分配的邻近性。