Темы для курсовых работ 2017 (РС)

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск

Содержание

Курсовые работы

Ниже приведены описания возможных проектов курсовой работы (напоминаю, что на третьем курсе в качестве курсовой работы засчитывается и проектная работа).

Если вас заинтересовала какая-либо из предложенных тем и вы хотите над ней поработать в рамках вашей курсовой работы, то ваша последовательность действий такая:

  1. напишите письмо руководителю темы, в копию письма добавьте Пузыревского Ивана (ipuzyrevskiy@hse.ru); укажите, над какой задачей вы хотите поработать; укажите релевантную информацию про вас (публичный github, опыт по теме, что вы сочтете нужным);
  2. далее, вам нужно с руководителем обсудить задачу и возможность работы над ней; обычно руководитель вам чуть более подробно вам расскажет, что от вас будет требоваться, вы обсудите, насколько реально вам выполнить предлагаемую работу;
  3. в конечном итоге, вы вместе с руководителем приходите или к положительному решению (вы работаете над оговоренной задачей), или к отрицательному (вам необходимо выбрать другую тему курсовой работы).

Рекомендуемые темы проектной работы

Безопасность

По поводу тем курсовых работ на тему информационной безопасности можно обращаться напрямую к [Гамаюнову]. В рамках командной проектной работы предлагается два проекта: http://wiki.cs.hse.ru/Децентрализованный_крипточат_(командный_проект) http://wiki.cs.hse.ru/Веб-краулер_для_поиска_уязвимостей_авторизации_(командный_проект)

Криптовалюты, блокчейн

По поводу курсовых работ на тему криптовалют, блокчейна можно обращаться напрямую к Ярославу Яворскому для непосредственного обсуждения. Ниже приведены примеры тем, предлагаемых в рамках проектной работы на 2-м курсе. http://wiki.cs.hse.ru/Анализ_данных,_хранимых_в_реестрах_криптовалют_(проект) http://wiki.cs.hse.ru/Аналитический_сервис_по_новостям_в_сфере_блокчейн_технологий_(проект) http://wiki.cs.hse.ru/Тестирование_и_верификация_смарт-контрактов_(проект) http://wiki.cs.hse.ru/Разработка_веб_интерфейсов_для_криптовалют_и_смарт-контрактов_(проект)

Темы возможных курсовых работ

!! Список тем еще дополняется / расширяется.

ClickHouse

Руководитель: Миловидов Алексей

ClickHouse -- открытая колоночная СУБД, позволяющая выполнять аналитические запросы в интерактивном режиме по данным, обновляемым в реальном времени. ClickHouse разработан в Яндексе для задач Яндекс.Метрики -- второй по величине системы веб-аналитики в мире.

В качестве тем для курсовых работ предлагается следующий набор проектов:

  • Использование первичного ключа при ORDER BY monotonic(PK), GROUP BY injective(subset(PK)).
  • Поддержка форматов ввода-вывода Parquet и Protobuf.
  • Модификаторы WITH ROLLUP и WITH CUBE для GROUP BY.
  • Поддержка вычисляемых DEFAULT выражений для полуструктурированных форматов JSONEachRow, TSKV.
  • Short-curcuit вычисление некоторых функций.
  • Оптимизация простых выражений с помощью генерации LLVM кода.
  • Кэширование промежуточных данных конвейера выполнения запроса.
  • Оптимизация алгоритма слияний.
  • Генератор тестовых данных.

Postgres Pro: Автоматизация смены мастера в кластере PostgreSQL, использующем логическую репликацию

Руководитель: Абубекеров Марат

Есть кластер PostgreSQL с мастером и несколькими репликами. Используется логическая репликация. Требуется разработать приложение, к оторое в случае выхода мастера из строя автоматически выбирает нового мастера и переключает на него остальные реплики. Допускается з ависимость от сторонних приложений, в частности etcd или Consul.

Postgres Pro: Приоритезация запросов в РСУБД PostgreSQL

Руководитель: Абубекеров Марат

Исследовать различные механизмы приоритезации з апросов в реляционных базах данных. Реализовать механизм приоритезации з апросов для РСУБД PostgreSQL. Запросы с большим приоритетом выполняются раньше з апросов с низким приоритетом. Кроме т ого, время, выделяемое на выполнение з апросов, пропорционально их приоритетам. Например, при одновременном выполнении OLTP и OLAP з апросов становится возможно присвоить первым более высокий приоритет, чем вторым. В результате OLTP з апросы будут выполняться к ак можно быстрее, а OLAP з апросы будут выполняться в фоне с меньшим приоритетом.

Postgres Pro: Разработка механизма ограничения используемых ресурсов в PostgreSQL

Руководитель: Абубекеров Марат

Исследование механизмов ограничения использования системных ресурсов - времени CPU, оперативной памяти, места на диске, сетевого т рафика, и т ак далее. Реализация механизма ограничения используемых ресурсов по пользователям и сессиям для РСУБД PostgreSQL. Допускается использование сторонних механизмов, в частности cgroups.

Postgres Pro: Реализация в модуле pg_trgm поиска по N-граммам с N > 3

Руководитель: Абубекеров Марат

Модуль pg_trgm для PostgreSQL позволяет делать индексы по т риграммам для нечеткого поиска. К примеру, слово ' молоко' будет разложено на массив триграмм [ мол, оло, лок, око] и если поисковый слово содержит опечатку, т о большинство т риграмм останется неизменным. Это свойство используется для поиска: можно разложить искомые слова/фразы на т риграммы, построить по ним обратный ( инвертированный) индекс и при поиске искать документы с максимальным числом одинаковых т риграмм. Такой подход хорошо и быстро работает на словах и небольших фразах. Однако данный подход не эффективен, если поиск ведется по предложениям. Так к ак предложение большое, т о разных т риграмм от к аждого документа получается много и поисковый з апрос будет пересекаться с очень большим количеством строк в т аблице. Чтобы избежать этого, предлагается реализовать поддержку не т риграмм, а на N-грамм с N= 4, 5 и т ак далее. Тогда разных N-грам ставится экспоненциально больше с ростом N и соответственно вероятность встретить данную N-грамму - меньше, следовательно при поиске требуется проверять на соответствие меньше строк и поиск становится эффективнее.

Улучшение симулятора планировщика ресурсов кластера

Руководитель: Игнатий Игоревич Колесниченко

В системе YT одна из наиболее значимых компонент -- это планировщик вычислений. Именно он отвечает за распределение ресурсов кластера между пользователями с учетом их требований и желаемых гарантий (зачастую, противоречивых). От эффективности работы планировщика зависит общая эффективность работы кластера и удовлетворенность пользователей. Для проведения оффлайн-экспериментов над алгоритмами планировщика был разработан симулятор, использующий "трейс" событий, снятый с реального кластера (запуск вычислений, освобождение вычислительных ресурсов, потеря вычислений в результате сбоя, и др.). Ниже представлены возможные направления для последующих исследований и улучшений данной функциональности.

В текущей версии симулятора известен ряд недоработок, существенно влияющих на качество симуляции. Например, текущий симулятор не учитывает зависимость вычислений между собой (когда выход одного вычисления используется как вход для другого). За счет использования метаинформации (имя пользователя, время начала/окончания вычислений, именование входных/выходных данных) можно было бы восстановить данные зависимости, что позволит существенно улучшить качество симуляции и, соответственно, качество вычисляемых метрик для цепочек вычислений.

Формальная спецификация HDFS

Руководитель: Иван Витальевич Пузыревский

HDFS (Hadoop Distributed File System) -- распределенная отказоустойчивая файловая система. В данной работе предлагается разработать и проверить формальную спецификацию системы с помощью TLA+.


Имитационное моделирование вычислительных ресурсов и распределенных вычислительных инфраструктур

Руководитель: Олег Викторович Сухорослов

Имитационное моделирование активно используется в исследованиях распределенных систем, заменяя натурные эксперименты и позволяя воспроизводимым образом сравнивать между собой различные методы (например, алгоритмы планирования задач). В данной работе объектом моделирования являются распределенные вычислительные инфраструктуры, состоящие из нескольких автономных ресурсов различного типа (кластеров, гридов, облаков, персональных компьютеров). Для реалистичного моделирования таких инфраструктур требуется хорошо моделировать отдельные ресурсы, их планировщики, нагрузку и доступность, а также передачу данных по сети. Для данных целей предлагается использовать SimGrid, фреймворк для создания симуляторов распределенных систем. Требуется улучшить имеющиеся или реализовать новые модели ресурсов (например, кластер с планировщиком и внутренним потоком заданий), а также интегрировать их в единую модель. Возможны отдельные подтемы и работа в команде.

Симуляция и сравнительный анализ алгоритмов планирования задач в распределенных вычислительных системах

Руководитель: Олег Викторович Сухорослов

Планирование выполнения задач в распределенных системах в постановках, представляющих практический интерес, является NP-полной задачей. За последнее десятилетие было предложено множество алгоритмов планирования, основанных на различного рода (мета)эвристиках и ориентированных на различные классы приложений (bag of tasks, parallel job, workflow) и систем. При этом недостаточно хорошо изучен вопрос об области применимости и сравнительной эффективности данных алгоритмов в различных ситуациях. В данной работе предлагается реализовать на базе существующего симулятора наиболее известные алгоритмы и сравнить их друг с другом путем проведения имитационных экспериментов для различных типов приложений и систем. Возможны отдельные подтемы и работа в команде.

Исследование и экспериментальная оценка технологий распределенных вычислений на основе pilot jobs

Руководитель: Олег Викторович Сухорослов

При реализации крупномасштабных вычислений на базе распределенных ресурсов с собственными планировщиками часто используется стратегия pilot jobs. Данная стратегия, заключающаяся в запуске на ресурсах заданий-агентов с последующим динамическим распределением по ним задач, позволяет уменьшить влияние задержек в очередях ресурсов и накладные расходы на запуск задач. В настоящее время существует несколько технологий (pilot job frameworks), реализующих данный подход, например HTCondor, DIANE, BigJob, Swift, DIRAC. В данной работе предлагается изучить и сравнить между собой несколько данных технологий путем их развертывания и проведения экспериментов на тестовой инфраструктуре. Особое внимание планируется уделить сравнению производительности различных решений, оценке их масштабируемости, выявлению узких мест и поиску способов их устранения.

Использование простаивающих вычислительных ресурсов для распределенных вычислений на базе платформы Everest

Руководитель: Олег Викторович Сухорослов

Платформа Everest, разрабатываемая в ИППИ РАН, позволяет публиковать в виде веб-сервисов вычислительные приложения и запускать через веб-интерфейс расчеты на произвольных комбинациях внешних ресурсов, подключенных пользователями к платформе. Интеграция ресурсов с платформой реализована на основе специально разработанного агента, который выполняется на стороне ресурса. В настоящее время агент поддерживает запуск задач на одиночной машине (в монопольном режиме) и кластере (с приоритетом обычного пользователя), не учитывая внешнюю нагрузку на ресурс. В данной работе предлагается реализовать поддержку использования ресурса только в моменты его простоя, что требует мониторинга текущей загрузки ресурса и динамического управления задачами. При этом планируется использовать опыт и наработки систем, ориентированных на использование простаивающих персональных компьютеров (BOINC, Condor).

Реализация универсального вычислительного агента для систем распределенных вычислений

Руководитель: Олег Викторович Сухорослов

Платформа Everest, разрабатываемая в ИППИ РАН, позволяет публиковать в виде веб-сервисов вычислительные приложения и запускать через веб-интерфейс расчеты на произвольных комбинациях внешних ресурсов, подключенных пользователями к платформе. Интеграция ресурсов с платформой реализована на основе специально разработанного агента, который выполняется на стороне ресурса. Агент написан на языке Python с использованием фреймворка Tornado и реализует асинхронную обработку, запуск и мониторинг поступающих задач, загрузку данных и обмен сообщениями с платформой. В данной работе предлагается реализовать принципиально новую версию агента на языке Go. Помимо имеющейся функциональности планируется реализовать прямое взаимодействие по сети между агентами, автоматическое обновление кода агента, а также обеспечить универсальность агента для его использования с другими системами распределенных вычислений.

Исследование и реализация методов прямой передачи данных по сети между узлами за NAT и межсетевыми экранами

Руководитель: Олег Викторович Сухорослов

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

Исследование и экспериментальная оценка методов обеспечения отказоустойчивости MPI-приложений

Руководитель: Олег Викторович Сухорослов

Одной из основных проблем, связанных с использованием в будущем мощных вычислительных систем уровня exascale, является обеспечение устойчивости параллельных программ к отказам. Поскольку данные системы могут включать миллионы процессоров, выполняющих до миллиарда потоков, то ожидается что в них с высокой частотой (до нескольких раз в час) будут возникать всевозможные сбои на аппаратном и программном уровнях, приводящие к падению процессов или потере данных. Традиционные методы, такие как checkpointing, становятся неэффективными в условиях, когда сохранение состояния требует времени сопоставимого с частотой отказов. В настоящее время активно ведется разработка новых методов, нацеленных на решение данной проблемы, в частности применительно к выполнению MPI-программ. В данной работе предлагается изучить данные методы, провести их экспериментальную оценку и, возможно, улучшить.