通过优化缓存重用在多处理器共享存储器系统上体积绘制

摘要

本发明涉及一种方法、系统和产品，用于在以多内核处理器（P）和多个末级缓存（LLC）实现在多插座主板中的共享存储器系统（10）上的医学图像的体积绘制。本方法包括：-把绘制所要使用的图像空间（MR）分解成多个区域（Re）；-为每一个各分解后的区域（Re）分配两个插座（S）；-为一个区域（Re）确定一种瓦片枚举方案；-在分配的两个插座（S）上根据确定的瓦片枚举方案绘制区域（Re）内的多个瓦片（T）的所有瓦片（T），直至完成各自区域（Re）；-如果完成了一个区域（Re）：将这两个插座（S）分配给另一区域（Re）；-如果没有留下区域（Re）：根据分割方案将未绘制瓦片的现有区域分割成子区域，并且对于该子区域重复地应用这些步骤。

说明书

技术领域

本发明涉及图像处理领域，特别涉及体积绘制并且特别指的是通过考虑 硬件架构来优化缓存重用的方法。

在工程和科学的许多领域如医学技术图像处理中，快速显现大量图像数 据是主要问题。因为现代体素数据集的规模，尤其是在医学成像中，要计算 体积数据集的所有项目，不得不进行巨量的存储器存取。由于通过增加计算 内核数量所致并行化提升而带来的硬件计算能力改进大于存储器带宽的以 及存储器延迟的提升，所以对于体积绘制算法，体积数据存储器存取性能在 许多情况下成为确定总体性能的制约因素。因此，为了实现最佳性能，重要 的是通过最大化缓存重用使存储器存取的影响最小化。许多已知的体积绘制 过程就缓存重用而言显示出重大缺点。

背景技术

取决于各自计算机平台，已知用于体积绘制的不同方法。在使用多核处 理器的共享存储器系统的情况下，通行方法是，通过分解用于体积或图像绘 制的图像空间，来分布绘制图像所需要的工作负荷。将结果图像分解成许多 小瓦片（tile），其中各瓦片保持完整图像的一部分。然后，在不同硬件组件 上和/或借助不同线程，可以计算图像的瓦片的不同部分。

在大多数硬件上，对所要存取的数据进行缓存，因而，数据集一旦加载， 将在存储器缓存中保留一些时间。对缓存存储器的存取远远快于对标准存储 器的存取。如果在包含体素数据的随机存取存储器（RAM）中的每个数据 集对于各绘制图像只是一次加载进入缓存或从不加载，则存储器存取策略是 最优的。通常，存储器系统包括由多个缓存级别构成的多层次结构的缓存， 其中，这种层次结构的末级缓存（LLC）通常在所有内核之间共享。

对于多处理器系统上的体积绘制主要存在两类：

-对象空间分解算法，其中将体积分解成多个子块；以及

-图像空间分解算法，其中将得到的图像分解成多个瓦片；以及

-之前所提及方法的组合。

本发明针对第二类，即针对图像空间分解算法，并可以与对象空间分解 方案相结合。

一般而言，在射线跟踪或光栅化图形基元（如网格和样条（spline））的 背景下也使用图像空间分解算法。

在Kutluca H.等人于1997年发表的论文“Image-space decomposition  algorithms for sort-first parallel volume rendering of unstructured grids”中，描述 了三大类图像空间分解算法：

1．静态分解

2．动态分解，以及

3．适应性分解。

静态分解方案将图像分解成多个区域，这些区域静态地分配给可用的多 个线程。这种静态负荷平衡方法遭遇的问题是，绘制负荷在多个处理器间可 能不会均匀地分布。

动态负荷平衡基于这样的想法，各线程一完成其先前绘制工作，就动态 地查询新工作负荷。动态算法将图像分解成小瓦片。各线程接收一个瓦片、 计算该图像、并且在完成时请求要绘制的下一空闲瓦片。此方法保证在仍有 工作要做时没有任何线程是空闲的。

对这种基本动态算法的一种改进是额外地适应工作负荷的大小。这里， 开始时一个线程不是查询仅仅一个瓦片，而是查询多个瓦片。稍后，当未处 理瓦片的数量减少时，被查询瓦片的数量减少，直至刚好一个瓦片被查询并 且达成该基本算法（参见S.Parker等人，1998）。

这种修改基于这样的想法，开始时减少线程争用，同时达成该基本方案 而不使粒度变松，从而，仍允许细粒度工作负荷分布。

另一项建议的改进是，将初始图像分解成大小相等的矩形区域，其中将 各处理器分配给这样的区域。于是，各区域由更小的瓦片组成，并且，各处 理器按扫描线顺序来处理块体的多个瓦片。当一个处理器完成了计算所有其 瓦片时，其转向未完成工作负荷的按扫描线次序的下一处理器，并且获取 （grab）仍需计算的瓦片。由于开始时各处理器在彼此靠近的多个瓦片上工 作，所以这样一种算法改进了开始时关于各处理器的瓦片局部性。这种效果 有多大，取决于整个工作负荷在初始区域之间如何分布。

用于瓦片分解的另一动态算法由Whitman提出（S.Whitman，1994年）。 这里，将图像分解成矩形区域，其中区域数量至少和处理器数量一样多。最 初，将各处理器分配至这样的区域，以及，当完成此区域时，处理器请求下 一空闲区域。在区域内，沿扫描线处理内部工作负荷。当对于一个处理器来 说没有任何空闲区域留下时，将具有最多未完成的工作项目的处理器的工作 负荷分割成两个工作负荷。由于未完成的工作负荷形成一个矩形区域，该分 割将此矩形区域分解成两个较小矩形区域，并且该空闲处理器处理下部一 个，而另一处理器继续对上部的工作。通过总是在上部的区域上开始工作， 保证了当前处理器即使在分割期间也能在其工作负荷上继续，直至其完成其 所分配的区域。一种锁定避免一个以上的处理器在同时试图分割同一区域。

适应性分解算法使用附加假设来建立图像分解，以考虑整个图像上变化 的复杂分布。这种附加数据通常通过估计必须处理的预期工作负荷来建立， 目标是建立图像的分解，使得所建立的区域具有同量预期工作负荷。这种方 法经常使用空间分区算法来计算一种解决方案。

能使用的其他附加信息是预先计算出的图像的工作负荷，假设在相互作 用期间，区域中所要求的工作负荷之差在两个图像计算之间不会改变至较大 程度。

将适应性算法与静态或动态算法相结合以分布工作负荷。例如通过根据 预期工作负荷将瓦片分类并且首先处理具有较高预期工作负荷的那些瓦片， 那么当与动态算法结合时，假设信息也能用来影响动态调度过程内的工作分 布。

当基于将体积存储为线性切片阵列的体积数据格式进行体积绘制时，体 积绘制器的缓存行为受到体积相对于观察照相机的取向的强烈影响。在全部 内容以引用方式并入本文的美国专利2011/0170756中，提出了一种算法， 对于在规则网格上计算体积样本（例如，在使用正投影的体积绘制的情况下， 满足这一点），该算法允许克服这种问题。在三维规则网格内的三维块体的 情况下，示出如何找到一种采样位置的排列（permutation），当按照由该排 列所限定的顺序采样体积体素时，使缓存重用得到优化。

关于上述方法的进一步细节，在例如下列文献中可以找到，这些文献的 全部内容以引用方式并入本文：

-F.Abraham,W.Celes,R.Cerqueira and J.Campos,"A load-balancing  strategy for sort-first distributed rendering",in17th Brazilian  Symposium on Computer Graphics and Image Processing,2004,pp. 292-299.

-H.Kutluca,T.M.Kurc and C.Aykanat."Image-space decomposition  algorithms for sort-first parallel volume rendering of unstructured  grids",The Journal of Supercomputing,vol.15,pp.51-93,1997.

-B.B.Labronici,C.Bentes,L.Maria,A.Drummond and R.Farias, "Dynamic screen division for load balancing the raycasting of irregular  data",Cluster Computing and Workshops.IEEE CLUSTER2009.Pp. 1-10,2009.

-K-L.Ma,J.S.Painter,C.D.Hansen and M.F.Krogh,"A data  distributed,parallel algorithm for ray-traced volume rendering", Parallel Rendering Symposium,pp.15-22,1993.

-S.Marchesin,C.Mongenet and J-M.Dischler,"Dynamic load  balancing for parallel volume rendering",Eurographics Symposium on  Parallel Graphics and Visualization2006,pp.43-50.

-J.Nieh and M.Levoy,"Volume rendering on scalable shared-memory  MIMD architectures",in Proc.Of the1992Workshop on Volume  Visualization,October1992,pp.17-24.

-M.E.Palmer,B.Totty,S.Taylor:"Ray Casting on Shared-Memory  Architectures.Memory-Hierarchy Considerations in Volume  Rendering",IEEE Concurrency,IEEE Service Center,Piscataway,NY, US,vol.6,No.1,Jan.1998,pp.20-35,XP000737883.

-S.Parker,P.Shirley,Y.Livnat,C.Hansen,P.-P.Sloan.Interactive ray  tracing for isosurface rendering.VIS'98:Proceedings of the conference  on Visualization'98,Pages:233-238.

-R.Samanta,J.Zheng,T.Funkhouser,K.Li and J.P.Singh,"Load  Balancing for multi-projector rendering systems",in Proc.Of the  SIGGRAPH/Eurographics Workshop on Graphics Hardware,August  1999,pp.107-116.

-R.Schneider,"Method for sampling volume data of an object in an  imaging device",上文中提到的美国专利申请No.20110170756.

-J.P.Singh,P.Jaswinder and A.Gupta and M.Levoy.Parallel  Visualization Algorithms:Performance and Architectural Implications. Computer,pages45-55,1994.

-S.Tabik,F.Romero,G.Utrera and O.Plata,"Mapping parallel loops on  multicore systems",In15th Workshop on compilers for parallel  computing(CPC2010),Vienna,Jul2010.

-S.Whitman,"Dynamic load balancing for parallel polygon rendering", IEEE Computer Graph.and Appl.,vol.14,no.4,pp.41-48,July1994.

发明内容

本发明所要解决的问题是，克服上述已知系统的缺点，特别是提供一种 方法，该方法在考虑到在体积绘制期间能跨越瓦片充分利用大规模LLC缓 存的情况下，对于整个缓存层次结构而言允许跨越瓦片优化缓存重用。一般 而言，应当对具有一个或多个处理器的共享存储器系统内的体积绘制方法的 整体性能进行优化。本发明的又一目的是，通过使同步开销最小化来提供一 种动态负荷平衡，其也用于跨越瓦片组间的大的工作负荷差异。同步尤其应 当使锁定争用（lock contention）最小化，使得所有线程都忙碌，并且不会因 为同步而不是绘制瓦片而等待。所提出的方法应该是非阻塞的（不使用锁 定），或者至少应当使要求锁定情形的数量最小化。

根据独立权利要求的特征解决了这种问题。从从属权利要求中得到进一 步的实施方式。

下文中，更具体地描述本方法。关于本方法所要提及的优点、特点以及 可选实施方式也可应用于装置和/或应用于产品，反之亦然。功能特点可以 软件和/或以硬件方式实现。本发明还针对用于体积绘制的医学器材。

为了解决这种问题，提供了一种方法，用于在具有一个或多个处理器的 共享存储器系统上进行图像绘制。各处理器可以包括一个处理器内核或一组 内核。一个内核可以分配给一个缓存。也可能几个内核共享至少一个缓存， 特别是末级缓存。典型地，这些处理器可以并行地计算至少一个线程的指令。 将共享一个缓存的那些处理器内核定义为一种插座（socket）。本方法包括：

-把要用于绘制的图像空间分解为多个区域，其中，各区域包括多个瓦 片；

-将所有可用插座分配给这些区域，其中，给每一个分解后的区域分配 两个插座，用于绘制的目的；

-为一个区域确定一种瓦片枚举方案，其中该瓦片枚举方案包括用于瓦 片计算的正向标引和对应的反向标引；

-在所分配的第一插座上根据确定的瓦片枚举方案的正向标引、以及在 所分配的第二插座上根据确定的瓦片枚举方案的反向标引，绘制区域内的多 个瓦块，直至完成一个区域；

-如果完成了一个区域：将这两个插座分配给另一个（空闲）区域；

-如果没有留下任何区域：根据一种分割方案，将现有的未绘制瓦片的 区域分割成子区域，并且对于该子区域重复地应用确定和/或绘制的步骤。

下文中给出本申请中所使用术语的定义。

应广义地解释术语“图像”，包括二维图像或三维体积或时间序列（视频 等）。特别地，本方法用于体积绘制并且指医学体数据集。本方法可以应用 在医学图像处理的背景下和/或可以用原子指令（atomic instruction）实现在 动态链接库（作为DLL代码）中。此外，本方法可以实现或集成在具有插 入接口的插件中，以使其与主机应用程序和/或其他服务程序连接。

取决于用于图像或体积绘制的实际硬件，不同物理情况可能会有所区 别。进行体积绘制所使用的共享存储器系统可以包括内部具有一组处理内核 的一个处理器（称为1-插座系统）、或者多个这种处理器（其具有多个处理 器插座）。在某些情况下，内部方式“安装”在物理主板插座上的处理器可以 由封装进同一处理器插座的多个处理器构建而成，例如，AMD处理器的 Magny-Cours就是这样一种多芯片模块（MCM）处理器。

下文中，术语“多插座系统”是在具有共享末级缓存（LLC）的逻辑处理 器数量而非物理插座数量的意义上进行解释的。

缓存理解为具有快速存取的存储器。缓存可以由其它内核共享，或者可 以是私有的（分配给特定内核）。

有可能所有内核都在同一处理器上。可选择地，本方法也可以应用于系 统内有多个插座的情形。

插座理解为分别共享缓存或LLC的一组处理器内核。根据应用的方面， 不必只有一个可用的存储器缓存级别；往往存在这种缓存级别的层次结构。 最低级别缓存通常最小但最快，后随级别规模增大但缓存存取性能降低。

区域是绘制所要使用的图像空间的一部分。将区域分解成子区域或瓦 片。区域内的瓦片可以按任何顺序进行处理。一般而言，瓦片的大小没有限 制。优选地，各瓦片具有相同尺寸和矩形形状。

分解和/或分割是绘制所要使用的图像空间的细分。例如，图像可以初 始分解成两个区域，其中给各区域分配两个插座。一个初始区域可以是图像 的上半部，而第二个则是图像的下半部。术语“分割”主要用于后来的细分或 图像区域或子区域，优选为未绘制的以及具有绘制工作负荷留下的那些图像 区域或子区域。

序列的正向和反向标引的定义：设区域由数量为T的瓦片构成，其中 各瓦片具有相同尺寸。这样一个区域内的瓦片能按许多方式用瓦片位标i₀、 i₁、…i_T-2、i_T-1枚举为线性序列。可能的枚举方案的数量与一组位标的排列一 样多。假设选择了一种枚举序列，有两种可能选择来遍历此序列。第一选择 以i₀开始，然后通过增大位标逐步遍历此序列，第二选择以i_T-1开始，然后 通过减小位标逐步遍历此序列。下文中，增大的遍历方案称为“正向标引”， 而第二方案称为“反向标引”。

缓存对称瓦片枚举方案的定义：

如果其正向标引以及反向标引方案显示相同的缓存重用行为，则将枚举 方案定义为“缓存对称”。这意味着在序列的各方向遍历x个瓦片之后，平 均起来将达到相同量的缓存重用，必须对所有这样的x都满足。于是，这种 定义基本上意味着该方案在任何遍历方向都不比另一遍历方向更好。假设对 称负荷，完成瓦片的数量平均而言是相同的。

原子指令（atomic instruction）的定义：

原子指令是在阻塞（block）中处理的CPU指令，并且不会（被操作系 统）中断，因此，不需要锁定。当分析动态调度方案时，不得不在能使用原 子指令非常有效地实现为非阻塞（non-blocking）的算法与依赖于锁定的那 些算法之间进行区分。简单的动态方案具有的优点是它们能使用原子操作直 接实现。由Whitman（1994）提出的算法是几乎无锁定（nearly lock-free） 算法的示例。只是在分割区域时需要锁定，以避免其它处理器同时也执行这 样一种分割。没有在同一时间试图分割同一区域的其它所有线程都未被锁 定—保证锁定有较低的性能影响。根据本发明的方面，本方法是完全非阻塞 或至少几乎无锁定的。

上述方法的中心思想具有三个必要步骤：

1．将图像分解成具有多个瓦片的区域

2．给区域分配插座或成对的插座，用于绘制的目的

3．一旦计算完一个区域，搜索具有最大数量的未完成的瓦片的区域， 然后，分割剩余工作负荷，并且将所涉及的插座分配给两个新的或所创建的 子区域。

与Whitman（1994，参见上文）提出的方法相比，这种方法有许多额外 的自由度，因为：

-允许多个插座在一个区域上工作

-可以按任何顺序对瓦片进行处理

-分割操作是通用的，而没有限制要有具体的几何形式。

许多现有调度方法以考虑瓦片局部性的宏区域（macro region）（由一组 瓦片构成）开始（用于第一次迭代）-然后在没有任何宏瓦片可得到时开始 放松（loose）瓦片局部性，并且该阶段开始处理（“偷取（stolen）”）来自 其它宏瓦片的瓦片。在瓦片之间工作负荷差异非常大的情形下，宏瓦片可能 具有巨大的工作负荷不平衡。一些处理器非常早地完成初始阶段，于是开始 败坏局部性特性。相比于由[Whitman]提出的算法，本申请中所提出的方法 使用较少的分割操作，并且具有更好的缓存局部性参数。有利地，对于不均 匀的工作负荷，由于它们破坏了局部性（locality），本发明也最大限度地减 少了可能的分割操作数量。此外，使分割操作的影响最小化。

在一种实施例中，该内核（这些内核）是一种物理内核。在另一种实施 例中，该内核（这些内核）是一种逻辑或虚拟内核，例如，通过应用同步多 线程或超线程。

根据一种优选实施例，允许两个插座并行绘制一个区域。此外，在一种 多插座情形中，这些成对的插座并行处理它们的处理负荷，并且在一对插座 完成其工作的情况下，将该工作将重新分布。

按照又一种实施例，将该图像空间分解或分割成多个区域。优选地，这 只是在4个插座或多于4个插座情形中、并且只是如果一对线程已经完成而 另一对的瓦片仍未绘制时进行这种分解或分割。这些区域的数量应是插座数 量的至少一半。如果只有一个插座，这个插座在一个区域的多个瓦片上工作。 在2个插座情形下，2个插座处理用于单一区域的绘制指令。这是与上文描 述为现有技术的、由Whitman于1994年所提出的动态算法的一种主要区别。 另一种情形是4个插座情形，其中2个（各有两个插座的）插座对工作于两 个区域。在这种情况下，可能有几种简化，在具体描述中对此进行具体描述。 通常，使用偶数插座。在奇数情况下（不太可能），可以人为增加一个，并 且再次达到偶数情形。然后，一个插座从不做任何工作，并且，该区域仅由 分配给同一瓦片的另一插座进行处理。

根据本发明的一个方面，可以按任何顺序并且因此可以按相对于缓存重 用和对应局部性特性进行了优化的顺序在区域的这些瓦片上工作。因此，该 处理顺序是可配置的，并且还是动态可配置的。然而，对于瓦片枚举，也可 能使用一种静态方案。此外，有可能组合静态枚举与动态枚举方案。特别地， 有可能静态地枚举宏区域，并且动态地枚举这样一种宏区域内的瓦片，或者， 反之亦然（动态地枚举宏区域，并且静态地枚举该宏区域内的瓦片）。

在另一种实施例中，将待绘制的图像或体积存储成一种线性布局，例如， 作为一种线性切片阵列。替代实施方式涉及其它存储方案，例如，作为多个 小三维子块或层次化地，其中对混写的（swizzled）数据集的位标进行排列， 使得与线性存储器布置的情况相比，具有靠近位标的体素在三维空间中更靠 近在一起。当存取存储器时，在进行处理之前将线性布局的各体素位标转化 成其混写的位标（混写化）。重组待绘制数据，使得存储器存取能相对于缓 存局部性进行优化的另一方法已知为砌体（bricking）（例如，参见Parker等 人，1998，见上文）。

在又一种实施例中，分解和/或分割是基于一种分割方案，这种分割方 案基于用于检测多个可能分解或分割中哪一个具有最好缓存局部性特性的 度量f（B）。在这方面，必须注意，分解和/或分割并不局限于一种特定几何 形式，并且可以基于不同算法。这使该算法更加灵活。

根据本发明的另一方面，提供了一种装置，用于在具有一个或多个处理 器的共享存储系统上的图像绘制，其中，各处理器可以包括至少一个内核， 以及，其中，将一个或多个内核分配给至少一个缓存，并且可以并行计算至 少一个线程的指令，其中，将共享一个公用缓存的那些内核统一在一个插座 中，本装置包括：

-分解单元，使其适于把绘制所要使用的图像空间分解为多个区域，其 中，各区域包括多个瓦片；

-分配单元，其适于给所分解区域的每一个分配插座以用于绘制的目 的，其中，总是给一个区域分配两个插座;

-存储器单元，用于存储为区域所确定的瓦片枚举方案，其中，该瓦片 枚举方案包括用于瓦片计算的正向和对应反向标引；

-绘制单元，使其适于在所分配的插座上根据所确定的瓦片枚举方案绘 制区域内多个瓦片中的所有瓦片，直至完成各自区域；

-分割单元，如果其它区域中的瓦片仍然未绘制则该分割单元适于根据 分割方案将未绘制瓦片的区域分割成子区域，并且其适于存取存储单元以便 确定用于这些子区域的瓦片枚举方案和/或适于存取绘制单元以便重复地对 于这些子区域进行绘制，以及，如果完成了一个区域则该分割单元适于分配 该两个插座给另一个未绘制区域，以及，如果没有留下完全未绘制的区域， 该分割单元根据分割方案将具有未绘制瓦片的区域分割成子区域，并且其适 于对于这些子区域重复应用确定和/或绘制的这些步骤。

本装置可以涉及硬件，并且可以在多芯片模块（MCM）系统上实现。

下文中，具体描述本方法，假设将所要绘制的完整图像分解为不同区域， 各区域由瓦片组成。当有全部N个这种图像瓦片时，所有瓦片的集合可以 用以0开始直至N-1的位标枚举。全局图像映射函数允许将瓦片的位标转换 至能由绘制单元使用的实际瓦片信息——这意味着二维图像内的开始位置 和尺寸。区域内的瓦片位标总是全局位标，其具有的作用是，知道了瓦片位 标就全局性地完全指定了该瓦片。

给一个区域分配2个插座：

一般而言，允许一个以上插座在一个瓦片区域上工作。这背后的想法是， 如果可能给一个区域分配更多的插座——当然不用增加开销或者减少时间 或空间瓦片局部性——那么，有可能减少必要的分割次数，并因此改进由任 何分割操作所干扰的缓存效果。有可能给一个区域分配2个插座而没有减少 开销或缓存局部性。由于R个插座问题行为在许多方面与R/2个插座问题一 样，这允许减少将会发生的所要求的分割数量。

特殊情况：2个插座

与Whitman1994年提出的方法相反，只生成一个单一区域。两个插座 在该区域上并行工作——但是按照不需要任何分割的方式。

根据一种实施例，实现下列策略：

-创建单一区域的具有位标0、1、…N-1的瓦片枚举，该单一区域具 有如下特性：优化瓦片局部性、最小化缓存颠簸（cache thrashing）、并且是 缓存对称的。

-假设第一插座以正向标引方案开始绘制这些瓦片，而另一插座以反 向标引方案开始绘制这些瓦片。因为枚举的缓存对称特性，任何插座都没有 超过另一插座的固有性能优势。任何性能差异将只由计算这些瓦片时出现的 实际负荷差异引起。

-注意由两个插座绘制总共不超过N个瓦片。当最终绘制完最后一个 瓦片时，完成了该区域，并且这完全没有触发任何分割。

按照与1个插座的情形非常类似的方式，通过只使用原子操作，不要求 任何锁定，就能实现这种2个插座的方法。

有多种能实现这一点的方法。最简单的一种是对于已经处理过的瓦片的 数量使用图像瓦片计数器。在插座请求用于下一瓦片之前，对此变量使用原 子增加本征（intrinsic）。只在该本征小于等于N时继续在该瓦片上工作。

然而，这样一种方法没能很好地扩展到我们所要解决的一般插座情况， 因此，提供了可以扩展的下列方法：

设s1为第一插座的下一空闲瓦片的标引，同时，设s2为第二插座的下 一空闲瓦片的标引。设N为全部可用瓦片的总数。将这两个整数值存储成 64位整数变量；因而，低32位含有s1，而高32位含有N-1-s2。将上半部 反转，因而，能使用单一原子加（atomic add）操作来处理从第一插座以及 另一插座查询一个瓦片的情况。

在伪代码中，使用64位atomic_add操作，用于插座的下一空闲瓦片的 查询方法看起来可以是这样的：

一般插座情况

假设插座数目R是大于2的偶数。

将图像分解成至少R/2个区域，并且给每个区域分配2个插座，其中 一个区域内的每对插座行为都如同在2个插座的情况下那样。一个插座使用 正向标引开始处理或处置该区域内的瓦片，而另一插座使用反向标引。

完成一个区域后，搜索具有最大工作负荷留下的区域，然后，将此区域 分割成2个区域，然后，在分割之后，再次由两个插座处理各区域。这样完 成该分割，使得有工作负荷留下的该区域的2个插座（也称为成对插座）能 不受影响地继续它们的工作负荷，并且不失去瓦片局部性。因而，在按升序 分割之后，使用正向标引的插座能继续，而使用反向标引的插座也能继续。 这将一直继续，直至没有任何工作留下。

分割操作：

区域1：开始插座A1，结束插座B1——开始位标S1，结束位标E1

区域2：开始插座A2，结束插座B2，

假设区域2的工作运行完，而区域1有大部分瓦片留下，于是，我们进 行一次分割

->区域1：开始插座A1，结束插座A2——开始位标S1

->区域2：开始插座B2，结束插座B1——结束位标E1

只在有工作留下时，才进行该分割。在一次分割期间，重新计算瓦片位 标，因而，各得到的区域接收到半数的剩余瓦片。

因为该分割操作在2个插座的情况下不会发生，线程工作负荷处理不能 如2个插座情况那样简单处理。不过，这种情形通常也能几乎无锁定地实现。 然而，要求一种锁定来保护区域自身的分割，使得没有其它成对的插座能同 时分割一个区域。这种锁定只影响那些试图同时分割这个区域的线程。同样 地，该被分割区域的线程能继续在它们的瓦片上工作而不中断。另外，保证 了没有来自进行完工作的该插座的线程开始分割不同的区域。

相比于2个插座的情况，在一般情况下，需要存储更多的信息来描述一 个插座对。除了开始位标和结束位标，还有必要存储成对的插座ID（socket  IDs）。

于是，区域由下列数据进行描述：

-使用正向标引的插座ID

-使用反向标引的插座ID

-升序的下一空闲瓦片ID

-降序的下一空闲瓦片ID

当增加插座的数目时，需要更多比特来成对地存储插座ID。另一方面， 由于将该图像分解成更多区域，升序的瓦片ID与降序的瓦片ID之间最大的 可能差变小。为了节省比特，在另一数据结构变体中，考虑到了这一点：

由比特压缩方式存储的下列数据来描述区域：

-使用正向标引的插座ID

-使用反向标引的插座ID

-升序的下一空闲瓦片ID

-降序的下一空闲瓦片与升序的下一空闲瓦片ID之差。

将这种数据比特压缩成一种变量类型，其足够大并且能用原子操作 （atomic operation）进行处理——在这种情况下，使用64位的变量。取代使 用原子加操作，使用原子操作比较交换（COMPARE-AND-SWAP）（CAS）—— 即使另一线程当前在那个区域上执行位标变更或分割，原子比较交换也灵活 到足以检测到区域的变更。如果发生在该区域上的变更继续，则该线程考虑 这一点并再次尝试。这里的关键在于对描述一种区域的数据只执行原子操 作—这保证总是一致地描述一种区域。

在没有工作留下时的情况下，不得不搜索有最多工作留下的区域，并且 不得不触发该区域的分割。当一个区域需要被分割时使用一种锁定，使得想 要分割同一区域的其它那些插座不会冲突。还要保证没有来自运行完工作的 该插座的任何其它线程开始分割不同的区域。除这种特殊情形之外，只需要 原子操作—主要使用CAS指令。

与一般情况相比，对于4个插座的特殊情况，算法的有些部分可以简化。 这里，有可能实现该算法，而不必使用锁定，因此，以只使用原子操作的非 常有效的非锁定方案也能达到目的。

特殊情况：4个插座

4个插座的情况允许不同的简化，这主要源自只涉及两对区域的事实。 一种非常重要的简化是没有必要去搜索含有最大数量空闲瓦片的区域。由于 只有2个区域，当一个区域运行完工作时，余下的一个是仅有的能分割的区 域。另一简化是，不可能有2个不同的对同时试图分割第三对。与一般情况 相比，可能最重要的差异是，能在许多处理器架构上描述4个插座情况的整 个数据仍能在一个变量中描述，该变量只用原子操作就能进行修改。4个插 座实现依赖于128比特原子指令。

这里，低64位描述表示第一插座对的数据，而高64位描述第二插座对。 因为这种128原子操作，能用一个原子指令执行完全分割，保证这里不会出 现任何中断。这允许取消在一般情况下使用的锁定，并且简化其余代码，这 些代码在一般情况下必须能应对被中断的分割，这种被中断的分割中已经更 新了1个区域、而第二个却没有。

在伪代码中，我们用于查询下一瓦片的4个插座方法看起来像这样：

与在Do-While循环的开始处的初始128比特查询相比，如果修改了该 对之内的任何插座ID，则Update_SocketPair_using_atomic_64_CAS和 Split_data_using_128_CAS能使用CAS原子指令进行检测。如果检测到这样 一种插座ID变化，这意味着应用了一次或多次分割操作，则置位aRetry标 志，这将触发循环的重新开始。如果没有检测到插座ID的变化，则没有发 生分割，或已经发生了这样的多次分割，所述分割已经在所有对中导致相同 的插座分布。在后者情况下，只是修改了开始结束瓦片位标数据，这将由 CAS指令进行检测。

Update_SocketPair_using_atomic_64_CAS方法试图修改该插座对数据， 以及，如果成功，则置位返回的aTildID数据。只有在没有改变任何组件 （package）并且有实际要做的留下的工作的情况下，才进行这种修改。CAS 原子指令保证了，只在计算更新所依据的假设没有改变时才进行这一点。如 果只是改变了插座位标而没有重新分配任何插座，则更新该假设，并且再次 触发CAS更新。如果没有工作留下，该方法置位aSplitNecessary标志，以 触发分割。当分割被触发时，调用Split_data_using_128_CAS，其进行插座 对数据的再计算并且试图使用128位CAS指令来执行分割。只是在留下了 工作并且该对之内任何插座ID都没有改变时进行该分割。又一次地，CAS 原子指令保证了，只是计算分割所依据的假设没有改变才进行这一点。如果 只是改变了插座位标而没有改变任何插座ID，则更新该假设，并且再次触 发CAS更新。

由于只有能执行该分割的第一线程进行该分割操作，其余线程将检测已 经改变的插座对ID，并且触发了循环的完整重试用于这些线程，所以可以 调用本分割方法而无需使用锁定。

标引在区域内的瓦片

选择了瓦片枚举方案，因而，使跨越瓦片的缓存重用可能性得以优化， 而无需知道由瓦片绘制单元将要涉及的缓存线具体量的细节。因此，由于可 能只是利用从图像内的瓦片位置得到的非常一般的信息，这种缓存重用优化 问题不同于绘制瓦片时绘制器必须解决的那种。

然而，优化像素/体素访问的缓存重用的相同策略也将优化目前的宏瓦 片访问问题。当转移到目前问题时这些策略导致：

-平铺（tiling）：创建具有多个瓦片的宏瓦片，这些瓦片足够小，因而， 缓存局部性效应是可能的

-混写（swizzling）：在宏瓦片中存储多个瓦片，所述宏瓦片由更小的 宏瓦片重复构成

-Hilbert曲线：存储使用由Hibert曲线所限定的标引方案的瓦片。

假设在这些瓦片内完成了体积绘制，周知当该体积存储为线性切片阵列 时视见体积的取向能强烈影响缓存行为。由于这种线性存储格式很常见，对 此加以考虑。

根据本申请的一方面，产生了一种优化动态瓦片枚举方案，其为每一帧 重新排列这些瓦片。该动态瓦片排列满足瓦片局部性，并且还通过利用体积 取向进一步降低了缓存颠簸。

当由按正向和反向顺序位标所标识的瓦片进行排列，使得它们全部点对 称或轴对称时，实现了缓存对称。这意味着有一种自对称，其映射成在各方 向遍历彼此相同数量位标后得到的位标。

为按线性格式存储的体积动态优化地缓存重用的瓦片枚举

如上所述，当对存储体积为线性层面阵列的体积数据格式进行体积绘制 时，体积相对于观察照相机的取向强烈影响体积绘制器的缓存行为。

对于在规则格网上计算体积样本，例如，在使用正交投影体积绘制情况 下满足规则格网要求，在美国专利2011/0170756中提出了一种允许克服这 一问题的算法。在三维规则格网内的三维块体的情况下，示出如何找到一种 采样位置的排列，当按照由该排列限定的顺序采样体积体素时，该排列使缓 存重用得到优化。在美国专利2011/0170756中，该算法基于一种采样存取 模式，其允许最优地存取n维体积的立方体。将这种存取模式进行修改，以 将其用作一种枚举方案，用于产生区域内的瓦片序列。

对于该网格内具有尺寸（2^X，2^Y，2^Z）的块体B，限定一种重复细分方 案，其中对于3种可能细分的每一个都应用一种测度函数，其具有测量由细 分所得到的哪个子块对于采样最为缓存友好的性质。结果，建立3元数，其 唯一地描述优化缓存重用的块细分序列。这里的想法是，在线性存储体积的 情况下，当获取体积数据时，缓存中大量的相邻体素在体素空间中具有相同 的y-z坐标。利用这种特性，提出了一种度量（metric），其基于这样的想法， 使用将所有触及体素投影到体素空间中y-z坐标平面的面积。

设T为仿射变换，其映射坐标系统，其中将规则网格限定成体素空间。 设P是投影算子，其将体素空间投影到y-z平面，于是，用于平均缓存测量 函数f(B)的公式可以明确表达为：

f(B)=|p_x×p_y|+|p_x×p_z|+|p_y×p_z|+1.72(|p_x|+|P_y|+|p_z|)。

这里，向量p_x、p_y和p_z通过将P施加至由块B所描述的平行六面体的 边缘而得到。

在目前情况下，不必沿规则格网来采样体积，但需要找到遍历瓦片用的 序列。在各瓦片内，已知通过进行体积绘制来存取体积数据；不做任何其他 特殊假设。如果该体积绘制单元使用正投影，则可以延伸美国专利 2011/0170756中所提出的原则想法，使其能应用于目前问题：

设t_x和t_y是描述瓦片的二维向量，并且设t_z是与照相机的观察方向平行 的任意向量。假设这些向量形成块体B，并假设在这样的块体中将发生规则 网格采样。在这样的情况下，可以使用上文的度量，其中，向量p_x、p_y和 p_z由施加投影算子P至t_x、t_y和t_z而得到。

由于目前情况涉及一种宏观设置，其中相比于体素尺寸，向量t_x、t_y和 t_z较大，而相比于表达式中的其余部分，项1.72(|p_x|+|P_y|+|p_z|)较小。对 于宏观问题组合（constellation），可以简化该项而得到：

f(B)=|p_x×p_y|+|p_x×p_z|+|p_y×p_z|。

应当使用这种度量来判断向量t_x或t_y的长度是否应减半。对于这种操 作，两种情形下的第一项都给出了相同结果，因而，可以将该度量进一步简 化到：

f(B)=|p_x×p_z|+|p_y×p_z|。

只要向量P_z具有非零长度，则可以将这个表达式写为：

f(B)=|p_z|（|p_x×e_z|+|p_y×e_z|）。

这里，e_z是P_z的单位长度向量。再一次地，这里项|p_z|与应当在其上应 用的度量的操作不相关。这再次导致该简化表达式，并且最终得到：

（1）   f(B)=|p_x×e_z|+|p_y×e_z|。

在该情况下，|p_z|是零，因此|e_z|不存在，度量f（B）为零，表示在这 种特殊情况下，出于度量观点，两种可能分割都没有任何优点。

在这最后的度量f（B）中，沿观察方向上块体的长度不存在，仅观察 方向和跨越该瓦片的投影具有影响。由于沿观察方向的这种独立性，这种度 量极为适用于当前目的。所以，如下文中所述，使用这种度量，以导出一种 视点独立的二进制瓦片细分方案。

定义（二进制瓦片细分）：

假设有一个矩形区域，其由全部具有相同尺寸的瓦片构成。设x方向的 瓦片数为2_x，以及y方向的瓦片数为2_y。让我们以数字0标识使用x方向线 进行对分的瓦片，并且以数字1标识使用y方向线进行对分的瓦片。使用这 种标识，有可能重复地细分这种区域的瓦片，直至达到单一瓦片。该细分方 案能用二进制数加以描述。

所有这种二进制细分方案的集合由具有（x+y）位数字的全部二进制数 的集合描述，其中，数位0出现x次，而数位1出现y次。

已经定义了一种度量，其允许决定矩形区域的哪次分割导致平均触及较 少缓存行（cache lines）的区域，现在有可能描述一种动态瓦片细分方案， 其数学上类似于美国专利2011/0170756中所描述的规则格网内块体的体积 采样方案，但对于宏观情形其只能利用瓦片局部性信息。

动态瓦片细分

当细分图像区域时，我们计算2个可能细分中哪一个导致较小的度量 值。然后，选择建立较小度量值的那一种细分。通过重复地进行这种决策步 骤，我们得出描述该细分方案的一个二进制数。各细分方案导致开始区域内 这些瓦片的不同枚举。在两个细分导致相同度量值（使用大于零的正数，其 描述我们认为度量相同时的情况）的情况下，我们计数这种情况，以及，对 于奇数计数使用数位0，而对于偶数我们使用数位1。

静态瓦片细分

当能够定义一种动态细分方案时，类似于美国专利2011/0170756，然后， 也能定义一种细分方案，其对描述细分方案的二进制数的数位进行预定义。 一种周知的静态细分方案，当描述小区域时由交替的数位0和1进行描述， 然后，取决于矩形区域的哪一边较大，用0或1填充其余数位。

静态细分是一般混写（swizzling）方案的一种特殊情况，其具有优异局 部性特性。

在向量|e_z|不存在的情况下，二者瓦片细分步骤导致相同的度量。对于 度量相同的该特殊情况我们增加的计数修改，在那种情况下导致静态细分方 案。在度量没有给出清楚提示哪个细分更为缓存友好的那些情况下，这保证 了局部性是优选的。

动态方案和静态方案也能以混合组合的形式进行使用，例如，描述达到 插座内线程数的最小行为的数位使用静态方法，而对于其余数位则使用动态 方法。在这一方面，不得不指出，也能将静态瓦片细分用于正投影以及透视 投影。

到目前为止，已假设这些图像区域是矩形的，并且在x方向和y方向具 有2的乘方的瓦片数。在一般情况下不是这种情况时，以下列直接修改建立 枚举：

-为满足2的乘方特性并且含有给定任意区域的所有区域中的最小区 域建立枚举E

-通过除去属于那些不属于该区域的瓦片的所有位标，由枚举Ｅ建立一 种新的枚举。然后，可以除去枚举中的那些空洞，以再次得到一种位标序列。

下文中，对描述有R个插座时情况所用的算法进行总结：

-预定义一种具有良好局部性特性的瓦片枚举方案，其允许枚举图像中 的所有瓦片。如果应当利用体积取向特性以便为特殊取向获得额外的缓存益 处，则使用动态方案。在所有其它情况下，静态细分方案导致对于平均取向 来说不远离动态方案的性能结果。可选择地，也能使用具有良好局部性特性 的其它枚举方案，例如，使用由Hilbert曲线得到的枚举方案。

-创建将该图像分解成R/2个区域的初始分解；这一点通过将瓦片枚举 位标分解成具有相同瓦片数的R/2子集可以实现。

-当一个线程准备好绘制瓦片时，检查该线程当前运行于哪个插座上， 然后，根据我们提出的动态负荷平衡算法，查询用于此插座的下一瓦片。动 态算法关心分配给不同插座的那些瓦片彼此具有最小的冲突，同时，对根据 相同插座的线程所查询到的那些瓦片的缓存重用进行优化。同等地进行处理 所有属于相同处理器插座的线程，这里没有任何区别——只是使用线程运行 所在哪个组件（package）上的信息。

-当完成一个区域时，对具有最多工作留下的区域执行分割并且继续。

然后，体积绘制算法接收由该瓦片描述了图像哪个部分的信息，并且计 算图像的那个部分。对于瓦片内进行的体积绘制的种类、以及内部应用了什 么策略来优化性能（只是对于动态瓦片枚举方案假设了一种正投影；对于透 视取向，使用静态方案或Hilbert曲线实现最好结果）没有限制。然而，已 知这种算法不得不触及体积数据来计算样本，以及一些缓存行将以足够大缓 存留在处理器上的末级缓存中。

如果多个线程没有被锁定，其有助于为各瓦片查询该线程属于哪个插 座，由于该线程可能被操作系统动态重定位至另一处理器组件。如果多个线 程被锁定于内核，这只要在初始做一次。

然而，在windows操作系统实现中，注意到确定该插座的查询具有非 常低的开销，并且，重定位至不同插座只是非常罕见地发生，因而，不必锁 定这些绘制线程。

实现的性能提升很大程度上取决于具体LLC大小和插座数目。在具有 双插座结构的最新的服务器处理器上（例如，在英特尔开发的微架构如Sandy  Bridge上），与在插座之间没有差异的动态方法相比，我们已经看到了近10 ％的整体性能提升。由于LLC缓存将随着即将到来的处理器中的内核数量 而继续增加，我们的算法在这种未来系统上将产生更令人印象深刻的性能结 果。

修改算法成为一种适应性分解方案

到目前为止给出的本算法都是一种动态瓦片分解算法，其不是适应性 的。然而，本算法可以进行修改，以成为一种适应性算法。

假设对于每个瓦片，提供数量c_i，其描述绘制该瓦片必须的预期工作负 荷。这样的数量可能这样得到，例如，使用交互作用期间来自末帧的各瓦片 的工作负荷，或者使用瓦片内预期采样位置的数量，或者使用由现有适应性 算法所使用的任何其它技术。一旦对于各瓦片能得到这样一种数量，能以2 种方式使用这种数据来修改我们的算法：

-使用这些瓦片的预期工作负荷来建立初始区域，其具有的性质是将它 们瓦片工作负荷的总和平均分布在这些区域上。

-进行分割操作时使用预期瓦片工作负荷数量。我们已经提出的分割假 设所有瓦片具有大致相同的工作负荷，因此该分割操作将均等地分割刚好瓦 片的数量。当工作负荷数量可得到时，我们能修改该分割，使得工作负荷总 和均等地分配，而不是按瓦片的数量分配。

这种修改允许（一般来说）使能发生的发生分割的数量进一步最小化。 由于因为2个插座的情况是无需分割的并且由此适应性分割不再带来任何 好处，所以这种适应性修改应当只用于插座的数量大于2的情况。当然，适 应性修改引起了一些额外开销，因而，只在能非常有效地得到预期工作负荷 数量时，适应性变体才是有意义的。

一般而言，上述方法可以在软件或计算机代码中实现，以在计算机上执 行。可选择地，该方法可以在图形处理单元（GPU）或与软件模块组合的硬 件模块中实现。于是，硬件模块适于执行上述的本方法的步骤的功能。据此， 也可能有硬件和软件模块的组合。这些模块优选地集成进现有的以计算机为 基础的医学环境。

本发明的另一方面在可加载进计算机存储器内的计算机程序中看到，其 中该计算机程序适于执行如上所述的本方法的步骤。

此外，本发明涉及一种包括程序指令的计算机可读介质，由计算机系统 的处理器执行这些程序指令时，促使该处理器在如上所述的具有一个或多个 处理器的共享存储器系统上执行用于图像绘制的本方法。

附图说明

附图示出了根据特定实施方式的本发明的原理。因此，按其它实施方式 也能实现本发明，因而，这些附图仅仅解释为示例。此外，这些附图中，相 同的附图标记在不同附图中都表示对应的模块或零件。

图1是根据用于体积绘制的计算机实现的医学系统的一种实施例的示 意性框图；

图2是根据具有多个处理器、包括多内核处理器的绘制系统的一种实施 例的示意图；

图3是具有多个内核的多内核处理器的示意图，所述内核被分配给一个 区域的瓦片；

图4是描述与瓦片尺寸相关的总体系统性能的图；

图5是由多个枚举瓦片构成的应当绘制的区域的示意图；

图6示出线性瓦片枚举方案的示例性图示；

图7示出基于Hilbert曲线的瓦片枚举方案的示例性图示；

图8示出基于静态细分的瓦片枚举方案的示例性图示；

图9示出具有6种可能结果的动态细分方案的示例性图示；

图10是2个插座系统上的动态瓦片分解方案的示例性图示；

图11是4个插座系统上的动态瓦片分解方案的示例性图示；

图12是用于2个插座瓦片分布情形（示于右侧）的结果绘制图像（示 于左侧）的示例性图示；

图13是用于4个插座瓦片分布情形（示于右侧）的结果绘制图像（示 于左侧）的示例性图示；以及

图14是一种根据本发明优选实施例的流程图。

具体实施方式

参照图1，描述了一种体积绘制系统，其包括图像采集系统，如CT系 统或MRT系统等，所述图像采集系统在图1中用附图标记CT示出。将模 态（modality）通过网络NW与服务器系统相耦合，以用于要显示在监视器 M上的图像或体积绘制。

图2示出了一种绘制系统10，其包括若干处理器P₁、P₂、...P_n。通常， 各处理器P可以包括一个或多个处理器内核C₁、C₂、...C_n，因此，将其称 为多核系统。每个内核C对缓存12或具有几个有着不同存取性能的缓存12 的缓存层次结构进行存取。随着多核处理器变得普遍以及片上（on-die）内 核数量的增加，关键的处理器设计问题是在考虑到高效缓存层次结构的情况 下用于片上末级缓存LLC的以及因此用于算法的层次结构和策略，以减少 片外数据失误（miss），并提供快速存储器存取。末级缓存LLC可以按照围 绕可扩展片上互连的分布方式进行组织。末级缓存可以是私有的或由内核C 共享。绘制系统10包括几个单元、或者与几个单元相互作用，这些单元可 以实现为硬件：分解单元D、分配单元A、存储器MEM、绘制单元RU、以 及分割单元SU。上述这些单元适于执行对应方法的步骤，并可以将它们实 现为片上模块。

本发明涉及体积绘制，并且基于图像空间分解的范畴，其中将用于绘制 所得到图像的图像空间分解为多个瓦片T。

一般而言，当进行体积绘制时，图像瓦片大小影响整体积绘制时间。许 多因素影响性能，一些因素受益于较小的瓦片，另一些因素则受益于较大的 瓦片。总体上，当分析瓦片尺寸如何影响性能时，通常可以参考图4中所示 的性能图。结果，可以选择给出整体最好性能结果的瓦片尺寸，在图4中所 示的示例中，将选择8×8像素的瓦片尺寸。

现代处理器的LLC规模增大只是影响图4中性能图的众多因素之一。 因此，增大瓦片尺寸并不是一种允许充分利用存在的大规模末级缓存LLC 的解决方案。所以，可以看出，根据本发明一种优选实施例的方法的主要优 点在于，能独立于所选择的、显现瓦片体积绘制器的最佳性能的瓦片尺寸来 使用算法。这一事实允许独立地选择瓦片尺寸，以优化体积绘制性能，并且， 从宏观角度允许本算法充分利用大规模LLC缓存。

根据本发明的一种实施例，各处理器P包括存取末级缓存LLC的几个 内核C。通常，这些缓存LLC中的至少一个在几个内核C之间共享。这示 于图3中，其中，末级缓存LLC至内核C的分配由各自连接线表示。共享 一个单一末级缓存LLC的那些内核C定义为插座S。在图3示意性示出的 示例中，内核C₁具有私有LLC，内核C₂、C₃共享第二LLC，内核C₄、C₅、 C₆共享第三LLC，而内核C₇、C₈共享第四LLC。据此，形成四个插座：S₁、 S₂、S₃、S₄，这可以表示为：R=4，其中，R是插座S的数量。根据本发明 的一种实施例，将图像空间分解为插座数量的一半，也就是，分成R/2个区 域。将各区域Re分配给一对插座（两个插座），以便绘制在该区域Re中的 瓦片T。这在图3中由插座S与宏区域MR内的相应的区域Re之间的连接 线来描绘。宏区域具有矩形形状，并且将其分解成上半部Re₁和下半部Re₂。 在图3所示的示例中，将上半部分配给插座S₁、S₂，而下半部则分配给其余 插座S₃、S₄。所分配的区域在图3中示为阴影区域。

在2个插座方案的情况下，只有一个单一区域Re，并且没有任何分割。

图5举例方式示出一个区域Re，该区域应当被绘制，并且将其分解成 64个瓦片T，其中各瓦片T由像素矩形构成，选择这些像素矩形以便具有允 许计算该瓦片T的体积绘制器达到最佳性能（瓦片边缘尺寸不必是2的乘方） 的尺寸。

忽略限定这些瓦片尺寸的像素矩形的大小，但考虑形成区域Re的瓦片 T的集合。图5中的各方块是区域Re所分解成的瓦片T中的一个。以范围 从1至64的位标来枚举瓦片T，并且这种枚举限定按哪种顺序绘制这些瓦 片T。在本示例中，按扫描线次序线性地枚举这些瓦片T，这是在现有瓦片 分解算法中使用的典型枚举。如果缓存影响可以被忽略，这些瓦片T在我们 的方案中可以按任意次序进行处理，而在整体积绘制性能方面没有显著差 异。然而，对于即将到来的具有大规模LLC的新处理器而言，情况不再是 这样。

由于缺乏局部性特性，线性扫描线枚举将无法达到最佳的缓存重用。通 常，在瓦片T的绘制期间，各瓦片在这样一种情况下仅有2个足够近的要处 理的瓦片以便受益于留在LLC中的数据。

就图6、图7和8而论，描述了简单4×4瓦片区域的一些可能的瓦片枚 举方案。在图6至图8所示的这些示例中，可以看出，这些方法如何能用来 建立标引方案。

图6涉及一种线性扫描线枚举。图7涉及由Hilbert曲线限定的枚举。 图8示出如由使用二进制数“1010”的静态分解所限定的枚举，其中首先将瓦 片区域首先沿y方向、然后在x方向上重复地对分。

如可以看到的那样，Hilbert曲线枚举形成了一种曲线，其在这组所有 瓦片T上从未间断。静态细分具有良好特性，所有细分区域有许多自相似性。

如可以看到的那样，所有3种枚举方案在正向标引与反向标引之间满足 对称性条件。线性和静态细分枚举是点对称，而Hilbert曲线枚举是沿y轴 的轴对称。在所有情况下，正向和反向标引遍历针对其它遍历都没有固有优 点。

下面相对于图9描述一种动态细分方案。一般而言，细分方案可以由二 进制数进行描述，如在表示瓦片T的4×4场下面可以看到的二进制数。

这种方案考虑了体积相对于观察照相机的取向，以便将体积存储为线性 切片阵列。假设初始区域包括16个瓦片T，它们以4×4方式排列，对于一 种动态分解，有6种可能结果，示于图9中。

由根据本发明一种实施例的决策度量f（B）来限定，针对具体情形事 实上将建立哪种可能细分（注意：细分解释为通用术语，用于分割和分解图 像面积）方案。通过评估关于两种可能分解的每一个的度量，我们得到指示 分割结果变得如何缓存友好的测量结果，因而，我们决定来选择更为缓存友 好的。第一分割决定了由位标0-7和8-19所限定区域的形式，其余分割通过 对分瓦片区域来重复地限定其余位标。

关于图10和图11中所示的示例，示出涉及多个插座S上多个处理器P 的情况，于是，瓦片局部性只是在相邻瓦片T都由相同插座S处理时提高缓 存重用。否则，瓦片T不共享共用的LLC，因此不会受益。在图10所示的 示例中，示出2个插座系统上的一种典型动态瓦片分解方案。图11表示4 个插座系统，其中进行动态负荷平衡，而没有考虑瓦片局部性。

在图10和图11所示的这种示例中，由相同插座S处理的瓦片T按相 同方式加阴影或影线。由于在各插座S上有多核处理器P，给各插座S分配 多个线程。

如可以看到的那样，由于仅具有相同阴影或加重的瓦片T有机会，而 且，仅仅如果它们还在序列内靠得足够近，所以，几乎没有任何缓存重用。 所涉及插座S的数量越多，任何缓存重用将会发生的机会越少。

如上所述，与增大的LLC规模相结合，现代处理器具有增加数量的内 核C。LLC越大，被缓存数据——主要是体积数据——越可能仍然存在于 LLC中。所以，设计目标是，所得到的动态瓦片调度方案不得不关心驻留在 相同物理处理器插座S上的线程具有大的瓦片局部性。这里考虑了不同点：

-处理相同插座S上具有优化局部性特性的瓦片T。

-体积存储格式能影响局部性特性。

-在多插座系统上注意该局部性不被与其它插座S的冲突而破坏。

图12示出了使用根据本发明优选实施例的算法时关于2个插座情形用 动态瓦片分解所得到的图像（示于图12左侧）的示例。该2个插座瓦片分 布示于图12中右手侧。这里没有进行适应性分解修改，只有上文所述的动 态瓦片分解。如可以看到的那样，在本示例中，工作负荷在瓦片T上非常不 同地分布。绘制头盖骨的大多数瓦片T涉及（hit）骨头，并且能很大程度受 益于早期射线终止（termination），同时，例如，绘制头盖骨下方组织的瓦片 T，由于它们要处理透明的部分，则更是具有高要求。

如可以看到的那样，本算法良好地适应工作负荷差异，而不必使用适应 性技术。由于没有发生任何分割，该2插座算法找到了关于该问题的最优解 决方案。

图13示出了使用上面给出的算法时关于4个插座情形用动态瓦片分解 （示于右侧）所得到图像（示于图13中左侧）的示例。这里没有做任何适 应性分解修改。这里所绘制的图像与2个插座示例中的一样。

如已经说明的那样，根据一种优选实施例，只在有工作留下（未绘制的 瓦片）时才进行分割。在分割期间，重新计算瓦片的位标，使得各得到的区 域接纳一半数量的余留瓦片（参见图13）。

在该情形下，如图13中示，图像最初分解成两个区域Re，其中给各区 域Re分配两个插座S。一个初始区域是图像的上半部（分配了右斜条纹和 左斜条纹插座S），而第二个区域是图像的下半部（分配了水平条纹和竖直 条纹的着色插座）。由于上区能更快地计算，这对插座S较早完成，并且触 发下区的分割。竖直条纹和水平条纹插座S能不受影响地继续，而右斜条纹 和左斜条纹插座则开始新工作。稍后，由水平条纹和右斜条纹限定的一对插 座S较早完成，并且分割余留区域。最后，一个区域再次较早完成，并触发 最后分割。总体来说这里只发生3个分割，说明本算法如何极好地能自动处 理大图形工作负荷差异——即使没有应用另外的适应性技术。当然，也能另 外应用适应性技术，如果插座S的数量大于2，带来的效果是将另外减少发 生分割的整体数量。采用考虑了瓦片T预期工作负荷的适应性技术，将使用 该信息来建立其他初始区域Re，并且进行分割，使得预期工作负荷均匀地 分布，并且不是如本示例那样的瓦片T的数量。

参照图14，描述了根据本发明优选实施例的一种流程图。本方法可以 分成两个时间段：配置段，其主要可以用来定义一种枚举方案；以及绘制段， 将其用于绘制。系统开始之后，在步骤100中预定义瓦片枚举方案。

在步骤105中，给宏区域MR分配一对插座S。

在步骤110中，在R/2个区域Re中，建立具有相同数量瓦片T的图像 的初始分解。

在步骤120中，由所分配的成对插座S绘制所分解的宏区域MR的瓦 片T。

在步骤130中，有一个查询：当线程准备好绘制瓦片T时，检查该线 程目前在哪个插座S上运行，然后：

在步骤130中：根据动态负荷平衡算法，查询用于此插座S的下一瓦片 T。该动态算法关心分配给不同插座S的瓦片T相互间具有最少冲突，同时， 使具有由相同插座的线程所查询的瓦片的缓存重用得以优化。属于相同的处 理器插座S的所有线程都均等处理，这里没有任何区别——仅仅使用线程 在哪个组件上运行的信息。

步骤140：检查，是否完全绘制了一个区域Re。当完成了一个区域Re 时，然后进行至步骤150。否则，回到步骤130。

步骤150：对具有最多工作留下的区域Re的分割执行并且继续。然后， 体积绘制算法接收由该瓦片描述图像的哪个部分的信息，并且计算该图像的 那个部分。

在步骤160中，分析是否完全绘制了该图像。如果是，本方法结束。否 则，回到步骤130。

本发明显示了以下几个优点：

与用于瓦片的现有动态负荷平衡算法相比，所提出的方法具有的优点在 于，它允许充分利用近些年来出现的现代硬件中的LLC增加。这保证了计 算属于相同插座S的瓦片T，使得LLC重用得到优化。在多插座情况下， 本算法另外关心各插座S最大限度地减少其对其它插座S的缓存行为的影 响。由于多核处理器中内核C的数量将稳步增加，并且因此典型地LLC规 模也将稳步增加，这种算法的性能优势将继续随未来硬件而稳步提高。

动态瓦片枚举方案允许运行中充分利用存储为线性切片阵列的体积的 取向，以进一步优化缓存重用。这种枚举方案几乎没有任何开销，并且能容 易地动态应用。

对于高达4个插座的系统，尤其高效的实现是可能的，其为使用原子指 令的非阻塞（non-blocking）。由于关键步骤——区域分割——是由原子指令 处理的，所以这些实现在极端情形下也是非常有效的。分割没有任何可能被 操作系统中断。此外，由于触发分割的插座对的所有线程都能做分割，保证 该分割导致最少的开销。由于2个和4个插座系统是目前最常见的多插座系 统，在实践中能经常应用这些特殊情况。

在一般插座（>4）的情况下，本算法使阻塞的影响最小化，由于这里 只是为了保护分割而要求锁定，但是对于所有其它情况都未触及。以及，由 于我们算法的设计，分隔状态是罕见的。

在2个插座的情况下，本算法完美解决了给出的问题，因为这里可能没 有任何分割。

本算法R->R/2的复杂性降低特性，出于许多观点都允许将一种R插 座系统转换为一种R/2系统。

本算法非常适合平消除由图像内具有非常不规则负荷分布引起的影响， 对于体积绘制这是经常的情况，其中不透明和透明的区域可能在复杂图案中 交错。它很少取决于算法开始时所分配的初始工作负荷（瓦片T的数量）的 良好近似（特别在适应性情况下）。

虽然本算法设计用于体积绘制应用，但它足够通用以在类似情形中使 用，这些类似情形下在多插座系统上的瓦片间不得不优化缓存重用。对于更 加通用的绘制问题，这也会是有益的。

最后，本发明可以概括如下：

提供了一种用于图像瓦片负荷平衡的计算机实现的方法，其极为适于在 通用多插座系统上对用于体积绘制应用的跨越瓦片的缓存重用进行优化。本 方法是一种动态方案，即使在图像内的工作负荷以较大差异分布的情况下， 这种动态方案也以与其它插座S的最小冲突保证各插座S达到优化缓存重 用。本算法能非常有效地实现，这保证了线程的开销最小。对于2个插座的 情况，本方法可以实现为仅仅使用一个单一原子操作的非阻塞算法。

提供了一种度量f（B），其允许在体积存储为线性切片阵列的情况下检 测两种可能的瓦片细分的哪一个对于体积绘制更为缓存友好。只要求该瓦片 的大小、观察方向、以及该体积相对于观察照相机的取向作为输入参数。该 照相机是一种正交相机（对于动态情况）。

提供了一种动态算法，其使用度量f（B）以找到瓦片T的一种枚举， 对于存储为线性切片阵列的瓦片，这种枚举允许对跨越瓦片的缓存重用进行 优化。

产生了一种用于区域标引序列的静态瓦片枚举方案，其极为适合于优化 处理器内的缓存重用。这种静态方案在区域的x轴与y轴之间重复地交替分 割。在本静态情况下，照相机可以是正交的或透视的。

产生了一种用于区域标引序列的瓦片枚举方案，其极为适合于使用 Hilbert曲线优化处理器内的缓存重用。

提供了一种用于一对插座的存储格式，其非常适合于原子指令使用。还 示出如何优化这种存储格式以最大限度地减小所需的比特数。

提供了一种使用原子指令的2个及4个插座情况的非常有效的非阻塞实 现。

示出了如果修改本算法，使其成为适应性分解方案。使用预期工作负荷 数量来建立具有相等工作负荷的初始区域，并且进一步使用预期工作负荷数 量来建立分割，这些分割建立具有相等工作负荷的子区域。

示例实施方式在所有方面都应当示为说明性的而非限制性的。所以，本 发明的范围由所附权利要求而不是这里的描述限定。所以，在该权利要求的 等效置换的含义及范围内的所有变化都包含在本发明的范围内。