GPU中非对齐访存问题研究.docx
- 文档编号:18618624
- 上传时间:2023-08-20
- 格式:DOCX
- 页数:18
- 大小:263.75KB
GPU中非对齐访存问题研究.docx
《GPU中非对齐访存问题研究.docx》由会员分享,可在线阅读,更多相关《GPU中非对齐访存问题研究.docx(18页珍藏版)》请在冰点文库上搜索。
GPU中非对齐访存问题研究
GPU的性能表现与内存的不规则引用相关。
一些近期工作展示了数据重组对于消除由不规则相关引用引起的非聚合性数据访问的研究进展。
然而之前的方法使用的是简单地、启发式的方法来决定新的数据布局的创建。
结果,他们既没有提供任何性能保证,并且只是在一些固定的情境下有效。
本文对该问题进行了基础性的研究。
在多种设置中系统分析了问题的固有的复杂性,第一次证明了该问题是一个NP-complete问题。
然后指出了现有技术存在的局限性,并且在实践中揭示了设计一个适当算法的本质是在时间、空间和复杂性之间进行折衷。
基于此,提出了两种新的重组算法以克服之前方法的缺陷。
实验表明新算法与就算法的组合可以避免需找最佳数据布局的固有复杂性,从而可以比现有技术更好的减少由一系列不规则引用引起的非聚合的内存访问,。
介绍
近几年GPU计算广泛应用于高性能计算中。
作为一种大规模的并行架构,GPU对于许多规则的数据并行的应用具有明显加速作用。
但是对于不规则的应用则性能明显降低,特别是应用包含动态的、不规律的访存相关。
原因来自于GPU的硬件特征。
GPU以groups的形式组织线程,以segments的形式组织内存。
每W个线程组成一个warp,以连续的ID编号。
全局内存中每S个连续的bytes组成一个segment。
当进行一次内存引用时,一个warp访问的数据由内存处理动作进行加载,该数量需要与包含数据的segments数量相同,当该数字大于可能的最小值,则该访存动作成为非聚合内存访问。
非聚合内存访问的定义,如果一个warp中的线程对全局内存访问地址是连续的,则实现了对其访问,其中某些线程可以不参与访问,与此相反,线程的交叉访问或者偏离起始地址的访问都构成了非对齐访问。
非对齐内存访问普遍存在于不规则应用中。
图一(a)展示了一个简化的分子动力仿真的核心计算代码。
划线部分代表值与当前分子的neighbor相关。
作为一种典型的动态不规则访存,它可以展示许多不同的访存模式,取决于neighbor中究竟有什么。
(b)中,warp的所有访问目标都是一个内存segment,假设一个segment中可以包含四个分子位置,则只需要执行一次内存访问动作。
在C中,由于neighbor中的不规则数据,使得该访问是非对齐的,需要多个内存处理动作。
这种不规则性在分子动态仿真中普遍存在,因为分子运动以及其动态的邻居。
这是许多科技仿真的关键性质。
非聚合性访问可能导致访存动作达到最低值的W倍,使得吞吐率一系列因素低于GPU的峰值。
他们成为了最近的研究热点。
但是大多数相关实验是关于静态的不规则,因此在编译时内存的访问模式是确定已知的。
本文中的不规则形式是动态的,例如,在图一中的索引组中的neighbors取决于程序的输入,而程序是在对分子运动的仿真过程中不断更新。
当程序运行时需要对动态不规则的数据访问进行处理。
早之前的研究基于一种特殊的硬件扩展来调整GPU以避开这种访问。
近期有种研究展示了希望使用纯软件的方法去解决整个问题。
它提出了一种管道调度算法,目的是GPU运行在当前的kernel时,CPU完成对数据和线程的重组,并调用稍后的GPU运行kernel。
相关研究宣称可以将重组交给GPU,从而使CPU可以参与处理负载。
虽然这些研究显示了可喜的加速比,对重组数据以减少非聚合的GPU内存访问的理解仍然停留在初步。
之前的研究狙击在联合CPU和GPU以允许运行数据可以重组。
他们还没有挖掘出数据重组和GPU内存性能之间的关系这一基础问题。
结果是,他们提出的重组算法缺乏性能保证或者只是适用于有限的条件下。
当前工作提供了提供了理解GPU数据重组以减少非聚合访问的原则。
复杂性分析:
系统的分析了数据重组与GPU访存之间的关系,证明了在多项式时间内只是通过数据重组并不能减少访存动作,除非P=NP。
此外,还证明了及时允许线程重组为warps,复杂性仍然不会改变。
结果显示,论有或没有硬件扩展,通过数据移位,线程重组,或者二者的结合,都不能找到一种通用的减少GPU访存的次数,虽然在之前的GPU存储优化中普遍使用这三种方法。
强大的理论结果为知道当前的研究方向提供了指导。
局限性及本质:
这部分的工作指出了现有GPU动态不规则引用的优化算法的局限性,并进行了验证,设计数据重组算法的本质实际上可以看作是在空间、时间和复杂度之间的权衡。
算法:
基于结论,这部分工作提出了两种新的数据重组算法,以各自的优势完善现有算法的。
结果表明,新算法在降低非聚合内存访问的同时有效的降低了空间消耗。
对比及选择:
该部分工作对比了多种算法,将它们结合成了一个组件,并开发了一些选择的准则和自动算法选择器以适应GPU在不同场景下的动态不规则访问。
评估:
基于动态不规则应用的实验展示了所开发的组件,与算法选择器一起,在寻找优化的数据布局时规避固有的复杂性,从而使得可以针对一系列不规则应用和设置达到减少非聚合存储访问的目的,是超越现有技术的实现。
与现有技术相比,组件可以达到两倍的加速比,平均为10%到50%,证实了它作为解决GPU中动态不规则访存问题的方法的优势。
2问题设置和复杂性分析
该部分首先介绍一些与GPU密切相关的背景知识。
接着描述了研究人员所提出的解决方法。
最后揭示了这类方法所面临的根本性的挑战,即这些方法根本不能减少动态不规则访问的非聚合访存数量,除非P=NP。
2.1GPU的背景
作为一种大规模并行设备,GPU在一个SM(streamingmultiprocessors,流多处理器)包含了数百个内核。
当一个kernel被启动,在运行时会产生上千条GPU线程在这些core上并行运行。
这些线程被分层组织。
若干具有连续ID的线程(在NVIDIAGPU中是32个)组成一个warp,若干warp组成一个线程块(threadblock),所有的线程块组成一个grid(本文使用CUDA术语)。
一个warp是GPU调度的基本单位,warp中的所有线程是以lockstep的形式执行。
GPU有多种内存。
最大的是全局内存。
由大量的段(32、62或者128bytes)组成。
由于其大尺寸和长时间的访问延迟,全局存储器的存取效率是个关键的问题。
GPU因此支持内存合并功能,基于硬件特点,只要一个warp的load/store指令,就可以只运行一次存储器事务就可以load/store一个存储器段中的所有的数据。
结果,一个warp执行一个load/store指令产生K个存储事务,K等于包含需要的数据的存储器段的数目。
假设一个warp的load/store指令需要Dbytes的数据,而一个存储器段有Sbytes,当K>[D/S]时,该引用为非聚合引用,该访问为非聚合访问。
GPU中另一种存储器是共享存储器,这是这是一种访问延迟可以与寄存器相媲美的存储器。
当且仅当两个线程属于同一个block时,一个线程可以访问另一个线程在共享存储器上加载或者存储的单元。
在接下来的讨论中,所有提到的存储器默认为全局存储器。
2.2研究目标以及复杂度
非聚合访存最小化研究的目标是最小化一个GPUkernel的非聚合访问数量。
最小化对于GPU的性能表现非常重要,因此吸引了大量的注意力。
然而,合适的解决方法任然只是在有限的特殊情况下有效。
在本节中,我们将检测以前的方法的复杂性,并证明在一般情况下,使用该方法来达到目的是不可行的,除非P=NP.结果将会指导未来的研究方向,也为本工作剩余部分提供了理论基础。
一个GPUkernel可能包含多种引用,我们关注于一种情况,剩余情况在之后进行讨论。
2.2.1数据的重新定位和NP完全问题
数据重新定位是之前关于减少非聚合访问工作的主要方向。
基本思想是重新排列存储器上的数据元素,使得一个warp中所要访问的数据可以保持连续,从而覆盖最小的存储器段。
例如图一(c)中。
转换机制将会创建一个新的数组POS’,将POS的元素重新排序后作为POS’的元素,这样使得POS[9\103\23\67]落在同一个存储器段中。
矩阵转置是另外一个例子:
通过重新定位内存中的数据以创建column-major数据布局,可以减少对对矩阵column-wise相关的非聚合访问。
虽然听起来简单,但是当数据被对个warp重叠访问时,使用数据重新定位会变得非常麻烦。
考虑一个相关A[P[tid]],P的内容为P[]={8,23,46,93,8,9,10,67,5,11,41,67,9,41,55,59}.假设存储器段的长度S等于4,warp的尺寸W为4。
P中的重复值使得A中的一些元素会被多个warp访问。
这些存放这些数据的segment处理起来十分棘手。
例如:
将A[8]同A[23],A[46],A[93]放在一个segment中,使得第一个warp的访问时聚合的,但是剩余的warp的访问将会变得非聚合。
这个问题已经非常吸纳之数据重定位技术的适用性。
尽管最近许多努力花费在该技术上,这个方法唯一有效的情况就是每个被访问的数据元素只会被kernel中的唯一一个warp访问。
在动态不规则条件下应用,这种情况几乎不会出现:
这分子动力学中,一个分子往往有多个邻居;在稀疏矩阵乘法中,向量中的元素通常会多次作为乘数。
复杂性定理:
各种各样的人在寻找一种通用的数据重定位算撒以保证最小非聚合访问时所遇到的困难,我们进行了一个关于问题固有复杂度的系统性分析。
一个重要的结论就是这种算法根本不存在,除非P=NP。
提出如下定理:
定理1:
通过数据重新定位来创建一个新的数据层以减少非聚合性访存,对于GPU上的随意数据引用来说是个NP完全问题。
由于这是第一次对非聚合数据访存最小化的声明,值得进行正式的证明,同时提出的意见会对其他GPU优化技术提供分析帮助。
证明:
假设不规则的引用,被GPU的所有线程执行,会访问n个不同的数据项。
令z代表一个存储segment的长度,以数据项为单位。
重定位的目标实际上是将n个数据项均匀分为n/z个簇,从而使得每个簇可以放入一个单独的存储segmen中,从而使总的存储事务达到最小化。
为证明NP完全性问题,我们使用以下的标记法。
Δ:
将会被分区的所有的数据项;n=|Δ|;Ψ:
所有warps;m=|Ψ|;
Ψ
根据每簇有z个数据项的标准分区的Δ。
rC=|Ux∈CΨ
Δ,|C|=z){C中的数据项X,引用该X的warp的并集}。
代表:
rC表示包含所有访问在C中数据的warps。
因此rC表示在C中所有数据项放入同一个segmen中需要执行的内存事务。
因此,对于分区后的Ω总共需要
次的存储事务,如果每个簇中的数据都放入存储segment中。
而目标问题则抽象为寻找一个Ω使得
最小化。
它的相应的角色问题是:
给定一个任意数u,是否存在一个Ω存在,使得
.我们称这个决策性问题为DLDP(DataLayoutDecisionProblem)。
通过3DM(三维立体装箱)问题,一个著名的NP完全性问题,足以证明DLDP是一个NP-hard问题。
3DM问题定义如下:
输入:
三个不相交的集合R,G,B,|R|=|G|=|B|=l,以及一个三维向量T,
。
问题:
是否存在一个集合S满足以下条件:
(1)
;
(2)|S|=l;(3)V 根据SDM问题,将DLDP问题抽象如下: Δ=|BUGUP|,n=3l;m=|T|;z=3;u=l(m-1);Ψ: m个warps构成,每个warps有一个唯一的ID,与T中的一个元素相对应,一个包含ID Δ,x 。 我们得到一个结论, ’的构建使用DLDP去解决3DM问题。 由于 ’是Δ的划分,| ’|=l;由。 于 ’可以解决3DM问题, 成立。 从 ’中我们设置一个3D向量S’(|S’|=| ’|).S’中的每一个项目 ’,{x1,x2,x3}, 我们证明S’是3DM问题的解决方案,满足3DM问题的所有情况。 明细S’满足 装箱问题: 装箱问题也就是把一定数量的物品放入容量相同的一些箱子中,使得每个箱子中的物品大小之和不超过箱子容量并使所用的箱子数目最少。 其应用在实际生活中无处不在,货物装运,服装裁剪,以及我们计算机科学中的存储分配、共享资源调度、文件存储都是装箱问题在实际应用中的体现。 所以装箱问题有着广泛的应用背景,具有很大的研究价值。 装箱问题是经典的NP难解问题,这意味着该问题不存在在多项式时间内求得精确解的算法(如果P≠NP)因此对装箱问题算法的研究指的是对其近似算法的研究,所谓近似算法即该算法可以求得与精确解接近的结果但不一定得到精确解。 NP问题: 而如果任何一个NP问题都能通过一个多项式时间算法转换为某个NP问题,那么这个NP问题就称为NP完全问题。 通过归纳推导,证明了DLDP属于NP完全性问题。 2.2.2允许warp重组时的情况 上述证明假设数据重新定位可以用于非聚合内存访问。 近期一些研究表明warp重组可以同样减少非聚合存储访问,可以与数据重定位一起用于优化。 本节将证明使用warp重组问题同样改变不了NP完全问题这一事实。 定理二: 对GPU上的任意数据引用使用数据重定位,warp重组或者同时使用两种方法以减少非聚合访问是一个NP完全性问题。 Warp重组是指跨warp交换线程。 也叫jobswapping,因为它是交换一个warp访问过程中的线程和数据。 Swapping可以移开非聚合的访问。 例如: 假设线程t3访问A[7],线程t7访问A[3],开始的两个warps中的其余线程访问A[tid]。 交换t3和t7后,新的t3将会做t7原来做的工作去访问A[3],而新的t7会访问A[7]。 两个warp都会变得聚合。 运行时进行warp重组已被证明是可行的,可通过硬件扩展或者程序变换进行。 也可以与数据重定位一起被用于减少非聚合访问。 我们现在证明允许warp重组不影响数据重定位问题的计算复杂性。 证明了这一点,就证明了一个特殊情况下的NP完全性问题。 这一种特殊情况是,假设数据元素的大小作为segment的大小。 此时,数据的重定位不改变数据元素的聚类分析,对内存的访问数量没有影响。 因此我们如果可以证明只是经过warp重组减少非聚集的内存访问是一个NP完全性问题,就证明了定理二。 。 Warp重组实际相当于将每个线程的工作重组为簇,每个簇中包含Wjobs(W是每个warp中包含的线程数目)。 不是一般性的考虑,一个jobs仅包含一个对数组的不规则引用。 另N代表线程数目,M代表内存段的总数目,每个内存段至少包含一个需要访问的数据项。 我们认为将N个jobs划分为N/W个均匀的簇,使得每个warp运行一个集群的工作是,使内存事务的总数目达到最小是个NP完全问题。 证明是通过从一个已知的NP完全问题: 划分问题,得到的。 2.3讨论 本部分分析了使用数据重定位减少非聚合访问的计算复杂性。 已经证明的NP完全问题不排除通过一些启发式算法,可以对一些特殊类型的kernel进行良好的加速。 然而,它确实表明用它来达到最优是一个极具挑战的工作。 接下来展示了如果放松约束条件是可以避免这个挑战的。 3避免复杂性的算法 我们设计两种新的算法来规避数据重定位时面临的困难。 一个重要的观察发现时,数据重组的主要困难来源于一个隐含的约束: 新产生的数据布局与原来的数据布局使用的空间差不多,如果饿我们使用更多的空间,问题的难度将急剧减少。 下文的讨论基于对A[P[tid]]的访问,一个动态不规则访问的概念形式。 假设内存大小S是warp大小的倍数,往往是2的幂。 即使不是,如下讨论仍然有效,除了需要一些额外的预处理去对齐segment的数据。 3.1回顾复制方法 对于一个不规则引用,如A[P[tid]],算法创建一个新的数组A’,使得A’[tid]=A[P[tid]];使得kernel中对A[P[tid]]的引用替换为对A’[tid]的引用。 算法自然而然的保证了一个warp中的所有存储访问是对连续的区域,并且没有非聚合存储访问。 图4解释了原理。 图4 该算法成为复制算法是因为当P包含相应的值是就对目标数据项进行复制。 显然新的数组A’与GPU的线程数目相同(T),无论原来的数组A有多小。 更糟的是当存在相同的数据引用时(如A[P[tid]]+A[P[tid]+v),算法仍然为每个引用创建一个T长度的数组。 3.2限制与权衡 复制算法将不规则的访问转化为规则的访问。 然而,它对空间的使用可能会急剧膨胀。 如果一个K个元素的数组被GPU的T个线程应用n次,空间消耗为n*T/K。 在现代GPU中,T的大小可以与整个内存中的bytes数量相媲美。 空间开销很大会导致两个后果。 首先,基本的复制算法不能用于空间膨胀超过内存容量时。 第二,创建和传送大量的数据会导致大量的时间开销,抵消因此带来的性能提高。 有工作使用部分复制来解决问题。 基本思想是只将这种转换应用到部分的线程。 虽然可以减少空间消耗,但是它降低了优化质量。 第五节将会展示,这种技术的加速会比预期低。 图二展示了以往方法的在空间-质量-复杂度左边内的位置。 数据重定位和复制算法在空间消耗方面是两个极端。 部分扶着的空间消耗较低,但是相应的转换质量降低,延长了kernel的执行时间。 数据重定位算法具有最低的空间消耗,但是复杂度最高。 所有一个使用的算法需要找到一个平衡点,使得在不降低转换质量的同时空间开销得以减少,并且具有可以容忍的复杂性。 接下来介绍两种接近目标的算法。 3.3填充算法 填充算法的目的是在不降低优化质量的同时避免一些不必要的数据复制。 基本思想是如果同一个warp中的两个线程访问相同的数据项,则不需要复制数据项。 我们可以简单地让他们访问数据元素的副本。 将会改变数据与线程之间一对一的映射的复制算法,也不会因为两个线程访问相同的数据段segment而增加非聚合访问。 3.3.1简单地设计 一个简单地设计是将复制算法进行如下更改。 当算法在新的数组A’中创建一个数据项的副本时,检查当前线程在当前warp中是否是第一个访问该数据项的,如果不是则不创建该副本。 不幸的是这个改动因为两个原因存在不足。 第一,能避免的重复只占原来完全复制的很小的一部分,因为在同一warp中的线程访问同一数据项的机会很小。 其次,一些回避的重复复制经常在warp和segment中引起错位。 结果是,一个warp可能会跨越对应segment的边界,造成了新的非聚合访问。 3.3.2改进设计 改进的算法解决了上述两个问题,通过整理和排序操作。 图3展示了该算法的伪代码,包括三个步骤。 第一步是根据数据的访问频率对其进行重新排序。 在数据引用中,数据的访问频率代表访问该数据的线程数目。 第二步是将线程重新组成warps、根据数据元素的顺序重新排序线程,即如果数据X在数据Y之前,则所有线程如果要访问数据Y,则必须先访问X。 排序之后,从第一个线程开始,每W个相邻的线程组成一个warp。 这两步解决了上述简单算法的第一个问题: 通过使访问相同数据元素的线程相邻并组成warp,从而可以有更多的机会实现复制。 第三步,将数据元素存入segment。 新的顺序中从第一个数据元素开始,数据元素一个接一个的放入segment。 但是当发现当前segment无法存储当前线程所要访问的所有数据时(例如,图4c中的第一个segment,) 它将warp要访问的所有数据放入下一个存储segment中,在先前的segment的尾部插入了一个空格。 数据只在需要的时候才被复制,即当一个数据项会被多个warp访问时,而这个数据项不会落入一个segment中时,图4c中的两个c。 这步解决了简单算法的第二个问题。 通过在必要时使用空字段填充segment,使得segment与warp同步工作。 分析这种填充方法保证了零非聚合访问,自从他将每个工作的warp都放入一个segment中。 它的空间开销来自那些填充的空槽和一些重复的数据元素。 如果在warp中有k个线程访问同一个数据元素,则一个segment中的空槽就是mod[S,[W/k]],其中[W/k]代表一个warp中需要访问多少个不同的数据项,S代表一个segment中能包含多少数据项。 S和W是2的倍数关系。 所以最坏的情况是k很小但是不是2的倍数。 例如当k=3时,空槽是最长的,达到了W/2.但是即使在这种情况下,空间消耗也大大小于复制算法的。 在这种情况下一个segment所服务的线程数不低于t=(S-W/3+1)/(W/3).假设S是W的倍数,令S=r*W则t必定不小于3r-1.至少是2.在复制算法中,这些线程将使用至少2S个内存segment。 在分析填充算法的重复数量时,需要注意所有warp访问当前segment时,只有第一个可能会数据项复制。 因为只有当一个warp的工作组与前一segment有数据重叠时,才会在当前segment进行复制,这些重叠必须基本上是完全重叠,前一segment包含了第一个warp的工作集,因此warp会更适合前一个segment。 由于线程被排序的方式,这部分重叠使得其他warp的工作集与前一segment中的数据重叠,因此没有重复数据。 根据观察,我们可以看到,在前段提到的情况下,一个segment的重复部分小于W/3-1,小于1/3*r.作为对比,重复算法为每个数据元素创建了至少3个副本。 局限性尽管算法具有吸引人的地方,填充算法有一个主要的限制。 因为它不仅重组数据还会重组线程。 对于kernel中的其他引用可能会造成副作用。 例如,如果kernel包括B[tid]+A[P[tid]],在交换第3个和第9个线程后,他们交换了jobs,则对B的访问必须交换。 也就是说B[tid]必须被B[R[tid]]代替。 否则,新的线程3将会用B[3]与A[P[9]]相加,而不是B[9].会导致错误的结果。 结果A[P[tid]]的优化会导致B的非聚合访问。 因此填充算法只对存在相同访问模式的kernel有效。 3.4共享算法 本算法从另一个角度改良了复制算法,克服了填充算法的缺点。 它使用GPU的共享存储来扩展复制算法的范围。 共享内存是GPU里一种片上内存。 一个线程在共享内存中写的数据只能被同一个线程块中的线程访问。 共享存储器的延迟比全局内存要小近百倍,更重要的是,它的性能表现对是否是不规则访问不敏感。 思想: 该算法的一个核心思想是将对全局访问的不规则访问转化为对共享内存的访问。 由于共享内存对于同一个线程块是可见的,因此共享算法将复制有效范围从一个warp扩展到线程块。 基本思想是对一个线程块所要访问的所有数据创建一个副本,每个数据元素都进行复制,并将其放入内存中的连续的块。 接下来,将这些连续的数据存入共享内存。 它将线程块对内存的访问重定向到了共享内存中。 整个线程块要访问的数据块进行了一个拷贝,可以避免许多冲动复制。 通过将不规则访问映射到共享内存中,减少了对全局内存中的非聚合访问。 通过聚会手段增加了节约重复的机会。 详细的算法描述如下: 算法: 图五展示了共享算法的伪代码。 包括两步,首先,在线程块之间进行交换线程,以达到聚类的效果,使得块中访问相同数据元素的线程尽可能的多,不同的线程尽可能的少。 许多聚类算法可以达到这个目的。 在我们的实现中,我们是实现了两种。 第一个是基于图划分的聚类,适合用于图的拓扑结构,例如在分子动力学仿真中的分子。 在这些应用中,特别是每个线程负责图中的一个顶点。 算法随机选择一些顶点作为种子,分配给他们一个不同的簇号。 接着各个节点不断的扩展器同类节点作为其邻居。 线程通过继承对应节点的簇号实现聚集。 第二种算法适合另外的情况,使用一个节点的工作机作为特征,使用标准的层次聚类来建立集群。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- GPU 中非 对齐 问题 研究
![提示](https://static.bingdoc.com/images/bang_tan.gif)