关闭
当前位置:首页 - 国际国内新闻 - 正文

苏州天气,7个示例科普CPU CACHE,杜康

admin 2019-04-12 294°c

(感谢网友 @我的上铺叫路遥 翻译投稿)

CPU cache一向是了解核算机体系架构的重要知识点,也是并发编程规划中的技能难点,并且相关参阅资料好像过江之鲫,众多繁星,阅之如临深渊,味同嚼蜡,片言只语难以入门。正好网上有人引荐了微软大牛Igor Ostrovsky一篇博文《周游处理器缓存效应》,文章不只仅用7个最简略的源码示例就将CPU cache的原理娓娓道来,还附加图表量化剖析做数学上的佐证,个人感觉这种事例教育的切入办法必定是俺的菜,故而不由得轻率译之,以飨列位看官。

原文地址:Gallery 姑苏气候,7个示例科普CPU CACHE,狂药of Processor Cache Effects

大多数读者都知道cache是一种快速小型的内存,用以存储最近拜访内存方位。这种描绘合理而精确,可是更多地了解一些处理器缓存作业中的“烦人”细节关于了解程序运转毒爱纯男功用有很大协助。

在这篇博客中,我将运用代码示例来详解cache作业的方方面面,以及对实际国际中程序运转发生的影响。

下面的比方都是用C#写的,但言语的挑选同程序运转状况以及得出的定论简直没什么影响。

示例1:内存拜访和运转

你认姑苏气候,7个示例科普CPU CACHE,狂药为相较于循环1,循环2会运转多快?


int[] arr = new int[64 * 1024 * 1024];

// Loop 1

for (int i = 0; i < arr.Length; i++) arr[i] *= 3;

// Loop 2

for (int i = 0; i < arr.Length; i += 16) arr[i] *= 3;

第一个循环将数组的每个值乘3,第二个循环将每16个值乘3,第二个循环只做了第一个约6%的作业,但在现代机器上,两者简直运转相一起间:在我机器上分别是80毫秒和78毫秒。

两个循环花费相一起间的原因跟内存有关。循环履行时刻长短由数组的内存拜访次数决议的,而非整型数的乘法运算次数。经过下面临第二个示例的解说,你会发现硬件对这两个循环的主存拜访次数是相同的。

示例2:缓存行的影响

让咱们进一步探究这个比方。咱们将测验不同的循环步长,而不只仅是1和16。


for (int i = 0; i < arr.Length; i += K) arr[i] *= 3;

下图为该循环在不同步长(K)下的运转时刻:

7个示例科普CPU CACHE


留意当步长在1到16范围内,循环运转时刻简直不变。但从16开端,每次步长加倍,运转时刻折半。

背面的原因是今日的CPU不再是按字节拜访内存,而是以64字节为单位的块(chunk)拿取,称为一个缓存行(cache line)。当你读一个特定的内存地址,整个缓存行将从主存换入缓存,并且拜访同一个缓存行内的其它值的开支是很小的。

由于16个整型数占用64字节(一个缓存行),for循环步长在1到16之间必定触摸到相同数目的缓存行:即数组中一切的缓存行。当步长为32,咱们只需大约每两个缓存行触摸一次,当步长为64,只需每四个触摸一次。

了解缓存行对某些类型的程序优化而言或许很重要。比方,数据字节对齐或许决议一次操作触摸1个仍是2个缓存行。那上面的比方来说,很显然操作不对齐的数据将丢失一半功用。

示例3:L1和L2缓存巨细

今日的核算机具有两级或三级缓存,一般叫做L1、L2以及或许的L3(译者注:假如你不理解什么叫二级缓存,能够参阅这篇精悍的博文lol)。假如你想知道不同缓存的巨细,你能够运用体系内部东西CoreInfo,或许Windows API调用GetLogicalProcessorInfo。两者都将通知你缓存行以及缓存自身的巨细。

在我的机器上,CoreInfo实际我有一个32KB的L1数据缓存,一个32KB的L1指令缓存,还有一个4MB巨细L2数据缓存。L1缓存是处理器独享的,L2缓存是成对处理器同享的。

Logical Processor to Cache Map:

*— Data Cache 0, Level 1, 32 KB, Assoc 8, LineSize 64

*— Instruction Cache 0, Level 1, 32 KB, Assoc 8, LineSize 64

-*– Data Cache 1, Level 1, 于莎莎32 KB, Assoc 8, LineSize 64

-*– Instruction Cache 1, Level 1, 32 KB, Assoc 8, LineSize 64

**– Unified Cache 0, Level 2, 4 MB, Assoc 16, LineSize 64

–*- Data Cache姑苏气候,7个示例科普CPU CACHE,狂药 2, Level 1, 32 KB, Assoc 8, LineSize 64

–*- Instruction Cache 2, Level 1, 32 KB, Assoc 8, LineSize 64

—* Data Cache 3, Level 1, 32 KB, Assoc 8, LineSize 64

—* Instruction Cache 3, Level 1, 32 KB, Assoc 8, LineSize 64

–** Unified Cache 1, Level 2, 4 MB, Assoc 16, LineSize 64

(译者注:作者渠道是四核机,所以L1编号为0~3,数据/指令各一个,L2只需数据缓存,两个处理器同享一个,编号0~1。相关性字段在后边比方阐明。)

让咱们经过一个试验来验证这些数字。遍历一个整型数组,每16个值自增1——一种节省地办法改动每个缓存行。罗宾当遍历到最终一个值,就重头开端。咱们将运用不同的数组巨细,能够看到当数组溢出一级缓存巨细,程序运转的功用将急剧滑落。


int steps = 64 * 1024 *孙志刚作业 1024;

// Arbitrary number of steps

int lengthMod = arr.Length - 1;

for (int i = 0; i < steps; i++)

{

arr[(i * 16) & lengthMod]++; // (x & lengthMod) is equal to (x % arr.Length)

}

下图是运转时刻图表:

7个示例科普CPU CACHE


你能够看到在32KB和4MB之后功用显着滑落——正好是我机器上L1和L2缓存巨细。

示例4:指令等级并发

现在让咱们看一看不同的东西。下面两个循环中你认为哪个较快?


int steps = 256 * 1024 * 1024;

int[] a = new int[2];

// Loop 1

for (int i=0; i

// Loop 2

for (int i=0; i

成果是第二个循环约比第一个快一倍,至少在我测验的机器上。为什么呢?这跟两个循环体内的操作指令依靠性有关。

第一个循环体内,操作做是彼此依靠的(译者注:下一次依靠于前一次):


但第二个比方中,依靠性就不同了:


现代处理器中对不同部分指令具有一点并发性(译者注:跟流水线有关,比方Pentium处理器就有U/V两条流水线,后边阐明)。这使得CPU在同一时刻拜访L1两处内存方位,或许履行两次简略算术操作。在第一个循环中,处理器无法开掘这种指令等级的并发性,但第二个循环中就能够。

[原文更新]:许多人在reddit上问询有关编译器优化的问题,像{ a[0]++; a[0]++; }能否优化为{ a[0]+=2; }。实际上,C#编译器和CLR JIT没有做优化——在数组拜访方面。我用release形式编译了一切测验(运用优化选项),但我查询了JIT汇编言语证明优化并未影响成果。

示例5:缓存相关性

缓存规划的一个猪刚强要害决议是保证每个主存块(chunk)能够存储在任何一个缓存槽里,或许只是其间一些(译者注:此处一个槽位便是一个缓存行)。

有三种办法将缓存槽映射到主存块中:

  1. 直接映射(Direct mapped cache)
  2. 每个内存块只能映射到一个特定的缓存槽。一个简略的计划是经过块索引chu网游之天谴修罗nk_index映射到对应的槽位(chunk_index % cache_slots)。被映射到同一内存槽上的两个内存块是不能一起换入缓存的。(译者注:chunk_index能够经过物理地址/缓存行字节核算得到)
  3. N路组相关(N-way set associative cache)
  4. 每个内存块能够被映射到N路特定缓存槽中的恣意一路。比方一个16路缓存,每个内存块能够被映射到16路不同的缓存槽。一般地,具有必定相同低bit位地址的内存块将同享16路缓存槽。(译者注:相同低位地址标明相距必定单元巨细的接连内存)
  5. 彻底相关(Fully associative cache)
  6. 每个内存块能够被映射到恣意一个缓存槽。操作作用上相当于一个散列表。

直接映射缓存会引发抵触——当多个值竞赛同一个缓存槽,它们将彼此驱赶对方,导致射中率暴降。另一方面,彻底相关缓存过于杂乱,并且硬件实姑苏气候,7个示例科普CPU CACHE,狂药现上贵重。N路组相关是处理器缓存的典型计划,它在电路完成简化和高射中率之间取得了杰出的折中。


(此图由译者给出,直接映射和彻底相关能够看做N路组相关的两个极点,从图中可知当N=1时,即直接映射;当N取最大值时,即彻底相关。读者能够自行幻想直接映射图例,详细表述见参阅资料。)

举个比方,4MB巨细的L2缓存在我机器上是16路相关。一切64字节内存块将分割为不同组,映射到同一组的内存块将竞赛L2缓存里的16路槽位。

L2缓存有65,536个缓存行(译者注:4MB/64),每个组需求16路缓存行,咱们将取得4096个集。这样一来,块归于哪个组取决于块索引的低12位bit(2^12=4096)。因而缓存行对应的物理地址凡是以262,144字节(4096*64)的倍数区其他,将竞赛同一个缓存槽。我何晴现任老公机器上最多保持16个这样的缓存槽。(译者注:请结合上图中的2路相关延伸了解,一个块索引对应64字节,chunk0对应组0中的恣意一路槽位,chunk1对应组1中的恣意一路槽位,以此类推chunk4095对应组4095中的恣意一路槽位,chunk0和chunk4096地址的低12bit是相同的,所以chunk4096、chunk8192将同chunk0竞赛组0中的槽位,它们之间的地址相差262,144字节的倍数,而最多能够进行16次竞赛,不然就要驱赶一个chunk)。

为了使得缓存相关作用愈加明晰,我需求重复地拜访同一组中的16个以上的元素,经过如下办法证明:


public static long UpdateEveryKthByte(byte[] arr, int K)

{

Stopwatch sw = Stopwatch.StartNew();

const int rep = 1024*1024; // Number of iterations – arbitrary

int p = 0;

for (int i = 0; i < rep; i++)

{

arr[p]++;

p += K;

if (p >= arr.Length) p = 0;

}

sw.Stop();

ret黑社会3urn sw.ElapsedMilliseconds;

}

该办法每次在数组中迭代K个值,当抵达结尾时从厂头开端。循环在运转满足长(2^20次)之后中止。

我运用不同的数组巨细(每次添加1MB)和不同的步长传入UpdateEveryKthByte()。以下是制造的图表,蓝色代表运转较长时刻,白色代表较短时刻:


蓝色区域(较长时刻)标明当咱们重复数组迭代时,更新的值无法一起放在缓存中。浅蓝色区域对应80毫秒,白色区域对应10毫秒。

让咱们来解说一下图表中蓝色部分:

1.为何有垂直线?垂直线标明步长值过多触摸到同一组中内存方位(大于16次)。在这些次数里,我的机器无法一起将触摸过的值放到16路相关缓存中。

一些糟糕的步长值为2的幂:256和512。举个比方,考姑苏气候,7个示例科普CPU CACHE,狂药虑512步长遍历8MB数组,存在32个元素以相距262,144字节空间散布,一切32个元素都会在循环遍历中更新到,由于512能够整除262,144(译者注:此处一个步长代表一个字节)。

由于32大于16,这32个元素将一向竞赛缓存里的16路槽位。

(译者注:为何512步长的垂直线比256步长色彩更深?在相同满足多的步数下,512比256拜访到存在竞赛的块索引次数多一倍。比方跨过262,144字节鸿沟512需求512步,而256需求1024步。那么当步数为2^20时,512拜访了2048次存在竞赛的块而256只需1024次。最差情况下步长为262,144的倍数,由于每次循环都会引发一个缓存行驱赶。)

有些不是2的幂的步长运转时刻长只是是命运欠好,终究拜访到的是同一组中不成比例的许多元素,这些步长值相同显现为蓝线。

2.为何垂直线在4MB数组长度的当地中止?维生素b族由于关于小于等于4MB的数组,16路相关缓存相当于彻底相关缓存。

一个16路相关缓存最多能够保护1美好来敲门6个以262,144字节分隔的缓存行,4MB内组17或更多的缓存行都没有对齐在262,144字节鸿沟上,由于16*262,144=4,194,304。

3.为何左上角呈现蓝色三角?在三角区域内,咱们无法在缓存中一起寄存一切必要的数据,不是出于相关性,而只是是由于L2缓存巨细所限。

举个比方,考虑步长128遍历16MB数组,数组中每128字节更新一次,这意味着咱们一次触摸两个64字节内存块。为了存储16MB数组中每两个缓存行,咱们需求8MB巨细缓存。但我的机器中只需4MB缓存(译者注:这意味着必定存在抵触然后延时)。

即便我机器中4MB缓存是全相关,仍无法一起寄存8MB数据。

4.为何三角最左面部分是褪色的?留意左面0~64字节部分——正好一个缓存行!就像上面示例1和2所说,额定拜访相同缓存行的数据简直没有开支。比方说,步长为16字节,它需求4步抵达下一个缓存行,也便是说4次内存拜访只需1次开支。

在相同循环次数下的一切测验用例中,采纳省力步长的运转时刻来得短。

将图表延伸后的模型:


缓存相关性了解起来风趣并且确能被证明,但关于本文讨论的其它问题比起来,它必定不会是你编程时所首要需求考虑的问题。

示例6:缓存行的伪同享(false-sharing)

在多核机器上,缓存遇到了另一个问题——一致性。不同的处理器具有彻底或部分别离的缓存。在我的机器上,L1缓存是别离的(这很遍及),无印良品官网而我有两对处理器,每一对同享一个L2缓存。这随康敏着详细情况而不同,假如一个现代多核机器上姑苏气候,7个示例科普CPU CACHE,狂药具有多级缓存,那么快速小型的缓存将被处理器独占。

当一个处理器改动了归于它自己缓存中的一个值,其它处理器就再也无法运用它自己本来的值,由于其对应的内存方位将被改写(invalidate)到一切缓存。并且由于缓存操作是以缓存行而不是字节为粒度,一切缓存中整个缓存行将被改写!

为证明这个问题,考虑如下比方:


private static int[] s_counter = new int[1024];

private void UpdateCounter(int position)

{

for (int j = 0; j < 100000000; j++)

{

s_counter[position] = s_counter[position] + 3;

}

}

在我的四核机上,假如我经过四个线程传入参数0,1,2,3并调用UpdateCounter,一切线程将花费4.3秒。

另一方面,假如我传入16,32,48,64,整个操作进花费0.28秒!

为何会这样?第一个未来之制药师比方中的四个值很或许在同一个缓存行里,每次一个处理器添加计数,这四个计数地点的缓存行将被改写,而其它处理器鄙人一次访女同电影问它们各自的计数(译者注:留意数组是private特点,每个线程独占)将失掉射中(miss)一个缓存。这种多线程行为有效地制止了缓存功用,削弱了程序功用。

示例7:硬件杂乱性

即便你懂得了缓存的作业根底,有时候硬件行为仍会使你惊奇。不必处理器在作业时有不同的优化、探试和奇妙的细节。

有些处理器上,L1缓存能够并发处理两路拜访,假如拜访是来自不同的存储体,而对同一存储体的拜访只能串行处理。并且处理器聪明的优化战略也会使你感到惊奇,比方在伪同享的比方中,曾经在一些没有微调的机器上运转体现并不杰出,但我家里的机器能够对最简略的比方进行优化来削减缓存改写。

下面是一个“硬件怪事”的古怪比方:


private static int A, B, C, D, E, F, G;

private static void Weirdness()

{

for (int i = 0; i < 200000000; i++)

{

// do something...

}

}

当我在循环体内进行三种不同操作,我得到如下运转时刻:

操作 时刻

A++; B++; C++; D++; 719 ms

A++; C++; E++; G++; 448 ms

A++; C++; 518 ms

添加A,B,C,D字段比添加A,C,E,G字段花费更长时刻,更古怪的是,添加A,C两个字段比添加A,C,E,G履行更久!

我无法必定这些数字背面的原因,但我置疑这跟存储体有关,假如有人能够解说这些数字,我将洗耳恭听。

这个比方的经验是,你很难彻底猜测硬件的行为。你能够猜测许多作业,但终究,衡量及验证你的假定十分重要。

关于第7个比方的一个回帖

Goz:我问询Intel的工程师最终的比方,得到以下答复:

“很显然这涉及到履行单元里指令是怎样停止的,机器处理存储-射中-加载的速度,以及怎么快速且高雅地处理试探性履行的循环展开(比方是否由于内部抵触而屡次循环)。但这意味着你需求十分详尽的流水线跟踪器和模拟器才干弄理解。在纸上猜测流水线里的乱序指令是无比困难的作业,就算是规划芯片的人也相同。关于外行人来说,没门,抱愧!”

P.S.个人感悟——局部性原理和流水线并发

程序的运转存在时刻和空间上的局部性,前者是指只需内存中的值被换入缓存,往后一段时刻内会被屡次引证,后者是指该内存邻近的值也被换入缓存。假如在编程中特别留意运用局部性原理,就会取得功用上的报答。

比方C言语中应该尽量削减静态变量的引证,这是由于静态变量存储在大局数据段,在一个被重复调用g6710的函数体指剑道内,引证该变量需求对缓存屡次换入换出,而假如是分配在仓库上的局部变量,函数每次调用CPU只需从缓存中就能找到它了,由于仓库的重复利用率高。

再比方循环体内的代码要尽量精简,由于代码是放在指令缓存里的,而指令缓存都是一级缓存,只需几K字节巨细,假如对某段代码需求屡次读取,而这段代码又跨过一个L1缓存巨细,那么缓存优势将化为乌有。

关于CPU的流水线(pipeline)并发性简略说说,Intel Pentium处理器有两条流水线U和V,每条流水线可各自独登时读写缓存,所以能够在一个时钟周期内一起履行两条指令。但这两条流水线不是对等的,叶继欢U流水线能够处理一切指令集,V流水线只能处理简略指令。

CPU指令一般被分为四类,第一类是常用的简略指令,像mov, nop, push, pop梦见抓鱼, add, sub, and, or, xor, inc, dec, cmp, lea,能够在恣意一条流水线履行,只需彼此之间不存在依靠性,彻底能够做到指令并发。

第二类指令需求同其他流水线合作,像一些进位和移位操作,这类指令假如在U流水线中,那么其他指令能够在V流水线并发运转,假如在V流水线中,那么U流水线是暂停的。

第三类指令是一些跳转指令,如cmp,call以及条件分支,它们同第二类相反,当作业在V流水线时才干通U流水姑苏气候,7个示例科普CPU CACHE,狂药线协作,不然只能独占CPU。

第四类指令是其它杂乱的指令,一般不常用,由于它们都只能独占CPU。

假如是汇编等级编程,要到达指令等级并发,必需要重视指令之间的配对。尽量运用第一类指令,防止第四类,还要在次序上削减上下文依靠。

参阅资料

wiki上的CPU cache解析(中文版)(英文版)。

上海交通大学师生制造的一个关于cache映射功用、射中率核算的教育演示程序,模拟了不同相关形式下cache的映射和射中几率,形象直观。

网易数据库大牛@何_登成克己PPT《CPU Cache and Memory Ordering》,信息量超大!

南京大学核算机教育揭露PPT,温馨提示,地址域名里边改动字段”lecture”后边的数字编号可切换课程;-)

admin 14文章 0评论 主页

相关文章

  用户登录