Распределённые вычисления: краткое введение в проекты BOINC. Распределённые вычисления

Возможные полезные результаты использования параллельных вычислений:

1) Повышение скорости счёта, т. е., проделывание того же объёма работы за меньшее время (интересно, в первую очередь, для задач, имеющих ограничения по времени).

2) Повышение пропускной способности, т. е., проделывание большего объёма работы за то же время (интересно, в первую очередь, для задач, содержащих большие объёмы данных).

3) Повышение мощности, т. е., решение задач большего объёма (интересно, в первую очередь, для задач, модели в которых недостаточно подробны).

Указанные полезные результаты могут быть недостижимы одновременно , с использованием одного и того же набора методов и технологий.

Понятие параллельности вычислений в первую очередь означает их одновременность, т.е., одновременное использование для их проведения различных вычислительных устройств (процессоров, ядер и др.). Сама же одновременность исполнения может использоваться различными способами. Так, например, 1) одинаковое вычисление может одновременно производиться с частями одного набора данных по отдельности (например, задачи метеорологии, распределённые сети в задачах транспорта, вообще распределённые системы управления ); 2) различные вычисления могут одновременно производиться с одним набором данных (например, задача многих тел в молекулярной динамике или в астрофизике); 3) различные вычисления могут образовывать конвейер (pipeline), где каждый вычислитель получает данные частями, обрабатывает их и передаёт следующему вычислителю (например, внутренняя реализация операций над вещественными числами в процессорах).

Для того, чтобы вычисления вообще могли исполняться параллельно/распределённо, требуется их перевод в форму, пригодную для такого исполнения – параллелизация . Выбор конкретной модели параллелизации зависит от характера имеющейся задачи; скалярные вычисления , отдельные части которых необходимо исполняются взаимно последовательно, параллелизации не поддаются.

История

В 1973 году Джон Шох и Джон Хапп из калифорнийского научно-исследовательского центра Xerox PARC написали программу, которая по ночам запускалась в локальную сеть PARC и заставляла работающие компьютеры выполнять вычисления .

В 1978 году советский математик Виктор Глушков работал над проблемой макроконвейерных распределённых вычислений. Он предложил ряд принципов распределения работы между процессорами .Шаблон:R/ref На базе этих принципов им была разработана ЭВМ ЕС-2701 .

В январе 1996 года стартовал проект GIMPS по поиску простых чисел Мерсенна , также используя компьютеры простых пользователей как добровольную вычислительную сеть.

28 января 1997 года стартовал конкурс RSA Data Security на решение задачи взлома методом простого перебора 56-битного ключа шифрования информации RC5 . Благодаря хорошей технической и организационной подготовке проект, организованный некоммерческим сообществом distributed.net , быстро получил широкую известность .

17 мая 1999 года стартовал SETI@home на базе Grid , а в начале 2002 года завершилась разработка Калифорнийского Университета в Беркли открытой платформы BOINC (Berkeley Open Infrastructure for Network Computing), разрабатываемой с апреля 2000 года первоначально для SETI@Home , но первым на платформе BOINC стал проект Predictor@home запущенный 9 июня 2004 года.

Управление вычислительными заданиями

Проблема распределения различных вычислительных задач в рамках распределенной системы относится к проблеме принятия решений в условиях неопределённости . Данная проблема рассматривается в теории принятия решений и в теории неопределённости .

Распределённые операционные системы

Распределённая ОС, динамически и автоматически распределяя работы по различным машинам системы для обработки, заставляет набор сетевых машин обрабатывать информацию параллельно. Пользователь распределённой ОС, вообще говоря, не имеет сведений о том, на какой машине выполняется его работа.

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

В результате сетевая ОС может рассматриваться как набор операционных систем отдельных компьютеров, составляющих сеть. На разных компьютерах сети могут выполняться одинаковые или разные ОС. Например, на всех компьютерах сети может работать одна и та же ОС UNIX . Более реалистичным вариантом является сеть, в которой работают разные ОС, например, часть компьютеров работает под управлением UNIX, часть - под управлением NetWare, а остальные - под управлением Windows NT и Windows 98 . Все эти операционные системы функционируют независимо друг от друга в том смысле, что каждая из них принимает независимые решения о создании и завершении своих собственных процессов и управлении локальными ресурсами. Но в любом случае операционные системы компьютеров, работающих в сети, должны включать взаимно согласованный набор коммуникационных протоколов для организации взаимодействия процессов, выполняющихся на разных компьютерах сети, и разделения ресурсов этих компьютеров между пользователями сети.

Если операционная система отдельного компьютера позволяет ему работать в сети, и может предоставлять свои ресурсы в общее пользование и/или использовать ресурсы других компьютеров сети, то такая операционная система отдельного компьютера также называется сетевой ОС.

Таким образом, термин «сетевая операционная система» используется в двух значениях: как совокупность ОС всех компьютеров сети и как операционная система отдельного компьютера, способного работать в сети. Из этого определения следует, что такие операционные системы, как, например, Windows NT, NetWare, Solaris, HP-UX, являются сетевыми, поскольку все они обладают средствами, которые позволяют их пользователям работать в сети.

Ссылки и примечания

В статье использованы материалы из Википедии .

Открытая литература

Parallel and distributed computation: numerical methods / D.P. Bertsekas, J.N. Tsitsiklis. – Prentice-Hall, 1989 ; Athena Scientific, 1997. – Режим доступа: .]

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

Благодаря совместным усилиям обычных пользователей удалось сделать множество значимых открытий. Только за последние три года они отыскали 53 пульсара, причём последние семь нашлись совсем недавно – в конце августа 2012 г. Результаты выполненных исследований используются при разработке лекарственных препаратов для лечения сахарного диабета второго типа, болезней Альцгеймера и Паркинсона, других тяжёлых заболеваний. По материалам выполненных работ опубликованы сотни научных статей.

Суперкомпьютеры и распределённые сети

Мощные суперкомпьютеры – это капля в море. Машин, которые представляют собой предмет гордости целых стран и занимают первые строчки рейтинга TOP 500, не так уж много, и на всех их не хватает. Чтобы получить доступ к суперкомпьютеру, требуется сначала обосновать необходимость выбранной задачи, а потом, если доводы оказались убедительными, дождаться очереди и успеть оптимизировать код для выполнения на своеобразной суперкомпьютерной архитектуре.

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

История [ | ]

Работы по распределённым вычислениям с весьма прикладной целью - для военных нужд, а именно автоматизации процессов секретной связи и обработки разведывательной информации, велись интенсивно в США с 1960-х гг. Разработкой технологий распределённых вычислений и созданием распределённых информационных систем в Соединённых Штатах по заказу Агентства по перспективным оборонным научно-исследовательским разработкам США , видов вооружённых сил и служб (агентств) в структуре Министерства обороны США занимались исследовательские подразделения компаний и университетов:

В 1978 году советский математик Виктор Глушков работал над проблемой макроконвейерных распределённых вычислений. Он предложил ряд принципов распределения работы между процессорами . :320 На базе этих принципов им была разработана ЭВМ ЕС-2701 .

Распределённые операционные системы [ | ]

См. также [ | ]

Примечания [ | ]

"Ну и что, что у меня Crysis не запускается", — с бесхитростной простотой признался мой друг Владимир, — "зато в 1974 году мой компьютер смог бы управлять эскадрой военных спутников!"

Я не стал возражать, мощность современных компьютеров доставляет удовольствие только производителям компьютерных игр и создателям монстроподобных операционных систем. 9 пользователей из 10 загружают процессор процентов на 40 в день. Всё остальное время – бессмысленное взбалтывания кулерами воздуха пока четырёхгигарцевый образец человеческого гения играет роль медиацентра.

Те, кого мучает совесть за нерациональное использование мощностей, организовали на нашей планете нечто вроде клуба любителей 100 процентного КПД ПК. Хакер проект SETI, от рака и СПИДа, а также множество других гуманных и нравственных проектов, включая получение наибольшего простого числа.

Предположим, в инопланетян вы до первого литра не верите, а лекарства считаете противными истинной сути «матери-природы». Более того, вам плевать даже на новые делители для чисел Ферма. Но не теряйте надежду. В мире существуют десятки других распределённых проектов, некоторые из которых разработаны хакерами для хакеров (RainbowCrack), предлагают вам неплохо заработать (GIMPS), а то и вовсе несут угрозу частичного вымирания человечества (LHC@home). Выбрать из них – лишь дело вкуса и ваших личных предпочтений.

Распределенные вычисления кажутся скучными играми математиков. До тех пор, пока кто-то не начинает считать на вашем компьютере модель локальной ядерной войны в странах третьего мира. Или разрабатывать новое бактериологическое оружие под видом лекарства от рака. Есть и очень популярные проекты, которые прямым текстом кричат «мы опасны!», но за общими словами создателей «ах, как это полезно и вы совсем ничего не теряете», трудно разглядеть истинные цели исследований. Знать заранее – и быть готовым к последствиям – ваша прямая обязанность. Иначе есть большой шанс, что миллионы леммингов сдвинут колесо истории в пропасть.

Climate Prediction

Проект, который пытается разбить на тысячу хрустящих осколков основы теории хаоса и предсказать погоду на 50 лет вперёд. Основываются предсказания не на «новых революционных методах прогнозирования, с использование суперкомпьютеров и магии индейских шаманов», а на самых что ни на есть старых теориях и схемах. То есть тем самым образом, каким погоду предсказывают и сейчас. Таким образом проект ставит перед собой 2 цели: во-первых, установить какова точность и эффективность используемых сейчас методик; во-вторых, если методики эффективны, предсказать погоду на наибольший период.

Участникам, как водится, придётся скачать программу, моделирующую различные погодные условия на Земле . Среди полученных результатов сначала отберут те, которые наиболее соответствуют результатам в прошлом, до 2000 года, и уже на их основе выстроят модель изменения климата в будущем.

Требования: во время работы программа занимает около 50 Мегабайт памяти, для сохранения данных потребуется 500 Мб на жёстком диске. В качестве бонуса отмечу интерактивность работы – вы сможете увидеть трёхмерную модель Земли и отследить своими глазами изменения в климате.

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

LHC@home

Если вы торопитесь приблизить конец света на Земле – этот проект для вас. Проект занимается моделированием процессов, которые будут происходить в строящемся сейчас в Швейцарии LHC (Large Hadron Collider ) — самом большом в мире ускорителе частиц . В ускорителе длиной около 27 километров планируют столкнуть два протона для того, чтобы экспериментально доказать существование некого бозона Хиггса. Некоторые специалисты и представители общественности высказывают опасения, что имеется отличная от нуля вероятность выхода проводимых в коллайдере экспериментов из-под контроля и развития цепной
реакции, которая при определённых условиях теоретически может уничтожить всю планету. Точка зрения сторонников катастрофических сценариев связанных с работой LHC изложена на сайте http://www.risk-evaluation-forum.org/anon1.htm .

Считаете, что за дело аннигиляции всей вселенной можно и умереть – тогда присоединяйтесь. Дело в том, что от LHC ежегодно планируют получать до 15 петабайт данных. Уже сейчас вы можете помочь начать обрабатывать эти данные скачав программу SixTrack , которая моделирует движущиеся по кольцу в LHC частицы для изучения стабильности их орбит. Результаты выполнения программы SixTrack очень важны, от них зависит как будет работать крупнейший в мире научный проект, деятельность которого может совершить революцию в физике или отправить нашу галактику в антипространство.

Требования: несущественны.

Результат: доказательства некоторых научных теорий; низкоуровневый распад вселенной.

Muon1 Distributed Particle Accelerator Design

При маловероятном раскладе успешного испытания LHC , человечество непременно погубит Muon1 . К 2015 году планируется соорудить первую в мире The Neutrino Factory – лабораторию генерации частиц нейтрино . Нейтрино – самая распространённая частица во вселенной. Проникает практически через любые объекты без существенного снижения скорости. Известно, что через тело человека ежесекундно проскакивают 10 14 нейтрино. Понимание природы нейтрино даст человечеству ключ к разгадке истории возникновения всей вселенной.

Для генерации нейтрино планируется использовать мюонный колайдер — ускоритель, благодаря которому можно будет достичь самых высоких энергий столкновения частиц, когда-либо осуществлённых человеком. По сравнению с ним LHC – игрушка для детсадовца. Будет ли эффективна Muon1 и какие вообще результаты следует ожидать от нового колайдера решит ваш компьютер, если присоединится к проекту. Какими конкретно расчётами занимается клиентская программа понятно только специалисту в области квантовой физики. Однако не сомневайтесь – результаты очень важны.

Требования: Pentium III-500 c 64 МБ памяти.

Результат: возможно именно вы дадите толчок к финансированию одного из самых амбициозных проектов в истории человечества.

RainbowCrack

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

Сейчас в проекте создано сотни гигабайт всех возможных паролей, которые позволяют с вероятностью порядка 99% найти за несколько минут обратное преобразование из хэша в любой пароль длиной до 7 символов (не только из букв, но также цифр и многих спец-символов), зашифрованных по алгоритмам LanMan (авторизация в Windows), NT LanMan (авторизация в Windows NT, в том числе сетевых доменах), MD2 , MD4 , MD5 , SHA1 , RIPEMD-160 , Cisco PIX (большинство маршрутизаторов), MySQL 3.23 , MySQL SHA1 .

Всем участникам проекта предоставляется возможность уже сейчас пользоваться полученной системой расшифровки паролей в виде онлайн-сервиса — частота использования сервиса одним участником неограниченна, но ограничено время действия каждого аккаунта. Для продления времени доступа участникам предлагается рассчитывать новые таблицы, увеличивающие количество поддерживаемых алгоритмов и комбинаций паролей. Обычно на расчёт таблицы уходит от нескольких дней до недели процессорного времени (2 ГГц) — за каждую таблицу время доступа продляется на 2 недели.

Требования: 640 Мегабайт на жёстком диске, исходящий трафик – около 3 Гигабайт в месяц. Почти не требует входящего трафика, процессорного времени или специфической оси.

Результат: редкий случай, когда работаете вы, скорее всего, на себя и результат используете в деле.

15 января 2013 в 10:55

Эх, ухнем! Распределенные вычисления вчера и сегодня

Блог компании Intel ,
Высокая производительность

Принцип параллельного проведения расчетов – один из тех, что буквально «витают в воздухе». И это естественно, ведь любую работу удобней выполнять сообща. Параллельные вычисления появились задолго до первой ЭВМ, однако идея расцвела именно в компьютерную эпоху, ведь именно тогда появились и задачи, требующие большой вычислительной мощности, и устройства, готовые «всем миром» эту мощность предоставить. В эти дни исполняется ровно 15 лет с моего первого знакомства с проектами распределенных вычислений – хороший повод, чтобы написать об их истории и сегодняшнем дне.

Краткое теоретическое предисловие

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

Раздача «сырых» кусочков клиентам и прием от них результатов обработки;
Контроль потерянных и неверно посчитанных фрагментов;
Интерпретация полученных кусочков в свете общей цели;
Подсчет и визуализация статистики.

Итак, программа, установленная на клиенте, получает кусочек задания, выполняет его и отсылает результат в центр. В первых проектах блоки пересылались вручную, по e-mail, потом транспортная функция была полностью автоматизирована, было бы подключение к интернету (что в конце 90-х, впрочем, не звучало так банально, как сейчас). По большому счету, из всех компонентов компьютера программа использует только процессор, так сказать, «подчищая» его незадействованный ресурс. Приложение-клиент работает с низким приоритетом, не мешая остальным, однако, есть, конечно, у стопроцентной утилизации и отрицательные стороны: прежде всего, повышенное энергопотребление и тепловыделение ПК.
Несмотря на кажущуюся простоту, создать систему распределенных вычислений до появления типовых решений было задачей нетривиальной – ведь надо было как минимум написать клиенты под несколько операционных систем и управляющий сервер, да так, чтобы это все вместе еще и работало. Некоторые проекты так и не смогли преодолеть «детские болезни» и не достигли своих целей. Однако существовали и вполне успешные – один из таких и затянул меня на без малого 5 лет.

Эпоха distributed.net

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

Проект, в который мы вошли, назывался Bovine RC5 . Как следует из названия, его идея – атака с помощью «грубой силы» (простого перебора вариантов) на алгоритм шифрования RC5. Первый ключ был 40-битным – его «расковыряли» за три с небольшим часа. 48-битный продержался 13 дней, 56-битный – 265 дней. На момент нашего подключения проект находился в 64-битной фазе, она продолжалась почти 5 лет.
Bovine RC5 быстро набрал популярность. Организаторы проекта, сообщество distributed.net , сумели правильно определить главную движущую силу процесса – азарт участников. Движуха приобрела глобальный масштаб: команда соревновалась с командой, страна – со страной. «Догнать и перегнать» стала практически смыслом жизни для сотен тысяч человек, а для русских, как водится, еще и чем-то вроде национальной идеи. Каждое утро начиналось для нас с просмотра командной и глобальной статистики, клиент RC5 ставился на любой компьютер, который попадал к нам в руки. Дошли до того, что запускали «коровок» на чужих серверах, до которых была удаленка – до первого конфликта.

Интерфейс клиента distributed.net почти не изменился за время существования проекта

После завершения 64-битной фазы интерес к проекту стал угасать, прежде всего потому, что следующая, 72-битная, обещала быть очень долгой. Предчувствия нас не обманули: она продолжается уже более 10 лет, за это время проверено лишь чуть более 2,5% пространства ключей. Скорее всего, до 80-битного ключа дело уже не дойдет, хотя вычислительная мощность компьютеров за время проекта и возросла многократно. Что ни говори, а предполагаемая продолжительность этапа в 400 лет определенно пугает.

Считаем линейки и ищем инопланетян

Bovine RC5 можно отнести скорее к спортивным соревнованиям, нежели к способу решения каких-то реальных вычислительных задач, тем более что затеявшая его RSA сама впоследствии от него открестилась. Есть, впрочем, у distributed.net и более ценный для науки проект: расчет оптимальных линеек Голомба , однако с каждой новой единицей длины линейки он также скрипит все больше.

Естественно, сообществом distributed.net организаторы проектов добровольных распределенных вычислений не исчерпываются. Напротив, в мире сейчас насчитывается не менее сотни активных проектов, некоторые из которых также имеют богатую историю: так, с 1996 года идет поиск простых чисел Мерсенна , а в 1999 году начался проект SETI@home , где на основе расшифровки данных радиотелескопов SETI изучается вопрос, есть ли жизнь на Марсе во Вселенной. Всего же, как уже говорилось, вариантов буквально «несть числа»: тут и поиск лекарств от самых страшных болезней, и совершенствование Большого Адронного Коллайдера, и изучение трехмерной структуры белка, и решение многочисленных математических проблем и гипотез… вам предоставляется огромный выбор, в каком проекте участвовать, и можно утверждать на 100%: для процессора своего ПК вы нагрузку обязательно найдете – к вящему удовольствию обоих. Не забывайте только следить за температурой.

Клиент BOINC выгодно отличается от всех прочих наличием дизайна

Важным событием в жизни «распределенного» сообщества стало появление в 2005 году платформы BOINC (Berkeley Open Infrastructure for Network Computing) производства краснознаменного Калифорнийского университета в Беркли, как у них водится – с открытым исходным кодом. BOINC представляет собой готовую обвязку (типовые серверные компоненты + клиент) для проектов по сетевым вычислениям, которая значительно облегчает их запуск, хотя и не избавляет полностью от умственного труда, поскольку ряд серверных модулей необходимо готовить под конкретную задачу. Зато клиент, можно сказать, готов почти полностью, отлаженный и красивый. Более того, он позволяет участвовать сразу в нескольких BOINC-совместимых проектах. Получается эдакая связка разнородных, но объединенных технологически задач, что идет на пользу и самим задачам, и идеологии в целом.

Закончить хотелось бы опять на лирической ноте. Возможно, распределенные вычисления – это не самый оптимальный способ потратить имеющиеся у вас процессорные мощности. Но, если подумать, другие способы ведь еще менее оптимальны? Зато почувствовать себя членом команды – более легкого пути, пожалуй, нет. Моя «карьера» в этой области закончилась в 2004 – почти 9 лет назад. И вот сюрприз: сейчас, когда писал этот пост, зашел в статистику своей команды – представляете, она до сих пор жива и по-прежнему занимает первое место в нашем регионе. Не перевелись еще на Руси увлеченные люди!
Я приглашаю всех, кто когда-либо участвовал в проектах по распределенным вычислениям, откликнуться и дополнить мой рассказ – может быть, я чего-то пропустил?

Теги:

распределённые вычисления
distributed.net

Добавить метки