Filters

Settings

Now showing1 - 2 of 2
  • Some of the metrics are blocked by your 
    consent settings
    Item type:Publication, Access status: without files ,
    On the parallel reconstruction from pooled data
    (IEEE, 2022)
    Gebhard, Oliver
    ;
    Hahn-Klimroth, Max
    ;
    Kaaser, Dominik
    ;
    Loick, Philipp
    In the pooled data problem the goal is to efficiently reconstruct a binary signal from additive measurements. Given a signal sigmain 0, 1n, we can query multiple entries at once and get the total number of non-zero entries in the query as a result. We assume that queries are time-consuming and therefore focus on the setting where all queries are executed in parallel. For the regime where the signal is sparse such that VertsigmaVert₁= o(n) our results are twofold: First, we propose and analyze a simple and efficient greedy reconstruction algorithm. Secondly, we derive a sharp information-theoretic threshold for the minimum number of queries required to reconstruct s with high probability. Our first result matches the performance guarantees of much more involved constructions (Karimi et al. 2019). Our second result extends a result of Alaoui et al. (2014) and Scarlett & Cevher (2017) who studied the pooled data problem for dense signals. Finally, our theoretical findings are complemented with empirical simulations. Our data not only confirm the information-theoretic thresholds but also hint at the practical applicability of our pooling scheme and the simple greedy reconstruction algorithm.
    Publicationtype: Conference Paper
      26
  • Some of the metrics are blocked by your 
    consent settings
    Item type:Publication, Access status: with files ,
    Memory access granularity aware lossless compression for GPUs
    (IEEE, 2022)
    Lal, Sohan
    ;
    Renz, Manuel
    ;
    Hartmer, Julian
    ;
    Juurlink, Ben H. H.
    High-bandwidth off-chip memory has played a key role in the success of Graphics Processing Units (GPUs) as an accelerator. However, as memory bandwidth scaling continues to lag behind the computational power, it remains a key bottleneck in computing systems. While memory compression has shown immense potential to increase the effective memory bandwidth by compressed data transfers between on-chip and off-chip memory, the large memory access granularity (MAG) of off- chip memory limits compression techniques from achieving a high effective compression ratio. Unfortunately, state-of-the-art lossless memory compression techniques do not take the large MAG of off-chip memory into account. A recent study has used MAG-aware approximation to increase the effective compression ratio, however, not all applications can tolerate errors, which limits its applicability. We propose extensions and GPU-specific optimizations to adapt a lossless memory compression technique to a MAG size to increase the effective compression ratio and performance gain. Our technique is based on the well-known Base-Delta-Immediate (BDI) compression technique that compresses a memory block to a common base and multiple deltas. We leverage the key observation that deltas often contain enough leading zeros to compress a block to a multiple of MAG without any loss of information. We show that MAG-aware BDI provides, on average, a 48% higher effective compression ratio, 10% (up to 27%) higher speedup, and 16% bandwidth reduction compared to normal BDI. While BDI, FPC, and CPACK have a similar compression ratio, MAG-aware BDI outperforms FPC, CPACK, and SLC by 56%, 47%, and 33%, respectively.
    Publicationtype: Conference Paper
    Scopus© Citations 1  175  1066