Аннотация:Данная магистерская диссертация Таратуты Е.Е. продолжает ряд работ, связанных с анализом и тонкой информационной структуры программ и их реализацией для современных высокопроизводительных платформ, ведущихся в Научно-исследовательском вычислительном центре МГУ имени М.В.Ломоносова. Тема данной работы является крайне актуальной, поскольку графовые алгоритмы активно используются в самых разных областях науки, а платформа Intel Xeon Phi является достаточно новой и перспективной для создания будущих высокопроизводительных систем.
Таратута Е.Е. провела исследование информационной структуры базовых графовых алгоритмов – алгоритма Борувки поиска минимального остовного дерева в графе и алгоритмов Дейкстры и Беллмана-Форда поиска кратчайших путей от заданной вершины. Проведено также независимое исследование аппаратной платформы Intel Xeon Phi, основное внимание в котором уделено характеристикам работы с памятью. Сопоставление характеристик алгоритмов и свойств платформы легло в основу полученных параллельных реализаций. Автором показана хорошая масштабируемость реализаций.