文摘

扩散张量成像(DTI)允许动物纤维组织测量水的扩散。通过重建纤维使用fiber-tracking从DTI数据算法,我们可以推断出的结构组织。在本文中,我们提出了一个方法来加速这种fiber-tracking算法使用图形处理单元(GPU)。这个算法,它是基于测地线的计算,表明合成和真实数据的有前景的结果,但有限的适用性高计算需求。我们提出一个解决方案,使用现代gpu的并行性,结合NVIDIA的CUDA平台,大大降低fiber-tracking算法的执行时间。相比一个多线程CPU实现相同的算法,我们的GPU映射达到40倍的加速因子。

1。介绍

Diffusion-Weighted成像(驾车)是最近,无创性磁共振成像(MRI)技术,允许用户在一个给定的测量水分子的扩散方向。扩散张量成像(DTI) (1]介绍了扩散测量与醉酒驾车是一个二阶张量。酒后驾驶工作的知识扩散的水分子在生物组织是受组织的微观结构的影响。布朗运动的理论规定统一的体积内分子的水将随机散射到各个方向,即扩散各向同性。然而,在对象的存在阻碍水的扩散在某些特定的方向,扩散就会越好各向异性。在纤维组织,水的扩散将是大的方向平行于纤维和小型垂直方向。因此,酒后驾驶数据用于推断和分析纤维组织的结构,如大脑的白质和心脏肌肉组织。醉酒驾车的数据已被应用在规划阶段的神经外科(2),在诊断和治疗某些疾病,如阿尔茨海默病(3),多发性硬化(4),和中风5]。白质的自组织宏观上均匀,其他成像技术,如t2加权MRI无法检测底层纤维的结构,使酒后驾驶白质的独一无二的适合体内检查。

使用测量扩散的过程中重建底层纤维结构被称为纤维跟踪。许多不同的纤维跟踪算法的引入DTI以来已经开发出来。本文构造一个纤维的方法通过寻找测地线在黎曼流形的定义的唯一数据。这种技术叫做[测地线的演6,7),比其他的有几个优点,比如它对测量噪声的敏感性相对较低,两点之间及其识别多个解决方案的能力,这使得它适用于复杂结构的分析。

该算法的一个最大的缺点是计算量大。我们的目标是要解决这个问题通过测地线的演算法映射到高度并行体系结构的图形处理单元(GPU),使用CUDA编程语言。由于纤维可以是彼此独立的,计算测地线的演算法可以有效地并行化。结果,可以减少运行时间高达40倍,比一个多线程CPU实现。本文描述了CUDA实现的结构,以及相关的设计考虑。

在下一节中,我们讨论相关背景理论方法,包括贸易工业部和测地线的演算法。接下来,我们给过去的相关研究概述了基于gpu加速的纤维跟踪算法。节4测地线的演算法的实现,讨论了使用CUDA GPU。接下来,我们给基准测试结果和优化策略的CUDA实现部分5,紧随其后的是一个讨论的结果部分6,和结论部分7。

2。背景

2.1。扩散张量成像

DTI允许我们重建白质的连接,从而使我们更加深刻的理解大脑的结构。表演醉酒驾车为多个不同的方向后,我们可以使用一个二阶张量模型的扩散过程(1,8]。是一个3×3正定张量,它可以可视化作为一个椭球由其特征向量和特征值,如图1。使用张量的特征值,我们可以量化的水平各向异性各向异性的措施(9,10]。地区的接近各向同性扩散张量椭圆体近球形,和各向异性测量值低,而地区的高度各向异性扩散(由于纤维的存在),将夏普和细长的椭圆体,和各向异性值将会很高。在各向异性的地区,最大的特征值对应的特征向量(主要特征向量)将显示纤维结构的方向。

2.2。纤维跟踪算法

DTI纤维跟踪数字重建路径的过程中纤维在纤维组织利用DTI张量数据,目的是推断的结构组织。纤维跟踪的一种常见方法是跟踪线从一个或多个种子点,使用一组微分方程。最直接的纤维跟踪算法(通常称为简化方法)使用与当地主要特征向量的方向取向的纤维12]。因此,生物组织的纤维可能被集成的主要特征向量重建,使用一个常微分方程(ODE)求解欧拉方法等。图2说明了扩散张量之间的关系和由此产生的纤维轨迹。纤维跟踪算法基于这种方法已被证明实现可接受的结果(13,14),但被限制在其准确性高灵敏度噪声和部分体积效应(15,16]。

经典优化方法的局限性一个可能的解决方案是使用一个全局极小化的解决方案,例如,一个front-propagation方法。在这种方法中,前面是传播从一颗种子点在整个体积(17- - - - - -19]。前面的地方传播速度取决于DTI图像的特点,构造和纤维back-tracing通过前面的特点。这些front-propagation方法的一个子集,利用测地线的理论找到潜在的纤维连接(19- - - - - -21]。这些算法通常计算测地线(定义为最短路径通过tensor-warped空间)通过求解静止哈密顿雅可比方程(HJ)。测地线算法已被证明产生好结果,通常是更健壮的噪音比简单的简化方法。然而,一个缺点是,他们通常只找到一个可能的目标区域之间的联系,这通常是不正确的解决方案在非常复杂的地区。此外,研究表明有可能有多个区域的白质纤维联系(22]。

2.3。测地线的演

本文的重点是一个相对较新的基于测地线的纤维跟踪算法,所提出的Sepasian et al。6,7]。该算法的主要优势,相比前一节中所讨论的,是它提供了这一事实多值解决方案(即。,it allows us to find multiple geodesics between regions in the brain), and the fact that it is able to detect fibers in regions with low anisotropy (e.g., regions of the white matter with crossing fiber bundles). In Figure3,我们表明,该算法能够检测复杂的结构特点,如胼胝体的散度,使用streamline-based方法无法捕捉到的。详细的验证该算法被认为是超出了本文的范围;深入讨论了算法的有效性和适用性,我们参考读者通过Sepasian et al。6,7]。

测地线的定义是黎曼流形上的最短路径。这是一个真实的,可微流形,每个切线空间配备一个所谓的黎曼度量,这是一个正定张量。大致说来,度规张量的元素的一个迹象成本(或能源所需的)在一个特定的方向移动。对DTI数据,指标是一个直观的选择逆扩散张量。大值DTI张量对应于它的逆矩阵值小,表明扩散成本低,反之亦然。在本地,测地线往往会按照最低的方向度量值,这是类似于最高的方向扩散。我们定义的黎曼度量,在那里扩散张量。

在本文中讨论的算法,迭代计算纤维的轨迹数值求解一组常微分方程。常微分方程用于计算的轨迹纤维来自理论的测地线在黎曼流形,如下所示。

让是一个光滑,可微曲线通过卷描述参数,导数向量。我们定义的黎曼长度如下:

测地线的线最小化测地线的长度(1)。我们可以用欧拉方程这个函数转换成一组常微分方程,根据Jost[详细描述23]。

让和是第一和第二衍生品方面分别测地线的维度。让我们计算测地线的常微分方程由以下方程: 在哪里是所谓的克里斯托费尔符号,定义如下:

在这里,代表元素逆扩散张量的代表的一个元素原始扩散张量。我们注意到,为了计算所有克里斯托费尔符号,我们需要计算逆DTI的衍生品在所有三维张量。

给定一个初始位置和初始方向,我们可以构造一个路径通过3 d DTI图像,利用二阶龙格-库塔ODE求解器进行求解。初始位置通常是由用户指定,他们感兴趣的特定区域的组织(在我们的例子中,白质)。最初的方向,我们可以使用大量的方向每种子点(分布均匀球面上,或在主特征向量),看看这产生的纤维相交一些指定的目标区域。这样会增加我们的机会找到所有有效的种子点之间的联系(s)和目标区域(s)。

这种方法被称为州以及地区与地区之间的连通性的方法,需要一个合适的连通性测量(24),量化的力量种子点和目标区域之间的联系。换句话说,这个措施象征的概率计算测地线对应于一个实际的白质纤维连接。虽然本文不讨论州以及地区与地区之间的连接的实现方法中,我们注意到,为了可靠地找到所有种子点之间的测地线(s)和目标地区,我们需要计算大量的轨迹向四面八方扩散。这需要大量的纤维,结合的高计算复杂度算法本身,促使我们决定并行化测地线的演算法。

3所示。相关工作

利用GPU加速的可能性纤维跟踪算法(使用CUDA或其他语言)最近一直在探索在其他文献[25- - - - - -28]。这些实现使用几何着色器或片段着色器加速流线跟踪算法。除了Mittmann et al。28),引入一个随机元素,这些文件都使用简单的流线的纤维跟踪的方法,主要特征向量DTI的张量作为集成的矢量方向的一步。除了使用算法计算复杂度较低的测地线的演算法中讨论部分2.3,这些实现不同于我们的,他们使用GPU计算纤维着色器,当我们使用CUDA,它提供了更高的灵活性,并使学习曲线更加柔和比可编程GPU着色器(29日]。

最近,Mittmann等人介绍了一个使用CUDA GPU实现一个简单的简化算法(30.]。多线程CPU实现相比,这个GPU实现允许更高的帧速率,使实时交互式探索大量的纤维。加速因子,基于帧每秒,10至20倍。然而,论文的重点是交互性,技术讨论的优势和局限性CUDA的纤维跟踪算法是省略了。

宋et al。31日)已经开发出的CUDA实现纤维跟踪算法基于哈密顿雅可比方程,计算了纤维通路通过传播前整个体积。他们的解决方案对前面的传播将DTI图像划分为43块体素,之后,前面的传播通过并行类块的数量。这种方法已被证明是50到100倍的顺序实现类似算法的CPU。然而,如前所述2.3他们基础的HJ算法实现不能找到多个目标之间的连接区域。此外,front-propagation宋等人所使用的算法需要一个完全不同的射线追踪方法的并行化方法。

因此,我们得出结论,我们的解决方案是第一个CUDA-aided加速度的纤维跟踪算法的复杂性。将在下一节中,算法的复杂性引入了许多挑战并行化过程。此外,测地线的演算法的优点,讨论部分2.3表明,它的实现也会有实际应用。

4所示。测地线的纤维跟踪使用CUDA GPU

4.1。算法概述

节2.3,我们介绍了一个系统的常微分方程可以用来计算纤维的轨迹,给定一个初始位置和方向。我们算法的基础数值的ODE求解器解决了(2)使用一个固定的积分步长。具体地说,让点的坐标沿着纤维维度,让在这一点上的局部方向纤维。利用欧拉ODE求解器,我们可以计算和(即。,the position and direction at the next time step) as follows:

在这里,是一个固定的步长,中定义的克里斯托费尔符号(3)。在下面描述的实现中,我们使用一个二阶龙格-库塔ODE求解欧拉求解程序,但数值求解常微分方程系统的基本方法是相同的。计算克里斯托费尔符号时,所需的四张量(逆DTI张量及其三个衍生物)使用三线性插值插值。

总而言之,一个ODE求解器的集成步骤包括以下操作。(1)计算逆扩散张量和它的导数在所有三个维度对当前光纤点周围的八个像素点()。(2)在当前光纤点插入四张量。(3)计算所有克里斯托费尔符号。根据(2)和(3每尺寸),我们需要九个符号,总共27个符号。然而,使用扩散张量的对称特性(因此,它的逆矩阵和逆的衍生物),我们可以减少到18独特的符号。(4)使用克里斯托费尔符号,计算下纤维点的位置和方向。(5)重复步骤1到步骤4直到满足停止条件。默认情况下,只有停止条件是纤维的体积DTI图像。

我们注意到,第一步可能表现作为预处理步骤。虽然这增加了算法所需要的内存数量,这也大大降低了每个集成所需的计算步骤。这个预处理步骤已经在CUDA实现,但由于其简单的实现和运行时间相对较低(步骤2到5的比较),我们不详细讨论它,而不是把注意力集中在实际跟踪过程。图4总结了跟踪过程的步骤2到5,假设四个输入张量字段计算在一个预处理步骤。

4.2。CUDA概述

节中列出的州以及地区与地区之间的连接方法2.3给我们一个重要的问题:它需要大量的计算测地线。结合相对复杂的常微分方程在(2)(相对于常微分方程用于简单的纤维跟踪方法),这使得这种方法需要大量的计算。我们的目标是克服这种障碍在CUDA实现该算法,我们在本节简要概述。

NVIDIA的统一计算设备架构(CUDA) [32]是一种促进通用计算图形处理单元(GPGPU)。现代gpu包含大量的通用并行处理器,和CUDA允许程序员利用这个大的计算能力nongraphical用途。在CUDA,内核(通常是一个小的,简单的函数)是由大量的并行执行的线程,每个输入数据的一部分。在一个典型的执行模式,主机电脑第一次上传GPU输入数据,然后启动一个线程执行内核的数量。结果数据然后下载回主机PC或绘制在屏幕上。

一个人通常GPU的设备内存512 MB和2 GB之间,这是大多数现代gpu,和数量多处理器(33]。每个多处理器包含八个标量处理器(在当代大多数gpu;新一代将会有更多的标量处理器每多处理器);一个寄存器文件;一个共享内存块,使标量处理器之间的通信;和一个教学单位,发出指令的处理器。在这些多处理器并行性的类型单指令,多个线程(SIMT),它不同于单指令,多数据(SIMD)的线程有某种程度的独立性。理想情况下,所有活动线程在一个多处理器将执行相同的指令在同一时间;然而,不像SIMD, SIMT还允许使用if指令分支线程。虽然这并允许程序员创建更复杂的内核,它还增加了开销在执行时间方面,由于不同的分支必须按顺序执行。因此,最好是在内核尽可能避免分支行为。

另一个重要的考虑因素在设计CUDA算法内存层次结构。这两个内存块地方multiprocessor-the寄存器文件和共享内存低内存访问延迟。然而,这两个内存块的可用空间是有限的,用典型值16 kB的共享内存,和16或32 kB的注册文件。设备内存更多的存储空间,但是访问该内存400年和900年之间增加了延迟时钟周期(34]。设备内存包含四个不同的内存空间:(我)不变的记忆,一个只读块最好用于常量值;(2)纹理内存,一个只读空间优化纹理读取;(3)全局内存,主要的随机存取存储器空间;(iv)本地内存,一个线程扩展的注册文件。

本地内存时使用多处理器的寄存器文件不能包含所有变量的内核。自设备内存访问延迟非常高,使用大内核通常是最好的避免。作为一般规则,设备内存和多处理器之间的通信应保持尽可能低。第二个重要的原则是,内核的大小,每个线程的寄存器的数量和每个线程使用共享内存块的数量,应该保持小。这样做将允许GPU并行运行多个线程,因此增加了入住率标量处理器(即。,the percentage of time that each scalar processor is active). The structure of a CUDA-enabled GPU is illustrated in Figure5。

4.3。CUDA实现

记住CUDA的优点和局限性,讨论部分4.2,我们可以设计一个CUDA实现算法中引入部分2.3。如前所述在步骤3中算法的部分4.1,我们要求衍生品的逆DTI在所有三维张量。我们直观地看到,计算这些衍生品为每个点沿纤维会太昂贵的指令的数量,为周围所有8个像素点计算这些衍生物(使用双面数值推导)需要32扩散张量的反演。因此,我们决定预先执行他们。

这给了我们四个输入每体素:张量扩散张量和它的逆矩阵的三个衍生品。有六个独特的元素/张量和每四个字节值,这给了我们一个内存的要求字节/体素。该算法也有种子点作为输入,包含每个纤维的初始位置和方向。这些种子点是由用户决定,例如,通过指定一个图像中感兴趣的区域。

算法的输出由纤维的数量,每个组成的列表的3 d坐标。在后处理步骤,这些纤维可以通过目标区域(s)过滤和排序根据其连通性测量值,但这些步骤不属于讨论的CUDA实现。自从CUDA不支持动态内存分配,我们硬编码的数量限制的迭代步骤为每个纤维,和静态分配相应大小的输出数组/纤维。我们注意,这个极限的选择可能影响性能:高限制,更多的纤维将提前终止(由于离开体积),导致后期的入住率低的算法,而对于低限制,CUDA算法的启动开销可能成为相关。

我们直观地认识到两种不同的方法测地线的演算法的并行化:每个区域都并行化和per-fiber并行化。按区域方法需要加载一个小区域的图像共享内存的多处理器,跟踪大量的纤维通过这个区域(使用一个线程/纤维),然后加载下一个地区。虽然这种方法将保证低内存带宽需求和多处理器之间的设备内存,这是不切实际的,由于两个原因。首先,它是不可能保证地区将包含一个足够数量的纤维,使有意义的并行化。其次,由于有限的共享内存的大小,这些区域将是非常小的(每地区不超过约160像素点),这将战胜这种方法的目的。换句话说,这种方法需要某种程度的空间相干性纤维之间,由于我们事先不知道他们的轨迹,确保这个空间相干性是非常不切实际的。

因此我们使用per-fiber并行的方法,每个线程计算单个纤维。这种方法的主要优点是,它不需要任何纤维之间的空间相干性,从而高效地利用了GPU的并行性。只要我们有大量的种子点和初始方向,所有的标量处理器GPU将能够运行自己的个人其他线程的线程,从而最大限度地减少需要复杂的线程之间的同步,并保证一个稳定的计算吞吐量为所有活跃的处理器。这种方法的主要缺点是,它需要一个更高的内存吞吐量比按区域的方法,因为它不允许我们避免冗余内存读取。

内核执行的纤维跟踪流程执行以下步骤,总结在图4:(1)获取初始位置和方向的纤维。(2)当前光纤位置,获取扩散张量和它的逆矩阵的导数,用三线性插值。(3)使用这些四张量,计算克里斯托费尔符号,定义在(3)。(4)使用符号和当前方向,计算的下一个位置和方向纤维,使用的常微分方程(2)和一个二阶龙格-库塔的步骤。(5)写新职位的全局内存。(6)停止,如果纤维体积或的最大数量的步骤。否则,返回步骤2。

4.4。使用纹理内存

正如在前一节中提到的,per-fiber并行方法的主要缺点是,它不允许我们避免冗余的读取。我们可以部分解决这个问题通过存储输入图像纹理内存,而不是在全局内存。与全局内存读取、纹理内存读取缓存通过一些小缓存。这些缓存可以包含每多处理器8 kB,虽然实际变化/ GPU。虽然我们认为缓存内存读取可以减少所需的内存吞吐量,我们注意到缺乏纤维之间的空间相干性,加上小缓存大小,将在很大程度上抵消缓存的内存读取的积极作用。

第二,更重要的是利用纹理内存是内置的纹理过滤功能。当阅读纹理数据从一个位置位于网格点之间,CUDA将加权或线性插值使用专用硬件纹理过滤。将输入数据存储在全局内存时,所有必须完成的插值内核,增加两个指令的数量/集成步骤,和所需的内核的内存数量。通过委托插值过程专用硬件,我们能够减少尺寸和计算复杂度的内核。大小是特别重要的在这种情况下,作为小内核允许更高程度的并行性。

虽然我们预计使用材质过滤插值是有益的对我们算法的运行时间(在下一节中,我们将演示),我们确定一个可能的折衷。一个内核的属性插值是八周围像素点的值可以被存储在线程的本地内存,或共享内存的多处理器。这样做会增加线程的大小,但也允许重用一些这些数据,从而减少内存吞吐量的需求。使用材质过滤插值,我们不能存储周围的体素值,所以我们需要读一遍每一个集成的步骤。因此,内核插值可能需要比材质过滤插值内存吞吐量明显降低,尤其是对小步大小(在这种情况下,需要多个步骤纤维交叉细胞)。在下一节中我们通过实验分析权衡。

5。实验和结果

对实验提出了在这一节中,我们使用了一种合成数据集的1024×64×64像素点与2048年预定义的种子点。种子点分布的随机模拟的低空间相干性纤维,和他们最初的方向选择,没有线程会过早终止由于其纤维体积(即离开。,所有纤维留在预定义的最大数量的体积集成步骤,平行的长边卷)。虽然无论是形状和体积的内容还是没有纤维离开过早体积可以被认为是现实的,这让我们在最大负载下基准算法。

所有实验在NVIDIA GTX 260年,中档模型与24多处理器(总共192标量处理器)和1 gb的内存设备(35]。

应该注意的是,我们只考虑实际的纤维跟踪过程为基准。数据准备阶段(包括预处理和张量的反演方法,计算逆矩阵张量的导数)也一直在CUDA实现,但是本文的范围之外的被认为是由于其低复杂度,相比微不足道的并行化,低运行时间跟踪阶段。260年,GTX公司,数据准备阶段需要大约50毫秒每百万像素点(36),只需要执行一次/形象。产生的开销CPU和GPU之间的沟通在于几毫秒的顺序。

5.1。纹理过滤与内核过滤

节4.4,我们指出,使用专用硬件纹理过滤算法将大大降低的三线性插值一步我们内核的规模和复杂性,允许增加性能。我们还发现了一个可能的权衡:小步大小,内核插值可能比材质过滤插值,前者允许数据重用,而后者没有。我们测试这个假说通过改变(即0.05之间的步长。二十步平均每细胞)和0.5(两个步骤)。提出两种插值方法的测量运行时间图所示6。从这,我们可以得出结论,小步大小确实减少了内核插值的运行时间,材质过滤插值仍然是典型的更快的选择步长值(在0.1和0.2之间)。

5.2。限制因素

CUDA程序的性能通常是通过最大有限内存吞吐量在设备内存和多处理器之间,或由最大值计算吞吐量标量处理器。找出这两种算法的限制因素,我们首先计算其性能的内存和计算的吞吐量。(我)当计算2048纤维,每个执行4096集成步骤,算法需要大约165毫秒到完成。对于每一个集成的步骤,一个线程需要读8像素点4张量6独特的张量元素4字节= 768字节,它写到12字节(新点的三维坐标)。这给了我们780年的总内存传输2048年4096年≈6.54 GB。将运行时间,我们得到一个有效的内存吞吐量约3.97 GB / s,这是远低于最大111.9 GB / s GTX的260年。(2)计算计算失败的吞吐量(每秒浮点操作),我们首先对CUDA进行反编译程序使用decuda软件。通过检查生成的代码中,我们知道每个集成步骤使用256浮点指令。请注意,这并不包括任何指令所需插值,由于我们使用的专用硬件纹理过滤的目的。该算法执行2562048年4096 = 2147483648浮点操作,给我们一个大约13 GFLOPS的吞吐量计算。这是远低于指定的最大GTX的260,也就是715 GFLOPS。

因为无论是内存吞吐量还是计算吞吐量接近指定的最大值,我们需要确定限制因素以不同的方式。我们首先排除计算吞吐量的限制因素通过替换当前的二阶龙格-库塔(RK2法)ODE求解器通过一个简单的欧拉求解器进行求解。这并不减少设备内存之间传输的数据量和多处理器,但它确实减少每集成浮点操作步骤的数量从256年到195年。然而,这并不显著影响运行时间(165.133女士RK2法与欧拉165.347毫秒),表明计算吞吐率(即。处理器负载)不是一个限制因素在我们的案例中。

证明内存吞吐量确实限制因素,我们需要减少读取的数据量在每次集成步骤中,在不改变指令的数量。我们通过使用知识,我们合成的四张量输入数据集共享一个重复的值的数量。通过删除一些多余的阅读,我们可以减少每个线程的内存需求,在不影响数学算法的正确性。这个实验的结果列在表中1。由此,我们可以得出结论,我们的算法的性能是有限的内存吞吐量,尽管实际吞吐量明显低于260 GTX的理论最大值。节中列出可能的解释这种差异6。

5.3。加速因子

5.3.1。设置

评估我们的CUDA实现的性能,我们比较其运行时间的同一算法的c++实现现代CPU上运行。为了充分探索性能时,我们使用四个不同CUDA-supported gpu:方形住宅区外汇770,的GeForce 8800 GT的GeForce 260 GTX公司,GeForce 470 GTX公司。这些gpu的重要规范如表所示2。应该注意的是,我们的CUDA实现GTX 260,不另gpu执行修改。特别是,这意味着我们没有优化我们的算法,利用改进的CUDA的特点最近GTX 470 GPU。

CPU运行c++实现英特尔酷睿i5 750,四核,与2.67 GHz的时钟速度。的发布日期和价格,i5 750(在2009年秋季发布)是最接近GTX 470(2010年春季);在写这篇文章的时候,都认为中期前一代的高档消费品。

在该基准测试中,我们使用脑DTI图像的尺寸体素。被放置在一个小种子点,二维区域22×4像素点,位于胼胝体的一部分。一个近似的种子区域,以及由此产生的纤维,如图8。种子点是随机放置在这个地区,一个随机的初始方向。种子点的数量从1024年到4096年不等。这个测试因此密切模仿射线跟踪算法的实际应用,显示在图8。

5.3.2。CPU实现

我们的c++实现的算法特性支持多个线程执行(多线程),它可以利用CPU的四核提供的并行性。让种子点的数量,线程的数量。我们分配种子点,每个CPU线程,因此每个线程计算纤维。我们已经测量了这个CPU实现的运行时间为不同的值,用设置为4096分。这个基准测试的结果图中可以看到7。从这些结果,我们可以得出这样的结论:并行CPU实现(使用基本相同的度并行至于我们GPU实现)可以减少运行时间约4.5倍。性能增加的事实比核的数量可以归因于一个CPU核心可以切换到一个不同的线程,当活动线程正在等待数据从主内存的电脑。从图7,我们也可以得出这样的结论:64个线程是最好的配置算法和CPU。

5.3.3。GPU基准测试结果

我们做了相同的基准实验四人gpu,我们比较了CPU运行时间的最佳配置。这个测试结果如表所示3。的结果,我们可以得出结论,我们的CUDA实现显著减少射线跟踪算法的运行时间。即使在一个中档GPU为笔记本电脑像外汇770,运行时间减少了大约两倍的一个因素。使用高端,最近的GPU如GTX 470,我们甚至能达到40倍的加速因素,大大提高了算法的适用性。gpu加速因素之间的差异可以解释部分的差异bandwidth-which被认定为部分的限制因素5。2——处理器的数量。

6。讨论

在前面的部分中,我们描述了测地线的CUDA实现纤维跟踪方法。这个CUDA程序使用的知识,纤维可以独立计算的并行化计算,从而减少运行时间因素的40倍,比多线程CPU实现相同的算法。

虽然该算法确实允许有意义的并行化,我们注意的两个问题,充分利用GPU的并行性提供了挑战。(我)该算法需要大量的内部存储;四张量输入,克里斯托费尔符号之间的位置和方向的纤维,即使最有效的版本,我们的实现仍然需要43每线程寄存器,而典型值CUDA 8 - 32之间的算法。(2)更重要的是,该算法需要大量的数据传输,因此,内存吞吐量成为限制因素。这个问题还远未(微不足道的解决,虽然有些选项确实存在,它们都有自己的缺点。(1)减少碎片的数量每输入值将降低所需的内存吞吐量,但付出的成本降低精度。(2)允许纤维重用输入数据用于插值大大增加内核的大小和材质过滤插值不工作,使用已被证明是非常有益的在我们的案例中。(3)线程之间共享输入数据在一个多处理器需要某种形式的空间相干性之间的纤维,这是极难保证。

如上所述,设备内存和多处理器之间的内存吞吐量性能的限制因素。然而,如上所述5。2,实际的吞吐量是远低于设备的理论最大值。下面,我们列出一些可能的原因不同。(3)大部分随机存取存储器(RAM)配置经验一定开销当随后的读取访问不同部分的数据范围。从种子点的空间位置较低会导致这种分散的访问模式,这开销可以解释我们的内存吞吐量相对较低。(iv)根据CUDA文档(32),纹理读取已经优化了2 d空间局部性,大概使用空间曲线。没有空间位置可以防止我们的算法利用这些优化。(v)纹理获取的吞吐量和过滤单元可能成为限制因素时大量的体素。文档GTX的260个国家,它应该能够处理369亿texel每秒(33),而我们的实现仅加载每秒390亿字节(多字节texel)。然而,这个数字是基于2 d双线性插值,而我们使用3 d三线性插值。

我们预计第一点是最主要的因素,虽然我们没有进行实验来证明或反驳这一假设。

测地线的基于gpu加速光线跟踪算法DTI是一个有用的技术,但是它的实现提出了一些挑战。问题的一部分等加速数值积分算法的论文讨论之一是它几乎不可避免地引入了不可预知的内存访问模式,虽然现有的CUDA算法通常使用更规律的,可预测的访问模式,从而更容易优化。这是一个基本的问题没有简单的解决方案,和一个并不局限于人gpu,但也适用于其他并行平台。然而,尽管我们的实现实现表现不佳,我们相信其显著的加速系数高达40倍,加上人的低成本和高可用性硬件,使其切实解决测地线的演算法的计算复杂度为纤维追踪,和一个很好的起点为未来加速度类似的算法。

7所示。结论和未来的工作

在本文中,我们讨论了基于gpu加速纤维跟踪DTI的测地线的演算法。这种算法的优点之一是它能找到多值的解决方案,也就是说,多个区域的白质之间可能的联系。然而,算法的计算复杂度高,再加上我们需要计算大量的轨迹如果我们想找到合适的连接,使其缓慢相比,类似的算法。为了克服这个问题,我们加快了算法通过实现一个高度GPU并行版本,使用NVIDIA的CUDA平台。我们表明,尽管大内核大小和高内存需求的GPU实现,我们可以加快算法的40倍。这显著减少运行时间使用廉价而广泛使用硬件大大增加算法的适用性。

除了进一步优化现有的GPU实现,目的是进一步减少其运行时间,我们确定了两种可能的扩展工作提出了。(我)目前,计算纤维下载回CPU、位的地方,随后可视化。更直接的方法是直接可视化纤维计算算法,使用可用的GPU的渲染功能。如果我们还可以在CUDA实现必要的后处理步骤,我们可以显著减少内存需要CPU和GPU之间的转移,从而加速完成纤维跟踪管道。(2)州以及地区与地区之间的连接方法是一种有价值的应用测地线的演算法。该方法引入了三个额外的步骤:(1)计算合适的连接措施,同时跟踪纤维或后处理步骤,(2)过滤纤维通过计算目标区域,和(3)排序其余纤维根据他们的连接措施,只显示这些纤维厘米高值。这三个步骤目前已经实现CPU,但GPU实现这些系统可以减少整体处理时间的纤维跟踪管道,如上所述。(3)DTI模型有限在模型其精度无法穿越的纤维。高角分辨率扩散成像(现成)旨在克服这种限制通过测量和建模的扩散方向(37]。节中给出的算法的扩展2.3它使用现成的数据而不是DTI理论上更准确,尤其是在复杂的区域的白质。这样的一个扩展,例如,实现通过使用Finsler度规张量(这都取决于位置和当地取向的纤维),而非黎曼度量张量(38,39]。而扩展算法的可能会更复杂的计算数量和所需的内存,使用并行的CUDA-based加速度原理提出了仍将大大快于任何CPU实现。

我们注意到,尽管这些扩展将有价值的补充,当前CUDA实现已经提供了一个实用的测地线的加速光线跟踪和可伸缩的解决方案。

承认

这个项目是NWO 639.021.407项目号码。