WIXLIB

(cuSZ ) Optimizing Error-Bounded LossyCompression for Scientific Data on GPUsJiannan Tian , Sheng Di† , Xiaodong Yu† , Cody Rivera§ , Kai Zhao‡ ,Sian Jin , Yunhe Feng , Xin Liang , Dingwen Tao , Franck Cappello† Washington State UniversityArgonne National Laboratory§The University of Alabama‡University of California, Riverside University of Washington Missouri University of Science and Technology†Thursday, Sept. 9, 2021CLUSTER ’21, Portland, Oregon, USA

: Supercomputing SystemsThe compute capability is developed much faster than storage and bandwidth: a widening gap between compute unit and storage bandwidth (PF–SB), or between main memory size and storage bandwidth (MS–SB)supercomputerCray JaguarCray Blue WatersCray CORIIBM Summityear2008201220172018class1 pflops10 pflops10 pflops100 pflopsPF1.75 pflops13.3 pflops30 pflops200 pflopsMS360 tb1.5 pb1.4 pb 10 pb PF: peak FLOPS MS: memory size SB: storage bandwidth when using burst buffer counting only DDR4supercomputerFujitsu FugakuIntel Aurora year2020futureclass“ExaScale”ExaScaleRpeak, TOP 500 for November 2020 PF537 pflops 1 eflopsSB240 gb/s1.1 tb/s1.7 tb/s 2.5 tb/sMS/SB1.5k1.3k0.8k 4kPF/SB7.3k13k17k80kSource: F. Cappello (ANL)MS4.85 pb 10 pbSBMS/SB 1.5 tb/s 3.2k 25 tb/s 0.4kPF/SB358k40kDDN NewsroomTable 3: Classes of supercomputers showing their performance, MS and SB.Thursday, Sept. 9, 2021 · CLUSTER ’21, Portland, Oregon, USA · cuSZ · 2 / 21

: Data-Heavy Scientific Applicationsapplicationdata scalepassive solution (?)HACC20 PBuse up FS10xcosmology simulationper one-trillion-particlesimulation26 PB for Mira@ANLin needCESMclimate simulationAPS-UHigh-Energy X-RayBeams Experiments50%20% vsof h/w budget for storage2013 vs 2017PBhundreds ofbrain initiatives5h30mto reduce10xto storeNSF Blue Waters, I/O at 1 TBpsin need100-PB100xbufferor, connection at 100 GBpsin needThursday, Sept. 9, 2021 · CLUSTER ’21, Portland, Oregon, USA · cuSZ · 3 / 21

IntroductionDesignEvaluationBackmatterWhat does data reduction of scientfic application entail?Under the context of huge imbalance between computecapability and data management,throughputprocessing uality It is required to have strict and diverse errorcontrol mechanisms toward scientific discoveryand accurate postanalysisreduction Today’s scientific research is data driven at alarge scale (simulations or instruments). Areduction rate at 10 on demand.throughput “. . . , the rate of data that can be computedon the Summit supercomputer is five orders ofmagnitude greater than the bandwidth of itsparallel file system. The I/O bottleneck is onedriver of in situ analysis.”Thursday, Sept. 9, 2021 · CLUSTER ’21, Portland, Oregon, USA · cuSZ · 4 / 21

d Lossy Compressionrandomness: non-repeated, non-patterned std::rand() parity float (CESM-CLDHGH)randomness (noise)mantissa randomnessThursday, Sept. 9, 2021 · CLUSTER ’21, Portland, Oregon, USA · cuSZ · 5 / 21

d Lossy CompressionCESM-CLDHGH, data range: 0.89401052, error-bound: 1e-4, relative to the range float (32 effective bits) int (13 effective bits, incl. signum) unsigned int (8 effective bits)mantissa randomnessrounding, type-castingintegerized regarding error boundprediction recorded errors(of prediction from the previous)decreased bit randomness from left to rightThursday, Sept. 9, 2021 · CLUSTER ’21, Portland, Oregon, USA · cuSZ · 5 / 21

IntroductionDesignEvaluationBackmatterSZ, cuSZ, and cuSZ throughputCPU-SZ data-fidelity and compressibility oriented error-control framework [Di and Cappello 2016] quantization, unified N D predictor, highercompressibility [Tao et al. 2017] linear-regression, higher compressibility,esp. for data viz [Liang al. 2018]reductionqualityThursday, Sept. 9, 2021 · CLUSTER ’21, Portland, Oregon, USA · cuSZ · 6 / 21

IntroductionDesignEvaluationBackmatterSZ, cuSZ, and cuSZ throughputCPU-SZ data-fidelity and compressibility oriented error-control framework [Di and Cappello 2016] quantization, unified N D predictor, highercompressibility [Tao et al. 2017] linear-regression, higher compressibility,esp. for data viz [Liang al. 2018]cuSZ performance oriented CUDA implementation, featuring changeddata generation scheme changed, enablingmassive parallelism [Tian et al. 2020]reductionqualityThursday, Sept. 9, 2021 · CLUSTER ’21, Portland, Oregon, USA · cuSZ · 6 / 21

IntroductionDesignEvaluationBackmatterSZ, cuSZ, and cuSZ throughputCPU-SZ data-fidelity and compressibility oriented error-control framework [Di and Cappello 2016] quantization, unified N D predictor, highercompressibility [Tao et al. 2017] linear-regression, higher compressibility,esp. for data viz [Liang al. 2018]cuSZ performance oriented CUDA implementation, featuring changeddata generation scheme changed, enablingmassive parallelism [Tian et al. 2020]reductioncuSZ this work: expand usability by enhancing throughput or CR w/o compromising throughputqualityThursday, Sept. 9, 2021 · CLUSTER ’21, Portland, Oregon, USA · cuSZ · 6 / 21

IntroductionDesignEvaluationBackmatterDesign: Overview of ssless encode(3.1) error uct.(3.2) quantizationlossless decode(d, 1.1) Huff. decode(4) histogram(5) multibyte Huff.(d, 2)(d, 1.2) scatter outlier(3.3) gather t.decompressframework prequantize predict postquantize: 1 record error controling quantcode 2 create compressibility histogram lossless encode: make use of compressibilityThursday, Sept. 9, 2021 · CLUSTER ’21, Portland, Oregon, USA · cuSZ · 7 / 21

IntroductionDesignEvaluationBackmatterDesign: Overview of cuSZ ss encode(3.1) error uct.(3.2) quantizationlossless decodereversedpred-quant(d, 1.1) Huff. decode(4) histogram(5) multibyte Huff.(d, 2)(d, 1.2) scatter outliercompress(3.3) gather outlierLorenzoreconstruct.decompressframework prequantize predict postquantize: 1 record error controling quantcode 2 create compressibility histogram lossless encode: make use of compressibilityproblem statement (cuSZ) Huffman-only reduction rate 32 (float)extra pattern-finding stage low performance Lorenzo reconstruction is coarse-grained.Thursday, Sept. 9, 2021 · CLUSTER ’21, Portland, Oregon, USA · cuSZ · 7 / 21

IntroductionDesignEvaluationBackmatterDesign: Overview of cuSZ ss encode(3.1) error uct.(3.2) quantizationreversedpred-quant(d, 1.1) Huff. decode(4) histogram(5) multibyte Huff.(d, 2)(d, 1.2) scatter uct.choose(3.3) gather outliercuSZ lossless decode(3.1) error control(3.2) quantization(4.1) hist.compress(d, 1.1a)(5.a) RLEreversed(VLE ) RLE(d, 1.1b) Huff. decode(4.2) decidedecompress(d, 2)( VLE)Lorenzoreconstruct.Lorenzoreconstruct.(5.b) multibyte Huff.(d, 1.2) scatter outlier(3.3) gather outlierproblem statement (cuSZ) Huffman-only reduction rate 32 (float)extra pattern-finding stage low performance Lorenzo reconstruction is coarse-grained.solution (cuSZ ) workflow-optimized run-length encoding (RLE):RLE ( optional VLE) Lorenzo reconstruction N -D partial-sumThursday, Sept. 9, 2021 · CLUSTER ’21, Portland, Oregon, USA · cuSZ · 7 / 21

IntroductionDesignEvaluationBackmatterDesign, Compressibility-Awareness (1/4): ContextHACC 655361e-2 256 1e-31e-41e-21e-31e-4Figure 1: Error-controling quantcodes can be 1- ormulti-byte, depending on the diversity of quantcodes.Hurricaneqgqhqhgqgqhqhg22.721.1 7.580.8 3.890.8 20.331.0 9.511.0 4.821.0 31.021.5 10.011.1 5.011.0 43.671.8 18.411.1 10.311.1 24.801.0 17.041.0 9.761.0 58.762.4 24.651.4 12.991.3 qgqhqhgqgqhqhg61.212.5 20.781.1 9.981.0 24.241.0 18.381.0 10.291.0 75.503.1 28.131.5 12.501.2 118.943.9 28.251.2 12.870.8 30.241.0 23.921.0 15.271.0 164.395.4 40.171.7 17.951.2 CESMNyxTable 4: Averaged compression ratios (per dataset) of differentcompression schemes on 109 fields of 4 datasets with 3 error boundsof 10 2 , 10 3 , 10 4 (relative to value range). q denotes quantcodes asstarting point, h denotes customized variable-length encoding(multibyte-symbol Huffman coding), g denotes gzip-featured scheme.“ab” denotes scheme a precedes scheme b.Thursday, Sept. 9, 2021 · CLUSTER ’21, Portland, Oregon, USA · cuSZ · 8 / 21

IntroductionDesignEvaluationBackmatterDesign, Compressibility-Awareness (2/4): Using RLEWhat is RLE? a form of lossless compression [Robinson and Cherry 1967] :runs of data, sequences of consecutive same-valueelements, stored as value-count tuples example: aaaaaaaaaaaabbcaaaaaaaa (a,12)(b,2)(c,1)(a,8) pro: performs well on “smooth” data con: overhead from storing count (no prefixproperty like Huffman coding)Thursday, Sept. 9, 2021 · CLUSTER ’21, Portland, Oregon, USA · cuSZ · 9 / 21

IntroductionDesignEvaluationBackmatterDesign, Compressibility-Awareness (2/4): Using RLEWhat is RLE? a form of lossless compression [Robinson and Cherry 1967] :runs of data, sequences of consecutive same-valueelements, stored as value-count tuples example: aaaaaaaaaaaabbcaaaaaaaa (a,12)(b,2)(c,1)(a,8) pro: performs well on “smooth” data con: overhead from storing count (no prefixproperty like Huffman coding)How to determine the “smoothness”? inspiration: variogram [Cressie and Hawkins 1980]measuring multidimensional data variance, spatialdata, sampling basedh 2 i2γ (s1 , s2 ) var Z(s1 ) Z(s2 ) E Z(s1 ) Z(s2 ),where Z(s) is a spatial random field variant: madogram, using absolute difference Z(s1 ) Z(s2 ) in place of square variance further adjust to binary difference 0 vthis vnext,1 vthis ̸ vnextwhose averaged value (per distance) is RLEroughness; smoothness (1 roughness)Thursday, Sept. 9, 2021 · CLUSTER ’21, Portland, Oregon, USA · cuSZ · 9 / 21

IntroductionDesignEvaluationBackmatterDesign, Compressibility-Awareness (3/4)estimate Huffman CR from histogramP starting with entropy: H (X ) pi log2 pi ⟨b⟩ to denote the average bit-length redundancy R to denote the discrepancy between ⟨b⟩Huffand entropy H (X ) (i.e., R ⟨b⟩Huff H (X )). p1 to denote the probability of the most likely symbolestimate CR of 1) RLE and 2) RLE VLE32 RLE only: CRRLE ⟨b⟩Huff R 32 RLE VLE: CRRLE VLE CRRLE ·,⟨b⟩Huff R with CRRLE knownthe upper and lower bounds of R lower bound [Johnsen 1980] : R R 1 H (p1 , 1 p1 ), H (p1 , 1 p1 ) p1 log2 p1 0.4 (sufficiency)1p1 (1 p1 ) log211 p1 upper bound [Gallager 1978] : R R p1 0.086 (norestriction)Thursday, Sept. 9, 2021 · CLUSTER ’21, Portland, Oregon, USA · cuSZ · 10 / 21

IntroductionDesignEvaluationBackmatterDesign, Compressibility-Awareness (4/4)(a) Smoothness against distance. Yellow line: linear(b) Smoothness-probability of the most likely symbolregression of variances at distances.relationship.Figure 2: CESM FSDSC at 1e-2. Smoothness of error-controling quantcodes. to determine when to use RLE. For example, athreshold compression ratio can be set to 32 to find the desired smoothness, and the smoothness can be directed to theprobability of the most likely symbol. Empirical average bitwidth: 1.09 bit from Huffman coding (obtainable from histogram).Thursday, Sept. 9, 2021 · CLUSTER ’21, Portland, Oregon, USA · cuSZ · 11 / 21

IntroductionDesignEvaluationBackmatterDesign, Lorenzo Reconstructiondata reconstruction: d p q′d reconstructed datappredicted valueq′ error-controling “quantcode”All are integer values.Thursday, Sept. 9, 2021 · CLUSTER ’21, Portland, Oregon, USA · cuSZ · 12 / 21

IntroductionDesignEvaluationBackmatterDesign, Lorenzo Reconstructiondata reconstruction: d p q′d reconstructed datappredicted valueq′ error-controling “quantcode”All are integer values.Prediction is given by extrapolative{1,2,3}-D Lorenzo,(x 1, y 1) p[x] d[x 1]p[y,x] d[y 1,x 1] d[y 1,x] d[y,x 1](x 1, y) p[z,y,x] d[z 1,y 1,x 1] d[z 1,y 1,x d[z,y 1,x] d[z] d[z 1,y,y 1,x 1],x] (x, y 1)(x, y)(x 1, y 1, z 1) (x 1, y 1, z) (x 1, y, z 1) (x 1, y, z) (x, y 1, z 1) (x, y 1, z) (x, y, z 1)(x, y, z) d[z 1,y,x 1] d[z,y,x 1]Thursday, Sept. 9, 2021 · CLUSTER ’21, Portland, Oregon, USA · cuSZ · 12 / 21