Self-adaptive clock synchronization for computational grid

This paper presents an innovative method to synchronize physical clocks for a computational grid, in particular for a computational grid linked through the asynchronous In-tranet or Internet environments. The method discussed is an asynchronous self-adaptive clock synchronization mechanism. Two strategies for clock synchronisation are introduced. (1) Use con-tinuous time intervals to calculate the precision of clocks, which can reduce the effect of network delay effciently. (2) Every node synchronizes its clock with its leader actively. In addition, a node self-adaptive model is presented, and the relationship between the clock precision and synchroniza-tion time is induced, hence a node can predict when it should begin the synchronization process.Detailed simulation and extension of this issue are provided at the end of the paper. The presented model is both practical and feasible.     

Joint QoS optimization for layered computational grid

Many existing grid resource allocation and scheduling algorithms mainly focus on isolated layers of the grid architecture. The inflexibility of the strict layering structure results in an inefficient utilization of the grid resources. This paper takes a system view of the computational grid and aims to jointly optimize global QoS by adopting cross-layer design. Cross-layer design is based on information exchange and joint optimization among multiple grid layers. Parameters from different layers are provided to a cross-layer optimizer, which selects the values of the layer specific parameters maximizing joint global QoS. The objective of the paper is to jointly optimize the parameters of all layers in a decentralized optimization problem and decompose joint QoS optimization into three sub problems at fabric layer, collective layer and application layer. In simulation part, we compare the performance of the global joint QoS optimization approach with application layer local optimization and resource layer local optimization approach, respectively.     

Parallel resource co-allocation for the computational grid

Resource co-allocation is one of the crucial problems affecting the utility of the grid. Because the numbers of the application tasks and amounts of required resources are enormous and quick responses to the requirements of users are necessary in the real grid environment, real-time resource co-allocation may be large-scale. A parallel resource co-allocation algorithm based on the framework for mapping with resource co-allocation is proposed in this paper. Through the result of experiments, it is concluded that the parallel method reduces the execution time of the resource co-allocation algorithm significantly, and makes the overall response time to the end-users small.     

A novel scheduling model for computational grid using quantum genetic algorithm

The Computational Grid (CG) provides a wide distributed platform for high end computing intensive applications. Scheduling on Computational grid is known to be NP-Hard problem and requires an efficient solution. Recently, quantum inspired computing has been introduced in the literature to solve such a complex combinatorial optimization problem efficiently. Combination of Genetic Algorithm (GA) and quantum concept evolves a new meta-heuristic technique known as Quantum Genetic Algorithms (QGA). QGA is a search procedure based on evolutionary computation and Quantum Computing (QC). This paper proposes a novel technique of scheduling in computational grid using QGA. The work simulates the model to study its performance. It also makes a comparative study with a GA-based scheduling model. Simulation results reveal the effectiveness of the model.     

A global optimization approach for three layers of computational grid stack

This paper presents a global optimization approach for three layers of grid stack. In grid environment, the Quality of Service (QoS) needs to be supported at every layer of the grid architecture. However, less attention has been paid to incorporating QoS at multiple layers of the grid architecture. The primary objective of most existing scheduling mechanisms is to improve QoS at single grid layer, while the QoS optimization at multiple grid layers is seldom considered. In the paper, we consider the requirements of fabric layer, collective layer and application layer at the same time, and propose a global optimization approach for three layers of grid stack. The paper deals with global optimization as optimization decomposition. The global optimization for three layers of grid stack can be decomposed into three sub-problems at different grid layers: resource allocation at the fabric layer, service integration at the collective layer, and application QoS optimization problem at the application layer. A distributed iterative algorithm for three-layer optimization is proposed. The convergence of the iterative algorithm is proved. The simulations are conducted to test Three-Layer Optimization Algorithm.     

Security‐aware scheduling model for computational grid

Grid applications with stringent security requirements introduce challenging concerns because the schedule devised by nonsecurity‐aware scheduling algorithms may suffer in scheduling security constraints tasks. To make security‐aware scheduling, estimation and quantification of security overhead is necessary. The proposed model quantifies security, in the form of security levels, on the basis of the negotiated cipher suite between task and the grid‐node and incorporates it into existing heuristics MinMin and MaxMin to make it security‐aware MinMin(SA) and MaxMin(SA). It also proposes SPMaxMin (Security Prioritized MinMin) and its comparison with three heuristics MinMin(SA), MaxMin(SA), and SPMinMin on heterogeneous grid/task environment. Extensive computer simulation results reveal that the performance of the various heuristics varies with the variation in computational and security heterogeneity. Its analysis over nine heterogeneous grid/task workload situations indicates that an algorithm that performs better for one workload degrades in another. It is conspicuous that for a particular workload one algorithm gives better makespan while another gives better response time. Finally, a security‐aware scheduling model is proposed, which adapts itself to the dynamic nature of the grid and picks the best suited algorithm among the four analyzed heuristics on the basis of job characteristics, grid characteristics, and desired performance metric. Copyright © 2011 John Wiley & Sons, Ltd.     

Cross-layer optimization policy for QoS scheduling in computational grid

This paper presents a cross-layer quality of service (QoS) optimization policy for computational grid. Efficient QoS management is critical for computational grid to meet heterogeneity and dynamics of resources and users’ requirements. There are different QoS metrics at different layers of computational grid. To improve perceived QoS by end users over computational grid, QoS supports can be addressed in different layers, including application layer, collective layer, fabric layer and so forth. The paper tackles cross-layer grid QoS optimization as optimization decomposition, each layer corresponds to a decomposed subproblem. The proposed policy produces an optimal set of grid resources, service compositions and user's payments at the fabric layer, collective layer and application layer respectively to maximize global grid QoS. The cross-layer optimization problem decomposes into three subproblems: grid resource allocation problem, service composing and user satisfaction degree maximization problem, all of which interact through the optimal variables for capacities of grid resources and service demand. In order to coordinate the subproblems, cross-layer QoS feedback mechanism is established to ensure different layer interactions. The simulations are conducted to validate the efficiency of the proposed policy.     

Utility-driven solution for optimal resource allocation in computational grid

Optimal resource allocation is a complex undertaking due to large-scale heterogeneity present in computational grid. Traditionally, the decision based on certain cost functions has been used in allocating grid resource as a standard method that does not take resource access cost into consideration. In this paper, the utility function is presented as a promising method for grid resource allocation. To tackle the issue of heterogeneous demand, the user's preference is represented by utility function, which is driven by a user-centric scheme rather than system-centric parameters adopted by cost functions. The goal of each grid user is to maximize its own utility under different constraints. In order to allocate a common resource to multiple bidding users, the optimal solution is achieved by searching the equilibrium point of resource price such that the total demand for a resource exactly equals the total amount available to generate a set of optimal user bids. The experiments run on a Java-based discrete-event grid simulation toolkit called GridSim are made to study characteristics of the utility-driven resource allocation strategy under different constraints. Results show that utility optimization under budget constraint outperforms deadline constraint in terms of time spent, whereas deadline constraint outperforms budget constraint in terms of cost spent. The conclusion indicates that the utility-driven method is a very potential candidate for the optimal resource allocation in computational grid.     

A survey of computational approaches to three-dimensional layout problems

The component layout or packaging problem requires efficient search of large, discontinuous spaces. This survey paper reviews the state-of-the-art in product layout algorithms. The focus on optimization and geometric interference calculation strategies addresses the common aspects of the layout problem for all applications.     

A computational economy for grid computing and its implementation in the Nimrod-G resource broker

Computational grids that couple geographically distributed resources such as PCs, workstations, clusters, and scientific instruments, have emerged as a next generation computing platform for solving large-scale problems in science, engineering, and commerce. However, application development, resource management, and scheduling in these environments continue to be a complex undertaking. In this article, we discuss our efforts in developing a resource management system for scheduling computations on resources distributed across the world with varying quality of service (QoS). Our service-oriented grid computing system called Nimrod-G manages all operations associated with remote execution including resource discovery, trading, scheduling based on economic principles and a user-defined QoS requirement. The Nimrod-G resource broker is implemented by leveraging existing technologies such as Globus, and provides new services that are essential for constructing industrial-strength grids. We present the results of experiments using the Nimrod-G resource broker for scheduling parametric computations on the World Wide Grid (WWG) resources that span five continents.     

Multi economic agent interaction for optimizing the aggregate utility of grid users in computational grid

This paper investigates the interactions between agents representing grid users and the providers of grid resources to maximize the aggregate utilities of all grid users in computational grid. It proposes a price-based resource allocation model to achieve maximized utility of grid users and providers in computational grid. Existing distributed resource allocation schemes assume the resource provider to be capable of measuring user’s resource demand, calculating and communicating price, none of which actually exists in reality. This paper addresses these challenges as follows. First, the grid user utility is defined as a function of the grid user’s the resource units allocated. We formalize resource allocation using nonlinear optimization theory, which incorporates both grid resource capacity constraint and the job complete times. An optimal solution maximizes the aggregate utilities of all grid users. Second, this paper proposes a new optimization-based grid resource pricing algorithm for allocating resources to grid users while maximizing the revenue of grid providers. Simulation results show that our proposed algorithm is more efficient than compared allocation scheme. Li Chunlin received the ME in computer science from Wuhan Transportation University in 2000, and PhD degree in Computer Software and Theory from Huazhong University of Science and Technology in 2003. She now is an associate professor of Computer Science in Wuhan University of Technology. Her research interests include computational grid, distributed computing and mobile agent. She has published over 15 papers in international journals. Li Layuan received the BE degree in Communication Engineering from Harbin Institute of Military Engineering, China in 1970 and the ME degree in Communication and Electrical Systems from Huazhong University of Science and Technology, China in 1982. Since 1982, he has been with the Wuhan University of Technology, China, where he is currently a Professor and PhD tutor of Computer Science, and Editor in Chief of the Journal of WUT. He is Director of International Society of High-Technol and Paper Reviewer of IEEE INFOCOM, ICCC and ISRSDC. His research interests include high speed computer networks, protocol engineering and image processing. Professor Li has published over 150 technical papers and is the author of six books. He also was awarded the National Special Prize by the Chinese Government in 1993.     

基于风险策略的多单元连续双向拍卖的网格资源分配

针对计算网格资源的特点,提出一种基于风险策略的多单元连续双向拍卖的网格资源分配机制,实现对网格资源灵活有效的管理。首先,介绍了基于多单元连续双拍卖的网格资源分配框架。其次,针对计算网格资源的有限性,提出了RB2-MCDA机制。RB2-MCDA机制是在多单元连续双向拍卖中,代理采用Risk-Based2策略进行资源交易。Risk-Based2策略是一种基于风险行为的代理策略。实验结果表明,在不同规模的有限资源的计算网格中采用RB2-MCDA机制能够实现较高的资源分配效率,当资源需求量接近供给量时,分配效率超过99%。     

Maximizing availability for task scheduling in computational grid using genetic algorithm

Computational grid provides a wide distributed platform for high‐end compute intensive applications. Grid scheduling is often carried out to schedule the submitted jobs on the nodes of the grid so that some characteristic parameter is optimized. Availability of the computational nodes is one of the important characteristic parameters and measures the probability of the node availability for job execution. This paper addresses the availability of the grid computational nodes for the job execution and proposes a model to maximize it. As such, the task scheduling problem in grid is nondeterministic polynomial‐time hard, and often, metaheuristics techniques are applied to solve it. Genetic algorithm, a metaheuristic technique based on evolutionary computation, has been used to solve such complex optimization problem. This work proposes a technique for the grid scheduling problem using genetic algorithm with the objective to maximize availability. Simulation experiment, to evaluate the performance of the proposed algorithm, is conducted, and results reveal the effectiveness of the model. A comparative study has also been performed. Copyright © 2014 John Wiley & Sons, Ltd.     

A novel approach of three-dimensional hybrid grid methodology: Part 2. Flow solution

Following the previous paper of this series, which addresses the generation approach of three-dimensional DRAGON grids, we demonstrate the capability of effectively performing three-dimensional flow calculations for multi-components complex configurations. The flow solution is conducted by means of using a seamlessly integrated package made up of two well-validated NASA solvers, which are structured- and unstructured-grid codes, respectively.     

一种面向随机性负载的计算网格资源预留定价策略

针对传统预留机制对本地任务服务质量造成的负面影响,提出了基于预留收益与损失均衡的资源预留机制。首先,基于本地任务相关统计特性利用概率论方法,给出并证明了一段时间内本地任务执行时间之和的概率分布函数。然后,在资源提供者的效用中考虑本地任务可能带来的损失,求解出了为保障本地任务服务质量的最低资源价格。实验结果表明,提出的预留机制能有效保障本地任务的服务质量,提高资源利用率、降低任务拒绝率。     

A novel approach of three-dimensional hybrid grid methodology: Part 1. Grid generation

We propose a novel approach of three-dimensional hybrid grid methodology, the DRAGON grid method in the three-dimensional space. The DRAGON grid is created by means of a Direct Replacement of Arbitrary Grid Overlapping by Nonstructured grid, and is structured-grid dominated with unstructured grids in small regions. The DRAGON grid scheme is an adaptation to the Chimera thinking. It is capable of preserving the advantageous features of both the structured and unstructured grids, and eliminates/minimizes their shortcomings. In the present paper, we describe essential and programming aspects, and challenges of the three-dimensional DRAGON grid method, with respect to grid generation. We demonstrate the capability of generating computational grids for multi-components complex configurations.     

基于Globus Toolkit和SunTM ONE Grid Engine构建计算网格

网格计算(grid computing)是近几年发展起来的一个崭新研究领域,引起国内外学术界及工业界的广泛关注。其目的是研究如何安全有效地将现有的各种计算资源(尤其是那些分布在Internet的异构网络中的计算资源)组织起来协同解决复杂的科学及工程计算问题。在化学信息学和生物信息学中最典型的应用是虚拟高通量筛选侯选药物分子。本文以两个Linux机群为基础,用开放源码的网格支持软件包Globus Toolkit 3．2及Sun^TM ONE Grid Engine 5．3成功构建了计算网格;并通过设计测试程序实现一次性提交多个作业(300个)以及分析作业在计算网格中各个节点的分配及运行情况,从而测试了计算网格的效率。结果表明,所构建的计算网格在保持原机群运行稳定、可靠的前提下,改进了系统资源的分配管理方式以及用户提交作业的方法,从整体上提高了网络计算资源的利用率,也同时方便了系统的管理。     

A method for particle location and field interpolation on complex, three-dimensional computational meshes

A method for locating particles within arbitrary three-dimensional computational meshes is described. It is based on an iterative procedure which uses transformed coordinates defined by iso-parametric functions. The method also enables one to interpolate field values from the mesh nodes to the particle position. Example applications demonstrate how effective the method is. For very distorted computational cells special practices have to be introduced in order to keep the number of iterations to a minimum.     

三维网格图的零可视警察与强盗博弈算法

警察与强盗博弈是一个图搜索问题,解决该问题的关键是确定能成功捕获强盗的最少警察数.在零可视警察与强盗博弈中强盗不可见:任意时刻警察都不知道强盗所在位置.通过建立顶点清理模型对三维网格图的性质进行分析,将三维网格图的顶点集划分成2个子集,导出划分中较小子集与边界的关系,并利用划分中的结论,给出三维网格图中最少警察数的下界...