检索结果-内蒙古大学图书馆

48th International Conference on Parallel Processing (ICPP)

作者： Brock, Benjamin Buluc, Aydin Yelick, Katherine Univ Calif Berkeley Lawrence Berkeley Natl Lab Berkeley CA 94720 USA

ISBN: (纸本)9781450362955

One-sided communication is a useful paradigm for irregular parallel applications, but most one-sided programming environments, including MPI's one-sided interface and PGAS programming languages, lack application-level libraries to support these applications. We present the Berkeley Container Library, a set of generic, cross-platform, high-performance data structures for irregular applications, including queues, hash tables, Bloom filters and more. BCL is written in C++ using an internal DSL called the BCL Core that provides one-sided communication primitives such as remote get and remote put operations. The BCL Core has backends for MPI, OpenSHMEM, GASNet-EX, and UPC++, allowing BCL data structures to be used natively in programs written using any of these programming environments. Along with our internal DSL, we present the BCL ObjectContainer abstraction, which allows BCL data structures to transparently serialize complex data types while maintaining efficiency for primitive types. We also introduce the set of BCL data structures and evaluate their performance across a number of high-performance computing systems, demonstrating that BCL programs are competitive with hand-optimized code, even while hiding many of the underlying details of message aggregation, serialization, and synchronization.

关键词： Parallel Programming Libraries RDMA distributed data structures

来源：评论

学校读者我要写书评

暂无评论

Improving Average Performance by Relaxing distributed data structures 28

Improving Average Performance by Relaxing Distributed Data S...

引用

28th International Symposium on distributed Computing

作者： Talmage, Edward Welch, Jennifer L. Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA

ISBN: (纸本)9783662451748

Linearizability is a powerful consistency condition but can be expensive to implement. Recently, reserarchers have suggested gaining performance by relaxing the sequential specification of objects' data types. We consider, for the first time, linearizable message-passing implementations of relaxed Queues and prove upper and lower bounds on the elapsed time for Dequeue operations both in the worst case and on average. Our results imply that worst-case time complexity does not indicate benefit from relaxation. In contrast, we present implementations of relaxed Queues for which the average time complexity of Dequeue is significantly smaller than both the worst-case lower bound for unrelaxed Queues and a newly-proved lower bound on the average time for unrelaxed Queues. We also prove lower bounds on the average time complexity of Dequeue for relaxed Queues that show our algorithms are asymptotically optimal and that there is an inherent complexity gap between different levels of relaxation.

关键词： consistency conditions distributed data structures relaxed specifications average cost time bounds

来源：评论

学校读者我要写书评

暂无评论

RDMA vs. RPC for Implementing distributed data structures 9

RDMA vs. RPC for Implementing Distributed Data Structures

引用

9th IEEE/ACM Workshop on Irregular Applications - Architectures and Algorithms (IA3)

作者： Brock, Benjamin Chen, Yuxin Yan, Jiakun Owens, John D. Buluc, Aydin Yelick, Katherine Univ Calif Berkeley Berkeley CA 94720 USA Lawrence Berkeley Natl Lab Berkeley CA 94720 USA Univ Calif Davis Davis CA 95616 USA Shanghai Jiao Tong Univ Shanghai Peoples R China

ISBN: (纸本)9781728159874

distributed data structures are key to implementing scalable applications for scientific simulations and data analysis. In this paper we look at two implementation styles for distributed data structures: remote direct memory access (RDMA) and remote procedure call (RPC). We focus on operations that require individual accesses to remote portions of a distributed data structure, e.g., accessing a hash table bucket or distributed queue, rather than global operations in which all processors collectively exchange information. We look at the trade-offs between the two styles through microbenchmarks and a performance model that approximates the cost of each. The RDMA operations have direct hardware support in the network and therefore lower latency and overhead, while the RPC operations are more expressive but higher cost and can suffer from lack of attentiveness from the remote side. We also run experiments to compare the real-world performance of RDMA- and RPC-based data structure operations with the predicted performance to evaluate the accuracy of our model, and show that while the model does not always precisely predict running time, it allows us to choose the best implementation in the examples shown. We believe this analysis will assist developers in designing data structures that will perform well on current network architectures, as well as network architects in providing better support for this class of distributed data structures.

关键词： distributed data structures remote procedure call (RPC) remote direct memory access (RDMA)

来源：评论

学校读者我要写书评

暂无评论

Rdma-Based distributed data structures for Large-Scale Parallel Systems

Rdma-Based Distributed Data Structures for Large-Scale Paral...

引用

作者： Brock, Benjamin Acker University of California Berkeley

学位级别：Ph.D., Doctor of Philosophy

Running programs across multiple nodes in a cluster of networked computers, such as in a supercomputer or commodity datacenter system,is increasingly important across multiple domains, including data science, machine learning, and scientific computing. This is brought on by a combination of increasing data sizes, which push beyond the memory capacity of a single node, and increasing computational demands from new, more elaborate simulations, models, and applications. However, writing parallel programs for clusters of computers remains a difficult task, particularly for programs that are irregular in terms ofdata distribution or access pattern. Many parallel programs today are still written using communication libraries like MPI or OpenSHMEM, which require users to explicitly manage low-level details. While high-level parallel programming languages and libraries do exist, and these can make implementing certain types of programs much easier, developers often have to expend significant effort building custom infrastructure and data structures for their applications. This thesis argues that a large part of the reason why parallel programming remains difficult is a lack of high-level distributed data structures analogous to the data structures that have become ubiquitous in sequential programming environments like C++ and Python. These especially include irregular data structures like hash tables and queues that may require fine-grained memory accesses along with synchronization. This thesis examines techniques for building high-level, cross-platform distributed data structures using one-sided remote memory operations like remote put, remote get, and remote atomics. These memory access primitives allow for a high degree of asynchrony, enabling better performance by removing synchronization bottlenecks and allowing a high degree of overlap between communication and computation. They can also be efficiently executed directly by the network hardware in modern supercomputer

关键词： distributed data structures distributed systems Parallel computing Partitioned global address space Remote direct memory access Sparse matrices

来源：评论

学校读者我要写书评

暂无评论

A Design Space for distributed Producer-Consumer data structures Using RDMA

A Design Space for Distributed Producer-Consumer Data Struct...

引用

作者： Sharma, Manoj Kumar University of Waterloo

学位级别：硕士

Remote Direct Memory Access (RDMA) has become a standard networking technology and is prominently used in high-performance applications. While RDMA can provide both excellent performance and novel capabilities, it can be more difficult than traditional kernel-supported networking to use effectively. RDMA adoption can be simplified through the use of abstractions that target broad classes of applications. In this thesis, we propose flow structures as an abstraction targeting distributed applications in which data need to flow directly between producers and consumers. Flow structures are asymmetric distributed producer/consumer data structures in which some servers only produce and others only consume. We present a design space for RDMA implementations of flow structures and illustrate the space using several concrete implementations of a simple flow structure: a FIFO queue. Finally, we present an empirical study that illustrates the design tradeoffs along the dimensions of the design space, and that shows that flow structures abstractions can capture the performance advantages of RDMA while making it much easier to use.

关键词： distributed data structures Flow structures RDMA

来源：评论

学校读者我要写书评

暂无评论

Energy Efficient Schemes for Accuracy-Guaranteed Sensor data Aggregation Using Scalable Counting

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND data ENGINEERING 2012年第8期24卷 1463-1477页

作者： Fan, Yao-Chung Chen, Arbee L. P. Natl Tsing Hua Univ Dept Comp Sci Kaohsiung 807 Taiwan Natl Chengchi Univ Dept Comp Sci Taipei 11605 Taiwan

Sensor networks have received considerable attention in recent years, and are employed in many applications. In these applications, statistical aggregates such as Sum over the readings of a group of sensor nodes are often needed. One challenge for computing sensor data aggregates comes from the communication failures, which are common in sensor networks. To enhance the robustness of the aggregate computation, multipath-based aggregation is often used. However, the multipath-based aggregation suffers from the problem of overcounting sensor readings. The approaches using the multipath-based aggregation therefore need to incorporate techniques that avoid overcounting sensor readings. In this paper, we present a novel technique named scalable counting for efficiently avoiding the overcounting problem. We focus on having an (epsilon, delta) accuracy guarantee for computing an aggregate, which ensures that the error in computing the aggregate is within a factor of epsilon with probability (1 - delta). Our schemes using the scalable counting technique efficiently compute the aggregates under a given accuracy guarantee. We provide theoretical analyses that show the advantages of the scalable counting technique over previously proposed techniques. Furthermore, extensive experiments are made to validate the theoretical results and manifest the advantages of using the scalable counting technique for sensor data aggregation.

关键词： Wireless sensor networks query processing distributed data structures reliability and robustness

来源：评论

学校读者我要写书评

暂无评论

Static single assignment form for message-passing programs

引用

INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING 2001年第2期29卷 139-184页

作者： Chakrabarti, DR Banerjee, P Northwestern Univ Inst Technol ECE Dept Ctr Parallel & Distributed Comp Evanston IL 60208 USA

This paper presents a novel scheme for maintaining accurate information about distributed data in message-passing programs. We describe static single assignment (SSA) based algorithms to build up an intermediate representation of a sequential program while targeting code generation for distributed memory machines employing the single program multiple data (SPMD) model of programming. This SSA-based intermediate representation helps in a variety of optimizations performed by our automatic parallelizing compiler, PARADIGM, which generates message passing programs and targets distributed memory machines. In this paper. we concentrate on the semantics and implementation of this SSA-form for message-passing programs while giving some examples of the kind of optimizations they enable. We describe in detail the need for various kinds of merge functions to maintain the single assignment property of distributed data. We give algorithms for placement and semantics of these merge functions and show how the requirements are substantially different owing to the presence of distributed data and arbitrary array addressing functions. This scheme has been incorporated in our compiler framework which can use uniform methods to compile, parallelize. and optimize a sequential program irrespective of the subscripts used in array addressing functions. Experimental results for a number of benchmarks on an IBM SP-2 show a significant improve ment in the total runtimes owing to some of the optimizations enabled by the SSA-based intermediate representation. We have observed up to around 10-25 % reduction in total runtimes in our SSA-based schemes compared to non-SSA-based schemes on 16 processors.

关键词： compiler optimizations static single assignment message passing programs distributed data structures

来源：评论

学校读者我要写书评

暂无评论

Self-tuning reactive diffracting trees

引用

JOURNAL OF PARALLEL AND distributed COMPUTING 2007年第6期67卷 674-694页

作者： Ha, Phuong Hoai Papatriantafilou, Marina Tsigas, Philippas Chalmers Dept Comp Sci & Engn S-41296 Gothenburg Sweden

Reactive diffracting trees are efficient distributed objects that support synchronization, by distributing sets of memory accesses to different memory banks in a coordinated manner. They adjust their size in order to retain their efficiency in the presence of different contention levels. Their adjustment is sensitive to parameters that have to be manually determined after experimentation. Since these parameters depend on the application as well as on the system configuration and load, determining their optimal values is difficult in practice. Moreover, the adjustments are done one level at a time, hence the cost of multi-level adjustments can be high. This paper presents a new method for reactive diffracting trees, without the need of hand-tuned parameters. The new self-tuning trees (ST-trees) can balance, in an online manner, the trade-off between the tree-traversal latency and the latency due to contention on accessing the leaf nodes (i.e. the nodes where the desirable computation takes place). Moreover, the paper presents a data structure that enables the trees to grow or shrink by several levels in one adjustment step. The behavior of the reactive diffracting trees is illustrated in the paper via experiments performed on a well-known ccNUMA multiprocessor system. The experiments study the new self-tuning trees, also in connection with the original hand-tuned reactive diffracting trees. The experiments have showed that the new self-tuning trees are efficient, and that they react in the same way (i.e. select the same tree depth for the same contention level) as the hand-tuned trees, while they are able to adjust quicker than the latter (as they are able to grow or shrink by several levels in one adjustment step). (c) 2007 Elsevier Inc. All rights reserved.

关键词： synchronization concurrent programming dynamic data structures distributed data structures trees

来源：评论

学校读者我要写书评

暂无评论

EXPERIENCE WITH MULTIPROCESSOR ALGORITHMS

引用

IEEE TRANSACTIONS ON COMPUTERS 1982年第4期31卷 278-288页

作者： DEMINET, J UNIV WARSAW PL-02089 WARSAWPOLAND

This paper presents results of experiments with parallel algorithms. Several versions of four different programs, each representing a class of applications, were tested. All the experiments were performed on Cm*,l a 50-processor computer with a hierarchical structure. The results show that when the structure of an algorithm corresponds well to the structure of the computer, a close-to-linear speedup may be achieved. An attempt was made to analyze the reference patterns and interprocess cooperation and their influence on the performance of the algorithms. Several still-open questions are formulated in the paper and some further research directions are suggested.

关键词： distributed data structures multiprocessors parallel processing performance evaluation synchronization

来源：评论

学校读者我要写书评

暂无评论

Concurrent maintenance of rings

引用

distributed COMPUTING 2006年第2期19卷 126-148页

作者： Li, Xiaozhou Misra, Jayadev Plaxton, C. Greg Univ Texas Dept Comp Sci Austin TX 78712 USA

A central problem for structured peer-to-peer networks is topology maintenance, that is, how to properly update neighbor variables when nodes join or leave the network, possibly concurrently. In this paper, we consider the maintenance of the ring topology, the basisof several peer-to-peer networks, in the fault-free environment. We design, and prove the correctness of, protocols that maintain a bidirectional ring under both joins and leaves. Our protocols update neighbor variables once a membership change occurs. We prove the correctness of our protocols using an assertional proof method, that is, we first identify a global invariant for a protocol and then show that every action of the protocol preserves the invariant. Our protocols are simple and our proofs are rigorous and explicit.

关键词： concurrency distributed algorithm distributed data structures network protocols correctness

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：