On development of an efficient parallel loop self-scheduling for grid computing environments

The approaches to deal with scheduling and load balancing on PC-based cluster systems are famous and well-known. Self-scheduling schemes, which are suitable for parallel loops with independent iterations on cluster computer system, they have been designed in the past. In this paper, we propose a new scheme that can adjust the scheduling parameter dynamically on an extremely heterogeneous PC-based cluster and Grid computing environments in order to improve system performance. A Grid computing environment consists of multiple PC-based clusters is constructed using Globus Toolkit and MPICH-G2 middleware. The experimental results show that our scheduling can result in higher performance than other similar schemes on Grid computing environments.     

Performance‐based parallel loop self‐scheduling using hybrid OpenMP and MPI programming on multicore SMP clusters

Parallel loop self‐scheduling on parallel and distributed systems has been a critical problem and it is becoming more difficult to deal with in the emerging heterogeneous cluster computing environments. In the past, some self‐scheduling schemes have been proposed as applicable to heterogeneous cluster computing environments. In recent years, multicore computers have been widely included in cluster systems. However, previous researches into parallel loop self‐scheduling did not consider certain aspects of multicore computers; for example, it is more appropriate for shared‐memory multiprocessors to adopt Open Multi‐Processing (OpenMP) for parallel programming. In this paper, we propose a performance‐based approach using hybrid OpenMP and MPI parallel programming, which partition loop iterations according to the performance weighting of multicore nodes in a cluster. Because iterations assigned to one MPI process are processed in parallel by OpenMP threads run by the processor cores in the same computational node, the number of loop iterations allocated to one computational node at each scheduling step depends on the number of processor cores in that node. Experimental results show that the proposed approach performs better than previous schemes. Copyright © 2010 John Wiley & Sons, Ltd.     

An Enhanced Parallel Loop Self-Scheduling Scheme for Cluster Environments

Approaches for dealing with scheduling and load-balancing in PC-based cluster systems are famous and well known. In such environments, Self-Scheduling Schemes are suitable for parallel loops with independent iterations. However, while schemes such as FSS, GSS, and TSS fit most computer systems, they cannot provide good load-balancing. Chao-Tung Yang and Shun-Chi Chang proposed a parallel loop scheduling scheme for heterogeneous PC cluster systems in Yang and Chang [13]. Though the proposed scheme allows users to choose parameters before execution initialization, weaknesses in it motivated us to develop further improvements. For instance, using fixed and monotonous parameters can easily lead to invalid scheduling due to use of previously input information. Thus, in this paper we propose a new scheme that fits most widely available computer systems and allows the scheduling parameter to be adjusted dynamically in order to provide higher overall performance.     

Cooperative load balancing in distributed systems

A serious difficulty in concurrent programming of a distributed system is how to deal with scheduling and load balancing of such a system which may consist of heterogeneous computers. In this paper, we formulate the static load‐balancing problem in single class job distributed systems as a cooperative game among computers. The computers comprising the distributed system are modeled as M/M/1 queueing systems. It is shown that the Nash bargaining solution (NBS) provides an optimal solution (operation point) for the distributed system and it is also a fair solution. We propose a cooperative load‐balancing game and present the structure of NBS. For this game an algorithm for computing NBS is derived. We show that the fairness index is always equal to 1 using NBS, which means that the solution is fair to all jobs. Finally, the performance of our cooperative load‐balancing scheme is compared with that of other existing schemes. Copyright © 2008 John Wiley & Sons, Ltd.     

Designing parallel loop self-scheduling schemes using the hybrid MPI and OpenMP programming model for?multi-core grid systems

Loop scheduling on parallel and distributed systems has been thoroughly investigated in the past. However, none of these studies considered the multi-core architecture feature for emerging grid systems. Although there have been many studies proposed to employ the hybrid MPI and OpenMP programming model to exploit different levels of parallelism for a distributed system with multi-core computers, none of them were aimed at parallel loop self-scheduling. Therefore, this paper investigates how to employ the hybrid MPI and OpenMP model to design a parallel loop self-scheduling scheme adapted to the multi-core architecture for emerging grid systems. Three different featured applications are implemented and evaluated to demonstrate the effectiveness of the proposed scheduling approach. The experimental results show that the proposed approach outperforms the previous work for the three applications and the speedups range from 1.13 to 1.75.     

Safe self-scheduling: A parallel loop scheduling scheme for shared-memory multiprocessors

In this papaer was present Safe Self-Scheduling (SSS), a new scheduling scheme that schedules parallel loops with variable length iteration execution times not known at compile time. The scheme assumes a shared memory space. SSS combines static scheduling with dynamic scheduling and draws favorable advantages from each. First, it reduces the dynamic scheduling overhead by statically scheduling a major portion of loop iterations. Second, the workload is balanced with a simple and efficient self-scheduling scheme by applying a new measure, thesmallest critical chore size. Experimental results comparing SSS with other scheduling schemes indicate that SSS surpasses other scheduling schemes. In the experiment on Gauss-Jordan, an application that is suitable for static scheduling schemes, SSS is the only self-scheduling scheme that outperforms the static scheduling scheme. This indicates that SSS achieves a balanced workload with a very small amount of overhead. This research has been supported in part by the National Science Foundation under Contract No. CCR-9210568.     

A performance-based parallel loop scheduling on grid environments

The effectiveness of loop self-scheduling schemes has been shown on traditional multiprocessors in the past and computing clusters in the recent years. However, parallel loop scheduling has not been widely applied to computing grids, which are characterized by heterogeneous resources and dynamic environments. In this paper, a performance-based approach, taking the two characteristics above into consideration, is proposed to schedule parallel loop iterations on grid environments. Furthermore, we use a parameter, SWR, to estimate the proportion of the workload which can be scheduled statically, thus alleviating the effect of irregular workloads. Experimental results on a grid testbed show that the proposed approach can reduce the completion time for applications with regular or irregular workloads. Consequently, we claim that parallel loop scheduling can benefit applications on grid environments.     

Performance evaluation of bag of gangs scheduling in a heterogeneous distributed system

Distributed systems deliver a cost-effective and scalable solution to the increasing performance intensive applications by utilizing several shared resources. Gang scheduling is considered to be an efficient time-space sharing scheduling algorithm for parallel and distributed systems. In this paper we examine the performance of scheduling strategies of jobs which are bags of independent gangs in a heterogeneous system. A simulation model is used to evaluate the performance of bag of gangs scheduling in the presence of high priority jobs implementing migrations. The simulation results reveal the significant role of the implemented migration scheme as a load balancing factor in a heterogeneous environment. Another significant aspect of implementing migrations presented in this paper is the reduction of the fragmentation caused in the schedule by gang scheduled jobs and the alleviation of the performance impact of the high priority jobs.     

Distributed dynamic load balancing for pipelined computations on heterogeneous systems

One of the most significant causes for performance degradation of scientific and engineering applications on high performance computing systems is the uneven distribution of the computational work to the resources of the system. This effect, which is known as load imbalance, is even more noticeable in the case of irregular applications and heterogeneous distributed systems. This motivated the parallel and distributed computing research community to focus on methods that provide good load balancing for scientific and engineering applications running on (heterogeneous) distributed systems. Efficient load balancing and scheduling methods are employed for scientific applications from various fields, such as mechanics, materials, physics, chemistry, biology, applied mathematics, etc. Such applications typically employ a large number of computational methods in order to simulate complex phenomena, on very large scales of time and magnitude. These simulations consist of routines that perform repetitive computations (in the form of DO/FOR loops) over very large data sets, which, if not properly implemented and executed, may suffer from poor performance. The number of repetitive computations in the simulation codes is not always constant. Moreover, the computational nature of these simulations may be in fact irregular, leading to the case when one computation takes (unpredictably) more time than others. For successful and timely results, large scale simulations require the use of large scale computing systems, which often are widely distributed and highly heterogeneous. Moreover, large scale computing systems are usually shared among multiple users, which causes the quality and quantity of the available resources to be highly unpredictable. There are numerous load balancing methods in the literature for different parallel architectures. The most recent of these methods typically follow the master-worker paradigm, where a single coordinator (master) is responsible for making all the scheduling decisions based on information provided by the workers. Depending on the application requirements, the scheduling policy and the computational environment, the benefits of this paradigm may be limited as follows: (1) its efficiency may not scale as the number of processors increases, and (2) it is quite probable that the scheduling decisions are made based on outdated information, especially on systems where the workload changes rapidly. In an effort to address these limitations, we propose a distributed (master-less) load balancing scheme, in which the scheduling decisions are made by the workers in a distributed fashion. We implemented this method along with other two master-worker schemes (a previously existing one and a recently modified one) for three different scientific computational kernels. In order to validate the usefulness and efficiency of the proposed scheme, we conducted a series of comparative performance tests with the two master-worker schemes for each computational kernel. The target system is an SMP cluster, on which we simulated three different patterns of system load fluctuation. The experiments strongly support the belief that the distributed approach offers greater performance and better scalability on such systems, showing an overall improvement ranging from 13% to 24% over the master-worker approaches.     

Iterative list scheduling for heterogeneous computing

Optimal scheduling of parallel applications on distributed computing systems represented by directed acyclic graph (DAG) is NP-complete in the general case. List scheduling is a very popular heuristic method for DAG-based scheduling. However, it is more suited to homogenous distributed computing systems. This paper presents an iterative list scheduling algorithm to deal with scheduling on heterogeneous computing systems. The main idea in this iterative scheduling algorithm is to improve the quality of the schedule in an iterative manner using results from previous iterations. The algorithm first uses the heterogeneous earliest-finish-time (HEFT) algorithm to find an initial schedule and iteratively improves it. Hence the algorithm can potentially produce shorter schedule length. The simulation results show that in the majority of the cases, there is significant improvement to the initial schedule. The algorithm is also found to perform best when the tasks to processors ratio is large.     

Performance-based dynamic loop scheduling in heterogeneous computing environments

With the rapid advance of computing technologies, it becomes more and more common to construct high-performance computing environments with heterogeneous commodity computers. Previous loop scheduling schemes were not designed for this kind of environments. Therefore, better loop scheduling schemes are needed to further increase the performance of the emerging heterogeneous PC cluster environments. In this paper, we propose a new heuristic for the performance-based approach to partition loop iterations according to the performance weighting of cluster/grid nodes. In particular, a new parameter is proposed to consider HPCC benchmark results as part of performance estimation. A heterogeneous cluster and grid were built to verify the proposed approach, and three kinds of application program were implemented for execution on cluster testbed. Experimental results show that the proposed approach performs better than the previous schemes on heterogeneous computing environments.     

分布式系统中的多用户并行调度算法

针对传统调度算法的不足,在多用户分布式天线系统的下行链路中引入并行调度思想,从而在系统吞吐量和公平性能间取得折中。首先将轮询调度算法进行了改进,同时提出一种并行调度算法,每次选择瞬时数据率和平均吞吐量较高的多个用户进行通信。采用优化的匹配算法改进传统穷尽搜索计算量大的缺陷。仿真结果显示与传统的并行调度和改进的并行轮询调度相比,本文算法在保证吞吐量的情况下,公平性有了显著提高。     

A multi‐grained distributed implementation of the parallel Block Conjugate Gradient algorithm

The Block Conjugate Gradient algorithm (Block‐CG) was developed to solve sparse linear systems of equations that have multiple right‐hand sides. We have adapted it for use in heterogeneous, geographically distributed, parallel architectures. Once the main operations of the Block‐CG (Tasks) have been collected into smaller groups (subjobs), each subjob is matched by the middleware MJMS (MPI Jobs Management System) with a suitable resource selected among those which are available. Moreover, within each subjob, concurrency is introduced at two different levels and with two different granularities: the coarse‐grained parallelism to perform independent tasks and the fine‐grained parallelism within the execution of a task. We refer to this algorithm as to multi‐grained distributed implementation of the parallel Block‐CG. We compare the performance of a parallel implementation with the one of the distributed implementation running on a variety of Grid computing environments. The middleware MJMS—developed by some of the authors and built on top of Globus Toolkit and Condor‐G—was used for co‐allocation, synchronization, scheduling and resource selection. Copyright © 2010 John Wiley & Sons, Ltd.     

集群系统中实现软实时服务机制的研究与评估

研究了集群架构服务器的三种实时调度策略,即集中式策略、分布式策略和主动型全分布策略。与调度功能主要集中在前端机的集中式策略比较,分布式策略将调度功能部分离散至后端节点,改善了系统的可扩展性。而主动型全分布式调度则进一步实现了调度分派功能的完全离散化,通过后端机的主动拉取事件和频率调控实现了负载平衡的自调节,极大地改善了系统的扩展性和服务效率。通过试验研究和试验表明,这三种都有效地降低了集群的响应服务请求的时间,还保证了系统的输出最大化。     

Optimal Recovery Schemes for High-Availability Cluster and Distributed Computing

Clusters and distributed systems offer two important advantages, viz. fault tolerance and high performance through load sharing. When all computers are up and running, we would like the load to be evenly distributed among the computers. When one or more computers break down the load on these computers must be redistributed to other computers in the cluster. The redistribution is determined by the recovery scheme. The recovery scheme should keep the load as evenly distributed as possible even when the most unfavorable combinations of computers break down, i.e., we want to optimize the worst-case behavior. In this paper we define recovery schemes, which are optimal for a number of important cases. We also define a bound on the performance of the recovery schemes for any number of computers.     

Dynamic partitioning of loop iterations on heterogeneous PC clusters

Loop partitioning on parallel and distributed systems has been a critical problem. Furthermore, it becomes more difficult to deal with on the emerging heterogeneous PC cluster environments. In the past, some loop self-scheduling schemes have been proposed to be applicable to heterogeneous cluster environments. In this paper, we propose a performance-based approach, which partitions loop iterations according to the performance ratio of cluster nodes. To verify the proposed approach, a heterogeneous cluster is built, and three types of application programs are implemented to be executed in this testbed. Experimental results show that the proposed approach performs better than traditional schemes.

Middleware infrastructure for parallel and distributed programming models in heterogeneous systems

We introduce a middleware infrastructure that provides software services for developing and deploying high-performance parallel programming models and distributed applications on clusters and networked heterogeneous systems. This middleware infrastructure utilizes distributed agents residing on the participating machines and communicating with one another to perform the required functions. An intensive study of the parallel programming models in Java has helped identify the common requirements for a runtime support environment, which we used to define the middleware functionality. A Java-based prototype, based on this architecture, has been developed along with a Java object-passing interface (JOPI) class library. Since this system is written completely in Java, it is portable and allows executing programs in parallel across multiple heterogeneous platforms. With the middleware infrastructure, users need not deal with the mechanisms of deploying and loading user classes on the heterogeneous system. Moreover, details of scheduling, controlling, monitoring, and executing user jobs are hidden, while the management of system resources is made transparent to the user. Such uniform services are essential for facilitating the development and deployment of scalable high-performance Java applications on clusters and heterogeneous systems. An initial deployment of a parallel Java programming model over a heterogeneous, distributed system shows good performance results. In addition, a framework for the agents' startup mechanism and organization is introduced to provide scalable deployment and communication among the agents.     

Service vulnerability scanning based on service-oriented architecture in Web service environments

Web services are becoming the critical components of business application, but they are often invoked with critical software and application bugs that can be explored by malicious users. Because the existing centralized vulnerability scanning systems often face performance bottleneck because of huge amount of tasks, a novel service vulnerability scanning scheme is high desirable. In this paper, we propose a service vulnerability scanning scheme based on service-oriented architecture (SoA) in Web service environments. The scanning scheme contains three components, i.e., domain-oriented distributed architecture, service providing mode based on SoA and hierarchical strategy scheduling model. The hierarchical strategy scheduling model is the key of the scanning scheme, which is used to solve the problems of distributed scheduling management in vulnerability scanning process for Web service environments. We conduct a centralized scanner to compare our scheme with other schemes by the implement of prototype system. Experimental results show that our proposed scheme outperforms other schemes with respect to time cost, accuracy and load.     

Improving scheduling of tasks in a heterogeneous environment

Optimal scheduling of parallel tasks with some precedence relationship, onto a parallel machine is known to be NP-complete. The complexity of the problem increases when task scheduling is to be done in a heterogeneous environment, where the processors in the network may not be identical and take different amounts of time to execute the same task. We introduce a task duplication-based scheduling algorithm for network of heterogeneous systems (TANH), with complexity O(V/sup 2/), which provides optimal results for applications represented by directed acyclic graphs (DAGs), provided a simple set of conditions on task computation and network communication time could be satisfied. The performance of the algorithm is illustrated by comparing the scheduling time with an existing "best imaginary level scheduling (BIL)" scheme for heterogeneous systems. The scalability for a higher or lower number of processors, as per their availability is also discussed. We have shown to provide substantial improvement over existing work on the task duplication-based scheduling algorithm (TDS).     

基于校园网络的元计算实验系统WADE的设计与实现

元计算系统是可以作为虚拟的整体而使用的地理上分散的异构计算资源，这些资源包括计算机、数据库和昂贵仪器等．元计算系统在硬件和软件方面均有异构性，适合具有不同内在并行性的复杂应用的执行．现存的绝大多数并行系统都是同构的，不具有这一优势，因此，研究异构环境下的元计算系统就很有现实意义．WADE是基于校园网络开发的元计算实验系统，使用MD支持异构数据格式转换，使用面向对象技术实现单一映像系统，使用优先约束的任务调度算法来实现应用程序的调度和运行，并提供与流行的并行编程软件如PVM等的接口。