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     

An adaptable distributed query processing architecture

Traditionally, distributed query optimization techniques generate static query plans at compile time. However, the optimality of these plans depends on many parameters (such as the selectivities of operations, the transmission speeds and workloads of servers) that are not only difficult to estimate but are also often unpredictable and fluctuant at runtime. As the query processor cannot dynamically adjust the plans at runtime, the system performance is often less than satisfactory. In this paper, we introduce a new highly adaptive distributed query processing architecture. Our architecture can quickly detect fluctuations in selectivities of operations, as well as transmission speeds and workloads of servers, and accordingly change the operation order of a distributed query plan during execution. We have implemented a prototype based on the Telegraph system [Telegragraph project. Available from >]. Our experimental study shows that our mechanism can adapt itself to the changes in the environment and hence approach to an optimal plan during execution.     

An assignment method for IPUs in distributed systems

In a distributed system,one of the most important thing is to establish an assignment method for distributing tasks.It is assumed that a distributed system does not have a central administrator,all independent processing units in this system want to cooperate for the best results,but they cannot know the conditions of one another,So in order to undertake the tasks in admirable proportions,they have to adjust their undertaking tasks only by selt-learning.In this paper,the performance of this system is analyzed by Markov chains,and a robust method of self-learning for independent processing units in this kind of systems is presented.This method can lead the tasks of the system to be distributed very well among all the independent processing units,and can also be used to solve the general assignment problem.     

DIN-A-MIT: An adaptable,distributed computer-based message system

A distributed computer-based message system in a heterogenous local computer network is introduced. DIN-A-MIT — a system of the basic modules User-Agent, Post-Station, User-Record-Base and Message-Base — can be used for varied purposes such as a Mail, a (network-) Status and a Library service. So-called “user-records” which “float” in the system due to the mobility of the user contain the link information for messages stored on different computers. One-to-one and one-to-many messages are possible by assigning attributes which represent either a unique user-name or an interest group. In all cases only a single message copy is stored. Implementation takes place in a portable subset of PASCAL based on a standardized FORTRAN interface to the network.     

Run-time issues in program partitioning on distributed memory systems

Our earlier work reported a Threshold Scheduling Method for compile-time mapping of functional parallism on distributed-memory systems. The work reported in this paper discusses run-time issues in efficiently supporting the functional parallism with minimal overheads, through a combination of compile-time and run-time ownership analysis. At compile time, the code generation phase determines whether a local copy of a live definition of a variable needed by a task is available on a given processor, through an ownership analysis. In case ownership cannot be resolved at compile time, an appropriate code is generated to perform analysis at run time. The code generation is carried out so that all the processors carry the same copy of the compiled program with the individual processor's code being isolated and the universally owned code being replicated on all processors to minimize run-time overheads. The run-time system maintains the static and dynamic ownerships at every processor to avoid communication overhead on ownership information. We demonstrate the approach by incorporating it in the compiler for targeting a parallel functional language, Sisal (streams and iterations in single assignment language), to Intel Touchstone i860 systems. Several benchmarks demonstrate the viability of the approach.     

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.     

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.     

A geometric partitioning method for distributed tomographic reconstruction

Tomography is a powerful technique for 3D imaging of the interior of an object. With the growing sizes of typical tomographic data sets, the computational requirements for algorithms in tomography are rapidly increasing. Parallel and distributed-memory methods for tomographic reconstruction are therefore becoming increasingly common. An underexposed aspect is the effect of the data distribution on the performance of distributed-memory reconstruction algorithms. In this work, we introduce a geometric partitioning method, which takes into account the acquisition geometry and aims to minimize the necessary communication between nodes for distributed-memory forward projection and back projection operations. These operations are crucial subroutines for an important class of reconstruction methods. We show that the choice of data distribution has a significant impact on the runtime of these methods. With our novel partitioning method we reduce the communication volume drastically compared to straightforward distributions, by up to 90% for a number of cases, and furthermore we guarantee a specified load balance.     

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.     

A transaction-based approach to vertical partitioning forrelational database systems

An approach to vertical partitioning in relational databases in which the attributes of a relation are partitioned according to a set of transactions is proposed. The objective of vertical partitioning is to minimize the number of disk accesses in the system. Since transactions have more semantic meanings than attributes, this approach allows the optimization of the partitioning based on a selected set of important transactions. An optimal binary partitioning (OBP) algorithm based on the branch and bound method is presented, with the worst case complexity of O(2ⁿ), where n is the number of transactions. To handle systems with a large number of transactions, an algorithm BPi with complexity varying from O(n) to O(2ⁿ) is also developed. The experimental results reveal that the performance of vertical partitioning is sensitive to the skewness of transaction accesses. Further, BPi converges rather rapidly to OBP. Both OBP and BPi yield results comparable with that of global optimum obtained from an exhaustive search     

Workload balancing in distributed crowd simulations: the partitioning method

The simulation of large crowds of autonomous agents with a realistic behavior is still a challenge for several computer research communities. Distributed architectures can provide scalability to crowd simulations, but they require the use of efficient partitioning methods. Although convex hulls have been shown as very efficient structures for crowd partitioning, providing efficient workload balancing to large scale simulations is still an open issue. In this paper, we propose the integration of a workload balancing technique for crowd simulations within a partitioning method based on convex hulls. The region-based balancing technique reassigns agents to servers using a criterion of distance. The performance evaluation results show that this technique ensures the saturation avoidance of the servers in an homogeneous distributed system. This feature can increase the scalability of crowd simulations.     

The ABS tool suite: modelling, executing and analysing distributed adaptable object-oriented systems

Modern software systems must support a high degree of variability to accommodate a wide range of requirements and operating conditions. This paper introduces the Abstract Behavioural Specification (ABS) language and tool suite, a comprehensive platform for developing and analysing highly adaptable distributed concurrent software systems. The ABS language has a hybrid functional and object- oriented core, and comes with extensions that support the development of systems that are adaptable to diversified requirements, yet capable to maintain a high level of trustworthiness. Using ABS, system variability is consistently traceable from the level of requirements engineering down to object behaviour. This facilitates temporal evolution, as changes to the required set of features of a system are automatically reflected by functional adaptation of the system’s behaviour. The analysis capabilities of ABS stretch from debugging, observing and simulating to resource analysis of ABS models and help ensure that a system will remain dependable throughout its evolutionary lifetime. We report on the experience of using the ABS language and the ABS tool suite in an industrial case study.     

An automated verification method for distributed systems softwarebased on model extraction

Software verification methods are used only sparingly in industrial software development today. The most successful methods are based on the use of model checking. There are, however, many hurdles to overcome before the use of model checking tools can truly become mainstream. To use a model checker, the user must first define a formal model of the application, and to do so requires specialized knowledge of both the application and of model checking techniques. For larger applications, the effort to manually construct a formal model can take a considerable investment of time and expertise, which can rarely be afforded. Worse, it is hard to secure that a manually constructed model can keep pace with the typical software application, as it evolves from the concept stage to the product stage. We describe a verification method that requires far less specialized knowledge in model construction. It allows us to extract models mechanically from source code. The model construction process now becomes easily repeatable, as the application itself continues to evolve. Once the model is constructed, existing model checking techniques allow us to perform all checks in a mechanical fashion, achieving nearly complete automation. The level of thoroughness that can be achieved with this new type of software testing is significantly greater than for conventional techniques. We report on the application of this method in the verification of the call processing software for a new telephone switch that was developed at Lucent Technologies     

APS: adaptable prefetching scheme to different running environments for concurrent read streams in distributed file systems

The Journal of Supercomputing - Distributed file systems (DFSs) are widely used in various areas. One of the key issues is to provide high performance of concurrent read streams (i.e., multiple...     

支持多属性决策的嵌入式系统软硬件划分

针对硬件面积、价格成本、功耗、实时性和可靠性多目标优化的一类嵌入式系统软硬件划分问题,提出了一种采用多属性决策技术的求解方法。首先对可靠性指标进行了转换,通过改进的最短路径算法获得满足约束的Pareto方案集合;然后,采用基于组合权重的TOPSIS算法对多个划分方案进行评价排序,得到最优的多目标划分解;最后,通过一个实例验证了本方法的有效性和可行性。     

An evaluation of vertical class partitioning for query processing in object-oriented databases

Vertical partitioning is a design technique for reducing the number of disk accesses to execute a given set of queries by minimizing the number of irrelevant instance variables accessed. This is accomplished by grouping the frequently accessed instance variables as vertical class fragments. The complexity of object-oriented database models due to subclass hierarchy and class composition hierarchy complicates the definition and representation of vertical partitioning of the classes, which makes the problem of vertical partitioning in OODBs very challenging. In this paper, we develop a comprehensive analytical cost model for processing of queries on vertically partitioned OODB classes. A set of analytical evaluation results is presented to show the effect of vertical partitioning, and to study the trade-off between the projection ratio versus selectivity factor vis-a-vis sequential versus index access. Furthermore, an empirical experimental prototype supporting vertical class partitioning has been implemented on a commercial OODB tool kit to validate our analytical cost model.     

An adaptable threshold detector

A data set often comprises some data classes. For example, a gray-scale image may consist of some objects, each of which has similar pixels’ gray-scales. The threshold obtained by Otsu’s thresholding method (OTM) is biased towards certain data class with larger variance or larger number of data when the variances or the numbers of data among classes are quite different. In this paper, Adaptable Threshold Detector (ATD) is proposed to improve the effectiveness of OTM in determining proper thresholds by dividing class variance by class interval. ATD is more versatile at selecting application-dependent thresholds by changing two parameter values which describe the relative importance among data size, standard deviation, and class interval of a class. In this paper, ATD is applied to crop the expected objects from images to verify its effect upon thresholding. Experimental results demonstrate that ATD is able to perform better than OTM in segmenting objects from images, besides excelling over the Valley-Emphasis Method (VEM) and the Minimum Class Variance Thresholding Method (MCVTM). ATD is also suitable for separating objects from serialized video images, i.e. computerized tomography.