`

СПЕЦИАЛЬНЫЕ
ПАРТНЕРЫ
ПРОЕКТА

Архив номеров

Как изменилось финансирование ИТ-направления в вашей организации?

Best CIO

Определение наиболее профессиональных ИТ-управленцев, лидеров и экспертов в своих отраслях

Человек года

Кто внес наибольший вклад в развитие украинского ИТ-рынка.

Продукт года

Награды «Продукт года» еженедельника «Компьютерное обозрение» за наиболее выдающиеся ИТ-товары

 

Леонид Бараш

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

+33
голоса

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

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

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

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

+33
голоса

Напечатать Отправить другу

Читайте также

 
 
IDC
Реклама

  •  Home  •  Рынок  •  ИТ-директор  •  CloudComputing  •  Hard  •  Soft  •  Сети  •  Безопасность  •  Наука  •  IoT