Professor van de Geijn and TACC Advance Computational Methodology

Professor Robert van de Geijn is out to make big changes in a single field of mathematics that supports much of scientific computing, namely, dense linear algebra libraries. Working with students and research colleagues at TACC and elsewhere, van de Geijn (of the Computer Sciences Department at The University of Texas at Austin and member of the Institute for Computational Engineering and Sciences), hopes to construct what he calls "the final library."

Computational scientists in every field frequently use libraries of algorithms (routines for solving numerical problems), and there is a long tradition of library development. After some forty years of librarial expansion, an applications scientist working on any platform faces a bewildering choice of libraries full of methods for solving a specific problem or group of problems. The choices grow as the platforms themselves become larger, more diverse, and more complex. Yet often the specific functionality needed by the scientist is missing. "To attain a final library," van de Geijn says, "we must accommodate future architectures, languages, and even functionalities. Right now, developers must finagle or somehow extend old libraries to accommodate such changes. The final library inherently must take the form of a system that, given a description of the operation and target architecture, mechanically--that is, automatically--creates an optimized library for that operation and architecture."

Van de Geijn and a large group of collaborators have been using resources at TACC to develop both their methods and a user-friendly environment in which new methods can be developed. The collaborators include colleagues at UT, other academic institutions worldwide, industry, and national laboratories as well as three TACC researchers, Kazushige Goto, Dr. Kent Milfeld, and Dr. Avijit Purkayastha.

Linear Algebra

Linear algebra is among the premier mathematical tools of modern technology. In the world of complex, multivariable systems and computers, linear algebra finds uses throughout the natural and social sciences. Certainly, many problems in physics, chemistry, and biology are fundamentally nonlinear. Still, most of these can be solved numerically only by recasting them as linear systems. Boundary-element methods, for example, solve partial differential equations by, ultimately, solving discrete systems of linear equations.

Linear algebra methods operate on large matrices, arrays of (real or complex) numbers. These are called "dense" when most elements are nonzero and "sparse" when the presence of zeroes enables or demands specialized treatment to reduce calculation. "What we've been developing for several years now," says van de Geijn, "is a methodology for the systematic derivation and implementation of provably correct algorithms for dense linear algebra calculations."

Formal Derivation

Professor van de Geijn's interest in formal derivation methods dates from the advent of computer architectures with multilevel memories (caches, shared memories, distributed memories), but he points out that using such methods was long ago advocated by the late University of Texas computer scientist and ACM Turing Award winner Edsger Dijkstra. Dijkstra wrote:

The only effective way to raise the confidence level of a program significantly is to give a convincing proof of its correctness. But one should not first make the program and then prove its correctness, because then the requirement of providing the proof would only increase the poor programmer's burden. On the contrary: the programmer should let correctness proof and program grow hand in hand. (E.W. Dijkstra: "The Humble Programmer," 1972 Turing Award lecture, in ACM Turing Award Lectures: The First Twenty Years, 1966-1985, ACM Press, New York, 1987.)

"Ideally, algorithmic derivation should be a constructive process," van de Geijn says. "We first derive predicates that describe the desired states of the variables at various points in the program. Then we choose program statements to change the state of the variables from that described by one predicate to that entailed by the next predicate. Since the statements are chosen to make the predicates true, the program is guaranteed to be correct."

Apart from toy examples solved in some computer science classes, this marriage of programming and predicate logic has rarely been implemented for loop-based problems. While formal methods exist to determine whether a program is correct after it has been written, the systematic derivation of predicates beforehand has seldom been done. "In the mid-1990s," van de Geijn says, "we noted that, for a broad class of dense linear algebra operations typically implemented using a coded 'loop,' the predicate—or 'loop invariant'—can in fact be determined systematically. Moreover, this can be done for multiple loop invariants, leading to an entire family of algorithms for the same operation."

PLAPACK and POOCLAPACK

With these principles in mind, van de Geijn first developed PLAPACK, a parallel linear algebra package. PLAPACK was also influenced by the general application in high-performance computing of the object-based Message Passing Interface (MPI) programming paradigm. Parallelization of linear algebra algorithms in PLAPACK begins with partitioning and distributing ("blocking") vectors and matrices among processors. "A compute-efficient distribution is ideally dictated by the physical problem to be solved rather than by the matrices its expression generates," van de Geijn says.

One particularly enthusiastic user of PLAPACK is Dr. Brian C. Gunter of The University of Texas Center for Space Research. Gunter processes data generated by the Gravity Recovery and Climate Experiment (GRACE), a pair of satellites orbiting the Earth to deliver the most accurate maps ever of the Earth's gravity field. [For more on GRACE, see State of GRACE.]

"I've worked with PLAPACK and with Robert van de Geijn since 1997," Gunter says, "and the work has been invaluable in our data processing for GRACE. When we solve a problem with millions of rows and tens of thousands of columns of data, intuitive partitioning and object orientation are essential. PLAPACK lets us avoid dealing with indices or labels for each element, with no loss in performance." Gunter was so impressed with PLAPACK that he helped van de Geijn develop a parallel out-of-core extension called POOCLAPACK, which enables huge problems, larger than will fit in memory, to be run on massively parallel distributed-memory supercomputers without sacrificing performance.

"We've been running our GRACE calculations on Longhorn at TACC," Gunter says. "Any scientist fitting data to a model by least-squares calculations in dense linear algebra can benefit from van de Geijn's insights."

FLAME

These insights led directly to van de Geijn's ongoing project, the Formal Linear Algebra Methods Environment (FLAME), whose aim is to construct a final dense linear algebra library.

"FLAME is an environment in the sense that it supports developers in the construction a family of algorithms for a broad spectrum of matrix operations," van de Geijn says. The basic FLAME code contains applications programming interfaces that represent the derived algorithms at a high level in various languages (C, Fortran, Matlab, OpenMP), eliminating common sources of error due to failure of code to reflect the algorithm or to explicit indexing. "Our experience shows that this correctness, simplicity, and modularity does not impede performance," van de Geijn notes. Runtime cost and stability analyses, soon to be added, will also facilitate the choice of high-performance algorithms and code implementations.

The overall construction of code in FLAME is facilitated by a "worksheet" format that lists the preconditions and postconditions for the problem under study and the loop invariants associated with algorithmic steps. Once these are delineated, the coding steps to get from one condition to the next are easily filled in.

Dr. Kent Milfeld of TACC advises the FLAME project on extensions using the OpenMP standard for shared multiprocessor systems like TACC's Maverick. Dr. Avijit Purkayastha of TACC has worked on another van de Geijn project called InterCol. Also working with van de Geijn is Kazushige Goto of TACC, who is world renowned for constructing the fastest implementations of the Basic Linear Algebra Subprogram kernels. Goto was a visitor in van de Geijn's laboratory before joining TACC.

"Our collaboration with Robert van de Geijn will enable TACC to help develop, deploy, and support scalable, high-performance linear algebra software that makes it easier for all TACC users to solve more challenging problems," says Dr. Jay Boisseau, director of TACC. "We will also start promoting and distributing this library to our partners in state, national, and international collaborations, ensuring that researchers worldwide have access to the best tools for tackling the biggest problems."

"Scientists who are interested in exploring the advantages of the formal linear algebra derivation process should visit the various project web sites," van de Geijn says. "Our pursuit of the question of what a final library would look like is yielding fundamental contributions to computer science in terms of systematizing the process of library development. But it is also of immediate relevance to domain scientists, who want libraries that have broad functionality, high performance, portability, and accuracy—together with forward compatibility to future computer architectures and programming languages." With FLAME, van de Geijn says, the group is also addressing the challenge of forward compatibility to operations yet to be identified by the applied mathematics community. "Not your grandpa's static library," he says.

Web sites for van de Geijn projects:

PLAPACK: http://www.cs.utexas.edu/users/plapack/

FLAME: http://www.cs.utexas.edu/users/flame/