We study the replication transition problem in distributed hierarchical systems. Most distributedsystems replicate data to increase data access efficiency. A replication strategy dictates where the replicas are store...
详细信息
ISBN:
(纸本)9781424416936
We study the replication transition problem in distributed hierarchical systems. Most distributedsystems replicate data to increase data access efficiency. A replication strategy dictates where the replicas are stored in respond to the data access pattern, therefore a good strategy can effectively improve data access efficiency. However the access pattern in a distributed system is constantly changing. As a result, a good replication strategy must evolve accordingly. The replication transition problem is to seek an efficient transition from one replication strategy to another in order to cope with the dynamic access pattern. This paper focuses on solving the replication transition problem on tree topology, which is one of the most important models in Data Grid systems and web proxy systems from the literature. To the best of our knowledge, our work is the first that proposes an optimal algorithm for the replication transition problem on tree topology. The algorithm has a time complexity of O(n log Delta log(n Lambda)), where n is the number of sites, A is the maximum degree in the tree and A is the largest communication delay in the network.
We overview a library generation framework called Spiral. For the domain of linear transforms, Spiral automatically generates implementations for parallel platforms including SIMD vector extensions, multicore processo...
详细信息
ISBN:
(纸本)9781424416936
We overview a library generation framework called Spiral. For the domain of linear transforms, Spiral automatically generates implementations for parallel platforms including SIMD vector extensions, multicore processors, field-programmable gate arrays (FPGAs) and FPGA accelerated processors. The performance of the generated code is competitive with the best available hand-written libraries.
We present a novel protocol for restructuring a tree-based overlay network in response to the workload of the application running over it. Through low-cost restructuring operations, our protocol incrementally adapts t...
详细信息
ISBN:
(纸本)9781424416936
We present a novel protocol for restructuring a tree-based overlay network in response to the workload of the application running over it. Through low-cost restructuring operations, our protocol incrementally adapts the tree so as to bring nodes that tend to communicate with one another closer together in the tree. It achieves this while respecting degree bounds on nodes so that, e.g., no node degenerates into a "hub" for the overlay. Moreover it limits restructuring to those parts of the tree over which communication takes place, avoiding restructuring other parts of the tree unnecessarily. We show via experiments on PlanetLab that our protocol can significantly reduce communication latencies in workloads dominated by clusters of communicating nodes.
A number of graph partitioners are currently available for solving linear systems on parallel computers. Partitioning algorithms divide the graph that arises from the linear system into a specified number of partition...
详细信息
ISBN:
(纸本)9781424416936
A number of graph partitioners are currently available for solving linear systems on parallel computers. Partitioning algorithms divide the graph that arises from the linear system into a specified number of partitions such that the workload per processor is balanced and the communication between the processors is minimized The measure of partition quality is often taken to be the number of edges cut by the partition. Ultimately the quality of a partition will be reflected in the execution time of the parallel application. In this paper, we introduce a linear solver benchmark that enables comparison of partition quality. This work also serves to motivate further work on developing benchmarks for graph partitioners.
Data-driven modeling of biological systems such as protein-protein interaction networks is data-intensive and combinatorially challenging. Backtracking can constrain a combinatorial search space. Yet, its recursive na...
详细信息
ISBN:
(纸本)9781424416936
Data-driven modeling of biological systems such as protein-protein interaction networks is data-intensive and combinatorially challenging. Backtracking can constrain a combinatorial search space. Yet, its recursive nature, exacerbated by dida-intensity, limits its applicability for large-scale systems. parallel, scalable, and memory-efficient backtracking is a promising approach parallel backtracking suffers from unbalanced loads. Load rebalancing via synchronization and data movement is prohibitively expensive. Balancing these discrepancies, while minimizing end-to-end execution time and memory requirements, is desirable. This paper introduces such a framework. Its scalability and efficiency, demonstrated on the maximal clique enumeration problem, are attributed to the proposed: (a) representation of search tree decomposition to enable parallelization;(b) depth-first parallel search to minimize memory requirement;(c) least stringent synchronization to minimize data movement;and (d) on-demand work stealing with stack splitting to minimize processors' idle time. The applications of this framework to real biological problems related to bioethanol production are discussed.
This paper describes the advances in software design methods for concurrent, real-time and distributed applications from structured methods for centralized systems to distributed, object-oriented, component-based and ...
详细信息
parallel execution environment, such as the multi-core CPU, a cluster, and a grid, has spread increasingly. The change from a homogeneous core based CPU and a shared memory to the distributed memory and the heterogene...
详细信息
The efficient allocation of jobs to grid resources is indispensable for high performance grid-based applications. The scheduling problem is computationally hard even when there are no dependencies among jobs. Thus, we...
详细信息
ISBN:
(纸本)9781424416936
The efficient allocation of jobs to grid resources is indispensable for high performance grid-based applications. The scheduling problem is computationally hard even when there are no dependencies among jobs. Thus, we present in this paper a new tabu search (TS) algorithm for the problem of batch job scheduling on computational grids. We consider the job scheduling as a bi-objective optimization problem consisting of the minimization of the makespan and flowtime. The bi-objectivity is tackled through a hierarchic approach in which makespan is considered a primary objective and flowtime a secondary one. An extensive experimental study has been first conducted in order to fine-tune the parameters of our TS algorithm. Then, our tuned TS is compared versus two well known TS algorithms in the literature (one of them is hybridized with an ant colony optimization algorithm)for the problem. The computational results show that our TS implementation clearly outperforms the compared algorithms. Finally, we evaluated the performance of our TS algorithm on a new set of instances that better fits with the concept of computational grid. These instances are composed of a higher number of -heterogeneous- machines (up to 256) and emulate the dynamic behavior of these systems.
When an adaptive software component is employed to select the best-performing implementation for a communication operation at runtime, the correctness of the decision taken strongly depends on detecting and removing o...
详细信息
ISBN:
(纸本)9781424416936
When an adaptive software component is employed to select the best-performing implementation for a communication operation at runtime, the correctness of the decision taken strongly depends on detecting and removing outliers in the data used for the comparison. This automatic decision is greatly complicated by the fact that the types and quantities of outliers depend on the network interconnect and the nodes assigned to the job by the batch scheduler. This paper evaluates four different statistical methods used for handling outliers, namely a standard interquartile range method, a heuristic derived from the trimmed mean value, cluster analysis and a method using robust statistics. Using performance data from the Abstract Data and Communication Library (ADCL) we evaluate the correctness of the decisions made with each statistical approach over three fundamentally different network interconnects, namely a highly reliable InfiniBand network, a Gigabit Ethernet network having a larger variance in the performance, and a hierarchical Gigabit Ethernet network.
As computer networks rapidly increase in size and speed, Internet-distributedsystems such as P2P, volunteer computing, and Grid systems are increasingly common. A precise and accurate characterization of Internet res...
详细信息
ISBN:
(纸本)9781424425785
As computer networks rapidly increase in size and speed, Internet-distributedsystems such as P2P, volunteer computing, and Grid systems are increasingly common. A precise and accurate characterization of Internet resources is important for the design and evaluation, of such Internet-distributedsystems, yet our picture of the Internet landscape is not perfectly clear. To improve this picture, we measure and characterize the time dynamics of availability ire a large-scale Internet-distributed system with over 110,000 hosts. Our characterization focuses on identifying patterns of correlated availability. We determine scalable and accurate clustering techniques and distance metrics for automatically detecting significant availability patterns. By means of clustering, we identify groups of resources with correlated availability that exhibit similar time effects. Then, we show how these correlated clusters of resources can be used to improve resource management for parallel applications in the context of volunteer computing.
暂无评论