The 2021 Turing Award

If a machine is expected to be infallible, it cannot also be intelligent.—Alan Turing

Jack Dongarra has just won the 2021 Turing Award. Congrats to him.

Dongarra is a Distinguished Professor of Computer Science in the Electrical Engineering and Computer Science Department at the University of Tennessee. He has connections to the nearby Oak Ridge National Laboratory, to Rice University, and in England to the University of Manchester—Turing’s academic home. The nub of ACM’s article says the following, with linear algebra emphasized:

Dongarra’s major contribution was in creating open-source software libraries and standards which employ linear algebra as an intermediate language that can be used by a wide variety of applications. These libraries have been written for single processors, parallel computers, multicore nodes, and multiple GPUs per node. Dongarra’s libraries also introduced many important innovations including autotuning, mixed precision arithmetic, and batch computations.

Dongarra’s doctoral advisor was Cleve Moler decades ago in 1980. I always think we should thank our advisors—having been one myself. But they continued on parallel tracks in the 1980s. Moler had invented MATLAB in the 1970s, but with the advent of IBM PCs in the 1980s, realized their promise for bringing advanced numerical computations into wide use. Moler and John Little and Steve Bangert co-founded MathWorks in 1984 to market their rewrite of MATLAB in C. Dongarra went on to co-write a host of mathematical tools: BLAS, LAPACK (which succeeded his work with Moler and others on EISPACK and LINPACK), ATLAS, HPCG, and much more.

Why The Turing Award?

Dongarra received the Turing for his software—code that has had significant impact in many areas of computational science from data analytics, healthcare, renewable energy, weather prediction, genomics, and economics, to name a few. His work was over four decades of writing code that can solve linear systems. Such systems occur in just about all of engineering and science. They challenge us because we constantly wish to solve bigger and more difficult systems. And we are able to solve bigger systems because computers continue to get faster—able to do more operations per second.

However, the challenge was and is that while computers get faster every year, how they get faster remains involved. They cannot just compute faster but how they get faster continues to be complex. If a computer just got faster every year, then Dongarra would not have been able to win a Turing award. That how they get faster is more complex, more involved, that made his Turing award possible.

Why So Hard?

What are some of the challenges that Dongarra had to fight, and continues to fight? We can build off the following quip by the Canadian software developer Craig Bruce:

“It’s hardware that makes a machine fast. It’s software that makes a fast machine slow.”

And in 1980 we could add: what could make an IBM PC fast?

The goal of Dongarra’s software was to run fast on the current hardware systems. The challenge over the decades is simple: As hardware systems were improved in performance they did not simply get faster. They needed to change how they worked in order to get faster. The systems changed from single processors, to parallel computers, multicore nodes, and multiple GPUs per node. These changes made the ability to exploit the potential performance harder and harder.

Let’s assume, for example, that the hardware could not go 100X faster but could execute 100 operations at the same time. Then provided we can exploit this parallelism we can make the hardware seem to be 100 times faster. But if we cannot exploit this, we are in trouble. This is the key issue that Dongarra faced. This challenge is exactly what made his work so difficult and important.

The Test of Time

The solutions found by Dongarra and his co-workers were definitive enough, and the core of linear algebra in LINPACK pure enough, that it could yield a salient benchmark of hardware power. The LINPACK benchmark suite won agreement by the early 1990s as giving the definitive measure of hardware power. A decade ago, they began updating it to involve HPCG.

Thus it is not enough to say that this work has stood the test of time: it is the test of time. And this is carrying into the future. A high LINPACK score in 2013 was an early indicator of the power achievable by D-Wave’s quantum adiabatic hardware. An article last month titled “The Race to Quantum Advantage Depends on Benchmarking” includes LINPACK as a contender. There is recent work toward a more-tailored quantum LINPACK benchmark.

Open Problems

Some interesting milestones about the Turing awards are: The first recipient of the award, in 1966, was Alan Perlis, an American computer scientist who wrote the compiler for the ALGOL computer programming language. The first woman to win the prize was Frances Allen, in 2006, for her work in compiler optimization, which contributed to the development of parallel execution in multiprocessing. The youngest recipient was Donald Knuth, who was 36 when he received the award in 1974 for his work on algorithms and computer programming. The oldest recipient was Alfred Aho, who was 79 when he received the award in 2020 for his work on algorithms and the theory of programming language implementation. I knew all the above winners pretty well. Rich DeMillo and I wrote a paper with Perlis in 1979.

Turing himself was also a pioneer in AI, of course. He thought about how computers could reason, how they could think. What directions will the Turing Awards take in the future—and will they reflect this side of Turing’s vision more?