logo资料库

《浅谈Cache Memory》.pdf

发布时间：2022-06-10 发布人：admin 分类：说明书 资料大小：4.13M 资料格式：pdf 举报 版权申诉
第1页 / 共112页
第2页 / 共112页
第3页 / 共112页
第4页 / 共112页
第5页 / 共112页
第6页 / 共112页
第7页 / 共112页
第8页 / 共112页
资料共112页，剩余部分请下载后查看
    版本说明 版本号 V0.01 修改说明 初始文档 备注 由 Wang, Qi，Yang, Xi，Zhu, Yuhao 书写
    Contributors List 贡献者名单以字母排序，希望更多的人加入。 Wang, Qi Yang, Xi Zhu, Yuhao V0.01 初始稿 V0.01 初始稿 V0.01 初始稿
    Contents 版本说明........................................................................................................................................... 1 Contributors List ................................................................................................................................ 2 序 ...................................................................................................................................................... 1 第 1 章 有关 Cache 的思考 ............................................................................................................. 3 1.1 Cache 不可不察也 .............................................................................................................. 4 1.2 伟大的变革 ........................................................................................................................ 6 1.3 让指令飞............................................................................................................................ 8 1.4 Crime and Punishment ...................................................................................................... 13 第 2 章 Cache 的基础知识 ............................................................................................................ 17 2.1 Cache 的工作原理 ............................................................................................................ 17 2.2 Cache 的组成结构 ............................................................................................................ 19 2.3 Why Index-Aware .............................................................................................................. 24 2.4 Cache Block 的替换算法 .................................................................................................. 28 2.5 指令 Cache ....................................................................................................................... 36 2.6 Cache Never Block ............................................................................................................. 40 第 3 章 Coherency and Consistency .............................................................................................. 46 3.1 Cache Coherency ............................................................................................................... 48 3.2 Memory Consistency 1 ...................................................................................................... 53 3.3 Memory Consistency 2 ...................................................................................................... 53 3.4 Memory Consistency 3 ...................................................................................................... 53 3.5 Memory Consistency 4 ...................................................................................................... 53 第 4 章 Cache 的层次结构 ............................................................................................................ 54 4.1 Cache 层次结构的引入 .................................................................................................... 54 4.2 存储器读写指令的发射与执行 ...................................................................................... 58 4.3 Cache Controller 的基本组成部件 ................................................................................... 64 4.4 To be inclusive or not to be ............................................................................................... 67 4.5 Beyond MOESIF ................................................................................................................. 73 4.6 Cache Write Policy ............................................................................................................. 82 4.7 Case Study on Sandy Bridge Cache Load ........................................................................... 87 第 5 章 Data Prefetch ..................................................................................................................... 91 5.1 数据预读.......................................................................................................................... 91 5.2 软件预读.......................................................................................................................... 93 5.3 硬件预读.......................................................................................................................... 95 5.4 Stream Buffer .................................................................................................................... 99 结束语 .......................................................................................................................................... 102
    序 近些年，我在阅读一些和处理器相关的论文与书籍，有很多些体会，留下了若干文字。 其中还是有一片领域，我一直不愿意书写，这片领域是处理器系统中的 Cache Memory。我 最后决定能够写下一段文字，不仅是为了这片领域，是我们这些人在受历史车轮的牵引，走 向一个未知领域，所产生的一些质朴的想法。 待到动笔，总被德薄而位尊，知小而谋大，力少而任重，鲜不及矣打断。多次反复后， 我几乎丢失了书写的兴趣。几个朋友间或劝说，不如将读过的经典文章列出来，有兴趣的可 以去翻阅，没有兴趣的即便是写成中文也于事无补。我没有采纳这些建议，很多事情可以很 多人去做，有些事情必须是有些人做。 这段文字起始于上半年，准备的时间更加久远些，收集翻译先驱的工作后，加入少许理 解后逐步成文。这些文字并是留给自己的一片回忆。倘若有人从这片回忆中收益，是我意料 之外的，我为这些意外为我的付出所欣慰。Cache Memory 很难用几十页字完成哪怕是一个 简单的 Survey，我愿意去尝试却没有足够的能力。知其不可为而为之使得这篇文章有许多未 知的结论，也缺乏必要的支撑数据。 在书写中，我不苛求近些年出现的话题，这些话题即便是提出者可能也只是抛砖引玉， 最后的结果未知。很多内容需要经过较长时间的检验。即便是这些验证过的内容，我依然没 有把握将其清晰地描述。这些不影响这段文字的完成。知识的积累是一个漫长的过程，是微 小尘埃累积而得的汗牛充栋。再小的尘埃也不能轻易拂去。 这些想法鼓励我能够继续写下去。 熙和禺皓的加入使本篇提前完成。每次书写时我总会邀些人参与，之前出版的书籍也是 如此，只是最后坚持下来只有自己。熙和禺皓的年纪并不大，却有着超越他们年纪的一颗坚 持的心。与他们商讨问题时，总拿他们与多年前的自己对照，感叹着时代的进步。他们比当 年的我强出很多。我希望看到这些。 个体是很难超越所处的时代，所以需要更多的人能够去做一些力所能及的，也许会对他 人有益的事情。聚沙成塔后的合力如上善之水。因为这个原因，我们希望能有更多的人能够 加入到 Contributors List，完善这篇与 Cache Memory 相关的文章。 Cache Memory 也被称为 Cache，是存储器子系统的组成部分，存放着程序经常使用的 指令和数据，这只是 Cache 的传统定义。从广义的角度上看，Cache 是缓解访问延时的 Buffer， 这些 Buffer 无处不在，只要存在着访问延时的系统，这些广义 Cache 就可以在掩盖访问延时 的同时，尽可能地提高数据带宽。 在处理器系统设计中，广义 Cache 的身影随处可见。在一个系统设计中，快和慢是一个 相对概念。与微架构(Microarchitecture)中的 L1/L2/L3 Cache 相比，DDR 是一个慢速设备，在 磁盘 I/O 系统中却是快速设备。在磁盘 I/O 系统中，仍在使用 DDR 内存作为磁介质的 Cache。 在一个微架构中，除了有 L1/L2/L3 Cache 之外，用于虚实地址转换的各级 TLB，在指令流水 线中的 ROB，Register File，BTB，Reservation Station 也是一种 Cache。我们准备书写的 Cache， 是狭义 Cache，是大家所熟悉的，围绕着处理器流水线和主存储器的 L1/L2/L3 Cache。这些 Cache 组成的层次结构，是微架构的设计核心。 广义 Cache 的设计可以在狭义的实现中获得帮助，却不是书中重点。在网络与存储这两 个热点话题中，算法层面之外的重中之重是广义 Cache 的管理问题。与云相关的各类概念中， 亟需解决的事情依然是算法与广义 Cache 管理。算法层面的实现需要考虑广义 Cache 的管理 策略，反之亦然。广义 Cache 与狭义 Cache 系统没有质的区别。这些 Cache 系统都是由数据 缓冲，连接缓冲的数据通路和控制逻辑这三个部分组成。 1
    从算法角度上看，广义 Cache 的设计与实现比狭义 Cache 相比也许略微复杂一些；用实 现的角度上看，狭义 Cache 的设计复杂度远远超过大多数广义 Cache。读者也许终其一生没 有机会去体验狭义 Cache 系统的设计，依然可以从这些设计思想中受益。这些思想，可以应 用于复杂的处理器系统中，可以解决一些细致入微的性能问题。系统开发者在不断思考探索 的过程中，在挑战极限的奋斗中，在身旁最后一把利器寸寸折断后，杀虎屠龙。 我未曾想过书写一篇学术意义上完美的文章。我更愿意用工程师的语言完成写作，这并 不阻碍本篇内容的有理可依。所有这些想法使我不堪重负，在整个处理器系统的设计中，几 乎没有什么部件比 Cache Memory 系统更为复杂。 本篇书写的 Cache 系统以 Alpha，Power，UltraSPARC 和 x86 处理器为主线，这四个处理 器目前属于 Tier 1。虽然 Alpha 处理器已退出历史舞台，但是并影响其 Tier 1 的地位。我不 会 刻 意 去 书 写 目 前 较 为 流 行 的 嵌 入 式 处 理 器 ， because yesterday’s high-performance technologies are today’s embedded technologies, but yesterday’s embedded-systems issues are today’s high-performance issues. 在 Tier 1 处理器中，本篇偏重于 Intel 的 x86 处理器实现，不管有多少资料引证 Power 和 UltraSPARC 处理器的诸多优点，x86 处理器依然是使用最为广阔，影响最为深远的处理器。 单纯从结构上看，Intel 的 x86，即便是最新的 Sandy Bridge EP 处理器，也远未到达学术界意 义上的完美。但是在 Cache Memory 层面，Intel 的领先是事实。 我最初曾试使用英文书写这些文字，我已经记不清楚最后一次抱着学习的目的去读中文 技术类书籍是曾几何时，中文科技类书籍不能如此发展下去。我远没有书写英文小说的能力， 依然有使用英文写科普文章的胆子，不用翻译的书写更加惬意。最终放弃了这个选择，因为 英文世界里有这样的文章，因为 Cache Memory 之外的内容，因为中文世界需要有人去贡献 一些勇气与智慧。 待到完成，总留有遗憾。我习得从这些遗憾中偷得间隙，留一片空间给自己。书不尽言， 言不尽意总是无可奈何。这些文字很难给予我任何成就感，细看先驱的诸多著作后，留下的 是何足道后的反思。我安于反思后的平静。 在阅读这些文字前，希望您能够仔细阅读 John 和 David 书写的“A Quantitative Approach”。 我常备这本书，看了许多遍，字里行间内外的一些细节仍然不慎明了，写作时重温此书有了 新的收获，借此重新审读了下列文字。 这篇文章最初的版本是 0.01，书名叫浅谈 Cache Memory。 2
    第1章 有关 Cache 的思考 在现代处理器系统中，Cache Memory 处于 Memory Hierarchy 的最顶端，其下是主存储 器和外部存储器。在一个现代处理器系统中，Cache 通常由多个层次组成，L1，L2 和 L3 Cache。 CPU 进行数据访问将通过各级 Cache 后到达主存储器。如果 CPU 所访问的数据在 Cache 中命 中，将不会访问主存储器，以缩短访问延时。 工艺的提高，使得主存储器的访问延时在持续缩短，访问带宽也在进一步的提高，但是 依然无法与 CPU 的主频，内部总线的访问延时和带宽匹配。主存储器是一个不争气的孩子， 不是如人们期望那般越来越快，是越变越胖。 主存储器膨胀的形体对 Cache Memory 提出了更高的要求，也进一步降低了主存储器所 提供的带宽与访问延时之间的比率。近些年，单端信号所提供的数据传送带宽受到了各种制 约，使得差分信号闪亮登场。差分信号的使用却进一步扩大了访问延时，对于这种现象，理 论派亦无能为力，只是简单规定了一个公式 1-1，这只是一个无奈的选择。 Latency Improvement2 ≤ Bandwidth Improvement 公式 1-1 从以上公式可以发现，延时在以平方增长，而带宽以线性增长。可以预计在不远的将来， CPU 访问主存储器的相对访问延时将进一步扩大，这是主存储器发展至今的现状，这使得在 处理器设计时需要使用效率更高的 Cache Memory 系统去掩盖这些 Latency，也使得 Cache Memory 需要使用更多的层次结构以提高处理器的执行效率。在现代处理器中，一个任务的 执行时间通常由两部分组成，CPU 运行时间和存储器访问延时，如公式 1-2 所示。 Excution Time = (CPU clock cycles + Memory stall cycles) × Clock cycle time 公式 1-2 在一个处理器系统中，影响 CPU 运行时间的因素很多，即便是几千页的书籍也未必能 够清晰地对其进行阐述。但是即便在一个可以容纳几千条指令的并行执行的 CPU 流水线中， 采用更多提高 ILP 的策略去进一步缩短 CPU 的运行时间，这些指令也必会因为存储器的访问 延时被迫等待。 这使得如何缩短存储器访问时间受到更多的关注，合理使用 Cache 是降低存储器访问时 间的有效途径。根据统计结果，在处理器执行一项任务时，在一段时间内通常会多次访问某 段数据。这些任务通常具有时间局部性(Temporal Locality)和空间局部性(Spatial Locality)的特 征，这使得 Cache 的引入顺理成章。这种局部性并不是程序天生具有的特性，是一个精心策 划的结果。我们不排除有些蹩脚的程序时常对这两个 Locality 发起挑战。对于这样的程序， 处理器微架构即便能够更加合理地安排 Cache 层次结构，使用更大的 Cache 也没有意义。 在一个任务的执行过程中，即便是同一条存储器指令在访问存储器时也可能会出现 Cache Hit 和 Cache Miss 两种情况。精确计算一个任务的每一次存储器访问时间是一件难以 完成的任务，于是更多的人关注存储器平均访问时间 AMAT(Average Memory Access Time)， 如公式 1-3 所示。 Average Memory Access Time = Hit time + Miss rate × Miss Penalt 公式 1-3 从公式 1-3 可以发现在一个处理器系统中，AMAT 的计算也许并不困难，只需要能够确 定 Hit time，Miss Rate 和 Miss Penalty 这三个参数即可。但是如何才能才能确定这三个参数。 3
    在一个程序的执行过程中，精确计算 Hit time，Miss Rate 和 Miss Penalty 这三个参数并 不容易，即便将计算这些参数所需的环境进行了一轮又一轮的约束。近些年，我在面试一些 Candidates 的时候，通常只问他们一个问题，让他们简单描述，在任何一个他所熟悉的处理 器中，一条存储器读写指令的执行全过程。我很清楚在短暂的面试时间内没有任何一个人能 够说清楚这个问题，即便这个 Candidate 已经获得了处理器体系结构方向的博士学位。 我所失望的是参加面试的学生几乎全部忘记了这些可能在课堂上学过的，可能会使他们 受益终身的基础内容。参加面试的学生们更多的是在其并不算长的硕士博士学习阶段，研究 如何提高编程能力，和一些与操作系统具体实现相关的技巧。这些并不是学生们的错，有太 多的评审官们本身就仅专注于小的技术和所谓的编程能力。 这些具体的编程能力和技巧，本不是一个学生应该在学校中练习的。在弥足珍贵的青春 岁月中，学会的这些小技巧越多，这个学生在整个技术生涯中的 Potential 可能越低。重剑 无锋，大巧不公。泱泱大国最为缺少的，不是能够书写程序，实现各类技巧的工程师。 1.1 Cache 不可不察也 在现代处理器中，Cache Hierarchy 一般由多级组成，处于 CPU 和主存储器之间，形成了 一个层次结构，这个层次结构日趋复杂。Intel 甚至放弃使用阿拉伯字母对 Cache 的各级层次 编号，而直接使用 LLC(Last-Level Cache)，MLC(Medium-Level Cache)这样的术语。 变化的称呼表明了一个事实，Cache 层次结构在整个处理器系统中愈发重要，也越发复 杂。Sandy Bridge 处理器大约使用了十亿个晶体管，在其正中不再是传统的 CPU，是 Ring Bus 包裹着的最后一级 Cache [1]。 图 1-1 Sandy Bridge 的拓扑结构[1] 处理器的制作过程异常复杂。在人类历史上，其设计难度只有古埃及的金字塔可以与其 媲美，即便是胡夫金字塔也只使用了 230 万个巨石，几十万个劳工而已。现代 CPU 的所耗 的资源何止这些数字。在处理器这座金字塔中，Cache 层次结构是最基本的框架。 几千年前，孙子曾经说过，“兵者，国之大事，死生之地，存亡之道，不可不察也”。对 于有志于站在金字塔顶峰的，即便目标只有半山腰的系统程序员，也是 Cache，不可不察也。 在 Intel 的 Values->Discipline 中有一句话“Pay attention to detail”。 4
    但是不要忘记 Devil is in the detail。准备深入理解 Cache 层次结构的读者需要时刻提醒 自己真正了解什么是细节之后，才会重视细节，才能够避免因为忽视细节而引发的灾难。重 视细节这个品质与你是否足够细心没有必然联系。 我们回到公式 1-3，简单探讨计算 Hit time，Miss Rate 和 Miss Penalty 这三个参数时所需 要考虑的因素和相关的环境。 似乎 Hit Time 参数最容易获得。我们很快就可以从 CPU 的数据手册中找到各级 Cache Hit 后的访问时间，并从 L1 Cache 的访问时间开始计算 Hit Time。可能我们上来就错了，现代处 理器大多使用了 Store-Load Forwarding 技术。存储器读操作首先要查询的并不是 L1 Cache， 是在更前面执行的，还没有来得及提交的 Store 结果，这些结果保存在一段数据缓冲中，这 个数据缓冲也是一种 Cache，不过比 L1 Cache 更加快速一些，也更接近 CPU。 除了数据 Cache，在现代处理器中，在指令 Cache 前还有一个 Line-Fill Buffer。Sandy Bridge 微架构中还含有一个 μops Cache[1]，计算指令 Cache 的 Hit 延时也没有想象中容易。精确计 算指令与数据 Cache Hit 的延时需要注意很多细节。简而言之，在处理器系统存储层次中， L1 Cache 并不是最快的，也不是第一级。如果进一步考虑到 Load Speculation 使用的各类算 法和命中率，Hit Time 参数并不容易计算清楚。 即便不考虑这些较为复杂的细节，我们仅从 L1 Cache 开始，Hit Time 参数也很难用简单 的公式描述。在单处理器环境中，L1 Miss 后会逐级查找下级 Cache，直到主存储器。但是在 多处理器内核环境中，情况复杂得多，一次存储器访问在自己的内核中没有命中，可能会在 其他内核的 Cache 中命中，在其他内核的 Cache 中命中后，又存在数据如何传递，延时如何 计算这些问题。说清楚这些问题并不容易。如果我们再进一步讨论多个 SMP 系统间 Cache 的一致性，这个 Hit Time 的计算就更加复杂。我只能选择放弃在这一节内，能够清楚地描述 如何计算 Hit Time 这个参数。 Miss Rate 参数更加难以琢磨。我们真的可以用 Vtune，Perf 这样的工具精确计算出哪怕 是单个任务的 Miss Rate 这样的参数吗，用这样的工具得到的统计数值有什么用途。同一片 树叶，有的人一叶障目，有的人一叶知秋。不要为一叶障目而苦恼。多看几片后，必会发现 春天的到来，也不要为一叶知秋而骄傲，少看几片，终会被最后一片树叶阻隔。 Miss Penalty 参数的计算仿佛容易一些。最糟糕的情况莫过于 CPU 从主存储器中获取数 据。我们可以将环境进一步简化，以便于读者计算这个参数。我们可以不讨论 SMP 系统间 的 Cache 一致性，甚至不讨论 SMP 之内的 Cache 一致性，仅讨论单处理器。即便如此 Miss Penalty 参数也不容易轻易计算，即便在这种情况之下，我们只讨论存储器读。 我们忽略在微架构在 Cache 前使用的各类 Queue，让存储器读操作首先对 L1 Cache 进行 尝试。如果没有命中这级 Cache，这次数据访问一定可以到达 L2 Cache 吗，如果不是 L2 Cache， 又是哪一级 Cache。这一切由 L1 和 L2 Cache 的关联结构决定。在一个处理器系统中，L1 与 L2 Cache 之间可能是 Inclusive，也可能是 Exclusive。如果是 Inclusive，存储器读操作将接着 尝试 L2 Cache，如果不是将会跨越这级 Cache。事实并非如此简单，L1 与 L2 Cache 并不会直 接相连，之间依然存在着许多 Buffer。 历经千辛万苦，数据访问最终到达最后一级 Cache，如果没有命中，就可以从主存储器 中获得数据。在这种情况之下，我们仿佛可以计算出最恶劣情况之下的 Miss Penalty。但是 这只是噩梦的开始。在现代处理器系统中，每一次存储器读写指令，都是由若干个步骤组成， 这些步骤间具有相互联系，如果进一步考虑 Memory Consistency 层面，所涉及到的同步操作 更多一些，这些操作并不能用几句话概括。 我们抛开这些复杂话题，讨论在 L1 和 L2 Cache Miss 之后从存储器获得数据这个模型。 存储器读从存储器获得数据仅是一次读访问的步骤。从主存储器获得的宝贵数据不会轻易丢 失，会存放在 Cache 中，需要将这些数据存放到哪一级 Cache 最为合理，LLC，MLCs 还是 FLC。 5
    分享到：
    赞 收藏

    相关推荐

    资料库

    存储

    共收录294份资料，累计8个分类，关注成员有19位，主要包括：EMC,SUN,IBM,Dell,HP,Microsoft,Veritas,其它

    热门标签

    EMC SUN IBM Dell HP Microsoft Veritas 其它

    最新资料