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

#1 · 26.12.2021, 08:11

Цитата: Удаленный пользователь от 26.12.2021, 08:11

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

Версія українською

автор - Arbalet

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

В конце 18-го века правительство Франции решило существенно улучшить логарифмические и тригонометрические таблицы. Работа была связана с огромными по тем временам объемами расчетов, а потому ее поручили профессионалу, барону Гаспару де Прони, состоявшему главным вычислителем при французском правительстве в 1790-1800 гг. В результате появилась знаменитая "вычислительная мануфактура" барона де Прони.

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

Идеи де Прони подтолкнули Чарльза Бэббиджа к созданию первой в истории вычислительной машины, а основанные на прототипе барона "вычислительные мануфактуры" использовались в исследовательских проектах вплоть до середины 20 века, с их помощью, в частности, рассчитывались первые ядерные бомбы в США, Великобритании и Советском Союзе.

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

Следующий качественный скачок в техническом решении задачи совместной работы многих компьютеров над единой сложной задачей произошел к концу 1980-х гг., когда появились персональные компьютеры и электронная почта. В 1988 г. Арьен Ленстра и Марк Менес, работавшие на компанию DEC (Palo Alto), написали программу для факторизации (разбиения на множители) длинных чисел. Для скорейшего завершения поставленной задачи программа могла запускаться на нескольких не связанных друг с другом машинах, каждая из которых обрабатывала свой небольшой фрагмент числа. Новые блоки заданий рассылались на компьютеры участников (также как посчитанные результаты принимались) с помощью центрального сервера проекта по обычной электронной почте. Для успешного разложения на множители числа длиной в сто знаков этому сообществу потребовалось два года и несколько сотен персональных компьютеров.

Таким образом, именно проект Ленстра-Менеса продемонстрировал не только принципиальную возможность распределенной вычислительной сети, но и высокую эффективность в выполнении поставленных перед таким проектом задач. По сути, именно отсюда нужно начинать историю публичных Internet-проектов распределенных вычислений (Distributed Computing).

В случае же с более ранним "червем" из исследовательского центра PARC, это было скорее начало другого направления распределенных вычислений, кластерного, позже названного Grid Computing (параллельные вычисления или "решетки" вычислительных ресурсов). Ведь в лаборатории PARC машины были связаны первой Ethernet-сетью и постоянно обменивались данными на большой скорости, синхронизируя свою работу над отдельными фрагментами задания.

Позже, в 1994 г., появилось первое техническое воплощение технологии Grid Computing - виртуальный кластер "Беовульф", организованный Дональдом Бекером и Томасом Стерлингом на основе 16 обычных компьютеров 486DX4, объединенных в единую 10Мбитную сеть с постоянным обменом информации между процессорами. Результат превзошел все ожидания. Фактически была доказана возможность построения сетей любой необходимой вычислительной мощности на базе обычных машин без использования дорогих суперкомпьютеров.

Теперь необходимо дать отличительные признаки двух направлений распределенных вычислений. Понятия Distributed Computing и Grid Computing зачастую смешивают, но это неправильно.

Задачи, которые реализуются с помощью Grid Computing, требуют активного межмашинного взаимодействия и синхронизации, реализуемого с помощью специальных библиотек MPІ, PVM, BSPlіb и др. Эти библиотеки обычно применимы только в кластерних системах, поскольку требуют высокой скорости сетевых взаимодействий и, соответственно, большого объема непрерывного сетевого трафика. Тот факт, что сетевые взаимодействия осуществляются между всеми машинами, задействованными в вычислениях, также означает запрет на использование межсетевых экранов или других средств ограничения сетевых потоков. Также это обычно означает, что абсолютно все машины должны быть доступны с начала до конца решения задачи. Поэтому, реализованная на таких принципах вычислительная сеть возможна чаще всего в пределах некоторой замкнутой организации. В силу этих ограничений, задачи, которые требуют использования этих библиотек, обычно не подходят для крупномасштабных распределенных проектов.

Вычислительные задачи, которые не требуют никакой координации или синхронизации между машинами, и не нуждаются в дополнительном управлении в процессе работы, обычно решаются с помощью технологии Distributed Computing. Этот тип задач очень подходит для больших Internet-проектов распределенных вычислений, реализуемых посредством связки "сервер - компьютер участника", поскольку отдельные фрагменты задачи могут выполняться в любом порядке, и могут быть перераспределены по другим машинам, если какой-нибудь из результатов не удалось получить с первого раза. Отсюда, кстати, проистекает необходимость избыточности вычислений, когда один и тот же блок задания рассылается нескольким участникам. Это необходимо, чтобы гарантировать получение результатов вычисления отдельного блока, что не всегда возможно, учитывая пестроту участников и установленного на их компьютерах программного обеспечения.

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

Высказываются оптимистические прогнозы, что в скором времени в строй войдет новая архитектура Distributed Computing, которая позволит компьютерам-участникам обмениваться данными непосредственно между собой, несмотря на сложности и эпизодичность подключения к сети Internet. Более того, проводятся активные исследования возможности использования в вычислениях графических процессоров (GPU) видеокарт. О планах по запуску клиента для GPU уже объявлено руководством проекта Folding@Home (уже запущено в 2007 году - прим. ред.). Это позволит не только расширить область применения публичных распределенных вычислений, но и значительно увеличит емкость ее вычислительного потенциала.

Но вернемся к истории Distributed Computing - времени выхода распределенных вычислений на широкую арену.

После успешного окончания проекта Ленстра-Менеса в ходу были проекты различных математических исследований. В 1993 г. участники одного из таких проектов факторизовали число длиной 129, потом 130 знаков. Затем пошла мода на поиск простых чисел (т.е. делящихся только на единицу и на самих себя), новых чисел Серпинского, Мерсенна и пр. в том же духе. Эти проекты не отличались ни технической проработанностью, ни размахом, ни большим количеством участников. Но так продолжалось не долго.

28 января 1997 г. стартовал конкурс RSA Data Security на решение задачи взлома 56-битного ключа RC5-32/12/7 методом простого перебора. Благодаря хорошей технической и организационной подготовке проект быстро получил невиданную до этого известность, привлек внимание мировой общественности к распределенным вычислениям и заложил основы последующих проектов Distributed Computing. Этот и последовавшие за ним проекты и конкурсы подобного рода (RC5-64, RC5-72, OGR и др.) организованы при активном участии Джеффа Лоусона и основанного им некоммерческого объединения distributed.net, которому удалось разработать наиболее совершенное программное обеспечение под математические задачи, решаемые с помощью Distributed Computing. В проектах distributed.net RC5-72 и OGR участвуют сильные украинские команды.

13 мая 1999 г. Дэвид Гиди и Крэйг Кэснов запустили проект поиска сигналов внеземных цивилизаций SETI@Home (SETI - Search for Extraterrestrial Intelligence), который стал наиболее массовым проектом распределенных вычислений всех времен. Огромной популярности (более 5 млн. участников) способствовало то, что проект впервые переложил на рельсы Distributed Computing интригующую научную задачу далекую от скучной факторизации или взлома очередного ключа. Оглушительный успех проекта (в плане привлеченных вычислительных мощностей) убедил ученых активнее использовать незадействованный потенциал компьютеров рядовых пользователей всемирной паутины во многих областях научных исследований.

1 октября 2000 г. под руководством Виждая Панде, основателя академического учреждения Pande Group при Стенфордском университете, стартовал проект Folding@Home. Благодаря четким практическим целям, хорошему научному основанию и реальным результатам проект получил массовую поддержку (более полумиллиона участников за все время работы проекта) и серьезные вычислительные ресурсы (более 200 тысяч процессоров, постоянно или временно подключенные сейчас к проекту).

Дополняем кто что знает...

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

Версія українською

автор - Arbalet

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

В конце 18-го века правительство Франции решило существенно улучшить логарифмические и тригонометрические таблицы. Работа была связана с огромными по тем временам объемами расчетов, а потому ее поручили профессионалу, барону Гаспару де Прони, состоявшему главным вычислителем при французском правительстве в 1790-1800 гг. В результате появилась знаменитая "вычислительная мануфактура" барона де Прони.

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

Идеи де Прони подтолкнули Чарльза Бэббиджа к созданию первой в истории вычислительной машины, а основанные на прототипе барона "вычислительные мануфактуры" использовались в исследовательских проектах вплоть до середины 20 века, с их помощью, в частности, рассчитывались первые ядерные бомбы в США, Великобритании и Советском Союзе.

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

Следующий качественный скачок в техническом решении задачи совместной работы многих компьютеров над единой сложной задачей произошел к концу 1980-х гг., когда появились персональные компьютеры и электронная почта. В 1988 г. Арьен Ленстра и Марк Менес, работавшие на компанию DEC (Palo Alto), написали программу для факторизации (разбиения на множители) длинных чисел. Для скорейшего завершения поставленной задачи программа могла запускаться на нескольких не связанных друг с другом машинах, каждая из которых обрабатывала свой небольшой фрагмент числа. Новые блоки заданий рассылались на компьютеры участников (также как посчитанные результаты принимались) с помощью центрального сервера проекта по обычной электронной почте. Для успешного разложения на множители числа длиной в сто знаков этому сообществу потребовалось два года и несколько сотен персональных компьютеров.

Таким образом, именно проект Ленстра-Менеса продемонстрировал не только принципиальную возможность распределенной вычислительной сети, но и высокую эффективность в выполнении поставленных перед таким проектом задач. По сути, именно отсюда нужно начинать историю публичных Internet-проектов распределенных вычислений (Distributed Computing).

В случае же с более ранним "червем" из исследовательского центра PARC, это было скорее начало другого направления распределенных вычислений, кластерного, позже названного Grid Computing (параллельные вычисления или "решетки" вычислительных ресурсов). Ведь в лаборатории PARC машины были связаны первой Ethernet-сетью и постоянно обменивались данными на большой скорости, синхронизируя свою работу над отдельными фрагментами задания.

Позже, в 1994 г., появилось первое техническое воплощение технологии Grid Computing - виртуальный кластер "Беовульф", организованный Дональдом Бекером и Томасом Стерлингом на основе 16 обычных компьютеров 486DX4, объединенных в единую 10Мбитную сеть с постоянным обменом информации между процессорами. Результат превзошел все ожидания. Фактически была доказана возможность построения сетей любой необходимой вычислительной мощности на базе обычных машин без использования дорогих суперкомпьютеров.

Теперь необходимо дать отличительные признаки двух направлений распределенных вычислений. Понятия Distributed Computing и Grid Computing зачастую смешивают, но это неправильно.

Задачи, которые реализуются с помощью Grid Computing, требуют активного межмашинного взаимодействия и синхронизации, реализуемого с помощью специальных библиотек MPІ, PVM, BSPlіb и др. Эти библиотеки обычно применимы только в кластерних системах, поскольку требуют высокой скорости сетевых взаимодействий и, соответственно, большого объема непрерывного сетевого трафика. Тот факт, что сетевые взаимодействия осуществляются между всеми машинами, задействованными в вычислениях, также означает запрет на использование межсетевых экранов или других средств ограничения сетевых потоков. Также это обычно означает, что абсолютно все машины должны быть доступны с начала до конца решения задачи. Поэтому, реализованная на таких принципах вычислительная сеть возможна чаще всего в пределах некоторой замкнутой организации. В силу этих ограничений, задачи, которые требуют использования этих библиотек, обычно не подходят для крупномасштабных распределенных проектов.

Вычислительные задачи, которые не требуют никакой координации или синхронизации между машинами, и не нуждаются в дополнительном управлении в процессе работы, обычно решаются с помощью технологии Distributed Computing. Этот тип задач очень подходит для больших Internet-проектов распределенных вычислений, реализуемых посредством связки "сервер - компьютер участника", поскольку отдельные фрагменты задачи могут выполняться в любом порядке, и могут быть перераспределены по другим машинам, если какой-нибудь из результатов не удалось получить с первого раза. Отсюда, кстати, проистекает необходимость избыточности вычислений, когда один и тот же блок задания рассылается нескольким участникам. Это необходимо, чтобы гарантировать получение результатов вычисления отдельного блока, что не всегда возможно, учитывая пестроту участников и установленного на их компьютерах программного обеспечения.

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

Высказываются оптимистические прогнозы, что в скором времени в строй войдет новая архитектура Distributed Computing, которая позволит компьютерам-участникам обмениваться данными непосредственно между собой, несмотря на сложности и эпизодичность подключения к сети Internet. Более того, проводятся активные исследования возможности использования в вычислениях графических процессоров (GPU) видеокарт. О планах по запуску клиента для GPU уже объявлено руководством проекта Folding@Home (уже запущено в 2007 году - прим. ред.). Это позволит не только расширить область применения публичных распределенных вычислений, но и значительно увеличит емкость ее вычислительного потенциала.

Но вернемся к истории Distributed Computing - времени выхода распределенных вычислений на широкую арену.

После успешного окончания проекта Ленстра-Менеса в ходу были проекты различных математических исследований. В 1993 г. участники одного из таких проектов факторизовали число длиной 129, потом 130 знаков. Затем пошла мода на поиск простых чисел (т.е. делящихся только на единицу и на самих себя), новых чисел Серпинского, Мерсенна и пр. в том же духе. Эти проекты не отличались ни технической проработанностью, ни размахом, ни большим количеством участников. Но так продолжалось не долго.

28 января 1997 г. стартовал конкурс RSA Data Security на решение задачи взлома 56-битного ключа RC5-32/12/7 методом простого перебора. Благодаря хорошей технической и организационной подготовке проект быстро получил невиданную до этого известность, привлек внимание мировой общественности к распределенным вычислениям и заложил основы последующих проектов Distributed Computing. Этот и последовавшие за ним проекты и конкурсы подобного рода (RC5-64, RC5-72, OGR и др.) организованы при активном участии Джеффа Лоусона и основанного им некоммерческого объединения distributed.net, которому удалось разработать наиболее совершенное программное обеспечение под математические задачи, решаемые с помощью Distributed Computing. В проектах distributed.net RC5-72 и OGR участвуют сильные украинские команды.

13 мая 1999 г. Дэвид Гиди и Крэйг Кэснов запустили проект поиска сигналов внеземных цивилизаций SETI@Home (SETI - Search for Extraterrestrial Intelligence), который стал наиболее массовым проектом распределенных вычислений всех времен. Огромной популярности (более 5 млн. участников) способствовало то, что проект впервые переложил на рельсы Distributed Computing интригующую научную задачу далекую от скучной факторизации или взлома очередного ключа. Оглушительный успех проекта (в плане привлеченных вычислительных мощностей) убедил ученых активнее использовать незадействованный потенциал компьютеров рядовых пользователей всемирной паутины во многих областях научных исследований.

1 октября 2000 г. под руководством Виждая Панде, основателя академического учреждения Pande Group при Стенфордском университете, стартовал проект Folding@Home. Благодаря четким практическим целям, хорошему научному основанию и реальным результатам проект получил массовую поддержку (более полумиллиона участников за все время работы проекта) и серьезные вычислительные ресурсы (более 200 тысяч процессоров, постоянно или временно подключенные сейчас к проекту).

Дополняем кто что знает...

PinkFloyd, Yura12 и 4 отреагировали на эту запись.