Good combination

Sandia National Laboratories’ Bruce Hendrickson has built a career on connections. No, he’s not a social climber. He’s spent his career at the New Mexico lab studying how structures of connections underlie complex computer simulations, enable sophisticated data analysis and inform efficient algorithms. Along the way, he’s also made connections between disparate mathematical and scientific fields.

This penchant for connecting led Hendrickson to co-found the field of combinatorial scientific computing (CSC), a development essential for the phenomenal growth and success of scientific computing on massively parallel world-leading machines.

As a result, he’s helped provide new ways to understand deep, hidden structures in our world – from protein folding, to genome sequences, to computational engineering.

Hendrickson’s work led to recognition as a 2012 Fellow of the Society for Industrial and Applied Mathematics (SIAM). He and other new fellows will be honored at SIAM’s annual meeting this month in Minneapolis.

Hendrickson arrived at Sandia in 1989, newly married and fresh from a Ph.D. in computer science at Cornell University, for what was to be “a lark” – a limited-duration adventure for the East Coast couple in the arid Southwest.

But at the lab Hendrickson finally found an intellectual home. He’d studied math as an undergraduate, earned a master’s in physics and his doctorate in computer science, all the while feeling something of a disciplinary outsider. At Sandia he found himself immersed in an intellectual stew for which he was a missing ingredient.

“I arrived at the laboratory with this weird hodge-podge of degrees and backgrounds, and it allowed me to talk to a lot of people,” Hendrickson recalls today as Sandia’s senior manager for computational sciences and mathematics. “I could talk to chemists about the quantum mechanical simulation they were trying to do, I could talk to computer scientists about algorithmic analysis, and I could talk to mathematicians about the linear algebra challenges that they were struggling with. They all needed each other but sometimes found it difficult to communicate.”

 Almost 20 years later, Chaco still is downloaded hundreds of times a year.

Hendrickson became a multidisciplinary connector at the lab when it faced a critical challenge that required just that. He’d arrived as the lab was shifting from scientific computing with vector- based supercomputers to today’s massively parallel machines.

“I joined a dynamic young group at Sandia that had a vision for transforming scientific computing,” Hendrickson says.

The first machine he used at Sandia was an experimental parallel supercomputer built by nCube – a company founded in 1983 by former Intel employees frustrated by the chipmakers’ unwillingness to develop parallel platforms. In 1987, Sandia researchers working on the nCube 10 won the first Gordon Bell Award.

But adapting efficient, powerful codes for parallel supercomputers involved more than just a little algorithmic tweaking; it required looking at problems in a whole new way.

“With each problem someone would start by speaking the language of physics,” Hendrickson says. “But as you peeled back the layers, what they were trying to do was to take a computation of a particular structure and map it on to the processors of a parallel machine in an effective way. And in the end it was almost always a combinatorial problem.”

The term combinatorial scientific computing didn’t exist then. But Hendrickson was steeped in a theoretical mathematical tradition that was to find its applied calling in parallel supercomputers: graph theory.

Traditional scientific computing – such as for advanced 3-D simulations – has grown out of fields like differential equations and linear algebra. Combinatorial scientific computing uses graph algorithms to exploit structure in the computation or in the computer and thereby enable greater efficiency. These graph algorithms have turned out to be essential for the efficient use of parallel supercomputers.

“To figure out how to get all the data to where it needs to be, at the right time, to keep all the processors busy, without stalling or using so much power that you overheat and melt the silicon – these are incredibly complicated scheduling and partitioning and load-balancing challenges,” Hendrickson explains. “The techniques to solve them have nothing to do with the numerical methods for solving the heat equation or whatever differential equation you are trying to model. Instead, they have to do with looking at the underlying structure of the computation, the constraints that an architecture imposes, and solving difficult combinatorial optimization problems.”

In 1993, Hendrickson and Sandia colleague Rob Leland released Chaco, advanced software based on graph algorithms for optimally partitioning the workload among thousands of processors on a parallel computer. Almost 20 years later, Chaco still is downloaded hundreds of times a year and used at most of the major computing centers around the world to increase parallel code efficiency.

During the past two decades, CSC has gone from an outlier to a mainstream component of scientific computing, Hendrickson says. One driver has been the rise of data-intensive computing, ­ such as in genomics and proteomics and increasingly in all fields as the mix of more and better sensors produce a deluge of data. Graph algorithms and CSC are key tools for finding the meaningful connections amid forests of data.

The importance of graph algorithms to data mining has generated interest in developing computers that are graph friendly and even built with CSC in mind. Hendrickson is on the steering committee of Graph 500 – a sister organization to the TOP500 supercomputer list – that promotes the development of benchmarks for data-intensive supercomputing.

Today, as a manager of 80 Ph.D. mathematicians and computational scientists, Hendrickson says the current challenge is to mature scientific computing to support its application to a wide variety of “high- consequence” engineering challenges – from nuclear weapons safety systems to nuclear reactor design.

“As computers and algorithms get faster, new scientific and engineering opportunities arise,” Hendrickson says. “Today, we routinely do things that were impossible a decade ago, and we need to be creating the mathematics to solve the challenges a decade hence. It will be critical to quantitatively understand the range of uncertainties in our simulations to drive deep understanding about the systems we build.”

Almost a quarter century after he arrived, Hendrickson still is connecting people, combining disciplines and thinking about how to integrate more new math to support Sandia’s missions.