MIT Develops New Programming Language for High-Performance Computers

With a tensor language prototype, “speed and correctness do not have to contend … they can go with each other, hand-in-hand.”

Superior-effectiveness computing is necessary for an ever-increasing selection of tasks — these kinds of as image processing or several deep learning applications on neural nets — the place a person ought to plow by means of immense piles of information, and do so fairly speedily, or else it could choose absurd quantities of time. It is broadly considered that, in carrying out operations of this form, there are unavoidable trade-offs involving speed and dependability. If pace is the top precedence, according to this watch, then reliability will probable go through, and vice versa.

Having said that, a crew of scientists, based mostly at A Tensor Language” (ATL), last month at the Principles of Programming Languages conference in Philadelphia.

“Everything in our language,” Liu says, “is aimed at producing either a single number or a tensor.” Tensors, in turn, are generalizations of vectors and matrices. Whereas vectors are one-dimensional objects (often represented by individual arrows) and matrices are familiar two-dimensional arrays of numbers, tensors are n-dimensional arrays, which could take the form of a 3x3x3 array, for instance, or something of even higher (or lower) dimensions.

The whole point of a computer algorithm or program is to initiate a particular computation. But there can be many different ways of writing that program — “a bewildering variety of different code realizations,” as Liu and her coauthors wrote in their soon-to-be published conference paper — some considerably speedier than others. The primary rationale behind ATL is this, she explains: “Given that high-performance computing is so resource-intensive, you want to be able to modify, or rewrite, programs into an optimal form in order to speed things up. One often starts with a program that is easiest to write, but that may not be the fastest way to run it, so that further adjustments are still needed.”

As an example, suppose an image is represented by a 100×100 array of numbers, each corresponding to a pixel, and you want to get an average value for these numbers. That could be done in a two-stage computation by first determining the average of each row and then getting the average of each column. ATL has an associated toolkit — what computer scientists call a “framework” — that might show how this two-step process could be converted into a faster one-step process.

“We can guarantee that this optimization is correct by using something called a proof assistant,” Liu says. Toward this end, the team’s new language builds upon an existing language, Coq, which contains a proof assistant. The proof assistant, in turn, has the inherent capacity to prove its assertions in a mathematically rigorous fashion.

Coq had another intrinsic feature that made it attractive to the MIT-based group: programs written in it, or adaptations of it, always terminate and cannot run forever on endless loops (as can happen with programs written in Java, for example). “We run a program to get a single answer — a number or a tensor,” Liu maintains. “A program that never terminates would be useless to us, but termination is something we get for free by making use of Coq.”

The ATL project combines two of the main research interests of Ragan-Kelley and Chlipala. Ragan-Kelley has long been concerned with the optimization of algorithms in the context of high-performance computing. Chlipala, meanwhile, has focused more on the formal (as in mathematically-based) verification of algorithmic optimizations. This represents their first collaboration. Bernstein and Liu were brought into the enterprise last year, and ATL is the result.

It now stands as the first, and so far the only, tensor language with formally verified optimizations. Liu cautions, however, that ATL is still just a prototype — albeit a promising one — that’s been tested on a number of small programs. “One of our main goals, looking ahead, is to improve the scalability of ATL, so that it can be used for the larger programs we see in the real world,” she says.

In the past, optimizations of these programs have typically been done by hand, on a much more ad hoc basis, which often involves trial and error, and sometimes a good deal of error. With ATL, Liu adds, “people will be able to follow a much more principled approach to rewriting these programs — and do so with greater ease and greater assurance of correctness.”

Reference: “Verified Tensor-Program Optimization Via High-Level” by Amanda Liu, Gilbert Louis Bernstein, Adam Chlipala and Jonathan Ragan-Kelley, 12 January 2022, Proceedings of the ACM on Programming Languages.
DOI: 10.1145/3498717