С помощью KaHIP моделируемые объекты (узлы графа) разделяются на блоки примерно одинакового размера, а количество ребер между блоками минимизируется. Таким образом, например, планировщики маршрутов могут быть ускорены: транспортная сеть, хранящаяся в планировщике маршрутов, разделяется. При планировании конкретного маршрута, например от Берлина до Гамбурга значительными участками транспортной сети можно пренебречь, поскольку они не имеют отношения к делу.
Таким образом, инструмент разделения, такой как KaHIP, может ускорить вычисление маршрута за счет нескольких факторов.Для сложных вычислений с очень подробными графиками, таких как вычисление характеристик потока самолета, часто требуется более одного компьютера. В таком случае KaHIP может распределять вычисления разумным образом и обеспечивает эффективные одновременные вычисления на нескольких компьютерах. Определяющим фактором является количество ребер, которые необходимо разрезать в графе. «Скорость вычислений увеличивается с уменьшением числа ребер, которые необходимо разрезать.
Наша система решает проблему разделения графа, сокращая примерно в три раза меньше ребер, чем аналогичные инструменты на рынке», — доктор Кристиан Шульц, ученый из Института теоретической науки KIT. Информатика, — поясняет.В рамках своей докторской диссертации в KIT Кристиан Шульц разработал KaHIP вместе с профессором Питером Сандерсом.
Уже на этапе разработки инструмент вызвал большой интерес в науке и промышленности. KaHIP теперь доступен как программа с открытым исходным кодом. В международном сравнении KaHIP уже доказал свою конкурентоспособность.
Он набрал большинство баллов в 10-м испытании внедрения DIMACS, а также в тесте Walshaw Benchmark, в котором разделители графов со всего мира соревнуются друг с другом.«Основываясь на нашем многолетнем опыте в области обработки графиков, мы теперь можем предложить KaHIP, инструмент, который обеспечивает лучшее качество решений во всем мире для ряда приложений», — говорит профессор Питер Сандерс из Института теоретической информатики KIT. .