Параллельный алгоритм поиска путей с КС-ограничениями на основе GLL

Алгоритм поиска путей с контекстно-свободными ограничениями показывает неплохую производительность даже при однопоточной реализации. В теории, данный алгоритм может быть естественным образом распараллелен, однако наивный подход ведёт к высоким накладным расходам и на практике не даёт выигрыша. Предлагается разработать и реализовать эффективную с точки зрения производительности параллельную версию алгоритма, провести её экспериментальное исследование и сравнение с аналогами.

Требования к студенту
  • Отличные знания теории формальных языков и алгоритмов синтаксического анализа: контекстно-свободные грамматики, рекурсивные автоматы, алгоритм GLL и аналоги.
  • Отличные знания и навыки в разработке и реализации параллельных алгоритмов для JVM: примитивы синхронизации, неблокирующие решения, библиотеки структур данных с конкурентным доступом, многопоточное программирование.
  • Хорошие знания в теории графов и алгоритмах анализа графов: ориентированные графы, алгоритмы поиска путей и обходов, параллельные алгоритмы на графах.
Уровень

3 курс, Бакалаврская ВКР, Магистерская ВКР

Руководитель

Григорьев Семен Вячеславович

Консультант

Grigorev Semyon

Источник

Кафедра системного программирования СПбГУ