Scientists build first in-memory sorting chip without comparators

A new computing era arrives with the breakthrough in how computers can sort information. This vital function, at the heart of everything from searches on the internet to artificial intelligence, has long been restricted by the limits of how it may be accomplished by conventional computers.

But a team of scientists, directed by Peking University Professor Yang Yuchao, found a new and powerful way. Their research presents the first sort-in-memory hardware platform designed for nonlinear sorting—a problem that has proved elusive for engineers for half a century.

It seems simple to sort, but computers make it anything but simple. Most employ a configuration called the von Neumann architecture, in which memory and processor are distinguished. When data must be sorted, it must be moved from memory to processor, using time and energy. It is similar to sorting laundry alternating between two rooms. Back-and-forth is time-wasting, especially when sorting massive or complex data sets.

Researchers have been pondering processing-in-memory (PIM) as a way of eliminating that inefficiency for decades. Instead of moving data in and out of memory, PIM processes it in place. Memristors—tiny devices that store and process data simultaneously—have been promising contenders in this regard, especially for linear operations like matrix multiplication.

But sorting is different. Unlike summing numbers or matrix multiplication, sorting involves nonlinear operations—comparing values and swapping values—which may involve special units called comparators. These comparators are hard to implement efficiently within memristor arrays. That is where Professor Yang's group left their mark.

Instead of using comparators, they invented a new algorithm for sorting. The heart of their system is a new method called Digit Read. This approach avoids comparisons altogether by reading out committed pieces of data to sort determinations. Imagine quickly seeing only one digit from each number in a list and determining which go into which.

Doing this step by step, the system avoids direct comparisons altogether. Their hardware utilizes so-called 1T1R (one-transistor–one-resistor) memristor array. These tiny building blocks enable the system to compute and store without requiring extra circuitry. Digit Read acts as a smart filter, taking only what is necessary from each data point to sort it effectively and quickly.

Hardware alone wasn't sufficient. To actually accelerate, the team also came up with an amazing algorithm known as Tree Node Skipping (TNS). Typical sorting trees will look through each branch, and that is time-consuming. TNS, however, follows old routes, jumping sections of the tree where possible. It's like recalling where you have already looked for your misplaced keys so you wouldn't need to keep looking through those same spaces.

In order to deal with different data sizes and types, three more approaches were proposed by the researchers, which are known as Cross-Array TNS (CA-TNS):

Use of all these methods makes a versatile sorting engine that can be used across a great range of needs, from small datasets to big-data platforms.

To verify their system in reality, the team cobbled together a full demo setup. They created a real memristor chip and coupled it with hardware components like field-programmable gate arrays (FPGAs) and circuit boards. It was not an experiment in the lab—it was a working system that could be tested. And what they discovered was astonishing.

As compared to traditional sorting machinery, their system ran between 7.7 times as quickly. It used 160 times less energy and needed about 32 times less space. That kind of advancement would be a significant big deal in domains like mobile computing or data centers, where space is limited and expensive, as well as power. But figures tell only so much. The researchers also applied their sorter to real-world issues.

They applied it in one experiment to run Dijkstra's shortest path algorithm, a valuable navigation and mapping tool. It performed well to calculate the shortest distances among 16 subway stations in Beijing—fast and with very little power.

In a second experiment, they applied the sorter to neural network inference, that process by which AI models arrive at their conclusions. They combined their sorting method with a technique referred to as in situ pruning, which removes unnecessary parts of the AI model on the fly. Using a 3D object recognition model called PointNet++, the computer ran 15 times faster and used 67 times less energy than traditional methods.

This research not only improves the manner in which we sort data—it redefines the way computers could be constructed. Processing-in-memory, a one-time niche idea, now promises to take on the sophisticated work that modern technology demands.

With AI, machine learning, and edge computing becoming more critical, systems need to process vast amounts of data with minimal delay. Those functions are maxed out today. By developing a sorting accelerator that avoids the historic bottlenecks, Professor Yang's researchers have set a standard for smarter, faster machines.

More notably, this system is not just fast—it's adaptable. Because it doesn't employ static comparators, it can be adapted to different types of data and applications. That makes it useful not only in the current work but in the future, where unforeseen issues will always arise. And because it's interoperable with other PIM-based approaches, it can be part of an intelligent hardware environment at the larger level.

Whether it's driving a self-driving vehicle, managing information within an intelligent city, or powering the next AI boom, this kind of technology can potentially be a key player.

Prof. Yang and his team have addressed one of the hardest challenges of in-memory computing and come out with a solution that's fast, efficient, and flexible. By eliminating comparators and introducing new methods to read, sort, and skip data, they've brought PIM technology to enable nonlinear operations—something that was considered impossible by many.

Their technology may not be in your phone or laptop yet. But in the race to miniaturize, intellectualize, and optimize machines, this innovation brings the future an awful lot sooner. It's a giant step in computing—a step that could soon extend into AI, robots, big data, and beyond.

Research findings are available online in the journal Nature Electronics.

Like these kind of feel good stories? Get The Brighter Side of News' newsletter.