smooths parallel processing
Technology Research News
Computer 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
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
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,"
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,
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
Teleporting goes distance
lessons for robots
sturdier than Net
Logic scheme gains power
Research News Roundup
Research Watch blog
View from the High Ground Q&A
How It Works
News | Blog
Buy an ad link