Повышение эффективности сложных вычислений

14 апрель, 2014 - 14:49Леонід Бараш

Планируете поездку из Берлина в Гамбург, симуляцию воздушных потоков вокруг нового пассажирского самолета или дружеские связи на Facebook – многие компьютерные приложения моделируют взаимосвязи между объектами посредством графов в смысле дискретной математики. Важным методом для управления сложными вычислениями на стабильно растущих сетях является разбиение графа на подграфы (graph partitioning). В Технологическом институте Карлсруэ (KIT) проф. Питер Сандерс (Peter Sanders) и д-р Кристиан Шульц (Christian Schulz) уже разработали для этой цели инструмент, названный Karlsruhe High Quality Partitioner (KaHIP). Решения, полученные с его помощью, в настоящее являются лучшими во всем мире.

С помощью KaHIP смоделированные объекты (вершины графа) разделяются на блоки примерно одинакового размера, в то время как число ребер между блоками минимизируется. Таким образом, планирование маршрута, например, может быть ускорено: транспортная сеть, хранящаяся в планировщике маршрута, разбивается. При планировании определенного маршрута, скажем, из Берлина в Гамбург, большими частями транспортной сети можно пренебречь, так как они не являются важными. Таким образом, инструмент разбиения, такой как KaHIP, может ускорить вычисление маршрута в несколько раз.

Сложные вычисления с очень подробными графами, такие как вычисления характеристик обтекания самолета, часто требуют более одного компьютера. В этом случае, KaHIP может распределить вычислений и обеспечить эффективность параллельных вычислений на нескольких компьютерах. Определяющим фактором является количество ребер, которые должны быть разрезаны при разбиении. «Скорость вычислений увеличивается с уменьшением числа ребер, которые должны быть разрезаны. Наша система решает проблему разбиения графа за счет разрезания примерно в три раза меньше ребер, чем сопоставимые инструменты на рынке», - объяснил д-р Шульц.

Уже на этапе разработки программой заинтересовалась наука и промышленность. KaHIP теперь доступна в качестве программы с открытым исходным кодом. Она уже доказала свою конкурентоспособность – набрала большинство очков на X DIMACS Implementation Challenge, а также в Benchmark Walshaw, в котором разделители графов со всего мира соревнуются друг с другом.