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

45th Annual International IEEE-Computer-Society Computers, Software, and Applications Conference (COMPSAC)

作者： Ma, Teng He, Dongbiao Liu, Ning Tsinghua Univ Beijing Peoples R China Alibaba Hangzhou Peoples R China

ISBN: (纸本)9781665424639

RDMA (Remote Direct Memory Access) delivers both high performance and OS kernel bypass thus triggers the revolutions of the modern data center. Especially, compared with traditional Ethernet, by exploiting memory semantics operations, RDMA-based data structure has shown great potential for high scalability and CPU utilization reduction. SkipList is an elegant sorted index data structure, and yet presents low throughput upon memory semantics RDMA due to the heavy remote access. By using SkipList as a case study, we revisit the current design paradigm of RDMA such as operation type, transport type, and caching. Accordingly, we propose a one-sided/two-sided hybrid paradigm to gain high scalability and at the same time achieve high throughput based on lock-based concurrent SkipList. To reduce the number of expensive network round trips, a client-sided cache is presented. With an in-depth analysis of the design choices, we implement HybridSkipList and deploy at an eight-machine RDMA cluster. The evaluations show it can outperform two baselines by 4.41 x and 3.45 x respectively.

关键词： distributed data structure RDMA SkipList Hybrid Communication Paradigm

来源：评论

学校读者我要写书评

暂无评论

DArray: A High Performance RDMA-Based distributed Array 23

DArray: A High Performance RDMA-Based Distributed Array

引用

52nd International Conference on Parallel Processing (ICPP)

作者： Ding, Baorong Han, Mingcong Chen, Rong Shanghai Jiao Tong Univ Shanghai Peoples R China Shanghai Jiao Tong Univ Shanghai AI Lab Shanghai Peoples R China

ISBN: (纸本)9798400708435

This paper presents DArray, a high performance RDMA-based distributed memory system. DArray achieves high performance through three key designs. First, DArray is designed with an object array abstraction, which captures the high-level application semantics and provides a rich set of optimized interfaces with object granularity. Second, DArray adopts distributed cache to absorb remote data accesses. In order to reduce the performance overhead incurred by the cache layer and increase the parallelism, DArray devises a lock-free data access path to the local cache which utilizes reference counters to prevent data races. Finally, based on the observation that most data update operators are associative and commutative, DArray proposes a new "Operate" interface, which enables concurrent data operations on multiple nodes, and extends existing distributed cache coherence protocol to support the new "Operate" semantics. A graph analytics engine and a distributed key-value store (KVS) are built on top of DArray to demonstrate its versatility. The experiment results on graph applications show that DArray achieves two to three orders of magnitude better performance than GAM (a state-of-the-art distributed memory), also with a maximum speedup of 2.1x compared to Gemini (a state-of-the-art distributed graph engine). Furthermore, the DArray-based KVS outperforms the GAM-based KVS by up to 41x (from 2x).

关键词： RDMA distributed Shared Memory distributed data structure distributed System

来源：评论

学校读者我要写书评

暂无评论

A self-stabilizing Hashed Patricia Trie

引用

INFORMATION AND COMPUTATION 2022年第PartA期285卷

作者： Knollmann, Till Scheideler, Christian Paderborn Univ Heinz Nixdorf Inst Furstenallee 11 D-33102 Paderborn Germany Paderborn Univ Comp Sci Dept Furstenallee 11 D-33102 Paderborn Germany

While many research in distributed computing has covered solutions for self-stabilizing computing and topologies, there is far less work on self-stabilization for distributed data structures. However, when peers in peer-to-peer networks crash, a distributed data structure may not remain intact. We present a self-stabilizing protocol for a distributed data structure called the Hashed Patricia Trie (Kniesburges and Scheideler WALCOM'11) that enables efficient prefix search on a set of keys. The data structure has many applications while offering low overhead and efficient operations when embedded on top of a distributed Hash Table. Especially, longest prefix matching for x can be done in O(log vertical bar x vertical bar) hash table read accesses. We show how to maintain the structure in a self-stabilizing way, while assuring a low overhead in a legal state and an asymptotically optimal memory demand of Theta(d) bits, where d is the number of bits needed for storing all keys. (C) 2021 Elsevier Inc. All rights reserved.

关键词： Self-stabilizing Prefix search distributed data structure

来源：评论

学校读者我要写书评

暂无评论

HCL: Distributing Parallel data structures in Extreme Scales 22

HCL: Distributing Parallel Data Structures in Extreme Scales

引用

IEEE International Conference on Cluster Computing

作者： Devarajan, Hariharan Kougkas, Anthony Bateman, Keith Sun, Xian-He Illinois Inst Technol Dept Comp Sci Chicago IL 60616 USA

ISBN: (纸本)9781728166773

Most parallel programs use irregular control flow and data structures, which are perfect for one-sided communication paradigms such as MPI or PGAS programming languages. However, these environments lack the presence of efficient function-based application libraries that can utilize popular communication fabrics such as TCP, Infinity Band (IB), and RDMA over Converged Ethernet (RoCE). Additionally, there is a lack of high-performance data structure interfaces. We present Hermes Container Library (HCL), a high-performance distributed data structures library that offers high-level abstractions including hash-maps, sets, and queues. HCL uses a RPC over RDMA technology that implements a novel procedural programming paradigm. In this paper, we argue a RPC over RDMA technology can serve as a high-performance, flexible, and co-ordination free backend for implementing complex data structures. Evaluation results from testing real workloads shows that HCL programs are 2x to 12x faster compared to BCL, a state-of-the-art distributed data structure library.

关键词： distributed data structure RPC over RDMA Hybrid data Access Model HPC data Containers

来源：评论

学校读者我要写书评

暂无评论

A Self-stabilizing Hashed Patricia Trie 1

引用

20th International Symposium on Stabilization, Safety, and Security of distributed Systems (SSS)

作者： Knollmann, Till Scheideler, Christian Paderborn Univ Heinz Nixdorf Inst Comp Sci Dept Paderborn Germany Paderborn Univ Comp Sci Dept Paderborn Germany

ISBN: (数字)9783030032326

ISBN: (纸本)9783030032326;9783030032319

While a lot of research in distributed computing has covered solutions for self-stabilizing computing and topologies, there is far less work on self-stabilization for distributed data structures. Considering crashing peers in peer-to-peer networks, it should not be taken for granted that a distributed data structure remains intact. In this work, we present a self-stabilizing protocol for a distributed data structure called the hashed Patricia Trie (Kniesburges and Scheideler WALCOM'11) that enables efficient prefix search on a set of keys. The data structure has a wide area of applications including string matching problems while offering low overhead and efficient operations when embedded on top of a distributed hash table. Especially, longest prefix matching for x can be done in O(log vertical bar x vertical bar) hash table read accesses. We show how to maintain the structure in a self-stabilizing way. Our protocol assures low overhead in a legal state and a total (asymptotically optimal) memory demand of Theta(d) bits, where d is the number of bits needed for storing all keys.

关键词： Self-stabilizing Prefix search distributed data structure

来源：评论

学校读者我要写书评

暂无评论

distributed Combinatorial Maps for Parallel Mesh Processing

引用

ALGORITHMS 2018年第7期11卷 105-105页

作者： Damiand, Guillaume Gonzalez-Lorenzo, Aldo Zara, Florence Dupont, Florent Univ Lyon CNRS UMR5205 LIRIS F-69622 Lyon France Univ Lyon 1 Fac Sci F-69100 Lyon France Univ Lyon 1 Technol Dept F-69100 Lyon France

We propose a new strategy for the parallelization of mesh processing algorithms. Our main contribution is the definition of distributed combinatorial maps (called n-dmaps), which allow us to represent the topology of big meshes by splitting them into independent parts. Our mathematical definition ensures the global consistency of the meshes at their interfaces. Thus, an n-dmap can be used to represent a mesh, to traverse it, or to modify it by using different mesh processing algorithms. Moreover, an nD mesh with a huge number of elements can be considered, which is not possible with a sequential approach and a regular data structure. We illustrate the interest of our solution by presenting a parallel adaptive subdivision method of a 3D hexahedral mesh, implemented in a distributed version. We report space and time performance results that show the interest of our approach for parallel processing of huge meshes.

关键词： distributed data structure combinatorial maps parallel mesh processing

来源：评论

学校读者我要写书评

暂无评论

Providing Parallel Debugging for DASH distributed data structures with GDB

Providing Parallel Debugging for DASH Distributed Data Struc...

引用

15th Annual International Conference on Computational Science (ICCS)

作者： Huenich, Denis Knuepfer, Andreas Gracia, Jose Tech Univ Dresden Ctr Informat Serv & High Performance Comp ZIH Dresden Germany Univ Stuttgart High Performance Comp Ctr Stuttgart HLRS D-70174 Stuttgart Germany

The C++ DASH template library provides distributed data container for Partitioned Global Address Space (PGAS)-like programming. Because DASH is new and under development no debugger is capable to handle the parallel processes or access/modify container elements in a convenient way. This paper describes how the DASH library has to be extended to interrupt the start-up process to connect a debugger with all started processes and to enable the debugger for accessing and modifying DASH container elements. Furthermore, an GDB extension to output well formatted DASH container information is presented.

关键词： C plus plus templates dash gdb debugging distributed data structure parallelization

来源：评论

学校读者我要写书评

暂无评论

Providing Parallel Debugging for DASH distributed data structures with GDB

引用

Procedia Computer Science 2015年 51卷 1383-1392页

作者： Denis Hünich Andreas Knüpfer José Gracia Center for Information Services and High Performance Computing (ZIH) TU Dresden Dresden Germany High Performance Computing Center Stuttgart (HLRS) University of Stuttgart Stuttgart Germany

The C + + DASH template library provides distributed data container for Partitioned Global Address Space (PGAS)-like programming. Because DASH is new and under development no debugger is capable to handle the parallel processes or access/modify container elements in a convenient way. This paper describes how the DASH library has to be extended to interrupt the start-up process to connect a debugger with all started processes and to enable the debugger for accessing and modifying DASH container elements. Furthermore, an GDB extension to output well formatted DASH container information is presented.

关键词： C++ templates dash gdb debugging distributed data structure parallelization

来源：评论

学校读者我要写书评

暂无评论

-Tree: A New Overlay with Deterministic Bounds

引用

ALGORITHMICA 2015年第3期72卷 860-883页

作者： Brodal, Gerth Stolting Sioutas, Spyros Tsichlas, Kostas Zaroliagis, Christos Univ Aarhus Dept Comp Sci MADALGO Aarhus Denmark Ionian Univ Dept Informat Corfu 49100 Greece Aristotle Univ Thessaloniki Dept Informat GR-54006 Thessaloniki Greece Univ Patras Dept Comp Engn & Informat Patras 26504 Greece Comp Technol Inst & Press Diophantus Patras 26504 Greece

We present a new overlay, called the Deterministic Decentralized tree (-tree). The -tree compares favorably to other overlays for the following reasons: (a) it provides matching and better complexities, which are deterministic for the supported operations;(b) the management of nodes (peers) and elements are completely decoupled from each other;and (c) an efficient deterministic load-balancing mechanism is presented for the uniform distribution of elements into nodes, while at the same time probabilistic optimal bounds are provided for the congestion of operations at the nodes. The load-balancing scheme of elements into nodes is deterministic and general enough to be applied to other hierarchical tree-based overlays. This load-balancing mechanism is based on an innovative lazy weight-balancing mechanism, which is interesting in its own right.

关键词： Overlay Indexing scheme Decentralized system distributed data structure Load-balancing

来源：评论

学校读者我要写书评

暂无评论

Approximate nearest neighbor algorithm based on navigable small world graphs

引用

INFORMATION SYSTEMS 2014年 45卷 61-68页

作者： Malkov, Yury Ponomarenko, Alexander Logvinov, Andrey Krylov, Vladimir Russian Acad Sci Inst Appl Phys Nizhnii Novgorod 603950 Russia MERA Labs LLC Nizhnii Novgorod 603163 Russia Natl Res Univ Higher Sch Econ Lab Algorithms & Technol Network Anal Nizhnii Novgorod 603093 Russia Nizhnii Novgorod State Tech Univ Nizhnii Novgorod Russia

We propose a novel approach to solving the approximate k-nearest neighbor search problem in metric spaces. The search structure is based on a navigable small world graph with vertices corresponding to the stored elements, edges to links between them, and a variation of greedy algorithm for searching. The navigable small world is created simply by keeping old Delaunay graph approximation links produced at the start of construction. The approach is very universal, defined in terms of arbitrary metric spaces and at the same time it is very simple. The algorithm handles insertions in the same way as queries: by finding approximate neighbors for the inserted element and connecting it to them. Both search and insertion can be done in parallel requiring only local information from the structure. The structure can be made distributed. The accuracy of the probabilistic k-nearest neighbor queries can be adjusted without rebuilding the structure. The performed simulation for data in the Euclidean spaces shows that the structure built using the proposed algorithm has small world navigation properties with log(2)(n) insertion and search complexity at fixed accuracy, and performs well at high dimensionality. Simulation on a CoPHiR dataset revealed its high efficiency in case of large datasets (more than an order of magnitude less metric computations at fixed recall) compared to permutation indexes. Only 0.03% of the 10 million 208-dimensional vector dataset is needed to be evaluated to achieve 0.999 recall (virtually exact search). For recall 0.93 processing speed 2800 queries/s can be achieved on a dual Intel X5675 Xenon server node with Java implementation. (C) 2013 Elsevier Ltd. All rights reserved.

关键词： Similarity search k-Nearest neighbor Approximate nearest neighbor Navigable small world distributed data structure

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：