Сейчас, сейчасОхотники за квадратами
vott.ru — Добровольные распределенные вычисления — относительно новый способ расчетов, в которых компьютеры частных лиц объединяются в специальных проектах для решения масштабных (чаще всего научных) задач. После подключения к проекту вычисления выполняются автоматически, не причиняя участнику никаких неудобств (используются только свободные ресурсы компьютеров)
Суммарная производительность всех проектов сейчас составляет более 7 петафлопс, с помощью этих колоссальных ресурсов каждый год де- лаются научные открытия в многих областях. Среди важных результатов стоит упомянуть открытие нескольких десятков радиопульсаров в проекте Einstein@home и открытие ряда простых чисел специального вида и арифметических прогрессий из простых чисел в проекте PrimeGrid. Успехи любого проекта были бы невозможны без наличия в нем достаточных компьютерных мощностей. Но поскольку количество проектов «@home» при- ближается уже к сотне и каждый их них борется за пользователей и их компьютеры, то конкуренция из-за вычислительных ресурсов идет достаточно серьезная. Российские кранчеры (так называют себя участники проектов добровольных вычислений) давно истосковались по отечественным проектам, которые можно пересчитать по пальцам. Конечно, интересно участвовать в поиске новых лекарств (проект Rosetta@ home) или помогать в расчетах магнитной системы Большого адронного коллайдера (проект LHC@home). Однако вдвойне приятнее было бы оказать посильную помощь ученым-соотечественникам. И вот, в сентябре 2011 года появился российский проект SAT@home, который сразу привлек внимание отечественных кранчеров. SAT (сокращенно от Satisfiability) — это задача доказательства выполнимости булевых формул специального вида. SAT-подход состоит в сведении исходных задач к SAT-задачам с их последующим решением специальными решателями. С помощью SAT-подхода можно решать задачи верификации, криптографии, комбинаторики, биоинформатики. В лаборатории дискретного анализа и прикладной логики Института динамики систем и теории управления Сибирского отделения РАН (ИДСТУ СО РАН) SAT-подход активно развивается. В частности, созданы программные комплексы, с помощью кото- рых к SAT сведены задачи анализа динамики поведения генных сетей, задачи криптоанализа генераторов ключевого потока, а также задачи поиска новых комбинаторных структур (в первую очередь — систем латинских квадратов). Получаемые SAT-задачи довольно сложные, но они допускают разбиение на независимые друг от друга подзадачи, что позволяет использовать для их решения не только суперкомпьютеры, но и гриды. В лаборатории были разработаны и успешно использованы на суперкомпьютерах параллельные SAT-решатели, но для обработки некоторых классов задач не хватало вычислительных ресурсов. Именно поэтому в 2011 году Институтом динамики систем и теории управления Сибирского отделения РАН (Иркутск) в сотрудничестве с Институтом системного анализа РАН (Москва) был запущен проект добро- вольных распределенных вычислений SAT@home. Сначала производительность SAT@home была как у небольшого компьютерного класса, но уже к середине 2012 года она приблизилась к показателям из списка ТОП-50 суперкомпьютеров СНГ. Но, в отличие от обычного суперкомпьютера, ресурсы проекта работают в режиме 24/7 на одну масштабную задачу.
По состоянию на 10 ноября 2012 года, в проекте было зарегистрировано 3152 участника из 92 стран, которые подключили 8277 компьютеров. На данный момент российские добровольцы суммарно выполнили 42% вычислений в проекте, добровольцы из США выполнили 17%, а из Германии — 11%. У остальных стран доля выполненных вычислений значительно меньше. Средняя производительность проекта составляет 2,3 терафлопс. В мае 2012 года в проекте был проведен полугодовой эксперимент, направленный на решение 10 задач исследования стойкости системы шифрования A5/1, которые не решаются известными стандартными способами (с помощью rainbow-таблиц). В каждой задаче нужно было найти неизвестное начальное заполнение генератора ключевого потока, по сути это задача обращения функции — по известному выходному значению надо найти входное значение. Все 10 задач были успешно решены в проекте. Сейчас в SAT@home запущен эксперимент, направленный на поиск пар и троек ортогональных латинских квадратов порядка 10. Латинский квадрат порядка n — это таблица n * n, заполненная n различными символами таким образом, чтобы в каждой строке и в каждом столбце встречались все n символов (каждый по одно- му разу). Пара латинских квадратов одинакового порядка называется ортогональной, если различны все упорядоченные пары символов (a,b), где a — символ в некоторой клетке первого латинского квадрата, а b — символ в той же клетке второго латинского квадрата. Латинские квадраты применяются в различных прикладных областях, таких как криптография (несколько шифров построены на специально подобранных латинских квадратах), проведение экспериментов (использование пар ортогональных латинских квадратов позволяет сократить перебор вариантов), а также в кодировании информации (система попарно ортогональных латинских квадратов позволяет составить правильный порядок передачи данных). Руководители российского проекта SAT@ home изначально установили тесный контакт с российским сообществом любителей добровольных распределенных вычислений. Ведутся активные дискуссии на форуме сайта BOINC.RU, обеспечивая обратную связь между организаторами и участниками проекта. И это показало свою эффективность. Для ускорения работы проекта одна из российских команд организовала на статистическом сайте BOINCstats.com соревнования в проекте SAT@home, в которых приняли участие 16 команд и более 200 участников из разных стран. Суть подобных виртуальных со- ревнований состоит в том, что в течение ограниченного периода времени (обычно 7 дней) статистика для зарегистрированных участников обновляется каждые 15 минут (а не раз в сутки, как обычно). Поэтому следить за изменением соревновательной ситуации мож- , ня практически в реальном масштабе времени. Победителем считается участник или команда, получившие наибольшее количество начисляемых баллов (кредитов) за отведенное время, т.е. обработавшие наибольшее число заданий проекта. В итоге команды и участники стараются активизироваться, подключить дополнительные вычислительные мощности для более успешного выступления. Проект при этом получает мощный прирост производительности и одновременно се- рьезную нагрузку на сервер, так как резко возрастает количество подключений для получения заданий и отправки результатов. Ну а участники взамен имеют соревновательный азарт, приток адреналина и моральное удовлетворение. Данное соревнование было посвящено годовщине проекта. Но поскольку оно проводилось на месяц позднее «юбилея» (из-за запуска в проекте нового эксперимента в нем некоторое время не было заданий), то получило в шутку название «Счастливая "чертова дюжина"» («Happy "baker's dozen"»). Соревнование проходило в очень напряженной борьбе, которую вели между собой команды «Russia Team» и «Astronomy. Ru Forum». Первые два дня команды шли «ноздря в ноздрю», попеременно занимая лидирующую позицию. При этом, если «Russia Team» сделала ставку на привлечение и активизацию максимального числа своих участников (77 человек), то «Astronomy. Ru Forum» удалось победить с огромным итоговым отрывом благодаря участнику из Туркменистана с ником tanos. Ему уда- лось привлечь к работе в проекте более 200 компьютеров и не только обеспечить своей команде победу в этой виртуальной гонке, но и заслуженно стать одним из авторов двух найденных решений.
Идея запуска соревнования полностью себя оправдала. Была достигнута производительность 6,3 терафлопс, что стало историческим максимумом за 13 месяцев работы проекта (предыдущий рекорд был 4,7 терафлопс, он также был достигнут во время подобного соревнования в 2011 году). График произ- водительности проекта за последний год представлен ниже. Последний пик соответствует проведенному недавно соревнованию. Однако главным результатом соревнования стало нахождение двух пар диагональных ортогональных латинских квадратов порядка 10. Ниже приведена одна из найденных пар. В этой паре в каждом квадрате каждая строка, столбец а также главная и побочная диагонали состоят из чисел от 0 до 9, при этом ни одно число не повторяется. Именно поэтому каждый из этих квадратов является латинским и диагональным. Условие ортогональности выполняется, так как если наложить первый квадрат на второй, то ни одна из полученных пар чисел не будет повторяться (для первой ячейки первой строки это пара 08, для второй ячейки — 16 и т. д.). Сейчас мы пытаемся оценить важность полученных нами результатов. С одной стороны, ранее были известны только три пары диагональных ортогональных латинских квадратов, они были опубликованы в 1992 году.
С другой стороны, главный результат статьи состоял в доказательстве существования таких пар, и авторы не ставили перед собой задачу найти их как можно больше. В перспективе в рамках проекта планируется ор- ганизация нового масштабного вычислительного эксперимента, направленного на поиск тройки по- парно ортогональных латинских квадратов порядка 10. На текущий момент 10 — это минимальный порядок, для которого неизвестно существование такой тройки. Эта задача очень сложная, несколько научных коллективов по всему миру пытаются решить ее уже несколько десятилетий. Вообще добровольные вычисления оказались очень хорошим подспорьем для проведения научных экспериментов. К тому же здесь идет постоянное живое общение с участниками, что очень полезно для развития и оптимизации как проекта, так и всего процесса научного исследования. 1. Brown et al. Completion of the Spectrum of Orthogonal Diagonal Latin Squares. Lecture notes in pure and applied mathematics. 1992. Vol. 139.
[censored]
[censored]
[censored]
[censored]