用于光线追踪调度的方法和装置

摘要

本公开提供了用于光线追踪调度的方法、装置和系统、以及计算机可读介质。所述方法包括获取关于多个光线信息对的数据分配信息，其中所述数据分配信息包括所述多个光线信息对中的每一个在存储器中被存储的位置。所述方法还包括实时地获取关于所述多个光线信息对在当前时刻的bank使用信息，其中所述bank使用信息中的每一个表示所述多个光线信息对中的每一个是否涉及bank冲突。所述方法还包括基于所获取的数据分配信息和bank使用信息来调度所述多个光线信息对中的不涉及bank冲突的光线信息对。

权利要求

1.一种用于光线追踪调度的方法，其特征在于，所述方法包括：

获取关于多个光线信息对的数据分配信息，其中所述光线信息对包括配对的节点数据和光线数据，并且所述数据分配信息包括所述多个光线信息对中的每一个在存储器中被存储的位置；

实时地获取关于所述多个光线信息对在当前时刻的bank使用信息，其中所述bank使用信息中的每一个表示所述多个光线信息对中的每一个是否涉及bank冲突；以及基于所获取的数据分配信息和bank使用信息来调度所述多个光线信息对中的不涉及bank冲突的光线信息对。

2.根据权利要求1所述的方法，其特征在于，每个光线信息对中的节点数据和光线数据分别被存储在所述存储器中的各自对应的bank处，所述bank冲突是指存储所述节点数据和光线数据的bank中的任意一个被外部调用。

3.根据权利要求1所述的方法，其特征在于，所述数据分配信息还包括节点数据的有效性标志，所述有效性标志有效表示所述节点数据已经被取回并存储在所述存储器中。

4.根据权利要求3所述的方法，其特征在于，基于所获取的数据分配信息和bank使用信息来调度所述多个光线信息对中的不涉及bank冲突的光线信息对包括：针对每个光线信息对，仅当所述光线信息对中的节点数据的有效性标志有效，并且不涉及bank冲突时，调度所述光线信息对中的节点数据和光线数据。

5.根据权利要求1所述的方法，其特征在于，基于所获取的数据分配信息和bank使用信息来调度所述多个光线信息对中的不涉及bank冲突的光线信息对包括：向所述存储器发送数据调度指令，以传输所述不涉及bank冲突的光线信息对到计算单元以用于求交运算。

6.根据权利要求1所述的方法，其特征在于，获取关于所述多个光线信息对的数据分配信息包括：接收并缓存所述数据分配信息。

7.根据权利要求1所述的方法，其特征在于，实时地获取关于所述多个光线信息对在当前时刻的bank使用信息包括：实时地接收并缓存所述bank使用信息。

8.根据权利要求1所述的方法，其特征在于，所述数据分配信息由bank标识符和line标识符来表示。

9.一种用于光线追踪调度的装置，其特征在于，所述装置包括：

分配信息获取模块，其被配置成获取关于多个光线信息对的数据分配信息，其中所述光线信息对包括配对的节点数据和光线数据，并且所述数据分配信息包括所述多个光线信息对中的每一个在存储器中被存储的位置；

使用信息获取模块，其被配置成实时地获取关于所述多个光线信息对在当前时刻的bank使用信息，其中所述bank使用信息中的每一个表示所述多个光线信息对中的每一个是否涉及bank冲突；以及调度模块，其被配置成基于所述数据分配信息和所述bank使用信息来调度所述多个光线信息对中的不涉及bank冲突的光线信息对。

10.根据权利要求9所述的装置，其特征在于，每个光线信息对中的节点数据和光线数据分别被存储在所述存储器中的各自对应的bank处，所述bank冲突是指存储所述节点数据和光线数据的bank中的任意一个被外部调用。

11.根据权利要求9所述的装置，其特征在于，所述数据分配信息还包括节点数据的有效性标志，所述有效性标志有效表示所述节点数据已经被取回并存储在所述存储器中。

12.根据权利要求11所述的装置，其特征在于，所述调度模块进一步被配置成：针对每个光线信息对，仅当所述光线信息对中的节点数据的有效性标志有效，并且不涉及bank冲突时，调度所述光线信息对中的节点数据和光线数据。

13.根据权利要求9所述的装置，其特征在于，所述调度模块进一步被配置成：向所述存储器发送数据调度指令，以传输所述不涉及bank冲突的光线信息对到计算单元以用于求交运算。

14.根据权利要求9所述的装置，其特征在于，所述获取模块进一步被配置成：接收并缓存所述数据分配信息。

15.根据权利要求9所述的装置，其特征在于，所述获取模块进一步被配置成：实时地接收并缓存所述bank使用信息。

16.根据权利要求9所述的装置，其特征在于，所述数据分配信息由bank标识符和line标识符来表示。

17.一种用于光线追踪调度的系统，其特征在于，所述系统包括：

第一存储器，其被配置成存储节点数据；

第二存储器，其被配置成存储光线数据；

计算单元，其通信地耦合到所述第一存储器和所述第二存储器，并且被配置成接收来自第一存储器和第二存储器的节点数据和光线数据以用于求交运算；以及调度器，其通信地耦合到所述第一存储器和所述第二存储器，并且被配置成执行根据权利要求1‑8中任一项所述的方法。

18.一种其上存储有指令的计算机可读介质，其特征在于，所述指令在被计算设备的处理器执行时使得所述计算设备实行根据权利要求1‑8中任一项所述的方法。

说明书

用于光线追踪调度的方法和装置

技术领域

[0001] 本公开总体上涉及光线追踪的调度。更具体地，本公开涉及用于光线追踪调度的方法、装置和系统、以及计算机可读介质。

背景技术

[0002] 光线追踪（ray tracing）技术是一种用于在二维（2D）屏幕上呈现三维（3D）图像时使用的方法。光线追踪技术利用算法来模拟真实世界中的光线的物理特性，能够实现物理上精确的阴影、反射和折射以及全局光照，从而使虚拟场景中的物体更加具有真实感。因此，光线追踪被广泛地应用于游戏、电影等领域，并且作为一项新颖技术被用于诸如图形卡或图形处理单元（GPU）等装置中。

[0003] 在光线追踪技术的操作中，可以由GPU中的算术逻辑单元（ALU）对场景中的光线和节点（例如BOX或Triangle）进行求交运算，因此ALU会接收分别来自节点缓存和光线缓存的彼此配对的节点数据和光线数据，其中配对的节点数据和光线数据可以由调度器来调度，以便被发送到ALU或计算单元用于求交运算。

[0004] 然而，在调度器调度每一对节点数据和光线数据时，节点缓存和光线缓存两者中可能存在bank冲突——即，配对的节点数据和光线数据分别所在的两个bank（这两个bank分别位于节点缓存和光线缓存）中的一个或两者被除了调度器之外的其他访问者所访问或调用，从而导致这些数据当前无法被调度用于求交运算。在传统的光线追踪调度方法中，当遇到bank冲突时，调度器需要等待冲突消失之后再进行数据读取，而这种等待时间会影响ALU的工作效率。

[0005] 因此，需要一种能够在节点缓存和光线缓存中可能发生bank冲突的情况下高效地调度节点数据和光线数据对的技术，以实现快速的流水，消除等待时间，并保证ALU的工作效率。

发明内容

[0006] 有鉴于此，本公开的目的是提供用于光线追踪调度的方法、装置和系统、以及计算机可读介质，以期望克服上面提到的缺陷。

[0007] 根据本公开的一个方面，提供了一种用于光线追踪调度的方法，包括：获取关于多个光线信息对的数据分配信息，其中所述数据分配信息包括所述多个光线信息对中的每一个在存储器中被存储的位置；实时地获取关于所述多个光线信息对在当前时刻的bank使用信息，其中所述bank使用信息中的每一个表示所述多个光线信息对中的每一个是否涉及bank冲突；以及基于所获取的数据分配信息和bank使用信息来调度所述多个光线信息对中的不涉及bank冲突的光线信息对。

[0008] 在一些实施例中，所述光线信息对包括配对的节点数据和光线数据。

[0009] 在一些实施例中，每个光线信息对中的节点数据和光线数据分别被存储在所述存储器中的各自对应的bank处，所述bank冲突是指存储所述节点数据和光线数据的bank中的任意一个被外部调用。

[0010] 在一些实施例中，所述数据分配信息还包括节点数据的有效性标志，所述有效性标志有效表示所述节点数据已经被取回并存储在所述存储器中。

[0011] 在一些实施例中，基于所获取的数据分配信息和bank使用信息来调度所述多个光线信息对中的不涉及bank冲突的光线信息对包括：针对每个光线信息对，仅当所述光线信息对中的节点数据的有效性标志有效，并且不涉及bank冲突时，调度所述光线信息对中的节点数据和光线数据。

[0012] 在一些实施例中，基于所获取的数据分配信息和bank使用信息来调度所述多个光线信息对中的不涉及bank冲突的光线信息对包括：向所述存储器发送数据调度指令，以传输所述不涉及bank冲突的光线信息对到计算单元以用于求交运算。

[0013] 在一些实施例中，获取关于所述多个光线信息对的数据分配信息包括：接收并缓存所述数据分配信息。

[0014] 在一些实施例中，实时地获取关于所述多个光线信息对在当前时刻的bank使用信息包括：实时地接收并缓存所述bank使用信息。

[0015] 在一些实施例中，所述数据分配信息由bank标识符和line标识符来表示。

[0016] 根据本公开的另一个方面，提供了一种用于光线追踪调度的装置，包括：分配信息获取模块，其被配置成获取关于多个光线信息对的数据分配信息，其中所述数据分配信息包括所述多个光线信息对中的每一个在存储器中被存储的位置；使用信息获取模块，其被配置成实时地获取关于所述多个光线信息对在当前时刻的bank使用信息，其中所述bank使用信息中的每一个表示所述多个光线信息对中的每一个是否涉及bank冲突；以及调度模块，其被配置成基于所述数据分配信息和所述bank使用信息来调度所述多个光线信息对中的不涉及bank冲突的光线信息对。

[0017] 根据本公开的另一个方面，提供了一种用于光线追踪调度的系统，包括：第一存储器，其被配置成存储节点数据；第二存储器，其被配置成存储光线数据；计算单元，其通信地耦合到所述第一存储器和所述第二存储器，并且被配置成接收来自第一存储器和第二存储器的节点数据和光线数据以用于求交运算；以及调度器，其通信地耦合到所述第一存储器和所述第二存储器，并且被配置成执行根据本公开所描述的方法中的任一个。

[0018] 根据本公开的另一个方面，提供了一种其上存储有指令的计算机可读介质，所述指令在被计算机执行时使得计算机实行根据本公开所描述的方法中的任一个。

[0019] 一般而言，在本公开所要求保护的用于光线追踪调度机制的背景下，来自每个输入光线的每一对节点数据和光线数据可以被分别存储在节点缓存和光线缓存中的相应bank处。然后，调度器查询节点缓存和光线缓存中的bank冲突情况，并且调度如下节点和光线数据对：这些节点和光线数据对中的每一对所在的节点缓存和光线缓存中的两个bank均未发生冲突。具体而言，例如，如果其中存储有某一对节点数据和光线数据的两个bank中的任一个或两者发生了冲突，则调度器不调度这一对节点数据和光线数据；如果其中存储有某一对节点数据和光线数据的两个bank都没有发生冲突，则调度器调度这一对节点数据和光线数据，即，促使它们被发送到ALU以执行求交运算。

[0020] 根据本公开的一些实施例，即使节点缓存和光线缓存的bank中可能会出现bank冲突，调度器也会选择调度那些不涉及bank冲突的节点数据和光线数据对，而不是简单地等待当前数据的bank冲突结束。因此，根据本公开的调度机制消除了现有技术中用于等待bank冲突结束的时间延迟，实现了快速的流水，使得ALU能够尽可能在满负荷状态下运行，从而保证了ALU的工作效率。

[0021] 根据下文中描述的实施例，本公开的这些和其他优点将变得清楚，并且参考下文描述的实施例来阐明本公开的这些和其他优点。

附图说明

[0022] 现在将参考附图描述本公开的具体示例性实施例。然而，本公开可以以很多不同的形式来实施，并且不应当被解读为限于本公开所阐述的实施例；相反，这些实施例被提供以便使该公开全面而完整，并且将向本领域技术人员完全表达本公开的范围。在对附图所示特定示例性实施例的详细描述中所使用的术语不旨在对本公开进行限制。在附图中，相同的数字指代相似的部件。

[0023] 图1是示出了可以在其中实现根据本公开的实施例的技术方案的示例性应用场景。

[0024] 图2是示出了根据本公开的一种实施方式的用于光线追踪调度的方法的示例性流程图。

[0025] 图3是示出了根据本公开的实施例的用于光线追踪调度的系统的示例性结构框图。

[0026] 图4是示出了图3的系统中的节点缓存在执行根据本公开的实施例的光线追踪调度期间的过程步骤的示例性流程图。

[0027] 图5是示出了图3的系统中的光线缓冲器在执行根据本公开的实施例的光线追踪调度期间的过程步骤的示例性流程图。

[0028] 图6是示出了图3的系统中的调度器在执行根据本公开的实施例的光线追踪调度期间的过程步骤的示例性流程图。

[0029] 图7示出了根据本公开的实施例的用于光线追踪调度的装置的示例性框图。

[0030] 图8图示了示例系统，其包括表示可以实现本公开所描述的各种方法的一个或多个系统和/或设备的示例计算设备。

具体实施方式

[0031] 下面的描述提供了本公开的各种实施例的具体细节，以便本领域的技术人员能够充分理解和实施本公开的各种实施例。应当理解的是，本公开的技术方案可以在没有这些细节中的一些细节的情况下被实施。在某些情况下，本公开并没有示出或详细描述一些熟知的结构或功能，以避免这些不必要的描述使对本公开的实施例的描述模糊不清。在本公开中使用的术语应当以其最宽泛的合理方式来理解，即使它是结合本公开的特定实施例来使用的。

[0032] 光线追踪是一种用于在二维（2D）屏幕上呈现三维（3D）图像时使用的方法。光线追踪技术利用算法来模拟真实世界中的光线的物理特性，能够实现物理上精确的阴影、反射和折射以及全局光照，从而使虚拟场景中的物体更加具有真实感。具体而言，光线追踪技术主要涉及至少四种元素：场景中的3D物体、场景中的光源、图像平面（作为2D显示屏幕）、以及相机（一般是虚拟的相机或人眼，作为观看3D物体的视角）。

[0033] 下文中，以后向光线追踪（Backward Ray Tracing）为例，简单地描述了光线追踪的示例性过程。首先，从相机发射一条观察光线（例如向量），使其穿过图像平面中的某个像素，之后，该观察光线可能会与场景中的某个物体相交。当使用求交运算确定了该光线与物体相交并计算出交点后，从该交点向场景中的光源发射一条“阴影线”，并判断该阴影线是会碰到其他物体、还是直接到达光源。如果该阴影线直接到达光源，则可以确定先前的观察光线与该物体的交点会被光源照亮，并且相应地计算该光线所穿过的图像平面中像素的颜色（例如，将其颜色设置为表示亮部的值）。然而，如果该阴影线碰到或命中了其他物体，则可以确定先前的交点处于阴影中（即，在该交点处，光源的光被其他物体所遮挡），并且可以将图像平面中被穿过的像素的颜色设置为表示暗部的值。

[0034] 以此类推，可以从相机发射多个方向上的多条观察光线，这些光线随后与场景中的多个物体相交并产生许多反射和折射光线等，这些反射和折射光线可能再次与其他物体相交并产生另外的反射和折射光线，这类似于一个递归过程。然后，可以通过所有这些光线与光源之间建立的阴影线来更准确地确定图像平面中与它们相交的各个像素的颜色，由此确定整个图像平面的颜色，以便被呈现并渲染到显示器上。这样，在显示器上呈现的3D场景以及其中的物体会更加逼真，能够充分地反映出现实世界中光线与各种物体的相互作用，从而增强用户的观看或游戏体验。

[0035] 应当理解的是，上述过程仅仅是示例性的，以便于理解本公开，并且除了后向光线追踪之外，光线追踪技术还包括正向光线追踪、分布式光线追踪、路径追踪、双向路径追踪、随机光线追踪等等。也就是说，本公开所描述的用于数据调度方法适用于各种类型的光线追踪技术。

[0036] 根据上面描述的关于光线追踪的内容，可以看出的是，每当判断某个光线是否与场景中的物体相交以及确定其交点时，要使用ALU或计算单元来执行求交运算。因此，针对每条光线，计算单元可以获得关于该光线的光线数据以及与该光线配对的节点（BOX或Triangle）的数据，而这一对光线和节点数据分别被存储在节点缓存和光线缓存中的两个bank中。当这两个bank中的任一个发生冲突（即bank冲突）时，即存在外部调用，也就是说当这两个bank中的一个或两者被其他设备访问或调用时，其中的光线数据或节点数据可能无法被调度并发送到计算单元以进行求交运算。在常规的光线追踪调度方法中，调度器需要等待bank冲突结束，然后再对数据进行读取和调度，这造成了计算单元的空闲，并且影响了计算单元的效率。

[0037] 为了解决上述问题，本公开提出了一种用于光线追踪调度的机制，即，通过分别查看节点缓存和光线缓存的bank冲突情况并且调度在节点缓存和光线缓存两者中都不涉及bank冲突的光线和节点数据对，来消除等待bank冲突结束的时间，从而改进计算单元的工作效率。

[0038] 图1是示出了可以在其中实现根据本公开的实施例的技术方案的示例性应用场景100。如图1所示，所示的应用场景100包括设备120以及与设备120通信地耦合的GPU 110和显示器130，其中GPU 110和显示器130可以被设置在设备120内部，也可以被设置在设备120外部。此外，GPU 110可以与存储元件和/或其他组件一起作为整体（例如，图形卡）通信地耦合到设备120。

[0039] 作为示例，当设备120产生计算需求时，会将计算请求发送到与设备120连接的GPU 110，并等待GPU 110返回计算结果。在光线追踪的背景下，在一个示例中，GPU 110响应于来自设备120的请求而在3D场景中产生传入光线（例如，上面描述的观察光线、反射光线、折射光线等），并且根据其中包含的信息来获取并缓存关于传入光线的数据（例如节点数据和光线数据），然后对这些数据进行调度和计算（例如求交运算或其他计算等），最后将最终计算结果渲染并呈现到显示器130上进行显示。在上述操作过程中，GPU 110中的计算单元对这些数据进行计算的效率取决于数据调度的效率，数据调度的效率越高，GPU 110中的计算单元越能够以满负荷运行，而不会浪费其计算能力。如图1所示，通过在GPU 110中实现根据本公开的光线追踪调度方法，可以提高GPU 110的计算效率，增强图像渲染的实时性，使得图像像素能够被更好、更快地渲染到显示器130上，从而改进用户的使用体验。

[0040] 作为示例，当在GPU 110中实现本公开的用于光线追踪的数据调度方法时，首先，获取关于多个光线信息对的数据分配信息，其中所述数据分配信息包括所述多个光线信息对中的每一个在存储器中被存储的位置；然后，实时地获取关于所述多个光线信息对在当前时刻的bank使用信息，其中所述bank使用信息中的每一个表示所述多个光线信息对中的每一个是否涉及bank冲突；最后，基于所获取的数据分配信息和bank使用信息来调度所述多个光线信息对中的不涉及bank冲突的光线信息对。

[0041] 上面描述的场景100仅仅是可以在其中实现本公开的实施例的一个示例，并且不是限制性的。例如，GPU 110可以是常见的图形处理器或图形处理单元。设备120可以是终端或者服务器等能够与GPU通信地耦合的设备。当设备120是终端时，其可以是智能手机、平板电脑、笔记本电脑、台式计算机、智能音箱、智能手表等，此处不做限制。当设备120是服务器时，其可以是独立的物理服务器，也可以是多个物理服务器构成的服务器集群或者分布式系统，并且还可以是提供云服务、云数据库、云计算、云函数、云存储、网络服务、云通信、中间件服务、域名服务、安全服务、CDN、以及大数据和人工智能平台等基础云计算服务的云服务器。要注意的是，当设备120是服务器时，显示器130可以是通信地耦合到另一个设备（未示出）的显示装置。例如，作为服务器的设备120可以将其计算结果通过网络（未示出）发送到该另一个设备，使得计算结果可以实时呈现在该另一个设备的显示器130上。

[0042] 图2是示出了根据本公开的一种实施方式的用于光线追踪调度的方法200的示例性流程图。方法200例如可以在如图1所示的GPU 110或设备120上实施。如图2所示，方法200包括以下步骤。

[0043] 步骤210，获取关于多个光线信息对的数据分配信息，其中所述数据分配信息包括所述多个光线信息对中的每一个在存储器中被存储的位置。作为示例，所述存储器可以是GPU中用于缓存数据（例如，来自双倍速率同步动态随机存取存储器（DDR SDRAM）的数据）的组件，诸如高速缓存、缓冲器或其他存储器件等（例如，本公开所描述的节点缓存或光线缓存），并且所述数据分配信息可以是由调度器从所述存储器来接收的。此外，所述光线信息对可以指代由如图1所示的GPU 110中的计算单元接收并对其进行求交运算的数据对。

[0044] 在一些示例中，所述光线信息对可以包括配对的节点数据和光线数据。也就是说，每个光线信息对可以包括一个节点数据以及与其配对的一个光线数据，并且这一对数据可以被用于求交运算。本公开所描述的节点数据可以是节点的坐标，其中术语“节点”指代3D物体在被分割之后所得到的许多“盒子（BOX）”或“三角形（Triangle）”。例如，当节点是BOX时，节点数据可以是对应于该BOX的对角线的两个坐标。此外，本公开所描述的光线数据可以是光线的向量或坐标，其中术语“光线”一般指代从相机或视角发射的光线以及从物体反射或折射的光线等。光线通常可以用原点和向量来表示，用于指示发出该光线的位置以及该光线的行进方向。在另一个示例中，光线也可以用两个三维坐标来表示。因此，当ALU或计算单元获得了配对的光线数据和节点数据时，就可以执行求交运算，即，判断这一对数据所对应的光线和节点是否相交，并且如果相交的话，还可以计算它们的交点。

[0045] 在一些示例中，所述数据分配信息可以包括节点数据分配信息和光线数据分配信息，并且所述数据分配信息可以由bank标识符和line标识符来表示。作为示例，每个光线信息对中的节点数据和光线数据可以分别被存储在节点缓存和光线缓存中的它们各自对应的bank处，并且在这种情况下，所述节点数据分配信息指示所述节点数据被存储在其处的相应bank的标识符以及该bank所在的line的标识符（例如，line ID和bank ID），并且所述光线数据分配信息指示所述节点数据被存储在其处的相应bank的标识符以及该bank所在的line的标识符（例如，line ID和bank ID）。如本公开所使用的，术语“bank”和“line”具有与本领域技术人员所理解的含义相同的含义，即，表示高速缓存或缓冲器等高速存储器件中的存储单元，例如，一个高速缓存中可以具有多条line，其中每条line可以包含四个bank——bank 0、bank 1、bank 2、bank 3，以用于缓存数据。例如，如果所述节点数据分配信息可以被表述为向量(cache_line_ID, cache_bank_ID)，那么关于节点数据分配信息的向量(1, 2)就可以表示某个节点数据被存储在节点缓存的line 1中的bank 2处，并且如果所述光线数据分配信息可以被表述为向量(ray_line_ID, ray_bank_ID)，那么关于光线数据分配信息的向量(2, 3)就可以表示对应的光线数据被存储在光线缓存的line 2中的bank 3处。节点数据和光线数据被分别单独存储（例如，节点数据被存储在节点缓存中，光线数据被存储在光线缓存中），并且每个bank仅能够存储一个节点数据或光线数据。例如，如果关于第一个传入光线RAY1的节点数据被存储在节点缓存的line 1中的bank 2处，那么关于第二个传入光线RAY2的节点数据就不可以被存储在该节点缓存的line 1中的bank 2处，而是仅能够被存储在该节点缓存中的其他bank处。上述示例同样适用于光线数据。这样，就可以仅通过line标识符和bank标识符来定位节点缓存或光线缓存中的每个数据。

[0046] 在一些示例中，所述节点数据可以是根据其节点地址从存储装置中被取回并存储的，其中所述节点地址表示所述节点数据在所述存储装置中的地址。作为示例，所述存储装置可以是GPU中的用于存储要处理的图形信息或数据的组件（例如，DDR SDRAM），这些信息或数据稍后可能被读取出来（例如被读取到高速缓存）以用于缓存、计算或其他操作。所述存储装置可以包括但不限于易失性存储介质（诸如随机存取存储器（RAM）、静态随机存取存储器（SRAM）和动态随机存取存储器（DRAM））和/或非易失性存储介质（诸如只读存储器（ROM）、闪存、光盘、磁盘等）。作为示例，节点缓存可以首先从传入光线接收节点地址，其中传入光线包含光线数据以及与所配对的节点数据相对应的节点地址；然后，节点缓存可以为该节点数据分配存储位置（例如，节点缓存的某个line中的某个bank）并且将该存储位置（即，数据分配信息）发送给调度器；最后，节点缓存根据该节点地址在存储装置中查找该节点数据并且将该节点数据取回并存储在该位置处。作为另一个示例，节点数据也有可能已经被存储在节点缓存中。例如，节点缓存首先根据该节点地址进行搜索，以确定节点数据是否已经被存储在节点缓存中，如果是，则节点缓存向调度器发送该节点数据被存储的位置（例如，节点缓存中的line的标识符和bank的标识符）；如果否，则节点缓存为该节点数据分配存储位置并将该位置发送给调度器，然后根据节点地址从存储装置中取回该节点数据并将其存储在该位置处，如上面描述的那样。

[0047] 在一些示例中，所述数据分配信息还可以包括节点数据的有效性标志，所述有效性标志有效表示所述节点数据已经被取回并存储在所述存储器中。具体而言，所述数据分配信息可以包括节点数据分配信息和光线数据分配信息，并且所述节点数据分配信息可以包括针对每个节点数据的有效性标志。在这种情况下，如果所述节点数据分配信息可以被表述为例如向量(cache_line_ID, cache_bank_ID, cache_line_valid)——其中“cache_line_valid”是该节点数据的有效性标志，那么关于节点数据分配信息的向量(1, 2, 0)（其中cache_line_valid = 0）可以表示分配给某个节点数据的存储位置是节点缓存的line 1中的bank 2并且该节点数据已经被取回并存储在那里，并且关于节点数据分配信息的向量(1, 2, 1)（其中cache_line_valid = 1）可以表示分配给该节点数据的存储位置是节点缓存的line 1中的bank 2并且该节点数据尚未被取回并存储在那里。要注意的是，本公开所描述的有效性标志并不是始终不变的，也就是说，关于每个节点数据的有效性标志可以随时间或周期性地被更新，以表示节点数据在当前时刻是否有效，从而确保了数据及时性。例如，某个节点数据已经被分配了相应的存储位置（例如，关于节点缓存的line ID和bank ID），但是该节点数据在当前时钟周期尚未被取回并存储在该位置处，因此其有效性标志可以被设置为0，以指示该节点数据在当前时钟周期是无效的；然而，当处于下一个时钟周期时，该节点数据很可能已经被取回并存储在相应的位置处，因此，在此时，其有效性标志可以被设置为1，以指示该节点数据是有效的。在这种情况下，在一个示例中，节点缓存可以以各种方式向调度器实时通知某个节点数据的有效性标志的改变、或者直接将改变后的有效性标志发送给调度器。

[0048] 在一些示例中，获取关于所述多个光线信息对的数据分配信息可以包括：接收并缓存所述数据分配信息。具体而言，调度器可以接收并缓存多个数据分配信息，因此可以得到关于多个光线信息对（对应于多个传入光线RAY1‑N）的数据分配信息的列表，其具体描述了关于每个光线信息对中的节点数据和光线数据分别被存储或分配的位置、以及可能地还有针对节点数据的有效性标志。此外，在一个示例中，当所述数据分配信息包括节点数据分配信息和光线数据分配信息并且由line标识符和bank标识符来表示时，调度器可以通过将关于节点数据和光线数据的line和bank标识符缓存在不同的地方或者通过其他任何方式来区分表示节点数据与光线数据的存储位置的标识符。

[0049] 步骤220，实时地获取关于所述多个光线信息对在当前时刻的bank使用信息，其中所述bank使用信息中的每一个表示所述多个光线信息对中的每一个是否涉及bank冲突。作为示例，所述bank使用信息可以是由调度器从节点缓存或光线缓存来接收的。如本公开所使用的，实时地获取所述bank使用信息意味着每个bank使用信息可以仅表示当前时钟周期的bank冲突情况，并且当处于下一个时钟周期时，所述bank使用信息可以被再次获取。具体而言，所述bank使用信息指示配对的节点数据和光线数据分别被存储在其处的两个bank中的一个或两者在当前时刻是否发生冲突，也就是说，表示这两个bank中的一个或两者在例如当前时钟周期是否正在被其他访问者所访问或调用。这样，关于多个光线信息对中的每一个的bank使用信息可以随时间或周期性地被更新，例如在每个时钟周期被更新，因此确保了数据及时性，有利于更高效地调度和计算其中的光线和节点数据，并且避免了由于bank占用情况随时间的变化而导致的误调度。如本公开所使用的，术语“bank冲突”可以指代如下情况：即，本公开所描述的高速缓存或缓冲器中的某个缓存单元bank被除了调度器之外的其他访问者所访问或调用，从而导致调度器无法读取或调度该bank中的数据。此外，如本公开所使用的，术语“其他访问者”可以指代GPU内除了调度器之外的可以执行数据访问或读取或调用等功能的任何其他组件或元件，此处不做限制。

[0050] 在一些示例中，实时地获取关于所述多个光线信息对在当前时刻的bank使用信息可以包括：实时地接收并缓存所述bank使用信息。具体而言，例如，调度器可以在每个时钟周期接收并缓存关于当前光线RAYi的bank使用信息，因此可以得到关于多个光线信息对（对应于多个传入光线RAY1‑N）的bank使用信息的列表，其具体描述了每个光线数据在当前时刻是否涉及bank冲突。

[0051] 步骤230，基于所获取的数据分配信息和bank使用信息来调度所述多个光线信息对中的不涉及bank冲突的光线信息对。作为示例，假设调度器所获取的数据分配信息包含对应于五个传入光线RAY1‑5的五个光线信息对中的节点数据和光线数据分别被存储的位置（例如，分别由关于节点缓存和光线缓存的line ID和bank ID来表示），并且调度器所获取的bank使用信息指示只有对应于传入光线RAY1和RAY2的两个光线信息对不涉及bank冲突，则调度器此时可以根据这两个光线信息对中的节点数据和光线数据被存储的位置来调度它们，而不调度其他剩余的三个光线信息对。这样，即使节点缓存和光线缓存的bank中可能会出现bank冲突，调度器也会选择调度不涉及bank冲突的那些节点数据和光线数据对，而不是简单地等待bank冲突结束，由此消除了现有技术中用于等待bank冲突结束的时间延迟，实现了快速的流水，并保证了ALU的工作效率。要注意的是，在本公开中，并没有限制那些不涉及bank冲突的光线信息对被调度的次序，它们可以是根据对应光线被传入的时间来调度的，或者是根据所定义的优先级来调度的，或者是以其他方式来调度的。

[0052] 在一些示例中，基于所获取的数据分配信息和bank使用信息来调度所述多个光线信息对中的不涉及bank冲突的光线信息对可以包括：向所述存储器发送数据调度指令，以传输所述不涉及bank冲突的光线信息对到计算单元以用于求交运算。作为示例，当调度器根据bank使用信息确定了某个光线信息对不涉及bank冲突时，它可以向该数据对中的节点数据和光线数据分别所在的节点缓存和光线缓存发送调度指令（例如，该调度指令还可以包括节点数据和光线数据分别被存储的位置，即，所获取的数据分配信息），使得节点缓存和光线缓存能够将这一对节点和光线数据传输到ALU或计算单元以进行求交运算。

[0053] 在一些示例中，所述bank冲突是指存储所述节点数据和光线数据的bank中的任意一个被外部调用。如本公开所使用的，术语“被外部调用”可以指代存储所述节点数据和光线数据的bank中的任一个或两者被其他访问者所访问或调用。换句话说，不涉及bank冲突的光线信息对就可以指代那些其中的节点数据和光线数据分别被存储的两个bank都没有被其他访问者所访问或调用的光线信息对。作为示例，假设某个光线信息对中的节点数据被存储在节点缓存的line 1中的bank 2处，并且对应的光线数据被存储在光线缓存的line 2中的bank 3处，如果这两个bank都没有发生bank冲突，即，这两个bank都没有被其他访问者所访问或调用，则该光线信息对不涉及bank冲突，因此可以被调度；否则（即，如果这两个bank中的任何一个或两个发生了bank冲突），则该光线信息对涉及bank冲突，因此不可以被调度。如本公开所使用的，术语“其他访问者”可以指代GPU内除了调度器之外的可以执行数据访问或读取或调用等功能的任何其他组件或元件，此处不做限制。

[0054] 在一些示例中，基于所获取的数据分配信息和bank使用信息来调度所述多个光线信息对中的不涉及bank冲突的光线信息对可以包括：针对每个光线信息对，仅当所述光线信息对中的节点数据的有效性标志有效，并且不涉及bank冲突时，调度所述光线信息对中的节点数据和光线数据。作为示例，在所述节点数据分配信息包括每个节点数据的有效性标志的情况下，如果某个光线信息对中的节点数据在存储之前被分配了节点缓存的line 1中的bank 2以供存储，并且其对应的光线数据被存储在光线缓存的line 2中的bank 3处，那么当该节点数据已经被取回并存储在节点缓存的line 1中的bank 2处并且节点缓存和光线缓存中的这两个bank都没有被其他访问者所访问或调用时，调度器就可以调度该光线信息对中的节点数据和光线数据。

[0055] 总体来说，方法200首先分别从节点缓存和光线缓存获取关于多个节点和光线数据对的数据分配信息，然后实时地获取关于它们的bank使用信息，最后根据所获取的数据分配信息和bank使用信息来调度不涉及bank冲突的那些节点和光线数据对。以这种方式，如果调度器在调度某一对节点和光线数据之前根据数据分配信息和实时获取的bank使用信息发现该对数据可能涉及bank冲突，它就可以根据这些信息来调度不涉及bank冲突的其他节点和光线数据对，而无需等待当前数据对的bank冲突结束，由此消除了等待时间，提高了GPU中的计算单元或ALU的效率。

[0056] 图3是示出了根据本公开的实施例的用于光线追踪调度的系统300的示例性结构框图。如图3所示，系统300可以包括调度器310、节点缓存320、光线缓冲器330和计算单元340。系统300可以被包括在如图1所示的GPU 110中或者是其一部分，以执行本公开所描述的用于光线追踪调度方法，诸如方法200。在图3中，节点缓存320可以被配置成存储节点数据，并且光线缓冲器330可以被配置成存储光线数据。计算单元340可以通信地耦合到节点缓存320和光线缓冲器330，并且可以被配置成接收来自节点缓存320和光线缓冲器330的节点数据和光线数据以用于求交运算。此外，调度器310可以通信地耦合到节点缓存320和光线缓冲器330，并且可以被配置成执行本公开所描述的用于光线追踪的调度方法，诸如方法
200。具体而言，节点缓存320和光线缓冲器330可以分别存储光线信息对中的节点数据和光线数据，并且将它们的数据分配信息和bank使用信息发送给调度器310，而调度器310在接收到该数据分配信息和bank使用信息后，可以基于这些信息来调度那些不涉及bank冲突的光线信息对，即，分别向节点缓存320和光线缓冲器330发送调度指令以使得它们将这些光线信息对中的节点数据和光线数据传输到计算单元340以用于求交运算。

[0057] 图4是示出了图3的系统300中的节点缓存320在执行根据本公开的实施例的光线追踪调度期间的过程步骤400的示例性流程图。图5是示出了图3的系统300中的光线缓冲器330在执行根据本公开的实施例的光线追踪调度期间的过程步骤500的示例性流程图。图6是示出了图3的系统300中的调度器310在执行根据本公开的实施例的光线追踪调度期间的过程步骤600的示例性流程图。参考图3至图6，详细描述了根据本公开的调度系统300如何执行用于光线追踪的数据调度的具体过程。

[0058] 下面，将参考图3至图5，针对系统300中的节点缓存320和光线缓冲器330进行描述。

[0059] 步骤410，节点缓存320接收关于传入光线RAY_IN（i 其中i=1...N，N＞1）的node_data_alloc_request（节点数据分配请求）。步骤510，光线缓冲器330接收关于RAY_INi的ray_data_alloc_request（光线数据分配请求）。这里，node_data_alloc_request和ray_data_alloc_request两者均来自于系统300外部的组件或逻辑（未示出），所述组件或逻辑可以是响应于RAY_IN（传入光线）而向节点缓存320和光线缓冲器330发送请求的任何软件或硬件或固件、或其任何组合，在此不做限制。

[0060] 步骤420，响应于node_data_alloc_request，节点缓存320接收RAY_INi中包含的node_address（节点地址），并且为与node_address相对应的node_data（节点数据）分配其在节点缓存320中的存储位置，例如由关于节点缓存320的line ID和bank ID来表示。这里，RAY_IN包含node_data（节点数据）的node_address、以及配对的ray_data（光线数据），其中彼此配对的node_data和ray_data可以构成光线信息对，并且node_address表示node_data在存储装置中的地址。作为示例，所述存储装置可以是GPU中的用于存储要处理的图形信息或数据的组件（例如，DDR SDRAM），这些信息或数据稍后可能被读取出来（例如被读取到高速缓存）以用于缓存或计算以及显示在显示器上。所述存储装置可以包括但不限于易失性存储介质（诸如随机存取存储器（RAM）、静态随机存取存储器（SRAM）和动态随机存取存储器（DRAM））和/或非易失性存储介质（诸如只读存储器（ROM）、闪存、光盘、磁盘等）。步骤425，节点缓存320根据node_address在所述存储装置中查找node_data，以便将其取回并存储在节点缓存320中的所分配的位置处。

[0061] 步骤520，响应于ray_data_alloc_request，光线缓冲器330接收RAY_INi中包含的ray_data，并且将ray_data存储在光线缓冲器330中，其中，ray_data在光线缓冲器330中被存储的位置由line ID和bank ID来表示。

[0062] 步骤430，节点缓存320向调度器310发送关于RAY_INi的tag_lookup_response（节点数据分配信息），其中tag_lookup_response包括给对应于RAY_INi的node_data分配的在节点缓存320中的存储位置以及node_data是否有效（是否已经被取回并存储）的信息，例如，由向量(cache_line_ID, cache_bank_ID, cache_line_valid)来表示。这里，“cache_line_ID”和“cache_bank_ID”指代node_data的存储位置被分配在节点缓存320中的哪个line中的哪个bank处，并且“cache_line_valid”指代node_data是否已经被取回并存储在这里。

[0063] 步骤530，光线缓冲器330向调度器310发送关于RAY_INi的ray_buffer_alloc_info（光线数据分配信息），其中ray_buffer_alloc_info包括关于RAY_INi的ray_data在光线缓冲器330中被存储的位置，例如，由向量(ray_line_ID, ray_bank_ID)来表示。这里，“ray_line_ID”和“ray_bank_ID”指代ray_data被存储在光线缓冲器330中的哪个line中的哪个bank处。由于光线缓冲器330在接收到ray_data之后会直接将ray_data存储在其中，因此不需要针对ray_data的有效性标志来表明ray_data是否已经被存储，也就是说，ray_data在光线缓冲器330中是始终有效的。

[0064] 要理解的是，虽然没有在图3中示出，但是node_data也有可能在被分配存储位置之前就已经被存储在节点缓存320中。因此，在一些示例中，节点缓存320可以首先根据node_address在其中进行搜索，以确定node_data是否已经被存储在节点缓存320中，如果是，则节点缓存320向调度器310发送node_data被存储的位置（例如，节点缓存320中的line的标识符和bank的标识符），此时，与ray_data一样，node_data在节点缓存320中是始终有效的；如果否，则节点缓存320可以先给node_data分配其在节点缓存320中的存储位置，然后根据node_address在存储装置中查找node_data以便将其取回并存储，如上面描述的步骤420和425那样。

[0065] 步骤440，节点缓存320根据tag_lookup_response向调度器310发送关于RAY_INi在当前时刻的cache_bank_use_info（即，关于节点缓存的bank使用信息），其中cache_bank_use_info表示对应于RAY_INi的node_data当前是否涉及bank冲突。在一个示例中，cache_bank_use_info可以具体地表示对应于RAY_INi的node_data的存储位置（例如，被分配的用于存储的位置、或已经被存储在其中的位置，其可以由cache_line_ID和cache_bank_ID来表示）当前是否发生bank冲突，即对应于该位置的bank当前是否被外部调用，即，被除了调度器310之外的其他访问者所访问或调用。例如，针对当前传入光线RAY_INi，如果其对应的node_data在当前时钟周期涉及bank冲突，则节点缓存320可以向调度器310传输指示“1”的标志，并且如果其对应的node_data在当前时钟周期不涉及bank冲突，则节点缓存320可以向调度器310传输指示“0”的标志。

[0066] 步骤540，光线缓冲器330根据ray_buffer_alloc_info向调度器310发送关于RAY_INi在当前时刻的ray_bank_use_info（即，关于光线缓冲器330的bank使用信息），其中ray_bank_use_info表示对应于RAY_INi的ray_data当前是否涉及bank冲突。在一个示例中，ray_bank_use_info可以具体地表示对应于RAY_INi的ray_data在光线缓冲器330中被存储的位置（其可以由ray_line_ID和ray_bank_ID来表示）当前是否发生bank冲突，即对应于该位置的bank当前是否被外部调用，即，被除了调度器310之外的其他访问者所访问或调用。例如，针对当前传入光线RAY_INi，如果其对应的ray_data在当前时钟周期涉及bank冲突，则光线缓冲器330可以向调度器310传输指示“1”的标志，并且如果其对应的ray_data在当前时钟周期不涉及bank冲突，则光线缓冲器330可以向调度器310传输指示“0”的标志。

[0067] 这里，由于cache_bank_use_info和ray_bank_use_info仅指代当前时刻（例如，当前时钟周期）的bank使用信息，因此节点缓存320和光线缓冲器330可以实时地向调度器310发送这些bank使用信息，以确保数据的及时性。这样，当在先前时刻正在被其他访问者访问或调用的某个bank在当前时刻结束了bank冲突时，该bank所对应的节点缓存320或光线缓冲器330就可以针对该bank中的数据向调度器310发送新的cache_bank_use_info和ray_bank_use_info、或者将该情况反馈给调度器310以用于更新。因此，这样做可以使得调度器310了解到最新的bank冲突情况，避免了数据或信息的滞后性。

[0068] 在执行步骤440之后，节点缓存320可以返回到步骤410，并针对下一个光线RAY_INi+1执行上述步骤410‑440。要注意的是，虽然没有示出，但是在针对下一个光线RAY_INi+1执行这些步骤时，节点缓存320不仅可以同时更新并发送对应于上一个光线RAY_INi的node_data在当前时刻的有效性标志和bank冲突信息，而且还可以并行地执行稍后描述的步骤450。

[0069] 同样地，在执行步骤540之后，光线缓冲器330也可以返回到步骤510，并针对下一个光线RAY_INi+1执行上述步骤510‑540。要注意的是，虽然没有示出，但是在针对下一个光线RAY_INi+1执行这些步骤时，光线缓冲器330不仅可以同时更新并发送对应于上一个光线RAY_INi的ray_data在当前时刻的bank冲突信息，而且还可以并行地执行稍后描述的步骤550。

[0070] 步骤450，响应于接收到node_data_request（节点数据请求），节点缓存320将对应于其中数据有效且不涉及bank冲突的那些RAY_IN的node_data发送到计算单元340用于求交运算。这里，node_data_request是由调度器310发送的，具体而言，它可以是当调度器310基于tag_lookup_response和cache_bank_use_info确定了对应于这些RAY_IN的node_data有效并且该node_data和ray_data对不涉及bank冲突时被发送的。在一个示例中，node_data_request可以基于tag_lookup_response，即，除了针对node_data的请求之外，还可以包括node_data在节点缓存320中被存储的位置，例如cache_line_ID和cache_bank_ID，以便于节点缓存320能够找到node_data并将其发送。

[0071] 步骤550，响应于接收到ray_data_request（光线数据请求），光线缓冲器330将对应于其中数据有效且不涉及bank冲突的那些RAY_IN的ray_data发送到计算单元340用于求交运算。这里，ray_data_request是由调度器310发送的，具体而言，它可以是当调度器310基于ray_buffer_alloc_info和ray_bank_use_info确定了对应于这些RAY_IN的node_data有效并且该node_data和ray_data对不涉及bank冲突时被发送的。在一个示例中，ray_data_request可以基于ray_buffer_alloc_info，即，除了针对ray_data的请求之外，还可以包括ray_data在光线缓冲器330中被存储的位置，例如ray_line_ID和ray_bank_ID，以便于光线缓冲器330能够找到ray_data并将其发送。

[0072] 要注意的是，出于说明性的目的，上述操作和过程仅仅是示例性的，并且在此不做限制。此外，上面描述的过程可以包括更多或更少的步骤，并且这些步骤可以迭代地或以流水线的方式来执行，或者可以并行或同时地执行，或者以其他方式执行。

[0073] 下面，将参考图3和图6，针对系统300中的调度器310进行描述。

[0074] 步骤610，调度器310分别从节点缓存320和光线缓冲器330获取关于多个RAY_IN1‑N（其中N＞1）的tag_lookup_response和ray_buffer_alloc_info，其中tag_lookup_response和ray_buffer_alloc_info分别表示对应于该多个RAY_IN1‑N的配对node_data和ray_data分别在节点缓存320和光线缓冲器330中的存储位置。在一个示例中，调度器310可以接收并缓存tag_lookup_response和ray_buffer_alloc_info，因此可以得到关于该多个RAY_IN1‑N的数据分配信息的列表。在tag_lookup_response还包括针对每个node_data的有效性标志的情况下，调度器310可以实时更新该有效性标志、或者实时获取更新后的有效性标志。由于步骤610与上面描述的步骤430和530相对应，因此在这里不进行详细描述。

[0075] 步骤620，调度器310分别从节点缓存320和光线缓冲器330实时地获取关于多个RAY_IN1‑N在当前时刻的cache_bank_use_info和ray_buffer_alloc_info，其中cache_bank_use_info和ray_buffer_alloc_info分别表示对应于该多个RAY_IN1‑N的多个光线信息对中的每一对node_data和ray_data当前是否涉及bank冲突。在一个示例中，调度器310可以接收并缓存cache_bank_use_info和ray_buffer_alloc_info，因此可以得到关于该多个RAY_IN1‑N的bank使用信息的列表。此外，由于cache_bank_use_info和ray_buffer_alloc_info仅表示当前时刻的bank使用信息并且是实时获取的，因此针对每一对node_data和ray_data的bank使用信息可以随时间或周期性地被更新，因此确保了数据及时性，并且避免了由于bank占用情况随时间的变化而导致的误调度。由于步骤620与上面描述的步骤440和540相对应，因此在这里不进行详细描述。

[0076] 步骤630，基于接收到的tag_lookup_response和ray_buffer_alloc_info以及cache_bank_use_info和ray_buffer_alloc_info，调度器310针对每一个传入光线（例如，RAY_INi）确定与其相对应的node_data是否有效并且这一对node_data和ray_data是否不涉及bank冲突。作为示例，node_data的有效性可以用向量(cache_line_ID, cache_bank_ID, cache_line_valid)中的“cache_line_valid”来表示。此外，某个node_data和ray_data对不涉及bank冲突意味着node_data和ray_data两者都不涉及bank冲突，也就是说，它们在节点缓存320和光线缓冲器330中分别被存储的两个位置都没有发生bank冲突。

[0077] 步骤640，在确定了关于每一个传入光线的有效性和bank冲突情况后，调度器310选择调度那些有效并且不涉及bank冲突的node_data和ray_data对。作为示例，如果调度器310获取到关于五个传入光线RAY_IN1‑5的数据分配信息和bank使用信息，并且其中仅两个光线RAY_IN1和RAY_IN2所对应的光线信息对（即，配对的node_data和ray_data）有效并且不涉及bank冲突，则调度器310就可以调度这些光线信息对，而不调度对应于其余光线RAY_IN3‑5的光线信息对。在一个示例中，在执行调度操作时，调度器310可以向节点缓存320和光线缓冲器330发送node_data_request和ray_data_request，以使得节点缓存320和光线缓冲器330将满足上述条件的那些配对的node_data和ray_data传输到计算单元340，计算单元340此时可以关于每一对node_data和ray_data执行求交运算，并输出结果RAY_OUT。此外，在上面的示例中，如果对应于传入光线RAY_IN1‑5的光线信息对全部未能满足上述条件，则调度器310可以等待至下一个时钟周期并再次进行判断，直到找到满足上述条件的传入光线（可能是RAY_IN1‑5中的一个或多个，也可能是其他传入光线，或者其两者）为止。

[0078] 因此，相比于传统的调度方法（即，等待当前数据的bank冲突结束后，才能够读取并调度数据），根据本公开的方法能够大大减少等待时间，提高GPU中的计算单元的效率。在根据上面描述的用于光线追踪调度方法中，即使调度器需要等待至下一个时钟周期，该时间也远远小于如传统方法中那样等待关于当前数据的bank冲突结束为止的时间，这是因为调度器会在每个时钟周期持续地接收许多条传入光线并且节点缓存或光线缓存中每个bank的冲突情况也会随时间快速改变，因此满足上述条件（即，不涉及bank冲突）的传入光线可以被调度器很快地找到，然后与它们相对应的节点数据和光线数据对就可以被调度。

[0079] 要注意的是，出于说明性的目的，上述操作和过程仅仅是示例性的，并且在此不做限制。此外，上面描述的过程可以包括更多或更少的步骤，并且这些步骤可以迭代地或以流水线的方式来执行，或者可以并行或同时地执行，或者以其他方式执行。

[0080] 图7示出了根据本公开的实施例的用于光线追踪调度的装置700的示例性框图。如图7所示，装置700包括分配信息获取模块710、使用信息获取模块720和调度模块730。装置700可以与图3的系统300中的调度器310具有类似的配置，并且被配置成执行根据本公开的用于光线追踪调度的方法中的任一个，诸如图2的方法200、或图4至图6中的方法步骤400‑
600。

[0081] 分配信息获取模块710被配置成获取关于多个光线信息对的数据分配信息，其中所述数据分配信息包括所述多个光线信息对中的每一个在存储器中被存储的位置。

[0082] 使用信息获取模块720被配置成实时地获取关于所述多个光线信息对在当前时刻的bank使用信息，其中所述bank使用信息中的每一个表示所述多个光线信息对中的每一个是否涉及bank冲突。

[0083] 调度模块730被配置成基于所述数据分配信息和所述bank使用信息来调度所述多个光线信息对中的不涉及bank冲突的光线信息对。

[0084] 要注意的是，上面描述的装置700的结构和配置仅仅是示例性的，并且在此不做限制。

[0085] 图8图示了示例系统800，其包括表示可以实现本公开所描述的各种方法的一个或多个系统和/或设备的示例计算设备810。计算设备810可以是例如服务提供商的服务器、与服务器相关联的设备、片上系统、和/或任何其他合适的计算设备或计算系统。上面参考图6描述的装置700和上面参考图3描述的系统300均可以采取计算设备810的形式或者被包括在计算设备810中。替代地，装置700或系统300可以以应用816的形式被实现为计算机程序。

[0086] 所图示的示例计算设备810包括彼此通信地耦合的处理系统811、一个或多个计算机可读介质812以及一个或多个I/O接口813。尽管未示出，但是计算设备810还可以包括将各种组件彼此耦合的系统总线或其他数据和命令传送系统。系统总线可以包括不同总线结构的任何一个或组合，所述总线结构诸如存储器总线或存储器控制器、外围总线、通用串行总线、和/或利用各种总线架构中的任何一种的处理器或局部总线。还构思了各种其他示例，诸如控制和数据线。

[0087] 处理系统811表示使用硬件来执行一个或多个操作的功能。因此，处理系统811被图示为包括可以被配置成处理器、功能块等的硬件元件814。这可以包括在硬件中实现为专用集成电路或使用一个或多个半导体形成的其他逻辑器件。硬件元件814不受其形成的材料或其中采用的处理机构的限制。例如，处理器可以由（多个）半导体和/或晶体管（例如，电子集成电路（IC））组成。在这种情境中，处理器可执行指令可以是电子可执行指令。

[0088] 计算机可读介质812被图示为包括存储器/存储装置815。存储器/存储装置815表示与一个或多个计算机可读介质相关联的存储器/存储装置。存储器/存储装置815可以包括易失性介质（诸如随机存取存储器（RAM））和/或非易失性介质（诸如只读存储器（ROM）、闪存、光盘、磁盘等）。存储器/存储装置815可以包括固定介质（例如，RAM、ROM、固定硬盘驱动器等）以及可移动介质（例如，闪存、可移动硬盘驱动器、光盘等）。计算机可读介质812可以以下面进一步描述的各种其他方式来配置。

[0089] 一个或多个I/O接口813表示允许用户使用各种输入设备向计算设备810输入命令和信息并且可选地还允许使用各种输出设备将信息呈现给用户和/或其他组件或设备的功能。输入设备的示例包括键盘、光标控制设备（例如，鼠标）、麦克风（例如，用于语音输入）、扫描仪、触摸功能（例如，被配置成检测物理触摸的容性或其他传感器）、相机（例如，可以采用可见或不可见的波长（诸如红外频率）将不涉及触摸的运动检测为手势）等等。输出设备的示例包括显示设备（例如，监视器或投影仪）、扬声器、打印机、网卡、触觉响应设备等。因此，计算设备810可以以下面进一步描述的各种方式进行配置以支持用户交互。

[0090] 计算设备810还包括应用816。应用816可以例如是用于光线追踪调度的装置700的软件实例，并且与计算设备810中的其他元件相组合地实现本公开所描述的技术。

[0091] 在本公开中，可以在软件硬件元件或程序模块的一般情境中描述各种技术。一般来说，这些模块包括执行特定任务或实现特定抽象数据类型的例程、程序、对象、元素、组件、数据结构等。本公开所使用的术语“模块”，“功能”和“组件”一般表示软件、固件、硬件或其组合。本公开所描述的技术的特征是与平台无关的，意味着这些技术可以在具有各种处理器的各种计算平台上实现。

[0092] 所描述的模块和技术的实现可以被存储在某种形式的计算机可读介质上或者跨某种形式的计算机可读介质来传输。计算机可读介质可以包括可由计算设备810访问的各种介质。作为示例而非限制，计算机可读介质可以包括“计算机可读存储介质”和“计算机可读信号介质”。

[0093] 与单纯的信号传输、载波或信号本身相反，“计算机可读存储介质”是指能够持久存储信息的介质和/或设备，和/或有形的存储装置。因此，计算机可读存储介质是指非信号承载介质。计算机可读存储介质包括诸如易失性和非易失性、可移动和不可移动介质和/或以适用于存储信息（诸如计算机可读指令、数据结构、程序模块、逻辑元件/电路或其他数据）的方法或技术实现的存储设备之类的硬件。计算机可读存储介质的示例可以包括但不限于RAM、ROM、EEPROM、闪存或其他存储器技术、CD‑ROM、数字通用盘（DVD）或其他光学存储装置、硬盘、盒式磁带、磁带，磁盘存储装置或其他磁存储设备，或其他存储设备、有形介质或适于存储期望信息并可以由计算机访问的制品。

[0094] “计算机可读信号介质”是指被配置成诸如经由网络将指令发送到计算设备810的硬件的信号承载介质。信号介质典型地可以将计算机可读指令、数据结构、程序模块或其他数据体现在诸如载波、数据信号或其他传输机制的调制数据信号中。信号介质还包括任何信息传递介质。术语“调制数据信号”是指如下这样的信号，该信号的特征中的一个或多个被设置或改变，从而将信息编码到该信号中。作为示例而非限制，通信介质包括诸如有线网络或直接连线的有线介质以及诸如声、RF、红外和其他无线介质的无线介质。

[0095] 如前所述，硬件元件814和计算机可读介质812表示以硬件形式实现的指令、模块、可编程器件逻辑和/或固定器件逻辑，其在一些实施例中可以用于实现本公开所描述的技术的至少一些方面。硬件元件可以包括集成电路或片上系统、专用集成电路（ASIC）、现场可编程门阵列（FPGA）、复杂可编程逻辑器件（CPLD）以及硅中的其他实现或其他硬件设备的组件。在这种情境中，硬件元件可以作为执行由硬件元件所体现的指令、模块和/或逻辑所定义的程序任务的处理设备，以及用于存储用于执行的指令的硬件设备，例如，先前描述的计算机可读存储介质。

[0096] 前述组合也可以用于实现本公开所描述的各种技术和模块。因此，可以将软件、硬件或程序模块和其他程序模块实现为在某种形式的计算机可读存储介质上和/或由一个或多个硬件元件814体现的一个或多个指令和/或逻辑。计算设备810可以被配置成实现与软件和/或硬件模块相对应的特定指令和/或功能。因此，例如通过使用处理系统的计算机可读存储介质和/或硬件元件814，可以至少部分地以硬件来实现将模块实现为可由计算设备810作为软件执行的模块。指令和/或功能可以由一个或多个制品（例如，一个或多个计算设备810和/或处理系统811）可执行/可操作以实现本公开所描述的技术、模块和示例。

[0097] 在各种实现方式中，计算设备810可以采用各种不同的配置。例如，计算设备810可以被实现为包括个人计算机、台式计算机、多屏幕计算机、膝上型计算机、上网本等的计算机类设备。计算设备810还可以被实现为包括诸如移动电话、便携式音乐播放器、便携式游戏设备、平板计算机、多屏幕计算机等移动设备的移动装置类设备。计算设备810还可以实现为电视类设备，其包括具有或连接到休闲观看环境中的一般地较大屏幕的设备。这些设备包括电视、机顶盒、游戏机等。

[0098] 本公开所描述的技术可以由计算设备810的这些各种配置来支持，并且不限于本公开所描述的技术的具体示例。功能还可以通过使用分布式系统、诸如通过如下所述的平台822而在“云”820上全部或部分地实现。

[0099] 云820包括和/或表示用于资源824的平台822。平台822抽象云820的硬件（例如，服务器）和软件资源的底层功能。资源824可以包括在远离计算设备810的服务器上执行计算机处理时可以使用的应用和/或数据。资源824还可以包括通过互联网和/或通过诸如蜂窝或Wi‑Fi网络的订户网络提供的服务。

[0100] 平台822可以抽象资源和功能以将计算设备810与其他计算设备连接。平台822还可以用于抽象资源的分级以提供遇到的对于经由平台822实现的资源824的需求的相应水平的分级。因此，在互连设备实施例中，本公开所描述的功能的实现可以分布在整个系统800内。例如，功能可以部分地在计算设备810上以及通过抽象云820的功能的平台822来实现。

[0101] 本申请提供了一种计算机存储介质，其上存储有计算机指令。计算设备的处理器从计算机可读存储介质读取该计算机指令并且执行该计算机指令，使得该计算设备执行上述各种可选实现方式中提供的用于光线追踪调度的方法或技术。

[0102] 应当理解，为了清楚起见，参考不同的功能单元对本公开的实施例进行了描述。然而，将明显的是，在不偏离本公开的情况下，每个功能单元的功能可以被实现在单个单元中、实现在多个单元中、或作为其他功能单元的一部分来实现。例如，被说明成由单个单元执行的功能可以由多个不同的单元来执行。因此，对特定功能单元的参考仅被视为对用于提供所描述的功能的适当单元的参考，而不是表明严格的逻辑或物理结构或组织。因此，本公开可以被实施在单个单元中，或者可以在物理上和功能上被分布在不同的单元和电路之间。

[0103] 应当理解的是，尽管第一、第二、第三等术语在本公开中可以用来描述各种设备、元件、部件或部分，但是这些设备、元件、部件或部分不应当由这些术语所限制。这些术语仅用来将一个设备、元件、部件或部分与另一个设备、元件、部件或部分相区分。

[0104] 尽管已经结合一些实施例描述了本公开，但是其不旨在被限于本公开所阐述的特定形式。相反地，本公开的范围仅由所附权利要求来限制。附加地，尽管单独的特征可以被包括在不同的权利要求中，但是这些可以可能地被有利地组合，并且包括在不同权利要求中不暗示特征的组合不是可行的和/或有利的。特征在权利要求中的次序不暗示特征必须以其工作的任何特定次序。此外，在权利要求中，词“包括”不排除其他元件，并且术语“一”不排除多个。权利要求中的附图标记仅作为明确的示例被提供，不应该被解释为以任何方式限制权利要求的范围。