浅谈多核技术下的高速缓存区技术 学号:00748093 姓名:周天瑶 email: zhoutianvaovao 163 com 摘要:随着计算机技术的飞速发展,双核技术已经十分普及,四核产品也已问世。在追求双 核技术带给我们高性能的同时,它也带来了不少的技术难题。诸如多线程的编程与调试,多 核任务的合理分配,不同线程之间的互交与资源共享,等等。高速缓存区技术在提高计算机 性能上有着十分重要的作用,如何在多核的架构中利用好高速缓存,提高命中率,同时保证 缓存区信息共享的正确性都是值得深入思考的课题。我重点提出了多核带来的三个问题:高 速缓存不一致、高速缓存没有高效的分配、高速缓存流量增大。同时也结合现在的技术,提 出了自己的一些解决方法 关键词:多核,高速缓存,重要,问题,解决 多核是计算机芯片的未来。在单CPU时代,避免并发访问共享数据的方法相对简单 只有在中断发生的时候或在内核代码显式地请求重新调度,执行另一个任务时,数据才可能 被另并发访问。而今天芯片集成技术突飞猛进,如摩尔定律所说“ the number of cores will double every 18 months”。要想真正地发挥多核的优势,真正实现n个CPU的机器获得n倍 于一台单核机器的工作效率,高速缓存区的应用必不可少 高速缓存区的重要性 高速缓存的价值在于两个方面: 第一,访问磁盘的速度要远远低于访问内存的速度,因此,从内存访问数据比从磁盘访 问速度更快。DRAM芯片存取时间在100ns~20ons之间,随着CPU速度的不断提高,存储 器的速度难以满足CPU的要求,一般情况下,CPU访问存储器时要插入等待周期,对高速 CPU来说是一种极大的浪费。相比8086的5MHz时钟频率,现在的英特尔至强处理器已有 3GH主频,带有512KB二级高速缓存和400MHz系统总线。高速缓存对提升机器性能的 作用将更加明显 第二,数据一旦被访问,就很有可能在短期将被问到
浅谈多核技术下的高速缓存区技术 学号：00748093 姓名：周天瑶 email:zhoutianyaoyao@163.com 摘要：随着计算机技术的飞速发展，双核技术已经十分普及，四核产品也已问世。在追求双 核技术带给我们高性能的同时，它也带来了不少的技术难题。诸如多线程的编程与调试，多 核任务的合理分配，不同线程之间的互交与资源共享，等等。高速缓存区技术在提高计算机 性能上有着十分重要的作用，如何在多核的架构中利用好高速缓存，提高命中率，同时保证 缓存区信息共享的正确性都是值得深入思考的课题。我重点提出了多核带来的三个问题：高 速缓存不一致、高速缓存没有高效的分配、高速缓存流量增大。同时也结合现在的技术，提 出了自己的一些解决方法。 关键词：多核，高速缓存，重要，问题，解决 多核是计算机芯片的未来。在单 CPU 时代，避免并发访问共享数据的方法相对简单。 只有在中断发生的时候或在内核代码显式地请求重新调度，执行另一个任务时，数据才可能 被另并发访问。而今天芯片集成技术突飞猛进，如摩尔定律所说“the number of cores will double every 18 months”。要想真正地发挥多核的优势，真正实现 n 个 CPU 的机器获得 n 倍 于一台单核机器的工作效率，高速缓存区的应用必不可少。 一、 高速缓存区的重要性 高速缓存的价值在于两个方面： 第一，访问磁盘的速度要远远低于访问内存的速度，因此，从内存访问数据比从磁盘访 问速度更快。DRAM 芯片存取时间在 100ns~200ns 之间，随着 CPU 速度的不断提高，存储 器的速度难以满足 CPU 的要求，一般情况下，CPU 访问存储器时要插入等待周期，对高速 CPU 来说是一种极大的浪费。相比 8086 的 5MHz 时钟频率，现在的英特尔至强处理器已有 3GHz 主频，带有 512 KB 二级高速缓存和 400 MHz 系统总线。高速缓存对提升机器性能的 作用将更加明显。 第二，数据一旦被访问，就很有可能在短期将被问到
多核引发的问题 现在的双核架构一般为两个处理器,每个处理器内部有两个CPU内核,每个内核有其 各自专用的一级高速缓存,同时共享二级高速缓存。 CUZ 一级缓存 级缓存 级缓存 这样的结构一定的优势,比如当一个内核处于闲置状态,那么其它内核会占用所有共享 高速缓存,这样末级高速缓存得到了高效利用。同时减少数据存储冗余,同一个数据仅需储 存一次。借助内核间的高效数据共享,数据请求可在共享高速缓存层中实现,而不必全在系 统内存中完成,这样也就意味着提高了效率。 那么,多核会给高速缓存带来什么问题呢 1、高速缓存不一致 先来举个生活中简单的例子 假设学校图书馆里有5本书,有两个窗口可以进行图书预约。这两个窗口相当于两个 CPU,它们要同时访问图书馆这个“高速缓存”。我们不妨理想地考虑,先有一名同学来预 约,数量是3本,那么所剩的书就变为了2本。这时又来了一名同学想预约4本,由于馆里 只剩2本了,没法预约成功。但是如果两处预约同时进行,第一位同学3本小于5本预约成 功;第二位同学预约由于同时进行4本小于5本也预约成功,最终数据刷新为剩余1本 显然,两个预约窗口不应出现上面这样的情况,而应该是每一次预约全部完成后再进行 下一次预约,在一次预约的过程中是不能被另一次预约打断的。 可见,多核的高速缓存一致性是十分重要的。在多线程的程序中对于 cache的不正确使 用将严重影响系统性能
二、多核引发的问题 现在的双核架构一般为两个处理器，每个处理器内部有两个 CPU 内核，每个内核有其 各自专用的一级高速缓存，同时共享二级高速缓存。 这样的结构一定的优势，比如当一个内核处于闲置状态，那么其它内核会占用所有共享 高速缓存，这样末级高速缓存得到了高效利用。同时减少数据存储冗余，同一个数据仅需储 存一次。借助内核间的高效数据共享，数据请求可在共享高速缓存层中实现，而不必全在系 统内存中完成，这样也就意味着提高了效率。 那么，多核会给高速缓存带来什么问题呢？ 1、高速缓存不一致 先来举个生活中简单的例子： 假设学校图书馆里有 5 本书，有两个窗口可以进行图书预约。这两个窗口相当于两个 CPU，它们要同时访问图书馆这个“高速缓存”。我们不妨理想地考虑，先有一名同学来预 约，数量是 3 本，那么所剩的书就变为了 2 本。这时又来了一名同学想预约 4 本，由于馆里 只剩 2 本了，没法预约成功。但是如果两处预约同时进行，第一位同学 3 本小于 5 本预约成 功；第二位同学预约由于同时进行 4 本小于 5 本也预约成功，最终数据刷新为剩余 1 本。 显然，两个预约窗口不应出现上面这样的情况，而应该是每一次预约全部完成后再进行 下一次预约，在一次预约的过程中是不能被另一次预约打断的。 可见，多核的高速缓存一致性是十分重要的。在多线程的程序中对于 cache 的不正确使 用将严重影响系统性能
如下图所示,两个核对二级缓存都进行读操作,该调整缓存在两个L1 cache中将都处 于 shared状态。此时假设核1上的一个线程改写了其中一个数组元素a[0],将使这个core 上的这条 cache line将变修改状态,而另外一个核上的对应的 cache line将变成无效状态,此 时若核2上的一个线程马上读取a[],为了确保 cache一致性,这条 cache line的更新数据 必须被传输到所需数据的那个核上。若读写的次数频繁,将增大 cache miss的次数,严重影 响系统性能。 CPU1 CPUZ 级缓存 一级缓存 二级缓存 2、高速缓存没有在多核间进行高效的分配 CPU没有就近地利用高速缓存 CUZ 高速缓存 高速缓存 核的增加同时也增加了访问的灵活性。计算机的内存空间并不是一致地排在一处 的。如果每个CPU对内存的访问是随机的,有可能发生的情况是某个进程没有利用离 它最近的空间,而是占用了离别的核近的空间,这样就增加了无谓的总线同期和信息传
如下图所示，两个核对二级缓存都进行读操作，该调整缓存在两个 L1 cache 中将都处 于 shared 状态。此时假设核 1 上的一个线程改写了其中一个数组元素 a[0]，将使这个 core 上的这条 cache line 将变修改状态, 而另外一个核上的对应的 cache line 将变成无效状态，此 时若核 2 上的一个线程马上读取 a[1]，为了确保 cache 一致性，这条 cache line 的更新数据 必须被传输到所需数据的那个核上。若读写的次数频繁，将增大 cache miss 的次数，严重影 响系统性能。 2、高速缓存没有在多核间进行高效的分配 核的增加同时也增加了访问的灵活性。计算机的内存空间并不是一致地排在一处 的。如果每个 CPU 对内存的访问是随机的，有可能发生的情况是某个进程没有利用离 它最近的空间，而是占用了离别的核近的空间，这样就增加了无谓的总线同期和信息传
递等待周期,造成两个进程都不能最高效地工作。 3.增加了高速缓存流量 数据一旦被访问到,就很有可能在短期内再次被访问到。这在单核时很容易,过期的数 据被清除,新的数据被写入。而在多核时就会出现这样的问题,CPU进行一项任务时,它 把相关的数据读到了高速缓存区中,同时CPU2也在进行另一项任务,另外的数据也需要放 入缓存区。不幸的是CPU2以为自己没用到了信息(CPU1所需的数据)是过期的,而进行了 数据的更新,造成的高速缓存命中率的大大下降。导致这样问题出现的原因一是核之间没有 进行信息交流,二是高速缓存的分配没有合理的算法保证。 三、如何解决多核带给高速缓存的问题 1、如何保证高速缓存的一致性? 种最简单的思路是直接写算法。当修改一块高速缓存时,新的值保存高速缓存中,并 立即写回到主存储器相关存储块中。此方法优点是简单,不用担心更新内容的丢失,但是每 次对缓存的修改同时要写入主存储器,使总线操作频繁,影响系统性能 另一种思路是关闭时回写。即当高速缓存中的数据块被其他数据替换时,才将缓存中的 数据写回到主存储器。与直接写相比,关闭时回写减少了写存储器次数。 还有就是所谓的集中控制算法。在CPU打开某个文件时,先要声明是为读打开,还是 为写打开,还是兼而有之。为读打开的话都不会出现缓存区数据不一样的情形。为写打开的 话,在写的过程中必须禁止很有其他的访问。 2、如何进行缓存区的高效分配? 可以适当地分级,CPU访问需要的缓存区一级级扩大,而不是无序地选择
递等待周期，造成两个进程都不能最高效地工作。 3.增加了高速缓存流量 数据一旦被访问到，就很有可能在短期内再次被访问到。这在单核时很容易，过期的数 据被清除，新的数据被写入。而在多核时就会出现这样的问题，CPU1 进行一项任务时，它 把相关的数据读到了高速缓存区中，同时 CPU2 也在进行另一项任务，另外的数据也需要放 入缓存区。不幸的是 CPU2 以为自己没用到了信息(CPU1 所需的数据)是过期的，而进行了 数据的更新，造成的高速缓存命中率的大大下降。导致这样问题出现的原因一是核之间没有 进行信息交流，二是高速缓存的分配没有合理的算法保证。 三、如何解决多核带给高速缓存的问题 1、如何保证高速缓存的一致性？ 一种最简单的思路是直接写算法。当修改一块高速缓存时，新的值保存高速缓存中，并 立即写回到主存储器相关存储块中。此方法优点是简单，不用担心更新内容的丢失，但是每 次对缓存的修改同时要写入主存储器，使总线操作频繁，影响系统性能。 另一种思路是关闭时回写。即当高速缓存中的数据块被其他数据替换时，才将缓存中的 数据写回到主存储器。与直接写相比，关闭时回写减少了写存储器次数。 还有就是所谓的集中控制算法。在 CPU 打开某个文件时，先要声明是为读打开，还是 为写打开，还是兼而有之。为读打开的话都不会出现缓存区数据不一样的情形。为写打开的 话，在写的过程中必须禁止很有其他的访问。 2、如何进行缓存区的高效分配？ 可以适当地分级，CPU 访问需要的缓存区一级级扩大，而不是无序地选择
CAC的空间分配 CPU CACHE CACHE 3.如何提高命中率、减小高速缓存流量? 可采用高速缓存模块化的方法进行数据分块,达到更好的高速缓存命中率, 高速緩存模块化 将大型数据集细分为更小的模块,使所有操作先在每个模块上运行,然后再转到下一个 模块,那么整个数据模块就有可能在所有操作后仍留存在高速缓存中 左边模块所示为:比高速缓存容量更大的一个大型数据集上的数据循环。为了完成一次 循环,在循环开始时预取至高速缓存中的某些数据必须被淸除,以使数据的剩余部分得以运 行。为了执行循环过程中新的迭代操作,之前被清除的数据需要重新预取到高速缓存中。其
3.如何提高命中率、减小高速缓存流量？ 可采用高速缓存模块化的方法进行数据分块，达到更好的高速缓存命中率。 将大型数据集细分为更小的模块，使所有操作先在每个模块上运行，然后再转到下一个 模块，那么整个数据模块就有可能在所有操作后仍留存在高速缓存中。 左边模块所示为：比高速缓存容量更大的一个大型数据集上的数据循环。为了完成一次 循环，在循环开始时预取至高速缓存中的某些数据必须被清除，以使数据的剩余部分得以运 行。为了执行循环过程中新的迭代操作，之前被清除的数据需要重新预取到高速缓存中。其
结果是:产生了更多进出高速缓存的流量,并导致更多的高速缓存请求未命中。 右侧所示:流程被分为数据集中更小数据块上的四个数据循环,其中每个数据块的大小 都比高速缓存的容量更低。随之而来的结果是:在每个循环过程中,更小的数据块在高速缓 存中留存的时间更久,这就减少了进出高速缓存的数据流量,进而降低了高速缓存请求的未 命中率。此处所述实例可能是最简单的高速缓存模块化技术。还有许多更先进的高速缓存 模块化方案,依具体应用和算法的性质而定。 另外,还可以通过保留方法,让每个线程保留其自已的专用数据来降低到共享数据的访 问频率,仅在必要时更新共享数据,来提高效率 4如何避免错误共享? 当位于不同位置的多个处理器向一个共享缓存行写入时,错误共享将发生。例如,为 了保持专用一级高速缓存中高速缓存的一致性,错误共享可能会发生。如图所示,CPU 线程向一级高速缓存中添加一行,然后对其中的部分内容进行修改。CPU2中的线程也希 望修改同一个高速缓存行中的不同部分。高速缓存行已被CPUI修改。则CPUl中的一级 高速缓存行必须清除至二级高速缓存,然后加载至CPU2中的一级高速缓存,之后更新才能 完成 一级缓存 一级缓存 二级缓存 解决错误共享问题的一种最常用的方法是分配未共享的数据给不同的高速缓存行。另外 也可将线程移至同一个内核中,但这已体现不出多核的优势了。 参考书目: Robert love著,陈莉君等译。 Linux内核设计与实现(第2版)北京:机械工业出 版社200
结果是：产生了更多进出高速缓存的流量，并导致更多的高速缓存请求未命中。 右侧所示：流程被分为数据集中更小数据块上的四个数据循环，其中每个数据块的大小 都比高速缓存的容量更低。随之而来的结果是：在每个循环过程中，更小的数据块在高速缓 存中留存的时间更久，这就减少了进出高速缓存的数据流量，进而降低了高速缓存请求的未 命中率。此处所述实例可能是最简单的高速缓存模块化技术。 还有许多更先进的高速缓存 模块化方案，依具体应用和算法的性质而定。 另外，还可以通过保留方法，让每个线程保留其自已的专用数据来降低到共享数据的访 问频率，仅在必要时更新共享数据，来提高效率。 4.如何避免错误共享？ 当位于不同位置的多个处理器向一个共享缓存行写入时，错误共享将发生。 例如，为 了保持专用一级高速缓存中高速缓存的一致性，错误共享可能会发生。 如图所示，CPU1 线程向一级高速缓存中添加一行，然后对其中的部分内容进行修改。 CPU2 中的线程也希 望修改同一个高速缓存行中的不同部分。 高速缓存行已被 CPU1 修改。则 CPU1 中的一级 高速缓存行必须清除至二级高速缓存，然后加载至 CPU2 中的一级高速缓存，之后更新才能 完成。 解决错误共享问题的一种最常用的方法是分配未共享的数据给不同的高速缓存行。另外 也可将线程移至同一个内核中，但这已体现不出多核的优势了。 参考书目： [1] Robert Love 著，陈莉君等译。Linux 内核设计与实现（第 2 版）北京：机械工业出 版社 2006
2周荷琴,吴秀清编著微型计算机原理与接口技术第三版合肥:中国科学技术大 学出版社2004.12 丨3 Andrew S. Tanenbaum著陆丽娜等译分布式操作系统北京:电子工业出版社1999
[2]周荷琴，吴秀清编著 微型计算机原理与接口技术 第三版 合肥：中国科学技术大 学出版社 2004.12 [3]Andrew S.Tanenbaum 著 陆丽娜等译 分布式操作系统 北京：电子工业出版社 1999