现代GPU上的高效控制流与异常流机制综述

浙江大学现代GPU上的高效控制流与异常流机制综述21221144沈阳2012/12/30

目录摘要…………………………….21 引言 21.1 强大的计算能力，便宜的价格 21.2 编程模型和体系结构 22 体系结构 42.1 微体系结构 62.2 发散的控制流 73 高效控制流执行方案 83.1 DynamicWarpFormation 93.2 ThreadBlockCompaction 93.3 CAPRI 113.4 SBI和SWI 134 异常流 165 总结 186 参考资料 18

摘要GPU性能的快速增长，加上其最近十年来可编程性的提高，使得现代GPU成为了许多领域运行计算任务越来越引人注目的平台。现代可编程GPU允许不规则的控制流在其SIMD流水线中平稳运行。为了保证分支执行的正确性，GPU使用掩码让每个SIMDlane执行一条逻辑线程。然而，掩码执行导致性能的下降，因为被掩码屏蔽的lane的计算性能都被浪费了。另一方面，为了提高GPU的适用范围和可用性，对GPU提供异常支持将是下一步努力的方向。在这篇综述中，我会对GPU上的高效控制流执行和提供异常支持的方法进行描述，总结和分析。我会从利用GPU进行通用编程的动机开始，描述GPU的通用编程模型和体系结构。GPU的编程模型决定了GPU的体系结构设计，而体系结构设计对理解GPU的控制流执行方法改进和异常支持的困难至关重要。从这里出发，综述分成两部分。首先，我会描述高效控制流执行的方法，这些方法企图合并多条没有屏蔽的线程在一个SIMD处理器上执行。接着，我会描述一种软硬件结合设计对GPU提供轻量级异常支持的方法。引言GraphicsProcessingUnit（GPU）很可能是今天每单位人民币计算能力最强大的计算硬件了。越来越多的研究者和开发者开始对利用GPU进行通用计算（GPGPU）感兴趣。在这篇文章中，我会描述GPU的微体系结构，并以此为基础描述GPU上高效控制流执行机制以及提供异常支持的方法。现在从利用GPU进行通用计算的动机开始。强大的计算能力，便宜的价格最近的GPU提供惊人的计算能力和内存带宽。如REF_Ref344454617\h错误!未找到引用源。REF_Ref344454627\h错误!未找到引用源。ADDINEN.CITE<EndNote><Cite><Author>NVIDIA</Author><Year>2010</Year><RecNum>13</RecNum><DisplayText>[1]</DisplayText><record><rec-number>13</rec-number><foreign-keys><keyapp="EN"db-id="vfwsswdpydftfherdv2x0a5vw9rr5r5prtaz">13</key></foreign-keys><ref-typename="ElectronicBook">44</ref-type><contributors><authors><author>NVIDIA</author></authors></contributors><titles><title>NVIDIACUDAProgrammingGuide</title></titles><dates><year>2010</year></dates><urls></urls></record></Cite></EndNote>[\o"NVIDIA,2010#13"1]所示，从04年六月以来，NVIDIA每一代GPU都比Intel同等价位的CPU的浮点计算能力要强，并且这种差距越拉越大。GeForceGTX580的理论浮点运算能力达到1500GFLOP/s，而SandyBridge只有500GFLOP/s不到。另一方面，如REF_Ref344455381\h错误!未找到引用源。ADDINEN.CITE<EndNote><Cite><Author>NVIDIA</Author><Year>2010</Year><RecNum>13</RecNum><DisplayText>[1]</DisplayText><record><rec-number>13</rec-number><foreign-keys><keyapp="EN"db-id="vfwsswdpydftfherdv2x0a5vw9rr5r5prtaz">13</key></foreign-keys><ref-typename="ElectronicBook">44</ref-type><contributors><authors><author>NVIDIA</author></authors></contributors><titles><title>NVIDIACUDAProgrammingGuide</title></titles><dates><year>2010</year></dates><urls></urls></record></Cite></EndNote>[\o"NVIDIA,2010#13"1]所示，NVIDIA每一代GPU的内存带宽也比Intel同等价位的CPU要高许多。同样的，这种差距也在逐代扩大，NVIDIA的GeForceGTX480的理论内存带宽接近180GB/s，而Intel的Bloomfield只有40GB/s不到。为什么GPU的性能增长比CPU更加快速？半导体制造技术的进步在两种平台上都是一样的。造成这种不同的主要原因可以归结为根本的硬件体系结构的差异：CPU为了最优化运行顺序代码的性能，将许多的晶体管运用于利用指令级并行（instruction-levelparallelism，ILP）技术，比如分支预测和乱序执行。而图形程序高度数据并行（data-levelparallelism）的性质使得GPU的设计将更多的晶体管直接运用于计算，从而达到了单位晶体管更高的运算密集度，如REF_Ref344456487\h错误!未找到引用源。ADDINEN.CITE<EndNote><Cite><Author>NVIDIA</Author><Year>2010</Year><RecNum>13</RecNum><DisplayText>[1]</DisplayText><record><rec-number>13</rec-number><foreign-keys><keyapp="EN"db-id="vfwsswdpydftfherdv2x0a5vw9rr5r5prtaz">13</key></foreign-keys><ref-typename="ElectronicBook">44</ref-type><contributors><authors><author>NVIDIA</author></authors></contributors><titles><title>NVIDIACUDAProgrammingGuide</title></titles><dates><year>2010</year></dates><urls></urls></record></Cite></EndNote>[\o"NVIDIA,2010#13"1]所示。编程模型和体系结构现代GPU不仅计算能力强大，而且也在其上进行通用编程也越来越方便。现在GPU的设计者针对通用计算编程模型如CUDA，OpenCL进行设计。这两个计算模型大同小异，术语分歧却很多，为了避免术语的混乱，以下如无特别说明，编程模型默认使用CUDA的术语。CUDA显示的GPU体系结构如图4ADDINEN.CITE<EndNote><Cite><Author>Aamodt</Author><Year>2012</Year><RecNum>14</RecNum><DisplayText>[2]</DisplayText><record><rec-number>14</rec-number><foreign-keys><keyapp="EN"db-id="vfwsswdpydftfherdv2x0a5vw9rr5r5prtaz">14</key></foreign-keys><ref-typename="WebPage">12</ref-type><contributors><authors><author>TorAamodt</author></authors></contributors><titles><title>GPGPU-Sim3.x:APerformanceSimulatorforManycoreAcceleratorResearch</title></titles><dates><year>2012</year></dates><publisher>MICRO2012Tutorial</publisher><urls></urls></record></Cite></EndNote>[\o"Aamodt,2012#14"2]所示。CUDA程序从CPU开始执行，然后会加载并行的计算核（computekernel）到GPU上。每次核加载会分发许多线程，这些线程构成一种层级关系，一个线程网格（grid）由许多线程块（block）构成，而一个block又由许多标量线程（thread）构成，这些标量线程运行核程序处理众多数据中的数据单元，如图5ADDINEN.CITE<EndNote><Cite><Author>NVIDIA</Author><Year>2010</Year><RecNum>13</RecNum><DisplayText>[1]</DisplayText><record><rec-number>13</rec-number><foreign-keys><keyapp="EN"db-id="vfwsswdpydftfherdv2x0a5vw9rr5r5prtaz">13</key></foreign-keys><ref-typename="ElectronicBook">44</ref-type><contributors><authors><author>NVIDIA</author></authors></contributors><titles><title>NVIDIACUDAProgrammingGuide</title></titles><dates><year>2010</year></dates><urls></urls></record></Cite></EndNote>[\o"NVIDIA,2010#13"1]所示。Block作为单个工作单元分配到一个单指令，多线程（SIMT,single-instruction,multiplethread）ADDINEN.CITE<EndNote><Cite><Author>Lindholm</Author><Year>2008</Year><RecNum>15</RecNum><DisplayText>[3]</DisplayText><record><rec-number>15</rec-number><foreign-keys><keyapp="EN"db-id="vfwsswdpydftfherdv2x0a5vw9rr5r5prtaz">15</key></foreign-keys><ref-typename="JournalArticle">17</ref-type><contributors><authors><author>ErikLindholm</author><author>JohnNickolls</author><author>StuartOberman</author><author>JohnMontrym</author></authors></contributors><titles><title>NVIDIATesla:AUnifiedGraphicsandComputingArchitecture</title><secondary-title>IEEEMicro</secondary-title></titles><periodical><full-title>IEEEMicro</full-title></periodical><pages>39-55</pages><volume>28</volume><number>2</number><dates><year>2008</year></dates><isbn>0272-1732</isbn><urls></urls><custom1>1373197</custom1><electronic-resource-num>10.1109/mm.2008.31</electronic-resource-num></record></Cite></EndNote>[\o"Lindholm,2008#15"3]核心上。一个block中的线程通过核心上的共享内存（sharedmemory）通信。SIMT核心访问全局的缓存和DRAM内存。图SEQ图\*ARABIC1CPU和GPU每秒浮点数运算次数图SEQ图\*ARABIC2CPU和GPU的内存带宽图SEQ图\*ARABIC3GPU将更多的晶体管运用于数据处理，绿色代表计算单元，面积代表使用的晶体管数量图4CUDA编程模型显示的GPU体系结构图5Grid由block构成体系结构现代GPU，例如NVIDIA的FermiADDINEN.CITE<EndNote><Cite><Author>NVIDIA</Author><Year>2009</Year><RecNum>16</RecNum><DisplayText>[4]</DisplayText><record><rec-number>16</rec-number><foreign-keys><keyapp="EN"db-id="vfwsswdpydftfherdv2x0a5vw9rr5r5prtaz">16</key></foreign-keys><ref-typename="Report">27</ref-type><contributors><authors><author>NVIDIA</author></authors></contributors><titles><title>NVIDIA'sNextGenerationCUDAComputeArchitecture:Fermi</title></titles><dates><year>2009</year></dates><urls></urls></record></Cite></EndNote>[\o"NVIDIA,2009#16"4]，由许多核心（StreamingMultiprocessor，SM，也即SIMT核心）组成，如图6ADDINEN.CITE<EndNote><Cite><Author>NVIDIA</Author><Year>2009</Year><RecNum>16</RecNum><DisplayText>[4]</DisplayText><record><rec-number>16</rec-number><foreign-keys><keyapp="EN"db-id="vfwsswdpydftfherdv2x0a5vw9rr5r5prtaz">16</key></foreign-keys><ref-typename="Report">27</ref-type><contributors><authors><author>NVIDIA</author></authors></contributors><titles><title>NVIDIA'sNextGenerationCUDAComputeArchitecture:Fermi</title></titles><dates><year>2009</year></dates><urls></urls></record></Cite></EndNote>[\o"NVIDIA,2009#16"4]所示。每个核心的内部结构如图7ADDINEN.CITE<EndNote><Cite><Author>Hennessy</Author><Year>2012</Year><RecNum>11</RecNum><DisplayText>[5]</DisplayText><record><rec-number>11</rec-number><foreign-keys><keyapp="EN"db-id="vfwsswdpydftfherdv2x0a5vw9rr5r5prtaz">11</key></foreign-keys><ref-typename="ElectronicBook">44</ref-type><contributors><authors><author>Hennessy,JohnL.</author><author>Patterson,DavidA.</author><author>Asanovic,Krste</author></authors></contributors><titles><title>ComputerArchitecture:AQuantitativeApproach</title></titles><edition>5th</edition><keywords><keyword>Computerarchitecture.</keyword><keyword>Electronicbooks.</keyword></keywords><dates><year>2012</year></dates><pub-location>Amsterdam;Boston,MA</pub-location><publisher>MorganKaufmann/Elsevier</publisher><isbn>9780123838735 0123838738</isbn><accession-num>002008368</accession-num><urls><related-urls><url>/lib/mitlibraries/docDetail.action?docID=10506454</url></related-urls></urls></record></Cite></EndNote>[\o"Hennessy,2012#11"5]所示。每个核心包含许多并行通道（SIMDlane，或称为CUDAcore），一条指令发送到所有lane，这条指令在每个lane上重复执行。Fermi将32个标量线程组成Warp，一次调度执行一个Warp中的一条指令。Warp的组成没有被编程模型暴露，程序员指定线程块（也被称为cooperatingthreadarray，CTA），而这些线程块则由许多Warp组成。图6NVIDIAFermi，红色框代表一个SIMT核心。16个核心（SM）围绕L2Cache布置，每个核心包含调度器和分派（橙色），执行单元（绿色），寄存器和L1Cache（蓝色部分）图7SIMD处理器的简化块状图，它包含了16个SIMDlane。假设Warp调度器有48个不同的指令，那么它使用一张包含48个PC的表进行调度图8现代GPU上一个核心的微体系结构，N=#Warps/Core，W=#ThreadsinaWarp微体系结构更详细的现代GPU的微体系结构如图8ADDINEN.CITE<EndNote><Cite><Author>Fung</Author><Year>2011</Year><RecNum>5</RecNum><DisplayText>[6]</DisplayText><record><rec-number>5</rec-number><foreign-keys><keyapp="EN"db-id="vfwsswdpydftfherdv2x0a5vw9rr5r5prtaz">5</key></foreign-keys><ref-typename="ConferencePaper">47</ref-type><contributors><authors><author>WilsonW.L.Fung</author><author>TorM.Aamodt</author></authors></contributors><titles><title>ThreadblockcompactionforefficientSIMTcontrolflow</title><secondary-title>Proceedingsofthe2011IEEE17thInternationalSymposiumonHighPerformanceComputerArchitecture</secondary-title></titles><pages>25-36</pages><dates><year>2011</year></dates><publisher>IEEEComputerSociety</publisher><urls></urls><custom1>2014893</custom1></record></Cite></EndNote>[\o"Fung,2011#5"6]所示，这是Fung等人ADDINEN.CITE<EndNote><Cite><Author>Fung</Author><Year>2011</Year><RecNum>5</RecNum><DisplayText>[6]</DisplayText><record><rec-number>5</rec-number><foreign-keys><keyapp="EN"db-id="vfwsswdpydftfherdv2x0a5vw9rr5r5prtaz">5</key></foreign-keys><ref-typename="ConferencePaper">47</ref-type><contributors><authors><author>WilsonW.L.Fung</author><author>TorM.Aamodt</author></authors></contributors><titles><title>ThreadblockcompactionforefficientSIMTcontrolflow</title><secondary-title>Proceedingsofthe2011IEEE17thInternationalSymposiumonHighPerformanceComputerArchitecture</secondary-title></titles><pages>25-36</pages><dates><year>2011</year></dates><publisher>IEEEComputerSociety</publisher><urls></urls><custom1>2014893</custom1></record></Cite></EndNote>[\o"Fung,2011#5"6]根据最近的专利ADDINEN.CITEADDINEN.CITE.DATA[\o"Coon;BrettW.(SanJose,2008#18"7-9]定义的。这个图做了一些简化：假设取指单元每次都能命中指令缓存，不允许并发执行同一个warp中的不同指令，即一个warp中的指令按次序执行。每个SIMT核心逐时钟周期交错执行最多N个Warp。每个Warp在取指单元内有一个程序计数器（PC，图8中的eq\o\ac(○,1)），在instructionbuffer（I-Buffer）中有一个槽（eq\o\ac(○,2)），以及一个栈（eq\o\ac(○,3)）来管理分支这个warp内的发散（branchdivergence）。I-Buffer中每个槽（eq\o\ac(○,2)）有一个v-bit标示该槽是否有指令存在，一个r-bit标示是否已经可以执行（eq\o\ac(○,2)），即指令中依赖的源数据已经计算好。每个时钟周期取指单元为一个有空槽（eq\o\ac(○,2)）的warp选择PC，从instructioncache中取得相应的指令。这条指令被译码（eq\o\ac(○,6)）后放入I-Buffer的空槽中。这条指令在I-Buffer中等待直到它的r-bit（eq\o\ac(○,2)）被scoreboard（eq\o\ac(○,7)）设置，表明该warp中之前的指令已被执行完毕。一个warp中的指令顺序执行。这是简化的模型，事实上可以改进这个scoreboard用来追踪每个warp的寄存器依赖ADDINEN.CITE<EndNote><Cite><Author>al</Author><Year>2008</Year><RecNum>18</RecNum><DisplayText>[7]</DisplayText><record><rec-number>18</rec-number><foreign-keys><keyapp="EN"db-id="vfwsswdpydftfherdv2x0a5vw9rr5r5prtaz">18</key></foreign-keys><ref-typename="Patent">25</ref-type><contributors><authors><author><styleface="normal"font="Arial"size="100%">Coon;BrettW.(SanJose,CA),Mills;PeterC.(SanJose,CA),Oberman;StuartF.(Sunnyvale,CA),Siu;MingY.(Sunnyvale,CA)</style></author></authors></contributors><titles><title>Trackingregisterusageduringmultithreadedprocessingusingascoreboardhavingseparatememoryregionsandstoringsequentialregistersizeindicators</title></titles><dates><year>2008</year><pub-dates><date>October7</date></pub-dates></dates><publisher>NVIDIACorporation(SantaClara,CA)</publisher><urls></urls></record></Cite></EndNote>[\o"Coon;BrettW.(SanJose,2008#18"7]，从而可以让一个warp的多条指令同时在流水线中执行。发出逻辑（issuelogic，eq\o\ac(○,9)）从I-Buffer中选择一个已可以执行的Warp指令发出以执行。当一个指令发出时，它从分支单元中取得相应warp的重聚栈（reconvergencestack）顶端的活动掩码（activemask，eq\o\ac(○,10)）。这个掩码禁止由于分支发散不能执行的线程执行。当一个warp的分支指令被译码后，直到分支指令的结果知道后才能执行这个warp中的其它指令。一旦指令发出（eq\o\ac(○,11)），I-Buffer中相应的槽被标记为无效（v-bitreset），通知取指单元可以取得这个warp中的下一条指令了。发出的指令从寄存器中取得操作数，然后该指令被相应的流水线执行（ALUeq\o\ac(○,12)或MEMeq\o\ac(○,13)）。指令将其执行结果写入寄存器并通知scoreboard（eq\o\ac(○,8)）。Scoreboard然后更新相应warp中的下一条指令的r-bit（eq\o\ac(○,2)）。当一条内存指令执行时（eq\o\ac(○,13)），地址生成器（addressgenerationunit，AGU）为warp中的每个线程生成地址。对于共享内存，内存冲突处理单元（bankconflicthandlingunit）保证依次执行冲突访问。对全局内存ADDINEN.CITE<EndNote><Cite><Author>NVIDIA</Author><Year>2010</Year><RecNum>13</RecNum><DisplayText>[1]</DisplayText><record><rec-number>13</rec-number><foreign-keys><keyapp="EN"db-id="vfwsswdpydftfherdv2x0a5vw9rr5r5prtaz">13</key></foreign-keys><ref-typename="ElectronicBook">44</ref-type><contributors><authors><author>NVIDIA</author></authors></contributors><titles><title>NVIDIACUDAProgrammingGuide</title></titles><dates><year>2010</year></dates><urls></urls></record></Cite></EndNote>[\o"NVIDIA,2010#13"1]，访问合并单元（accesscoalescingunit）将不同lane对相同cache行的访问合并成一个宽访问，数据缓存一个时钟周期处理一个宽访问。图9IntelHDGraphics的分支屏蔽，每个线程有自己独立的PC，当该PC与整个warp的PC不同时屏蔽这个线程的执行，图中B5执行，而Exit被屏蔽。发散的控制流尽管GPU使用SIMD执行，但这个执行模型允许每个线程遵循自己的逻辑控制流。允许每个线程独立执行分支的基本机制是，硬件生成活动掩码（activemask，eq\o\ac(○,3)）表明哪些线程是活动的哪些不是。由于SIMD的控制，不活动的线程仍然执行操作，但是计算结果被屏蔽并丢弃。Warp调度器维护一个整个warp的PC，并且跟踪每个线程的逻辑PC。当发出一条指令时，硬件屏蔽那些不在执行整个warp当前的PC指向的指令的线程的操作。有两种常见的维护每个线程逻辑PC的方法。第一种，也是Intel的SandyBridgeADDINEN.CITE<EndNote><Cite><Author>Diamos</Author><Year>2011</Year><RecNum>6</RecNum><DisplayText>[10,11]</DisplayText><record><rec-number>6</rec-number><foreign-keys><keyapp="EN"db-id="vfwsswdpydftfherdv2x0a5vw9rr5r5prtaz">6</key></foreign-keys><ref-typename="ConferencePaper">47</ref-type><contributors><authors><author>GregoryDiamos</author><author>BenjaminAshbaugh</author><author>SubramaniamMaiyuran</author><author>AndrewKerr</author><author>HaichengWu</author><author>SudhakarYalamanchili</author></authors></contributors><titles><title>SIMDre-convergenceatthreadfrontiers</title><secondary-title>Proceedingsofthe44thAnnualIEEE/ACMInternationalSymposiumonMicroarchitecture</secondary-title></titles><pages>477-488</pages><dates><year>2011</year></dates><pub-location>PortoAlegre,Brazil</pub-location><publisher>ACM</publisher><urls></urls><custom1>2155676</custom1><electronic-resource-num>10.1145/2155620.2155676</electronic-resource-num></record></Cite><Cite><Author>Intel</Author><Year>2010</Year><RecNum>12</RecNum><record><rec-number>12</rec-number><foreign-keys><keyapp="EN"db-id="vfwsswdpydftfherdv2x0a5vw9rr5r5prtaz">12</key></foreign-keys><ref-typename="ElectronicBook">44</ref-type><contributors><authors><author>Intel</author></authors></contributors><titles><title>IntelHDGraphicsOpenSourceProgrammerReferenceManual</title></titles><dates><year>2010</year><pub-dates><date>June</date></pub-dates></dates><urls></urls></record></Cite></EndNote>[\o"Diamos,2011#6"10,\o"Intel,2010#12"11]上的GPU采用的，为每个线程维护一个单独的PC，屏蔽那些与当前整个warp的PC不同的线程，如图9ADDINEN.CITE<EndNote><Cite><Author>Intel</Author><Year>2010</Year><RecNum>12</RecNum><DisplayText>[11]</DisplayText><record><rec-number>12</rec-number><foreign-keys><keyapp="EN"db-id="vfwsswdpydftfherdv2x0a5vw9rr5r5prtaz">12</key></foreign-keys><ref-typename="ElectronicBook">44</ref-type><contributors><authors><author>Intel</author></authors></contributors><titles><title>IntelHDGraphicsOpenSourceProgrammerReferenceManual</title></titles><dates><year>2010</year><pub-dates><date>June</date></pub-dates></dates><urls></urls></record></Cite></EndNote>[\o"Intel,2010#12"11]所示，当前整个warp执行到指令B5，所以执行到Exit的线程被屏蔽。NVIDIA和AMD的GPU使用另一种方式，将活动掩码存储到重聚栈（eq\o\ac(○,10)）上，下面解释这种方法。当一个分支指令执行时，如果一个warp中不同的线程有不同的结果，即分支发散，新的条目就会被压到重聚栈（eq\o\ac(○,3)）上。每个条目的重聚PC（RPC）被设置为分支的最接近的post-dominator（PDOM），也就是所有分支控制流在退出程序前都必须经过的最早的点。活动掩码的每个比特位表明相应线程是否遵循栈中该条目的控制流路径。栈顶的PC被送至取指单元，开始执行分支的目标路径上的指令。当下一条指令的PC与栈顶的RPC相同时，说明已经到了重聚点，此时栈顶条目被弹出ADDINEN.CITE<EndNote><Cite><Author>Erik</Author><Year>2008</Year><RecNum>17</RecNum><DisplayText>[8]</DisplayText><record><rec-number>17</rec-number><foreign-keys><keyapp="EN"db-id="vfwsswdpydftfherdv2x0a5vw9rr5r5prtaz">17</key></foreign-keys><ref-typename="Patent">25</ref-type><contributors><authors><author>Coon;BrettW.;Lindholm;JohnErik</author></authors></contributors><titles><title>SystemandmethodformanagingdivergentthreadsinaSIMDarchitecture</title></titles><dates><year>2008</year><pub-dates><date>April1</date></pub-dates></dates><publisher>NVIDIACorporation</publisher><orig-pub>7353369</orig-pub><urls></urls></record></Cite></EndNote>[\o"Erik,2008#17"8]。举例来说，如图10ADDINEN.CITE<EndNote><Cite><Author>Rhu</Author><Year>2012</Year><RecNum>2</RecNum><DisplayText>[12]</DisplayText><record><rec-number>2</rec-number><foreign-keys><keyapp="EN"db-id="vfwsswdpydftfherdv2x0a5vw9rr5r5prtaz">2</key></foreign-keys><ref-typename="ConferencePaper">47</ref-type><contributors><authors><author>MinsooRhu</author><author>MattanErez</author></authors></contributors><titles><title>CAPRI:predictionofcompaction-adequacyforhandlingcontrol-divergenceinGPGPUarchitectures</title><secondary-title>Proceedingsofthe39thAnnualInternationalSymposiumonComputerArchitecture</secondary-title></titles><pages>61-71</pages><dates><year>2012</year></dates><pub-location>Portland,Oregon</pub-location><publisher>IEEEComputerSociety</publisher><urls></urls><custom1>2337167</custom1></record></Cite></EndNote>[\o"Rhu,2012#2"12]所示，当一个warp被执行前，栈顶条目被初始化成全掩码（fullmask），下个PC被设置成第一个基本块（图10（a）中的路径A）的第一条指令。注意每个warp的实际PC由warp调度器维护，栈中的PC是用来追踪重聚点用的。每次当一个warp执行一条发散的条件分支时，真值路径和假值路径的活动掩码都会被计算，然后栈中条目会被更新，如图10（b）所示，首先，栈顶条目中下条PC项会被更新成重聚点的PC，即当warp重聚后，使用当前活动掩码执行的下条指令。接着，假值路径的掩码，下个PC，以及重聚PC（RPC）信息被压到栈上，紧接着真值路径的信息也被压栈。因此，一个分支语句结束后，硬件先执行真值路径上的指令，屏蔽掉假值路径上的线程。注意如果warp没有发散则不需要改变重聚栈，因为warp中的所有线程可以继续用相同的PC执行。图10表明如何使用warp-widepost-dominator（WPDOM）来处理分支发散。每个线程块（block，也称CTA）由两个warp构成，每个warp由4个线程组成。每个基本控制块包含两条指令，执行一条指令需要一个时钟周期。活动掩码中的数值表示在执行那条路径的线程ID，x表示线程被屏蔽（为了表示清楚使用数字，真正的硬件使用比特位）当真值路径上的所有线程执行完该路径所有指令后，栈顶条目的下个PC与RPC匹配，这个条目出栈。此时，开始执行假值路径上的指令（图10（c））。当warp的PC再次与RPC相同时，栈顶条目再次出栈，线程重聚，恢复无发散的执行（图10（d））。这个算法很好地处理了嵌套的发散分支。当遇到另一个发散的条件分支，一对新的真假值掩码和PC被压入栈中，这些与栈顶掩码进行AND操作，这样栈顶条目正确地表示当前被调度执行的warp。然而，每次发散都会使得活动线程减少，被浪费的执行单元增加，SIMDlane的使用率降低。一些方案ADDINEN.CITEADDINEN.CITE.DATA[\o"Fung,2011#5"6,\o"Rhu,2012#2"12-14]被提出来缓解这个问题，下面我们讨论这些方案。高效控制流执行方案在这一节中，我们来讨论一下用来提高SIMDlane使用率的几种方案。DynamicWarpFormationDynamicWarpFormation（DWF）将执行相同指令的线程重新分组来提高SIMD效率。Fung等人验证了DWF可以带来20.7%的性能提高，估算需增加4.7%的芯片面积开销ADDINEN.CITE<EndNote><Cite><Author>Fung</Author><Year>2007</Year><RecNum>3</RecNum><DisplayText>[13]</DisplayText><record><rec-number>3</rec-number><foreign-keys><keyapp="EN"db-id="vfwsswdpydftfherdv2x0a5vw9rr5r5prtaz">3</key></foreign-keys><ref-typename="ConferencePaper">47</ref-type><contributors><authors><author>WilsonW.L.Fung</author><author>IvanSham</author><author>GeorgeYuan</author><author>TorM.Aamodt</author></authors></contributors><titles><title>DynamicWarpFormationandSchedulingforEfficientGPUControlFlow</title><secondary-title>Proceedingsofthe40thAnnualIEEE/ACMInternationalSymposiumonMicroarchitecture</secondary-title></titles><pages>407-420</pages><dates><year>2007</year></dates><publisher>IEEEComputerSociety</publisher><urls></urls><custom1>1331735</custom1><electronic-resource-num>10.1109/micro.2007.12</electronic-resource-num></record></Cite></EndNote>[\o"Fung,2007#3"13]。图11ADDINEN.CITE<EndNote><Cite><Author>Fung</Author><Year>2007</Year><RecNum>3</RecNum><DisplayText>[13]</DisplayText><record><rec-number>3</rec-number><foreign-keys><keyapp="EN"db-id="vfwsswdpydftfherdv2x0a5vw9rr5r5prtaz">3</key></foreign-keys><ref-typename="ConferencePaper">47</ref-type><contributors><authors><author>WilsonW.L.Fung</author><author>IvanSham</author><author>GeorgeYuan</author><author>TorM.Aamodt</author></authors></contributors><titles><title>DynamicWarpFormationandSchedulingforEfficientGPUControlFlow</title><secondary-title>Proceedingsofthe40thAnnualIEEE/ACMInternationalSymposiumonMicroarchitecture</secondary-title></titles><pages>407-420</pages><dates><year>2007</year></dates><publisher>IEEEComputerSociety</publisher><urls></urls><custom1>1331735</custom1><electronic-resource-num>10.1109/micro.2007.12</electronic-resource-num></record></Cite></EndNote>[\o"Fung,2007#3"13]阐明了这个想法。在图中，8个标量线程组成两个warp（W0和W1）运行右边图中的分支。每个时钟周期用一个矩形表示，矩形中的箭头表示一个warp中的标量线程。实心箭头表示执行代码块A，空心箭头表示执行代码块B。图中上半部分的SIMD流水线在分支发散后没有充分利用。下半部分在分支发散后，重组成新的warp（W2和W3），DWF这种方法使得流水线被充分利用起来。Fung等人对实现有很细致的描述ADDINEN.CITE<EndNote><Cite><Author>Fung</Author><Year>2007</Year><RecNum>3</RecNum><DisplayText>[13]</DisplayText><record><rec-number>3</rec-number><foreign-keys><keyapp="EN"db-id="vfwsswdpydftfherdv2x0a5vw9rr5r5prtaz">3</key></foreign-keys><ref-typename="ConferencePaper">47</ref-type><contributors><authors><author>WilsonW.L.Fung</author><author>IvanSham</author><author>GeorgeYuan</author><author>TorM.Aamodt</author></authors></contributors><titles><title>DynamicWarpFormationandSchedulingforEfficientGPUControlFlow</title><secondary-title>Proceedingsofthe40thAnnualIEEE/ACMInternationalSymposiumonMicroarchitecture</secondary-title></titles><pages>407-420</pages><dates><year>2007</year></dates><publisher>IEEEComputerSociety</publisher><urls></urls><custom1>1331735</custom1><electronic-resource-num>10.1109/micro.2007.12</electronic-resource-num></record></Cite></EndNote>[\o"Fung,2007#3"13]。图11一个DWF例子ThreadBlockCompaction图12DWF因为调度策略而饥饿的例子。阴影部分表示活动线程，空白表示非活动线程。右边上面部分表示基于重聚栈的执行流，中间部分表示DWF在warp调度顺序为W0-B，W1-B，W0-C，W1-C下的情况，SIMD的使用率增加。而下半部分表示warp调度顺序为W0-B，W1-B，W0-D，W1-D，W0-C，W1-C，DWF迟迟得不到合并warp的机会。DWF在多线程SIMD处理器上捕获了很大一部分多指令，多数据（multiple-instruction，multipledata，MIMD）硬件的益处。但是，DWF的效果受到调度策略ADDINEN.CITE<EndNote><Cite><Author>Fung</Author><Year>2009</Year><RecNum>1</RecNum><DisplayText>[13,15]</DisplayText><record><rec-number>1</rec-number><foreign-keys><keyapp="EN"db-id="vfwsswdpydftfherdv2x0a5vw9rr5r5prtaz">1</key></foreign-keys><ref-typename="JournalArticle">17</ref-type><contributors><authors><author>WilsonW.L.Fung</author><author>IvanSham</author><author>GeorgeYuan</author><author>TorM.Aamodt</author></authors></contributors><titles><title>Dynamicwarpformation:EfficientMIMDcontrolflowonSIMDgraphicshardware</title><secondary-title>ACMTrans.Archit.CodeOptim.</secondary-title></titles><periodical><full-title>ACMTrans.Archit.CodeOptim.</full-title></periodical><pages>1-37</pages><volume>6</volume><number>2</number><dates><year>2009</year></dates><isbn>1544-3566</isbn><urls></urls><custom1>1543756</custom1><electronic-resource-num>10.1145/1543753.1543756</electronic-resource-num></record></Cite><Cite><Author>Fung</Author><Year>2007</Year><RecNum>3</RecNum><record><rec-number>3</rec-number><foreign-keys><keyapp="EN"db-id="vfwsswdpydftfherdv2x0a5vw9rr5r5prtaz">3</key></foreign-keys><ref-typename="ConferencePaper">47</ref-type><contributors><authors><author>WilsonW.L.Fung</author><author>IvanSham</author><author>GeorgeYuan</author><author>TorM.Aamodt</author></authors></contributors><titles><title>DynamicWarpFormationandSchedulingforEfficientGPUControlFlow</title><secondary-title>Proceedingsofthe40thAnnualIEEE/ACMInternationalSymposiumonMicroarchitecture</secondary-title></titles><pages>407-420</pages><dates><year>2007</year></dates><publisher>IEEEComputerSociety</publisher><urls></urls><custom1>1331735</custom1><electronic-resource-num>10.1109/micro.2007.12</electronic-resource-num></record></Cite></EndNote>[\o"Fung,2007#3"13,\o"Fung,2009#1"15]的很大影响，如图12ADDINEN.CITE<EndNote><Cite><Author>Fung</Author><Year>2011</Year><RecNum>5</RecNum><DisplayText>[6]</DisplayText><record><rec-number>5</rec-number><foreign-keys><keyapp="EN"db-id="vfwsswdpydftfherdv2x0a5vw9rr5r5prtaz">5</key></foreign-keys><ref-typename="ConferencePaper">47</ref-type><contributors><authors><author>WilsonW.L.Fung</author><author>TorM.Aamodt</author></authors></contributors><titles><title>ThreadblockcompactionforefficientSIMTcontrolflow</title><secondary-title>Proceedingsofthe2011IEEE17thInternationalSymposiumonHighPerformanceComputerArchitecture</secondary-title></titles><pages>25-36</pages><dates><year>2011</year></dates><publisher>IEEEComputerSociety</publisher><urls></urls><custom1>2014893</custom1></record></Cite></EndNote>[\o"Fung,2011#5"6]所示。另外，DWF在试图优化控制流的同时也可能增加访问内存的开销，如图13ADDINEN.CITE<EndNote><Cite><Author>Fung</Author><Year>2011</Year><RecNum>5</RecNum><DisplayText>[6]</DisplayText><record><rec-number>5</rec-number><foreign-keys><keyapp="EN"db-id="vfwsswdpydftfherdv2x0a5vw9rr5r5prtaz">5</key></foreign-keys><ref-typename="ConferencePaper">47</ref-type><contributors><authors><author>WilsonW.L.Fung</author><author>TorM.Aamodt</author></authors></contributors><titles><title>ThreadblockcompactionforefficientSIMTcontrolflow</title><secondary-title>Proceedingsofthe2011IEEE17thInternationalSymposiumonHighPerformanceComputerArchitecture</secondary-title></titles><pages>25-36</pages><dates><year>2011</year></dates><publisher>IEEEComputerSociety</publisher><urls></urls><custom1>2014893</custom1></record></Cite></EndNote>[\o"Fung,2011#5"6]所示。为了克服这些问题Fung等人又提出了一种方案ThreadBlockCompaction（TBC）ADDINEN.CITE<EndNote><Cite><Author>Fung</Author><Year>2011</Year><RecNum>5</RecNum><DisplayText>[6]</DisplayText><record><rec-number>5</rec