Use of CABA for compression

We illustrate an important use case for the CABA framework: alleviating the memory bandwidth bottleneck by enabling flexible data compression in the memory hierarchy. The basic idea is to have assist warps that (1) compress cache blocks before they are written to memory, and (2) decompress cache blocks before they are placed into the cache.

CABA-based compression/decompression provides several benefits over a purely hardware-based implementation of data compression for memory. First, CABA primarily employs hardware that is already available on-chip but is otherwise underutilized. In contrast, hardware-only compression implementations require dedicated logic for specific algorithms. Each new algorithm (or a modification of an existing one) requires engineering effort and incurs hardware cost. Second, different applications tend to have distinct data patterns [15] that are more efficiently compressed with different compression algorithms. CABA offers versatility in algorithm choice as we find that many existing hardware-based compression algorithms (e.g., base-delta-immediate [BDI] compression [15], frequent pattern compression [FPC] [16], and C-Pack [17]) can be implemented using different assist warps with the CABA framework. Third, not all applications benefit from data compression. Some applications are constrained by other bottlenecks (e.g., oversubscription of computational resources) or may operate on data that is not easily compressible. As a result, the benefits of compression may not outweigh the cost in terms of additional latency and energy spent on compressing and decompressing data. In these cases, compression can be easily disabled by CABA, and the CABA framework can be used in other ways to alleviate the current bottleneck.

Other uses of CABA

The generality of CABA enables its use in alleviating other bottlenecks with different optimizations. We discuss two examples: (1) using assist warps to perform memoization to eliminate redundant computations that have the same or similar inputs [18–20], by storing the results of frequently performed computations in the main memory hierarchy (i.e., by converting the computational problem into a storage problem) and (2) using the idle memory pipeline to perform opportunistic prefetching to better overlap computation with memory access. Assist warps offer a hardware/software interface to implement hybrid prefetching algorithms [21] with varying degrees of complexity. We also briefly discuss other uses of CABA for (1) redundant multithreading, (2) speculative precomputation, (3) handling interrupts, and (4) profiling and instrumentation.

Contributions

The chapter makes the following contributions:

• It introduces the CABA framework, which can mitigate different bottlenecks in modern GPUs by using underutilized system resources for assist warp execution.

• It provides a detailed description of how our framework can be used to enable effective and flexible data compression in GPU memory hierarchies.

• It comprehensively evaluates the use of CABA for data compression to alleviate the memory bandwidth bottleneck. Our evaluations across a wide variety of applications from Mars [22], CUDA [23], Lonestar [24], and Rodinia [25] benchmark suites show that CABA-based compression on average (1) reduces memory bandwidth by 2.1×, (2) improves performance by 41.7%, and (3) reduces overall system energy by 22.2%.

• It discusses at least six other use cases of CABA that can improve application performance and system management, showing that CABA is a primary general framework for taking advantage of underutilized resources in modern GPU engines.

Unutilized compute resources

A GPU core employs fine-grained multithreading [32, 33] of warps, that is, groups of threads executing the same instruction, to hide long memory and arithmetic logic unit (ALU) operation latencies. If the number of available warps is insufficient to cover these long latencies, the core stalls or becomes idle. To understand the key sources of inefficiency in GPU cores, we conduct an experiment where we show the breakdown of the applications’ execution time spent on either useful work (active cycles) or stalling because of one of four reasons: compute, memory, data dependence stalls, and idle cycles. We also vary the amount of available off-chip memory bandwidth: (i) half (1/2 × BW), (ii) equal to (1 × BW), and (iii) double (2 × BW), the peak memory bandwidth of our baseline GPU architecture. Section 6 details our baseline architecture and methodology.

Fig. 2 shows the percentage of total issue cycles, divided into five components (as already described). The first two components—memory and compute stalls—are attributed to the main memory and ALU-pipeline structural stalls. These stalls are because of backed up pipelines due to oversubscribed resources that prevent warps from being issued to the respective pipelines. The third component (data dependence stalls) is due to data dependence stalls. These stalls prevent warps from issuing new instruction(s) when the previous instruction(s) from the same warp are stalled on long-latency operations (usually memory load operations). In some applications (e.g., dmr), special-function-unit (SFU) ALU operations that may take tens of cycles to finish are also the source of data dependence stalls. The fourth component, idle cycles, refers to idle cycles when either all the available warps are issued to the pipelines and not ready to execute their next instruction or the instruction buffers (IBs) are flushed due to a mispredicted branch. All these components are sources of inefficiency that cause the cores to be underutilized. The last component, active cycles, indicates the fraction of cycles during which at least one warp was successfully issued to the pipelines.

We make two observations from Fig. 2. First, compute, memory, and data dependence stalls are the major sources of underutilization in many GPU applications. We distinguish applications based on their primary bottleneck as either memory or compute bound. We observe that a majority of the applications in our workload pool (17 out of 27 studied) are memory bound, and bottlenecked by the off-chip memory bandwidth.

Second, for the memory-bound applications, we observe that the memory and data dependence stalls constitute a significant fraction (61%) of the total issue cycles on our baseline GPU architecture (1 × BW). This fraction goes down to 51% when the peak memory bandwidth is doubled (2 × BW) and increases significantly when the peak bandwidth is halved (1/2 × BW), indicating that limited off-chip memory bandwidth is a critical performance bottleneck for memory-bound applications. Some applications, for example, BFS, are limited by the interconnect bandwidth. In contrast, the compute-bound applications are primarily bottlenecked by stalls in the ALU pipelines. An increase or decrease in the off-chip bandwidth has little effect on the performance of these applications.

Unutilized on-chip memory

The occupancy of any GPU SM, that is, the number of threads running concurrently, is limited by a number of factors: (1) the available registers and shared memory, (2) the hard limit on the number of threads and thread-blocks per core, and (3) the number of thread-blocks in the application kernel. The limiting resource from the preceding leaves the other resources underutilized. This is because it is challenging, in practice, to achieve a perfect balance in utilization of all the preceding factors for different workloads with varying characteristics. Very often, the factor determining the occupancy is the thread or thread-block limit imposed by the architecture. In this case, many registers are left unallocated to any thread-block. Also, the number of available registers may not be a multiple of those required by each thread-block. The remaining registers are not enough to schedule an entire extra thread-block, which leaves a significant fraction of the register file and shared memory unallocated and unutilized by the thread-blocks. Fig. 3 shows the fraction of statically unallocated registers in a 128 KB register file (per SM) with a 1536 thread, 8 thread-block occupancy limit, for different applications. We observe that on average 24% of the register file remains unallocated. This phenomenon has previously been observed and analyzed in detail in Refs. [34–38]. We observe a similar trend with the usage of shared memory (not graphed).

Our goal

We aim to exploit the underutilization of compute resources, registers, and on-chip shared memory as an opportunity to enable different optimizations to accelerate various bottlenecks in GPU program execution. To achieve this goal, we want to enable efficient helper threading for GPUs to dynamically generate threads in hardware that use the available on-chip resources for various purposes. In the next section, we present the detailed design of our CABA framework that enables the generation and management of these threads.

4.1 Goals and Challenges

The purpose of CABA is to leverage underutilized GPU resources for useful computation. To this end, we need to efficiently execute subroutines that perform optimizations to accelerate bottlenecks in application execution. The key difference between CABA’s assisted execution and regular execution is that CABA must be low overhead and, therefore, helper threads need to be treated differently from regular threads. The low overhead goal imposes several key requirements in designing a framework to enable helper threading. First, we should be able to easily manage helper threads—to enable, trigger, and kill threads when required. Second, helper threads need to be flexible enough to adapt to the runtime behavior of the regular program. Third, a helper thread needs to be able to communicate with the original thread. Finally, we need a flexible interface to specify new subroutines, with the framework being generic enough to handle various optimizations.

With the preceding goals in mind, enabling helper threading in GPU architectures introduces several new challenges. First, execution on GPUs involves context switching between hundreds of threads. These threads are handled at different granularities in hardware and software. The programmer reasons about these threads at the granularity of a thread-block. However, at any point in time, the hardware executes only a small subset of the thread-block, that is, a set of warps. Therefore we need to define the abstraction levels when thinking about and managing helper threads from the point of view of the programmer, the hardware as well as the compiler/runtime. In addition, each of the thousands of executing threads could simultaneously invoke an associated helper thread subroutine. To keep the management overhead low, we need an efficient mechanism to handle helper threads at this magnitude.

Second, GPUs use fine-grained multithreading [32, 33] to time multiplex the fixed number of CUs among the hundreds of threads. Similarly, the on-chip memory resources (i.e., the register file and shared memory) are statically partitioned between the different threads at compile time. Helper threads require their own registers and compute cycles to execute. A straightforward approach is to dedicate a few registers and CUs just for helper thread execution, but this option is both expensive and wasteful. In fact, our primary motivation is to utilize existing idle resources for helper thread execution. In order to do this, we aim to enable sharing of the existing resources between primary threads and helper threads at low cost, while minimizing the interference to primary thread execution. In the remainder of this section, we describe the design of our low-overhead CABA framework.

4.2 Design of the CABA Framework

We choose to implement CABA using a hardware/software co-design, as pure hardware or pure software approaches pose certain challenges that we will describe. There are two alternatives for a fully software-based approach to using helper threads. The first alternative, treating each helper thread as independent kernel code, has high overhead, since we are now treating the helper threads essentially as regular threads. This would reduce the primary thread occupancy in each SM (there is a hard limit on the number of threads and blocks that an SM can support). It would also complicate the data communication between the primary and helper threads, since no simple interface exists for interkernel communication. The second alternative, embedding the helper thread code within the primary thread kernel itself, offers little flexibility in adapting to runtime requirements, since such helper threads cannot be triggered or squashed independently of the primary thread.

On the other hand, a pure hardware solution would make register allocation for the assist warps and the data communication between the helper threads and primary threads more difficult. Registers are allocated to each thread-block by the compiler and are then mapped to the sections of the hardware register file at runtime. Mapping registers for helper threads and enabling data communication between those registers and the primary thread registers would be nontrivial. Furthermore, a fully hardware approach would make it challenging to offer the programmer a flexible interface.

Hardware support enables simpler fine-grained management of helper threads that is aware of micro-architectural events and runtime program behavior. Compiler/runtime support enables simpler context management for helper threads and more flexible programming interfaces. Thus, to get the best of both worlds, we propose a hardware/software cooperative approach, where the hardware manages the scheduling and execution of helper thread subroutines, while the compiler performs the allocation of shared resources (e.g., register file and shared memory) for the helper threads, and the programmer or the microarchitect provides the helper threads themselves.

4.3 Main Hardware Additions

Fig. 4 shows a high-level block diagram of the GPU pipeline [39]. To support assist warp execution, we add three new components: (1) an Assist Warp Store (AWS) to hold the assist warp code, (2) an Assist Warp Controller (AWC) to perform the deployment, tracking, and management of assist warps, and (3) an Assist Warp Buffer (AWB) to stage instructions from triggered assist warps for execution.

Assist warp controller

The AWC (➋) is responsible for the triggering, tracking, and management of assist warp execution. It stores a mapping between trigger events and a SR.ID in the AWS, as specified by the programmer. The AWC monitors for such events, and when they take place, triggers the fetch, decode, and execution of instructions from the AWS for the respective assist warp.

Deploying all the instructions within an assist warp, back-to-back, at the trigger point may require increased fetch/decode bandwidth and buffer space after decoding [7]. To avoid this, at each cycle, only a few instructions from an assist warp, at most equal to the available decode/issue bandwidth, are decoded and staged for execution. Within the AWC, we simply track the next instruction that needs to be executed for each assist warp, and this is stored in the Assist Warp Table (AWT), as depicted in Fig. 5. The AWT also tracks additional metadata required for assist warp management, which is described in more detail in Section 4.4.

4.5 Applications of the CABA Framework

We envision multiple applications for the CABA framework, for example, data compression [15–17, 40], memoization [18–20], and data prefetching [41–45]. In Section 5, we provide a detailed case study on enabling data compression with the framework, as well as discuss various tradeoffs. We believe CABA can be useful for many other optimizations, and we discuss some of them briefly in Section 8.

5.1 Mapping Compression Algorithms Into Assist Warps

In order to employ CABA to enable data compression, we need to map compression algorithms into instructions that can be executed within the GPU cores. For a compression algorithm to be amenable for implementation with CABA, it ideally needs to be (1) reasonably parallelizable and (2) simple (for low latency). Decompressing data involves reading the encoding associated with each cache line that defines how to decompress it and then triggering the corresponding decompression subroutine in CABA. Compressing data, on the other hand, involves testing different encodings and saving data in the compressed format.

We perform compression at the granularity of a cache line. The data needs to be decompressed before it is used by any program thread. In order to utilize the full SIMD width of the GPU pipeline, we want to decompress/compress all the words in the cache line in parallel. With CABA, helper thread routines are managed at the warp granularity, enabling fine-grained triggering of assist warps to perform compression/decompression when required. However, the SIMT execution model in a GPU imposes some challenges: (1) threads within a warp operate in lock step, and (2) threads operate as independent entities, that is, they do not easily communicate with each other.

In this section, we discuss the architectural changes and algorithm adaptations required to address these challenges and provide a detailed implementation and evaluation of data compression within the CABA framework using the BDI compression algorithm [15]. Section 5.1.3 discusses implementing other compression algorithms.

5.1.1 Algorithm overview

BDI compression is a simple compression algorithm that was originally proposed in the context of caches [15]. It is based on the observation that many cache lines contain data with low dynamic range. BDI exploits this observation to represent a cache line with low dynamic range using a common base (or multiple bases) and an array of deltas (where a delta is the difference of each value within the cache line and the common base). Since the deltas require fewer bytes than the values themselves, the combined size after compression can be much smaller. Fig. 6 shows the compression of an example 64-byte cache line from the PageViewCount (PVC) application using BDI. As Fig. 6 indicates, in this case, the cache line can be represented using two bases (an 8-byte base value, 0x8001D000, and an implicit 0 value base) and an array of eight 1-byte differences from these bases. As a result, the entire cache line data can be represented using 17 bytes instead of 64 bytes (1-byte metadata, 8-byte base, and eight 1-byte deltas), saving 47 bytes of the originally used space.

Our example implementation of the BDI compression algorithm [15] views a cache line as a set of fixed-size values, that is, eight 8-byte, sixteen 4-byte, or thirty-two 2-byte values for a 64-byte cache line. For the size of the deltas, it considers three options: 1, 2, and 4 bytes. The key characteristic of BDI, which makes it a desirable compression algorithm to use with the CABA framework, is its fast parallel decompression that can be efficiently mapped into instructions that can be executed on GPU hardware. Decompression is simply a masked vector addition of the deltas to the appropriate bases [15].

5.1.2 Mapping BDI to CABA

In order to implement BDI with the CABA framework, we need to map the BDI compression/decompression algorithms into GPU instruction subroutines (stored in the AWS and deployed as assist warps).

Decompression

To decompress the data compressed with BDI, we need a simple addition of deltas to the appropriate bases. The CABA decompression subroutine first loads the words within the compressed cache line into assist warp registers and then performs the base-delta additions in parallel, employing the wide ALU pipeline.¹ The subroutine then writes back the uncompressed cache line to the cache. It skips the addition for the lanes with an implicit base of zero by updating the active lane mask based on the cache line encoding. We store a separate subroutine for each possible BDI encoding that loads the appropriate bytes in the cache line as the base and the deltas. The high-level algorithm for decompression is presented in Algorithm 1.

Algorithm 1

BDI: Decompression

Compression

To compress data, the CABA compression subroutine tests several possible encodings (each representing a different size of base and deltas) in order to achieve a high compression ratio. The first few bytes (2–8 depending on the encoding tested) of the cache line are always used as the base. Each possible encoding is tested to check whether the cache line can be successfully encoded with it. In order to perform compression at a warp granularity, we need to check whether all of the words at every SIMD lane were successfully compressed. In other words, if any one word cannot be compressed, that encoding cannot be used across the warp. We can perform this check by adding a global predicate register, which stores the logical AND of the per-lane predicate registers. We observe that applications with homogeneous data structures can typically use the same encoding for most of their cache lines [15]. We use this observation to reduce the number of encodings we test to just one in many cases. All necessary operations are done in parallel using the full width of the GPU SIMD pipeline. The high-level algorithm for compression is presented in Algorithm 2.

Algorithm 2

BDI: Compression

5.1.4 Implementing the FPC algorithm

For FPC, the cache line is treated as a set of fixed-size words, and each word within the cache line is compressed into a simple prefix or encoding and a compressed word if it matches a set of frequent patterns, for example, narrow values, zeros, or repeated bytes. The word is left uncompressed if it does not fit any pattern. We refer the reader to the original work [59] for a more detailed description of the original algorithm.

The challenge in mapping assist warps to the FPC decompression algorithm is in the serial sequence in which each word within a cache line is decompressed. This is because, in the original proposed version, each compressed word can have a different size. To determine the location of a specific compressed word, it is necessary to have decompressed the previous word. We make some modifications to the algorithm in order to parallelize the decompression across different lanes in the GPU cores. First, we move the word prefixes (metadata) for each word to the front of the cache line, so we know upfront how to decompress the rest of the cache line. Unlike with BDI, each word within the cache line has a different encoding and hence a different compressed word length and encoding pattern. This is problematic because statically storing the sequence of decompression instructions for every combination of patterns for all the words in a cache line would require very large instruction storage. In order to mitigate this issue, we break each cache line into a number of segments. Each segment is compressed independently, and all the words within each segment are compressed using the same encoding, whereas different segments may have different encodings. This creates a trade-off between simplicity/parallelizability versus compressibility. Consistent with previous works [59], we find that this does not significantly impact compressibility.

Decompression

The high-level algorithm we use for decompression is presented in Algorithm 3. Each segment within the compressed cache line is loaded in series. Each of the segments is decompressed in parallel—this is possible because all the compressed words within the segment have the same encoding. The decompressed segment is then stored before moving on to the next segment. The location of the next compressed segment is computed based on the size of the previous segment.

Algorithm 3

FPC: Decompression

Compression

Similar to the BDI implementation, we loop through and test different encodings for each segment. We also compute the address offset for each segment at each iteration to store the compressed words in the appropriate location in the compressed cache line. Algorithm 4 presents the high-level FPC compression algorithm we use.

Algorithm 4

FPC: Compression

Implementing the C-Pack algorithm

C-Pack [17] is a dictionary-based compression algorithm where frequent “dictionary” values are saved at the beginning of the cache line. The rest of the cache line contains encodings for each word that may indicate zero values, narrow values, full or partial matches into the dictionary or simply that the word is uncompressible.

In our implementation, we reduce the number of possible encodings to partial matches (only last byte mismatch), full word match, zero value, and zero extend (only last byte), and we limit the number of dictionary values to 4. This enables fixed compressed word size within the cache line. A fixed compressed word size enables compression and decompression of different words within the cache line in parallel. If the number of required dictionary values or uncompressed words exceeds 4, the line is left decompressed. This is, as in BDI and FPC, a trade-off between simplicity and compressibility. In our experiments, we find that it does not significantly impact the compression ratio—primarily because of the 32B minimum data size and granularity of compression.

Decompression

As described, to enable parallel decompression, we place the encodings and dictionary values at the head of the line. We also limit the number of encodings to enable quick decompression. We implement C-Pack decompression as a series of instructions (one per encoding used) to load all the registers with the appropriate dictionary values. We define the active lane mask based on the encoding (similar to the mechanism used in BDI) for each load instruction to ensure the correct word is loaded into each lane’s register. Algorithm 5 provides the high-level algorithm for C-Pack decompression.

Algorithm 5

C-Pack: Decompression

Compression

Compressing data with C-Pack involves determining the dictionary values that will be used to compress the rest of the line. In our implementation, we serially add each word from the beginning of the cache line to be a dictionary value if it was not already covered by a previous dictionary value. For each dictionary value, we test whether the rest of the words within the cache line are compressible. The next dictionary value is determined using the predicate register to determine the next uncompressed word, as in BDI. After four iterations (dictionary values), if all the words within the line are not compressible, the cache line is left uncompressed. Similar to BDI, the global predicate register is used to determine the compressibility of all of the lanes after four or fewer iterations. Algorithm 6 provides the high-level algorithm for C-Pack compression.

Algorithm 6

C-Pack: Compression

5.2 Walkthrough of CABA-Based Compression

We show the detailed operation of CABA-based compression and decompression mechanisms in Fig. 7. We assume a baseline GPU architecture with three levels in the memory hierarchy—two levels of caches (private L1s and a shared L2) and main memory. Different levels can potentially store compressed data. In this section and in our evaluations, we assume that only the L2 cache and main memory contain compressed data. Note that there is no capacity benefit in the baseline mechanism because compressed cache lines still occupy the full uncompressed slot, that is, we only evaluate the bandwidth-saving benefits of compression in GPUs.

5.3 Realizing Data Compression

Supporting data compression requires additional support from the main MC and the runtime system, as we describe here.

Evaluated applications

We use a number of CUDA applications derived from CUDA SDK (BFS, CONS,JPEG, LPS, MUM, RAY, SLA, TRA) [23], Rodinia (hs, nw) [25], Mars (KM, MM, PV C,PV R, SS) [22], and lonestar (bfs, bh, mst, sp, sssp) [24] suites. We run all applications to completion or for 1 billion instructions (whichever comes first). CABA-based data compression is beneficial mainly for memory-bandwidth-limited applications. In computation-resource-limited applications, data compression is not only unrewarding, but it can also cause significant performance degradation due to the computational overhead associated with assist warps. We rely on static profiling to identify memory-bandwidth-limited applications and disable CABA-based compression for the others. In our evaluation (see Section 7), we demonstrate detailed results for applications that exhibit some compressibility in memory bandwidth (at least 10%). Applications without compressible data (e.g., sc, SCP) do not gain any performance from the CABA framework, and we verified that these applications do not incur any performance degradation (because the assist warps are not triggered for them).

Evaluated metrics

We present instructions per cycle (IPC) as the primary performance metric. We also use average bandwidth utilization, defined as the fraction of total DRAM cycles that the DRAM data bus is busy, and compression ratio, defined as the ratio of the number of DRAM bursts required to transfer data in the compressed versus the uncompressed form. As reported in prior work [15], we use decompression/compression latencies of 1/5 cycles for the hardware implementation of BDI.

7.1 Effect on Performance and Bandwidth Utilization

Figs. 8 and 9 show, respectively, the normalized performance (vs Base) and the memory bandwidth utilization of the five designs. We make three major observations.

First, all compressed designs are effective in providing high performance improvement over the baseline. Our approach (CABA-BDI) provides a 41.7% average improvement, which is only 2.8% less than the ideal case (Ideal-BDI) with none of the overhead associated with CABA. CABA-BDI’s performance is 9.9% better than the previous [65] hardware-based memory bandwidth compression design (HW-BDI-Mem), and only 1.6% worse than the purely hardware-based design (HW-BDI) that performs both interconnect and memory bandwidth compression. We conclude that our framework is effective at enabling the benefits of compression without requiring specialized hardware compression and decompression logic.

Second, performance benefits, in many workloads, correlate with the reduction in memory bandwidth utilization. For a fixed amount of data, compression reduces the bandwidth utilization, and thus increases the effective available bandwidth. Fig. 9 shows that CABA-based compression (1) reduces the average memory bandwidth utilization from 53.6% to 35.6% and (2) is effective at alleviating the memory bandwidth bottleneck in most workloads. In some applications (e.g., bfs and mst), designs that compress both the on-chip interconnect and the memory bandwidth, that is, CABA-BDI and HW-BDI, perform better than the design that compresses only the memory bandwidth (HW-BDI-Mem). Hence CABA seamlessly enables the mitigation of the interconnect bandwidth bottleneck as well, since data compression/decompression is flexibly performed at the cores.

Third, for some applications, CABA-BDI performs slightly (within 3%) better than Ideal-BDI and HW-BDI. The reason for this counter intuitive result is the effect of warp oversubscription [75–78]. In these cases, too many warps execute in parallel, polluting the last level cache. CABA-BDI sometimes reduces pollution as a side effect of performing more computation in assist warps, which slows down the progress of the parent warps.

We conclude that the CABA framework can effectively enable data compression to reduce both on-chip interconnect and off-chip memory-bandwidth utilization, thereby improving the performance of modern GPGPU applications.

7.2 Effect on Energy

Compression decreases energy consumption in two ways: (1) by reducing bus energy consumption, (2) by reducing execution time. Fig. 10 shows the normalized energy consumption of the five systems. We model the static and dynamic energy of the cores, caches, DRAM, and all buses (both on-chip and off-chip), as well as the energy overhead related to compression: metadata (MD) cache and compression/decompression logic. We make two major observations.

First, CABA-BDI reduces energy consumption by as much as 22.2% over the baseline. This is especially noticeable for memory-bandwidth-limited applications, for example, PVC, mst. This is a result of two factors: (1) the reduction in the amount of data transferred between the LLC and DRAM (as a result of which we observe a 29.5% average reduction in DRAM power) and (2) the reduction in total execution time. This observation agrees with several prior works on bandwidth compression [55, 56]. We conclude that the CABA framework is capable of reducing the overall system energy, primarily by decreasing the off-chip memory traffic.

Second, CABA-BDI’s energy consumption is only 3.6% more than that of the HW-BDI design, which uses dedicated logic for memory-bandwidth compression. It is also only 4.0% more than that of the Ideal-BDI design, which has no compression-related overhead. CABA-BDI consumes more energy because it schedules and executes assist warps, utilizing on-chip register files, memory and computation units, which is less energy-efficient than using dedicated logic for compression. However, as results indicate, this additional energy cost is small compared to the performance gains of CABA (recall, 41.7% over Base), and may be amortized by using CABA for other purposes as well (see Section 8).

Energy-delay product

Fig. 11 shows the product of the normalized energy consumption and normalized execution time for the evaluated GPU workloads. This metric simultaneously captures two metrics of interest—energy dissipation and execution delay (inverse of performance). An optimal feature would simultaneously incur low energy overhead while also reducing the execution delay. This metric is useful in capturing the efficiencies of different architectural designs and features which may expend differing amounts of energy while producing the same performance speedup or vice-versa. Hence a lower Energy-Delay product is more desirable. We observe that CABA-BDI has a 45% lower Energy-Delay product than the baseline. This reduction comes from energy savings from reduced data transfers as well as lower execution time. On average, CABA-BDI is within only 4% of Ideal-BDI, which incurs none of the energy and performance overhead of the CABA framework.

7.3 Effect of Enabling Different Compression Algorithms

The CABA framework is not limited to a single compression algorithm and can be effectively used to employ other hardware-based compression algorithms (e.g., FPC [16] and C-Pack [17]). The effectiveness of other algorithms depends on two key factors: (1) how efficiently the algorithm maps to GPU instructions and (2) how compressible the data are with the algorithm. We map the FPC and C-Pack algorithms to the CABA framework and evaluate the framework’s efficacy.

Fig. 12 shows the normalized speedup with four versions of our design: CABA-FPC, CABA-BDI, CABA-C-Pack, and CABA-BestOfAll with the FPC, BDI, and C-Pack compression algorithms. CABA-BestOfAll is an idealized design that selects and uses the best of all three algorithms in terms of compression ratio for each cache line, assuming no selection overhead. We make three major observations.

First, CABA significantly improves performance with any compression algorithm (20.7% with FPC, 35.2% with C-Pack). Similar to CABA-BDI, the applications that benefit the most are those that are both memory-bandwidth-sensitive (Fig. 9) and compressible (Fig. 13). We conclude that our proposed framework, CABA, is general and flexible enough to successfully enable different compression algorithms.

Second, applications benefit differently from each algorithm. For example, LPS, JPEG, MUM, and nw have higher compression ratios with FPC or C-Pack; whereas MM, PVC, and PVR compress better with BDI. This indicates the necessity of having flexible data compression with different algorithms within the same system. Implementing multiple compression algorithms completely in hardware is expensive as it adds significant area overhead, whereas CABA can flexibly enable the use of different algorithms via its general assist warp framework.

Third, the design with the best of three compression algorithms, CABA-BestOfAll, can sometimes improve performance more than each individual design with just one compression algorithm (e.g., for MUM and KM). This happens because, even within an application, different cache lines compress better with different algorithms. At the same time, different compression-related overhead of different algorithms can cause one to have higher performance than another even though the latter may have a higher compression ratio. For example, CABA-BDI provides higher performance on LPS than CABA-FPC, even though BDI has a lower compression ratio than FPC for LPS, because BDI’s compression/decompression latencies are much lower than FPC’s. Hence a mechanism that selects the best compression algorithm based on both compression ratio and the relative cost of compression/decompression is desirable to get the best multiple compression algorithm. The CABA framework can flexibly enable the implementation of such a mechanism, whose design we leave for future work.

7.4 Sensitivity to Peak Main Memory Bandwidth

As described in Section 3, main memory (off-chip) bandwidth is a major bottleneck in GPU applications. In order to confirm that CABA works for different designs with varying amounts of available memory bandwidth, we conduct an experiment where CABA-BDI is used in three systems with 0.5×, 1×, and 2× amount of bandwidth of the baseline.

Fig. 14 shows the results of this experiment. We observe that, as expected, each CABA design (*-CABA) significantly outperforms the corresponding baseline designs with the same amount of bandwidth. The performance improvement of CABA is often equivalent to the doubling the off-chip memory bandwidth. We conclude that CABA-based bandwidth compression, on average, offers almost all the performance benefit of doubling the available off-chip bandwidth with only modest complexity to support assist warps.

7.5 Selective Cache Compression With CABA

In addition to reducing bandwidth consumption, data compression can also increase the effective capacity of on-chip caches. While compressed caches can be beneficial—as higher effective cache capacity leads to lower miss rates—supporting cache compression requires several changes in the cache design [15–17, 46, 50].

Fig. 15 shows the effect of four cache compression designs using CABA-BDI (applied to both L1 and L2 caches with 2× or 4× the number of tags of the baseline⁴ ) on performance. We make two major observations. First, several applications from our workload pool are not only bandwidth sensitive but also cache capacity sensitive. For example, bfs and sssp significantly benefit from L1 cache compression, while TRA and KM benefit from L2 compression. Second, L1 cache compression can severely degrade the performance of some applications, for example, hw and LPS. The reason for this is the overhead of decompression, which can be especially high for L1 caches as they are accessed very frequently. This overhead can be easily avoided by disabling compression at any level of the memory hierarchy.

7.6 Other Optimizations

We also consider several other optimizations of the CABA framework for data compression: (1) avoiding the overhead of decompression in L2 by storing data in the uncompressed form and (2) optimized load of only useful data.

Uncompressed L2

The CABA framework allows us to store compressed data selectively at different levels of the memory hierarchy. We consider an optimization where we avoid the overhead of decompressing data in L2 by storing data in uncompressed form. This provides another trade-off between the savings in on-chip traffic (when data in L2 is compressed—default option) and savings in decompression latency (when data in L2 is uncompressed). Fig. 16 depicts the performance benefits from this optimization. Several applications in our workload pool (e.g., RAY) benefit from storing data uncompressed as these applications have high hit rates in the L2 cache. We conclude that offering the choice of enabling or disabling compression at different levels of the memory hierarchy can provide higher levels of the software stack (e.g., applications, compilers, runtime system, system software) with an additional performance knob.

8.1 Memoization

Hardware memoization is a technique used to avoid redundant computations by reusing the results of previous computations that have the same or similar inputs. Prior work [19, 80, 81] observed redundancy in inputs to data in GPU workloads. In applications limited by available compute resources, memoization offers an opportunity to trade-off computation for storage, thereby enabling potentially higher energy efficiency and performance. In order to realize memoization in hardware, a look-up table (LUT) is required to dynamically cache the results of computations as well as the corresponding inputs. The granularity of computational reuse can be at the level of fragments [19], basic blocks or functions [18, 20, 82–84], or long-latency instructions [85]. The CABA framework provides a natural way to implement such an optimization. The availability of on-chip memory lends itself to use as the LUT. In order to cache previous results in on-chip memory, look-up tags (similar to those proposed in Ref. [34]) are required to index correct results. With applications tolerant of approximate results (e.g., image processing, machine learning, fragment rendering kernels), the computational inputs can be hashed to reduce the size of the LUT. Register values, texture/constant memory or global memory sections that are not subject to change are potential inputs. An assist warp can be employed to perform memoization in the following ways: (1) compute the hashed value for a look-up at predefined trigger points, (2) use the load/store pipeline to save these inputs in available shared memory, and (3) eliminate redundant computations by loading the previously computed results in the case of a hit in the LUT.

8.2 Prefetching

Prefetching has been explored in the context of GPUs [3, 4, 36, 86–89] with the goal of reducing effective memory latency. With memory-latency-bound applications, the load/store pipelines can be employed by the CABA framework to perform opportunistic prefetching into GPU caches. The CABA framework can potentially enable the effective use of prefetching in GPUs for several reasons. First, even simple prefetchers such as the stream [42, 43, 90] or stride [44, 45] prefetchers are nontrivial to implement in GPUs since access patterns need to be tracked and trained at the fine granularity of warps [87, 89]. CABA could enable fine-grained book keeping by using spare registers and assist warps to save metadata for each warp. The computational units could then be used to continuously compute strides in access patterns both within and across warps. Second, it has been demonstrated that software prefetching and helper threads [13, 36, 91, 92, 92–97] are very effective in performing prefetching for irregular access patterns. Assist warps offer the hardware/software interface to implement application-specific prefetching algorithms with varying degrees of complexity without the additional overhead of various hardware implementations. Third, in bandwidth-constrained GPU systems, uncontrolled prefetching could potentially flood the off-chip buses, delaying demand requests. CABA can enable flexible prefetch throttling (e.g., [90, 98, 99]) by scheduling assist warps that perform prefetching, only when the memory pipelines are idle or underutilized. Fourth, prefetching with CABA entails using load or prefetch instructions, which not only enables prefetching to the hardware-managed caches, but also could simplify the usage of unutilized shared memory or register files as prefetch buffers.

Helper threading

Previous works [6–9, 11–13, 91–97, 112–116] demonstrated the use of helper threads in the context of simultaneous multithreading (SMT) and multicore and single-core processors, primarily to speed up single-thread execution by using idle SMT contexts, idle cores in CPUs, or idle cycles during which the main program is stalled on a single thread context. These works typically use helper threads (generated by the software, the hardware, or cooperatively) to precompute useful information that aids the execution of the primary thread (e.g., by prefetching, branch outcome precomputation, cache management). No previous work discussed the use of helper threads for memory/interconnect bandwidth compression or cache compression.

These works primarily use helper threads to capture data flow and precompute useful information to aid in the execution of the primary thread. In these prior works, helper threads are either generated with the help of the compiler [113–115] or completely in hardware [9, 96, 97]. These threads are used to perform prefetching in Refs. [6, 13, 91, 92, 92–97, 117] which the helper threads predict future load addresses by doing some computation and then prefetch the corresponding data. Simultaneous subordinate multithreading [6] employs hardware generated helper threads to improve branch prediction accuracy and cache management. Speculative multithreading [105–107, 118] involves executing different sections of the serial program in parallel and then later verifying the runtime correctness. Assisted execution [8, 12] is an execution paradigm where tightly coupled nanothreads are generated using nanotrap handlers and execute routines to enable optimizations like prefetching. In slipstream processors [92], one thread runs ahead of the program and executes a reduced version of the program. In runahead execution [96, 97], the main thread is executed speculatively solely for prefetching purposes when the program is stalled because of a cache miss.

While our work was inspired by these prior studies of helper threading in latency-oriented architectures (CPUs), developing a framework for helper threading (or assist warps) in throughput-oriented architectures (GPUs) enables new opportunities and poses new challenges, both being due to the massive parallelism and resources present in a throughput-oriented architecture (as discussed in Section 1). Our CABA framework exploits these new opportunities and addresses these new challenges, including (1) low-cost management of a large number of assist warps that could be running concurrently with regular program warps, (2) means of state/context management and scheduling for assist warps to maximize effectiveness and minimize interference, and (3) different possible applications of the concept of assist warps in a throughput-oriented architecture.

In the GPU domain, CudaDMA [119] is a recent proposal that aims to ease programmability by decoupling execution and memory transfers with specialized DMA warps. This work does not provide a general and flexible hardware-based framework for using GPU cores to run warps that aid the main program.

Memory latency and bandwidth optimizations in GPUs

Many prior works focus on optimizing for memory bandwidth and memory latency in GPUs. Jog et al. [3] aim to improve memory latency tolerance by coordinating prefetching and warp scheduling policies. Lakshminarayana et al. [36] reduce effective latency in graph applications by using spare registers to store prefetched data. In OWL [4, 76], intelligent scheduling is used to improve DRAM bank-level parallelism and bandwidth utilization, and Rhu et al. [120] propose a locality-aware memory to improve memory throughput. Kayiran et al. [76] propose GPU throttling techniques to reduce memory contention in heterogeneous systems. Ausavarangniran et al. [78] leverage heterogeneity in warp behavior to design more intelligent policies at the cache and MC. These works do not consider data compression and are orthogonal to our proposed framework.

Compression

Several prior works [47, 50, 53,55–58, 65, 121] study memory and cache compression with several different compression algorithms [15–17, 40, 47, 49], in the context of CPUs or GPUs.

Alameldeen et al. [121] investigated the possibility of bandwidth compression with FPC [59]. The authors show that significant decrease in pin bandwidth demand can be achieved with FPC-based bandwidth compression design. Sathish et al. [65] examine the GPU-oriented memory link compression using C-Pack [17] compression algorithm. The authors make the observation that GPU memory (GDDR3 [122]) indeed allows transfer of data in small bursts and propose to store data in compressed form in memory, but without capacity benefits. Thuresson et al. [53] consider a CPU-oriented design where a compressor/decompressor logic is located on the both ends of the main memory link. Pekhimenko et al. [55] propose linearly compressed pages (LCP) with the primary goal of compressing main memory to increase capacity.

Our work is the first to demonstrate how one can adapt some of these algorithms for use in a general helper threading framework for GPUs. As such, compression/decompression using our new framework is more flexible since it does not require a specialized hardware implementation for any algorithm and instead utilizes the existing GPU core resources to perform compression and decompression. Finally, as discussed in Section 8, our CABA framework is applicable beyond compression and can be used for other purposes.