Bunde presents on program efficiency

David Bunde, assistant professor of computer science at Knox College, recently gave a presentation on boosting the efficiency of computer programs at an international conference, the 2007 Workshop on Models and Algorithms for Planning and Scheduling Problems. The conference was held July 2-6 at Koc University in Istanbul, Turkey.

Bunde's presentation, "Power-aware scheduling for makespan," was one of 60 given by researchers from around the world at the biennial meeting on the study of processes used to solve problems in a number of areas, including manufacturing and transportation, as well as computer science. "Makespan" is the term used for the time required to complete all of the tasks in a series.

Bunde's speciality is the design of algorithms -- the processes used by computers to solve problems. He was part of a group of researchers from Sandia National Laboratories in New Mexico, the State University of New York at Stony Brook, and the University of Illinois at Urbana who received a 2006 "R&D 100" award from R&D Magazine. The award recognizes the team's development of a Compute Process Allocator, or CPA. The allocator increases both speed and efficiency of supercomputers by controlling how tasks are assigned among the thousands of individual processors that make up the supercomputer.

Research on Boosting Program Efficiency
"In multi-processor supercomputers, tasks are assigned to groups of processors that work in parallel," Bunde said. "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 you spend a lot of time doing the calculations to make the assignments, that's time you're not working."

Bunde said his group discovered that, even though processors are physically arranged in a three-dimensional networked "grid," it was faster to assign tasks as if processors were connected in a single line.

In winning the R&D Award, the Sandia research group reported an improvement of one-percent over methods that looked at a three-dimensional grid of processors, and a 23 percent improvement over previous one-dimensional methods of making assignments.

"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 group adapted a mathematical formula, the Hilbert space-filling curve, first described in 1891 by a German mathematician, David Hilbert.

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

"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 as 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."

The Sandia group reported that their method can be used to allocate tasks to over 10,000 processors, more than twice as many as prior methods.

Much of Sandia's work is classified, Bunde said, but typical problems that require supercomputers include simulations of physical events, such as nuclear explosions or rocket launches.

Bunde joined the Knox faculty in September 2006. He is a graduate of Harvey Mudd College and earned his doctorate in computer science at the University of Illinois at Urbana. Bunde's research interests include 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.