Распределённые вычисления: как собрать с миру по гигафлопсу на развитие науки. Самые опасные распределенные вычисления
Распределенные вычисления
Часть 1. Высокопроизводительные вычисления в каждый дом
Серия контента:
1. Введение
Что делает ваш компьютер, когда ничего не делает? Пользователи одной из альтернативных операционных систем знают, что самый прожорливый процесс – это «System Idle»: как правило, он «съедает» около 90% ресурсов процессора. А чем занят ваш компьютер?
Выполните команду uptime, чтобы узнать среднюю загруженность системы. Если в этот момент ваш компьютер не занимается перекодированием видео или компиляцией ядра, то, скорее всего, средняя загруженность будет невелика – ниже 1.0. Такие действия, как просмотр Интернет-страниц, редактирование офисных документов и загрузка файлов с помощью торрент-клиента почти незаметны (с точки зрения производительности) для современных компьютеров.
Как же можно с пользой потратить время «безделья» компьютера? Ответу на этот вопрос и посвящена статья. Я расскажу вам, как можно заставить свою машину работать на благо человечества. В следующей статье речь пойдет о том, как создать собственный сервер распределенных вычислений.
2. Загадочная «решетка»
Речь пойдет об одной из форм распределенных вычислений (в международной терминологии такие вычисления называют GRID – решетка) – Volunteer Computing. Сначала поясним термины.
GRID – это объединение нескольких компьютеров для решения единой вычислительно сложной задачи, разбитой на подзадачи. Каждый компьютер решает несколько подзадач, а результаты отдельных вычислений объединяются. Основное преимущество GRID в том, что она может состоять из компьютеров, находящихся друг от друга на тысячи километров и имеющих различные характеристики (как аппаратные, так и программные). Задачу объединения этих разнородных компьютеров выполняет промежуточное программное обеспечение, которое (виртуально) связывает все компьютеры через Интернет в единый суперкомпьютер. Идея GRID возникла в 1990-х годах, когда с развитием средств компьютерных коммуникаций объединение географически удаленных друг от друга компьютеров стало более дешевым, простым и потенциально более мощным средством повышения производительности, чем наращивание мощности одного-единственного суперкомпьютера.
Существуют различные виды GRID. Volunteer Computing – это форма реализации GRID-вычислений, специфика которой заключается в использовании времени простоя компьютеров обычных пользователей по всему миру. На текущий момент самым крупным проектом Volunteer Computing как по числу участников, так и по суммарной мощности является Folding@home – проект по проведению компьютерной симуляции свертывания молекул белка, запущенный в октябре 2000 года учеными из Стэнфордского университета. Однако речь в этой статье пойдет не о Folding@home, а о втором по величине проекте – системе BOINC. Причина проста – в отличие от специализированного Folding@home, проект BOINC предоставляет возможность участия в самых разнообразных научных проектах, начиная от взлома криптографических систем и заканчивая поиском внеземных цивилизаций!
3. BOINC
Производительность
По состоянию на момент написания статьи, BOINC насчитывает 340 тысяч активных компьютеров, а суммарная производительность компьютеров участников проекта составляет 1,9 Петафлопа. Это почти в 2 раза превышает производительность мощнейшего современного суперкомпьютера IBM Roadrunner. Статистику проекта BOINC можно увидеть на официальной странице http://boinc.berkeley.edu/
Для организации распределенных вычислений (GRID-вычислений) необходима соответствующая программная платформа. Система должна уметь разбивать одну большую задачу на множество маленьких подзадач, распределять эти подзадачи по вычислительным узлам, принимать результаты вычислений и объединять их в единое целое. Для этого были созданы различные программные «прослойки» между управляющим сервером и вычислительными узлами. Одной из таких программных «прослоек» является BOINC.
3.1. Что такое BOINC
SETI@HOME
SETI@HOME – это некоммерческий проект по поиску внеземного разума с помощью анализа радиосигналов с радиотелескопа Аресибо.
SETI (Search for Extra Terrestrial Intelligence, Поиск ВнеЗемного Разума) – это направление исследований, направленное на обнаружение разумной жизни за пределами Земли. Основной метод – исследование радиосигналов, которыми пронизан космос. Ученые пытаются найти радиосигналы, источники которых не могут быть природными.
Сигналы с радиотелескопов содержат, в основном, шум (от внеземных источников и электроники приемников) и искусственные земные сигналы, такие как сигналы телевидения, радаров и спутников. Современный проект SETI анализирует данные в цифровой форме. Большая вычислительная мощность позволяет покрыть поиском больше частотных диапазонов с лучшей чувствительностью. SETI, следовательно, имеет неограниченную потребность в вычислительной мощности.
Предыдущие проекты SETI использовали специализированные суперкомпьютеры, выполнявшие основной объем анализа данных. В 1995 году Дэвид Андерсон (David Anderson) запустил проект по обработке данных SETI на виртуальном суперкомпьютере, состоящем из множества компьютеров, подключенных к сети Интернет, и организовал проект SETI@home (SETI на дому) для апробирования этой идеи. Проект SETI@home был запущен в мае 1999 года, а в 2005 году полностью перешел на платформу BOINC.
Выступление Дэвида Андерсона, посвященное SETI@HOME, распределенным вычислениям и BOINC, можно найти на YouTube: http://www.youtube.com/watch?v=8iSRLIK-x6A (EN).
BOINC (Berkeley Open Infrastructure for Network Computing – открытая платформа Университета Беркли для сетевых вычислений) – это свободная (распространяется под лицензией GNU LGPL) программная платформа для проведения распределенных вычислений (если точнее, то Volunteer Computing). Система BOINC была разработана в Калифорнийском университете в Беркли под руководством Дэвида Андерсона (David Anderson) командой, создавшей легендарный проект SETI@home. Основным мотивом разработки системы послужила нехватка свободных вычислительных мощностей для обработки данных, поступающих от радиотелескопов. Именно поэтому разработчики решили привлечь вычислительные ресурсы и объединить сообщества нескольких научных проектов. Для решения этой масштабной задачи и была создана программная платформа BOINC.
Система BOINC состоит из программы-клиента, общей для всех BOINC-проектов, составного сервера (термин «составной сервер» означает, что физически сервер может состоять из нескольких отдельных компьютеров) и программного обеспечения. Для выполнения распределенных вычислений используется архитектура клиент-сервер.
Пользователи, передающие вычислительные мощности BOINC-проектам типа SETI@home, «зарабатывают» кредиты, начисляемые за выполнение отдельных подзадач. Эти кредиты нужны только для создания духа соревновательности среди участников проекта – пользователи, имеющие наибольшее число кредитов, имеют шанс «засветиться» на главной странице проекта.
3.2. Установка
Установка программы-клиента BOINC в Linux проста до невозможности – пользуясь любимым пакетным менеджером, установите из репозитариев пакеты boinc-client, boinc-manager и boinc-gui. Если вы предпочитаете пользоваться новейшим программным обеспечением или если ваш дистрибутив Linux не имеет пакетного менеджера/репозитариев (а такие еще остались?), то получить установочный пакет свежей версии программы можно со страницы загрузки официального сайта проекта (ищите адрес сайта в разделе «Ссылки» под номером 1).
Вне зависимости от способа, которым вы установили программу-клиент, все основные файлы вы найдете в своем домашнем каталоге в подкаталоге BOINC – здесь находятся не только исполняемые файлы, но и файлы настроек, а также данные, необходимые для обсчета заданий. (Благодаря этому вы можете с легкостью «заставить работать» на один проект все компьютеры вашей корпоративной сети).
Для начала нужно запустить графический менеджер программы:
user: /home/user/run_manager
При первом запуске вам будет предложено подключиться к какому-либо проекту, упрощать этот процесс будет специальный помощник (см. рисунок 1).
На следующем шаге нужно будет выбрать проект, к которому вы хотите присоединиться, затем ввести свой электронный адрес и придумать пароль, а потом, возможно, потребуется завершить регистрацию на сайте самого проекта. В частности, на сайте можно выбрать команду (например, «Russia Team ») или даже создать свою собственную (я создал команду «Linux users Team» на проекте Climateprediction.net, присоединяйтесь!). Команды, как и отдельные участники, тоже участвуют в неформальном соревновании «Собери больше кредитов!».
К сожалению, описаний проектов менеджер BOINC при регистрации не предоставляет, поэтому выбором придется озаботиться заранее, например, просмотрев списки проектов, представленные по адресам в разделе «Ссылки» (). Не все так гладко и с предлагаемыми менеджером проектами, например, Einstein@home требует значительных аппаратных ресурсов, а SHA-1 Collision Search Graz уже не предоставляет заданий для обработки...
3.3. Работаем на благо науки!
Сразу после регистрации в проекте, программа-клиент BOINC начнет загрузку данных, необходимых для выполнения заданий. Учтите, что в зависимости от проекта этот этап может занять довольно продолжительное время и повлиять на вашу статистику полученного Интернет-трафика. Проекту ClimatePrediction.net понадобилось загрузить более 100 MБ, прежде чем начать обсчитывать первое задание.
Еще больше времени необходимо на вычисления по заданию: главное окно показывает текущий прогресс обсчета задания, затраченное время и оценку времени, необходимого для завершения задания (см. рисунок 2).
Помимо такого (упрощенного) вида окна программы-клиента BOINC, есть и более информативный расширенный вид – нажмите на кнопку Advanced View в правом нижем углу (см. рисунок 3).
Теперь вы можете получить большое количество дополнительной информации по проекту, в котором участвуете: различную статистику, информацию об использовании ресурсов компьютера, файлы, которые необходимо загрузить для расчета задания и многое другое! Все это скрывается за кнопками и пунктами меню с интуитивно понятными надписями, поэтому подробно останавливаться на этих возможностях мы не будем. Задержимся только на одной из них...
На вкладке «Задания» выделите строчку с заданием – тогда станут активными кнопки на панели слева (как на рисунке 3). Нажмите кнопку «Показать графику», и вашему взору предстанет замечательная картинка – это та самая модель, которую обсчитывает ваш компьютер. Поиграв управляющими клавишами (см. подсказки слева: T – температурная карта, R – снег и дождь, P – давление, C – облачность, S – запуск/остановка вращения глобуса, G – показать/скрыть сетку, H – помощь), можно наблюдать что-то аналогичное показанному на рисунке 4.
Конечно, какую картинку вы увидите – это зависит от проекта. Ничто не мешает вам поискать для себя что-то более интересное.
Еще одно замечание практического плана. На рисунках 2 и 3 видно, что общее время, необходимое для расчета задания, превышает 200 часов. Конечно, не каждый (особенно домашний) компьютер имеет время непрерывной работы порядка 10 суток. Для того чтобы не потерять все результаты расчетов при выключении компьютера, BOINC устанавливает контрольные точки. Кнопка «Информация» на вкладке «Задания» покажет, в том числе, и информацию о времени последней контрольной точки – при выключении компьютера вы потеряете лишь порядка 15 минут работы процессора.
3.4. Настройка программы-клиента «под себя»
Пользователю дается большой контроль над программой-клиентом BOINC с помощью различных настроек. Некоторые из этих настроек специфичны для проекта, другие являются общими и влияют на работу программы в целом. В расширенном виде окна программы-клиента выберите пункт меню «Дополнительно» – «Настройки клиента». Здесь вы можете указать такие параметры использования компьютера, что работа программы-клиента BOINC будет практически незаметна! Вы можете ограничить объем используемых для распределенных вычислений ресурсов процессора. Кроме всего прочего, можно указать, будет ли программа-клиент запускать на обсчет задания в то время, когда пользователь активно использует компьютер, или работа над распределенным проектом начнется только после определенного времени простоя процессора.
В качестве настройки, специфичной для проекта, можно указать минимальный и максимальный объем работ, который программа-клиент выполнит для указанного проекта между двумя подключениями к серверу. Когда объем оставшихся работ окажется ниже минимального значения, программа-клиент свяжется с сервером проекта и запросит столько заданий, сколько указано в значении максимального объема работ. Во время этого сеанса связи программа-клиент также отчитается о завершенных заданиях. Эта возможность полезна, если по каким-то причинам необходимо минимизировать количество выходов в Интернет.
Вы можете ограничить скорость загрузки заданий из Интернет, объем используемого программой-клиентом BOINC дискового пространства и оперативной памяти... Все эти настройки интуитивно понятны, и не составит труда изменить их так, чтобы работа на благо человечества не мешала вашим личным интересам.
Если вы до сих пор не определились, какому именно проекту отдать свободные силы своего компьютера, не переживайте! Вы можете участвовать сразу в нескольких проектах («Сервис» –«Добавить проект» в расширенном виде окна программы или кнопка «Add Project» – в упрощенном) – по умолчанию программа-клиент BOINC будет каждые 60 минут (этот параметр тоже можно изменить) переключаться между заданиями различных проектов.
3.5. Некоторые технические подробности
Как уже говорилось выше, распределенный проект BOINC состоит из составного сервера, раздающего задания клиентам и собирающего результаты, и множества подключаемых к серверу программ-клиентов, выполняющих основную работу по получению результатов.
Каждая программа-клиент подключается к серверу и получает задание на обработку. Через некоторое время, когда задание выполнено, программа-клиент снова подключается к серверу и передает ему результаты (а также получает новое задание). За выполнение задания зарегистрированный участник проекта, которому принадлежит программа-клиент, получает кредиты – баллы, характеризующие процессорное время, потраченное на проведение вычислений.
Однако в этой схеме для проекта распределенных вычислений спрятан ряд опасностей. Во-первых, программа-клиент, получившая задание, может по различным причинам никогда не выйти снова на связь с сервером. Например, если участник проекта, которому принадлежит программа-клиент, потерял интерес к проекту. Во-вторых, участники проекта (опять же по различным причинам) могут посылать неверные результаты. Это еще более опасно для проекта, чем просто отсутствие результата, так как одно-единственное неверно посчитанное задание может стать причиной полного фиаско проекта! И, в-третьих, участники проекта могут попытаться получить больше кредитов, чем они заработали. Конечно, так как заработанные кредиты используются только для статистики, эта опасность на первый взгляд не так уж страшна... Однако проблема лежит в психологии сохранения сообщества. Не такое уж большое число пользователей заинтересованы именно в помощи научному исследованию, большая часть пользователей будут раздражены «читерами» и, как следствие, разочарованы проектом, и перестанут уделять ему время.
Первую проблему система BOINC обходит просто – назначая конечный срок, к которому программа-клиент должна вернуть результат вычислений (например, на рисунке 3 видно, что конечный срок, к которому нужно вернуть результат задания – это 19 мая 2010 года).
Вторая проблема решается за счет передачи одного и того же задания нескольким пользователям (это называется избыточными вычислениями). Для каждого задания количество дублирующих друг друга исполнителей индивидуально, но значение по умолчанию платформы BOINC равняется пяти. Когда программа-клиент отчитывается о проведенных вычислениях, сервер сравнивает результаты, присланные разными участниками. Результат, принятый «кворумом» программ-клиентов, считается правильным, а неверные ответы отвергаются. Участники, вернувшие серверу неверные результаты, не получают кредитов. Число программ-клиентов, составляющее «кворум», также может быть указано для каждого задания в отдельности, а значение по умолчанию равняется трем. Кстати, именно из-за такой формы проверки результатов вы будете наблюдать задержки в подсчете заработанных кредитов.
Третью проблему BOINC решает так же, как и проблему неправильных ответов – выполняя избыточные вычисления. Если пользователь завышает значение кредитов, которые он должен получить, то он увеличивает также значение кредитов, которые получат честные пользователи. Это снижает ущерб от обмана.
3.6. Подведение итогов
Использование распределенных вычислений – новый шаг в развитии научных исследований. Ученые со всего мира разрабатывают проекты, которые требуют проведения большого числа расчетов, а программная платформа BOINC дает возможность присоединиться к этим проектам всем желающим, не требуя ни специализированного образования, ни особых аппаратных ресурсов. Все, что нужно – скачать и установить программу-клиент.
Однако это далеко не все, что можно было бы рассказать о BOINC. Например, BOINC умеет использовать для вычислений GPU (Graphics Processing Unit) видеокарты NVIDIA. Вы можете создавать обложки («скины») для программы-клиента, запускать программу-клиента на разных компьютерах под одной учетной записью, управлять работой программы-клиента без графического интерфейса и даже найти свой украденный компьютер с помощью BOINC! Ну и, конечно же, любой человек может создать свой собственный проект распределенных вычислений на основе BOINC. Начните с этой страницы http://boinc.berkeley.edu/wiki/User_manual официального сайта, а в случае затруднений обратитесь на русскоязычный форум: http://boinc.ru/forum/ .
В следующей статье мы подробно остановимся на том, как создать свой собственный сервер BOINC. Кто знает, быть может, это послужит появлению новых отечественных проектов распределенных вычислений? А пока подождем, когда на полную мощность будет запущен российский проект DrugDiscovery@Home (смотрите адрес сайта в разделе «Ссылки» под номером 9), созданный и поддерживаемый интернациональной командой разработчиков и находящийся в стадии альфа-тестирования.
4. Заключение
15 января 2013 в 10:55Эх, ухнем! Распределенные вычисления вчера и сегодня
- Блог компании Intel ,
- Высокая производительность
Принцип параллельного проведения расчетов – один из тех, что буквально «витают в воздухе». И это естественно, ведь любую работу удобней выполнять сообща. Параллельные вычисления появились задолго до первой ЭВМ, однако идея расцвела именно в компьютерную эпоху, ведь именно тогда появились и задачи, требующие большой вычислительной мощности, и устройства, готовые «всем миром» эту мощность предоставить. В эти дни исполняется ровно 15 лет с моего первого знакомства с проектами распределенных вычислений – хороший повод, чтобы написать об их истории и сегодняшнем дне.
Краткое теоретическое предисловие
Немного теории для тех, кто ранее не интересовался распределенными вычислениями. Проект подобного рода предполагает, что вычислительная нагрузка распределяется между компьютерами-клиентами, чем их больше, тем лучше. Необходим также центр управления, его функции состоят в следующем:- Раздача «сырых» кусочков клиентам и прием от них результатов обработки;
- Контроль потерянных и неверно посчитанных фрагментов;
- Интерпретация полученных кусочков в свете общей цели;
- Подсчет и визуализация статистики.
Несмотря на кажущуюся простоту, создать систему распределенных вычислений до появления типовых решений было задачей нетривиальной – ведь надо было как минимум написать клиенты под несколько операционных систем и управляющий сервер, да так, чтобы это все вместе еще и работало. Некоторые проекты так и не смогли преодолеть «детские болезни» и не достигли своих целей. Однако существовали и вполне успешные – один из таких и затянул меня на без малого 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
"Ну и что, что у меня 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 Гигабайт в месяц. Почти не требует входящего трафика, процессорного времени или специфической оси.
Результат: редкий случай, когда работаете вы, скорее всего, на себя и результат используете в деле.
- Tutorial
Девять лет назад я начал «в свободное от основной работы время» преподавать компьютерные дисциплины в одном из университетов Санкт-Петербурга. И только сравнительно недавно к своему удивлению обнаружил, что в наших вузах практически отсутствуют курсы с фокусом на проблематику распределённых вычислений. И даже на Хабре эта тема не раскрыта в достаточной мере! Надо прямо сейчас исправлять ситуацию.
Этой теме я и хотел посвятить статью или даже серию статей. Но потом решил выложить своё учебное пособие по основам распределённых вычислений, вышедшее в свет в этом году (читай, небольшую книгу объемом 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: Общее собрание».
В действительности события происходят в следующей последовательности:
- Первым отправляется сообщение от пользователя А.
- Пользователь В получает его, читает и отправляет ответ.
- Пользователь С получает оба сообщения от А и В и затем отправляет свой ответ, опирающийся на оба сообщения от А и В.
- Сообщение от пользователя С с темой «Re:Re: Общее собрание».
- Сообщение от пользователя А с темой «Общее собрание».
- Сообщение от пользователя В с темой «Re: Общее собрание».
Ага, оказывается порядок поступления сообщений, наблюдаемый различными процессами, может быть различным даже для FIFO каналов! А что делать, если мы хотим, чтобы наблюдаемый порядок был везде одинаков (и при этом не хотим использовать синхронный обмен сообщениями)? К примеру, если мы пишем свой транспорт с соответствующими гарантиями. Или хотим построить отказоустойчивую службу (replicated state machine), где каждая реплика должна обрабатывать поступающие запросы в едином для всех реплик порядке, чтобы состояния реплик не различались? Вопрос…
Рассмотрим теперь еще одно выполнение распределённой системы, в которой процессы взаимодействуют только с помощью обмена сообщениями, и каждый процесс занимается включением / выключением фонаря с определенным светом. Пусть первый процесс управляет фонарем с красным светом, второй – с желтым, а третий – с зеленым. Такая вот светофорная система. На рисунке ниже включение процессом своего фонаря обозначено прямоугольником, а выключение – вертикальной линией; отправка и получение сообщения – стрелкой. Вопрос: могут ли процессы определить, какие фонари светили одновременно?
Так вот оказывается, что в данном выполнении асинхронной системы процессы никак не смогут определить был ли включен красный свет одновременно с желтым. Может быть да. А может и нет… Сие останется неизвестным. Но зато будет точно известно, что красный и зеленый фонари одновременно находились во включенном состоянии. Другими словами, оказывается, нет особого смысла говорить о том, что то или иное глобальное состояние достигается по ходу выполнения распределённой системы! Равно как и очень часто нельзя сказать, выполнялось ли какое-либо условие (предикат), заданное на множестве его глобальных состояний! Опять же вопрос: почему?
Наш ответ Чемберлену. На самом деле ответы на эти и многие другие вопросы, связанные с работой асинхронных распределённых систем, крайне сложно уложить в рамки одной статьи. Поэтому я и решил опубликовать сразу несколько статей в одной. Точнее, как указано в начале статьи, представить свою небольшую книгу по основам распределённых вычислений, доступную в электронном виде.
Из этой книги вы узнаете:
- про причинно-следственный порядок событий распределённого вычисления
- что такое справедливость, безопасность и живучесть
- что такое конус прошлого и конус будущего для события вычисления
- чем логический параллелизм отличается от физического параллелизма
- почему не имеет особого смысла говорить о совокупности глобальных состояний вычисления, а имеет смысл говорить о совокупности событий вычисления
- как нам упорядочить события распределённого вычисления в одну или несколько последовательностей, которые «могли бы» происходить в системе
- что такое логические часы, и какое такое логическое время они отсчитывают
- почему логическое время останавливается, если в системе ничего не происходит
- чем скалярное время отличается от векторного
- как и для чего можно использовать логическое время в распределённых алгоритмах
- какие есть подходы к эффективной реализации векторных часов
- зачем нам может понадобиться матричное время
- чем распределённый алгоритм отличается от централизованного
- как решать задачу взаимного исключения без использования разделяемых переменных
- на какие категории делятся все распределённые алгоритмы взаимного исключения
- зачем в алгоритмах на основе получения разрешений используется логическое время
- почему философам так трудно пообедать в распределённой системе
- зачем нам граф конфликтов и граф предшествования
- почему граф предшествования должен меняться со временем
- почему в алгоритмах на основе передачи маркера есть еще много чего кроме собственно «передачи маркера»
- и, я надеюсь, ещё кое-что…
В начале я постарался в двух словах изложить, какие цели ставились при написании книги, и как она соотносится с другой литературой. Этому посвящено введение к книге. Оно занимает всего чуть более двух страниц, поэтому прочитать его стоит.
Первый раздел по большей части болтологический и посвящен «качественным» особенностям распределённых систем. Если вы не знаете, что такое распределённая система, и какие к ней предъявляются требования, то первый раздел имеет смысл прочитать. Если же вы знаете, что поступающие процессу-получателю сообщения могут давать устаревшее представление о процессе-отправителе, точно так же, как и световое излучение, поступающее к нам от далекой звезды, дает представление о состоянии этой звезды в прошлом, то первые четыре пункта можно пропустить:) Отдельно стоит отметить п. 1.5 «Взаимодействие в распределённых системах», в котором я попытался привести несколько простых задач, демонстрирующих сложности, с которыми можно столкнуться при разработке распределённых систем. Эти задачи мы будем потом решать, вооружившись теоретическими знаниями, поэтому стоит с ними ознакомиться.
Во втором разделе представлена модель распределённого вычисления и основная теория, используемая при дальнейшем изложении. В определенном смысле этот раздел является ключевым. Однако надо быть готовым к работе с такими терминами как «множество / подмножество», «бинарное отношение», «отношение эквивалентности», «отношение порядка», «линейный / частичный порядок». В этом разделе вы встретите доказательства некоторых утверждений. Мне кажется, что их следует, как минимум, проглядеть (а лучше изучить) для более глубокого понимания существенных особенностей функционирования распределённых систем, выделяющих их среди систем других классов.
На базе теории, представленной выше, в третьем разделе, наконец, рассматриваются более практичные вещи, а именно, различные механизмы логических часов. С их помощью мы можем упорядочивать события в одну или несколько последовательностей, которые могли бы происходить в системе, что позволяет значительно упростить разработку алгоритмов для распределённых систем. Приводятся примеры использования логических часов для решения задач, сформулированных в п. 1.5 «Взаимодействие в распределённых системах».
Четвертый раздел посвящен изучению основных распределённых алгоритмов взаимного исключения, построенных без применения привычных разделяемых переменных. Ключевые идеи этих алгоритмов используются и для решения многих других задач в распределённых системах. Кроме того, их изучение позволяет раскрыть такие важные вопросы, как обеспечение свойств безопасности и живучести распределённых алгоритмов. Поэтому этот раздел мне представляется весьма полезным для ознакомления.
На кого ориентирована эта книга?
Материал книги следует рассматривать в качестве введения в проблематику распределённых вычислений. Она выросла из академической вузовской среды, и будет, безусловно, полезна, если вы только начинаете работать в этой области. Если же у вас уже есть определённый опыт в разработке распределённых систем и алгоритмов, возможно, вы найдете для себя что-то новое и поделитесь своим мнением в комментариях. Если же вы имеете многолетний опыт за плечами и являетесь экспертом в этой теме, надеюсь, что вы сможете дополнить меня своими мыслями и соображениями.
Чего бы мне хотелось?
Возможные полезные результаты использования параллельных вычислений:
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. – Режим доступа: .]
Загрузка...
