一种光线追踪加速器的数据预取缓冲方法及装置

1.本发明涉及微处理器设计技术领域，具体涉及一种光线追踪加速器的数据预取缓冲方法及装置。


背景技术：

2.长期以来，人们认为光线追踪算法由于需要大量的计算以至于无法在交互式渲染中应用。随着集成电路工艺技术的进步，在单个芯片上可以集成越来越多的计算单元，因而光线追踪会随着计算能力的增加而显著提高性能，但内存系统成为面向交互式应用的瓶颈，特别是采用常规的光线追踪算法时由于随机内存访问的模式而导致cache的失效率提升。
3.光栅化和光线追踪这两种主要的渲染方式在处理3d场景的方式不同。光栅化算法通过对场景数据(三角形)进行遍历，而光线追踪算法是采用分层数据结构访问场景中必要的部分。由于光线追踪的理论复杂度与场景大小是亚线性的，几十年来，人们预计当增长的平均场景达到一定程度时，光线追踪的速度会比光栅化更快，而光栅化的复杂度与场景大小是线性相关的。然而，从存储架构的角度来看，由于加速数据结构(光线追踪)驱动的数据访问比三角形数据流(光栅化)更随机，所以数据访问可能会限制现代计算机系统中主要的性能限制和能源开销。迄今为止，对场景数据的随机访问影响了光线追踪达到预期的理论峰值性能。如果光线追踪的场景访问模式不能更好地匹配内存架构硬件，距离超越光栅化还有很大的差距。目前光栅化的渲染广泛应用在实时渲染领域，一方面是由于其采用局部光照原理，仅考虑光源照射到物体表面直接可见的光照效果，另一方面是由于光栅化的方式对数据流而言可以完美地进行预取，使得存储架构更高效。
4.当前gpu大多是针对光栅化图形渲染流水线设计的，由于数据流的不规则形，使得控制分歧与访存分歧现象严重，导致在传统gpu上实现非常低效，计算资源的利用率和缓冲的命中率都非常低。传统的缓冲在实际应用时，有以下缺陷：1)由于场景加速数据结构在片外存储上是存储的，不规则的访问导致缓冲命中率；2)缓冲块的大小与加速数据结构的大小不匹配，导致效率低；3)查找与替换策略与光线遍历和三角形相交测试运算不匹配。


技术实现要素：

5.本发明要解决的技术问题：针对现有技术的上述问题，提供一种光线追踪加速器的数据预取缓冲方法及装置，本发明旨在解决光线追踪加速器的存储系统效率低下、导致性能无法进一步提升的问题，能够提升光线追踪加速器的存储系统效率，进而提升光线追踪加速器的加速性能。
6.为了解决上述技术问题，本发明采用的技术方案为：
7.一种光线追踪加速器的数据预取缓冲方法，包括：
8.s101，检测光线追踪加速器当前取数据的地址b在一级缓冲中是否命中，若命中则直接从一级缓冲中取出地址b的光线数据并返回，结束并退出；否则跳转步骤s102；
9.s102，判断是否包含为地址b的数据分配的流缓冲区，若包含分配的流缓冲区，则跳转步骤s103，否则为地址b的数据分配流缓冲区并跳转步骤s104；
10.s103，从对应的流缓冲区中取出地址b的数据并返回、从流缓冲区的下一级存储单元中取出地址b+n的数据并放入流缓冲区，其中n为流缓冲区的大小，退出；
11.s104，从流缓冲区的下一级存储单元中取出地址b的数据并返回，将地址b+1～b+n的数据放入流缓冲区，退出。
12.可选地，步骤s102中判断是否包含为地址b的数据分配的流缓冲区时，包括遍历多个流缓冲区以判断是否存在某一个流缓冲区的数据地址与地址b偏移量等于设定值，若某一个流缓冲区的数据地址与地址b偏移量等于设定值则判定该流缓冲区是为地址b的数据分配的流缓冲区。
13.可选地，所述流缓冲区包含多个存储单元，每一个存储单元用于存储一个地址的数据，且多个存储单元采用队列的方式存储。
14.可选地，步骤s102中为地址b的数据分配流缓冲区时采用的调度策略为选择距离上一次使用时间间隔最长策略、随机选择策略或者轮换选择策略。
15.可选地，步骤s103中从对应的流缓冲区中取出地址b的数据并返回、从流缓冲区的下一级存储单元中取出地址b+n的数据并放入流缓冲区时，还包括将剩余地址b+1～b+n-1的数据依次迁移以使得地址b+1～b+n的光线数据按照读取顺序排列。
16.此外，本发明还提供一种光线追踪加速器的数据预取缓冲装置，包括相互连接的一级缓冲和下一级存储单元，所述一级缓冲和下一级存储单元之间串接有流缓冲单元，所述流缓冲单元包括流缓冲区和用于控制流缓冲区读写的预取模块，所述预取模块被编程或配置以执行前文所述光线追踪加速器的数据预取缓冲方法。
17.可选地，所述流缓冲单元包括多个流缓冲区，每一个流缓冲区包含多个存储单元，每一个存储单元用于存储一个地址的数据，且多个存储单元采用队列的方式存储。
18.此外，本发明还提供一种光线追踪加速器，包括加速器本体和用于为加速器本体中的光线遍历单元提供数据缓冲的数据预取缓冲装置，所述数据预取缓冲装置为所述的光线追踪加速器的数据预取缓冲装置。
19.此外，本发明还提供一种光线追踪加速器的数据预取缓冲装置，包括微处理器、光线追踪加速器和存储器，所述微处理器分别与光线追踪加速器和存储器相连，所述光线追踪加速器被编程或配置以执行前文所述光线追踪加速器的数据预取缓冲方法。
20.此外，本发明还提供一种计算机可读存储介质，所述计算机可读存储介质中存储有计算机程序，所述计算机程序用于被光线追踪加速器编程或配置以执行前文所述光线追踪加速器的数据预取缓冲方法。
21.和现有技术相比，本发明主要具有下述优点：
22.1、读取数据效率提升。由于方法的特性，使得流缓冲区的设计在面向光线追踪加速器中访存效率更高。调整流缓冲区的大小也会增加访存效率。
23.2、设计逻辑简单。流缓冲区在传统cache(一级缓冲)的基础上增加了一级缓冲区做预取数据的存储，实现较为简单。
24.3、增加的存储开销小。一级缓冲可根据实际应用情况选择增加缓冲区的大小，如果对硬件资源要求高，那么可将缓冲区的深度设置为1。
附图说明
25.图1为本发明实施例方法的基本流程示意图。
26.图2为本发明实施例中数据预取缓冲装置的结构示意图。
27.图3为本发明实施例中数据预取缓冲装置的工作过程实例示意图。
具体实施方式
28.如图1所示，本实施例光线追踪加速器的数据预取缓冲方法包括：
29.s101，检测光线追踪加速器当前取数据(可为光线数据、加速数据结构或三角形数据)的地址b在一级缓冲中是否命中，若命中则直接从一级缓冲中取出地址b的数据并返回，结束并退出；否则跳转步骤s102；
30.s102，判断是否包含为地址b的数据分配的流缓冲区，若包含分配的流缓冲区，则跳转步骤s103，否则为地址b的数据分配流缓冲区并跳转步骤s104；
31.s103，从对应的流缓冲区中取出地址b的光线数据并返回、从流缓冲区的下一级存储单元中取出地址b+n的数据并放入流缓冲区，其中n为流缓冲区的大小，退出；
32.s104，从流缓冲区的下一级存储单元中取出地址b的数据并返回，将地址b+1～b+n的数据放入流缓冲区，退出。
33.本实施例光线追踪加速器的数据预取缓冲方法采用数据预取缓冲对光线追踪硬件进行存储架构的定制化设计，结合光线追踪算法中数据特性以及数据访问存在的时间和空间局部性等，主要原理如下：一方面由于光线数据在系统中按顺序读取，读取方法类似于cpu中的顺序指令读取，因而针对光线数据的cache更高效；另一方面，当光线与加速数据结构的节点或三角形数据相交测试时，有很大几率与下一个地址的节点或三角形数据也相交，所以针对加速数据结构和三角形的缓冲也会更高效。
34.本实施例中，步骤s102中判断是否包含为地址b的数据分配的流缓冲区时，包括遍历多个流缓冲区以判断是否存在某一个流缓冲区的数据地址与地址b偏移量等于设定值，若某一个流缓冲区的数据地址与地址b偏移量等于设定值则判定该流缓冲区是为地址b的数据分配的流缓冲区。
35.本实施例中，流缓冲区包含多个存储单元，每一个存储单元用于存储一个地址的数据，且多个存储单元采用队列的方式存储。
36.本实施例中，步骤s102中为地址b的数据分配流缓冲区时采用的调度策略为选择距离上一次使用时间间隔最长策略、随机选择策略或者轮换选择策略。
37.本实施例中，步骤s103中从对应的流缓冲区中取出地址b的数据并返回、从流缓冲区的下一级存储单元中取出地址b+n的数据并放入流缓冲区时，还包括将剩余地址b+1～b+n-1的数据依次迁移以使得地址b+1～b+n的光线数据按照读取顺序排列。
38.综上所述，本实施例光线追踪加速器的数据预取缓冲方法旨在解决光线追踪加速器存储系统效率低下，导致性能无法进一步提升的问题。随着半导体技术不断发展，在单个芯片上可以集成越来越多的硬件资源，内存系统成为影响光线追踪性能进一步提升的主要瓶颈，由于其算法不规则的访存方式，导致cache缺失率高，访存低效。而本实施例方法结合光线追踪加速器的光线追踪算法，使用支持数据预取的缓冲能够有效对光线、加速数据结构、三角形等数据进行预取，进而优化光线追踪的访存效率，提升性能。
39.如图2所示，本实施例提供一种光线追踪加速器的数据预取缓冲装置，包括相互连接的一级缓冲(l1 cache)和下一级存储单元，一级缓冲和下一级存储单元之间串接有流缓冲单元，流缓冲单元包括流缓冲区(流缓冲区1～流缓冲区3)和用于控制流缓冲区读写的预取模块(图中省略未绘出)，预取模块被编程或配置以执行前文所述光线追踪加速器的数据预取缓冲方法。，其工作流程为：每当预取的缓存检测到内存块(如b缺失)时，预取cache将分配一个数据流并从命中的cache块开始预取连续的块。如果缓冲区可以容纳四个块，则可以预取如图所示的b+1、b+2、b+3和b+4，并将其保存在分配好的流缓冲区中。然后，当硬件加速器读取b+1，它将流缓冲区中的数据“向上”移动到一级缓冲(l1 cache)中。流缓冲区的第一个流中的值变为b+2，以此类推。假定当前取数的地址设置为b，因此在流缓冲区存储的数据为b+1，b+2，b+3，b+4。当前取数据的地址为b，当次取数发生缺失，所以l1级预取cache会向下一级存储单元取数，在取数的同时会将b+1，b+2，b+3，b+4的数据预取到流缓冲区中，这时将地址为b的数据存放在l1级cache中，预取的数据存放在流缓冲区1中。假设下次取数的数据为b+1，首先在l1级cache中再次发生缺失，会向流缓冲区中和下一次存储单元取数，在流缓冲区中可以读取b+1，那么，就将地址为b+1数据“向上”移动到l1级cache中去，同时在下一级存储单元读取地址为b+5的数据。完成读取数据后，在流缓冲区的数据按顺序变为b+2，b+3，b+4和b+5。其他流缓冲区的数据移动与流缓冲区1相似。在实际设计时可以根据需求设计一组或多组流缓冲区用于缓存预取数据，也可以根据硬件资源限制选择设置每个流缓冲区的深度。需要说明的是可，根据光线、加速数据结构和三角形数据进行定制流缓冲区的cache块大小设计。
40.本实施例中，流缓冲单元包括多个流缓冲区，每一个流缓冲区包含多个存储单元，每一个存储单元用于存储一个地址的数据，且多个存储单元采用队列的方式存储。
41.此外，本实施例还提供一种光线追踪加速器，包括加速器本体和用于为加速器本体中的光线遍历单元提供数据缓冲的数据预取缓冲装置，数据预取缓冲装置为的光线追踪加速器的数据预取缓冲装置。
42.此外，本实施例还提供一种光线追踪加速器的数据预取缓冲装置，包括微处理器、光线追踪加速器和存储器，微处理器分别与光线追踪加速器和存储器相连，光线追踪加速器被编程或配置以执行前文光线追踪加速器的数据预取缓冲方法。
43.此外，本实施例还提供一种计算机可读存储介质，计算机可读存储介质中存储有计算机程序，计算机程序用于被光线追踪加速器编程或配置以执行前文光线追踪加速器的数据预取缓冲方法。
44.本领域内的技术人员应明白，本技术的实施例可提供为方法、系统、或计算机程序产品。因此，本技术可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本技术可采用在一个或多个其中包含有计算机可用程序代码的计算机可读存储介质(包括但不限于磁盘存储器、cd-rom、光学存储器等)上实施的计算机程序产品的形式。本技术是参照根据本技术实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实
现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。
45.以上所述仅是本发明的优选实施方式，本发明的保护范围并不仅局限于上述实施例，凡属于本发明思路下的技术方案均属于本发明的保护范围。应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理前提下的若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。

技术特征：
1.一种光线追踪加速器的数据预取缓冲方法，其特征在于，包括：s101，检测光线追踪加速器当前取数据的地址b在一级缓冲中是否命中，若命中则直接从一级缓冲中取出地址b的数据并返回，结束并退出；否则跳转步骤s102；s102，判断是否包含为地址b的数据分配的流缓冲区，若包含分配的流缓冲区，则跳转步骤s103，否则为地址b的数据分配流缓冲区并跳转步骤s104；s103，从对应的流缓冲区中取出地址b的数据并返回、从流缓冲区的下一级存储单元中取出地址b+n的数据并放入流缓冲区，其中n为流缓冲区的大小，退出；s104，从流缓冲区的下一级存储单元中取出地址b的数据并返回，将地址b+1～b+n的数据放入流缓冲区，退出。2.根据权利要求1所述的光线追踪加速器的数据预取缓冲方法，其特征在于，步骤s102中判断是否包含为地址b的数据分配的流缓冲区时，包括遍历多个流缓冲区以判断是否存在某一个流缓冲区的数据地址与地址b偏移量等于设定值，若某一个流缓冲区的数据地址与地址b偏移量等于设定值则判定该流缓冲区是为地址b的数据分配的流缓冲区。3.根据权利要求1所述的光线追踪加速器的数据预取缓冲方法，其特征在于，所述流缓冲区包含多个存储单元，每一个存储单元用于存储一个地址的数据，且多个存储单元采用队列的方式存储。4.根据权利要求1所述的光线追踪加速器的数据预取缓冲方法，其特征在于，步骤s102中为地址b的数据分配流缓冲区时采用的调度策略为选择距离上一次使用时间间隔最长策略、随机选择策略或者轮换选择策略。5.根据权利要求1所述的光线追踪加速器的数据预取缓冲方法，其特征在于，步骤s103中从对应的流缓冲区中取出地址b的数据并返回、从流缓冲区的下一级存储单元中取出地址b+n的数据并放入流缓冲区时，还包括将剩余地址b+1～b+n-1的数据依次迁移以使得地址b+1～b+n的数据按照读取顺序排列。6.一种光线追踪加速器的数据预取缓冲装置，包括相互连接的一级缓冲和下一级存储单元，其特征在于，所述一级缓冲和下一级存储单元之间串接有流缓冲单元，所述流缓冲单元包括流缓冲区和用于控制流缓冲区读写的预取模块，所述预取模块被编程或配置以执行权利要求1～5中任意一项所述光线追踪加速器的数据预取缓冲方法。7.根据权利要求6所述的光线追踪加速器的数据预取缓冲装置，其特征在于，所述流缓冲单元包括多个流缓冲区，每一个流缓冲区包含多个存储单元，每一个存储单元用于存储一个地址的数据，且多个存储单元采用队列的方式存储。8.一种光线追踪加速器，包括加速器本体和用于为加速器本体中的光线遍历单元提供数据缓冲的数据预取缓冲装置，其特征在于，所述数据预取缓冲装置为权利要求6或7所述的光线追踪加速器的数据预取缓冲装置。9.一种光线追踪加速器的数据预取缓冲装置，包括微处理器、光线追踪加速器和存储器，所述微处理器分别与光线追踪加速器和存储器相连，其特征在于，所述光线追踪加速器被编程或配置以执行权利要求1～5中任意一项所述光线追踪加速器的数据预取缓冲方法。10.一种计算机可读存储介质，所述计算机可读存储介质中存储有计算机程序，其特征在于，所述计算机程序用于被光线追踪加速器编程或配置以执行权利要求1～5中任意一项所述光线追踪加速器的数据预取缓冲方法。

技术总结
本发明公开了一种光线追踪加速器的数据预取缓冲方法及装置，本发明方法包括检测光线追踪加速器当前取光线数据、加速数据结构或三角形数据的地址B在一级缓冲中是否命中，若未命中则判断是否包含为地址B的数据分配的流缓冲区，若包含分配的流缓冲区，则从对应的流缓冲区中取出地址B的数据并返回、从流缓冲区的下一级存储单元中取出地址B+n的数据并放入流缓冲区，否则为地址B的数据分配流缓冲区并从流缓冲区的下一级存储单元中取出地址B的数据并返回，将地址B+1～B+n的光线数据放入流缓冲区。本发明能够有效对光线、加速数据结构、三角形等数据进行预取，进而优化光线追踪的访存效率，提升性能。提升性能。提升性能。


技术研发人员：黄立波 闫润 苏垠 郭辉 郑重 邓全 郭维 雷国庆 王俊辉 隋兵才 孙彩霞 王永文 倪晓强
受保护的技术使用者：中国人民解放军国防科技大学
技术研发日：2023.04.13
技术公布日：2023/7/21