Распределительный способ вычисления это

Распределительные вычисления

Распределённые вычисле́ния (distributed computing, grid computing, volunteer computing) — способ решения трудоёмких вычислительных задач с использованием двух и более компьютеров, объединённых в сеть.

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

Содержание

История

В последнее время в качестве исполнителей выступают компьютеры, связанные посредством той или иной среды передачи данных, однако в прошлом для этого использовались и люди. Например, решение для модели атомной бомбы в США было получено коллективом учёных, которые пользовались вычислительными машинами.

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

Такой проект распределённых вычислений в интернете, как SETI@Home и Folding@Home обладает не меньшей вычислительной мощностью, чем самые современные суперкомпьютеры. Проект отмечен в Книге рекордов Гиннеса, как самое большое вычисление.

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

Участие в проектах распределенных вычислений

Общая схема участия

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

Привлечение и мотивация участников

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

Многие проекты создают среду для соревнования участников по объёму проделанных вычислений, как в личном, так и в командном зачёте. Вероятно, стимулом для участия в таких проектах является возможность «похвастаться» перед другими участниками доступными вычислительными ресурсами. Немаловажным фактором здесь является наличие подробной и красиво оформленной статистики о проделанной участниками работе, таблиц рейтингов, форумов для обсуждения проекта и т.п. — все это образует социальную сеть для общения участников в среде единомышленников. При этом собственно цель вычислений проекта для многих из них уходит на второй план и становится не так важна, как, например, детали оформления сайта и клиентского программного обеспечения. Успешность такого подхода доказывает существование множества сайтов команд-участниц того или иного проекта (см. ссылки), которые добровольно и самостоятельно рекламируют выбранный проект и привлекают новых участников.

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

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

Критика проектов распределенных вычислений

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

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

Это может привести к ситуации, когда участники интернациональной команды своими усилиями укрепляют возможности страны-организатора проекта при получении результатов проекта производить политический, военный или экономический шантаж остального мира, как в случае с атомной бомбой.

Организации, участвующие в проектах распределенных вычислений

Список проектов распределённых вычислений

Ниже приведен список наиболее популярных проектов распределённых вычислений в интернете. Более полный список практически всех существующих и существовавших проектов распределённых вычислений в интернете доступен на сайте Distributed Computing (англ.) .

Биология и медицина

• Rosetta@home — вычисление структуры белка с самой низкой энергией.
• Folding@Home — проект по расчёту третичной структуры белков;
• World Community Grid — исследования, связанные с генетикой человека, а также с различными тяжёлыми заболеваниями. Изучение белков и их каталогизация.
• grid.org — проект по поиску лекарства от рака (завершен 27 апреля 2007 года (не нашли));
• Find-a-Drug — проект по поиску лекарств от различных болезней путём расчёта докинга белков с различными молекулами (завершен в 2005 году);

Математика и криптография

• Seventeen or Bust — проект, занимающийся решением задачи Серпинского;
• чисел Мерсенна;
• ZetaGrid — проверка гипотезы Римана. /Окончен/
• RC5 полным перебором, поиск оптимальных линеек Голомба;

Естественные науки

• SETI@Home — проект по обработке сигналов радиотелескопа, для поиска радиосигналов внеземных цивилизаций.
• Einstein@Home — проект по проверке гипотезы Эйнштейна о гравитационных волнах с помощью анализа гравитационных полей пульсаров или нейтронных звёзд.
• Climate Prediction — проект по моделированию влияния выбросов углекислого газа на климатЗемли.
• Spinhenge@home — проект в области нанотехнологий.
• LHC@home — расчёты для создания ускорителя заряженных частиц — Большого адронного коллайдера (LHC, ввод в эксплуатацию в 2009 году).
• Muon1 DPAD — расчёты по проектировке еще более мощного ускорителя — Neutrino Factory/Muon Collider.
• Enabling Grids for E-sciencE — информация о проекте EGEE.

Ссылки

• «Распределённые вычисления в Интернете» — поддержка массы проектов распределенных вычислений.
• Сравнение биомедицинских проектов распределенных вычислений
• русский Сайт о параллельных вычислениях
• Подборки материалов о GRID вычислениях. Полезные ссылки
• Премия Дейкстры за выдающиеся работы в области распределенных вычислений

Статьи о распределенных вычислениях

• Леонид Дурман «Гонки по вертикали. Числа Ферма от Эйлера до наших дней: начало, продолжение, окончание». Компьютерра, №№ 393-395, 2001. (альтернативная ссылка)
• boinc.ru: Кто организует распределённые вычисления и кто в них участвует, Распределённые вычисления,
• Операционная система Интернет-масштаба — перевод статьи основателя SETI@home о будущем распределённых вычислений
• Региональные grid-сети, Мир ПК, №08, 2005.
• Научные статьи по распределенным вычислениям

Командные сайты

ПО для организации распределённых вычислений

• LGPL.
• Condor (англ.)
• Globus Toolkit (англ.) — набор программ значительно упрощающий создание и управление распределёнными вычислениями.

См. также

Проекты распределённых вычислений Астрономические Einstein@Home • SETI@home • Orbit@home • Cosmology@home Биомедицинские CommunityTSC • eOn • evolution@home • FightAIDS@Home • Folding@home • Lattice Project • Malariacontrol • Predictor@home • Rosetta@home • Tanpaku • SIMAP@home • QMC@Home • United Devices Cancer Research Project Климатологические BBC Climate Change Experiment • Seasonal Attribution Project Математические 3x+1 • ABC@Home • Chess960@home • GIMPS • PrimeGrid • Rectilinear Crossing Number • Seventeen or Bust • SZTAKI Desktop Grid Физико-технические CuboidSimulation • LHC@home • Magnetism@home • µFluids@home • Muon1 DPAD • Spinhenge@home Прочие Africa@HOME • BURP • DIMES • HashClash • AQUA@home

Wikimedia Foundation . 2010 .

Полезное

Смотреть что такое «Распределительные вычисления» в других словарях:

система — 4.48 система (system): Комбинация взаимодействующих элементов, организованных для достижения одной или нескольких поставленных целей. Примечание 1 Система может рассматриваться как продукт или предоставляемые им услуги. Примечание 2 На практике… … Словарь-справочник терминов нормативно-технической документации

блок — 23.02.13 блок* [block]: Часть текста, определенная пользователем, с которой проводят операции обработки текста. Источник: ГОСТ Р ИСО/МЭК 2382 23 2004: Информационная технология. Словарь. Часть 23. Обработка текста … Словарь-справочник терминов нормативно-технической документации

ГОСТ Р МЭК 60204-1-2007: Безопасность машин. Электрооборудование машин и механизмов. Часть 1. Общие требования — Терминология ГОСТ Р МЭК 60204 1 2007: Безопасность машин. Электрооборудование машин и механизмов. Часть 1. Общие требования оригинал документа: TN систем питания Испытания по методу 1 в соответствии с 18.2.2 могут быть проведены для каждой цепи… … Словарь-справочник терминов нормативно-технической документации

метод — метод: Метод косвенного измерения влажности веществ, основанный на зависимости диэлектрической проницаемости этих веществ от их влажности. Источник: РМГ 75 2004: Государственная система обеспечения еди … Словарь-справочник терминов нормативно-технической документации

определение — 2.7 определение: Процесс выполнения серии операций, регламентированных в документе на метод испытаний, в результате выполнения которых получают единичное значение. Источник … Словарь-справочник терминов нормативно-технической документации

ОТОПЛЕНИЕ — ОТОПЛЕНИЕ, обогревание жилых и других помещений с целью поддержания в них определенной t°. О. должно иметь технически правильное устройство и удовлетворять ряду сан. требований. Основные сан. требования ко всяким системам О. следующие: 1)… … Большая медицинская энциклопедия

условия — (см. раздел 1) d) Может ли машина представлять опасности при создании или потреблении определенных материалов? Нет Источник: ГОСТ Р МЭК 60204 1 2007: Безопасность машин. Электрооборудование машин и механизмов. Часть 1. Общие требования … Словарь-справочник терминов нормативно-технической документации

Источник

Распределённые вычисления: немного теории

Девять лет назад я начал «в свободное от основной работы время» преподавать компьютерные дисциплины в одном из университетов Санкт-Петербурга. И только сравнительно недавно к своему удивлению обнаружил, что в наших вузах практически отсутствуют курсы с фокусом на проблематику распределённых вычислений. И даже на Хабре эта тема не раскрыта в достаточной мере! Надо прямо сейчас исправлять ситуацию.

Этой теме я и хотел посвятить статью или даже серию статей. Но потом решил выложить своё учебное пособие по основам распределённых вычислений, вышедшее в свет в этом году (читай, небольшую книгу объемом 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: Общее собрание».

В действительности события происходят в следующей последовательности:

1. Первым отправляется сообщение от пользователя А.
2. Пользователь В получает его, читает и отправляет ответ.
3. Пользователь С получает оба сообщения от А и В и затем отправляет свой ответ, опирающийся на оба сообщения от А и В.

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

1. Сообщение от пользователя С с темой «Re:Re: Общее собрание».
2. Сообщение от пользователя А с темой «Общее собрание».
3. Сообщение от пользователя В с темой «Re: Общее собрание».

Ага, оказывается порядок поступления сообщений, наблюдаемый различными процессами, может быть различным даже для FIFO каналов! А что делать, если мы хотим, чтобы наблюдаемый порядок был везде одинаков (и при этом не хотим использовать синхронный обмен сообщениями)? К примеру, если мы пишем свой транспорт с соответствующими гарантиями. Или хотим построить отказоустойчивую службу (replicated state machine), где каждая реплика должна обрабатывать поступающие запросы в едином для всех реплик порядке, чтобы состояния реплик не различались? Вопрос…

Рассмотрим теперь еще одно выполнение распределённой системы, в которой процессы взаимодействуют только с помощью обмена сообщениями, и каждый процесс занимается включением / выключением фонаря с определенным светом. Пусть первый процесс управляет фонарем с красным светом, второй – с желтым, а третий – с зеленым. Такая вот светофорная система. На рисунке ниже включение процессом своего фонаря обозначено прямоугольником, а выключение – вертикальной линией; отправка и получение сообщения – стрелкой. Вопрос: могут ли процессы определить, какие фонари светили одновременно?

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

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

Из этой книги вы узнаете:

• про причинно-следственный порядок событий распределённого вычисления
• что такое справедливость, безопасность и живучесть
• что такое конус прошлого и конус будущего для события вычисления
• чем логический параллелизм отличается от физического параллелизма
• почему не имеет особого смысла говорить о совокупности глобальных состояний вычисления, а имеет смысл говорить о совокупности событий вычисления
• как нам упорядочить события распределённого вычисления в одну или несколько последовательностей, которые «могли бы» происходить в системе
• что такое логические часы, и какое такое логическое время они отсчитывают
• почему логическое время останавливается, если в системе ничего не происходит
• чем скалярное время отличается от векторного
• как и для чего можно использовать логическое время в распределённых алгоритмах
• какие есть подходы к эффективной реализации векторных часов
• зачем нам может понадобиться матричное время
• чем распределённый алгоритм отличается от централизованного
• как решать задачу взаимного исключения без использования разделяемых переменных
• на какие категории делятся все распределённые алгоритмы взаимного исключения
• зачем в алгоритмах на основе получения разрешений используется логическое время
• почему философам так трудно пообедать в распределённой системе
• зачем нам граф конфликтов и граф предшествования
• почему граф предшествования должен меняться со временем
• почему в алгоритмах на основе передачи маркера есть еще много чего кроме собственно «передачи маркера»
• и, я надеюсь, ещё кое-что…

Из чего состоит книга и как её читать?

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

Первый раздел по большей части болтологический и посвящен «качественным» особенностям распределённых систем. Если вы не знаете, что такое распределённая система, и какие к ней предъявляются требования, то первый раздел имеет смысл прочитать. Если же вы знаете, что поступающие процессу-получателю сообщения могут давать устаревшее представление о процессе-отправителе, точно так же, как и световое излучение, поступающее к нам от далекой звезды, дает представление о состоянии этой звезды в прошлом, то первые четыре пункта можно пропустить 🙂 Отдельно стоит отметить п. 1.5 «Взаимодействие в распределённых системах», в котором я попытался привести несколько простых задач, демонстрирующих сложности, с которыми можно столкнуться при разработке распределённых систем. Эти задачи мы будем потом решать, вооружившись теоретическими знаниями, поэтому стоит с ними ознакомиться.

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

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

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

На кого ориентирована эта книга?

Материал книги следует рассматривать в качестве введения в проблематику распределённых вычислений. Она выросла из академической вузовской среды, и будет, безусловно, полезна, если вы только начинаете работать в этой области. Если же у вас уже есть определённый опыт в разработке распределённых систем и алгоритмов, возможно, вы найдете для себя что-то новое и поделитесь своим мнением в комментариях. Если же вы имеете многолетний опыт за плечами и являетесь экспертом в этой теме, надеюсь, что вы сможете дополнить меня своими мыслями и соображениями.

Чего бы мне хотелось?

Буду рад, если материал книги окажется для вас полезным и познавательным — будет время вернуться сюда после её прочтения и черкнуть «спасибо», буду признателен. Кроме того, мне бы хотелось собрать весь материал по теме, включая комментарии, вопросы и ответы в одном месте, чтобы потом отсылать сюда всех желающих, включая новые курсы новых студентов. Если вы сможете помочь и дополнить материал своими мыслями, своим опытом, буду признателен вдвойне. Читайте, набирайтесь знаний и используйте их в своей работе! Скачать книгу в формате PDF прямо сейчас вы сможете по ссылке ниже:

Успехов!
Михаил Косяков

Вместо эпилога. «Информация, в отличие от ресурсов, задумана, чтобы ею делились». Роберт Кийосаки

Источник