Механизм генерации и JIT-компиляции IR LLVM кода для быстрого поиска в больших текстовых файлах с возможностью использования регулярных выражений

Руководитель от корпоративного партнера: Старичков Н.Ю., 1C
Руководитель от Университета ИТМО: Авксентьева Елена Юрьевна, Университет ИТМО

Набор в этот проект закончен.

Краткая аннотация

Разработка механизма генерации и JIT-компиляции IR LLVM кода для быстрого поиска в больших текстовых файлах с возможностью использования регулярных выражений.

Задачи поиска подстроки в тексте всегда были известны своей вычислительной трудоемкостью. Это либо достаточно большое время работы (если текст большой), либо большое количество потребляемой памяти (если проводится тот или иной препроцессинг текста). Если говорить о нечетком поиске, в частности, с помощью регулярных выражений, то дела обстоят еще хуже - производительность таких механизмов оставляет желать лучшего. При этом есть предположение, что поиск по регулярному выражению можно достаточно сильно оптимизировать, если использовать не какой-то общий код (с большим количеством условных переходов), а специально написанный и скомпилированный для исполнения именно этого поискового запроса. При этом при большом размере текста и/или сложном регулярном выражении выигрыш по производительности может компенсировать потери на кодогенерацию и компиляцию этого кода - что по итогу делает этот подход более выгодным. В рамках данного проекта предлагается разработать механизм генерации кода на языке IR LLVM, его JIT-компиляцию и исполнение.

План действий

  1. Изучение динамической компиляции запросов
  2. Изучение и применение инфраструктуры компиляторов LLVM для построения собственных решений на её основе.
  3. Исследование методов и алгоритмов обработки больших текстовых файлов (написание расширений для PostgreSQL с использованием GiST, генетический алгоритм) 4.Проектирование, разработка и тестирование механизма генерации и JIT-компиляции IR LLVM кода для быстрого поиска в больших текстовых файлах с возможностью использования регулярных выражений

Решаемые технические проблемы

Увеличение скорости поиска в больших текстовых файлах в системах управления базами данных

Стек технологий

1) User and Organizations

  • Инструменты гибкой разработки Agile, Scrum, Kanban
  • Тайм-менеджмент и планирование временем

2) System Modeling

  • Системное моделирование с использованием языков UML/SysML
  • Анализ требований

3) System Architecture and Infrastructure

  • Методы проектирование программных систем
  • Методы проектирования интеллектуальных систем
  • Организация параллельных и распределенных вычислений
  • Компьютерные сети
  • Виртуальные системы и сервисы

4). Software Development

  • Программирование на языках C++, Java, Python
  • Использование стандартных библиотек С++, Boost, библиотек Python для обработки, анализа и визуализации данных
  • Web-разработка с использованием HTML, CSS, Java Script, PHP.
  • СУБД PostgreSQL

5) Software Fundamentals

  • Алгоритмы и структуры данных
  • Операционные системы реального времени

6) Hardware

  • Архитектура вычислительных систем

Предварительный перечень курсов

  1. Обработка и анализ данных https://openedu.ru/course/ITMOUniversity/BIGDATA2035/
  2. Прикладной искусственный интеллект https://openedu.ru/course/ITMOUniversity/APPARTINT2035/
  3. Методы машинного обучения https://openedu.ru/course/ITMOUniversity/INTROML/
  4. Интеллектуальный анализ данных https://openedu.ru/course/ITMOUniversity/MLDATAN/
  5. Хранилища и базы данных https://openedu.ru/course/spbu/DTBS/
  6. Технологии веб-сервисов https://www.specialist.ru/course/1cwebs 7.Параллельные вычисления https://mipt.ru/online/algoritmov-i-tekhnologiy/raspr-calc.php
  7. Распределенные вычисления https://mipt.ru/online/algoritmov-i-tekhnologiy/raspr-calc.php
  8. Администрирование PostgreSQL 9.4. Базовый Курс https://www.youtube.com/watch?v=h_GdEaF1Ymc&list=PLaFqU3KCWw6KzGwUubZm-9-vKsi6vh5qC&index=2
  9. Специализация Learn SQL Basics for Data Science https://ru.coursera.org/specializations/learn-sql-basics-data-science
  10. Intermediate PostgreSQL https://ru.coursera.org/learn/intermediate-postgresql
  11. Библиотека программиста https://proglib.io/p/postgresql/
  12. Профессиональный информационно-аналитический ресурс, посвященный машинному обучению, распознаванию образов и интеллектуальному анализу данных http://www.machinelearning.ru/

Кем станет студент по завершению магистратуры

Программист-стажер, программист, разработчик систем машинного обучения и ИИ

Пререквизиты

Базовые программы курсов:

  • Высшая математика
  • Основы программирования
  • Алгоритмы и структуры данных
  • Программная инженерия
  • Архитектура программных систем
  • Базы данных