Задумывались ли вы когда-нибудь над вопросом, сколько времени ваш компьютер работает вхолостую? С первых шагов развития вычислительной техники машинное время было драгоценным, его пытались использовать как можно эффективнее, оптимизируя программы, запуская задачи в пакетном режиме, выжимая из машины все до последнего байта (с последствиями одной из таких оптимизаций мы имеем шанс столкнуться уже менее чем через месяц, ну да сейчас речь не об этом). Сейчас же мы имеем ситуацию, совершенно немыслимую еще лет 10-15 назад. На наших столах стоят системы, по производительности равные суперкомпьютерам десятилетней давности. Причем основное их занятие у среднего пользователя - отрисовка окошек да простенькие расчеты, на что уходит, дай бог, процентов пять процессорного времени. С другой стороны, задач, решение которых находится на пределе возможностей современной техники, меньше не становится - просто появляются новые, о решении которых раньше не смели и мечтать. А какие задачи можно было бы решать, если б удалось утилизовать всю вычислительную мощь, накопленную человечеством на миллионах простаивающих компьютеров - аж дух захватывает...

А способ, между прочим, лежит на поверхности, и имя ему - распределенные вычисления. Его уже нельзя назвать экзотическим - стандартные возможности по одновременной компиляции программы на нескольких машинах включал еще Symantec C++, аналогичными возможностями по просчитыванию трехмерных изображений давным-давно обзавелась 3DStudio, и это только примеры продуктов, ориентированных на относительно широкие массы.

Существуют реализации бесплатно распространяемых библиотек, поддерживающих распределенные вычисления. Наибольшую популярность получили PVM (Parallel Virtual Machine) и реализации относительно недавно возникшего стандарта MPI (Message Passing Interface). С их помощью достаточно легко создать гетерогенные вычислительные системы, состоящие, к примеру, из Unix- и NT-машин.

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

Одним из пионеров интернетовского распределенного компьютинга (по крайней мере, доживших до наших дней), по праву считается группа distributed.net. Организованная в начале 1997 года в рамках проекта по вскрытию 56-битного ключа RC5, спонсируемого разработчиком шифра RSA (вообще надо сказать, что немалая часть популярных проектов связана именно с вскрытием некоего шифра - и спонсируется его разработчиком, в целях доказательства его надежности или ненадежности, само же вскрытие осуществляется методом грубой силы - простым перебором), группа успешно завершила его 27 октября 1997 года, достигнув к этому моменту скорости в 5.3 гигаключей в секунду. Тогда же начался очередной проект по взлому уже 64-битного ключа RC5, продолжающийся до сих пор со все возрастающей скоростью. Параллельно основной задаче, RC5-64, за это время distributed.net были успешно выиграны два конкурса на вскрытие DES, а совсем недавно начался проект по вскрытию ключа CS-Cipher. Надо отметить, что приз, назначенный RSA за обнаружение ключа RC5-64, составляет десять тысяч долларов, а приз за взлом CSCipher - десять тысяч евро.

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

Таким образом, отдавая distributed.net часть мощности своих компьютеров, участники проекта получают возможность выиграть некий денежный приз. Изначальная сумма делится по-братски: две тысячи долларов (или евро в случае CSC) забирает distributed.net, шесть тысяч уходят в подарок некоторой некоммерческой организации (которая определяется голосованием участников), одна тысяча счастливчику, нашедшему ключ, и одна тысяча - его команде (или опять же ему, если он не принимает участия в команде).

Да, я же совсем ничего не сказал о командах. Именно команды стали тем, что выделило distributed.net на фоне других аналогичных проектов, существовавших два года назад, и придало всей затее характер спортивного соревнования. Многие ведущие компьютерные сайты и компании сочли своим долгом организовать свои команды. Фигурирующие в именах команд названия AnandTech, SlashDot, L0pht, IBM о чем-то да говорят. Участвуют в проекте и российские (точнее, русскоязычные) команды, и крупнейшая из них - HackZone Team - объединяя в своих рядах более 1700 участников из xUSSR, на равных борется с упомянутыми грандами (достаточно сказать, что это четвертая команда проекта по количеству участников и производительности). Впрочем, будучи одним из основателей команды, я не могу быть до конца беспристрастным :)

В планах distributed.net - создание клиента для решения чисто математической задачи - нахождения оптимальной линейки Голомба. Задача ставится следующим образом. Рассматривается линейка с ограниченным количеством делений. Расстояния между делениями кратны некоторому минимальному значению и соответствуют неотрицательным целым числам, причем расстояние между любой парой делений должно быть уникальным. Пример простейшей линейки с тремя делениями - 0,1,3 - расстояния между делениями - 1, 2, 3. Общее количество пар делений для линейки с N делениями, очевидно, равно числу сочетаний из N по 2, т.е. N*(N-1)/2. Оптимальной линейкой Голомба называется линейка с минимальными расстояниями между делениями. Приведенная выше линейка с тремя делениями является одновременно и оптимальной, что видно невооруженным глазом, но для большего количества делений объем вычислений, необходимых для проверки оптимальности, резко возрастает. 8 мая прошлого года был завершен проект OGR-21, не приведший, однако, к обнаружению новой линейки, но доказавший оптимальность ранее найденной, сейчас в процессе OGR-22, на подходе - OGR-23 и OGR-24, и уже эти проекты стартуют скорее всего при участии distributed.net.

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

Ближайший конкурент distributed.net в конкурсе CSC - проект DCypher.Net. Принцип работы все тот же, также есть команды (многие даже с теми же организаторами, что и у dnet). Отличий два. Во-первых, основатель DCypher утверждает, что обеспечивает в среднем двукратную производительность по сравнению с клиентом от distributed. Во-вторых, что немаловажно для участников, все десять тысяч евро получит победитель - достаточно сильный, хотя и вынужденный маркетинговый ход, явно нацеленный на перетягивание части народа из distributed.net. Что ж, через месяц-другой станет понятно, оправдались ли эти надежды.

Но гораздо более успешно с distributed.net по количеству участников конкурирует проект SETI@home, назначение которого, как видно из названия, - поиск внеземных цивилизаций. Я довольно скептически отношусь к самой идее проекта (несмотря на всю свою любовь к фантастике и вере в инопланетный разум), равно как и к уровню его реализации - первые версии клиентов были разработаны под крайне ограниченное количество платформ, да и работали только в качестве хранителей экранов, что резко уменьшало вычислительную мощность системы. В настоящее время, правда, разработаны уже консольные версии для Win32, Unix и других систем. Не очень удачно организованы команды - все они разбиты на группы, четыре из которых связаны с образовательными учреждениями, три с компаниями разного размера, и по одной с государственными агентствами и клубами. Классификация явно могла быть и поудачнее, с другой стороны, дает возможность командам типа Sydney Boys High School с 24 участниками быть на виду. Роль национального первенства явно отведена клубному разделу, российская команда занимает там скромное сороковое место.

Целиком и полностью коммерческим является проект Terra One. Он берется за решение различных задач, требующих больших вычислительных мощностей, и выплачивает своим участникам некие кредиты, которые можно отоварить в онлайновых магазинах наподобие Amazon.Com. Впрочем, не могу пока сказать, насколько это является выгодным.

На другом полюсе находится проект GIMPS - Great Internet Mersenne Prime Search. Марен Мерсенн, живший в конце XVI - начале XVII века, поддерживал переписку практически со всеми ведущими учеными своего времени и обеспечивал обмен научными идеями в эпоху становления основ современной математики. Известны его работы по музыкальной акустике, им была впервые измерена скорость звука, предложена одна из систем зеркальных телескопов, с его подачи Гюйгенс создал первые маятниковые часы, в списке его корреспондентов были Ферма, Паскаль, Гассенди, Декарт, Галилей, Торричелли. В математику Мерсенн вошел в первую очередь благодаря своей гипотезе о том, что числа вида 2^p-1, где p - простое число, также будут простыми. Гипотеза эта не подтвердилась, но среди чисел этого вида действительно много простых, и именно задаче поиска таких чисел и посвящен упомянутый проект.

Проект PiHex посвящен вычислению числа Пи с маниакальной точностью. В настоящее время вычисляется квадриллионный бит Пи, занимаются этим 583 человека.

Сайт http://supercomputer.i.am/ любопытен тем, что предлагаемый здесь клиент для распределенных вычислений реализован в качестве java-апплета, а это позволяет любому мало-мальски посещаемому сайту с легкостью заставить потрудиться во благо человечества своих посетителей. Здесь пока доступен всего лишь один проект по моделированию гамма-излучения от ядерного топлива, но в ближайшее время обещается объединить этот проект с DCypher.Net.

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

Таким образом, возможностей загрузить ваш процессор с чувством глубокого удовлетворения от осознания приобщенности к общему делу у вас масса. Могу сказать одно - это затягивает :)

Дополнительные ссылки:

• PVM (Parallel Virtual Machine)
• MPI (Message Passing Interface)
• MPI для начинающих
• Distributed.Net
• RC5 HackZone Team
• DCypher.Net
• Оптимальные линейки Голомба
• SETI@home
• Terra One - коммерческий проект
• GIMPS - Great Internet Mersenne Prime Search
• Моделирование климатических условий в XXI веке
• Моделирование гамма-излучения от ядерного топлива
• Вычисление Пи с повышенной точностью
• Поиск минимальных решений относительно n уравнения вида a₁^k+a₂^k+...+ a_m^k= b₁^k+b₂^k+ ... + b_n^k
• Поиск простых чисел, идущих подряд (точнее, отличающихся на 2, поскольку четные числа, большие 2, простыми не бывают по определению)
• Поиск простых чисел, описанных в теореме Прота.