Scheme
smooths parallel processing
By
Kimberly Patch,
Technology Research NewsComputer calculations are blazingly fast. Today's desktop models carry out several billion computing steps in a single second. But very large problems that involve simulating events that have many variables -- like the workings of financial markets or the progress of traffic on a large computer network -- require still faster calculations.
One strategy is to distribute portions of a problem to several different computers that can work on it in parallel. It is a complicated proposition, however, to portion a problem into discrete tasks, coordinate often far-flung processors as they solve interrelated parts of the problem, and then put the parts together to form an answer.
Researchers from Rensselaer Polytechnic Institute, Mississippi State University, Los Alamos National Laboratory and Florida State University have drawn from nature to coordinate large numbers of parallel processors without the top-down management of a central plan.
In earlier work the researchers had discovered that the pattern of parallel event timing can be described by the same mathematical equation that describes crystal growth.
They applied equations that govern smooth growth patterns in crystals to interactions between processors; this enabled the parallel processors to carry out computations more uniformly in time so that no one processor gets very far ahead of the others, according to Gyorgy Korniss, an assistant professor of physics at Rensselaer Polytechnic Institute. "We looked at the parallel simulation itself as a complex system," he said.
The work could translate to more efficiently running systems that coordinate tasks like assigning channels on-the-fly to cell-phone users.
When a system's variables are numerous, random and asynchronous -- like calls arriving in cellphone networks, infections arising in epidemiological models, or troops moving in battlefield simulations -- coordinating them becomes a big challenge that can itself take a lot of compute power. This coordination, however, is essential to keeping cause and effect straight.
When the number of parallel events, or pieces of a problem, reaches tens of thousands, things start to slow down, according to Korniss.
This is because an event can only be safely updated by one of the processors working on a problem if the resulting change is guaranteed not to violate causality in the entire simulation, otherwise it must wait. In simulating "a huge system using a large number of processors, the process of saving and collecting data from the processors, which have progressed to very different simulated times, can become a bottleneck," said Korniss.
The researchers' method irons out these bumpy waiting periods.
In sharp contrast to standard parallel processor architectures, which periodically synchronize processors globally, the researchers' scheme does not use any type of central control. Instead, the processors communicate only with their nearest neighbors and one randomly chosen processor from anywhere on the network.
Checking in periodically with these random processors allows the whole system to remain closely in sync, said Korniss. "This essentially results in a small-world network," he said.
Small world networks contain shortcuts that make it possible to communicate across large populations using relatively few intervening connections. Small-world social networks are responsible for the six-degrees of separation phenomenon, which says that everyone in the United States is separated by six or fewer people who know each other.
This small-world coordination allows each processor to correctly capture the behavior of the underlying system, said Korniss. "Individual processors learn how the whole system is doing without receiving any global information," he said. "We achieved... nearly perfect synchronization of the processors without global constraint."
The simulation showed that the overhead generated by checking in with random processors is far outweighed by the coordination gained. "[A] small frequency of checking the progress of the random neighbor for each processor is sufficient to synchronize the whole simulation, said Korniss.
The model can be tuned to require the processors to check in with their neighbors and the random processor more or less often to make the periods of waiting more or less smooth, depending on the application, said Korniss. "It is [a matter of] optimizing the tolerance for the roughness of the virtual times for a given application and available memory on each processor," he said.
The simulation showed that the model is scalable to very large systems with many processors, according to Korniss. "We can control and achieve a close-to-uniform progress of infinitely many processors, without ever explicitly feeding them with global information about the system as a whole," he said.
The researchers are looking to apply the model to examine invasion phenomena in large-scale ecological systems and the growth of nano-scale thin-film ferromagnets. The model can also be used to design decentralized control mechanisms for agent-based systems, said Korniss.
The ultimate goal is to be able to run simulations using hundereds of thousands of processors in parallel, according to Korniss.
The model could be ready to implement in real systems within two years, he said.
Korniss's research colleagues were Mark Novotny from Mississippi State University, Hasan Guclu from Rensselaer Polytechnic Institute, Zoltan Toroczkai from Los Alamos National Laboratory, and Per Arne Rikvold from Florida State University.
The research appeared in the January 31, 2003 issue of Science. The research was funded by National Science Foundation (NSF), Research Corporation, and the Department of Energy (DOE).
Timeline: > 2 years
Funding: Government, Private
TRN Categories: Applied Technology; Distributed Computing; Networking; Internet; Physics
Story Type: News
Related Elements: Technical paper, "Suppressing Roughness of Virtual Times in Parallel Discrete-Event Simulations," Science, January 31, 2003.
Advertisements:
February 12/19, 2003
Page One
Teleporting goes distance
Scheme smooths parallel processing
Butterflies offer lessons for robots
Social networks sturdier than Net
Logic scheme gains power
News:
Research News Roundup
Research Watch blog
Features:
View from the High Ground Q&A
How It Works
RSS Feeds:
News
| Blog
| Books 
Ad links:
Buy an ad link
| Advertisements:
|
 |
Ad links: Clear History
Buy an ad link
|
TRN
Newswire and Headline Feeds for Web sites
|
© Copyright Technology Research News, LLC 2000-2006. All rights reserved.
