In the era of big data, min/max searching from bulk data arrays is one of the most important and widely used fundamental operations in data-intensive applications such as sorting, ranking, bioinformatics, data mining, graph processing, and route planning. Online news and social media require real-time ranking using fast min/max searching from massive data stores to evaluate trending information to display on their sites.
The process of min/max searching is a time-consuming computation in many large-scale graph processing algorithms. However, implementing fast and efficient min/max searching for big data faces significant challenges in conventional computer systems with respect to memory architecture and computing algorithms. Within memory architectures, the well-known ‘memory-wall’ challenge causes significant issues, like long off-chip memory access latency, data congestion due to limited memory bandwidth and two orders higher energy consumption in data movement than data processing. Within computing algorithms, min/max searching is in general a comparison-based algorithm, where the CPU needs to compare every element serially of colossal amounts of raw data. Such computing properties causes min/max searching to demand ultra-high computing resources and power. There is a need for efficient min/max searching algorithms and supporting hardware for bulk data storage that greatly minimizes the time and cost associated with the computing.
Researchers at Arizona State University (ASU) have developed a min/max-in-memory algorithm to find the minimum/maximum of an array stored in dynamic random-access memory (DRAM). Additionally, the ASU researchers have developed a hardware that hosts and computes the data via in-DRAM computing. The algorithm and hardware support parallel in-memory searching for minimum and maximum values of bulk data stored in DRAM as unsigned and signed integers, fixed-point and floating-point numbers.
Related publication: Max-PIM: Fast and Efficient Max/Min Searching in DRAM
Potential Applications:
- Accelerate min/max searching within big data widely used by:
- cloud computing
- social media
- online news
- data center providers
- bioinformatics
Benefits and Advantages:
- Optimized with a one-cycle fast XNOR logic in-DRAM operation and in-memory data transpose
- Example experiments utilizing the algorithm and hardware in big data sorting and graph processing applications produced speeds up to ~50x and ~1000x faster than GPU and CPU while only consuming 10% and 1% of the energy, respectively
- Compared to in-DRAM computing platforms, i.e., Ambit and DRISA, ASU’s algorithm and hardware increases speed of computations by ~3-10x