Clutch: High Performance Vector-Scalar Comparison using DRAM via Chunked Temporal Coding

Summary

Vector–scalar comparison is a fundamental computation primitive that compares each element in a vector against a single scalar value. It is widely used in a broad range of data-intensive workloads from databases to machine learning. Due to its low computational intensity, the execution of this operation tends to be memory-bound, especially for large vectors, thereby limiting the utilization of compute resources. Processing-using-DRAM (PuD) is an emerging computing paradigm that performs massively parallel bitwise operations directly within the DRAM array, alleviating off-chip data movement. Unfortunately, no prior work proposes an efficient PuD-based solution tailored to vector–scalar comparisons. Existing PuD-based approaches require many DRAM commands because the comparison’s algorithmic complexity grows with operand bit-width in the bit-serial execution model, which is inherently induced by current PuD architectures. As a result, this command overhead becomes the dominant performance bottleneck, limiting application-level speed up. We propose Clutch, a novel data representation and comparison algorithm for accelerating vector–scalar comparisons in PuD systems with high efficiency and scalability. Our key idea is twofold. First, to reduce the number of DRAM commands required for comparison, Clutch adopts temporal coding for vectors, where each value is encoded as a sequence of leading ones. This enables lookup-based comparisons, where comparing against a scalar input simply involves accessing the corresponding DRAM row. Second, Clutch leverages our key insight that a divide-and-conquer approach enables scalable lookup-based comparisons without incurring a prohibitive memory footprint at high bit-precision. Specifically, Clutch partitions the operand into multiple multi-bit chunks which can be compared independently using compact lookup tables, and merges per-chunk results through a procedure designed to execute efficiently on PuD. Clutch provides a flexible tradeoff between throughput and memory usage by adjusting chunk count. Experimental results on two applications, predicate evaluation and decision tree inference, demonstrate that Clutch improves end-to-end application throughput (and energy efficiency) by an average of 12 × (69 ×) over highly-optimized CPU and GPU execution and 2.9 × (3.0 ×) over the state-of-the-art bit-serial PuD implementation. Notably, we present, to our knowledge, the first mapping of decision tree inference to PuD execution, extending PuD to a new application domain. Our results demonstrate that DRAM can serve as a high-performance and energy-efficient computing substrate for comparison-intensive workloads.