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

30th ACM Symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Geissmann, Barbara Gianinazzi, Lukas Swiss Fed Inst Technol Dept Comp Sci Zurich Switzerland

ISBN: (纸本)9781450357999

We present the first near-linear work and poly-logritharithmic depth algorithm for computing a minimum cut in a graph, while previous parallel algorithms with poly-logarithmic depth required at least quadratic work in the number of vertices. In a graph with n vertices andm edges, our algorithm computes the correct result with high probability in O(m log(4) n) work and O(log(3) n) depth. This result is obtained by parallelizing a data structure that aggregates weights along paths in a tree and by exploiting the connection between minimum cuts and approximate maximum packings of spanning trees. In addition, our algorithm improves upon bounds on the number of cache misses incurred to compute a minimum cut.

关键词： Minimum Cut Graph algorithms Minimum Path Data Structure Parallel algorithms cache-oblivious algorithms

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: cache-oblivious Scheduling of Streaming Applications

Brief Announcement: Cache-Oblivious Scheduling of Streaming ...

引用

26th ACM Symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Agrawal, Kunal Fineman, Jeremy T. Washington Univ St Louis MO 63110 USA Georgetown Univ Washington DC 20057 USA

This paper considers the problem of cache-obliviously scheduling streaming pipelines on uniprocessors with the goal of minimizing cache misses. Our recursive algorithm is not parameterized by cache size, yet it achiev... 详细信息

ISBN: (纸本)9781450328210

关键词： cache-oblivious algorithms Caching Partitioning Pipelines Scheduling Streaming Synchronous Data Flow

来源：评论

学校读者我要写书评

暂无评论

cache-oblivious Hashing 10

Cache-Oblivious Hashing

引用

29th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems

作者： Pagh, Rasmus Wei, Zhewei Yi, Ke Zhang, Qin IT Univ Copenhagen Copenhagen Denmark Hong Kong Univ Sci & Technol Hong Kong Hong Kong Peoples R China

ISBN: (纸本)9781450300339

The hash table, especially its external memory version, is one of the most important index structures in large databases. Assuming a truly random hash function, it is known that in a standard external hash table with block size b, searching for a particular key only takes expected average t(q) = 1+1/2(Omega(b)) disk accesses for any load factor a bounded away from 1. However, such near-perfect performance is achieved only when b is known and the hash table is particularly tuned for working with such a blocking. In this paper we study if it is possible to build a cache-oblivious hash table that works well with any blocking. Such a hash table will automatically perform well across all levels of the memory hierarchy and does not need any hardware-specific tuning, an important feature in autonomous databases. We first show that linear probing, a classical collision resolution strategy for hash tables, can be easily made cache-oblivious but it only achieves t(q) = 1 + O(alpha/b). Then we demonstrate that it is possible to obtain tq = 1 + 1/2(Omega(b)), thus matching the cache-aware bound, if the following two conditions hold: (a) b is a power of 2;and (b) every block starts at a memory address divisible by b. Both conditions hold on a real machine, although they are not stated in the cache-oblivious model. Interestingly, we also show that neither condition is dispensable: if either of them is removed, the best obtainable bound is tq = 1 + O(alpha/b), which is exactly what linear probing achieves.

关键词： cache-oblivious algorithms hashing

来源：评论

学校读者我要写书评

暂无评论

An Experimental Comparison of cache-oblivious and cache-conscious Programs 07

An Experimental Comparison of Cache-oblivious and Cache-cons...

引用

19th Annual Symposium on Parallelism in algorithms and Architectures

作者： Yotov, Kamen Roeder, Tom Pingali, Keshav Gunnels, John Gustavson, Fred Cornell Univ Ithaca NY 14853 USA IBM Corp TJ Watson Res Ctr Armonk NY 10504 USA

ISBN: (纸本)9781595936677

cache-oblivious algorithms have been advanced as a way of circumventing some of the difficulties of optimizing applications to take advantage of the memory hierarchy of modern microprocessors. These algorithms are based on the divide-and-conquer paradigm - each division step creates sub-problems of smaller size, and when the working set of a sub-problem fits in some level of the memory hierarchy, the computations in that sub-problem can be executed without suffering capacity misses at that level. In this way, divide-and-conquer algorithms adapt automatically to all levels of the memory hierarchy;in fact, for problems like matrix multiplication, matrix transpose, and FFT, these recursive algorithms are optimal to within constant factors for some theoretical models of the memory hierarchy. An important question is the following: how well do carefully tuned cache-oblivious programs perform compared to carefully tuned cache-conscious programs for the same problem? Is there a price for obliviousness, and if so, how much performance do we lose? Somewhat surprisingly, there are few studies in the literature that have addressed this question. This paper reports the results of such a study in the domain of dense linear algebra. Our main finding is that in this domain;even highly optimized cache-oblivious programs perform significantly worse than corresponding cache-conscious programs. We provide insights into why this is so, and suggest research directions for making cache-oblivious algorithms more competitive.

关键词： Memory hierarchy Memory Latency Memory bandwidth cache-oblivious algorithms cache-conscious algorithms Numerical Software

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Low Depth cache-oblivious Sorting 09

Brief Announcement: Low Depth Cache-Oblivious Sorting

引用

21st ACM Symposium on Parallelism in algorithms and Architectures

作者： Blelloch, Guy E. Gibbons, Phillip B. Simhadri, Harsha Vardhan Carnegie Mellon Univ Pittsburgh PA 15213 USA

ISBN: (纸本)9781605586069

cache-oblivious algorithms have the advantage of achieving good sequential cache complexity across all levels of a multi-level cache hierarchy, regardless of the specifies (cache size and cache line size) of each level. In this paper, we describe cache-oblivious sorting algorithms with optimal work, optimal cache complexity and polylogarithmic depth. Using known mappings, these lead to low cache complexities on shared-memory multiprocessors with a single level of private caches or a single shared cache. Moreover, the low cache complexities extend to shared-memory multiprocessors with common configurations of multi-level caches. The key factor in the low cache complexity on multiprocessors is the low depth of the algorithms we propose.

关键词： cache-oblivious algorithms sorting parallel algorithms multiprocessors schedulers

来源：评论

学校读者我要写书评

暂无评论

Dynamic programming in faulty memory hierarchies (cache-obliviously)

Dynamic programming in faulty memory hierarchies (cache-obli...

引用

31st IARCS Annual International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)

作者： Caminiti, Saverio Finocchi, Irene Fusco, Emanuele G. Silvestri, Francesco Univ Roma La Sapienza Dept Comp Sci Rome Italy Univ Padua Dept Informat Engn I-35100 Padua Italy

ISBN: (纸本)9783939897347

Random access memories suffer from transient errors that lead the logical state of some bits to be read differently from how they were last written. Due to technological constraints, caches in the memory hierarchy of modern computer platforms appear to be particularly prone to bit flips. Since algorithms implicitly assume data to be stored in reliable memories, they might easily exhibit unpredictable behaviors even in the presence of a small number of faults. In this paper we investigate the design of dynamic programming algorithms in faulty memory hierarchies. Previous works on resilient algorithms considered a one-level faulty memory model and, with respect to dynamic programming, could address only problems with local dependencies. Our improvement upon these works is two-fold: (1) we significantly extend the class of problems that can be solved resiliently via dynamic programming in the presence of faults, settling challenging non-local problems such as all-pairs shortest paths and matrix multiplication;(2) we investigate the connection between resiliency and cache-efficiency, providing cache-oblivious implementations that incur an (almost) optimal number of cache misses. Our approach yields the first resilient algorithms that can tolerate faults at any level of the memory hierarchy, while maintaining cache-efficiency. All our algorithms are correct with high probability and match the running time and cache misses of their standard non-resilient counterparts while tolerating a large (polynomial) number of faults. Our results also extend to Fast Fourier Transform.

关键词： Unreliable memories fault-tolerant algorithms dynamic programming cache-oblivious algorithms Gaussian elimination paradigm

来源：评论

学校读者我要写书评

暂无评论

Praktické datové struktury

Praktické datové struktury

引用

作者： Pokorný, Michael Charles University of Prague

In this thesis, we implement several data structures for ordered and unordered dictionaries and we benchmark their performance in main memory on synthetic and practical workloads. Our survey includes both well-known data structures (B-trees, red-black trees, splay trees and hashing) and more exotic approaches (k-splay trees and k-forests). Powered by TCPDF (***)

关键词： cache-oblivious algorithms data structures dictionaries search trees

来源：评论

学校读者我要写书评

暂无评论

Compact I/O-Efficient Graph Representations

Compact I/O-Efficient Graph Representations

引用

作者： Tětek, Jakub Charles University of Prague

The objective of this thesis is to develop a fast memory-efficient representa- tion of some graphs that occur in real-world applications. We consider separable graph classes (e.g. planar graphs or graphs of bounded genus) and show how to represent them in a way that (1) makes accessing vertices in a walk cache-efficient on average and (2) is highly memory-efficient. In particular, we show a compact representation of separable graph classes with the I/O cost of a random walk of length k being O(K/(Bw)1−c ) w.h.p. In the second part of the thesis, we consider layout of trees with optimal worst-case I/O cost for root-to-leaf traversal, show an additive (+1)-approximation of I/O optimal compact layout and contrast this with a proof of NP-hardness of exact solution. In this thesis, we also prove generalisations of the recursive separator theo- rem. The first one generalises the theorem for weighted graphs and the second one replaces minimum region size by average region size in the bound. 1

关键词： graph theory cache-oblivious algorithms compact representation separable graphs

来源：评论

学校读者我要写书评

暂无评论

cache-oblivious Hilbert Curve-based Blocking Scheme for Matrix Transposition

引用

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 2022年第4期48卷 37-37页

作者： Ferreira Alves, Joao Nuno Silveira Russo, Luis Manuel Francisco, Alexandre INESC ID R Alves Redol 9 Lisbon Portugal

This article presents a fast SIMD Hilbert space-filling curve generator, which supports a new cache-oblivious blocking-scheme technique applied to the out-of-place transposition of general matrices. Matrix operations found in high performance computing libraries are usually parameterized based on host microprocessor specifications to minimize data movement within the different levels of memory hierarchy. The performance of cache-oblivious algorithms does not rely on such parameterizations. This type of algorithm provides an elegant and portable solution to address the lack of standardization in modern-day processors. Our solution consists in an iterative blocking scheme that takes advantage of the locality-preserving properties of Hilbert space-filling curves to minimize data movement in any memory hierarchy. This scheme traverses the input matrix, in O(nm) time and space, improving the behavior of matrix algorithms that inherently present poor memory locality. The application of this technique to the problem of out-of-place matrix transposition achieved competitive results when compared to state-of-the-art approaches. The performance of our solution surpassed Intel MKL version after employing standard software prefetching techniques.

关键词： cache-oblivious algorithms out-of-place transposition Hilbert spacefilling curve dense matrix

来源：评论

学校读者我要写书评

暂无评论

POSTER: cache-oblivious MPI All-to-All Communications on Many-Core Architectures 17

POSTER: Cache-Oblivious MPI All-to-All Communications on Man...

引用

Proceedings of the 22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

作者： Shigang Li Yunquan Zhang Torsten Hoefler Institute of Computing Technology Chinese Academy of Sciences Beijing China ETH Zurich Zurich Switzerland

ISBN: (纸本)9781450344937

In the many-core era, the performance of MPI collectives is more dependent on the intra-node communication component. However, the communication algorithms generally inherit from the inter-node version and ignore the cache complexity. We propose cache-oblivious algorithms for MPI all-to-all operations, in which data blocks are copied into the receive buffers in Morton order to exploit data locality. Experimental results on different many-core architectures show that our cache-oblivious implementations significantly outperform the naive implementations based on shared heap and the highly optimized MPI libraries.

关键词： mpi_alltoall many-core cache-oblivious algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：