Архивы: по дате | по разделам | по авторам

Распределенное время

Архив
автор : Владимир Николаевич   08.06.2004

В прошлом году массовым распределенным вычислениям исполнилось пятнадцать лет, а наиболее крупный из таких проектов — SETI@home — в этом году отмечает свое пятилетие.

В прошлом году массовым распределенным вычислениям исполнилось пятнадцать лет, а наиболее крупный из таких проектов — SETI@home — в этом году отмечает свое пятилетие. В таком возрасте уже можно подвести некоторые итоги, оценить достигнутое и сделать прогнозы на будущее.

В начале 1997 года распределенные вычисления впервые привлекли внимание широкой публики. Компания RSA Data Security, продвигающая на рынок свой криптоалгоритм, объявила, что заплатит десять тысяч долларов тому, кто взломает небольшое сообщение, зашифрованное старомодным алгоритмом DES. Перебор ключей для DES-шифровки на одной машине был безнадежен (количество вариантов равнялось 7х1016), но RSA ожидала, что солидный приз заставит энтузиастов объединится в команды, связанные по Сети, и перебирать ключи совместно. Расчет оправдался — за дело взялось множество групп, и одна из них — DESCHALL — нашла ключ (и получила приз) уже в июне 1997 года. Таким образом RSA

продемонстрировала, что общепринятая DES-криптография устарела и надо использовать новую, разработанную ею. Кроме DES-шифровки RSA предложила взломать свою собственную, и вот вокруг одной из команд, собравшейся для решения этой задачи, само собой сложилось крупное сетевое сообщество, координировавшее усилия через сайт Distributed.net. Сайт предлагал новичкам понятную инструкцию, удобную статистику и хорошую программу для подбора ключей, работавшую в фоновом режиме. В уставе сообщества заявлялось, что если денежный приз достанется им, то большая часть будет передана в Project Gutenberg, занимающийся переводом книг в электронную форму1.

В течение 1997 года количество участников Distributed.net росло как на дрожжах. Интернет-бум был в самом разгаре, проект часто освещали масс-медиа (включая «КТ»), а множество веб-сайтов размещали у себя баннеры сервера. В результате этот стихийно образовавшийся коллектив быстро перевалил за 10 тысяч человек, потом за 50, потом за сто и между делом бил прежние рекорды распределенных вычислений. Компания RSA вовремя подкидывала новые задания с денежными призами, но уже в начале 1998 года многим стало ясно, что затея переросла в нечто большее и взлом какой-то шифровки мало кого интересует, — не будь этого задания, было бы другое.

Сообщество Distributed.net стало первым, набравшим более ста тысяч участников. Оно же первым превратилось в своеобразную самоподдерживающуюся реакцию, которая длится по сей день. Его размеры со временем не уменьшаются: хотя большинство зарегистрировавшихся теряет к проблеме интерес и уходит — расширение Интернета обеспечивает постоянный приток новичков, которые полностью компенсируют потери. Из-за этого даже спустя семь лет сообщество активно работает и периодически берется за новые задачи2.

С 1998 года, после стремительного взлета Distributed.net, проекты распределенных вычислений начали расти как грибы. Сегодня только действующих насчитывается больше полусотни, а если прибавить к ним те, что за истекшее время были начаты и закрыты, то окажется, что последние шесть лет ежемесячно запускалось не меньше двух новых проектов, открытых для всех желающих. Большая часть из них канула в небытие, и это подводит нас к интересной теме — огромной разнице в размерах распределенных сообществ и, как следствие, разнице их судеб.

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

Если мы внимательно приглядимся к окружающему миру, то заметим, что сплошь и рядом в нем действует довольно странное правило степенного распределения. Все мы интуитивно знаем его и нередко формулируем в расхожих выражениях, вроде: «меньшинство людей совершает большинство преступлений» или: «20% книг получают на рынке 80% читательской аудитории». На деле, конечно, кривая распределения не всегда настолько крутая, и цифры не такие круглые, но, по большому счету, они верны. Например, наша речь состоит из крошечной группы самых употребимых слов, а остальные десятки тысяч слов мы произносим всего пару раз в жизни. И это вовсе не человеческая особенность. Более 9/10 видимой массы нашей Вселенной приходится на один элемент — водород. Небольшая часть людей контролирует большую часть денег и ресурсов. Основная энергия нашего Солнца излучается в очень узком диапазоне волн…

Сеть подчиняется этому правилу. Если мы рассмотрим любую группу ее ресурсов — поисковики или почтовые серверы, игровые или новостные ресурсы, веблоги или форумы, — везде увидим степенное распределение, по которому (очень упрощенно) занимающий N-ное место получает 1/N чего-либо3. Например, ссылок с других веб-сайтов. Или ежедневных посещений, хакерских атак, денег рекламодателей и пр. Какой бы показатель мы ни взяли, нарисовав график его распределения (между веб-ресурсами), увидим, что никакого равенства в свободной Сети нет.

Как легко догадаться, распределенные вычисления не являются исключением. Первое место держит проект SETI@home, за пятилетнюю историю привлекший 4,8 млн. участников. На втором месте — Grid.org компании United Devices, созданный для поиска лекарств от рака (около двух миллионов человек). А следующие места занимают сообщества, насчитывающие всего по несколько сотен тысяч участников. Так, Distributed.net за пять лет взлома шифровки RSA-64 привлек 330 тысяч человек (взлом завершен в 2002 году). Участников Folding@home, ведущих4 распределенный фолдинг белков (проект начат в октябре 2000 года), сегодня насчитывается около полутораста тысяч, не в последнюю очередь из-за встраивания кода проекта в Google.Toolbar известного поисковика Google. Это чистое степенное распределение, где кучка мегазвезд получает львиную долю, а остальное большинство находится ниже срединной линии.

Как изменится эта ситуация в будущем? Например, через десять лет, когда доступ в Сеть будет у миллиарда человек и проекты будут исчисляться сотнями? Здравый смысл говорит нам, что многообразие сгладит различия и неравенство станет менее острым. Однако в действительности все будет наоборот! По мере развития Интернета его пользователи вовсе не растекаются ровным слоем по всем доступным ресурсам. Их миллионные массы группируются лишь в нескольких местах, и с годами меняются только лидеры этой стихийной иерархии. Сама же она не выказывает никаких признаков размывания. А поскольку размеры аудитории растут, то растет и пропасть между верхушкой и серединой, между Альфой и Омегой. И если сегодня сообщество лидера (SETI@home) в тысячу раз больше сообщества аутсайдера (например, российского MD@home), то через десять лет разрыв может стать десятитысячным.

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

Примечательна судьба двух нынешних лидеров — SETI@home и Grid.org. Оба родились довольно поздно и были вынуждены соперничать с проектами-ветеранами. Оба активно рекламировали себя в сетевых масс-медиа. Однако SETI@home менее чем за год стал бесспорным лидером, а Grid.org, стартовав 3 апреля6 2001 года, повторить этот успех так и не смог. Несмотря на активную рекламу и солидное финансирование (поначалу среди участников регулярно разыгрывались приставки PlayStation 2), проект компании United Devices сегодня более чем вдвое отстает от лидера. Наверняка UD рассчитывала на большее. Она вообще выделяется на общем фоне Distributed Computing, действуя основательно и с американским размахом.

Созданная Дэвидом Андерсом (стоявшим у истоков SETI@home), UD сразу зарегистрировала как торговую марку сочетание «Global MetaComputer» и заняла домен grid.org. Программная платформа UD, координирующая нынешние антираковые вычисления, рекламируется как гибкий механизм использования компьютерных ресурсов в маленьких фирмах и больших корпорациях. Об успехах этого бизнеса судить трудно, но важны сами попытки заработать деньги на внедрении распределенных вычислений. Кстати, своей главной целью UD считает не поиск лекарства от рака (это лишь пробный шар), а создание огромного сообщества для решения самых разных вычислительных задач. На сайте grid.org можно ознакомиться с планами компании на будущее: миллиарды компьютеров соединены в огромную сеть, и все желающие получают из нее столько вычислительной мощности, сколько хотят. Как электричество из розетки — дешево, много и в любую секунду. Именно отсюда термины «Grid» (power grid — электросеть) и «глобальный метакомпьютер»7.

В сравнении с усилиями UD, SETI@home выглядит студенческим утренником. Однако именно эта затея с, мягко говоря, эксцентричной целью — поймать радиосигналы от инопланетян — привлекает вдвое больше людей, нежели поиск лекарств от рака8. Наверняка и участники SETI@home, если поставить вопрос ребром, согласятся, что борьба с раком неизмеримо благороднее их игры в бисер. Тем не менее, ряды искателей братьев по разуму множатся быстрее всего. За четыре последних года мощность виртуального метакомпьютера этого проекта почти удесятерилась, увеличившись с 8 до 70 Тфлопс. За пять лет существования он утилизировал (иначе не скажешь) без малого два миллиона машино-лет вычислений. Не часов, а лет! Два миллиона! Если принять, что один клиент SETI@home потребляет при работе 10 Вт9, то окажется, что всего на эту затею было потрачено почти 200 гигаватт-часов электроэнергии. Даже по нашим, далеко не калифорнийским ценам они тянут на сотню миллионов долларов. И конца тратам не видно — сообщество SETI@home продолжает расти…

Распределенные вычисления, не привлекшие должного внимания публики

MD@home. Первый и пока единственный российский проект распределенных вычислений. Проводится при поддержке кафедры биофизики МГУ и ставит целью моделирование свойств очень коротких цепочек аминокислот. Запущен в 2002 году. Насчитывает чуть более полутысячи активных участников, которые уже просчитали все возможные комбинации из трех и четырех аминокислот. Сейчас обрабатываются пятичлены (пентапептиды). Результаты будут выложены в открытый доступ и использованы для создания искусственных белков, а также лекарств нового типа. Пример такого лекарства — гекса-D-аргинин, созданный в 2002 году для лечения сибирской язвы и состоящий всего из шести молекул одной аминокислоты — аргинина. По «доброй» российской традиции MD@home хронически страдает от неустойчивого хостинга. Подробнее см. на www.md-at-home.ru.

D2OL — Drug Design Optimization Lab (www.d2ol.com ). Распределенный поиск новых лекарств от малярии, лихорадки Эбола и некоторых форм склероза. Проект насчитывает несколько десятков тысяч участников и спонсируется крупными университетами.

Find-a-drug (www.find-a-drug.com ). Поиск лекарств от рака, СПИДа, поиск безопасных гербицидов и т. д. В проект регулярно добавляются новые направления исследований, а участники могут свободно выбирать, на что тратить ресурсы своего компьютера.

Distributed Folding (www.distributedfolding.org ). Моделирование свертывания белков (фолдинг) и одновременно отладка алгоритма моделирования. Проект имеет программы-клиенты для самых разных операционных систем, включая Linux для Sony PlayStation. Зачем нужен фолдинг белков, «КТ» рассказывала в теме номера «Биоконструктор» (#483).


1 Project Gutenberg тоже распределенный проект, хотя не столько вычислений, сколько распознаваний. В октябре 2003 года силами его участников была выложена в свободный доступ десятитысячная книга.
2 Участники Distributed.net (как и большинства других проектов) могут образовывать команды, и одна из них ноcит название «Команда Компьютерры». 159 ее участников занимают 21-е место в командном рейтинге проекта. Подробнее см. www.myportal.ru/team.
3 По такой (1/N) формуле первый номер списка должен забрать себе все. Но эта дробь задает только изначальную форму базовой кривой.
4 folding.stanford.edu.
5 Интересующиеся этим вопросом могут прочесть в «Русском Журнале» статью Клэя Ширки «Веблоги и неравенство» (www.russ.ru/netcult/20030217 ), где кроме примеров и попыток анализа даются ссылки на академические работы по данной теме.
6 www.ud.com .
7 Заметим, что UD не является автором подобных идей, а Grid-вычисления в целом — крайне модная сегодня тема. Так, в конце мая в Филадельфии прошла конференция Grid Today 2004 с участием компании Boeing, American Airlines и торговая сеть Wal-Mart. Тема обсуждения — Commercial Business Applications of Grid Computing.
8 Сравнить эти проекты можно и по количеству машино-часов, которые ежесуточно тратятся на расчеты. По официальной статистике, у SETI@home их 3,2 млн., а у Grid.org 2,3 млн. Но это необъективный показатель, поскольку предполагает выбор некоей усредненной машины, которая в разных проектах всегда разная.
9 Цифра занижена, для удобства расчетов. Большинство процессоров потребляет десятки ватт, а распределенные расчеты максимально загружают процессор. В обычных же офисных задачах потребление составляет лишь несколько ватт.

Дело, конечно, не в этом конкретном проекте. Если завтра он внезапно закроется, это мало что изменит. Дело в том, что наши вычислительные ресурсы ограничены, а проблемы бесконечны. И в такой ситуации надо тщательно выбирать цели, прежде чем тратить на них столь огромные усилия. Однако миллионные массы не могут тщательно выбирать! Особенно если они молоды и не привыкли к самокопанию. Отчего взлом шифровок на Distributed.net, бесполезный абсолютно и очевидно, привлек в несколько раз больше людей, чем фолдинг белков? Не в последнюю очередь оттого, что взламывать шифровки — круто. Это порождает чувство причастности к славному племени хакеров, и 330 тысяч взломщиков RSA-64 — это 330 тысяч маленьких, но гордых друзей Кевина Митника и Нео. А на кого похожи участники Folding@home? Даже в собственных глазах они похожи на «чокнутых ученых» в белых халатах, которых в 3D-шутерах обычно расстреливают, чтоб не путались под ногами.

Главным ресурсом развития распределенных проектов являются домашние пользователи. Очевидно, их приток в Сеть будет продолжаться еще долго. Вероятно, самые активные и богатые проекты начнут вести целенаправленные рекламные кампании. До сих пор этого не наблюдается, из-за чего в распределенных вычислениях участвует менее одного процента сетевой аудитории. На это просто нет моды. Постоянное ускорение домашних компьютеров (по закону Мура) позволит проектам, как и раньше, непрерывно наращивать силы. Трудно сказать, смогут ли самые крупные из них по-прежнему превосходить любой «нормальный» суперкомпьютер. Кластерные системы, входящие в Тор500, тоже развиваются необычайно быстро. Так, в скором времени должны быть запущены суперкомпьютеры Red Storm от Cray и ASCI Purple от IBM, производительностью соответственно 40 и 100 Тфлопс. Они наверняка обставят виртуальные метакомпьютеры Grid.org и SETI@home, если только у последних не найдется подходящего туза в рукаве…

Одним из вычислительных резервов, который до сих пор не используется, могли бы стать современные видеокарты, уже нередко превосходящие центральные процессоры по количеству транзисторов. На первый взгляд эта идея — использовать видеоускоритель для вычислений — может показаться шуткой. Тем не менее, группа товарищей из Стэнфордского университета уже создала программу BrookGPU, превращающую шутку в реальность. Эта программа (точнее, набор С-библиотек и специальный компилятор) позволяет исполнять на графическом процессоре видеокарты многие операции с плавающей запятой. Пока разработана бета-версия, но и она достигает на карте GeForce FX 5900 Ultra скорости 20 Гфлопс. Так мог бы работать Pentium 4, разогнанный до 10 ГГц.

Впрочем, и подключение видеокарт, и закон Мура, и общий рост сетевой аудитории — это лишь количественные перемены. А качественный скачок (очередной) распределенные проекты могут совершить благодаря широкополосному интернет-доступу. Среди домашних пользователей он распространяется медленно, но уже сегодня больше двадцати миллионов семей в США являются абонентами кабельного или ADSL-подключения, обычно на условиях круглосуточного Unlimited. Представьте, что двадцатая часть этих семей включится в некий проект, выделив ему на своих винчестерах 1 Гбайт свободного места, 100 Мбайт оперативной памяти и (в среднем) 1 ГГц процессорной мощи. С хорошим ADSL тут действительно недалеко до глобального метакомпьютера, который нам обещает United Devices…

 

Многие думают, что история Distributed Computing началась лишь во второй половине 1990-х годов, когда в Интернет начали вливаться миллионы рядовых пользователей. Однако еще в начале 1970-х в исследовательском центре PARC (Xerox, Palo Alto) ученые, создававшие программы для первых компьютерных сетей, задумались об использовании свободных вычислительных ресурсов имевшихся в центре машин.

Двое исследователей — Джон Шох и Жон Хапп (John F. Shoch, Jon A. Hupp) — написали в 1973 году несложную программу, которая запускалась в локальную сеть центра по ночам, расползалась по невыключенным компьютерам и заставляла их выполнять разного рода вычисления. В честь похожей программы из фантастического рассказа Джона Браннера авторы назвали свое детище червяком. Параллель между программой из PARC и современными интернет-червями справедлива. Однако стоит заметить, что Шох и Хапп вовсе не пытались создать некоего гада, разбегающегося по всем щелям с максимальной скоростью, — это сделал Роберт Моррис в 1988 году, отчего его и считают отцом сетевых червей. Ученых же из PARC волновали сугубо утилитарные задачи.

Идея совместной работы множества компьютеров, объединенных в сеть, оказалась вполне плодотворной и далее развивалась медленно, но верно. К концу 1980-х, когда компьютеры уже стали персональными, а их владельцы все чаще использовали электронную почту, произошел качественный скачок. Арьен Ленстра и Марк Менес (Arjen K. Lenstra, Mark S. Manasse), также работавшие в Рало-Альто, но уже на компанию DEC, написали программу для факторизации (разбиения на множители) длинных чисел. Чтобы процесс шел быстрее, программа могла запускаться на множестве машин, каждая из которых обрабатывала лишь небольшой фрагмент числа. Проект был сугубо научным и очень простым, но главное — связь между его участниками могла быть эпизодической. Фактически использовалась обычная электронная почта, и очень быстро в расчеты оказалось втянуто несколько сотен человек. Через два года это сообщество впервые в истории разложило на множители число длиной сто знаков.

По сути, Ленстра и Менес продемонстрировали, как можно создать «на коленке» необычайно успешный распределенный проект. Именно поэтому родословную нынешних распределенных вычислений следует вести от первой факторизации 1988 года, а не от более раннего червя-вампира из PARC. Все-таки, несмотря на общую суть, эти два проекта сильно отличались. В лаборатории PARC машины были связаны первым Ethernet’ом и постоянно обменивались данными на большой скорости. Это был прообраз кластерных суперкомпьютеров. В тоже время участники факторизации были связаны очень медленными каналами, да и то не всегда, а эпизодически, и не друг с другом, а лишь с центральным сервером проекта.

Хотя термины для того и другого давно устоялись (Distributed Computing и Grid Computing), их до сих пор часто смешивают, нередко сознательно и с вполне корыстными целями. Мы не станем вникать в нюансы терминологии, а просто зафиксируем, что далее будем рассматривать лишь идейных потомков проекта Ленстры и Менеса, поскольку их могут создавать обычные люди и они открыты для участия рядовых интернет-пользователей.
Уже в первые распределенные вычисления (1988) оказалась втянута компьютерная мощь, суммарно стоившая миллионы долларов. Это впечатляло, но было понятно, что вычисления такого рода годятся лишь для специфических задач. В отличие от суперкомпьютера Cray, способного, грубо говоря, считать что угодно, тысячи энтузиастов связанных по электронной почте при всем желании не могут эффективно рассчитывать, например, форму гребного винта — эта задача требует постоянного обмена данными между машинами участников. Проблема взаимосвязи — ахиллесова пята распределенных проектов. Их участники только изредка, раз в сутки (а лучше — реже), готовы обмениваться с сервером проекта небольшими файлами. Очевидно, что организовать вычисления в таком квазипараллельном режиме — весьма непросто. Тем не менее, некоторые задачи даже в таких условиях решаются просто замечательно, если удовлетворяют одному требованию — огромное количество работы над маленьким объемом данных.

Вполне естественно, что первыми такими проектами стали разного рода математические исследования. Нередко их участникам рассылалось всего несколько байт — координаты на линии чисел, между которыми надо было провести некий поиск, например новых чисел Серпинского. Конечно, все это было интересно лишь горячим поклонникам математики, но, судя по хронике, увлеченных людей в Интернете всегда хватало. В 1993 году одна из таких групп факторизовала число длиной 129 знаков. Потом длиной 130. А затем пошла мода на поиск простых чисел — делящихся лишь на единицу и на самих себя. Проектов такого рода возникло не один десяток — разные группы брались за поиск новых чисел Мерсенна, дружественных и совершенных чисел, расчет числа p и т. д. и т. п. Многие из этих сообществ работают до сих пор, но мы не будем на них останавливаться — читатели могут найти в нашем архиве статью «Гонки по вертикали» Леонида Дурмана («КТ» ## 394, 395). 

© ООО "Компьютерра-Онлайн", 1997-2024
При цитировании и использовании любых материалов ссылка на "Компьютерру" обязательна.