RSG地形的矢量视域改进算法

针对视域分析改进算法及其矢量化进行研究,提出了一种基于局部最优检测和高程限制的改进通视性算法。介绍了空间中两点通视性问题的基本算法;给出了局部最优单调区间的定义;通过分析视线方向与地形遮挡点之间的关系,提出了基于局部最优区间和最大高程限制的通视性改进算法,给出了算法的实现方法;改进算法只对一般高程点进行局部最优判断,而只对点序列中相对较少的一部分点进行完整的通视性计算,因此改进算法在收敛速度方面得到了明显改善;最后,通过程序仿真对改进算法进行了验证,并利用改进算法进行了视域分析与矢量化仿真。     

Fault-tolerant Resource Discovery in Peer-to-peer Grids

Peer-to-peer overlay technologies offer several advantages over centralized solutions to managing desktop Grids. We present a new hybrid approach to resource discovery in P2P Grids, i.e. desktop Grids based on peer-to-peer overlays. This approach combines the advantages of information propagation based on spanning trees in chord-like structured overlays and epidemic algorithms. We provide a mathematical model for predicting the process of information dissemination and verify its prediction quality in various evaluations. Moreover, we show the failure resistance of the proposed approach in several scenarios. In particular, we demonstrate the efficiency of our approach even in scenarios where 50% of the peers in the overlay fail in short time.     

基于网格法的等值线绘制方法

等值线是一种形和数的统一。在许多领域是成果数据表示的重要图件之一。时工程应用中的等值线图的绘制方法进行了研究，常规的等值线绘制方法分为矩形网格法和不规则三角形网法2种，矩形网格法具有算法简单的优点。其绘制的步骤一般为：离散数据网格化、网格点数值化、等值点的计算、等值线的追踪、光滑和标记等值线。详细阐述了采用矩形网格法绘制的步骤及其计算机实现。采用Delphi开发了运用该法绘制等值线的软件，可应用于不同的操作平台，移植性好。     

An Adaptive Scheduler for Grids

The recent development of telecommunication infra-structures such as the world-wide networks, interconnecting millions of computers spread all over the world, has made possible the coordinated use of a large amount of heterogeneous, weakly connected computational resources. This new area, known as Grid computing, is currently the focus of several research activities and projects. However, as in every new domain of research, in this one there are many unsolved questions, in particular those related to the management of the processing load inside the system. In this work, the problem of balancing processing loads on a Grid is approached by the introduction of the Generational Scheduling with Task Replication (GSTR) algorithm. A comprehensive set of simulations and tests is carried out in order to validate the proposed solution. A methodology for calculating and analyzing speed-up and efficiency ratios on heterogeneous groups of computers is also shown.     

AnO(logk)-approximation algorithm for thek minimum spanning tree problem in the plane

Givenn points in the Euclidean plane, we consider the problem of finding the minimum tree spanning anyk points. The problem isNP-hard and we give anO(logk)-approximation algorithm.     

Scheduling for Responsive Grids

Grids are facing the challenge of seamless integration of the Grid power into everyday use. One critical component for this integration is responsiveness, the capacity to support on-demand computing and interactivity. Grid sched uling is involved at two levels in order to provide responsiveness: the policy level and the implementation level. The main contributions of this paper are as follows. First, we present a detailed analysis of the performance of the EGEE Grid with respect to responsiveness. Second, we examine two user-level schedulers located between the general scheduling layer and the application layer. These are the DIANE (distributed analysis environment) framework, a general-purpose overlay system, and a specialized, embedded scheduler for gPTM3D, an interactive medical image analysis application. Finally, we define and demonstrate a virtualization scheme, which achieves guaranteed turnaround time, schedulability analysis, and provides the basis for differentiated services. Both methods target a brokering-based system organized as a federation of batch-scheduled clusters, and an EGEE implementation is described.     

Trusted Grid Computing with Security Binding and Trust Integration

Trusted Grid computing demands robust resource allocation with security assurance at all resource sites. Large-scale Grid applications are being hindered by lack of security assurance from remote resource sites. We developed a security-binding scheme through site reputation assessment and trust integration across Grid sites. We do not treat the trust factor deterministically. Instead, we apply fuzzy theory to handle the fuzziness or uncertainties behind all trust attributes. The binding is achieved by periodic exchange of site security information and matchmaking to satisfy user job demands. PKI-based trust model supports Grids in multi-site authentication and single sign-on operations. However, cross certificates are inadequate to assess local security conditions at Grid sites. We propose a new fuzzy-logic trust model for distributed trust aggregation through fuzzification and integration of security attributes. We introduce the trust index of a Grid site, which is determined by site reputation from its track record and self-defense capability attributed to the risk conditions and hardware and software defenses deployed at a Grid site. A Secure Grid Outsourcing (SeGO) system is designed for secure scheduling a large number of autonomous and indivisible jobs to Grid sites. Significant performance gains are observed after trust aggregation, which is evaluated by running scalable NAS and PSA workloads over simulated Grids. Our security-binding scheme scales well with increasing user jobs and Grid sites. The new scheme can guide the security upgrade of Grid sites and predict the Grid performance of large workloads under risky conditions. The research work reported here was supported by a NSF ITR Grant 0325409. The paper is significantly extended from preliminary results presented in IFIP International Conference on Network and Parallel Computing (NPC-2004), IEEE International Parallel and Distributed Processing Symposium (IPDPS-2005), and International Workshop on Grid Security and Resource Management (GSRM-2005). The corresponding author is Kai Hwang at the University of Southern California.     

Grid enabled magnetic resonance scanners for near real-time medical image processing

This paper presents the initial steps taken to integrate the University of California at San Francisco Radiology Department's magnetic resonance (MR) scanners with its high-performance computing (HPC) grid. The objective is to improve patient care by enabling near real-time, computationally intensive medical image processing, directly at an MR scanner. A graphical software tool is described that was developed to run on the MR scanners for submitting processing jobs to the Departmental grid. The computationally intensive parallel reconstruction and quantification of large, multi-dimensional MR spectroscopic imaging (MRSI) data sets was used as the prototype application for this system. Initial results indicate that real-time processing of medical imaging data on a shared HPC resource is reliable and possible in a clinically acceptable time of less than 5 min. The Department's HPC resource is comprised of hardware owned by multiple research groups at three separate University facilities throughout San Francisco.     

Analysis of DNA sequence transformations on grids

Study of the evolution of species or organisms is essential for various biological applications. Evolution is typically studied at the molecular level by analyzing the mutations of DNA sequences of organisms. Techniques have been developed for building phylogenetic or evolutionary trees for a set of sequences. Though phylogenetic trees capture the overall evolutionary relationships among the sequences, they do not reveal fine-level details of the evolution. In this work, we attempt to resolve various fine-level sequence transformation details associated with a phylogenetic tree using cellular automata. In particular, our work tries to determine the cellular automata rules for neighbor-dependent mutations of segments of DNA sequences. We also determine the number of time steps needed for evolution of a progeny from an ancestor and the unknown segments of the intermediate sequences in the phylogenetic tree. Due to the existence of vast number of cellular automata rules, we have developed a grid system that performs parallel guided explorations of the rules on grid resources. We demonstrate our techniques by conducting experiments on a grid comprising machines in three countries and obtaining potentially useful statistics regarding evolutions in three HIV sequences. In particular, our work is able to verify the phenomenon of neighbor-dependent mutations and find that certain combinations of neighbor-dependent mutations, defined by a cellular automata rule, occur with greater than 90% probability. We also find the average number of time steps for mutations for some branches of phylogenetic tree over a large number of possible transformations with standard deviations less than 2.     

Anticipating resource saturation in Federated Grids

In a dynamic and geographically distributed Federated Grid where resources are shared between system participants, there is a lack of mechanisms capable of reallocating already scheduled tasks based on grid infrastructure owners’ current internal needs. In this paper we propose a set of policies for both, users and owners, that aid owners to satisfy internal peak demands and users to achieve the best makespan despite the circumstances. As in our previous work, the main purpose is to do so in the least intrusive way possible to maintain software stack independence of all participants, and to save time and communication bandwidth by anticipating grid resources saturation. These strategies suppose a novel approach for decentralized and non-cooperative workflow scheduling in a federation of heterogeneous grid infrastructures. We evaluate and prove the feasibility of our policies through a set of simulations that reflect the worst case where all resources are saturated. The results show that, in the worst scenario, our scheduling mechanism is beneficial to big infrastructure owners since they can achieve their own internal objectives, as well as to small users since they can reach the best possible completion time.