Новости

20 сентября, 2015 16:41

Многоликая AlgoWiki. Математики МГУ создают всемирную энциклопедию алгоритмов.

Источник: Газета "Поиск"
Источник: пресс-служба РНФ

- В названии проекта есть ко многому обязывающее слово - “энциклопедия”. Оно предполагает фундаментальный подход к реализации идеи. С этой точки зрения результатом вашего проекта станет именно такая энциклопедия?

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

- Откуда такое название? 

Воеводин: - Algo - поскольку в основе идеи глубокий априорный анализ свойств алгоритмов и их реализация. Wiki - потому что в своей работе мы решили использовать стандартные викитехнологии, те самые, которые привели к созданию известной “Википедии”, когда разные люди подключаются к одному и тому же проекту и, используя современные интернет-технологии, привносят свое знание в общий проект. Мы сознательно пошли на такую открытость, ведь алгоритмов - огромное множество и силами одного коллектива сделать фундаментальное описание, пополнять и развивать энциклопедию просто невозможно. 

- То есть, как и в “Википедии”, к проекту может присоединиться кто угодно и вписать в AlgoWiki то, что считает нужным?

Воеводин: - Не совсем так. Мы действительно ориентированы на работу с большим числом авторов, в перспективе со всем мировым вычислительным сообществом. Но вместе с этим все добавляемые материалы будут проходить научную экспертизу, что позволит обеспечить качество материалов AlgoWiki.

- Как родилась идея столь необычной энциклопедии? Расскажите, пожалуйста, о предыстории проекта.

Воеводин: - Мы привыкли, решая те или иные задачи с помощью компьютерной техники, к последовательной форме организации вычислений, когда есть один вычислитель, один процессор, вычислительный узел и последовательно, операция за операцией, выполняется алгоритм. Со временем задачи усложнялись, техника модифицировалась - за последние 40 лет сменилось уже шесть поколений архитектур. Очередная новинка вызывает необходимость кардинальных изменений в программном обеспечении - его нужно опять и опять переписывать. Но основные новации в компьютерном мире связаны с возрастающей степенью параллельности, которая пронизывает всю архитектуру сверху донизу. В суперкомпьютерах огромное количество вычислительных узлов, на каждом из них несколько отдельных процессоров, каждый процессор - это несколько ядер. Каждое ядро может быть суперскалярным - когда работает несколько функциональных устройств одновременно и синхронно запускается несколько операций. Если хотя бы на одном этапе процесса решения задачи допустить несогласованность, то эффективность работы компьютера будет близка к нулю. Поэтому фундаментальной проблемой высокопроизводительных вычислений стала необходимость аккуратного согласования структуры алгоритмов и программ с особенностями архитектуры компьютеров. 

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

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

- Какова структура описания алгоритма в энциклопедии?

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

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

- И эти описания будут размещать на сайте члены того самого вычислительного сообщества? Сколько же потенциальных авторов у AlgoWiki? 

Воеводин: - Хороший вопрос. Не подсчитывали, но стоит подумать. Полагаю, миллионов двадцать. На первом этапе AlgoWiki реализуется как русскоязычный проект для отечественного вычислительного сообщества, на следующем - как англоязычный. Создается и многоязычная версия, которая затем и станет основной. Ведь все используют одни и те же платформы, сталкиваются с одинаковыми проблемами, так что это проект для всего мирового вычислительного сообщества. 

- Но как можно организовать такую массу людей, да еще из разных стран, для решения общей задачи? 

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

Антонов: - Уже сейчас идет первоначальное наполнение сайта, и к коллективной работе над ним подключаются все новые авторы. Каждое описание включает в себя исследование свойств алгоритмов, программ и сопоставление их с особенностями архитектуры компьютеров. На всех трех этапах должны быть проанализированы два принципиально важных свойства, определяющих качество реализации алгоритма: ресурс параллелизма и эффективность работы с данными. Дополнительная сложность заключается в том, что эти особенности должны быть согласованы как по всем трем этапам, так и между собой на каждом этапе. Нужно выделить инварианты в описании алгоритмов, которые не меняются при переходе с платформы на платформу и которые как раз и станут основой для упрощения процесса программирования параллельных компьютеров. Описав в AlgoWiki свойства алгоритма, эту работу не нужно будет выполнять вновь при переходе с одного компьютера на другой. 

- AlgoWiki поможет решать какие-то практические задачи? 

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

Владимир Воеводин: "РНФ в требованиях к отчетам не забюрократизирован, его больше интересует содержательная сторона проекта, что вызывает положительную реакцию зарубежных коллег". 

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

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

- И это можно сделать, всего лишь заглянув в AlgoWiki? 

Антонов: - Если в первой части описания будут приведены все свойства алгоритма - его потенциал, количество операций, степень параллельности, ресурс параллельности, то во второй части - все, что связано с написанием конкретной программы, на конкретном языке, с помощью конкретной технологии параллельного программирования, под конкретную параллельную вычислительную систему. И тогда, начиная дело, каждый сможет увидеть, как решалась такая задача до него. Зная, что ему предстоит решить систему линейных уравнений, он зайдет на сайт энциклопедии, посмотрит, какие есть алгоритмы, оценит их с точки зрения эффективности реализации на той или иной платформе и поймет, стоит ли вкладывать деньги и время в разработку, основанную на данном алгоритме. А мы должны дать ему определенное резюме по эффективности, производительности платформы. И поскольку везде будет присутствовать параллелизм, то надо учесть такое важное понятие, как масштабируемость: будет ли работать вся система на восьми процессорах, на шестнадцати, или как распределить всю работу между тысячей, миллионом одновременно работающих узлов, процессоров. Но прежде кто-то должен добавить в AlgoWiki свои знания о том, как уже им решалась подобная задача. 

- У AlgoWiki есть зарубежный аналог? 

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

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

- В требованиях к заявке на грант Российский научный фонд ввел так называемый “принцип репутации”. Руководителем вашей научной группы стал Джек Донгарра. Это значит, что его репутация не вызывает никаких сомнений? 

Воеводин: - Да, на сегодня это авторитет №1 в суперкомпьютерном мире. Лет 15-20 назад у него были свои проекты по структуре алгоритмов. Сначала мы познакомились с его публикациями, потом встречались на научных конференциях, а в 2009 году состоялся его первый визит к нам - он выступил в МГУ с лекциями по вычислительным системам. Начали чаще пересекаться, думать о совместных проектах, потом он стал ведущим научным сотрудником НИВЦ МГУ с официальным статусом высококвалифицированного специалиста, приглашенного работать в России. Как раз тогда образовался РНФ, который объявил о первом конкурсе, и мы поняли, что есть хорошее поле для взаимодействия. К тому же РНФ в требованиях к отчетам не забюрократизирован, его больше интересует содержательная сторона проекта, что вызывает положительную реакцию зарубежных коллег. 

- Каким образом Донгарра осуществляет руководство проектом?

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

- Работа над энциклопедией завершится, когда закончатся все алгоритмы? 

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

- Тогда в каком случае проект можно будет считать успешным, завершенным?

Антонов: - Когда AlgoWiki будет работать без нашей помощи и начнется ее самоорганизация. Мы сразу делаем ее как международный проект. Но если “Википедию”, например, ругают, потому что там много ошибок, искаженной информации, то у нас, когда вычислительное сообщество подключится, автор каждой статьи нам будет известен. AlgoWiki станет действительно многоликой, и люди будут заглядывать в нее прежде, чем начинать что-то делать.

29 марта, 2024
Российские ученые обучили ИИ подбирать эффективную защиту для глаз от лазерного излучения
Российские ученые разработали нейросеть для быстрой оценки способности материалов блокировать опас...
29 марта, 2024
Ученые НГУ впервые провели радиоуглеродный анализ образцов из памятника андроновской культуры Вахрушево-1
Исследователи Института археологии и этнографии СО РАН совместно с коллегами из НГУ установили, чт...