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

作者： Mička, Ondřej Charles University of Prague

Modern computers employ a sophisticated hierarchy of caches to decrease the latency of memory accesses. This led to the development of cache-oblivious algorithms that strive to achieve the best possible performance on such memory hierarchies with minimal knowledge of the exact parameters of the hierarchy. A common technique used in the design of cache-oblivious algorithms is a recursion-based divide-and-conquer method. In this work, we show an alternative technique based on the Gray codes. We use the binary reflected Gray code to traverse arrays in the cache-oblivious way, allowing us to design algorithms for problems such as matrix transposition, naive matrix multiplication or naive convolution that match the asymptotic performance of their recursion-based counterparts. The advantage is that our algorithms can be implemented without recursion (or a stack that simulates it) by using a loopless algorithm. We also introduce a variant of the binary reflected Gray code tuned to certain applications of our technique and an almost loopless algorithm to generate it. Apart from the theoretical analysis of our techniques performance, we also examine its practical performance on the problem of matrix transposition.

关键词： Gray codes cache-oblivious algorithms

来源：评论

学校读者我要写书评

暂无评论

Parallel Minimum Cuts in Near-linear Work and Low Depth

引用

ACM TRANSACTIONS ON PARALLEL COMPUTING 2021年第2期8卷 1–20页

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

We present the first near-linear work and poly-logarithmic depth algorithm for computing a minimum cut in an undirected graph. Previous parallel algorithms with poly-logarithmic depth required at least quadratic work in the number of vertices. In a graph with n vertices and m edges, our randomized algorithm computes the minimum cut 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, in addition 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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Extending the limits for big data RSA cracking: Towards cache-oblivious TU decomposition

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2020年第0期138卷 65-77页

作者： Abu Salem, Fatima K. Al Arab, Mira Yang, Laurence T. Amer Univ Beirut Comp Sci Dept Beirut Lebanon St Francis Xavier Univ Dept Comp Sci Antagonish NS Canada

Nowadays, Big Data security processes require mining large amounts of content that was traditionally not typically used for security analysis in the past. The RSA algorithm has become the de facto standard for encryption, especially for data sent over the internet. RSA takes its security from the hardness of the Integer Factorisation Problem. As the size of the modulus of an RSA key grows with the number of bytes to be encrypted, the corresponding linear system to be solved in the adversary integer factorisation algorithm also grows. In the age of big data this makes it compelling to redesign linear solvers over finite fields so that they exploit the memory hierarchy. To this end, we examine several matrix layouts based on space-filling curves that allow for a cache-oblivious adaptation of parallel TU decomposition for rectangular matrices over finite fields. The TU algorithm of Dumas and Roche (2002) requires index conversion routines for which the cost to encode and decode the chosen curve is significant. Using a detailed analysis of the number of bit operations required for the encoding and decoding procedures, and filtering the cost of lookup tables that represent the recursive decomposition of the Hilbert curve, we show that the Morton-hybrid order incurs the least cost for index conversion routines that are required throughout the matrix decomposition as compared to the Hilbert, Peano, or Morton orders. The motivation lies in that cache efficient parallel adaptations for which the natural sequential evaluation order demonstrates lower cache miss rate result in overall faster performance on parallel machines with private or shared caches and on GPU's. (C) 2019 Elsevier Inc. All rights reserved.

关键词： Exact linear algebra cache-oblivious algorithms Space-filling curves Morton-hybrid order

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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 MPI All-to-All Communications Based on Morton Order

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2018年第3期29卷 542-555页

作者： Li, Shigang Zhang, Yunquan Hoefler, Torsten Chinese Acad Sci Inst Comp Technol State Key Lab Comp Architecture Beijing 100864 Peoples R China ETH Dept Comp Sci CH-8092 Zurich Switzerland

Many-core systems with a rapidly increasing number of cores pose a significant challenge to parallel applications to use their complex memory hierarchies efficiently. Many such applications rely on collective communications in performance-critical phases, which become a bottleneck if they are not optimized. We address this issue by proposing cache-oblivious algorithms for MPI_Alltoall, MPI_Allgather, and the MPI neighborhood collectives to exploit the data locality. To implement the cache-oblivious algorithms, we allocate the send and receive buffers on a shared heap and use Morton order to guide the memory copies. Our analysis shows that our algorithm for MPI_Alltoall is asymptotically optimal. We show an extension to our algorithms to minimize the communication distance on NUMA systems while maintaining optimality within each socket. We further demonstrate how the cache-oblivious algorithms can be applied to multi-node machines. Experiments are conducted on different many-core architectures. For MPI_Alltoall, our implementation achieves on average 1.40X speedup over the naive implementation based on shared heap for small and medium block sizes (less than 16 KB) on a Xeon Phi KNC, achieves on average 3.03X speedup over MVAPICH2 on a Xeon E7-8890, and achieves on average 2.23X speedup over MVAPICH2 on a 256-node Xeon E5-2680 cluster for block sizes less than 1 KB.

关键词： cache-oblivious algorithms collective communication NUMA MPI_Alltoall MPI_Allgather neighborhood collectives

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Resilient Dynamic Programming

引用

ALGORITHMICA 2017年第2期77卷 389-425页

作者： Caminiti, Saverio Finocchi, Irene Fusco, Emanuele G. Silvestri, Francesco Sapienza Univ Rome Dept Comp Sci Rome Italy Univ Padua Dept Informat Engn Padua Italy IT Univ Copenhagen Copenhagen Denmark

We investigate the design of dynamic programming algorithms in unreliable memories, i.e., in the presence of errors that lead the logical state of some bits to be read differently from how they were last written. Assuming that a limited number of memory faults can be inserted at run-time by an adversary with unbounded computational power, we obtain the first resilient algorithms for a broad range of dynamic programming problems, devising a general framework that can be applied to both iterative and recursive implementations. Besides all local dependency problems, where updates to table entries are determined by the contents of neighboring cells, we also settle challenging non-local problems, such as all-pairs shortest paths and matrix multiplication. All our algorithms are correct with high probability and match the running time of their standard non-resilient counterparts while tolerating a polynomial number of faults. The recursive algorithms are also cache-efficient and can tolerate faults at any level of the memory hierarchy. Our results exploit a careful combination of data replication, majority techniques, fingerprint computations, and lazy fault detection. To cope with the complex data access patterns induced by some of our algorithms, we also devise amplified fingerprints, which might be of independent interest in the design of resilient algorithms for different problems.

关键词： Dynamic programming cache-oblivious algorithms Gaussian Elimination Paradigm Memory faults Resilient computing

来源：评论

学校读者我要写书评

暂无评论

cache-oblivious MPI All-to-All Communications on Many-Core Architectures 22

Cache-Oblivious MPI All-to-All Communications on Many-Core A...

引用

22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP)

作者： Li, Shigang Zhang, Yunquan Hoefler, Torsten Chinese Acad Sci Inst Comp Technol SKL Comp Architecture Beijing Peoples R China Swiss Fed Inst Technol Dept Comp Sci 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.

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：