Performance-reliability issues in distributed file systems

This paper discusses some policies for performance-reliability improvement in distributed file systems. File replication, file migration, and process migration are considered, and the decision whether to replicate a file, or to move a file or a process, is based on the workload demands on the system resources. The utilization of system components, especially that of the communication network, is important, and the system bottleneck and the hosts' bottlenecks are detected. A model of a distributed system is constructed and consists of a number of hosts connected by a communication network. Concurrency control policy allows transaction type access to the shared resources. A unit of concurrency control (i.e., entity to be locked) is a sector of a file. Concurrency control policy is a single writer or multiple readers. Two-phase locking protocol is used for transaction serialization.     

An adaptable vertical partitioning method in distributed systems

Vertical partitioning is a process of generating the fragments, each of which is composed of attributes with high affinity. The concept of vertical partitioning has been applied to many research areas, especially databases and distributed systems, in order to improve the performance of query execution and system throughput. However, most previous approaches have focused their attention on generating an optimal partitioning without regard to the number of fragments finally generated, which is called best-fit vertical partitioning in this paper. On the other hand, there are some cases that a certain number of fragments are required to be generated by vertical partitioning, called n-way vertical partitioning in this paper. The n-way vertical partitioning problem has not fully investigated.In this paper, we propose an adaptable vertical partitioning method that can support both best-fit and n-way vertical partitioning. In addition, we present several experimental results to clarify the validness of the proposed algorithm.     

分布式仿真系统中的全局一致性问题研究

系统一致是分布仿真应用DSA的基础和前提。为提高DSA的全局一致性程度,获得真实、可信的仿真结果,首先阐述了DSA全局一致性问题;然后以某分布仿真系统为例,系统阐述了其全局不一致现象;在此基础上,分析了DSA系统的全局一致性需求;最后,重点给出了模型域、服务域和认知域内的一致性控制策略与建议。本研究可为DSA系统设计与开发人员提供技术与方法指导。     

Fundamental issues in testing distributed real-time systems

This paper examines the fundamental problems that one faces when testing a distributed, hard real-time system. It specifically identifies the influences of the distributedness and of the real-time requirements of the systems considered. We show how the usual problems of testing become more difficult, and which additional problems are introduced, because of these additional system characteristics.We identify six such fundamental problems: Organization, Observability, Reproducibility, Host/Target Approach, Environment Simulation, and Representativity. These, as well as their interrelations, are presented in a general framework that is independent of a particular system architecture or application. This framework could serve as a starting point for all activities geared towards a particular system architecture or a specific application.As an example, we illustrate how these test problems have been handled when developing a test methodology for the distributed real-time system MARS. Finally, the additional issues of test data generation and test result analysis are briefly discussed.     

A partitioning algorithm for distributed software systems design

One complication in using distributed computer systems is the increased complexity of developing distributed software systems. These software systems are composed of asynchronously executing components which communicate via message passing. Current software design techniques are not adequate for use in the design of distributed software systems. New design methods which explicitly address the problem of system partitioning are needed. An overall distributed software design approach is presented. The key to the design approach is the presentation of a distributed processing component (DPC) partitioning algorithm for clustering functional modules in order to derive a set of distributed processing components. The design approach is oriented towards producing a software system which is hierarchical, which exploits potential concurrency that exists between functional modules, and which avoids nonprofitable message traffic.     

An efficient partitioning algorithm for distributed virtualenvironment systems

Distributed virtual environment (DVE) systems model and simulate the activities of thousands of entities interacting in a virtual world over a wide area network. Possible applications for DVE systems are multiplayer video games, military and industrial trainings, and collaborative engineering. In general, a DVE system is composed of many servers and each server is responsible to manage multiple clients who want to participate in the virtual world. Each server receives updates from different clients (such as the current position and orientation of each client) and then delivers this information to other clients in the virtual world. The server also needs to perform other tasks, such as object collision detection and synchronization control. A large scale DVE system needs to support many clients and this imposes a heavy requirement on networking resources and computational resources. Therefore, how to meet the growing requirement of bandwidth and computational resources is one of the major challenges in designing a scalable and cost-effective DVE system. In this paper, we propose an efficient partitioning algorithm that addresses the scalability issue of designing a large scale DVE system. The main idea is to dynamically divide the virtual world into different partitions and then efficiently assign these partitions to different servers. This way, each server will process approximately the same amount of workload. Another objective of the partitioning algorithm is to reduce the server-to-server communication overhead. The theoretical foundation of our dynamic partitioning algorithm is based on the linear optimization principle. We also illustrate how one can parallelize the proposed partitioning algorithm so that it can efficiently partition a very large scale DVE system. Lastly, experiments are carried out to illustrate the effectiveness of the proposed partitioning algorithm under various settings of the virtual world     

Parallel partitioning for distributed systems using sequential assignment

This paper introduces a method to combine the advantages of both task parallelism and fine-grained co-design specialisation to achieve faster execution times than either method alone on distributed heterogeneous architectures. The method uses a novel mixed integer linear programming formalisation to assign code sections from parallel tasks to share computational components with the optimal trade-off between acceleration from component specialism and serialisation delay. The paper provides results for software benchmarks partitioned using the method and formal implementations of previous alternatives to demonstrate both the practical tractability of the linear programming approach and the increase in program acceleration potential deliverable.     

小型分布式控制系统中共享存储器的使用

介绍在小型分布式控制系统中,使用共享存储器作为主机和通信处理器的接口,以提高系统的实时响应能力。叙述了主机和通信处理器在访问共享存储器时可能发生的冲突的解决方法,以及主机和通信处理器接口协议及其实现方法。     

Multilevel security issues in distributed database management systems

This paper describes the security needs in a distributed processing environment common to many enterprises and discusses the applicability of multilevel secure database management systems in such an environment.     

Materialisation and data partitioning algorithms for distributed RDF systems

Many RDF systems support reasoning with Datalog rules via materialisation, where all conclusions of RDF data and the rules are precomputed and explicitly stored in a preprocessing step. As the amount of RDF data used in applications keeps increasing, processing large datasets often requires distributing the data in a cluster of shared-nothing servers. While numerous distributed query answering techniques are known, distributed materialisation is less well understood. In this paper, we present several techniques that facilitate scalable materialisation in distributed RDF systems. First, we present a new distributed materialisation algorithm that aims to minimise communication and synchronisation in the cluster. Second, we present two new algorithms for partitioning RDF data, both of which aim to produce tightly connected partitions, but without loading complete datasets into memory. We evaluate our materialisation algorithm against two state-of-the-art distributed Datalog systems and show that our technique offers competitive performance, particularly when the rules are complex. Moreover, we analyse in depth the effects of data partitioning on reasoning performance and show that our techniques offer performance comparable or superior to the state of the art min-cut partitioning, but computing the partitions requires considerably less time and memory.     

A window-assisted video partitioning strategy for partitioning and caching video streams in distributed multimedia systems

In this paper, we address the issue of efficiently streaming a set of heterogenous videos under the constraint of service latency over a scalable multimedia systems. We propose a novel strategy, referred to as window-assisted video partitioning (WAVP), for rendering cost-effective multimedia services. The objective is to minimize the service cost and maximize the number of requests that can be successfully served under resources constraints (cache capacity and link bandwidth). We formulate the problem of video partitioning as an optimization of both bandwidth resources and cache space, and derive the optimal schedule window for different video portions under consideration of time constraints, the popularities and the sizes of the video portions. In WAVP, video are partitioned into multiple portions and delivered according to by adaptive schedule windows. We prove that WAVP strategy not only optimize the service cost but also be able to serve requests under the time constraints without causing too much delay. We conduct mathematical analysis and derive certain performance bounds that quantify the overall performance of the strategy. It shows that the service cost can be optimized by adjusting the schedule window and resources utilization can be improved as video streams are partitioned into multiple portions. We evaluate the performance under several influencing parameters such as available bandwidth, cache capacity, and partition gradients. Simulation results show that our proposed method can not only significantly reduce the service cost under tight time constraints and with low partition overhead, but also balance the utilization of network resources to achieve high acceptance ratio with low average service cost.     

Message scheduling for array re-decomposition on distributed memory systems

For many parallel applications on distributed memory systems, array re-decomposition is usually required to enhance data locality and reduce the communication overheads. How to effectively schedule messages to improve the performance of array re-decomposition has received much attention in recent years. This paper is devoted to develop efficient scheduling algorithms using the compiling information provided by array distribution patterns, array alignment patterns and the periodic property of array accesses. Our algorithms not only avoid inter-processor contention, but also reduces real communication cost and communication generation time. The experimental results show that the performance of array redecomposition can be significantly improved using our algorithms     

Macromolecular electron density averaging on distributed memory MIMD systems

The paper discusses algorithms and programs for electron density averaging using a distributed memory MIMD system. Electron density averaging is a computationally intensive step needed for phase refinement and extension in the computation of the 3-D structure of macromolecules like proteins and viruses. The determination of a single structure may require thousands of hours of CPU time for traditional supercomputers. The approach discussed in this paper leads to a reduction by one to two orders of magnitude of the computing time. The program runs on an Intel iPSC/860 and on the Touchstone Delta system and uses a user controlled shared virtual memory and a dynamic load-balancing mechanism.     

Reliable performance prediction for multigrid software on distributed memory systems

We propose a model for describing and predicting the parallel performance of a broad class of parallel numerical software on distributed memory architectures. The purpose of this model is to allow reliable predictions to be made for the performance of the software on large numbers of processors of a given parallel system, by only benchmarking the code on small numbers of processors. Having described the methods used, and emphasized the simplicity of their implementation, the approach is tested on a range of engineering software applications that are built upon the use of multigrid algorithms. Despite their simplicity, the models are demonstrated to provide both accurate and robust predictions across a range of different parallel architectures, partitioning strategies and multigrid codes. In particular, the effectiveness of the predictive methodology is shown for a practical engineering software implementation of an elastohydrodynamic lubrication solver.     

Synchronization and load imbalance effects in distributed memory multi-processor systems

Synchronization is a major cause of wasted computing cycles and of diminished performance in parallel computing. This paper investigates the effects of synchronization upon the performance of iterative methods on distributed memory MIMD machines. A quantitative analysis of the effects of the communication latency and of the load imbalance due to the non-deterministic execution times for iterative methods is presented. This analysis explains the rather poor performance observed often in actual implementations of such methods and suggests better ways to achieve convergence without frequent synchronization.     

Evaluation of markov program models in virtual memory systems

A first order Markov model of program behaviour is developed from FORTRAN program instruction data. The program model is evaluated by using it to generate page references for input into a simple virtual memory operating system (VMOS) simulation model. The actual trace data are also used to drive the VMOS model. In both cases the fault probability is obtained for different replacement rules, memory sizes and page sizes. A comparison of fault probabilities is used to determine the effectiveness of the Markov program model.     

A survey of recoverable distributed shared virtual memory systems

Distributed Shared Virtual Memory (DSVM) systems provide a shared memory abstraction on distributed memory architectures. Such systems ease parallel application programming because the shared-memory programming model is often more natural than the message-passing paradigm. However, the probability of failure of a DSVM increases with the number of sites. Thus, fault tolerance mechanisms must be implemented in order to allow processes to continue their execution in the event of a failure. This paper gives an overview of recoverable DSVMs (RDSVMs) that provide a checkpointing mechanism to restart parallel computations in the event of a site failure     

Optimizing memory access traffic via runtime thread migration for on-chip distributed memory systems

On-chip distributed memory system has become an attractive solution for massive parallel memory accesses found in future many-core processors. However, increasing number of on-chip cores and memory controllers inevitably introduce many remote memory accesses, which generate a large amount of on-chip traffic and put great pressure on the interconnection. This paper tries to optimize on-chip memory access traffic via runtime thread migration. We first analyze memory access behaviors in multi-threaded applications and find that the memory access targets and volumes are similar during short periods, which makes runtime prediction feasible. But the memory access targets exhibit great mobility during long periods, motivating us to dynamically move threads towards the data. Based on these observations, we propose a novel low-cost and distributed thread migration algorithm which adjusts thread placement in chains based on benefit estimation. We present details of the workflow, including the trigger and arbitration of migration requests and the procedures to determine the migration chains. Simulation results show that our algorithm achieves system performance speedup of 11.5 % and reduces average memory access latency by 11.0 %. It can find a few but effective thread migrations to optimize on-chip memory access traffic with acceptable hardware and runtime overheads.     

Relationships between broadcast and shared memory in reliable anonymous distributed systems

We study the power of reliable anonymous distributed systems, where processes do not fail, do not have identifiers, and run identical programmes. We are interested specifically in the relative powers of systems with different communication mechanisms: anonymous broadcast, read-write registers, or read-write registers plus additional shared-memory objects. We show that a system with anonymous broadcast can simulate a system of shared-memory objects if and only if the objects satisfy a property we call idemdicence this result holds regardless of whether either system is synchronous or asynchronous. Conversely, the key to simulating anonymous broadcast in anonymous shared memory is the ability to count: broadcast can be simulated by an asynchronous shared-memory system that uses only counters, but read-write registers by themselves are not enough. We further examine the relative power of different types and sizes of bounded counters and conclude with a non-robustness result. James Aspnes is a Professor of Computer Science at Yale University. He received his Ph.D. from Carnegie-Mellon University in 1992. Faith Ellen Fich is a Professor of Computer Science at the University of Toronto. She received her Ph.D. from the University of California, Berkeley in 1982. Eric Ruppert was educated at the University of Toronto, where he completed his doctorate in 1999. He spent a year as a postdoctoral fellow at Brown University and is an Associate Professor at York University.