问题标签 [cache-oblivious]

我理解缓存不经意的表达是什么意思。但是我想知道是否有任何简单的解释可以解释如何设计可以优化使用缓存的数据结构，而不知道缓存的大小。

您能否提供这样的解释，最好是一个（简单的）示例？

我想使用隐式指针实现一个使用 van Emde Boas 布局存储在数组中的缓存忽略二叉树。树中的所有项目都是 32 位整数，树会变得相当大，因此存储指针意味着至少 3 倍以上的数据。

问题是，给定节点索引（我可以在遍历树时跟踪任何信息），我想不出任何非迭代方法来计算指向左右子节点的指针。许多论文/讲座都提到了这种带有隐式指针的树，但我还没有看到计算指针的算法。有没有一种有效的方法来做到这一点？

我已经阅读了很多关于 Cache Oblivious Algorithms 和 Streaming trees 等的内容。我了解了我仍然无法看到的基础知识，为什么它们对并行编程有好处？我想我看到约翰哈罗普说他们是革命性的。

我读过可以使用加倍数组来实现缓存遗忘堆栈。

有人可以解释一下分析如何使每次推送和弹出都具有1/B摊销的 I/O 复杂性吗？

请原谅这个愚蠢的问题，但我没有通过谷歌搜索找到任何提示。

如果我有一个数组（连续内存），并且我按顺序搜索给定的模式（例如构建所有偶数的列表），我是否使用缓存忽略算法？是的，它作为一种算法非常愚蠢，但我想在这里理解:)

我想通过使用 morton 顺序来转置矩阵以进行改进矩阵转置。

我找到了一些关于 morton order 的文章，但我不明白如何使用它。

尤其，

和

我想反转这个矩阵 A = [1 2 3 4; 5 6 7 8；9 10 11 12；13 14 15 16]（线性地址）

至

B = [1 2 5 6; 3 4 7 8; 9 10 13 14；11 12 15 16；]。

然后转置。

但是我解决不了......

有人知道这种转变的原理吗？

真的提前谢谢了。

缓存（遗忘|最佳|感知）算法通常会在其模型中考虑寻道时间。如果没有，是否有考虑寻道时间的模型示例，以及该模型中的算法分析。

I am pressed for time to optimize a large piece of C code for speed and I am looking for an algorithm---at the best a C "snippet"---that transposes a rectangular source matrix u[r][c] of arbitrary size (r number of rows, c number of columns) into a target matrix v[s][d] (s = c number of rows, d = r number of columns) in a "cache-friendly" i. e. data-locality respecting way. The typical size of u is around 5000 ... 15000 rows by 50 to 500 columns, and it is clear that a row-wise access of elements is very cache-inefficient.

There are many discussions on this topic in the web (nearby this thread), but as far as I see all of them discuss the spacial cases like square matrices, u[r][r], or the definition an on-dimensional array, e. g. u[r * c], not the above mentioned "array of arrays" (of equal length) used in my context of Numerical Recipes (background see here).

I would by very thankful for any hint that helps to spare me the "reinvention of the wheel".

Martin

我正在研究 wiki 文章中描述的方法的实现，用于方阵的就地缓存不经意转置。

https://en.wikipedia.org/wiki/In-place_matrix_transposition

该算法基本上递归地将矩阵分成四个，然后转置沿对角线的象限并交换其上方和下方的象限。实际的转置/交换仅在矩阵大小为 2*2 或更低时发生，否则将再次拆分。

我把它分成三个功能：

这将启动给定大小 N 的过程：

然后：

最后：

但是，这行不通，我正在努力看看我的逻辑在哪里出错了。

编辑：输出示例

正确的输出应该是转置矩阵。

编辑：主要功能和声明：

完整代码的链接：https ://jpst.it/QaBq