«Олимпиадами по информатике заниматься проще, если у вас есть хорошая математическая база»
Я пошел в школу с пяти лет, но это не моя заслуга. Маме показалось, что мне было скучно в детском саду. Моей первой школой стала французская гимназия, поэтому я изучал французский достаточно долго. Но позже мама решила, что мне нужно заниматься математикой, поэтому я пошел в кружок Математического центра Президентского ФМЛ №239. У меня были не самые низкие показатели, поэтому в итоге я перешел в эту школу и забросил изучение французского.
Когда я перешел в девятый класс, мама решила, что перспективы за программированием и надо подтягивать информатику. На тот момент она у меня была не самая сильная, поэтому я понял, что надо поехать на Летнюю компьютерную школу. Туда я попал с огромным трудом, потому что программированию меня практически не учили. Пришлось заниматься в дополнительное время с нашей учительницей по информатике, чтобы я смог сдать вступительные. В итоге я написал вступительную работу в ЛКШ на уровне D. Это не очень сильная группа, но в тот год впервые в школе организовали группу между C и D, группу С-штрих, где можно было быстро нагнать какую-то информацию.
После этого я пошел на кружок по информатике в Университет ИТМО. А уже через год проскочил две группы и попал на ЛКШ в группу A-штрих. Думаю, что во многом мне помогла хорошая математическая база. В 10 классе я вышел на Всероссийскую олимпиаду по математике. Это помогло мне и в информатике: решать задачи по этому предмету все-таки проще, если есть математический бэкграунд.
Тогда я не только решал олимпиадные задачи по информатике, но и с нуля сделал свою игру — летом, просто от нечего делать. Это была пошаговая стратегия. Знаете Age of Empires? В этой игре можно строить здания, развиваться, делать юниты — как в любой real time strategy. Но представьте, если сделать то же самое можно не в реальном времени, а пошагово, чтобы определенное действие можно было совершить за один ход? Так честнее и дает свободу пользователю: он может оценить ситуацию, понять, что происходит. По сути, как в шахматах, где можно обдумать ход наперед. Интересно, что таких игр до сих пор нет. По крайней мере, я не встречал.
Оставить спортивное программирование и найти себя в науке
Я окончил школу в 15 лет, тогда я не особо понимал, чем буду заниматься дальше. У меня был выбор между матмехом СПбГУ и Университетом ИТМО, но в случае с матмехом было не понятно, чем я буду заниматься дальше, а после окончания ИТМО перспективы были более очевидны. Кроме того, еще когда я ходил в кружок, познакомился с Павлом Мавриным (тьютор факультета информационных технологий и программирования, двукратный чемпион ACM ICPC — прим.ред.), здесь сложилась более целостная, дружеская атмосфера.
Уже поступив в университет, научной деятельностью я не занимался очень долго. В то время, вплоть до третьего курса, я занимался олимпиадным программированием, начинал с Ниязом Нигматуллиным (тьютор факультета информационных технологий и программирования, двукратный чемпион ACM ICPC — прим.ред.). Но в отличие от тех, кто много времени отдает только тренировкам, у меня был немного другой подход: я занимался программированием, ходил на тренировки а также посещал все пары и делал домашние задания. В какой-то момент я перегорел, и на финал так и не поехал. В итоге меня перевели сразу в члены жюри.
Первым шагом в науку можно считать бакалаврскую, целью которой было определитель матрицы смежности графа-прямоугольника. По сути, это чистая математика. В магистерской я решил продолжить исследования в этой же области и развить тему. Мы сделали статью по бакалаврской, потом получилось сделать еще две статьи по магистерской и довести исследование до логической точки.
Тогда же я начал интересоваться параллельным программированием. Еще на третьем курсе у нас были лекции от Романа Елизарова (разработчик языка Kotlin в компании JetBrains, эксперт в области многопоточного программирования, тьютор факультета информационных технологий и программирования Университета ИТМО — прим.ред.), и мне понравилась сама идея распределенных вычислений. А после пятого курса к нам приехал читать курс Умут Акар (Umut Acar), он рассказал о задачах в области параллельных структур данных. Тогда он искал аспиранта, и я решил, почему бы не попробовать, раз мне интересна эта тема. Так я вписался в аспирантуру.
Как защитить PhD во Франции, даже сменив научного руководителя
На тот момент Умут базировался во Франции, в INRIA, это национальный исследовательский институт, работающий в области компьютерных наук, теории управления и прикладной математики. Он позвал меня к себе на работу, а для моего факультета было бы полезно организовать совместную аспирантуру. Этот процесс был достаточно непростым, потому что INRIA — не вуз, он не выдает дипломы. Поэтому необходимо было зарегистрироваться в другом университете. В итоге в результате длительного процесса удалось организовать совместную аспирантуру с Университетом Париж 7 Дениса Дидро.
Обучение в аспирантуре во Франции похоже на то, как было у нас раньше. Это сейчас у нас в аспирантуре действительно учатся, ходят на занятия, сдают экзамены. Там тебя, по сути, никто не трогает: ты можешь почти все время посвятить своей научной работе. Поэтому три года я занимался своим исследованием, во Франции я находился примерно восемь месяцев в год, а четыре проводил в Петербурге.
Но в моей истории было не все так гладко: почти сразу мне пришлось сменить своего научного руководителя, так как он уехал в Америку, а работать таким образом было достаточно сложно. Поэтому по большей части я работал один. Но потом я познакомился с профессором Петром Кузнецовым (профессор Télécom ParisTech, выпускник кафедры компьютерных технологий Университета ИТМО — прим.ред.), с которым получилось продолжить работу. Поэтому в итоге на защите у меня было три научных руководителя — Анатолий Абрамович Шалыто из Университета ИТМО, Петр Кузнецов и профессор Carole Delporte из Университета Париж 7, с которым была организована совместная аспирантура.
Структуры без ожидания: почему над этой задачей исследователи бьются 20 лет
Интересно, что в процессе работы Петр Кузнецов поставил мне задачу, которая является открытой уже около 20 лет. Суть ее в том, можно ли реализовать очередь без ожидания, иными словами систему, в которой каждый процесс завершает операцию за конечное число своих шагов.
Представьте процессы, все они выполняют свои операции. Но что может произойти? Процесс пытается добавить элемент, но кто-то его постоянно опережает, и он не может это сделать. В итоге этот процесс фактически стоит и ждет. Это система с ожиданием. Без ожидания — это когда ему кто-то помогает и добавляет перед собой. Известно, как это сделать, используя такую универсальную операцию, как compare-and-swap (CAS), реализованную в большинстве процессоров. Но вопрос в другом: а что если взять не этот универсальный примитив, а несколько более упрощенный примитив, который, скорее всего, проще реализовать на физическом уровне. Над этой задачей исследователи бьются уже 20 лет и пока результатов нет.
Зачем в целом все это нужно? По-хорошему все структуры данных должны быть без ожидания. Иначе процесс попросту простаивает, он не может продвинуться вперед, и мы не можем давать никаких гарантий на время работы — процесс может выйти через десять минут, а может быть, через час. К примеру, в ядерных реакторах так нельзя: здесь нужно все по расписанию, поэтому структуры без ожидания очень важны.
Оптимизация структур данных и уменьшение синхронизации: как параллельные вычисления могут помочь ускорить многие процессы
В самой диссертации у меня получилось несколько результатов. В целом моя работа состоит из пяти различных частей. Первая часть, которую я делал со своим первым научным руководителем, рассматривает именно параллельные программы. Как именно? Есть такая операция Fork/Join. Она подразумевает, что у нас есть две задачи и мы можем выполнить их в параллель. Безусловно, мы можем выполнить их последовательно, но тогда никакого выигрыша от запуска различных процессов не будет. Поэтому логичнее сказать: «Fork/Join, запусти мне эти задачи параллельно».
Проблема в том, что каждый Fork/Join сколько-то стоит, то есть его вызов занимает сколько-то времени. Поэтому важная задача — определить, когда их нужно вызывать, а когда нет. Ведь если у вас две маленькие задачи, которые вы хотите запустить в параллель, то стоимость Fork/Join может просто перебить стоимость самих задач и вам будет выгоднее сделать все последовательно.
Я занимался разработкой метода, который позволит автоматически определить, как сделать оптимальнее в каждом конкретном случае. У меня получилось разработать схему такого автоматического определения.
Где это нужно? Параллельные программы на Fork/Join пишут все, они встречаются повсюду. Возьмите, например, любую игру — тот же CS:GO, где нужно как-то обработать пули при их столкновении с фигурой. Пуль много и хочется их обрабатывать быстрее, в ином случае, при последовательной обработке, мы теряем скорость. Параллельное программирование позволяет сделать все быстрее. И, по сути, это можно написать простым способом с помощью Fork/Join.
Другие части моей работы были посвящены задаче оптимизации разных структур данных. Например, я занимался конкурентно оптимальным деревом поиска. Дерево поиска используется везде, например, в базах данных. Основной целью было ускорить эту структуру данных.
Почему это необходимо? Если мы возьмем обычную последовательную структуру данных и в нее будут параллельно добавляться элементы, то может произойти что-то не то. Например, они будут добавлять одновременно информацию в одно и то же место, и одна операция попросту затрет другую. Именно поэтому нужна синхронизация: если один процесс уже добавляет данные, второй «видит» это, стоит и ждет. Я же, в свою очередь, попытался подумать, как сделать так, чтобы этой синхронизации стало меньше. Это фундаментальная задача, которая применима в разных областях, к примеру, в тех же поисковиках.
Нужно ли для общения в научной среде знать не только английский
На защите мне немного помог французский язык, который я когда-то учил в специализированной гимназии. Конечно, перед тем, как ехать во Францию, я еще походил на курсы, чтобы подтянуть разговорную часть. Потому что единственное, что я помнил со школы, — как читать тексты на французском, и читаю я неплохо.
Во время защиты одна из членов комиссии сказала, что, если она будет говорить мне на английском, скорее всего, я ее не пойму и задала вопрос по-французски. В итоге я ей также ответил по-французски. И в результатах защиты PhD мне даже написали: «Он ответил хорошо на английском и французском языках».
Но в целом я думаю, что сегодня для общения в научной среде и на международных конференциях и школах достаточно хорошо знать один английский. Даже во Франции сегодня молодые люди знают английский язык на хорошем уровне, а те, кто работает в научной среде, тем более.
Перспективы после PhD
Сейчас пока надо разобраться с документами. Но в перспективе я планирую поехать постдоком в Австрию, уже есть соответствующая договоренность с Дэном Алистархом (Dan Alistarh) из IST Austria. Он работает с очень интересными вещами, структурами данных, но конкретно к нему я еду, чтобы заниматься машинным обучением. Сегодня, наверно, все этим занимаются, но я хочу работать именно в области параллельного машинного обучения.
Объяснить это несложно: есть обычное машинное обучение, где мы последовательно обучаем нейросеть. А теперь представим, что мы будем обучать ее параллельно. Как нам ускорить последовательное время работы, если у нас есть много ядер, например, 60? Необходимо придумать алгоритмы, которые будут позволять обрабатывать данные как можно скорее. В идеале — во столько раз, сколько у нас есть ядер.
Конечно, это недостижимая цифра. Я считаю, что если на 60 ядрах можно будет достичь ускорения хотя бы в 20 раз, это будет прогресс. Я буду заниматься базовыми алгоритмами машинного обучения, например, градиентным спуском, который хочется распараллелить. И здесь я также буду работать над уменьшением синхронизации в известных алгоритмах машинного обучения.
Почему научные задачи интереснее работы в Facebook
Еще со школы больше всего в программировании меня привлекала возможность запрограммировать какие-то математические идеи. Как в науке: в голову приходит идея, например, как можно что-то оптимизировать, какой алгоритм можно придумать, а после она воплощается в жизнь. Когда ты работаешь программистом в компании, ты просто поддерживаешь продукт, делаешь довольно простые вещи и не пишешь какие-то сложные алгоритмы.
Я работал некоторое время в индустрии: год провел в Mail.ru и стажировался три месяца в Facebook. Но это было далеко не самое полезное времяпровождение. Да, в индустрии прилично платят, но, на мой взгляд, это единственное преимущество. Задачи, которые ставятся в компаниях, не очень интересны, и, более того, ты сам не можешь выбрать себе задачу. Иногда везет с интересными проектами, но по большей части нет. В Facebook, например, я полтора месяца занимался только тем, что переписывал файл из одного формата в другой просто потому, что мне дали такое задание. В науке ты можешь придумать что-то новое, что может продвинуть всю сферу вперед. Писать не свое очень скучно, мне интереснее реализовывать свои идеи.
