Researchers have developed a new programming technique that can make some calculations on graphics processing units, or GPUs, nearly four times faster by teaching computers to skip calculations that produce nothing useful.
The work, led by researchers at MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL), could improve computing for artificial intelligence, scientific simulations, graphics and other applications that process huge amounts of data.
At the center of the problem are matrices and tensors, which are essentially grids or higher-dimensional collections of numbers.
Multiplying these collections is one of the most common calculations performed in modern computing, particularly in AI.
Powerful computers and GPUs are extremely good at working with “dense” arrays, where most positions contain useful numbers. But real-world data is often “sparse,” meaning that many positions contain zeros.
Consider a high-resolution image showing the moon surrounded by a large black sky. Most of its pixels may represent empty darkness and contain values of zero. Storing and processing all those zeros wastes memory and computing power.
The problem becomes especially obvious during multiplication. Multiplying anything by zero always produces zero, yet computers may still perform millions of these pointless calculations.
The researchers developed a new approach to avoid that wasted work.
Their work builds on a compact way of describing matrix and tensor calculations called an Einsum, based on mathematical notation associated with Albert Einstein. Einsums allow programmers to describe complicated calculations using relatively little code.
However, standard Einsums do not automatically know where zeros are located inside sparse data. As a result, they can still tell GPUs to perform calculations involving those zeros.
The researchers created a modified system called an Indirect Einsum, or Insum. Instead of processing the original calculation directly, the system first reorganizes it so the computer knows where useful, nonzero values are located.
Sparse data can also be compressed by removing zeros entirely while keeping information about where the remaining values originally appeared. Insum understands this compressed structure and can perform calculations without repeatedly processing empty positions.
The researchers compare the idea to taking attendance in a classroom. Imagine a class has 100 assigned seats, but you already know 55 students are away on a field trip. Instead of calling all 100 names and waiting for responses, you could call only the 45 students who are expected to be there.
In experiments, the Insum compiler made some sparse GPU applications almost four times faster. It also dramatically reduced the amount of programming required, cutting the number of lines of code by factors ranging from about 200 to 4,500.
There are limitations. Modern GPUs are so efficient at dense calculations that data needs to contain a substantial number of zeros before converting it to the new format becomes worthwhile. The conversion process also currently requires some manual programming.
The researchers are now working to automate that process and tackle the harder problem of multiplying two sparse arrays.
If those challenges can be overcome, Insum could help GPUs spend less time calculating zeros and more time doing useful work—potentially making demanding AI and scientific applications faster and more efficient.
