协同调度算法Dasic的性能评价

对一个动态自适应的NOW(network of workstations)协同调度算法Dasic算法进行了性能评估.通过对Dasic算法和典型的NOW协同调度算法MAX算法、Grab算法的性能模拟,在响应时间和系统流量两个主要性能指标上进行分析和比较,从而验证了在较大规模的NOW系统中,动态自适应对协同调度的性能有较大的影响.     

网络并行计算可伸缩策略的研究及其实现

文中提出了一种策略,能够进行可伸缩的调度和动态负载平衡调节,在保证工作站用户独点特性的前提下提高了整个系统资源的利用率;同时,我们能保持效率的相对恒定并给出了在资源动态变化情况下的系统性能评价方案。实验表明,该策略效果良好,通用性强。     

网络环境下的并行计算模型

1.引言所谓网络并行计算就是将一群计算机系统用网络以某种结构互连起来,充分利用各系统资源,统一调度,协调处理,以实现高效的并行处理。它是并行分布式计算领域近年来比较活跃的研究领域。由于网络技术的发展,特别是局域网中高速数据通讯网络的出现,使得利用工作站集群(NOW或COW)作为并行计算的平台越来越具有吸引力,同时也出现了许多支持异种机网络计算的软件工具环境,如MPI、PVM、EXPRESS等。NOW与巨型机和MPP系统相比,具有很高的性能价格比,可扩展性     

一种实用的并行计算模型

对于当前流行的工作站集群环境和各类并行机系统,文中提出了一种实用的并行计算模型,即基于LogGP的非独占异质同步模型NHBL（Nondedicated Heterogeneous Barrier LogGP）,它旨在反映具有异质性和非独占性的NOW计算环境对并行算法设计和分析的影响,然后用NHBL模型分析了PSRS算法在国家高性能计算中心（合肥）的工作站集群NHPCC-Cluster和曙光－1000MPP由的代价,并用实测结果进行了验证。     

分布式动态负载平衡调度的一个通用模型

在大规模并行分布处理系统，特别是网络工作站机群（ＮＯＷ）系统中，各结点机之间的负载平衡调度是最为常见的关键性问题之一．本文在简单分析了动态负载平衡调度中接收者驱动和发送者驱动这两个常用策略基础上，提出了一个通用的基于混合驱动策略的动态负载平衡调度模型，并给出了曙光１０００并行机上的部分实验结果.     

在Windows 2000下实现NOW系统的构建

本文介绍了在Windows 2000环境下如何构建并行工作站机群NOW，并且详细地介绍了以VC 6．0作为编译环境安装MPICH的过程和具体配置。     

基于簇结构的以调度器的设计和实现

1 引言目前,工作站性能大幅度提高,高速网络技术日益成熟,工作站网络(NOW,Network Of Workstations)得到迅猛的发展。但随着网络环境日趋大规模化,传统方式下基于节点的调度方式显然已不能适应,因为随着节点数目的增多不仅管理更加复杂,而且系统开销也将增加很多,所以我们提出层次调度方式。其主要特     

媒体流动态自适应合并策略

流式媒体应用的核心问题是资源调度,在诸多媒体流的动态调度算法中,SelectivePeriodPatching算法有显著优点,但仍有不足。文章在SelectivePeriodPatching算法基础上,提出媒体流动态自适应合并策略,可有效利用系统资源,提高系统服务性能。     

开放式实时嵌入式系统自适应调度模型研究

开放式实时嵌入式系统中多类型实时任务并存和资源受限的情况给实时调度机制带来了新的需求和挑战。通过引入准入控制、资源管理、调度服务器、自适应调节机制等,提出了一个形式化的自适应调度模型。它能适应开放计算环境的不确定性,有控制地接受不同类型任务的运行;可根据系统资源和任务需求的最新变换情况计算带宽变化,自适应地调节任务的优先等级,使得系统运行在最优的实时性能上;该模型在某航空机载系统设计中得到了实际应用,同其它类似系统相比,该模型的应用提高了系统的调度性和系统稳定性。     

云计算环境下的自适应资源管理技术综述

云环境下的自适应资源管理是当前云计算研究领域的热点问题,是云计算具备弹性扩展、动态分配和资源共享等特点的关键技术支撑,具有重要的理论意义和实用价值.其主要研究点包括:虚拟机放置优化算法,虚拟资源动态伸缩模型、多IDC间的全局云计算资源调度、全局资源配置及能力规划模型等.对云环境下自适应资源管理研究现状进行分析研究,并指出当前研究中存在的一些主要问题,同时进一步展望本领域未来的研究方向.     

A model for dynamic adaptive coscheduling

is paper proposes a dynamic adaptive coscheduling model DASIC to take advantage of excess available resources in a network of workstations(NOW). Besides coscheduling related subtasks dynamically,DASIC can scale up or down the process space depending upon the number of available processors on an NOW. Based on the dynamic idle processor group(IPG),DASIC employs thre modules:the coscheduling module,the scalabele scheduling module and the load balancing module,and uses six algorithms to achieve scalability.A simplified DASIC was also implemented,and experimental results are presented in this paper,which show that it can maximize system utilization,and achieve task parallelism as much as possible.     

Cooperating CoScheduling: A Coscheduling Proposal Aimed at Non-Dedicated Heterogeneous NOWs

Implicit coscheduling techniques applied to non-dedicated homogeneous Networks Of Workstations （NOWs） have shown they can perform well when many local users compete with a single parallel job. Implicit coscheduling deals with minimizing the communication waiting time of parallel processes by identifying the processes in need of coscheduling through gathering and analyzing implicit runtime information, basically communication events. Unfortunately, implicit coscheduling techniques do not guarantee the performance of local and parallel jobs, when the number of parallel jobs competing against each other is increased. Thus, a low efficiency use of the idle computational resources is achieved.
In order to solve these problems, a new technique, named Cooperating CoScheduling （CCS）, is presented in this work. Unlike traditional implicit coscheduling techniques, under CCS, each node takes its scheduling decisions from the occurrence of local events, basically communication, memory, Input/Output and CPU, together with foreign events received from cooperating nodes. This allows CCS to provide a social contract based on reserving a percentage of CPU and memory resources to ensure the progress of parallel jobs without disturbing the local users, while coscheduling of communicating tasks is ensured. Besides, the CCS algorithm uses status information from the cooperating nodes to balance the resources across the cluster when necessary. Experimental results in a non-dedicated heterogeneous NOW reveal that CCS allows the idle resources to be exploited efficiently, thus obtaining a satisfactory speedup and provoking an overhead that is imperceptible to the local user.     

Coscheduled distributed-Web servers on system area network

As cluster-based Web servers are increasingly adopted to host a variety of network-based services, improving the performance of such servers has become critical to satisfy the customers’ demands. Especially, the user response time is an important factor so that clients feel satisfied with the Web services. In this paper, we investigate the feasibility of minimizing the response time of a server by exploiting the advantages of both user-level communication and coscheduling. We, thus, propose a coscheduled server model based on the recently proposed distributed PRESS Web server, where the remote cache accesses can be coscheduled on different nodes to reduce the response time. We experiment this concept using two known coscheduling techniques, called dynamic coscheduling (DCS) and DCS with immediate blocking. We have developed a comprehensive simulation testbed that captures the underlying communication layer in a cluster, the characteristics of various coscheduling algorithms, and the characteristics of the distributed server model to estimate the average delay and throughput with different system configurations. The accuracy of the VIA communication layer and the DCS mechanism is verified using measurements on a 16-node Linux cluster. Extensive simulation of four server models (PRESS over VIA, coscheduled PRESS model with DCS, with DCS and blocking, and Adaptive) using 32-node cluster configurations indicates that the average response time of a distributed server can be minimized significantly by coscheduling the communicating processes. The use of the DCS scheme reduced the average latency up to four times to the PRESS over VIA model that uses only user-level communication.     

IMPROVED RESOURCE UTILIZATION WITH BUFFERED COSCHEDULING

We present buffered coscheduling, a new methodology to multitask parallel jobs in a message-passing environment and to develop parallel programs that can pave the way to the efficient implementation of a distributed operating system. Buffered coscheduling is based on three innovative techniques: communication buffering, strobing, and non-blocking communication. By leveraging these techniques, we can perform effective optimizations based on the global status of the parallel machine rather than on the limited knowledge available locally to each processor

The advantages of buffered coscheduling include higher resource utilization, reduced communication overhead, efficient implementation of flow-control strategies and fault-tolerant protocols, accurate performance modeling, and a simplified yet ;.till expressive parallel programming model which offloads many resource-management tasks to the operating system. Preliminary experimental results show that buffered coscheduling is very effective in increasing the overall performance in the presence of load imbalance and communication-intensive workloads and is relatively insensitive to the local process scheduling strategy.     

Adaptive parallel job scheduling with flexible coscheduling

Many scientific and high-performance computing applications consist of multiple processes running on different processors that communicate frequently. Because of their synchronization needs, these applications can suffer severe performance penalties if their processes are not all coscheduled to run together. Two common approaches to coscheduling jobs are batch scheduling, wherein nodes are dedicated for the duration of the run, and gang scheduling, wherein time slicing is coordinated across processors. Both work well when jobs are load-balanced and make use of the entire parallel machine. However, these conditions are rarely met and most realistic workloads consequently suffer from both internal and external fragmentation, in which resources and processors are left idle because jobs cannot be packed with perfect efficiency. This situation leads to reduced utilization and suboptimal performance. Flexible coscheduling (FCS) addresses this problem by monitoring each job's computation granularity and communication pattern and scheduling jobs based on their synchronization and load-balancing requirements. In particular, jobs that do not require stringent synchronization are identified, and are not coscheduled; instead, these processes are used to reduce fragmentation. FCS has been fully implemented on top of the STORM resource manager on a 256-processor alpha cluster and compared to batch, gang, and implicit coscheduling algorithms. This paper describes in detail the implementation of FCS and its performance evaluation with a variety of workloads, including large-scale benchmarks, scientific applications, and dynamic workloads. The experimental results show that FCS saturates at higher loads than other algorithms (up to 54 percent higher in some cases), and displays lower response times and slowdown than the other algorithms in nearly all scenarios.     

Coscheduling based on runtime identification of activity working sets

This paper introduces a method for runtime identification of sets of interacting activities (“working sets”) with the purpose ofcoscheduling them, i.e., scheduling them so that all the activities in the set execute simultaneously on distinct processors. The identification is done by monitoring access rates to shared communication objects: activities that access the same objects at a high rate thereby interact frequently, and therefore would benefit from coscheduling. Simulation results show that coscheduling with our runtime identification scheme can give better performance than uncoordinated scheduling based on a single global activity queue. The finer-grained the interactions among the activities in a working set, the better the performance differential. Moreover, coscheduling based on automatic runtime identification achieves about the same performance as coscheduling based on manual identification of working sets by the programmer.     

A runtime resolution scheme for priority boost conflict in implicit coscheduling

High-performance parallel and scientific applications are composed of multiple processes running on distinct CPUs that communicate frequently. Due to the synchronization needs of such applications, performance is greatly hampered if their processes are not scheduled simultaneously on the CPUs. Implicit coscheduling (ICS) is a well-known technique to address this problem in multi-programmed clusters, however, traditional ICS schemes do not incorporate steps to adequately deal with priority boost conflicts, leading to significantly degraded performance. In this paper, we propose the use of runtime difference in contention across nodes to provide more sophisticated coscheduling decisions in response to the conflicts. We also present a novel coscheduling scheme termed PROC (Process ReOrdering-based Coscheduling) that adaptively regulates the scheduling sequence of conflicting processes based on the rescheduling latency of their correspondents in remote nodes. We perform extensive simulation-based experiments using both synthetic and realistic workloads to analyze the performance of PROC compared to alternatives such as local scheduling, a widely used batch scheduling, gang scheduling, and existing ICS schemes. The results show that all ICS schemes commonly experience priority boost conflicts, and that the proposed PROC significantly outperforms other ICS alternatives (or batch scheduling) by up to 50.4% (or 72.5%) in the average job response time. This improvement is achieved by reducing wasted idle time and spinning time without sacrificing fairness.

一类图像并行处理的理论最优化调度方法

在图像并行处理应用中，有很大一部分并行算法是属于迭代同步的数据并行算法。这类分布式应用的子任务间需要某种形式的同步，因而要有协作调度的算法保证子任务基本上同时开始，并以同样速度执行。该文提出了一种以并行程序最短执行时间为目标的数据划分和任务协作调度算法。与其它类似算法相比，这个算法的最大特点是考虑了通信开销，因而更加符合实际的应用，更加有效。     

A comprehensive performance and energy consumption analysis of scheduling alternatives in clusters

In this paper, we conduct an in-depth evaluation of a broad spectrum of scheduling alternatives for clusters. These include the widely used batch scheduling, local scheduling, gang scheduling, most prior communication-driven coscheduling algorithms-Dynamic Coscheduling (DCS), Spin Block (SB), Periodic Boost (PB), and Co-ordinated Coscheduling (CC)-and a newly proposed HYBRID coscheduling algorithm on a 16-node, Myrinet-connected Linux cluster. Performance and energy measurements using several NAS, LLNL and ANL benchmarks on the Linux cluster provide several conclusions. First, although batch scheduling is currently used in most clusters, the blocking-based coscheduling techniques such as SB, CC and HYBRID and the gang scheduling can provide much better performance even in a dedicated cluster platform. Second, in contrast to some of the prior studies, we observe that blocking-based schemes like SB and HYBRID can provide better performance than spin-based techniques like PB on a Linux platform. Third, the proposed HYBRID scheduling provides the best performance-energy behavior and can be implemented on any cluster with little effort. All these results suggest that blocking-based coscheduling techniques are viable candidates to be used in clusters for significant performance-energy benefits.

Multi-domain job coscheduling for leadership computing systems

Current supercomputing centers usually deploy a large-scale compute system together with an associated data analysis or visualization system. Multiple scenarios have driven the demand that some associated jobs co-execute on different machines. We propose a multi-domain coscheduling mechanism, providing the ability to coordinate execution between jobs on multiple resource management domains without manual intervention. We have evaluated our mechanism based on real job traces from Intrepid and Eureka, the production Blue Gene/P system and a cluster with the largest GPU installation, deployed at Argonne National Laboratory. The experimental results show that coscheduling can be achieved with limited impact on system performance under varying workloads.