The modern parallel I/O stack consists of several software layers with complex inter-dependencies and performance characteristics. While each layer exposes tunable parameters, it is often unclear to users how differen...
详细信息
ISBN:
(纸本)9781450319102
The modern parallel I/O stack consists of several software layers with complex inter-dependencies and performance characteristics. While each layer exposes tunable parameters, it is often unclear to users how different parameter settings interact with each other and affect overall I/O performance. As a result, users often resort to default system settings, which typically obtain poor I/O bandwidth. In this research, we develop a benchmark guided auto-tuning framework for tuning the HDF5, MPI-IO, and Lustre layers on production supercomputing facilities. Our framework consists of three main components. H5Tuner uses a control file to adjust I/O parameters without modifying or recompiling the application. H5PerfCapture records performance metrics for HDF5 and MPI-IO. H5Evolve uses a genetic algorithm to explore the parameter space to determine well-performing configurations. We demonstrate I/O performance results for three HDF5 application-based benchmarks on a Sun HPC system. All the benchmarks running on 512 MPI processes perform 3X to 5.5X faster with the auto-tuned I/O parameters compared to a configuration with default system parameters.
Prediction of the translation initiation site is of vital importance in bioinformatics since through this process it is possible to understand the organic formation and metabolic behavior of living organisms. Sequenti...
详细信息
ISBN:
(纸本)9781467317146
Prediction of the translation initiation site is of vital importance in bioinformatics since through this process it is possible to understand the organic formation and metabolic behavior of living organisms. Sequential algorithms are not always a viable solution due to the fact that mRNA databases are normally very large, resulting in long processing times. Applying parallel and distributed computing resources to such databases could help reduce this time. The objective of this article is to present a class balancing solution for the translation initiation site process using parallel and distributed computing resources in a hybrid model. The results reveal a speedup of up to 23 times compared to sequential methods and performance rates for accuracy, precision, sensitivity, specificity and adjusted accuracy of 91.15%, 39.83%, 89.11%, 88.93% and 89.02%, respectively, for the Homo sapiens database. For the Drosophila melanogaster database, the speedup was 18.33 times and accuracy, precision, sensitivity, specificity and adjusted accuracy were 95.22%, 43.01%, 90.83%, 90.47% and 90.64%, respectively. Both sets of results are considered important. Thus, the solution presented in this article demonstrated itself viable for the problem in question.
Hadoop is an efficient and simple parallel framework following the MapReduce paradigm, and making the parallel processing recently become a hot issue in data-intensive applications. Since Hadoop can be easily deployed...
详细信息
ISBN:
(纸本)9781467345651;9780769549033
Hadoop is an efficient and simple parallel framework following the MapReduce paradigm, and making the parallel processing recently become a hot issue in data-intensive applications. Since Hadoop can be easily deployed on large-scale clusters including up to thousands of computers, various studies intend to process common relational database operations also on this new platform and expect to achieve a remarkable performance. However, these works have to prepare customized programs according to different input format, making the communication between co-workers difficult. Additionally, all intermediate data have to be transformed to key-value pairs and then transferred through the underlying HDFS, making the data processable by Map and Reduce tasks and keeping a balanced workload on the cluster. During this period, unnecessary overhead decreases both the speed-up and scale-up of these systems. Therefore, this paper attempts to propose a light and efficient coupling structure thus to combine Hadoop with single-computer databases on the engine level. On one hand, it uses a well-designed parallel data model to make end-users represent parallel queries like common queries. All current and future data types and algorithms can be used directly, having no need to be specifically changed for the parallel platform. On the other hand, it provides a simple and independent distributed file system to transfer data among database engines directly, without passing through HDFS, hence to remove as much as possible unnecessary transform and transfer overhead. For purpose of demonstration, a prototype parallel SECONDO is introduced in this paper. It has been fully evaluated in both small and large scale clusters, achieving satisfactory performances for different database operations.
We study a basic information ranking problem in networks where each node holds an individual preference over a set of items and the goal for each node is to identify a sorted list of items with the largest aggregate p...
详细信息
ISBN:
(纸本)9781467325790
We study a basic information ranking problem in networks where each node holds an individual preference over a set of items and the goal for each node is to identify a sorted list of items with the largest aggregate preference. We would like to achieve this with a fully decentralized algorithm that uses a limited per-node memory and limited pair-wise communications. We show how this problem can be reduced to a plurality selection problem where the goal for each node is to identify an item with the largest aggregate ranking score, and show that solving the reduced problem solves the original ranking problem with high probability. Then we introduce a simple and natural plurality selection algorithm for the selection over m > 1 items that uses only log(2) (m) + 1 bits of per-node memory and per pair-wise communication. We prove correctness of the algorithm with high probability as the number of nodes grows large for the case when each node communicates with any other node, and establish tight convergence time bounds. The information ranking problem studied in this paper is a basic ranking problem that arises in various applications such as sorting elements in distributed computing systems, paralleldatabases, and may as well serve as a model of decentralized inference and opinion formation in distributed environments.
This paper develops the sufficiency principle suitable for data reduction in decentralized inference systems. Both parallel and tandem networks are studied and we focus on the cases where observations at decentralized...
详细信息
ISBN:
(纸本)9781467325790
This paper develops the sufficiency principle suitable for data reduction in decentralized inference systems. Both parallel and tandem networks are studied and we focus on the cases where observations at decentralized nodes are conditionally dependent. For a parallel network, through the introduction of a hidden variable that induces conditional independence among the observations, the locally sufficient statistics, defined with respect to the hidden variable, are shown to be globally sufficient for the parameter of inference interest. For a tandem network, the notion of conditional sufficiency is introduced and the related theories and tools are developed. Finally, connections between the sufficiency principle and some distributed source coding problems are explored.
Replicated storage systems allow their stored data objects to outlive the life of the nodes storing them through replication. In this paper, we focus on durability, and more specifically on the concept of an object...
详细信息
ISBN:
(纸本)9780769547848;9781467323970
Replicated storage systems allow their stored data objects to outlive the life of the nodes storing them through replication. In this paper, we focus on durability, and more specifically on the concept of an object's lifetime, i.e., the duration of time between the creation of an object and when it is permanently irretrievable from the system. We analyze two main replication strategies: reactive, in which replication occurs in response to failures, and proactive, in which replication occurs in anticipation of failures. Our work presents a quantitative analysis that compares reactive and proactive through analytical models and simulations, considering exponentially distributed failures and reactive repairs, and periodic proactive replications. We also present a derivation of the analytical formula for the variance of the lifetime in the reactive model. Our results indicate that a proactive strategy leads to multiple times higher storage requirements than a reactive strategy. In addition, reactive systems are only moderately bursty in terms of bandwidth consumption, with rare peaks of at most five times the bandwidth consumption in proactive systems (given input parameter values that are compatible with real systems). Finally, for both strategies, the standard deviation is very close to the expected lifetime, and consequently, the lifetimes close to being exponentially distributed.
distributed storage systems rely heavily on redundancy to ensure data availability as well as durability. In networked systems subject to intermittent node unavailability, the level of redundancy introduced in the sys...
详细信息
ISBN:
(纸本)9780769547848;9781467323970
distributed storage systems rely heavily on redundancy to ensure data availability as well as durability. In networked systems subject to intermittent node unavailability, the level of redundancy introduced in the system should be minimized and maintained upon failures. Repairs are well-known to be extremely bandwidth-consuming and it has been shown that, without care, they may significantly congest the system. In this paper, we propose an approach to redundancy management accounting for nodes heterogeneity with respect to availability. We show that by using the availability history of nodes, the performance of two important faces of distributed storage (replica placement and repair) can be significantly improved. Replica placement is achieved based on complementary nodes with respect to nodes availability, improving the overall data availability. Repairs can be scheduled thanks to an adaptive per-node timeout according to node availability, so as to decrease the number of repairs while reaching comparable availability. We propose practical heuristics for those two issues. We evaluate our approach through extensive simulations based on real and well-known availability traces. Results clearly show the benefits of our approach with regards to the critical trade-off between data availability, load-balancing and bandwidth consumption.
We propose a Snapshot Isolation based transaction execution and consistency model, referred to as causally-coordinated snapshot isolation, for geographically replicated data. The data replication is managed through as...
详细信息
ISBN:
(纸本)9780769547848;9781467323970
We propose a Snapshot Isolation based transaction execution and consistency model, referred to as causally-coordinated snapshot isolation, for geographically replicated data. The data replication is managed through asynchronous update propagation. Our approach provides snapshot-isolation model over multiple sites and ensures causal ordering of transactions. We present here an efficient protocol for precisely capturing the causal data dependencies of transactions and ensuring the causal ordering based on these dependencies when applying transactions' updates at remote sites. Through experimental evaluations, we demonstrate the benefit of this protocol over an alternative approach for providing causal consistency for geo-replicated data. We further extend this model to support session consistency guarantees such as read-your-writes and monotonic-reads. Additionally, we provide a notion of group-session where a group of users are involved in a collaborative session. We provide various group-session consistency guarantees for users collaborating in a group. We present the mechanisms for providing these session consistency guarantees and evaluate their performance.
Graph-based structures are being increasingly used to model data and relations among data in a number of fields. Graph-based databases are becoming more popular as a means to better represent such data. Graph traversa...
详细信息
ISBN:
(纸本)9780769546759
Graph-based structures are being increasingly used to model data and relations among data in a number of fields. Graph-based databases are becoming more popular as a means to better represent such data. Graph traversal is a key component in graph algorithms such as reachability and graph matching. Since the scale of data stored and queried in these databases is increasing, it is important to obtain high performing implementations of graph traversal that can efficiently utilize the processing power of modern processors. In this work, we present a scalable Breadth-First Search Traversal algorithm for modern multi-socket, multi-core CPUs. Our algorithm uses lock- and atomic-free operations on a cache-resident structure for arbitrary sized graphs to filter out expensive main memory accesses, and completely and efficiently utilizes all available bandwidth resources. We propose a work distribution approach for multi-socket platforms that ensures load-balancing while keeping cross-socket communication low. We provide a detailed analytical model that accurately projects the performance of our single- and multi-socket traversal algorithms to within 5-10% of obtained performance. Our analytical model serves as a useful tool to analyze performance bottlenecks on modern CPUs. When measured on various synthetic and real-world graphs with a wide range of graph sizes, vertex degrees and graph diameters, our implementation on a dual-socket Intel (R) Xeon (R) X5570 (Intel microarchitecture code name Nehalem) system achieves 1.5X-13.2X performance speedup over the best reported numbers. We achieve around 1 Billion traversed edges per second on a scale-free R-MAT graph with 64M vertices and 2 Billion edges on a dual-socket Nehalem system. Our optimized algorithm is useful as a building block for efficient multi-node implementations and future exascale systems, thereby allowing them to ride the trend of increasing per-node compute and bandwidth resources.
The proceedings contain 25 papers. The topics discussed include: PowerGraph: distributed graph-parallel computation on natural graphs;hails: protecting data privacy in untrusted web applications;eternal sunshine of th...
ISBN:
(纸本)9781931971966
The proceedings contain 25 papers. The topics discussed include: PowerGraph: distributed graph-parallel computation on natural graphs;hails: protecting data privacy in untrusted web applications;eternal sunshine of the spotless machine: protecting privacy with ephemeral channels;CleanOS: limiting mobile data exposure with idle eviction;appinsight: mobile app performance monitoring in the wild;DJoin: differentially private join queries over distributeddatabases;improving integer security for systems with KINT;and dissent in numbers: making strong anonymity scale.
暂无评论