ИСТИНА

В работе предложена технология решения графовых задач на гибридных архитектурах. В качестве примера подробно рассмотрены задачи построения минимального основного дерева и поиска кратчайших путей. Для каждой задачи приведено точное математическое описание, а так же результат исследования информационной структуры, на основе чего предлагается алгоритм решения задачи и его эффективная параллельная реализация. Ориентир на гибридные вычисления позволяет эффективно использовать все доступные ресурсы – как многоядерных CPU, так и GPU. Так же для вычислений используется out-of-core алгоритм, позволяющий обрабатывать графы, размер которых значительно превышает объем доступной памяти. Проведены экспериментальные исследования, показавшие высокую производительность и хорошую масштабируемость предложенного решения. Данный подход может быть расширен и на другие задачи над большими графами, актуальность которых в последнее время существенно возросла.