PaGrid: A Mesh Partitioner for Computational Grids

Computational Grids are emerging as a new infrastructure for high performance computing. Since the resources in a Grid can be heterogeneous and distributed, mesh-based applications require a mesh partitioner that considers both processor and network heterogeneity. We have developed a heterogeneous mesh partitioner, called PaGrid. PaGrid uses a multilevel graph partitioning approach, augmented by execution time load balancing in the final uncoarsening phase. We show that minimization of total communication cost (e.g., as used by JOSTLE) can lead to significant load being placed on processors connected by slow links, which results in higher application execution times. Therefore, PaGrid balances the estimated execution time of the application across processors. PaGrid performance is compared with two existing mesh partitioners, METIS 4.0 and JOSTLE 3.0, for mapping several application meshes to two models of heterogeneous computational Grids. PaGrid is found to produce significantly better partitions than JOSTLE and slightly better partitions than METIS in most cases, in terms of estimated application execution time averaged over a large number of runs with different random number seeds.     

Market-oriented Grids and Utility Computing: The State-of-the-art and Future Directions

Traditional resource management techniques (resource allocation, admission control and scheduling) have been found to be inadequate for many shared Grid and distributed systems, that consist of autonomous and dynamic distributed resources contributed by multiple organisations. They provide no incentive for users to request resources judiciously and appropriately, and do not accurately capture the true value, importance and deadline (the utility) of a user’s job. Furthermore, they provide no compensation for resource providers to contribute their computing resources to shared Grids, as traditional approaches have a user-centric focus on maximising throughput and minimising waiting time rather than maximising a providers own benefit. Consequently, researchers and practitioners have been examining the appropriateness of ‘market-inspired’ resource management techniques to address these limitations. Such techniques aim to smooth out access patterns and reduce the chance of transient overload, by providing a framework for users to be truthful about their resource requirements and job deadlines, and offering incentives for service providers to prioritise urgent, high utility jobs over low utility jobs. We examine the recent innovations in these systems (from 2000–2007), looking at the state-of-the-art in price setting and negotiation, Grid economy management and utility-driven scheduling and resource allocation, and identify the advantages and limitations of these systems. We then look to the future of these systems, examining the emerging ‘Catallaxy’ market paradigm. Finally we consider the future directions that need to be pursued to address the limitations of the current generation of market oriented Grids and Utility Computing systems.     

Computational and data Grids in large-scale science and engineering

As the practice of science moves beyond the single investigator due to the complexity of the problems that now dominate science, large collaborative and multi-institutional teams are needed to address these problems. In order to support this shift in science, the computing and data-handling infrastructure that is essential to most of modern science must also change in order to support this increased complexity. This is the goal of computing and data Grids: software infrastructure that facilitates solving large-scale problems by providing the mechanisms to access, aggregate, and manage the computer network-based infrastructure of science. This infrastructure includes computing systems, data archive systems, scientific instruments, and computer-mediated human collaborations. This paper examines several large-scale science problems, their requirements for computing and data Grid infrastructure, and the current approaches to providing the necessary functionality.     

Characterizing the computational power of energy-based P systems

We investigate the computational power of energy-based P systems, a model of membrane systems, where a fixed amount of energy is associated with each object and the rules transform single objects by adding or removing energy from them. We answer the recently proposed open questions about the power of such systems without priorities associated with the rules, for both sequential and maximally parallel modes. We also conjecture that deterministic energy-based P systems are not computationally complete.     

Enhancing Computational Grids with Peer-to-Peer Technology for Large Scale Service Discovery

Within computational Grids, some services (typically software components, e.g., linear algebra libraries) are made available by some servers to some clients. In spite of the growing popularity of such Grids, the service discovery, although efficient in many cases, does not reach several requirements. Among them, the flexibility of the discovery and its efficiency on wide-area dynamic platforms are two major issues. Therefore, it becomes crucial to propose new tools coping with such platforms. Emerging peer-to-peer technologies provide algorithms allowing the distribution and the retrieval of data items while addressing the dynamicity of the underlying network. Whereas merging peer-to-peer technology and Grid infrastructures has been widely suggested, very few implementations are available. The contribution of this paper is twofold. First, we present the design, the implementation and the experimentation of the first architecture, to our knowledge, extending traditional Network-Enabled Servers (NES) systems with an unstructured peer-to-peer network. This extension allows to dynamically connect distributed agents thus providing to clients an entry point to servers geographically distributed. Our implementation is based on the Diet middleware and the JXTA toolbox and experimentation have been conducted on a high speed network. Then, we study the service discovery in a pure peer-to-peer environment. We describe a new trie-based approach for the peer-to-peer service discovery service, supporting range queries while providing fault-tolerance and taking into account the topology of the underlying network. We validate this approach both by analysis and simulation. This work has been supported in part by the ANR project LEGO (ANR-05-CIGC-11).     

A Launch-time Scheduling Heuristics for Parallel Applications on Wide Area Grids

Large and dynamic computational Grids, generally known as wide-area Grids, are characterized by a large availability, heterogene- ity on computational resources, and high vari- ability on their status during the time. Such Grid infrastructures require appropriate schedule mechanisms in order to satisfy the application performance requirements (QoS). In this paper we propose a launch-time heuristics to schedule component-based parallel applications on such kind of Grid. The goal of the proposed heuristics is threefold: to meet the minimal task computation- al requirement, to maximize the throughput between communicating tasks, and to evaluate on-the-fly the resource availability to minimize the aging effect on the resources state. We evaluate the proposed heuristics by simulations applying it to a suite of task graphs and Grid platforms randomly generated. Moreover, a further test was conducted to schedule a real application on a real Grid. Experimental results shown that the proposed solution can be a viable one.     

Auctioning resources in Grids: model and protocols

In this paper, we propose and study an auction model for resource management in Grids. We propose and investigate by simulation three types of auction‐based resource‐allocation protocols: (i) first‐price auction protocol; (ii) Vickrey auction protocol; and (iii) double auction protocol. The goal is to find which of these is best suited to the Grid environment from the users' perspective as well as from the resources' perspective. The results showed that when we consider a mix of risk‐averse and risk‐neutral users, the first‐price auction protocol favors resources while the Vickrey auction protocol favors users. On the other hand, the double auction protocol favors both users and resources. Copyright © 2006 John Wiley & Sons, Ltd.     

Simulation Studies of Computation and Data Scheduling Algorithms for Data Grids

Data Grids seek to harness geographically distributed resources for large-scale data-intensive problems. Such problems, involving loosely coupled jobs and large data-sets, are found in fields like high-energy physics, astronomy and bioinformatics. A variety of factors need to be considered for effective scheduling of resources in such environments: e.g., resource utilization, response time, global and local allocation policies and scalability. We propose a general and extensible scheduling architecture that addresses these issues. Within this architecture we develop a suite of job scheduling and data replication algorithms that we evaluate using simulations for a wide range of parameters. Our results show that it is important to evaluate the combined effectiveness of replication and scheduling strategies, rather than study them separately. More specifically, we find that scheduling jobs to locations that contain the data they need and asynchronously replicating popular data-sets to remote sites, works rather well.     

具有自主计算特征的计算网格资源备份服务系统

设计了具有自主计算特征的计算网格资源备份服务系统,该系统采用了先进的自主计算思想,具有一定程度的自识别、自感知、自管理、自组织、自优化、自稳定和自愈合的能力。     

Grids and Grid technologies for wide‐area distributed computing

The last decade has seen a substantial increase in commodity computer and network performance, mainly as a result of faster hardware and more sophisticated software. Nevertheless, there are still problems, in the fields of science, engineering, and business, which cannot be effectively dealt with using the current generation of supercomputers. In fact, due to their size and complexity, these problems are often very numerically and/or data intensive and consequently require a variety ofheterogeneous resources that are not available on a single machine. A number of teams have conducted experimental studies on the cooperative use of geographically distributed resources unified to act as a single powerful computer. This new approach is known by several names, such as metacomputing, scalable computing, global computing, Internet computing, and more recently peer‐to‐peer or Grid computing. The early efforts in Grid computing started as a project to link supercomputing sites, but have now grown far beyond their original intent. In fact, many applications can benefit from the Grid infrastructure, including collaborative engineering, data exploration, high‐throughput computing, and of course distributed supercomputing. Moreover, due to the rapid growth of the Internet and Web, there has been a rising interest in Web‐based distributed computing, and many projects have been started and aim to exploit the Web as an infrastructure for running coarse‐grained distributed and parallel applications. In this context, the Web has the capability to be a platform for parallel and collaborative work as well as a key technology to create a pervasive and ubiquitous Grid‐based infrastructure. This paper aims to present the state‐of‐the‐art of Grid computing and attempts to survey the major international efforts in developing this emerging technology. Copyright © 2002 John Wiley & Sons, Ltd.     

分布式概念格的属性约简研究

概念格的属性约简是形式化概念分析理论的重要研究内容之一,传统的格属性约简方法主要是针对非分布式环境下单个形式背景的,而随着数据分布存储和处理的广泛应用,研究基于分布式环境下概念格的属性约简具有重要的意义.为此,提出属性的超集和确定集的概念,刻画了形式背景中不同类型属性的局部特征与全局特征,推导出属性约简的判定定理;在此基础上,给出计算分布式环境下概念格属性约简的ADSCL和DRCL算法.ADSCL算法用于计算属性的超集和最小确定集,这些约简信息将作为DRCL算法的输入,以计算得到全局形式背景的约简.理论分析和实验结果表明,该算法是有放可行的.     

密码计算网格的计算节点控制系统设计与实现

密码计算需要强大的计算能力,而网格计算作为一种新型有效的计算技术,能广泛集合网络上的资源形成一台虚拟的超级计算机.因此,把网格技术应用到密码学计算中具有重大的意义.介绍了一种密码计算网格系统的框架设计,并对其中的计算节点控制管理模块进行了详细设计和实现.此系统在DES穷举攻击实验中取得了非常好的效果,其它一些密码计算任务类似地也可用此系统分布式地实现.     

基于网格的分布式数据挖掘

针对分布式数据挖掘和网格计算的特点,本文详细分析了目前主流的几种网格体系结构,设计了一种基于开放网格服务架构的Web服务资源框架的分布式数据挖掘整体架构,通过应用描述了它们的具体数据挖掘流程。应用结果验证了该架构在网格环境下进行分布式数据挖掘的可行性和高效性。     

内存网格中的自主协同缓存技术研究

本文基于原有工作提出了利用内存网格进行磁盘缓存的技术,从而组织和共享网络上分布的空闲内存资源,提高具有大量磁盘IO的节点的系统性能;给出了一种基本设计方案,并提出了缓存节点的时间分布和空间合并等自主协同机制,进一步优化了系统性能;最后通过基于实际采集数据的模拟,对方案进行了评价。     

On the Expressive Power of Abstract Categorial Grammars: Representing Context-Free Formalisms

We show how to encode context-free string grammars, linear context-free tree grammars, and linear context-free rewriting systems as Abstract Categorial Grammars. These three encodings share the same constructs, the only difference being the interpretation of the composition of the production rules. It is interpreted as a first-order operation in the case of context-free string grammars, as a second-order operation in the case of linear context-free tree grammars, and as a third-order operation in the case of linear context-free rewriting systems. This suggest the possibility of defining an Abstract Categorial Hierarchy.     

Scheduling parameter sweep applications on global Grids: a deadline and budget constrained cost–time optimization algorithm

Computational Grids and peer‐to‐peer (P2P) networks enable the sharing, selection, and aggregation of geographically distributed resources for solving large‐scale problems in science, engineering, and commerce. The management and composition of resources and services for scheduling applications, however, becomes a complex undertaking. We have proposed a computational economy framework for regulating the supply of and demand for resources and allocating them for applications based on the users' quality‐of‐service requirements. The framework requires economy‐driven deadline‐ and budget‐constrained (DBC) scheduling algorithms for allocating resources to application jobs in such a way that the users' requirements are met. In this paper, we propose a new scheduling algorithm, called the DBC cost–time optimization scheduling algorithm, that aims not only to optimize cost, but also time when possible. The performance of the cost–time optimization scheduling algorithm has been evaluated through extensive simulation and empirical studies for deploying parameter sweep applications on global Grids. Copyright © 2005 John Wiley & Sons, Ltd.     

Dimensioning and on-line scheduling in Lambda Grids using divisible load concepts

Due to the large amounts of data required to be processed by the typical Grid job, it is conceivable that the use of optical transport networks in Grid deployment (hence the term “Lambda Grid”) will increase. The exact topology of the interconnecting network is obtained by solving a dimensioning problem, and the outcome of this strongly depends on both the expected workload characteristics and Grid scheduling policy. Solving this combined scheduling and dimensioning problem using straightforward ILP modelling is cumbersome; however, for steady-state Grid operation, Divisible Load Theory (DLT) can yield scalable formulations of this problem. In this paper, the on-line hierarchical scheduling on a lambda Grid of workload approaching the Grid’s capacity in a two-tier Grid mode of operation is studied. A number of these algorithms are goal-driven, in the sense that target per-resource goals are obtained from the off-line solution to the Divisible Load model. We compare these on-line multiresource scheduling policies for different workloads, Grid interconnection topologies and Grid parameters. We show that these algorithms perform well in the studied scenarios when compared to a fully centralized scheduling algorithm.

Labs of the World, Unite!!!

eScience is rapidly changing the way we do research. As a result, many research labs now need non-trivial computational power. Grid and voluntary computing are well-established solutions for this need. However, not all labs can effectively benefit from these technologies. In particular, small and medium research labs (which are the majority of the labs in the world) have a hard time using these technologies as they demand high visibility projects and/or high-qualified computer personnel. This paper describes OurGrid, a system designed to fill this gap. OurGrid is an open, free-to-join, cooperative Grid in which labs donate their idle computational resources in exchange for accessing other labs’ idle resources when needed. It relies on an incentive mechanism that makes it in the best interest of participants to collaborate with the system, employs a novel application scheduling technique that demands very little information, and uses virtual machines to isolate applications and thus provide security. The vision is that OurGrid enables labs to combine their resources in a massive worldwide computing platform. OurGrid is in production since December 2004. Any lab can join it by downloading its software from .     

基于非结构网格隐式算法的GPU加速研究

针对非结构网格隐式算法在GPU上的加速效果不佳的问题,通过分析GPU的架构及并行模式,研究并实现了基于非结构网格格点格式的隐式LU-SGS算法的GPU并行加速.通过采用RCM和Metis网格重排序（重组）方法,优化非结构网格的数据局部性,改善非结构网格的隐式算法在GPU上的并行加速效果.通过三维机翼算例验证了本文实现的正确性及效率.结果表明两种网格重排序（重组）方法分别得到了63%和69%的加速效果提高.优化后的LU-SGS隐式GPU并行算法获得了相较于CPU串行算法27倍的加速比,充分说明了本文方法的高效性.