Что такое распределенные вычисления
Распределённые вычисления: краткое введение в проекты BOINC
Здесь многие слышали о программе распределённых вычислений BOINC, возможно, многие даже принимают в нём участие. Эта статья рассчитана в первую очередь на тех, кто не слышал об этом проекте, но, может быть, заинтересуется им. Здесь я приведу краткие описания самых популярных проектов.
BOINC — программный комплекс для быстрой организации распределённых вычислений. Состоит из серверной и клиентской частей. Первоначально разрабатывался для крупнейшего проекта добровольных вычислений — SETI@home, но впоследствии разработчики из Калифорнийского университета в Беркли сделали платформу доступной для сторонних проектов. На сегодняшний день BOINC является универсальной платформой для проектов в области математики, молекулярной биологии, медицины, астрофизики и климатологии. BOINC даёт исследователям возможность задействовать огромные вычислительные мощности персональных компьютеров со всего мира¹.
Суть заключается в том, что эта программа позволяет различным исследовательским, учебным заведениям или просто энтузиастам науки найти помощь у людей, которые готовы поделиться с ними процессорным временем. Задача, требующая значительной вычислительной мощности, разбивается на более простые части и рассылается различным людям, если решение является верным для своей части – сервер проекта начисляет определённое количество баллов участнику.
Многие участники организуются в команды и устраивают соревнования между собой в различных проектах.
Кратко изобразить этот процесс можно так:
В данный момент в сети BOINC насчитывается около 300 тысяч активных участников, что в сумме даёт более 9 миллионов компьютеров и производительность более 8 петафлопс (на момент написания статьи).
Список проектов
Здесь можно посмотреть статистику по всем активным проектам.
SETI@home
SETI (Поиск Внеземного Разума (Search for Extraterrestrial Intelligence)) — область науки, чьей целью ставится нахождение разумной внеземной жизни. Один из методов, известный как «радио SETI», заключается в использовании радиотелескопов для приёма узкополосных сигналов из космоса. Сигналы, не характерные для естественных явлений, будут служить доказательством использования внеземных технологий.
Раньше проекты ПВР использовали специальные суперкомпьютеры, расположенные у телескопа для анализа поступающей информации. В 1995 году, Дэвид Геди предложил использовать большое количество домашних компьютеров, подключённых к сети Интернет как виртуальный суперкомпьютер для анализа радиосигналов. Для изучения этой идеи он организовал проект SETI@home. Проект SETI@home был запущенн в мае 1999 года.
Rosetta@home
Проект Rosetta@home направлен на вычисление трёхмерной структуры белков. Подобные исследования могут привести к созданию лекарств от таких заболеваний как ВИЧ, малярия, рак и болезнь Альцгеймера.
Более подробную информацию по целям и методам этого проекта можно найти здесь.
WorldCommunityGrid
Этот проект был запущен корпорацией IBM с целью производить расчёт в различных областях науки: расшифровка генома человека, разработка лекарства от вируса эбола, картирование химических маркеров различных типов рака, а также исследования в области возобновляемых источников энергии.
Einstein@Home
Einstein@Home направлен на определение местонахождения пульсаров, используя данные Лазерно-интерферометрической гравитационно-волновой обсерватории (LIGO), радиотелескопа Аресибо, космического гамма-телескопа Ферми (GLAST).
Сигнал, доказавший существование гравитационных волн был слишком коротким для обработки проектом, однако теперь производится подготовка данных для нового поиска продолжительных гравитационных волн по всему небу.
Climate Prediction
Проект просчитывает различные симуляции климатических моделей, что позволяет спрогнозировать, как изменится погода на Земле в будущем.
Malaria Control
Проект использует ресурсы компьютеров для стохастического моделирования эпидемиологии и естественной истории малярии вызываемой Plasmodium falciparum.
MilkyWay@Home
Проект направлен на создание высокоточных трёхмерных моделей Потока Стрельца, что даёт информацию о том, как сформировался Млечный Путь и как образуются приливные рукава во время столкновения галактик.
LHC@Home
Подпроект SixTrack, созданный для помощи учёным улучшения работы БАК, просчитывает различные траектории 60 частиц, при которых луч сохранит стабильность в ускорителе. Количество циклов от 100000 до миллиона циклов, что соответствует менее 10 секундам реального времени. Этого достаточно, чтобы проверить будет ли пучок сохранять траекторию на протяжении гораздо большего времени или существует риск потери стабильности пучка, что может привести к серьёзным проблемам в реальности, например, к остановки ускорителя или к выходу из строя некоторых детекторов.
PrimeGrid
Проект направлен на поиск простых чисел специального вида. Полный список подпроектов можно найти на официальном сайте.
Asteroids@home
Проект ставит целью увеличить объём информации о физических характеристиках астероидов. Программа обрабатывает данные фотометрических наблюдений разными приборами за разное время. Эта информация преобразуется методом инверсии кривой блеска, что позволяет создать 3D-модель формы астероида вместе с определением периода и направлением вращения вокруг своей оси.
Поскольку данные фотометрических наблюдений обычно растянуты во времени, период вращения не «виден» напрямую. Большой объём параметров должен быть проверен для определения оптимального решения. В подобных случаях инверсия кривой блеска занимает слишком много времени и распределённые вычисления – единственный выход эффективно разобраться с фотометрией сотен и тысяч астероидов. Кроме того, для обнаружения ошибок в методе и реконструировать подлинные физические параметры астероидов, необходимо обработать большой объём данных о «синтетических» объектах.
Изучение формы и других параметров астероидов позволит больше узнать об их реальных размерах, представляют ли они реальную угрозу, а в дальнейшем поможет определить подходящие цели для исследовательских миссий.
Cosmology@Home
Проект направлен на поиски модели лучшим образом описывающую нашу Вселенную, и найти какая группа моделей подтверждает текущие данные, полученные теоретическими космологическими исследованиями и практическими физическими наблюдениями.
Yoyo@home
Проект состоит из пяти подпроектов, каждый из которых является проектом по поиску решения различных теоретических вопросов: от поиска нечётных странных чисел до проекта по моделированию работы мюонного коллайдера.
POEM@Home
Проект направлен на моделирование сворачивания белков, что в дальнейшем поможет точнее определять функцию белков по их структуре. Такие знания могут помочь в медицинских исследованиях.
theSkyNet POGS
Это астрономический исследовательский проект обработки данных с различных телескопов мира в разных диапазонах электромагнитного спектра. Проект объединяет GALEX, Pan-STARRS1 и WISE, чтобы создать многочастотный (ультрафиолетовый-оптический-инфракрасный спектры) атлас ближних к нам окрестностей Вселенной. Проект определяет физические параметры (звездная масса галактик, поглощение излучения пылью, масса пылевой компоненты, скорость образования звезд) для каждого пиксела, используя технику поиска оптимума для распределения спектральной энергии.
GPUGRID
Молекулярные симуляции, выполняемые проектом – одни из самых частых при работе учёных, но они также одни из самых ресурсоёмких, поэтому для их просчёта обычно используется суперкомпьютер. Как и в других биологических проектах BOINC, GPUGRID использует ресурсы компьютера для симуляции белков для лучшего понимания их структуры и разработки лекарств от различных болезней.
Распределенные вычисления
Распределённые вычисле́ния (distributed computing, grid computing, volunteer computing) — способ решения трудоёмких вычислительных задач с использованием двух и более компьютеров, объединённых в сеть.
Распределённые вычисления являются частным случаем параллельных вычислений, то есть одновременного решения различных частей одной вычислительной задачи несколькими процессорами одного или нескольких компьютеров. Поэтому необходимо, чтобы решаемая задача была сегментирована, то есть разделена на подзадачи, которые могут вычисляться параллельно. При этом для распределенных вычислений приходится также учитывать возможное различие в вычислительных ресурсах, которые будут доступны для расчёта различных подзадач. Более того, не всякую задачу можно разделить на подзадачи, которые можно решать параллельно.
Содержание
История
В последнее время в качестве исполнителей выступают компьютеры, связанные посредством той или иной среды передачи данных, однако в прошлом для этого использовались и люди. Например, решение для модели атомной бомбы в США было получено коллективом учёных, которые пользовались вычислительными машинами.
С появлением и бурным развитием интернета всё большую популярность стала получать идея добровольного использования для распределённых вычислений компьютеров простых пользователей, соединённых через интернет.
Такой проект распределённых вычислений в интернете, как SETI@Home и Folding@Home обладает не меньшей вычислительной мощностью, чем самые современные суперкомпьютеры. Проект отмечен в Книге рекордов Гиннеса, как самое большое вычисление.
На сегодняшний день для упрощения процесса организации и управления распределёнными вычислениями создано несколько программных комплексов, как коммерческих, так и абсолютно бесплатных (см. ссылки).
Участие в проектах распределенных вычислений
Общая схема участия
Общая схема участия в том или ином проекте распределённых вычислений выглядит так: потенциальный участник скачивает клиентскую часть программного обеспечения под свою операционную систему, настраивает и запускает её. Клиент периодически общается с сервером проекта — запрашивает у него данные на обработку и отсылает результаты. При этом клиент выполняется с наименьшим приоритетом (приоритетом простоя (англ.)) и не мешает основной работе.
Привлечение и мотивация участников
Существует несколько методов привлечения участников в проекты распределённых вычислений. Прежде всего это реклама, в том числе на вебсайтах по смежной проекту тематике. Почти каждый проект старается заинтересовать потенциальных участников описанием важности решаемой задачи и последующего применения результатов её решения в реальной жизни. Здесь, безусловно, большую выгоду могут извлечь проекты, у которых такие приложения есть (например, поиск лекарств и другие биомедицинские проекты).
Многие проекты создают среду для соревнования участников по объёму проделанных вычислений, как в личном, так и в командном зачёте. Вероятно, стимулом для участия в таких проектах является возможность «похвастаться» перед другими участниками доступными вычислительными ресурсами. Немаловажным фактором здесь является наличие подробной и красиво оформленной статистики о проделанной участниками работе, таблиц рейтингов, форумов для обсуждения проекта и т.п. — все это образует социальную сеть для общения участников в среде единомышленников. При этом собственно цель вычислений проекта для многих из них уходит на второй план и становится не так важна, как, например, детали оформления сайта и клиентского программного обеспечения. Успешность такого подхода доказывает существование множества сайтов команд-участниц того или иного проекта (см. ссылки), которые добровольно и самостоятельно рекламируют выбранный проект и привлекают новых участников.
Некоторые проекты распределённых вычислений так или иначе финансируются и предлагают своим участникам денежное вознаграждение при достижении определённых результатов. В частности, проекты, занимающиеся поиском редких объектов (например, чисел специального вида), могут награждать конкретных участников, нашедших на своём компьютере очередной объект поиска. Такие проекты можно рассматривать как лотерею, в которой участники платят своими компьютерными ресурсами, вычисляя что-то полезное (или бесполезное), и имеют шанс выиграть приз. При этом шанс на успех прямо пропорционален вложенным мощностям — как и в лотерее: чем больше покупаешь лотерейных билетов, тем больше вероятность выигрыша.
Несмотря на то, что большинство проектов распределенных вычислений основываются на добровольном участии пользователей ПК, у рядового пользователя существует потенциальная возможность стать невольным участником того или иного проекта, клиентское ПО которого может быть установлено компьютерным вирусом. При современном уровне развития информационных технологий и сетей передачи данных такая клиентская программа на вирусной основе, не наносящая вреда информации, но занимающая вычислительную мощность компьютера, может долгое время оставаться необнаруженной.
Критика проектов распределенных вычислений
Организаторами распределённых вычислений изначально заявляется безвозмездность участия всех, кто присоединяется к их проектам, а так же то, что их результаты будут опубликованы, однако, существует возможность того, что:
Организации, участвующие в проектах распределенных вычислений
Список проектов распределённых вычислений
Биология и медицина
Математика и криптография
Естественные науки
Ссылки
Статьи о распределенных вычислениях
Командные сайты
ПО для организации распределённых вычислений
См. также
Проекты распределённых вычислений
Полезное
Смотреть что такое «Распределенные вычисления» в других словарях:
Стаб (распределенные вычисления) — Под cтабом в распределённых вычислениях понимается фрагмент программного кода, используемый для конвертации параметров, передаваемых при помощи удаленных вызовов процедур (RPC). Главная идея RPC заключается в предоставлении возможности локальному … Википедия
Добровольные вычисления — Участие в проекте добровольных вычислений с помощью клиента BOINC … Википедия
Распределительные вычисления — Распределённые вычисления (distributed computing, grid computing, volunteer computing) способ решения трудоёмких вычислительных задач с использованием двух и более компьютеров, объединённых в сеть. Распределённые вычисления являются частным… … Википедия
Параллельные вычисления — Не следует путать с Распределённые вычисления. Параллельные вычисления такой способ организации компьютерных вычислений, при котором программы разрабатываются как набор взаимодействующих вычислительных процессов, работающих параллельно… … Википедия
облачные вычисления — По сути под словом «облако» в ИТ понимается некое небольшое сообщество аппаратных ресурсов или интернет. «Облачные вычисления» позволяют осуществлять пользователям доступ к их данным без обязательного понимания ими того где… … Справочник технического переводчика
Распределённые вычисления — Не следует путать с Добровольные вычисления. См. также: Параллельные вычисления Распределённые вычисления способ решения трудоёмких вычислительных задач с использованием нескольких компьютеров, чаще всего объединённых в параллельную… … Википедия
Облачные вычисления — (англ. cloud computing), в информатике это модель обеспечения повсеместного и удобного сетевого доступа по требованию к общему пулу (англ. pool) конфигурируемых вычислительных ресурсов (например, сетям передачи данных,… … Википедия
SLinCA@Home — Тип Грид, распределенные вычисления, волонтёрские … Википедия
Список академических дисциплин — Эта статья содержит незавершённый перевод с иностранного языка. Вы можете помочь проекту, переведя её до конца. Если вы знаете, на каком языке написан фрагмент, укажите его в этом шаблоне … Википедия
Portable Batch System — (PBS, OpenPBS) Тип распределенные вычисления Разработчик MRJ Операционная система Unix подобная Языки интерфейса Английский Первый выпуск 90 е Аппаратная платформа … Википедия
Распределённые вычисления: немного теории
Девять лет назад я начал «в свободное от основной работы время» преподавать компьютерные дисциплины в одном из университетов Санкт-Петербурга. И только сравнительно недавно к своему удивлению обнаружил, что в наших вузах практически отсутствуют курсы с фокусом на проблематику распределённых вычислений. И даже на Хабре эта тема не раскрыта в достаточной мере! Надо прямо сейчас исправлять ситуацию.
Этой теме я и хотел посвятить статью или даже серию статей. Но потом решил выложить своё учебное пособие по основам распределённых вычислений, вышедшее в свет в этом году (читай, небольшую книгу объемом 155 страниц). В итоге получился гибрид – статья со ссылкой на книгу. Книга распространяется бесплатно и доступна в электронном виде.
Вместо пролога. Приступив к тексту статьи, я в очередной раз задумался, а зачем программисту нужно знать теоретические основы распределённых вычислений. Этот вопрос я неоднократно слышал (и продолжаю слышать) от студентов и специалистов, уже работающих в области ИТ. Действительно, зачем, например, знать, что «множество событий распределённого вычисления упорядочено частично, а не линейно»? В чем, так сказать, каждодневная практическая польза этого фундаментального знания?
Должен признать, что у меня нет готового заученного ответа, который я могу выдать не задумываясь. Поэтому каждый раз приходится напрягаться извилинами, и каждый раз ответы и аргументы получаются разными. Вот и сейчас всё как впервые…
Давайте попробуем начать издалека. И чтобы было нагляднее – с медицины. Потому как, если речь заходит о врачебных ошибках, мозг начинает активно работать и генерировать сильное возмущение: ужас, ужас, могли человека угробить. Что они там, совсем что ли? Неужели не знают, чего делают?
Все мы совершенно естественным образом рассчитываем на то, что перед тем как начать какие-либо манипуляции с человеческим организмом врачи всё-таки изучают его внутреннее устройство и принципы работы. Мы абсолютно не согласны с утверждением, что хирургам гораздо важнее пройти практические курсы кройки и шитья вместо многолетней зубрежки теоретического материала о том, что у нас там внутри и зачем оно там. Так почему же программистам, занимающимся разработкой системы с сетевым взаимодействием (т.е. к настоящему моменту практически любой системы), не нужно знать «что там внутри и зачем оно там»? Почему ошибки в ИТ воспринимаются максимум с легкой иронией? Ну да, ну баг. А кто не пьет не делает багов?! Назови! Нет, я жду! Среди требований к программистам очень часто почему-то на передний план выходят практические навыки владения тем или иным языком программирования. Причем сильно на передний план, полностью затмевая собой требования к пониманию основных концепций, теоретических моделей, алгоритмов, в конце концов… Да и сами программисты, чего греха таить, с началом разговора «про никому не нужную теорию» вянут как цветы в пустыне… Чудеса, не правда ли…
Приведу небольшое высказывание Л. Лэмпорта на эту тему (чуть ниже я постарался перевести это высказывание на русский язык, не сильно отдаляясь от оригинала):
For quite a while, I’ve been disturbed by the emphasis on language in computer science. One result of that emphasis is programmers who are C++ experts but can’t write programs that do what they’re supposed to. The typical computer science response is that programmers need to use the right programming / specification / development language instead of / in addition to C++. The typical industrial response is to provide the programmer with better debugging tools, on the theory that we can obtain good programs by putting a monkey at a keyboard and automatically finding the errors in its code.
I believe that the best way to get better programs is to teach programmers how to think better. Thinking is not the ability to manipulate language; it’s the ability to manipulate concepts. Computer science should be about concepts, not languages.
Уже довольно длительное время меня беспокоит слишком большое внимание, уделяемое компьютерному языку в ИТ. В результате переизбытка такого внимания появляются программисты, которые являются экспертами в С++, но которые не в состоянии написать программы, делающие то, что от этих программ требуется. Типичная реакция представителей ИТ на эту проблему заключается в предложении программистам использовать другой более подходящий язык (программирования, спецификаций и т.п.) вместо / вдобавок к С++. В свою очередь характерный для индустрии разработки ПО выход из ситуации видится в предоставлении программистам более совершенных инструментов отладки, видимо, основываясь на предположении, что получить хорошие программы можно просто посадив мартышку за клавиатуру и затем отыскивая и исправляя ошибки в её коде.
Моё твердое убеждение в том, что для получения качественных программ необходимо учить программистов думать лучше. Умение думать – это не способность оперировать компьютерным языком; это способность оперировать концепциями. Изучение информационных технологий должно быть сфокусировано на изучении концепций, а не языков.
Для иллюстрации того насколько могут быть важны «концепции» и «элементы теории» в вопросах построения распределённых систем давайте рассмотрим парочку простеньких примеров. Для начала — групповую рассылку сообщений электронной почты между пользователями A, B, C и Х. Предположим, что пользователь А отправляет всей группе письмо с темой «Общее собрание». Пользователи В и С отвечают на него всей группе своими сообщениями с темой «Re: Общее собрание».
Ага, оказывается порядок поступления сообщений, наблюдаемый различными процессами, может быть различным даже для FIFO каналов! А что делать, если мы хотим, чтобы наблюдаемый порядок был везде одинаков (и при этом не хотим использовать синхронный обмен сообщениями)? К примеру, если мы пишем свой транспорт с соответствующими гарантиями. Или хотим построить отказоустойчивую службу (replicated state machine), где каждая реплика должна обрабатывать поступающие запросы в едином для всех реплик порядке, чтобы состояния реплик не различались? Вопрос…
Рассмотрим теперь еще одно выполнение распределённой системы, в которой процессы взаимодействуют только с помощью обмена сообщениями, и каждый процесс занимается включением / выключением фонаря с определенным светом. Пусть первый процесс управляет фонарем с красным светом, второй – с желтым, а третий – с зеленым. Такая вот светофорная система. На рисунке ниже включение процессом своего фонаря обозначено прямоугольником, а выключение – вертикальной линией; отправка и получение сообщения – стрелкой. Вопрос: могут ли процессы определить, какие фонари светили одновременно?
Так вот оказывается, что в данном выполнении асинхронной системы процессы никак не смогут определить был ли включен красный свет одновременно с желтым. Может быть да. А может и нет… Сие останется неизвестным. Но зато будет точно известно, что красный и зеленый фонари одновременно находились во включенном состоянии. Другими словами, оказывается, нет особого смысла говорить о том, что то или иное глобальное состояние достигается по ходу выполнения распределённой системы! Равно как и очень часто нельзя сказать, выполнялось ли какое-либо условие (предикат), заданное на множестве его глобальных состояний! Опять же вопрос: почему?
Наш ответ Чемберлену. На самом деле ответы на эти и многие другие вопросы, связанные с работой асинхронных распределённых систем, крайне сложно уложить в рамки одной статьи. Поэтому я и решил опубликовать сразу несколько статей в одной. Точнее, как указано в начале статьи, представить свою небольшую книгу по основам распределённых вычислений, доступную в электронном виде.
Из этой книги вы узнаете:
В начале я постарался в двух словах изложить, какие цели ставились при написании книги, и как она соотносится с другой литературой. Этому посвящено введение к книге. Оно занимает всего чуть более двух страниц, поэтому прочитать его стоит.
Первый раздел по большей части болтологический и посвящен «качественным» особенностям распределённых систем. Если вы не знаете, что такое распределённая система, и какие к ней предъявляются требования, то первый раздел имеет смысл прочитать. Если же вы знаете, что поступающие процессу-получателю сообщения могут давать устаревшее представление о процессе-отправителе, точно так же, как и световое излучение, поступающее к нам от далекой звезды, дает представление о состоянии этой звезды в прошлом, то первые четыре пункта можно пропустить 🙂 Отдельно стоит отметить п. 1.5 «Взаимодействие в распределённых системах», в котором я попытался привести несколько простых задач, демонстрирующих сложности, с которыми можно столкнуться при разработке распределённых систем. Эти задачи мы будем потом решать, вооружившись теоретическими знаниями, поэтому стоит с ними ознакомиться.
Во втором разделе представлена модель распределённого вычисления и основная теория, используемая при дальнейшем изложении. В определенном смысле этот раздел является ключевым. Однако надо быть готовым к работе с такими терминами как «множество / подмножество», «бинарное отношение», «отношение эквивалентности», «отношение порядка», «линейный / частичный порядок». В этом разделе вы встретите доказательства некоторых утверждений. Мне кажется, что их следует, как минимум, проглядеть (а лучше изучить) для более глубокого понимания существенных особенностей функционирования распределённых систем, выделяющих их среди систем других классов.
На базе теории, представленной выше, в третьем разделе, наконец, рассматриваются более практичные вещи, а именно, различные механизмы логических часов. С их помощью мы можем упорядочивать события в одну или несколько последовательностей, которые могли бы происходить в системе, что позволяет значительно упростить разработку алгоритмов для распределённых систем. Приводятся примеры использования логических часов для решения задач, сформулированных в п. 1.5 «Взаимодействие в распределённых системах».
Четвертый раздел посвящен изучению основных распределённых алгоритмов взаимного исключения, построенных без применения привычных разделяемых переменных. Ключевые идеи этих алгоритмов используются и для решения многих других задач в распределённых системах. Кроме того, их изучение позволяет раскрыть такие важные вопросы, как обеспечение свойств безопасности и живучести распределённых алгоритмов. Поэтому этот раздел мне представляется весьма полезным для ознакомления.
На кого ориентирована эта книга?
Материал книги следует рассматривать в качестве введения в проблематику распределённых вычислений. Она выросла из академической вузовской среды, и будет, безусловно, полезна, если вы только начинаете работать в этой области. Если же у вас уже есть определённый опыт в разработке распределённых систем и алгоритмов, возможно, вы найдете для себя что-то новое и поделитесь своим мнением в комментариях. Если же вы имеете многолетний опыт за плечами и являетесь экспертом в этой теме, надеюсь, что вы сможете дополнить меня своими мыслями и соображениями.
Чего бы мне хотелось?
Буду рад, если материал книги окажется для вас полезным и познавательным — будет время вернуться сюда после её прочтения и черкнуть «спасибо», буду признателен. Кроме того, мне бы хотелось собрать весь материал по теме, включая комментарии, вопросы и ответы в одном месте, чтобы потом отсылать сюда всех желающих, включая новые курсы новых студентов. Если вы сможете помочь и дополнить материал своими мыслями, своим опытом, буду признателен вдвойне. Читайте, набирайтесь знаний и используйте их в своей работе! Скачать книгу в формате PDF прямо сейчас вы сможете по ссылке ниже:
Успехов!
Михаил Косяков
Вместо эпилога. «Информация, в отличие от ресурсов, задумана, чтобы ею делились». Роберт Кийосаки