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

IEEE/ACM Workshop on Memory Centric High Performance Computing (MCHPC)

作者： Butcher, Neil A. Olivier, Stephen L. Kogge, Peter M. Univ Notre Dame Comp Sci & Engr Notre Dame IN 46556 USA Sandia Natl Labs POB 5800 Albuquerque NM 87185 USA

ISBN: (纸本)9780738110660

Many-core systems are beginning to feature novel large, high-bandwidth intermediate memory as a visible part of the memory hierarchy. This paper discusses how to make use of intermediate memory when composing matrix multiply with transpose to compute A(*) A(T). We re-purpose the cache-oblivious approach developed by Frigo et al. and apply it to the composition of a bandwidth-bound kernel (transpose) with a compute-bound kernel (matrix multiply). Particular focus is on regions of matrix shapes far from square that are not usually considered. Our codes are simpler than optimized codes, but reasonably close in performance. Also, perhaps of more importance is developing a paradigm for how to construct other codes using intermediate memories.

关键词： cache oblivious algorithms Matrix Multiplication Multi Level Memory

来源：评论

学校读者我要写书评

暂无评论

cache oblivious algorithms for the RMQ and the RMSQ Problems

引用

MATHEMATICS IN COMPUTER SCIENCE 2010年第4期3卷 433-442页

作者： Hasan, Masud Moosa, Tanaeem M. Rahman, M. Sohel Bangladesh Univ Engn & Technol Dept Comp Sci & Engn Dhaka 1000 Bangladesh Kings Coll London Dept Comp Sci Algorithm Design Grp London England

In the Range Minimum/ Maximum Query (RMQ) and Range Maximum- Sum Segment Query (RMSQ) problems, we are given an array which we can preprocess in order to answer subsequent queries. In the RMQ query, we are given a range on the array and we need to find the maximum/minimum element within that range. On the other hand, in RMSQ query, we need to return the segment within the given query range that gives the maximum sum. In this paper, we present cache oblivious optimal algorithms for both of the above problems. In particular, for both the problems, we have presented linear time data structures having optimal cache miss. The data structures can answer the corresponding queries in constant time with constant cache miss.

关键词： algorithms cache oblivious algorithms Range minima/maxima query Range maximum-sum segment query

来源：评论

学校读者我要写书评

暂无评论

The cache Complexity of Multithreaded cache oblivious algorithms

引用

THEORY OF COMPUTING SYSTEMS 2009年第2期45卷 203-233页

作者： Frigo, Matteo Strumpen, Volker IBM Corp Austin Res Lab Austin TX 78758 USA

We present a technique for analyzing the number of cache misses incurred by multithreaded cache oblivious algorithms on an idealized parallel machine in which each processor has a private cache. We specialize this technique to computations executed by the Cilk work-stealing scheduler on a machine with dag-consistent shared memory. We show that a multithreaded cache oblivious matrix multiplication incurs O(n(3)/root Z + (Pn)(1/3)n(2)) cache misses when executed by the Cilk scheduler on a machine with P processors, each with a cache of size Z, with high probability. This bound is tighter than previously published bounds. We also present a new multithreaded cache oblivious algorithm for 1D stencil computations incurring O(n(2)/Z + n + root Pn(3+epsilon)) cache misses with high probability, one for Gaussian elimination and back substitution, and one for the length computation part of the longest common subsequence problem incurring O(n(2)/Z + root Pn(3.58)) cache misses with high probability.

关键词： cache oblivious algorithms Multithreading Stencil computations

来源：评论

学校读者我要写书评

暂无评论

The cache Complexity of Multithreaded cache oblivious algorithms 06

The Cache Complexity of Multithreaded Cache Oblivious Algori...

引用

18th Annual ACM Symposium on Parallelism in algorithms and Architectures

作者： Frigo, Matteo Strumpen, Volker IBM Corp Austin Res Lab Austin TX 78758 USA

ISBN: (纸本)9781595934529

关键词： cache oblivious algorithms Multithreading Stencil computations

来源：评论

学校读者我要写书评

暂无评论

Memory-Efficient Sierpinski-Order Traversals on Dynamically Adaptive, Recursively Structured Triangular Grids

引用

10th Nordic International Conference on Applied Parallel Computing - State of the Art in Scientific and Parallel Computing (PARA)

作者： Bader, Michael Rahnema, Kaveh Vigh, Csaba Univ Stuttgart Inst Parallel & Distributed Syst D-7000 Stuttgart Germany Tech Univ Munich Dept Informat Munich Germany

ISBN: (纸本)9783642281440;9783642281457

Adaptive mesh refinement and iterative traversals of unknowns on such adaptive grids are fundamental building blocks for PDE solvers. We discuss a respective integrated approach for grid refinement and processing of unknowns that is based on recursively structured triangular grids and space-filling element orders. In earlier work, the approach was demonstrated to be highly memory-and cache-efficient. In this paper, we analyse the cache efficiency of the traversal algorithms using the I/O model. Further, we discuss how the nested recursive traversal algorithms can be efficiently implemented. For that purpose, we compare the memory throughput of respective implementations with simple stream benchmarks, and study the dependence of memory throughput and floating point performance from the computational load per element.

关键词： adaptive mesh refinement cache oblivious algorithms space-filling curves memory-bound performance partial differential equations

来源：评论

学校读者我要写书评

暂无评论

A Synergetic Approach to Throughput Computing on x86-Based Multicore Desktops

引用

IEEE SOFTWARE 2011年第1期28卷 39-50页

作者： Luk, Chi-Keung Newton, Ryan Hasenplaugh, William Hampton, Mark Lowney, Geoff Intel

In the era of multicores, many applications that require substantial computing power and data crunching can now run on desktop PCs. However, to achieve the best possible performance, developers must write applications in a way that exploits both parallelism and cache locality. This article proposes one such approach for x86-based architectures that uses cache-oblivious techniques to divide a large problem into smaller subproblems, which are mapped to different cores or threads. The authors then use the compiler to exploit SIMD parallelism within each subproblem. Finally, they use autotuning to pick the best parameter values throughout the optimization process. The authors have implemented this approach with the Intel compiler and the newly developed Intel Software Autotuning Tool. Experimental results collected on a dual-socket quad-core Nehalem show that the approach achieves an average speed up of almost 20x over the best serial cases for an important set of computational kernels.

关键词： Multicore Throughput Computing cache oblivious algorithms Parallelization Simdization Vectorization Autotuning Intel Nehalem

来源：评论

学校读者我要写书评

暂无评论

The memory behavior of cache oblivious stencil computations

引用

JOURNAL OF SUPERCOMPUTING 2007年第2期39卷 93-112页

作者： Frigo, Matteo Strumpen, Volker IBM Corp Austin Res Lab Austin TX 78758 USA

We present and evaluate a cache oblivious algorithm for stencil computations, which arise for example in finite-difference methods. Our algorithm applies to arbitrary stencils in n-dimensional spaces. On an "ideal cache" of size Z, our algorithm saves a factor of Theta(Z(1/n)) cache misses compared to a naive algorithm, and it exploits temporal locality optimally throughout the entire memory hierarchy. We evaluate our algorithm in terms of the number of cache misses, and demonstrate that the memory behavior agrees with our theoretical predictions. Our experimental evaluation is based on a finite-difference solution of a heat diffusion problem, as well as a Gauss-Seidel iteration and a 2-dimensional LBMHD program, both reformulated as cache oblivious stencil computations.

关键词： cache oblivious algorithms stencil computations analysis of algorithms performance analysis system simulation

来源：评论

学校读者我要写书评

暂无评论

cache oblivious matrix multiplication using an element ordering based on a Peano curve

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2006年第2-3期417卷 301-313页

作者： Bader, Michael Zenger, Christoph Tech Univ Munich Inst Informat D-85748 Garching Germany

One of the keys to tap the full performance potential of current hardware is the optimal utilization of cache memory. cache oblivious algorithms are designed to inherently benefit from any underlying hierarchy of caches, but do not need to know about the exact structure of the cache. In this paper, we present a cache oblivious algorithm for matrix multiplication. The algorithm uses a block recursive structure and an element ordering that is based on Peano curves. In the resulting code, index jumps can be totally avoided, which leads to an asymptotically optimal spatial and temporal locality of the data access. (c) 2006 Elsevier Inc. All rights reserved.

关键词： cache oblivious algorithms matrix multiplication space filling curves

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：