|
|||||||||||||||||
|
|||||||||||||||||
 |
NCSA NEWS |
||||||||||||||||
|
Nug30—Unsolved for More than Three Decades—Cracked on the Gridreleased July 18, 2000
Contact CHAMPAIGN, IL — In what one researcher called one of "the largest Grid computing successes for the Alliance" to date, researchers at National Computational Science Alliance partners University of Iowa and Argonne National Laboratory announced in June that they used the Partnerships for Advanced Computational Infrastructure (PACI) Grid to solve the nug30 quadratic assignment problem (QAP). Nug30 had gone unsolved since 1968 when it was first proposed as a test problem in the area of applied mathematics known as location theory. Kurt Anstreicher, a professor of management sciences at the University of Iowa, and his student Nathan Brixius designed the algorithm that solved the nug30 problem. They worked in collaboration with Jeff Linderoth and Jean-Pierre Goux of Argonne to parallelize their QAP algorithm using a variety of Alliance Grid resources and software tools. Processors from machines at eight locations around the world using five different computing platforms were harnessed in the seven-day nug30 run-effectively creating a single, integrated parallel computing platform. The QAP solution consumed more than 96,000 CPU-hours. An average of about 650 processors were used to solve the problem at any given time, with a peak of 1,009. Processors at Argonne, the University of Wisconsin, Georgia Tech's Interactive High Performance Computing Laboratory, the Italian Istituto Nazionale di Fisica Nucleare, the National Center for Supercomputing Applications (NCSA), the Albuquerque High Performance Computing Center, Columbia University, and Northwestern University participated in the nug30 run. SGI Origin2000 supercomputers at Argonne and NCSA also contributed. "Computing like this, using different systems in different locations to create a single [problem-solving] environment, has opened the door to addressing new, important scientific applications," says Jeff Linderoth, a research scientist in the MetaNEOS project at Argonne. "However, as this sort of heterogenous, distributed computing becomes more prevalent, it has to become easier." The tools deployed by Alliance partners made the massive nug30 computation easier, even for intrepid early users like the team from Argonne and Iowa. The Condor high-throughput computing system was used to harness the power of desktop computers and commodity clusters by monitoring their status and running jobs on them when they are available. The MetaNEOS project's Master-Worker library was used to implement the algorithm on Condor, coordinating the activities of the large number of processors in solving the problem. Finally, the Globus toolkit was used to setup access to some of the computational resources. Condor was developed at Wisconsin; MetaNEOS's Master-Worker was developed by Argonne and Wisconsin; and Globus development is centered at Argonne and the University of Southern California, with NCSA and others also contributing. "The most important thing to remember here is that this wasn't a demo," says Miron Livny, a computer science professor at Wisconsin who heads the Condor project. "The nug30 team wasn't working in any sort of bubble. They were using generic grid middle-ware, on production grid resources, in a very dynamic multi-user environment." "This tremendous achievement demonstrates that the Grid being established within the Alliance can have a real impact on the practice of science," says Ian Foster, a senior scientist at Argonne and computer science professor at the University of Chicago who co-leads the Globus project. "As grid services provided by Globus and Condor enter the infrastructure, we can expect that computations such as these will become easier and breakthrough results commonplace." In QAPs like nug30, there are a set of n locations and a set of n facilities, and each facility must be assigned a location. To measure the cost of each possible assignment, the flow between each pair of facilities is multiplied by the distance between the pair's assigned locations, and then a sum is taken over all of the pairs. In nug30, for example, 30 facilities must be assigned to 30 fixed locations, and the goal is to find the assignment that minimizes total cost of transferring material between the facilities. QAP problems like these present themselves in a variety of fields, from designing the layout of hospitals or factories to designing computer chips. Despite the simplicity of the problem statement, QAPs are incredibly difficult to solve to optimality. "The complexity of a QAP like nug30 is really hard to imagine," says Anstreicher. "Without the use of metacomputing, the solution process would have required about 7 years on a fast workstation, even with our very sophisticated algorithm."
|
||||||||||||||||
|
|
|||||||||||||||||
