Охотники за квадратами

Александр Андреев

Алек­сандр Андре­ев


Олег Заикин

Олег Заи­кин

Доб­ро­воль­ные распределен­ные вычисле­ния — отно­си­тель­но новый спо­соб рас­че­тов, в кото­рых ком­пью­те­ры част­ных лиц объ­еди­ня­ют­ся в спе­ци­аль­ных про­ек­тах для реше­ния мас­штаб­ных (чаще все­го на­учных) задач. После под­клю­че­ния к проек­ту вычис­ле­ния выпол­ня­ют­ся авто­ма­ти­че­ски, не при­чи­няя участ­ни­ку ника­ких неудобств (исполь­зу­ют­ся толь­ко сво­бод­ные ресур­сы ком­пью­те­ров). Хотя идея подоб­ной орга­низации вычис­ле­ний появи­лась доволь­но дав­но, пер­вым доб­ро­воль­ным про­ек­том с совре­мен­ны­ми чер­та­ми был стар­то­вав­ший в 1996 году про­ект GIMPS, предназначен­ный для поис­ка про­стых чисел Мер­сен­на. В 1999 году спе­ци­а­ли­ста­ми из Берк­ли был запу­щен про­ект SETI@home, зада­чей кото­рого был поиск радио­сиг­на­лов вне­зем­ных циви­ли­за­ций. В 2002 году на осно­ве SETI@ home была раз­ра­бо­та­на откры­тая платфор­ма BOINC, кото­рая зна­чи­тель­но упро­сти­ла созда­ние новых про­ек­тов доб­ро­воль­ных вычис­ле­ний. На дан­ный момент актив­но рабо­та­ют более 70 про­ек­тов, боль­шин­ство из кото­рых осно­ва­но на BOINC. Сум­мар­ная про­из­во­ди­тель­ность всех про­ек­тов сей­час состав­ля­ет более 7 петафлопс, с помо­щью этих колос­саль­ных ресур­сов каж­дый год де­лаются науч­ные откры­тия в мно­гих обла­стях. Сре­ди важ­ных резуль­та­тов сто­ит упо­мя­нуть откры­тие несколь­ких десят­ков радиопуль­саров в про­ек­те Einstein@home и откры­тие ряда про­стых чисел спе­ци­аль­но­го вида и ариф­ме­ти­че­ских про­грес­сий из про­стых чисел в про­ек­те PrimeGrid.

Успе­хи любо­го про­ек­та были бы невоз­можны без нали­чия в нем доста­точ­ных ком­пью­тер­ных мощ­но­стей. Но посколь­ку коли­че­ство про­ек­тов «@home» при­ближается уже к сотне и каж­дый их них борет­ся за поль­зо­ва­те­лей и их компью­теры, то кон­ку­рен­ция из-за вычислитель­ных ресур­сов идет доста­точ­но серьез­ная.

Рос­сий­ские кран­че­ры (так назы­ва­ют себя участ­ни­ки про­ек­тов доб­ро­воль­ных вычис­лений) дав­но истос­ко­ва­лись по отечествен­ным про­ек­там, кото­рые мож­но пере­счи­тать по паль­цам. Конеч­но, инте­рес­но участ­во­вать в поис­ке новых лекарств (про­ект Rosetta@home) или помо­гать в рас­че­тах маг­нит­ной систе­мы Боль­шо­го адрон­но­го кол­лай­де­ра (про­ект LHC@home). Одна­ко вдвойне при­ятнее было бы ока­зать посиль­ную помощь уче­ным-сооте­че­ствен­ни­кам. И вот, в сентя­бре 2011 года появил­ся рос­сий­ский про­ект SAT@home, кото­рый сра­зу при­влек внима­ние оте­че­ствен­ных кран­че­ров.

SAT (сокра­щен­но от Satisfability) — это зада­ча дока­за­тель­ства выпол­ни­мо­сти буле­вых фор­мул спе­ци­аль­но­го вида. SAT-под­ход состо­ит в све­де­нии исход­ных задач к SAT-зада­чам с их после­ду­ю­щим реше­ни­ем специальны­ми реша­те­ля­ми. С помо­щью SAT-под­хо­да мож­но решать зада­чи вери­фи­ка­ции, крип­тографии, ком­би­на­то­ри­ки, биоинформати­ки. В лабо­ра­то­рии дис­крет­но­го ана­ли­за и при­клад­ной логи­ки Инсти­ту­та дина­ми­ки си­стем и тео­рии управ­ле­ния Сибир­ско­го от­деления РАН (ИДСТУ СО РАН) SAT-под­ход актив­но раз­ви­ва­ет­ся. В част­но­сти, созда­ны про­грамм­ные ком­плек­сы, с помо­щью кото­рых к SAT све­де­ны зада­чи ана­ли­за динами­ки пове­де­ния ген­ных сетей, зада­чи крипто­анализа гене­ра­то­ров клю­че­во­го пото­ка, а так­же зада­чи поис­ка новых комбинатор­ных струк­тур (в первую оче­редь — систем латин­ских квад­ра­тов).

Полу­ча­е­мые SAT-зада­чи доволь­но слож­ные, но они допус­ка­ют раз­би­е­ние на неза­висимые друг от дру­га под­за­да­чи, что по­зволяет исполь­зо­вать для их реше­ния не толь­ко супер­ком­пью­те­ры, но и гри­ды. В ла­боратории были раз­ра­бо­та­ны и успеш­но исполь­зо­ва­ны на супер­ком­пью­те­рах па­раллельные SAT-реша­те­ли, но для обра­ботки неко­то­рых клас­сов задач не хва­тало вычис­ли­тель­ных ресур­сов. Имен­но поэто­му в 2011 году Инсти­ту­том динами­ки систем и тео­рии управ­ле­ния Сибирско­го отде­ле­ния РАН (Иркутск) в сотрудни­честве с Инсти­ту­том систем­но­го ана­ли­за РАН (Москва) был запу­щен про­ект добро­вольных рас­пре­де­лен­ных вычис­ле­ний SAT@home. Сна­ча­ла про­из­во­ди­тель­ность SAT@home была как у неболь­шо­го ком­пьютерного клас­са, но уже к сере­дине 2012 года она при­бли­зи­лась к показате­лям из спис­ка ТОП-50 суперкомпьюте­ров СНГ. Но, в отли­чие от обыч­но­го супер­компьютера, ресур­сы про­ек­та рабо­та­ют в режи­ме 247 на одну мас­штаб­ную зада­чу. По состо­я­нию на 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». Пер­вые два дня коман­ды шли «нозд­ря в нозд­рю», попе­ре­мен­но зани­мая лиди­ру­ю­щую пози­цию. При этом, если «Rus­sia Team» сде­ла­ла став­ку на при­вле­че­ние и акти­ви­за­цию мак­си­маль­но­го чис­ла сво­их участ­ни­ков (77 чело­век), то «Astronomy. Ru Forum» уда­лось побе­дить с огром­ным ито­го­вым отры­вом бла­го­да­ря участ­ни­ку из Турк­ме­ни­ста­на с ником tanos. Ему уда­лось при­влечь к рабо­те в про­ек­те более 200 ком­пью­те­ров и не толь­ко обес­пе­чить сво­ей коман­де побе­ду в этой вир­ту­аль­ной гон­ке, но и заслу­жен­но стать одним из ав­торов двух най­ден­ных реше­ний.

Идея запус­ка сорев­но­ва­ния полно­стью себя оправ­да­ла. Была достигну­та про­из­во­ди­тель­ность 6,3 терафлопс, что ста­ло исто­ри­че­ским мак­си­му­мом за 13 меся­цев рабо­ты про­ек­та (преды­дущий рекорд был 4,7 терафлопс, он так­же был достиг­нут во вре­мя подоб­но­го со­ревнования в 2011 году). Гра­фик произ­водительности про­ек­та за послед­ний год пред­став­лен ниже. Послед­ний пик соот­ветствует про­ве­ден­но­му недав­но сорев­нованию.

Одна­ко глав­ным резуль­та­том соревно­вания ста­ло нахож­де­ние двух пар диаго­нальных орто­го­наль­ных латин­ских ква­дратов поряд­ка 10. Ниже при­ве­де­на одна из най­ден­ных пар.

В этой паре в каж­дом квад­ра­те каж­дая стро­ка, стол­бец а так­же глав­ная и побоч­ная диа­го­на­ли состо­ят из чисел от 0 до 9, при этом ни одно чис­ло не повто­ря­ет­ся. Имен­но поэто­му каж­дый из этих квад­ра­тов яв­ляется латин­ским и диа­го­наль­ным. Усло­вие орто­го­наль­но­сти выпол­ня­ет­ся, так как если нало­жить пер­вый квад­рат на вто­рой, то ни одна из полу­чен­ных пар чисел не будет повторять­ся (для пер­вой ячей­ки пер­вой стро­ки это пара 08, для вто­рой ячей­ки — 16 и т. д.). Сей­час мы пытаем­ся оце­нить важ­ность полу­чен­ных нами результа­тов. С одной сто­ро­ны, ранее были извест­ны толь­ко три пары диа­го­наль­ных орто­го­наль­ных латин­ских квад­ра­тов, они были опуб­ли­ко­ва­ны в 1992 году [1]. С дру­гой сто­ро­ны, глав­ный резуль­тат ста­тьи [1] со­стоял в дока­за­тель­стве суще­ство­ва­ния таких пар, и авто­ры не ста­ви­ли перед собой зада­чу най­ти их как мож­но боль­ше.

В пер­спек­ти­ве в рам­ках про­ек­та пла­ни­ру­ет­ся ор­ганизация ново­го мас­штаб­но­го вычис­ли­тель­но­го экс­пе­ри­мен­та, направ­лен­но­го на поиск трой­ки по­парно орто­го­наль­ных латин­ских квад­ра­тов поряд­ка 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. Pp 43–49.

Если вы нашли ошиб­ку, пожа­луй­ста, выде­ли­те фраг­мент тек­ста и нажми­те Ctrl+Enter.

Связанные статьи

Оценить: 
Звёзд: 1Звёзд: 2Звёзд: 3Звёзд: 4Звёзд: 5 (Пока оценок нет)
Загрузка...
 
 

Метки: , , , , ,

 

Один комментарий

  • димыч:

    все это хоро­шо, вот толь­ко перед сорев­но­ва­ни­я­ми нуж­но боль­ше зада­ний гене­рить, что­бы потом во вре­мя рас­че­та не сидеть за ком­пом и вруч­ную не обнов­лять запро­сы зада­ний. а то в обыч­ном режи­ме запас по 40–50 тысяч, а как чел­лендж, так идет элек­трон­ный вари­ант игры «кто пер­вый успел схва­тить тот и моло­дец»

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Недопустимы спам, оскорбления. Желательно подписываться реальным именем. Аватары - через gravatar.com