Professor David Bunde Shares in Computer Programming Patent

David Bunde, assistant professor of computer science at Knox College, helps computers run 1% faster. That's a significant improvement, when you're talking about a supercomputer that has 10,000 processors in a massive network.

Bunde is one of four computer scientists who recently received a patent for developing an improved method of assigning tasks in a computer program to a group of networked processors. U.S. Patent #7,565,657 covers "communication routing and processor allocation in multiple processor computing."

Bunde explains: "In multi-processor supercomputers, tasks are assigned to groups of processors that work in parallel. Intuitively, the best allocation assigns a task to processors that are close together, since this shortens the time necessary to send messages between processors working on the task. But if your program spends a lot of time on the calculations to make the assignments, that's time taken away from working on the task itself."

The work covered by the patent was completed in 2005 at the Sandia National Laboratory in New Mexico by Bunde, Vitus Leung, Michael Bender and Cynthia Phillips. At the time Bunde was a doing post graduate work at the University of Illinois at Urbana, and the other researchers were from Sandia and the State University of New York at Stony Brook. Their work also has been honored with an "R&D 100" award from R&D Magazine.

Bunde and his colleagues discovered that even though processors are physically connected in a three-dimensional network, it was faster to assign tasks as if processors were arranged in a line. "We found that it is more efficient to ignore the third dimension and allocate tasks to a processor and its neighbors on either side," Bunde said.

The research group reported an improvement of 1% over methods that looked at a three-dimensional grid of processors, and a 23% improvement over previous one-dimensional methods of making assignments. Their method can be used to allocate tasks to upwards of 10,000 processors, more than twice as many as prior methods.

The research uses a formula, the Hilbert space-filling curve, first described in 1891 by a German mathematician, David Hilbert. The formula calculates a path that passes through every point in a grid.

"We developed a 21st-century application for a 19th-century mathematical discovery," Bunde said.

"The Hilbert curve has a number of useful attributes for this problem," Bunde said. "Because it's 'space-filling' it doesn't leave any 'holes,' or unused processors in the neighborhood, when you're assigning processors to a task. It has excellent 'locality,' which means each processor is close to the other processors that are working on the same task. It is a simple formula, so you don't waste a lot of time figuring where to assign the tasks. And, finally, it is what mathematicians call a 'fractal' -- even though it is a simple formula, it can be scaled up to handle the thousands of processors in a supercomputer."

Typical problems that require supercomputers include simulations of physical events, such as nuclear explosions or rocket launches -- and much of Sandia's work is classified, Bunde said.

Bunde joined the Knox faculty in 2006. He is a graduate of Harvey Mudd College and earned his doctorate in computer science at the University of Illinois at Urbana. He has conducted research in computer program scheduling, in particular the balancing of speed with energy conservation. At Knox, he teaches introductory and advanced courses in computer science, including algorithm design.

Bunde has collaborated with several Knox students on projects to improve the performance of scheduling in supercomputers. Most recently, he was an advisor for an independent study project during the summer of 2009 with Peter Walker, a senior mathematics major from Portland, Oregon. Bunde and one of his colleagues at Sandia, along with Ojaswirajanya Thebe, a computer science major from Nepal who graduated from Knox in 2009, co-authored a paper that was published in the Proceedings of the 14th Workshop on Job Scheduling Strategies for Parallel Processing.

Bunde also has worked on computer allocation and scheduling studies with Knox student Christopher Johnson, a senior mathematics and computer science major from Hammonton, New Jersey; and with 2009 Knox graduates Kyle Sibley, a computer science major from Galesburg, Illinois; and Alexander Lindsay, a computer science major from Benicia, California.

Bunde has given presentations on raising the efficiency of computer programs at conferences worldwide, including the International Workshop on Models and Algorithms for Planning and Scheduling Problems.

Founded in 1837, Knox is a national liberal arts college in Galesburg, Illinois, with students from 47 states and 48 countries. Knox's "Old Main" is a National Historic Landmark and the only building remaining from the 1858 Lincoln-Douglas debates.