Millipede: Die-Stacked Memory Optimizations for Big Data Machine Learning Analytics

The technology-push of die stacking and application pull of Big Data machine learning analytics (BMLA) have created a unique opportunity for processing-near-memory (PNM). This paper makes four contributions: (1) While previous PNM work explores general MapReduce workloads, we identify three application characteristics of most BMLAs: (a) irregular-and-compute-light (i.e., perform only a few operations per input word which include data-dependent branches and indirect memory accesses); (b) compact (i.e., the relevant portion of the input data and the intermediate live data for each thread are small); and (c) memory-row-dense (i.e., process the input data without skipping over many bytes). These characteristics, except for irregularity, are necessary for bandwidth-and energy-efficient PNM, irrespective of the architecture. (2) Based on these characteristics, we propose memory optimizations for a "sea of simple MIMD cores (SSMC)" PNM architecture, called Millipede, which (pre) fetches and operates on entire memory rows to exploit BMLAs' row-density. Instead of this row-oriented access and compute-schedule, traditional multicores opportunistically improve row locality while fetching and operating on cache blocks. (3) Millipede employs well-known MIMD execution to handle BMLAs' irregularity, and sequential prefetch of input data to hide memory latency. In Millipede, however, one corelet prefetches a row for all the corelets which may stray far from each other due to their MIMD execution. Consequently, a leading corelet may prematurely evict the prefetched data before a lagging corelet has consumed the data. Millipede employs cross-corelet flow-control to prevent such eviction. (4) Millipede further exploits its flow-controlled prefetch for frequency scaling based on coarse-grain compute-memory rate-matching which decreases (increases) the processor clock speed when the prefetch buffers are empty (full). Using simulations, we compare PNM architectures to show that Millipede improves performance and energy, by 135% and 27% over a GPGPU with prefetch, and by 35% and 36% over SSMC with prefetch, when all three PNM architectures use the same resources (i.e., number of cores and on-processor-die memory) and identical die-stacking.