WIXLIB

CUDAOpenCLthreadwarpthread blockgridlocal memoryshared memoryglobal memoryscalar coremulti-processor (SM)work item—work groupindex spaceprivate memorylocal memoryglobal memoryprocessing elementcompute unitTable 1: Equivalent terminologies between CUDAand OpenCL are listed here. Although we make useof NVIDIA hardware and ‘C’ for CUDA terminologies in this paper, the same discussion can be extended to GPUs from other vendors using OpenCL.bypassing the hardware scheduler altogether. To circumventthese limitations, developers have used a PT style and itslower level of abstraction to gain performance by directlycontrolling scheduling.2.1.1Core Limitations of GPGPU ProgrammingA brief summary of other major characteristics of the current GPGPU programming style, many of which impact performance and are directly targeted by the Persistent Threadsprogramming style, are outlined below:1. Host-Device Interface:Master-slave processing: Only the host (master) processor has the ability to issue commands for data movement, synchronization, and execution on the deviceoutside of a kernel.Kernel size: The dimensions of a block, and the number of blocks per kernel invocation, are passed as launchconfiguration parameters to the kernel invocation API.2. Device-side Properties:Lifetime of a block: Every block is assumed to perform its function independent of other blocks, and retire upon completion of its task.Hardware scheduler: The hardware manages a list ofyet-to-be executed blocks and automatically schedulesthem onto a multi-processor (SM) at runtime. Asscheduling is a runtime decision, the programming styleo ers no guarantees of when or where a block will bescheduled.Block state: When a new block is mapped onto a particular SM, the old state (register and shared memory)on that SM is considered stale, disallowing any communication between blocks, even when run on the sameSM.3. Memory Consistency:Intra-block: Threads within a block communicate datavia either local (per-block) or global (DRAM) memory. Memory consistency is guaranteed between twosections within a block if they are separated by anappropriate intrinsic function (typically a block-widebarrier).Inter-block: The only mechanism for inter-block communication is global memory. Because blocks are independent and their execution order is undefined, themost common method for communicating between blocksis to cause a global synchronization by ending a kerneland starting a new one. Inter-block communicationthrough atomic memory operations is also an option,but may not be suitable or deliver sufficient performance for some application scenarios.4. Kernel Invocations:Producer-consumer: Due to the restrictions imposedon inter-block data sharing, kernels can only producedata as they run to completion. Consuming data onthe GPU produced by this kernel requires another kernel.Spawning kernels: A kernel cannot invoke another copyof itself (recursion), spawn other kernels, or dynamically add more blocks. This is especially costly in caseswhere data reuse exists between invocations.2.2Persistent Threads Programming StyleThe requirement imposed by the nonPT programmingstyle of dividing a workload into several blocks, more thancan physically reside simultaneously at kernel launch time,is a design choice of the programming style, and not dueto some constraint imposed by the SM. From a hardwareperspective, threads are active throughout the execution ofa kernel. This di ers from a developer’s perspective usingnonPT style coding guidelines by implying that as blocksrun to completion, threads corresponding to these blocksare “retired”, while a batch of threads are “launched” as newblocks are scheduled onto the SM.The Persistent Threads style of programming alters thenotion of the lifetime of virtual software threads, bringing them closer to execution lifetime of physical hardwarethreads, i.e. the developer’s view is that threads are activefor the entire duration of a kernel. This is achieved by twosimple modifications to kernel code: First, the virtualizationof hardware SMs is limited to the level shown in Figure 2(a),also referred to as maximal launch. Second, the lack of additional blocks shown in Figure 2(b) is compensated by employing work queues. Both these are described in greaterdetail below. The PT style of coding is much closer to howone would program CPUs or Intel’s Larrabee processor [14],which exposes the scheduler for the programmer to influence, if desired.1. Maximal Launch: A kernel uses at most asmany blocks as can be concurrently scheduledon the SM:Since each thread remains persistent throughout theexecution of a kernel, and is active across traditionalblock boundaries until no work remains, the programmer schedules only as many threads as the GPU SMscan concurrently run. This represents the upper boundon the number of threads with which a kernel canlaunch. The lower bound can be as small as the number of threads required to launch a single block. Inorder to distinguish nonPT and PT thread blocks, wewill refer to blocks in PT style programming as thread

GPU1201234567891011121314150123231010323201PT illustration012301233vertical motion blur;processed on a 4-SM GPU16 blocks mapped to the 4SMs in random order4 SMsHardware viewOutput Image0nonPT illustrationSoftware viewInput ImageA sample image of 64x64pixels divided into 16 blocks4 thread groupsFigure 3: An illustration of nonPT and PT programming styles through an example image of 64x64 pixelsundergoing vertical motion blur — In this example, 16x16 threads combine to form a block and process theimage in a set of 4x4 blocks. The GPU has four SMs labeled 0-3. We assume a load-balanced system whereeach SM runs one block at a time and four blocks each. For nonPT, the kernel launches with 16 blocks. At runtime the hardware non-deterministically schedules new blocks to SMs as other blocks complete. A PT kernellaunches at-most the number of blocks corresponding to ‘maximal launch’, which in this example correspondto four thread groups, along with a 16-entry work queue; with each entry in this queue representing a blockindex. Through the work queue, developers can control scheduling of blocks onto SMs. In this example,each SM processes all blocks within a vertical sub-section of the image, thus helping data-reuse as pixels areshared across vertical block boundaries.groups for the remainder of this paper. A thread grouphas the same dimensions as a thread block, but isformed by combining persistent threads launched atkernel invocation, processing work equivalent to zero,one, or many thread blocks, and remaining active untilno more work is left for the kernel to process.2. Software schedules work through work queues,not hardware:The traditional programming environment does notexpose the hardware scheduler to the programmer, thuslimiting the ability to exploit workload communicationpatterns. In contrast, the PT style bypasses the hardware scheduler by relying on a work queue of all blocksthat are to be processed for kernel execution to complete. When a block finishes, it checks the queue formore work and continues doing so until no work is left,at which point the block retires.Depending on the communication pattern exhibited bythe algorithm, the queue can either be static (known atcompile time) or dynamic (generated at runtime) andcan be used to control the order, location, and timingof the execution of each block. There are several kindsof optimizations one could incorporate in how work issubmitted and fetched from these queues – one example would be to incorporate distributed queues insteadof a global queue that could lead to optimal load balancing via work stealing/donating or a hybrid of thetwo approach. In this paper we focus on the base caseof a single queue which primarily as a FIFO.3.USE CASESOver the past two years, several researchers have used PTtechniques in their applications to improve performance. Wehave categorized these into four use cases, each of which aredescribed in detail in the following four subsections.PT-style programming lacks native hardware and programming API support. While past studies have shown PTto be advantageous, the benefits and limitations of hacking the nonPT model to fit into a PT style in software isnot well understood and documented, and therefore cannotbe universally applied to all scenarios. Although a handfulbenchmark suites are available for GPU computing [5, 6],these workloads primarily deal with performance at a higherlevel than we wanted for our analysis. Hence, apart fromdistinctly categorizing use cases in this paper, another contribution of this paper is the creation of an un-biased microkernel benchmark suite that future studies can use/compareagainst, and that vendors can use to evaluate future designs.For each use case, we give a brief introduction and citerelevant studies that have utilized the use case. We provide implementation details of our synthetic workloads followed by results and conclusions. We wrote our tests inboth OpenCL and CUDA. Specifically, since OpenCL provides the ability for fine-grain profiling, we wrote the firstuse case in OpenCL, and the remaining in CUDA. We ranall our use cases on an NVIDIA GeForce GTX2951 . Un1We also tested on a GTX580 (Fermi) and found the generaltrends were similar, even though we made heavy use of atomics and the Fermi architecture supposedly has better atomicsupport (atomics in Fermi happen in the L2 cache/shared

Use CaseScenarioAdvantage of Persistent ThreadsCPU-GPU SynchronizationKernel A produces a variable amountof data that must be consumed byKernel BLoad BalancingTraversing an irregularly-structured,hierarchical data structureMaintaining Active StateA kernel accumulates a single valueacross a large number of threads, orKernel A wants to pass data to KernelB through shared memory or registersGlobal synchronization within a kernel across thread blocksnonPT implementations require a round-trip communication to the host to launch Kernel B with the exactnumber of blocks corresponding to work items produced by Kernel A.PT implementations build an efficient queue to allowa single kernel to produce a variable amount of output per thread and load balance those outputs ontothreads for further processing.Because a PT kernel processes many more items perblock than a nonPT kernel, it can e ectively leverageshared memory across a larger block size for an application like a global reduction.In a nonPT kernel, synchronizing across blocks withina kernel is not possible because blocks run to completion and cannot wait for blocks that have not yet beenscheduled. The PT model ensures that all blocks areresident and thus allows global synchronization.Global SynchronizationTable 2: Summary of Persistent Threads use casesless otherwise stated, every block consists of 256 threadsin our experiments, and as a proxy for work per thread,we perform a varying number of fused multiply-add (FMA)operations on single-precision floating-point values. In thefollowing subsections, “more FMAs per item” is equivalentto “more work per item”. For each experiment, we implemented two versions of our synthetic benchmarks, nonPTand PT (both with equivalent functionality), to evaluateperformance and identify tradeo s. The four use cases areCPU-GPU synchronization, load balancing/irregular parallelism, producer-consumer locality, and global synchronization, which are summarized in Table 2.3.1CPU-GPU SynchronizationSince the CPU (host) and GPU (device) are coupled together as a master and slave, the device lacks the ability tosubmit work to itself. Outside of the functionality built intoa kernel, the device is dependent on the host for issuing alldata movement, execution and synchronization commands.In cases where a producer kernel generates a variable number of items for the consumer kernel to process at run time,the host must issue a readback, determine the number ofblocks needed to consume the intermediate data, and thenlaunch a new kernel. The readbacks have significant overhead, especially in systems where the host and device do notshare the same memory space or are not on the same chip.Boyer et al. present a systematic approach for acceleratingthe process of detecting and tracking in-vivo blood vessels ofleukocytes [3]. By modifying memory access patterns, reformulating the computations within the kernel, and fusing kernels to minimize the CPU-GPU synchronization overhead,they report a 60 speedup over the baseline naive implementation. Further, upon restructuring the computationsthat originally required 50,000 kernel invocations to just onePT invocation, they achieved a 211 speedup over the baseline. Tzeng et al. utilized a work-queue based task-donationstrategy for efficiently handling split and dice stages in theReyes pipeline [16]. Their work splits micropolygons of ascene into a variable number of patches at each step. Withmemory, not in DRAM).the nonPT traditional programming style, this would require a host readback of the number of patches to be splitin the next iteration. But by combining these two stagesinto a single uberkernel and wrapping it in a PT kernel,they eliminated the need for this readback and created aself-sustaining Reyes engine that efficiently handles their irregular workload.3.1.1ImplementationOverhead Characterization: In order to characterizethe overhead of host-device synchronization, we performeda timing analysis of the three steps involved, shown in redas the critical path in Figure 4-I: a blocking readback bythe host to determine the subsequent launch bounds, thehost overhead of generating configuration parameters for akernel with the appropriate number of items, and the kernellaunch time from the moment of issue to the moment thedevice starts the kernel.To obtain an accurate assessment of the synchronizationoverhead, we used the low-level profiling API, clGetEventProfilingInfo(), provided in OpenCL (CUDA does not provide the fine-grained control we need, hence why we did notimplement this use case in CUDA). This call provides fourinstances pertaining to when a call in the command queue isissued by the host, dispatched to the device execution queue,begins execution on the device, and the end time. For thisexperiment, we computed the time it takes from the momentthe producer kernel (GPU-kP ) ends to when the consumerkernel (GPU-kC ) starts.Persistent Threads Alternative: The PT alternativerequires two modifications. First, GPU’-kC is reformulatedto encapsulate the original kernel in a while loop, along withan atomic operation to either increment or decrement thenumber of items remaining. Second, the modified kernelis launched with a fixed number of blocks by the host, regardless of how many items are to be processed. When thework queue counter exceeds the item count in the case of anincremental queue or goes below zero in the case of a decremental queue, the corresponding block exits. At runtime,the last block of the GPU-kP writes the number of itemsGPU’-kP must process to a predefined GPU-accessible lo-

cation. GPU’-kP then uses this value as its terminal count.Thread groups retire once they reach this count.Both modifications outlined here in the PT formulationare sources of overhead. In order to further understand thisoverhead w.r.t. nonPT kernels, we created two syntheticworkloads, one that was compute-intensive (CI), and theother a combination of compute and memory (CMI) operations. For the CI kernel we read data from memory,perform a variable number of FMAs, and then write theresult to global memory. For the CMI kernel we performstrided access to memory for every iteration of FMA computation, committing the result to global memory after thepre-determined number of operations has been performed.In both cases, we unroll the FMA loop completely in orderto minimize loop overhead. For the nonPT case, the timeof execution is the sum of performing a synchronous datatransfer from GPU to CPU, and kernel execution.Results & Conclusions3.2Load Balancing / Irregular ParallelismEfficiently processing poorly-structured algorithms or irregular data-structures is a challenge on any compute device,but especially the GPU. Extracting parallelism on the GPU(c) GTX295 – Compute only(d) GTX295 – Compute Mem.Figure 5: Results from CPU-GPU Synchronizationon NVIDIA’s GeForce 9400M and GTX295.Initial Inputs# of levelsUsing empty kernels we measured the round-trip cost of asynchronized copy to the CPU and the launch on the GPUto be around 400 µs. In addition to running this use caseon a NVIDIA GTX295, we also ran it on a GeForce 9400Mprocessor. A more detailed analysis of PT vs. nonPT performance for a varying number of FMAs and blocks for ourworkloads on both the processors is shown in Figure 5.From Figure 5(a) we see that non-compute-intensive kernels benefit from a PT formulation. As the number of blocksto process increases, the atomic pressure increases considerably, resulting in a slowdown. As the arithmetic intensity ofthe amount of work processed per block increases, the PTformulation generally results in a speedup, eventually dipping below the nonPT baseline. In Figure 5(b) we see a different trend than for the CI case. While having fewer blocksresults in significant speedup with a small amount of workper thread, as this work increases, we transition to a considerable slowdown. We attribute this, in part, to the dropin occupancy, the ratio of number of thread groups startedat launched time to the theoretical maximum supported bythe hardware. As the number of iterations to be unrolledincreases, the compiler requires more registers, and is morerestricted in making optimizations within the while-loop forthe PT case.In stark contrast, we see a very distinct set of results forthese workloads on the GTX295. On both CI and CMIworkloads, the PT version is almost always slower than itsnonPT counterpart. The slowdown further increases as thenumber of blocks to process increase. The only reasonableexplanation we hypothesize for this is the cost of contentionfor atomics. The 9400M has only 2 SMs while the GTX295has 30.From these workloads we conclude that using PTto avoid CPU-GPU synchronization is beneficial forsmall workloads with few memory accesses and smallarithmetic intensity. Further, PT through softwareis better for kernels launching fewer thread groups,and where the cost of synchronization is a significantfraction of the overall cost of the application.(b) 9400M – Compute Mem.(a) Full ForestInitial Inputs# of levels3.1.2(a) 9400M – Compute only(b) Tilted ForestFigure 6: An illustration of our complete and tiltedforest.is left to the programmer, often requiring low-level controlroutines to be written in software. These workloads presenttwo important issues—vector processor efficiency and handling variable work items being consumed or produced, Ailaet al. present a thorough study of improving the efficiencyof processing the irregular the trace() phase in ray tracingon vector processors through PT [1]. Their solution for handling the varying depths of traversal for each ray was by using warp-wide blocks for avoiding a single ray holding severalwarps within a block hostage2 ,and bypassing the hardwarescheduler by the use of PT. Tzeng et al. [16] addressed the2We surmise that the large speedups seen by Aila et al.and other researchers in this area were in large part due towarp retirement serializatio

employing a GPU is governed by Amdahl’s Law, necessitat-ing the port of larger portions of an application to the GPU for achieving better overall application acceleration. As a wider variety of workloads are implemented on the GPU, many of which are highly irregular, limitations of GPU pro