（电子科学与技术专业论文）“银河飞腾dx”dsp高效二级cache的设计与实现.pdf

the design and implementation of high performance secondary cache on yhft-dx dsp candidate：jin qiang advisor：prof. guo yang a thesis submitted in partial fulfillment of the requirements for the degree of master of engineering in electronic science and technology graduate school of national university of defense technology changsha，hunan，p.r.china november，2011 国防科学技术大学研究生院工学硕士学位论文 第 i 页 目目 录录 摘 要 . i abstract . iii 第一章 绪论 . 1 1.1 课题研究背景 . 1 1.1.1 dsp 概述 . 1 1.1.2 dsp 片内 cache 结构的重要性 . 2 1.2 相关研究 . 3 1.2.1 cache 缺失流水线 . 3 1.2.2 cache 预取 . 4 1.3 本文所做的工作 . 5 1.4 文章结构 . 6 第二章 二级 cache 缺失流水线结构的设计与实现. 7 2.1 “银河飞腾-dx”dsp 片内二级存储体系 . 7 2.1.1 “银河飞腾-dx”dsp 总体结构 . 7 2.1.2 “银河飞腾-dx”dsp 二级存储结构 . 8 2.2 二级 cache 缺失流水线 . 11 2.2.1 读写缺失流水线问题的提出 . 12 2.2.2 二级 cache 缺失流水线结构 . 14 2.2.3 原子性控制 . 15 2.2.4 详细设计 . 17 2.3 性能评估 . 22 2.3.1 理论分析 . 22 2.3.2 模拟测试结果 . 23 2.4 小结 . 25 第三章 步长自适应二级 cache 预取机制. 27 3.1 二级 cache 失效行为分析 . 27 3.1.1 cache 失效率对比 . 27 3.1.2 cache 失效数据地址序列类型 . 28 3.2 预取结构 . 30 3.2.1 预取结构总体框图 . 30 3.2.2 预取表 . 30 国防科学技术大学研究生院工学硕士学位论文 第 ii 页 3.2.3 控制逻辑 . 31 3.2.4 结构参数 . 33 3.3 工作机理 . 34 3.3.1 工作流程 . 34 3.3.2 预取实例 . 38 3.4 性能评估与结构优化 . 40 3.4.1 性能评估 . 40 3.4.2 结构优化 . 41 3.5 小结 . 45 第四章 “银河飞腾-dx”dsp 二级 cache 预取结构 . 47 4.1 流水化二级 cache 预取结构 . 47 4.1.1 流水化步长自适应二级 cache 预取结构 . 47 4.1.2 改进的预取表结构 . 48 4.1.3 可配置结构设计 . 49 4.2 访存仲裁 . 50 4.2.1 l2 失效访存与预取的冲突仲裁 . 51 4.2.2 l2 失效访存命中预取的处理 . 52 4.3 小结 . 53 第五章 结束语 . 55 致 谢 . 57 参考文献 . 59 作者在学期间取得的学术成果 . 63 国防科学技术大学研究生院工学硕士学位论文 第 iii 页 表 目 录 表 3.1 程序访存模式 . 28 表 3.2 二级 cache 失效数据地址序列类型 . 29 表 3.3 固定步长类型预取实例 . 38 表 3.4 步长线性变化类型预取实例 . 39 表 3.5 测试平台的 cache 配置参数 . 40 表 3.6 信心系统机制16 . 42 国防科学技术大学研究生院工学硕士学位论文 第 iv 页 国防科学技术大学研究生院工学硕士学位论文 第 v 页 图 目 录 图 1.1 adsp21161n 功能结构图6 . 2 图 2.1 “银河飞腾-dx”dsp 体系结构总体框图 . 7 图 2.2 “银河飞腾-dx”dsp 片内存储体系结构 . 8 图 2.3 “银河飞腾-dx”dsp l2 存储器总体结构框图. 9 图 2.4 二级存储器模式配置示意图 . 10 图 2.5 l1d 缺失请求命中非流水二级 cache 的时序图 . 13 图 2.6 l2 流水处理 l1d 的连续缺失请求. 13 图 2.7 二级 cache 缺失流水线结构框图 . 14 图 2.8 tag比较段总体工作流程图 . 18 图 2.9 cpu 访问请求处理流程图. 19 图 2.10 l1d 替换回写请求处理流程图 . 20 图 2.11 控制寄存器触发的 cache 行操作处理流程图 . 21 图 2.12 添加 l2 缺失流水线之后的程序运行加速比 . 24 图 2.13 添加缺失流水线之后处理 l1p 缺失请求的性能加速比. 25 图 3.1 不同 cache 的失效率对比 . 28 图 3.2 预取结构总体框图 . 30 图 3.3 预取表结构图 . 30 图 3.4 预取总体工作流程图 . 34 图 3.5 查询预取表工作流程图 . 35 图 3.6 更新预取表工作流程 . 36 图 3.7 数据预取工作流程图 . 37 图 3.8 采用预取前后的失效率对比 . 41 图 3.9 预取表大小对性能提升的影响 . 41 图 3.10 信心系统机制对系统性能的影响 . 43 图 3.11 不同预取表大小在不同二级存储器配置下降低失效率的幅度对比 . 44 图 3.12 不同信心系统在不同二级存储器配置下降低失效率幅度的对比 . 45 图 4.1 “银河飞腾-dx”dsp 二级 cache 预取结构框图 . 48 图 4.2 改进后的预取表结构图 . 49 图 4.3 测试程序访问 l2 cache 的失效率 . 50 图 4.4 预取使能逻辑框图 . 50 图 4.5 访存仲裁逻辑框图 . 52 国防科学技术大学研究生院工学硕士学位论文 第 vi 页 国防科学技术大学研究生院工学硕士学位论文 第 i 页 摘 要 近年来，数字信号处理器（dsp）得到越来越广泛的应用，但 dsp 性能的提 升同样面临“存储墙”问题带来的设计瓶颈，解决这个问题的重要途径就是设置 多级存储结构。在当今 dsp 设计中，“cache+ram”的二级存储体系结构已成为 片内存储结构的主要选择，它不仅担任片内存储器的职责，同时还负责 dsp 核与 外存之间的通信任务。因此，如何设计一种高效的“cache+ram”片内二级存储 结构，特别是一种高效的二级 cache 工作机制，是 dsp 设计中的一个关键问题。 “银河飞腾-dx”dsp 是我院自主研发的高性能定点 dsp，采用超长指令字 结构（vliw），每个取值包由 8 条指令组成，最多可在一拍内完成 8 条指令的分 配与执行。采用片内二级存储体系结构，二级存储器为总容量为 1mb 的共享 “cache+ram”的可配置结构，用户可根据实际应用程序的需要灵活调整二级存 储器中 cache 和 ram 的比例。本文围绕高效二级 cache 的设计实现进行研究，主 要包括以下几方面工作。 首先，分析了一般的 cache 的设计方法，全面考察了主流 dsp 芯片中 cache 的性能要求和实现技术，设计实现了“银河飞腾-dx”dsp 中 l2 cache 的缺失流 水线结构。l2 cache 的缺失流水线能够流水地处理 l1 的缺失请求，能够有效隐藏 l1 缺失请求在 l2 cache 中的命中时间，在“银河飞腾-dx”dsp 平台上的 rtl 级 模拟测试表明，l2 cache 缺失流水线对处理访问 l2 存储器的缺失请求最多可达到 1.31 的加速比。 其次，分析了实际应用程序对于 cache 的访存行为，总结出两种可以进行预测 的访存失效地址序列类型，并针对这两种访存失效地址序列类型设计了一种步长 自适应二级 cache 预取机制。该机制针对二级 cache 的工作特点，使用访存失效地 址的 cache 块地址作为查询预取表的索引，简化了在 cache 基础上设计添加预取结 构的硬件实现。同时，预取机制引入信心系统机制，能够有效地降低 cache 的失效 率。对 spec2006 测试程序的运行结果表明，步长自适应二级 cache 预取机制对程 序访存的失效率最多可降低 4.5%，对程序的加速比最大可达 1.3。 最后， 结合 l2 cache 缺失流水线结构和步长自适应二级 cache 预取机制， 在 “银 河飞腾-dx“dsp 平台上设计了带有预取结构的 l2 cache 缺失流水线。该结构综 合了缺失流水线和步长自适应二级 cache 预取机制的优势，能够进一步提升“银河 飞腾-dx”dsp 的系统访存性能。 主题词：dsp；cache；缺失流水线；步长自适应；预取；信心系统机制 国防科学技术大学研究生院工学硕士学位论文 第 ii 页 国防科学技术大学研究生院工学硕士学位论文 第 iii 页 abstract nowadays, the digital signal processor (dsp) has been widely used, but dsps performance is also limited by the “memory wall” problem. to resolve this problem, multiple level memory structure is commonly used. today, the “cache+ram” two level memory structure is mostly used in dsp design. in dsp, the secondary memory is not only a memory, but also is in charge of the data transformation from dsp core to external memory. for this reason, how to design a high performance “cache+ram” two level memory structure, especially a high performance secondary cache scheme, is an important problem in dsp design. yhft-dx dsp is a high performance dsp which is developed independently by my university. it adopts very long instruction word (vliw) architecture, whose instruction fetching packet contains 8 instructions, and it can execute 8 instructions in parallel in one cycle at most. meanwhile, yhft-dx dsp uses two level memory structure on chip, and the secondary memory is a 1mb “cache+ram” memory, which is shared and can be configured. when customer is designing a program, he can adjust the proportion of cache and ram according to the program feature. this paper presents the design and implementation of high performance cache in yhft-dx dsp, and it contains following works. first of all, this paper reviews the cache techniques and the requisite performance in the popular dsp, and then designs and implements the miss pipeline of l2 cache on yhft-dx dsp, which can deal requests from l1 on pipeline way, and the miss pipeline can overlap the hit cost of l2 cache effectively. the speedup can be 1.31 at most, when it deals the miss requests which access the l2 memory. secondly, it analyses the feature of memory-access in programs, and summarizes two kinds of missing access address sequence which can be predicted. and then, it designs a stride adaptive prefetch scheme on secondary cache according to the two kinds of missing access address sequence. in dsp, the secondary cache can not see the address of memory-access instructions, so the prefetch scheme uses the line address to lookup the prefetch table, which can make the implementation of the prefetch scheme on l2 cache simply. meanwhile, the prefetch scheme uses a confidence system to control the producing of prefetch signal, which reduces the missing rate of cache effectively. through testing by spec2006, the scheme can reduce miss rate on l2 cache by 4.5%, and the speedup can be 1.3 at most. at last, it implements a stride adaptive prefetch scheme combined with l2 cache miss pipeline in yhft-dx dsp, which contains both the miss pipeline and the prefetch scheme introduced before. the structure has the advantage both of the miss pipeline and the prefetch scheme, so it can greatly improve the memory-access performance of 国防科学技术大学研究生院工学硕士学位论文 第 iv 页 yhft-dx dsp. key words：dsp, cache, miss pipeline, stride adaptive, prefetch, confidence system 国防科学技术大学研究生院工学硕士学位论文 第 1 页 第一章 绪论 1.1 课题研究背景课题研究背景 1.1.1 dsp 概述 数字信号处理器（digital single processor，简称 dsp）是具有特殊结构的，专 门用于数字信号处理的专用微处理器1。目前，dsp 凭借其大数据量处理能力、完 成指定运算的时间确定性、对特殊应用的专用结构等特点，在图像处理、视频编 解码、无线电技术、语音处理、雷达系统等领域得到广泛的应用。此外，dsp 也 越来越多的被应用到影音娱乐设备、汽车电子、智能家电、工业控制和医疗设备 等领域。发展 dsp 设计技术不仅对发展国防科技具有重大意义，也对国民经济的 发展、国家核心竞争力的提高有着重大意义。 1978 年 ami 公司发布的 s2811 是世界上第一个单片 dsp。1979 年美国 intel 公司发布了商用可编程器件 2920，它是 dsp 芯片发展的一个重要里程碑。dsp 的 体系结构自问世以来发生了巨大的变革，越来越多的通用处理器（gpp）体系结构 被应用到 dsp 的设计实现当中。从最初的以只能满足简单乘累加运算要求为特征 的第一代 dsp 发展到现在的第四代2，dsp 已经具有超长指令字（vliw）和单指 令多数据（simd）相结合的体系结构特点，并越来越多的引入了 cache 结构和独 创片内 cache+ram 的可配置存储结构。 目前国外的 dsp 生产商主要有德州仪器（ti）、摩托罗拉（motorola）、朗 讯科技（lucent）和模拟器件公司（adi），其中 ti 公司对 dsp 的发展具有巨大 的作用。 1997 年 ti 公司发布的 c62xx系列， 以其开创性地引入 vliw 结构使 dsp 设计技术进入一个新时代。随后各 dsp 公司在性能增强上，尤其在开发指令级并 行性上进行了很多创新性设计，如流水线、vliw、risc、superscalar、simd 等 技术都被融入到 dsp 结构中。 现在成功的高性能 dsp 都将 vliw 技术和 simd 技 术结合起来。 tms320c64x是 ti公司于2000年推出的 vliw结构的高性能 dsp3， 目前 tms320c6678 是国际上性能最高的主流 dsp，采用 8 个 1.25ghz 的 dsp 内 核构建而成，并在单个器件上集成了 320 gmac 与 160 gflop 定点及浮点性能。 ti c6000 系列 dsp 运算能力强、 片上存储器容量大、 外设丰富， 代表了高性能 dsp 发展的一个方向。 adi 公司的 tigersharc 系列4也在其传统的 simd 结构中融入了 许多 vliw 的特征。 此外现在还出现了一种把 dsp 核与 gpp 核结合起来的 hybrid 体系结构5，它保留了 gpp 指令集，以及不能被 gpp 指令替换的 dsp 专用指令， 如 sh-dsp 芯片。 国防科学技术大学研究生院工学硕士学位论文 第 2 页 1.1.2 dsp 片内 cache 结构的重要性 dsp 与 gpp 最大的区别在于，dsp 要满足“实时性”和“确定性”的要求6； 实时性：dsp 面向的应用一般为数据密集型运算，处理完一块数据之后要马 上处理下一块数据，并且数据多为流数据，数据保持的时间很短。如果不能及时 处理，数据很可能被下一个数据块淹没导致程序出错，所以 dsp 处理数据的响应 时间要很短，即满足“实时性”要求。 确定性：在 dsp 实时性要求的背景下，程序员必须非常清楚每块数据处理的 时间，以便在程序设计时进行准确的规划。这就要求 dsp 对数据块的处理时间是 相对确定的，即 dsp 的“确定性”问题。 由于 dsp“实时性”和“确定性”的要求，早期不追求高性能的 dsp 通常采 用如图 1.1 所示的 “cpu 核+片内 ram” 的结构， 将程序和数据放到片内 ram 中， 以降低访存的高延迟和时间不确定性6。 图 1.1 adsp21161n 功能结构图6 但是，这样的结构需要程序员自己控制数据搬移，程序员要对底层存储结构 非常清楚，而且基于芯片成本和功耗的的考虑，这种片内 ram 的容量也是很有限 的。随着数字信号处理领域需求的不断增大，需要处理的问题越来越复杂，处理 的数据量也越来越多，片内 ram 已无法满足如此庞大的数据存储要求。同时，要 在编程之前预先规划如此庞大的数据量，将使程序员的工作变得极其繁琐和低效， 程序员也不能很好的将主要精力放到程序和算法的优化上面。 国防科学技术大学研究生院工学硕士学位论文 第 3 页 同时，由于 vlsi 工艺的差异，微处理器和存储芯片性能的差异也越来越大， 存储器访问速度每年提高大约 7%，远落后于微处理器性能提高的速度。当今计算 机系统中，微处理器速度要远远大于存储芯片的速度，并在未来的一段时间内有 进一步加大的趋势， 已形成了一个巨大的剪刀差， 即所谓的 “存储墙” 问题7。 “存 储墙”问题已经成为限制微处理器性能提升的主要瓶颈之一。同样，在对外存容 量需求日益增大的今天，dsp 的设计同样面临“存储墙”问题的挑战。在 dsp 设 计中引入 cache 结构，不仅能够降低 dsp 程序开发的复杂性，同时对于 dsp 整体 性能的提升也有着重要的作用。 但是，对于 dsp 而言，cache 结构有一个致命的缺点：当发生 cache 失效时， cache 依然要从外存读取数据，而这样造成的失效开销不能满足 dsp 的“实时性” 要求，其失效开销的不确定性也不利于程序员对程序运行的掌控。为解决这个问 题，当前的 dsp 设计中采用了“cache+ ram”的片内存储体系结构，将一些核心 的程序和数据放入片内 ram 中，将其他的大量数据放到片外存储器中。这样，即 解决了 cache 失效造成的频繁访问外存问题，也解决了数据存储容量的问题。由此 可见，高效 cache 结构的研究，对提升 dsp 整体性能具有重要的作用。 1.2 相关研究相关研究 引入 cache 结构之后， cpu 的访存时间由 cache 命中时间、 cache 失效率、 cache 失效开销这三个因素共同决定： （1.1）7 其中，cache 命中时间是缺失请求命中本级 cache 并返回数据的时间；cache 失效率是一个概率值， 是上一级 cache 发出的缺失请求在本级 cache 中失效的概率； cache 失效开销为 cache 失效时，向下一级存储器发出访问请求到把整个数据块调 入 cache 所需的时间。因此，为减少 cache 访存时间、提高 cache 工作效率，可以 从 cache 命中时间、cache 失效率、cache 失效开销这三个方面寻求解决方案。 1.2.1 cache 缺失流水线 上一节中已经提到，为了降低 cache 失效造成的频繁访问外存的开销，dsp 采用了“cache+ ram”的片内存储体系结构。但是，即使这样的结构还存在 cache 失效问题的，特别是在对一段外存数据地址连读访问时，可能还会发生暂时的连 续失效。cache 缺失流水线结构能够流水地处理上一级 cache 的缺失请求，从而重 叠本级 cache 的命中时间，间接的减少上一级 cache 的失效开销，提升整个系统的 访存性能。 国防科学技术大学研究生院工学硕士学位论文 第 4 页 刘胜在其硕士学位论文6中介绍了一种 l1 缺失流水线结构，使得在理想情况 下每个 l1 缺失请求的代价只有两拍， 很好地解决了 cache 失效对 dsp 实时性和确 定性要求的影响。在该文中，作者还介绍了一种在 l1 和 l2 之间的写缺失缓冲队 列，减少了写缺失的等待时间。 傅祎晖在其硕士学位论文8 中结合预取 cache 和非阻塞 cache 的结构特点， 进 一步提高了缺失流水线结构的工作效率，解决了缺失请求发送、请求发送的相关 性问题、分支作废指令包等缺失流水线结构中的关键问题。 1.2.2 cache 预取 缺失流水线结构的引入，大大降低了本级 cache 的命中时间，但这只能对连续 缺失请求产生作用。如果 cache 缺失请求不是连续的，那么 cache 的命中时间是不 能被隐藏的，cache 的工作效率还是会受到影响。cache 预取机制能够在数据被请 求之前，将数据提前取进 cache。当数据被请求时能够命中 cache 而减少 cache 失 效的次数，继而降低 cache 的失效率，降低 cache 失效对 cache 工作效率的影响。 按实现方式的不同，预取技术可分为软件预取和硬件预取9。软件预取就是借 助编译器完成的，通过指令预取进行预取的预取机制。在这种预取机制中，编译 器在编译程序时，首先对程序的访存情况做一个整体的估计，然后在适当的位置 添加预取指令。沈立等在文献10中介绍了一种基于控制流的混合指令预取，这种 方法通过在编译程序时静态分析程序的控制流，根据不同的情况在分支出口处插 入不同的预取指令，实现顺序预取与非顺序预取相结合的预取技术。 相对于软件预取，硬件预取依据程序执行时的访存历史信息，动态分析访存 特征并进行预取， 这种预取机制对编译器的要求较低， 工作效率高。 alan jay smith 在文献11中介绍了最简单的一类称为 obl （one block lookahead） 硬件预取方法， 这种方法在访问第 i行时， 硬性地对第 i+1 行进行预取。 norman p.jouppi 在文献12 中介绍了 stream buffer 的预取方法，在访存失效时对 cache 失效数据地址的后续 地址进行预取， 并将预取回来的数据放入 fifo 结构的存储单元， 即 stream buffer。 tien-fu chen等在文献13总结了四种访存模式，同时介绍并分析了三种预取 功能单元对 cache 性能的影响。在该文中，作者详细介绍了基本预取、前瞻预取和 关联预取三种不同的预取方式。其中基本预取就是机械地对当前失效访存操作的 下一个地址进行预取；前瞻预取使用一个前瞻程序计数器控制预取，这个前瞻程 序计数器在理想状态下总是比真实的程序计数器提前一个访存周期，这样就能在 程序真正访存的前一个周期将数据预取进 cache；关联预取是一种更复杂的预取方 式，它将突破循环块的限制去查询访存模式。作者通过模拟测试发现，前瞻预取 对 cache 性能提升的性价比是三种预取方式中最高的。 suni l ki m 国防科学技术大学研究生院工学硕士学位论文 第 5 页 sunil kim 等在文献14中，介绍了一种基于步长的二级 cache 预取方法和系 统。在这篇文章中，作者分析了二级 cache 的预取特点，并针对这些特点设计了一 种专门的步长检测机制，同时结合 stream buffer 设计了一种更适合于二级 cache 的预取方法。郇丹丹等在文献15中介绍了一种结合访存失效队列的预取技术，这 种技术根据访存失效队列的状态进行预取，并将指令预取和数据预取分开，避免 了相互之间的影响。 肖勇在其博士学位论文16中介绍了一种利用增强型步长值预测器进行预取的 方法，该方法采用一种有效的步长反馈机制和信心系统机制，能够学习数据序列