2

编辑 - 我想我问的问题太长了,所以我把它说得很具体。

问题:如果内存位置在 L1 缓存中并且未标记为脏。假设它有一个值 X。如果你尝试将 X 写入同一个位置会发生什么?是否有任何 CPU 会看到这样的写入是多余的并跳过它?

例如,是否存在比较两个值并丢弃冗余写回主存储器的优化?具体来说,主流处理器是如何处理这个问题的?当值是像 0 这样的特殊值时呢?如果即使对于像 0 这样的特殊值也没有这样的优化,那有什么原因吗?

动机:我们有一个可以轻松放入缓存的缓冲区。多个线程可能会通过相互回收来使用它。每次使用都涉及写入缓冲区中的n 个位置(不一定是连续的)。回收只是意味着将所有值设置为 0。每次回收时,大小 n 个位置已经为 0。在我看来(直觉上)避免如此多的冗余回写会使回收过程更快,因此是个问题。

在代码中这样做没有意义,因为分支指令本身可能会导致不必要的缓存未命中(if (buf[i]) {...} )

4

3 回答 3

1

我不知道有任何处理器可以进行您描述的优化 - 消除不会改变值的清理缓存行的写入 - 但这是一个好问题,一个好主意,伟大的思想都一样。

我写了一个很大的回复,然后我想起来了:这在文献中被称为“沉默的商店”。参见“无声商店免费”,K. Lepak 和 M Lipasti,UWisc,MICRO-33,2000。

无论如何,在我的回复中,我描述了一些实施问题。

顺便说一句,USEnet 新闻组 comp.arch 中经常讨论此类主题。

我也在我的 wiki 上写过它们,http://comp-arch.net

于 2012-03-18T06:58:48.300 回答
1

您建议的硬件优化不会减少延迟。考虑最低级别的操作:

  1. 该位置的旧值从缓存加载到 CPU(假设它已经在缓存中)。
  2. 比较旧值和新值。
  3. 如果新旧值不同,则将新值写入缓存。否则将被忽略。

第 1 步实际上可能比第 2 步和第 3 步花费更长的时间。这是因为第 2 步和第 3 步无法开始,直到第 1 步中的旧值被带入 CPU。如果用软件实现,情况也会一样。

考虑我们是否只是将新值写入缓存,而不检查旧值。它实际上比上面提到的三步过程更快,原因有两个。首先,无需等待旧值。其次,CPU 可以简单地在输出缓冲区中安排写操作。输出缓冲区可以同时执行缓存写入,而 ALU 可以开始处理其他事情。

到目前为止,所涉及的唯一延迟是 CPU 和缓存之间的延迟,而不是缓存和主内存之间的延迟。


现代微处理器中的情况更为复杂,因为它们的高速缓存被组织成高速缓存行。当一个字节值被写入高速缓存行时,必须加载完整的高速缓存行,因为未重写的高速缓存行的另一部分必须保留其旧值。

http://blogs.amd.com/developer/tag/sse4a/

  • 缓存命中:数据从缓存行读取到目标寄存器
  • 缓存未命中:数据从内存移动到缓存,并读入目标寄存器
  • 缓存命中:数据从寄存器移动到缓存行
  • 缓存未命中:将缓存行取到缓存中,将寄存器中的数据移到缓存行
于 2010-07-27T04:43:12.910 回答
0

这不是您关于计算机体系结构的原始问题的答案,但可能与您的目标相关。

在这个讨论中,所有数组索引都从零开始。


假设n远小于size,请更改您的算法以保存两条信息:

  1. 大小数组
  2. 一个n数组和一个计数器,用于模拟一个集合容器。允许重复值。

每次将非零值写入全尺寸数组中的索引k时,将值k插入到集合容器中。

当需要清除全尺寸数组时,获取存储在 set 容器中的每个值(其中将包含k等),并将全尺寸数组中的每个对应索引设置为零。


也可以使用称为两级直方图或基数直方图的类似技术。

存储两条信息:

  1. 一个数组size
  2. 的布尔数组ceil(size / M),其中M是基数。ceil是天花板函数。

每次将非零值写入全尺寸数组中的索引kfloor(k / M)时,都应标记布尔数组中的元素。

比方说,bool_array[j]被标记了。这对应于全尺寸数组中从j*M到的范围。(j+1)*M-1

当需要清空全长数组时,扫描布尔数组是否有任何标记的元素,全长数组中对应的范围应该被清空。

于 2010-07-25T20:15:34.297 回答