2 Methodology

2.1 System and Compilers

We evaluated the CPU compressors on a system with dual 10-core Xeon E5-2687W v3 processors running at 3.1 GHz and 128 GB of main memory. The operating system was CentOS 6.7. We used the gcc compiler version 4.4.7 with “-O3 -pthread -march=native” for the CPU implementations.

For GPU compressors, we used a Kepler-based Tesla K40c GPU. It had 15 streaming multiprocessors with a total of 2880 CUDA cores running at 745 MHz and 12 GB of global memory. We also used a Maxwell-based GeForce GTX Titan X GPU. It had 24 streaming multiprocessors with a total of 3072 CUDA cores running at 1 GHz and 12 GB of global memory. We used nvcc version 7.0 with the “-O3 -arch=sm_35” flags to compile the GPU codes for the K40 and “-O3 -arch=sm_52” to compile the GPU codes for the Titan X.

2.2 Measuring Throughput and Energy

For all special-purpose floating-point compressors, the timing measurements were performed by adding code to read a timer before and after the compression and decompression code sections and recording the difference. For the general-purpose compressors, we measured the runtime of compression and decompression when reading the input from a disk cache in main memory and writing the output to /dev/null. In the case of GPU code, we excluded the time to transfer the data to or from the GPU as we assumed the data to have been produced or transferred there with or without compression. Each experiment was conducted three times, and the median throughput was reported. Note that the three measured throughputs were very similar in all cases. The decompressed results were always compared to the original data to verify that every bit was identical.

For measuring energy on the CPU, we used a custom power measurement tool based on the PAPI framework [15]. PAPI makes use of the Running Average Power Limit (RAPL) functionality of certain Intel processors, which in turn measures Model Specific Registers to calculate the energy consumption of a processor in real time. Our power tool simply made calls to the PAPI framework to start the energy measurements, to run the code to be measured, and then to stop the measurements and output the result. Doing so incurred negligible overhead.

For measuring energy on the GPU, we used the K20 Power Tool, which also works for the K40c GPU we used in our experiments [16]. To measure the energy consumption of the GPU, the K20 Power Tool uses power samples from the GPU’s internal power sensor and the “active” runtime. The power tool defines this as the amount of time the GPU is drawing power above the idle level. Fig. 2 illustrates this.

Because of how the GPU draws power and how the built-in power sensor samples, only readings above a certain threshold (the dashed line at 55 W in this case) reflect when the GPU is actually executing the program [16]. Measurements below the threshold are either the idle power (less than about 26 W) or the “tail power” due to the driver keeping the GPU active for a time before powering it down. Using the active runtime ignores any execution time that may take place on the CPU. The power threshold is dynamically adjusted to maximize accuracy for different GPU settings.

2.3 Data Sets

We used the 13 FPC data sets for our evaluation [3]. Each data set consisted of a binary sequence of IEEE 754 double-precision floating-point values. They included MPI messages (msg), numeric results (num), and observational data (obs).

MPI messages: These five data sets contain the numeric messages sent by a node in a parallel system running NAS Parallel Benchmark (NPB) and ASCI Purple applications.

• msg_bt: NPB computational fluid dynamics pseudo-application bt

• msg_lu: NPB computational fluid dynamics pseudo-application lu

• msg_sp: NPB computational fluid dynamics pseudo-application sp

• msg_sppm: ASCI Purple solver sppm

• msg_sweep3d: ASCI Purple solver sweep3d

Numeric simulations: These four data sets are the result of numeric simulations.

• num_brain: Simulation of the velocity field of a human brain during a head impact

• num_comet: Simulation of the comet Shoemaker-Levy 9 entering Jupiter’s atmosphere

• num_control: Control vector output between two minimization steps in weather-satellite data assimilation

• num_plasma: Simulated plasma temperature evolution of a wire array z-pinch experiment

Observational data: These four data sets comprise measurements from scientific instruments.

• obs_error: Data values specifying brightness temperature errors of a weather satellite

• obs_info: Latitude and longitude information of the observation points of a weather satellite

• obs_spitzer: Data from the Spitzer Space Telescope showing a slight darkening as an extrasolar planet disappears behinds its star

• obs_temp: Data from a weather satellite denoting how much the observed temperature differs from the actual contiguous analysis temperature field

Table 1 provides pertinent information about each data set. The first two data columns list the size in megabytes and in millions of double-precision values. The middle column shows the percentage of values that are unique. The fourth column displays the first-order entropy of the values in bits. The last column expresses the randomness of each data set in percent, that is, it reflects how close the first-order entropy is to that of a truly random data set with the same number of unique values. For the single-precision experiments, we simply converted the double-precision data sets.

2.4 Algorithmic Components

We tested the following algorithmic components in our experiments. They are generalizations or approximations of components extracted from previously proposed compression algorithms. Each component takes a block of data as input, transforms it, and outputs the transformed block.

The input data are broken down into fixed-size chunks. Each chunk is assigned to a thread block for parallel processing. We chose 1024-element chunks to match the maximum number of threads per thread block in our GPUs.

The NUL component simply outputs the input block. The INV component flips all the bits. The BIT component breaks a block of data into chunks and then emits the most significant bit of each word in the chunk, followed by the second most significant bits, and so on. The DIMn component also breaks the blocks into chunks and then rearranges the values in each chunk such that the values from each dimension are grouped together. For example, DIM2 emits all the values from the even positions first and then all the values from the odd positions. We tested the dimensions n = 2, 3, 4, 5, 8, 16, and 32. The LNVns component uses the nth prior value in the same chunk as a prediction of the current value, subtracts the prediction from the current value, and emits the residual. The LNVnx component is identical except it XORs the prediction with the current value to form the residual. In both cases, we tested n = 1, 2, 3, 5, 6, and 8. Note that all of the preceding components transform the data blocks without changing their size. The following two components are the only ones that can actually reduce the length of a data block. The ZE component outputs a bitmap for each chunk that specifies which values in the chunk are zero. The bitmap is followed by the nonzero values. The RLE component performs run-length encoding, that is, it replaces repeating values by a count and a single copy of the value. Each component has a corresponding inverse that performs the opposite transformation for decompression.

Because it may be more effective to operate at byte rather than word granularity, we also included the singleton pseudo component “|”, which we call the cut, that converts a block of words into a block of bytes through type casting (i.e., no computation is necessary). As a result, we need three versions of each component and its inverse, one for double-precision values (8-byte words), one for single-precision values (4-byte words), and one for byte values. Each component operates on an integer representation of the floating-point data, that is, the bit pattern representing the floating-point value is copied verbatim into an appropriately sized integer variable.

We chose this limited number of components because we only included components that we could implement in a massively parallel manner. Nevertheless, as the results in the next section show, very effective compression algorithms can be created from these components. In other words, the sophistication and effectiveness of the ultimate algorithm is the result of the clever combination of components, not the capability of each individual component. This is akin to how complex programs can be expressed through a suitable sequence of very simple machine instructions.

To derive MPC, we investigated all four-stage compression algorithms that can be built from the preceding components. Because of the presence of the NUL component, this includes all one-, two-, and three-stage algorithms as well. Note that only the first three stages can contain any 1 of the 24 components just described. The last stage must contain a component that can reduce the amount of data, that is, either ZE or RLE. The cut can be before the first component, in which case the data is exclusively treated as a sequence of bytes; after the last component, in which case the data is exclusively treated as a sequence of words; or between components, in which case the data is initially treated as words and then as bytes. The 5 possible locations for the cut, the 24 possible components in each of the first three stages, and the 2 possible components in the last stage result in 5 * 24 * 24 * 24 * 2 = 138, 240 possible compression algorithms with four stages.

3 Experimental results

3.1 Synthesis Analysis and Derivation of MPC

Table 2 shows the four chained components and the location of the cut that the exhaustive search found to work best for each data set as well as across all 13 data sets, which is denoted as “Best.” For Best, the CR is the harmonic mean over the data sets.

3.2 Compression Ratios

Tables 3 and 4 show the CRs on the double- and single-precision data sets, respectively, for the general-purpose compressors pbzip2 [17], pigz [18], and lzop [19], the special-purpose floating-point compressors pFPC [20] and GFC [21] (they only support double precision), and for MPC. The highest CR for each data set is highlighted in the tables. Because we wanted to maximize the CR, we selected the command-line flags that result in the highest CR where possible. For lzop we used –c6, as this is the highest compression level before the runtime becomes intractable. For pigz and pbzip2, we used –c9 –p20. For GFC and MPC, we specified the data-set dimensionality on the command line. GFC and MPC are parallel GPU implementations. pFPC, pbzip2, and pigz are parallel CPU implementations. The remaining compressor, lzop, is a serial CPU implementation.

All of the tested algorithms except lzop and GFC compressed at least one data set best. MPC delivered the highest CR on six double-precision and eight single-precision data sets. This was a rather surprising result given that MPC is “handicapped” by being constrained to only utilize GPU-friendly components that retain almost no internal state.

MPC proved to be superior to lzop and GFC, both of which it outperformed on most of the tested data sets in terms of CR. Moreover, GFC and pFPC did not support single-precision data. pFPC and pbzip2 outperformed MPC on average. However, this was the case only because of two data sets, msg_sppm and num_plasma, on which they yielded much higher CRs than MPC.

Most of the double-precision data sets were less compressible than the single-precision data sets. This was expected as the least significant mantissa bits tend to be the most random in floating-point values and many of those bits are dropped when converting from double to single precision.

3.3 Compression and Decompression Speed

Tables 5 and 7 list the double- and single-precision throughputs in gigabytes per second on the 13 data sets for all tested compressors. Tables 6 and 8 list the same information, but for decompression. As stated before, GFC and pFPC do not support single-precision data. For the GPU-based compressors, we show results for both the K40, which has a compute capability of 3.5, and the Titan X, which has a compute capability of 5.2.

lzop is the fastest CPU-based algorithm at compression and decompression, but it is still 28 times slower than MPC. Thus MPC not only compresses better than lzop but also greatly outperforms it in throughput.

pFPC, the overall best implementation in terms of CR (on the double-precision data), is roughly 18 times slower when running on 20 CPU cores than MPC. GFC is the fastest tested implementation (on the double-precision data sets). It is roughly 1.5–2 times faster than MPC, which is expected as GFC is essentially a two-component algorithm whereas MPC has four. However, GFC compresses relatively poorly. Importantly, the single- and double-precision compression and decompression throughput of MPC matches or exceeds that of the PCI-Express v3.0 bus linking the GPU to the CPU in our system, making real-time operation possible.

3.4 Compression and Decompression Energy

Tables 9 and 11 show the energy efficiency when compressing each of the 13 double- and single-precision inputs. Tables 10 and 12 show the same information, but for decompression. As stated before, pFPC does not support single-precision data. Also, the K20 Power Tool does not currently support measuring energy on the Titan X. Thus we provide energy measurements only for MPC_35.

We can clearly see that MPC dominates the CPU compressors in terms of energy efficiency. For the CPU compressors, lzop is best for double- and single-precision compression as well as single-precision decompression, while pFPC is best for double-precision decompression.

Data compression on the GPU is between 1.8 to over 80 times more energy efficient than even the most energy efficient of the tested CPU compressors. Furthermore, it appears that decompression is more energy efficient on average than compression for lzop, pbzip2, and pFPC. For pigz and MPC, compression is more efficient than decompression, though on average, MPC decompression is still over 25 times more energy efficient than CPU decompression.

3.5 Component Count

Fig. 3 illustrates by how much the CR is affected when changing the number of chained components on the double-precision data sets. The bars marked “Best” refer to the single algorithm that yields the highest harmonic-mean CR over all 13 data sets. The other bars refer to the best algorithm found for each individual data set. We used exhaustive search for up to four-component algorithms. Because the runtime of exhaustive search is exponential in the number of components, we had to use a different approach for algorithms with more than four stages. In particular, we chose a genetic algorithm to find good (though not generally the best) algorithms in those vast search spaces. The single-precision results are not shown as they are qualitatively similar.

Except on two data sets, a single-component suffices to reach roughly 80–90% of the CR achieved with four components. Moreover, the increase in CR when going from one to two stages is generally larger than going from two to three stages, which in turn is larger than going from three to four stages, and so on. For example, looking at the harmonic mean, going from one to two stages, the CR improves by 8.9%; going from two to three stages, it improves by 8.4%, then by 4.8%, 2.3%, and 0.7%; and going from six to seven stages, the harmonic mean does not improve any more at all (which is in part because of the genetic algorithm not finding better solutions). In other words, the improvements start to flatten out, that is, algorithms with large numbers of stages do not yield much higher CRs and are slower than the chosen four-stage algorithms. Note that, due to the presence of the NUL component, the algorithms that can be created with a larger number of stages represent a strict superset of the algorithms that can be created with fewer stages. As a consequence, the exhaustive-search results in Fig. 3 monotonically increase with more stages. However, this is not the case for the genetic algorithm, which does not guarantee finding the best solution in the search space.