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

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

来源：评论

学校读者我要写书评

暂无评论

Sorting with Asymmetric Read and Write Costs 15

Sorting with Asymmetric Read and Write Costs

引用

27th ACM symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Blelloch, Guy E. Fineman, Jeremy T. Gibbons, Phillip B. Gu, Yan Shun, Julian Carnegie Mellon Univ Pittsburgh PA 15213 USA Georgetown Univ Washington DC 20057 USA Intel Labs Santa Clara CA USA CMU Pittsburgh PA USA

ISBN: (纸本)9781450335881

Emerging memory technologies have a significant gap between the cost, both in time and in energy, of writing to memory versus reading from memory. In this paper we present models and algorithms that account for this difference, with a focus on write-efficient sorting algorithms. First, we consider the PRAM model with asymmetric write cost, and show that sorting can be performed in O(n) writes, O(n log n) reads, and logarithmic depth (parallel time). Next, we consider a variant of the External Memory (EM) model that charges k > 1 for writing a block of size B to the secondary memory, and present variants of three EM sorting algorithms (multi-way mergesort, sample sort, and heapsort using buffer trees) that asymptotically reduce the number of writes over the original algorithms, and perform roughly k block reads for every block write. Finally, we define a variant of the Ideal-cache model with asymmetric write costs, and present write-efficient, cache-oblivious parallel algorithms for sorting, FFTs, and matrix multiplication. Adapting prior bounds for work-stealing and parallel-depth-first schedulers to the asymmetric setting, these yield parallel cache complexity bounds for machines with private caches or with a shared cache, respectively.

关键词： Sorting asymmetric read-write costs non-volatile memory persistent memory write-efficient write-avoiding parallel algorithms cache-oblivious algorithms external memory model mergesort sample sort I/O buffer tree FFT matrix multiplication

来源：评论

学校读者我要写书评

暂无评论

Parallel Minimum Cuts in Near-linear Work and Low Depth 18

Parallel Minimum Cuts in Near-linear Work and Low Depth

引用

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

来源：评论

学校读者我要写书评

暂无评论

Engineering a cache-oblivious sorting algorithm

引用

ACM Journal of Experimental Algorithmics 2008年第PP1–23期12卷 1–23页

作者： Brodal, Gerth Stølting Fagerberg, Rolf Vinther, Kristoffer University of Aarhus University of Southern Denmark Odense Denmark Systematic Software Engineering A/S BRICS Department of Computer Science University of Aarhus DK-8200 Århus N IT Parken Åbogade 34 Denmark Department of Mathematics and Computer Science University of Southern Denmark DK-5230 Odense M Campusvej 55 Denmark Systematic Software Engineering A/S DK-8000 Århus C Søren Frichs Vej 39 Denmark

This paper is an algorithmic engineering study of cache-oblivious sorting. We investigate by empirical methods a number of implementation issues and parameter choices for the cache-oblivious sorting algorithm Lazy Funnelsort and compare the final algorithm with Quicksort, the established standard for comparison-based sorting, as well as with recent cache-aware proposals. The main result is a carefully implemented cache-oblivious sorting algorithm, which, our experiments show, can be faster than the best Quicksort implementation we are able to find for input sizes well within the limits of RAM. It is also at least as fast as the recent cache-aware implementations included in the test. On disk, the difference is even more pronounced regarding Quicksort and the cache-aware algorithms, whereas the algorithm is slower than a careful implementation of multiway Mergesort, such as TPIE. © 2008 ACM.

关键词： cache-oblivious algorithms Funnelsort Quicksort

来源：评论

学校读者我要写书评

暂无评论

Closing the Gap Between cache-oblivious and cache-adaptive Analysis 20

Closing the Gap Between Cache-oblivious and Cache-adaptive A...

引用

32nd ACM Symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Bender, Michael A. Chowdhury, Rezaul A. Das, Rathish Johnson, Rob Kuszmaul, William Lincoln, Andrea Liu, Quanquan C. Lynch, Jayson Xu, Helen SUNY Stony Brook Stony Brook NY 11794 USA VMware Res Palo Alto CA USA MIT CSAIL 77 Massachusetts Ave Cambridge MA 02139 USA

ISBN: (纸本)9781450369350

cache-adaptive analysis was introduced to analyze the performance of an algorithm when the cache (or internal memory) available to the algorithm dynamically changes size. These memory-size fluctuations are, in fact, the common case in multi-core machines, where threads share cache and RAM. An algorithm is said to be efficiently cache-adaptive if it achieves optimal utilization of the dynamically changing cache. cache-adaptive analysis was inspired by cache-oblivious analysis. Many (or even most) optimal cache-oblivious algorithms have an (a, b, c)-regular recursive structure. Such (a, b, c)-regular algorithms include Longest Common Subsequence, All Pairs Shortest Paths, Matrix Multiplication, Edit Distance, Gaussian Elimination Paradigm, etc. Bender et al. (2016) showed that some of these optimal cache-oblivious algorithms remain optimal even when cache changes size dynamically, but that in general they can be as much as logarithmic factor away from optimal. However, their analysis depends on constructing a highly structured, worst-case memory profile, or sequences of fluctuations in cache size. These worst-case profiles seem fragile, suggesting that the logarithmic gap may be an artifact of an unrealistically powerful adversary. We close the gap between cache-oblivious and cache-adaptive analysis by showing how to make a smoothed analysis of cache-adaptive algorithms via random reshuffling of memory fluctuations. Remarkably, we also show the limits of several natural forms of smoothing, including random perturbations of the cache size and randomizing the algorithm's starting time. Nonetheless, we show that if one takes an arbitrary profile and performs a random shuffle on when "significant events" occur within the profile, then the shuffled profile becomes optimally cache-adaptive in expectation, even when the initial profile is adversarially constructed. These results suggest that cache-obliviousness is a solid foundation for achieving cache-adaptivity when the me

关键词： cache-adaptive algorithms smoothed analysis 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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：