Optimizing the Grid with Master Worker

When Prof. Jeff Linderoth begins his presentations on the nation's coming computational grid, he can't resist resorting to humor.

Assuming the role of a TV game show host, Linderoth announces the results of an informal survey.

One hundred people, he says, were asked to name one common use of the Internet.

The top five answers - e-mail, looking up answers to homework problems, looking up stock quotes, downloading MP3s, and reading stories on entertainment stars.

Not a single respondent, says Linderoth, an assistant professor of industrial and systems engineering, cited super-computing as a common use of the Internet.

But sometime soon, he says, people around the world will be able to use their PCs to harness the power of hundreds or even thousands of computers to solve large-scale computational problems.

Engineers at remote locations on the computational grid will make this possible by scheduling and distributing resources, shifting available power from idle or under-utilized computers to online problem solvers much the same as the national power grid meets peak energy demand in Ohio with electric power produced in Pennsylvania or New York.

The national computational grid will result in what some have called the "democratization of computing power," says Linderoth. It will grant John and Jane Doe the same super-computing power that until now has been available only to those with proper credentials and access to labs with specialized computer networks.

But first, says Linderoth, researchers must develop software that can recognize available resources, schedule computing for those resources, handle faults, and recover from failures.

Linderoth and his colleague, Stephen J. Wright of the University of Wisconsin-Madison, recently received a three-year, $209,000 grant from the National Science Foundation through its National Middleware Initiative (NMI).

Middleware is defined on NSF's web site as software that links two or more separate applications across the Internet or across local area networks to enable users to share computers, data and other distributed resources and also to develop grid technologies to facilitate problem-solving.

Examples of potential middleware applications, says the site, include:

• The collaboration of thousands of scientists worldwide to design and operate a high-energy physics laboratory
• A complex scheme by industry and higher education to verify students' electronic identities and allow remote access to libraries
• The multi-faceted response by geologists, engineers, and emergency and medical personnel to an oil spill or similar catastrophe

Linderoth's goal is to develop Master Worker, a reliable, easy-to-use software tool that can execute complex numerical algorithms on computational grids and also be easily integrated with other NMI middleware.

As one small part of the larger NMI effort, Linderoth says, Master Worker will enable scientists, engineers and others to write very simple functions in order to use the computational grid for their large-scale computing problems.

Master Worker will accomplish this by taking one large computation and solving it in a distributive fashion, Linderoth says, much as a master assigns tasks according to which resources, or workers, are available.

To demonstrate the power and practicality of the computational grid, Linderoth and coworkers will use the Master-Worker software to solve numerical optimization problems.  Using the Master Worker paradigm, an algorithm for numerical optimization can be distributed or parallelized to run on resources made available on the computational grid. The software tool will ensure fault tolerance and will be robust, or flexible enough, to shift and make use of alternate resources if additional users come on line while a user is running a large computational problem.

Linderoth was a computation expert from 1998 to 2000 at the Mathematics and Computer Science Division at Argonne National Laboratory in Chicago, which has done much of the conceptual and software-design work in grid computing. He was named the Enrico Fermi Scholar at Argonne in 1999.

Linderoth was a member of the Argonne and University of Iowa team that solved the nug30 Quadratic Assignment Problem, a complex facility-location problem that had been unsolved for over 30 years. The computation took one week of calendar time and 11 years of CPU time, as 653 machines participated.

>From 2000 to 2002, Linderoth served as a senior consultant with Axioma Inc., a small start-up based in Atlanta, Ga., which makes optimization-based financial products.

In 2002, he was awarded the SIAM (Science and Industry Advance with Mathematics) Optimization Prize, which is given once every three years for the most outstanding paper on a topic in optimization that is published in English in a peer-reviewed journal.

Linderoth holds a Ph.D. in industrial and systems engineering from the Georgia Institute of Technology.