标签: cpu-cache

我有一个问题....我正在while循环中将数据写入数组.关键是我经常这样做.似乎这篇文章现在是代码中的瓶颈.所以我认为它是由写入内存引起的.这个数组不是很大(像300个元素一样).问题是可以这样做:将它存储在缓存中并仅在while循环完成后才在内存中更新？

[编辑 - 复制自Alex添加的答案]

double* array1  = new double[1000000]; // this array has elements  
unsigned long* array2  = unsigned long[300];
double varX,t,sum=0;
int iter=0,i=0;
while(i<=max_steps)
{
   varX+=difX;
   nm0 =  int(varX);
   if(nm1!=nm0)
   {
        array2[iter] = nm0;  // if you comment this string application works more then 2 times faster :)
        nm1=nm0;
        t = array1[nm0]; // if you comment this string , there is almost no change in time 
        ++iter;
   }
   sum+=t;
   ++i;
}

首先,我要感谢你们所有人的回答.实际上,不放置代码有点蠢.所以我现在决定这样做.

double* array1  = new double[1000000]; // this …

我想在ARM Cortex A8处理器上移植一小段代码.L1缓存和L2缓存都非常有限.我的程序中有3个数组.其中两个是按顺序访问的(大小>阵列A:6MB,阵列B:3MB),第三个阵列(大小>阵列C:3MB)的访问模式是不可预测的.虽然计算不是很严格,但是访问阵列C时存在巨大的缓存未命中.我认为一种解决方案是为阵列C分配更多的缓存(L2)空间,而对于阵列A和B则分配更少.但我不能找到任何方法来实现这一目标.我经历了ARM的预加载引擎但找不到任何有用的东西.

最新的英特尔XEON处理器拥有30MB的L3内存,足以容纳薄型1管理程序.

我有兴趣了解如何在CPU中保留这样的Hypervisor,即防止被刷新到RAM,或者至少在发送到内存/磁盘之前加密数据.

假设我们使用裸机运行,我们可以使用DRTM(延迟启动)来引导它,例如我们从不受信任的内存/磁盘加载,但是如果我们可以解密()用于解密的秘密,我们只能加载真实的操作系统.操作系统,在设置了适当的规则以确保发送到RAM的任何内容都已加密后进行.

ps我知道T​​XT的ACEA又称ACRAM(认证代码执行区域又称认证代码RAM)据说有这样的保证(即它限制在CPU缓存中)所以我想知道是否可以在此周围做一些技巧.

pps这似乎超出了目前的研究范围,所以我实际上并不确定答案是否可行.

我试图重现这里提供的结果每位程序员应该了解的内存,特别是下图所示的结果(文中的第20-21页)

基本上,对于不同的工作尺寸,每个元素的周期图,图中的突然上升位于工作集大小超过高速缓存大小的点.

为了实现这一点,我在这里编写了这段代码.我看到所有数据都是从内存中提取的(通过每次使用clflush刷新缓存),所有数据大小的性能都是相同的(如预期的那样),但是随着缓存的运行,我看到完全相反的趋势

Working Set: 16 Kb took 72.62 ticks per access
Working Set: 32 Kb took 46.31 ticks per access
Working Set: 64 Kb took 28.19 ticks per access
Working Set: 128 Kb took 23.70 ticks per access
Working Set: 256 Kb took 20.92 ticks per access
Working Set: 512 Kb took 35.07 ticks per access
Working Set: 1024 Kb took 24.59 ticks per access
Working Set: 2048 Kb took 24.44 ticks per …

所以我们一直负责编译一些代码(我们应该把它当作黑盒子),使用不同的intel编译器优化标志(-O1和-O3)以及矢量化标志(-xhost和 - no-vec)并观察以下变化:

• 执行时间处理时间
• 浮点运算(FPOs)
• L2和L3缓存丢失率

在执行这些优化之后,我们注意到执行时间的下降,这是预期的,考虑到编译器为了提高效率而对代码所做的所有更改.然而,我们也注意到FPO数量的下降,虽然我们知道这是一件好事,但我们不确定它为什么会发生.此外,我们注意到(并且无法解释)L2缓存未命中率的增加(随着优化级别的增加而增加),但缓存访问没有显着增加,并且L3级别几乎没有变化.

完全不使用矢量化或优化就L2缓存丢失率产生了最好的结果,我们想知道你们是否可以给我们一些见解,以及我们可以用来加深知识的支持文档,文献和资源关于这个话题.

谢谢.

编辑:使用的编译器选项是:

• O0 -no-vec(最高执行时间,最低L2缓存未命中)
• O1(执行时间越少,L2缓存未命中率越高)
• O3(更少的执行时间,甚至更高的L2缓存未命中)
• xhost(-O3执行时间相同,最高L2缓存未命中)

更新:

虽然整体L2缓存访问量略有下降,但实际未命中率却大幅增加.

使用-0O -no-vec

使用中的挂钟时间:13,957,075

• L2缓存未命中:207,460,564
• L2缓存访问:1,476,540,355
• L2缓存未命中率:0.140504
• L3缓存未命中:24,841,999
• L3缓存访问:207,460,564
• L3缓存未命中率:0.119743

使用-xhost

挂钟时间在usecs:4,465,243

• L2缓存未命中:547,305,377
• L2缓存访问:1,051,949,467
• L2缓存未命中率:0.520277
• L3缓存未命中:86,919,153
• L3缓存访问:547,305,377
• L3缓存未命中率:0.158813

我试图用来clflush手动驱逐缓存行,以确定缓存和行大小.我没有找到任何关于如何使用该指令的指南.我所看到的,是一些使用更高级别功能的代码.

有一个内核函数void clflush_cache_range(void *vaddr, unsigned int size),但我仍然不知道在我的代码中包含什么以及如何使用它.我不知道size该功能是什么.

更重要的是,我怎样才能确定该行被驱逐以验证我的代码的正确性？

更新:

这是我想要做的初始代码.

#include <immintrin.h>
#include <stdint.h>
#include <x86intrin.h>
#include <stdio.h>
int main()
{
  int array[ 100 ];
  /* will bring array in the cache */
  for ( int i = 0; i < 100; i++ )
    array[ i ] = i;

  /* FLUSH A LINE */
  /* each element is 4 bytes */
  /* assuming that cache line size is 64 bytes */
  /* array[0] till …

我正在尝试设计一个缓存模拟器。为了找到一个块的缓存命中/未命中，我将它的索引和偏移量与缓存中已经存在的块进行比较。在 n 关联缓存的情况下，我只检查该块可以去的那些缓存条目。

找到命中和冷未命中的数量是微不足道的。如果缓存已满（或者块可以进入的所有条目都已被占用），那么我们就会出现容量缺失。

有人可以告诉我如何找到冲突未命中的数量吗？冲突未命中的定义说：

Conflict misses are those misses that could have been avoided, 
had the cache not evicted an entry earlier

如何确定较早从缓存中删除的条目是否应该或不应该被删除？

我有一个独立的 NVIDIA GPU（例如 Kepler 或 Maxwell）。我想在调度某些内核之前清除 L2 缓存，以免污染我的测试结果。

我可以做一些事情，比如分配一大块内存并按顺序读取远处的大量内存，这可能会起作用。但我宁愿做一些简单的事情......

笔记：

• 我也对如何在 OpenCL 中做到这一点感兴趣，尽管不太感兴趣。
• PTX 内联是可以接受的（但我宁愿编写正确的代码）。

我正在尝试用C++实现股票匹配引擎/订单簿,并且正在寻找更加缓存友好的架构.目前,我的数据结构如下:

• 极限价格的侵入式rb-tree.
• 用于以限价价格持有订单的侵入性双重链表.

我已经考虑过替换rb-tree的方法,例如本身链接的稀疏数组的稀疏数组,但我相信rb-tree是一个更好的用例,因为我正在处理一本稀疏的书.现在,对于双向链表,我考虑过使用数组.除了填充后调整大小,附加和遍历将是最佳的,但删除将需要移动或跳过删除的条目.我还考虑了一个展开的链表,但是从我的研究和测试来看,当条目是几个字节而不是更大的Order结构时,它似乎工作得更好.

是否还有其他人可以指出的数据结构,尤其是优化缓存友好性？

另一方面,如果我使用LIFO堆栈作为内存池并提供带有来自此堆栈的对象的双向链接引用列表以重用最近删除的引号,则它将保留缓存时间局部性,但不一定保留空间局部性.我的直觉在这方面是否正确？

另外,我试图在linux中使用perf stat进行相当多的测试和分析缓存,但这并不容易.如果有人有关于如何进行缓存分析的更多提示,那么他们将非常受欢迎.

最后,请不要对过早优化发表评论.我这样做主要是为了锻炼和学习更多.这个项目不用于生产,我没有完成时间表.谢谢!

编辑更清晰,这与我当前的实现类似,最初来自https://web.archive.org/web/20110219163448/http://howtohft.wordpress.com/2011/02/15/how-to -build-a-fast-limit-order-book /:

限制订单簿(LOB)必须实现三个主要操作:添加,取消和执行.目标是在O(1)时间内实施这些操作,同时使交易模型能够有效地提出诸如"什么是最佳报价和报价？","价格A和B之间有多少交易量？"之类的问题.或者"订单X在书中的当前位置是什么？"

一本书中的绝大多数活动通常由增加和取消操作组成,因为做市商争夺头寸,执行距离遥远(实际上我会争辩说许多股票的大部分有用信息,特别是在早上,是添加和取消的模式,而不是执行,但这是另一个帖子的主题).添加操作在要以特定限价执行的订单列表的末尾下订单,取消操作从书中的任何地方删除订单,并且执行从书的内部删除订单(内部该书定义为最高购买价格的最早买单和最低卖价的最早卖单.这些操作中的每一个都是一个id号(下面的伪代码中的Order.idNumber),

Order
  int idNumber;
  bool buyOrSell;
  int shares;
  int limit;
  int entryTime;
  int eventTime;
  Order *nextOrder;
  Order *prevOrder;
  Limit *parentLimit;

Limit  // representing a single limit price
  int limitPrice;
  int size;
  int totalVolume;
  Limit *parent;
  Limit *leftChild;
  Limit *rightChild;
  Order *headOrder;
  Order *tailOrder;

Book
  Limit *buyTree;
  Limit *sellTree;
  Limit *lowestSell;
  Limit *highestBuy;

我们的想法是使用limitPrice排序的Limit对象的二叉树,每个对象本身都是Order对象的双向链接列表.本书的每一面,即购买限额和卖出限额,应该在不同的树中,以便书的内部分别对应于买入限价树的结束和开始,并且卖出限价树.每个订单也是一个键入idNumber的地图中的条目,每个限制也是一个键入limitPrice的地图中的条目.

使用此结构,您可以轻松实现这些关键操作并获得良好的性能:

• 添加 - O(log M)为限制的第一个订单,所有其他的O(1)
• 取消 - O(1)
• 执行 - O(1) …

假设我正在存储一个对象的链接列表，每个对象都是一个大小为 64 字节的结构，这也是我的缓存行的大小。随着时间的推移，我将在链接列表上进行延迟敏感的添加、删除和迭代。据我所知，性能主要取决于对象是否保存在缓存中，因此 RAM 访问的访问量约为 1 纳秒，而不是 > 50 纳秒。

通常建议通过空间局部性来实现这一点，最好将对象存储在连续的内存块中。这很有用，因为每当我访问内存地址时，处理器实际上都会提取缓存行的数据；我们希望这些附加数据成为其他有用的对象，因此我们将所有对象放在一个连续的块中。

我可能会误解，但如果对象大小 >= 缓存行大小，我们似乎不会从这种效果中受益。一次只能将一个对象放入缓存中。