Communications of the ACM
Enhancing the Efficiency of Complex Computations
In this graph of the air flow around an airplane wing, the four colors reflect the partitioning of the graph, and the distribution of computation among four computers.
Credit: Christian Shulz/KIT
The science and industry sectors are showing considerable interest in a graph partitioner developed by computer scientists at the Karlsruhe Institute of Technology (KIT).
The Karlsruhe High Quality Partitioner (KaHIP) can enhance complex computations with very detailed graphs that require multiple computers. The researchers say the tool can distribute computations in a reasonable manner, ensuring efficient, simultaneous computations on more than one computer. Modeled objects are divided into blocks of about the same size, while the number of edges between the blocks are minimized. In this manner, route planners, for example, can be accelerated. When planning a specific route, large parts of the transport network can be overlooked, as they are irrelevant. Thus, a partitioning tool such as KaHIP can accelerate the computation of a route by several factors. Fewer edges need to be cut, which allows for faster computation speed.
"Our system solves the graph-partitioning problem by cutting about three times less edges than comparable tools on the market," says KIT's Christian Schulz. He notes the program, available as open source, scored the most points in the 10th DIMACS Implementation Challenge as well as the Walshaw Benchmark.
From Karlsruhe Institute of Technology
View Full Article
Abstracts Copyright © 2013 Information Inc., Bethesda, Maryland, USA
No entries found