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

2nd International Conference on Artificial Intelligence and Pattern Recognition (AIPR)

作者： Ando, Ruo Natl Inst Informat Chiyoda Ku Tokyo 1018430 Japan

ISBN: (纸本)9781450372299

Recently, the art of concurrency and parallelism has been advanced rapidly. However, conventional techniques still suffer of the drawback of lock contention. To name a few, atomic instruction has relatively low scalability as the number of iterations are increasing. This causes a serious slowdown when programmer cope with large-scale data mining processing such as clustering billions of data with numerous iterations. This paper proposes a lock-free technique of tree-based reduction for large scale clustering on GPGPU. Proposal method is divided into two steps: fine reduction and coarse reduction. In the first reduction step, the clustering program obtain K * N intermediate array where K is the number of clusters and N is the number of blocks. In the following step, new mean value is calculated over N blocks. By doing this, the clustering program can evade using atomic instruction which causes lock contention in coping with large scale clusters. In experiment, the performance of native GPU kernel with atomic instruction, Thrust template libraries and proposal method is compared and evaluated.

关键词： lock-free algorithm Large scale unsupervised clustering GPGPU K-Means Tree-based reduction CUDA

来源：评论

学校读者我要写书评

暂无评论

A lock-free algorithm of Tree-Based Reduction for Large Scale Clustering on GPGPU

A Lock-Free Algorithm of Tree-Based Reduction for Large Scal...

引用

作者： Ruo Ando National Institute of Informatics

Recently,the art of concurrency and parallelism has been advanced ***,conventional techniques still suffer of the drawback of lock *** name a few,atomic instruction has relatively low scalability as the number of iterations are *** causes a serious slowdown when programmer cope with large-scale data mining processing such as clustering billions of data with numerous *** paper proposes a lock-free technique of tree-based reduction for large scale clustering on *** method is divided into two steps:fine reduction and coarse *** the first reduction step,the clustering program obtain K * N intermediate array where K is the number of clusters and N is the number of *** the following step,new mean value is calculated over N *** doing this,the clustering program can evade using atomic instruction which causes lock contention in coping with large scale *** experiment,the performance of native GPU kernel with atomic instruction,Thrust template libraries and proposal method is compared and evaluated.

关键词： lock-free algorithm Large scale unsupervised clustering GPGPU K-Means Tree-based reduction CUDA

来源：评论

学校读者我要写书评

暂无评论

lock-free Computation of PageRank in Dynamic Graphs

Lock-free Computation of PageRank in Dynamic Graphs

引用

1st International Conference on Smart Energy Systems and Artificial Intelligence (SESAI)

作者： Sahu, Subhajit Kothapalli, Kishore Eedi, Hemalatha Peri, Sathya Int Inst Informat Technol Hyderabad Hyderabad India JNTUH Coll Engn Hyderabad Hyderabad India Indian Inst Technol Hyderabad Hyderabad India

ISBN: (纸本)9798350364613;9798350364606

PageRank is a metric that assigns importance to the vertices of a graph based on its neighbors and their scores. Recently, there has been increasing interest in computing PageRank on dynamic graphs, where the graph structure evolves due to edge insertions and deletions. However, traditional harrier-based approaches for updating PageRanks encounter significant wait times on certain graph stnictures, leading to high overall runtimes. Additionally, the growing trend of multicore architectures with increased core counts has raised concerns about random thread delays and failures. In this study, we propose a lock-free algorithm for updating PageRank scores on dynamic graphs. First, we introduce our Dynamic Frontier (DF) approach, which identifies and processes vertices likely to change PageRanks with minimal overhead. Subsequently, we integrate DF with our lock-free and fault -tolerant PageRank (Alg. DFLF), incorporating a helping mechanism among threads between its Iwo phases. Experimental results demonstrate that Alg. Mix not only eliminates waiting times at iteration barriers but also withstands random thread delays and crashes. On average, it is 4.6x faster than lock-free Naive-dynamic PageRank (Alg. NDLF).

关键词： Parallel PageRank algorithm Dynamic Frontier approach lock-free algorithm

来源：评论

学校读者我要写书评

暂无评论

FEAST: A Lightweight lock-free Concurrent Binary Search Tree

引用

ACM TRANSACTIONS ON PARALLEL COMPUTING 2020年第2期7卷 1–64页

作者： Natarajan, Aravind Ramachandran, Arunmoezhi Mittal, Neeraj Qualcomm Res Santa Clara CA 95051 USA Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA

We present a lock-free algorithm for concurrent manipulation of a binary search tree (BST) in an asynchronous shared memory system that supports search, insert, and delete operations. In addition to read and write instructions, our algorithm uses (single-word) compare-and-swap (CAS) and bit-test-and-set (BTS) read-modify-write (RMW) instructions, both of which are commonly supported by many modern processors including Intel 64 and AMD64. In contrast to most of the existing concurrent algorithms for a binary search tree, our algorithm is edge-based rather than node-based. When compared to other concurrent algorithms for a binary search tree, modify (insert and delete) operations in our algorithm (a) work on a smaller section of the tree, (b) execute fewer RMW instructions, or (c) use fewer dynamically allocated objects. In our experiments, our lock-free algorithm significantly outperformed all other algorithms for a concurrent binary search tree especially when the contention was high. We also describe modifications to our basic lock-free algorithm so that the amortized complexity of any operation in the modified algorithm can be bounded by the sum of the tree height and the point contention to within a constant factor while preserving the other desirable features of our algorithm.

关键词： Multicore system concurrent data structure lock-free algorithm binary search tree

来源：评论

学校读者我要写书评

暂无评论

Nonblocking Persistent Software Transactional Memory 27

Nonblocking Persistent Software Transactional Memory

引用

27th IEEE International Conference on High Performance Computing, Data, and Analytics (HiPC)

作者： Beadle, H. Alan Cai, Wentao Wen, Haosen Scott, Michael L. Univ Rochester Dept Comp Sci Rochester NY 14627 USA

ISBN: (纸本)9781665422925

Newly emerging nonvolatile alternatives to DRAM raise the possibility that applications might compute directly on long-lived data, rather than serializing them to and from a file system or database. To ensure crash consistency, such data must, like a file system or database, provide failure-atomic transactional semantics. Several persistent software transactional memory (STM) systems have been devised to provide these semantics, but only one-the OneFile system of Ramalhete et al.-is nonblocking. Nonblocking progress is desirable to avoid both performance anomalies due to process preemption or failures and deadlock due to priority inversion. Unfortunately, OneFile achieves nonblocking progress at the cost of 2 x space overhead, sacrificing much of the cost and density benefit of nonvolatile memory relative to DRAM. OneFile also requires extensive and intrusive changes to data declarations, and works only on a machine with double-width compare-and-swap (CAS) or load-linked/store-conditional (LL/SC) instructions. To address these limitations, we introduce QSTM, a non-blocking persistent STM that requires neither the modification of target data structures nor the availability of a wide CAS instruction. We describe our system, give arguments for safety and liveness, and compare performance to that of the Mnemosyne and OneFile persistent STM systems. We argue that modest performance costs (within a factor of 2 of OneFile in almost all cases) are easily justified by dramatically lower space overhead and higher programmer convenience.

关键词： transactional memory non-volatile memory lock-free algorithm

来源：评论

学校读者我要写书评

暂无评论

FFQ: A Fast Single-Producer/Multiple-Consumer Concurrent FIFO Queue 31

FFQ: A Fast Single-Producer/Multiple-Consumer Concurrent FIF...

引用

31st IEEE International Parallel and Distributed Processing Symposium (IPDPS)

作者： Arnautov, Sergei Fetzer, Christof Trach, Bohdan Felber, Pascal Tech Univ Dresden Dresden Germany Univ Neuchatel Neuchatel Switzerland

ISBN: (纸本)9781538639146

With the spreading of multi-core architectures, operating systems and applications are becoming increasingly more concurrent and their scalability is often limited by the primitives used to synchronize the different hardware threads. In this paper, we address the problem of how to optimize the throughput of a system with multiple producer and consumer threads. Such applications typically synchronize their threads via multiproducer/ multi-consumer FIFO queues, but existing solutions have poor scalability, as we could observe when designing a secure application framework that requires high-throughput communication between many concurrent threads. In our target system, however, the items enqueued by different producers do not necessarily need to be FIFO ordered. Hence, we propose a fast FIFO queue, FFQ, that aims at maximizing throughput by specializing the algorithm for single-producer/multiple-consumer settings: each producer has its own queue from which multiple consumers can concurrently dequeue. Furthermore, while we provide a wait-free interface for producers, we limit ourselves to lockfree consumers to eliminate the need for helping. We also propose a multi-producer variant to show which synchronization operations we were able to remove by focusing on a single producer variant. Our evaluation analyses the performance using microbenchmarks and compares our results with other state-of-the-art solutions: FFQ exhibits excellent performance and scalability.

关键词： concurrent FIFO queue concurrent queue FIFO queue lock-free algorithm SPMC queue wait-free algorithm

来源：评论

学校读者我要写书评

暂无评论

Parallel Optimization of a Type of Dynamic Hashing 3

Parallel Optimization of a Type of Dynamic Hashing

引用

3rd IEEE International Conference on Computer and Communications (ICCC)

作者： Hu Xuexuan Xi Jianqing Lin Miao Bai Weihua South China Univ Technol Sch Comp Sci & Engn Guangzhou Guangdong Peoples R China South China Univ Technol Sch Software Engn Guangzhou Guangdong Peoples R China Zhaoqing Univ Sch Comp Sci & Engn Zhaoqing Guangdong Peoples R China

ISBN: (纸本)9781509063529

Extensible hashing is a type of dynamic hashing for fast data retrieval. To improve the access efficiency for large amounts of dynamic data, it is very important to quickly retrieve, insert, delete and modify records in a hash table and to dynamically grow and shrink storage space of the hash table. This paper present a parallel implementation of an improved extensible hashing-the gEHT algorithm, it adopts a two-tiered table structure, making full use of the parallel computing power of graphic processing unit(GPU) to process efficiently the various operations of hash tables. In addition, table reuse, pre-splitting and lock-free technologies are used to improve its space and time efficiency. Experimental results show that for performance on query data, maintenance of hash tables and updating records, our algorithm is superior to the radix tree ART on a multi-core CPU and other hash indexes on the GPU, particularly in the case of high load. Moreover, improvement in the table structure causes the algorithm's expansion of table space to be far less than that of traditional extensible hashing.

关键词： extensible hashing dynamic hashing data retrieval parallel computing GPU lock-free algorithm multi-core CPU

来源：评论

学校读者我要写书评

暂无评论

A Fast lock-free Internal Binary Search Tree 15

A Fast Lock-Free Internal Binary Search Tree

引用

16th International Conference on Distributed Computing and Networking

作者： Ramachandran, Arunmoezhi Mittal, Neeraj Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA

ISBN: (纸本)9781450329286

We present a new lock-free algorithm for concurrent manipulation of a binary search tree in an asynchronous shared memory system that supports search, insert and delete operations. It combines ideas from two recently proposed lock free algorithms: one of them provides good performance for a read-dominated workload and the other one for a write dominated workload. Specifically, it uses internal representation of a search tree (as in the first one) and is based on marking edges instead of nodes (as in the second one). Our experiments indicate that our new lock-free algorithm outperforms other lock-free algorithms in most cases providing up to 35% improvement in some cases over the next best algorithm.

关键词： Concurrent Data Structure lock-free algorithm Binary Search Tree

来源：评论

学校读者我要写书评

暂无评论

Topology-Aware and Dependence-Aware Scheduling and Memory Allocation for Task-Parallel Languages

引用

ACM TRANSACTIONS ON ARCHITECTURE AND CODE OPTIMIZATION 2014年第3期11卷 181-205页

作者： Drebes, Andi Pop, Antoniu Heydemann, Karine Cohen, Albert Drach, Nathalie Univ Manchester Sch Comp Sci Manchester M13 9PL Lancs England Ecole Normale Super Dept Informat F-75005 Paris France UPMC Univ Paris 06 Sorbonne Univ CNRS UMR 7606LIP6 Paris France Ecole Normale Super F-75005 Paris France INRIA Le Chesnay France

We present a joint scheduling and memory allocation algorithm for efficient execution of task-parallel programs on non-uniform memory architecture (NUMA) systems. Task and data placement decisions are based on a static description of the memory hierarchy and on runtime information about intertask communication. Existing locality-aware scheduling strategies for fine-grained tasks have strong limitations: they are specific to some class of machines or applications, they do not handle task dependences, they require manual program annotations, or they rely on fragile profiling schemes. By contrast, our solution makes no assumption on the structure of programs or on the layout of data in memory. Experimental results, based on the Open-Stream language, show that locality of accesses to main memory of scientific applications can be increased significantly on a 64-core machine, resulting in a speedup of up to 1.63x compared to a state-of-the-art work-stealing scheduler.

关键词： Performance Languages FIFO queue dynamic scheduling work stealing lock-free algorithm weak memory model dataflow programming Kahn process network

来源：评论

学校读者我要写书评

暂无评论

Lace: Non-blocking Split Deque for Work-Stealing

Lace: Non-blocking Split Deque for Work-Stealing

引用

20th Euro-Par International Workshops

作者： van Dijk, Tom van de Pol, Jaco C. Univ Twente Dept EEMCS Formal Methods & Tools NL-7500 AE Enschede Netherlands

ISBN: (纸本)9783319143132;9783319143125

Work-stealing is an efficient method to implement load balancing in fine-grained task parallelism. Typically, concurrent deques are used for this purpose. A disadvantage of many concurrent deques is that they require expensive memory fences for local deque operations. In this paper, we propose a new non-blocking work-stealing deque based on the split task queue. Our design uses a dynamic split point between the shared and the private portions of the deque, and only requires memory fences when shrinking the shared portion. We present Lace, an implementation of work-stealing based on this deque, with an interface similar to the work-stealing library Wool, and an evaluation of Lace based on several common benchmarks. We also implement a recent approach using private deques in Lace. We show that the split deque and the private deque in Lace have similar low overhead and high scalability as Wool.

关键词： work-stealing task-based parallelism dynamic load balancing lock-free algorithm non-blocking deque

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：