Параллельное программирование

GRID-технологии

Показывать лекцию целиком

Основные направления исследований в области Grid-технологий

Термин "Grid-вычисления" ( Computing grid ), где "grid" означает "решетка, сетка, сеть", по смыслу аналогичен выражению "единая энергосистема". Суть его заключается в стремлении объединить все компьютеры мира в единую систему — в виртуальный суперкомпьютер невиданной мощности, что позволит распределять и перераспределять ресурсы между пользователями в соответствии с их запросами. Именно так человечество пользуется электричеством единых энергетических сетей. Основу подобного объединения можно рассматривать и для транспортных сетей, сетей обеспечения водой, нефтью, газом и т.д.

Имея такой суперкомпьютер, пользователь может в любое время и в любом месте запросить столько вычислительных ресурсов, сколько ему требуется для решения своей задачи. Более того, он может заказать ее решение, послав запрос-заявку на сайт одного из центров обслуживания. Так же, как единая энергосистема локально испытывает переменную нагрузку (потребление электроэнергии в отдельной стране, регионе или населенном пункте изменяется в зависимости от времени суток, года и т.д.), так и система Grid-вычислений способна перераспределять мощности, направляя запросы на недогруженные компьютеры в соответствии с возросшими требованиями.

Предоставление вычислительных ресурсов по требованию связывают с известным понятием "коммунальная услуга", что вполне соответствует тенденции объединения и распределения ресурсов жизнеобеспечения.

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

И мы ловим себя на мысли, что говорим об Интернете!

Да, в сущности, речь идет о смелом, фантастическом развитии именно того, что фантастическим казалось вчера, о развитии всемирной паутины, о внедрении в нее вычислительных функций и о повышении качества информационного обслуживания. Именно так и намечается дальнейший путь развития Интернета: от WWW к GRID Петрушанко С. CERN: от WWW к GRID. "Компьютерра", 2004, \No21..

Таким образом, для Grid-технологии характерны два (традиционно смешиваемых) направления развития, определяемые их важностью и различиями в исследовании.

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

Однако именно здесь существует основная проблема. Неуправляемое стихийное, даже "дикое" развитие Интернета приводит к парадоксу: доступность огромных объемов мировой информации породила значительный вес отказов, ответов о действительной недоступности этой информации, о превышении допустимого времени поиска, об ошибках. Поисковые системы блуждают по иерархической, запутанной системе Web-серверов, натыкаясь на их перегрузку, образуя трафик для обратного движения информации. Мы с отчаянием следим за замершей планкой индикатора, в ожидании выдачи такой знакомой записи "Error..." — с указанием предположения об окончании допустимого времени адресного обращения.

Сделать всю информацию доступной, установить гарантированное время поиска, породить у пользователя ощущение того, что вся информация по его запросу находится рядом, — это фантастическая задача. Можно ли объединить всю информацию мира, блуждающую в Интернете, в одну огромную базу данных, размеры которой даже трудно оценить? Да еще с неограниченным многоканальным доступом?

Движение в направлении осуществления этой глобальной идеи и является задачей исследователей в области Grid-технологий. Ясно, что идеального решения эта задача может никогда не получить. Однако стремиться к минимизации времени выполнения запроса, несмотря на структурную "удаленность" информации, несомненно, следует.

Второе направление развития Grid-технологий связано, как ранее говорилось, с таким расширением функций Интернета, при котором пользователь может получать ответы на запросы вычислительного характера. Речь, конечно, идет о тех задачах, решение которых недоступно широкому пользователю — ученому, управленцу, коллективу, всем, кому необходима достоверная информация для важных решений. Интернет должен принимать заказ на работу с задачами высокой сложности, большой размерности, с задачами моделирования сложных физических явлений, таких, например, как точный метеорологический прогноз, с оптимизационными задачами хозяйственного планирования, с задачами статистической обработки экспериментов, с задачами — запросами по контролю космического пространства, с имитационными задачами для испытания новых технических средств и т.д.

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

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

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

Базовыми элементами защиты являются:

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

    Немного истории

    Первые опыты в области Grid -технологий связаны с расчетами экспериментов в ядерной физике. Считается, что этот опыт вообще стал базой формирования World Wide Web, WWW — Всемирной Паутины. С ним связывают имя: Тим Бернес-Ли. Перед этим ученым была поставлена задача найти способ, который позволил бы ученым, участвующим в экспериментах на Большом адронном коллайдере, обмениваться данными и представлять результаты их обработки на всеобщее обсуждение. Многие физики, большую часть времени находящиеся в своих научных институтах, тоже хотели полноправно участвовать в анализе данных.

    Тим Бернес-Ли предложил создать в Европейской организации ядерных исследований (CERN) систему распределенного информационного обеспечения, основанную на использовании гипертекста и способную объединить научные центры всей Земли. Были написаны специальные программы, установленные на многих компьютерах мира, которые были разбиты на группы, связанные со своим сервером. Эти программы могли работать с единой БД CERN, с помощью дополнительных серверов перерабатывая данные и возвращая результаты в единую БД.

    В 1990 году прототип того, что впоследствии получило название Всемирной Паутины, был создан в CERN, а начиная с 1991 года, первые браузеры и WWW-серверы появились в распоряжении ядерных физиков всего мира. Широкое распространение сразу же получили язык HTML и протокол HTTP.

    Однако теоретическое обобщение опыта CERN и развитие идеи WWW в область современного представления о будущей сети Grid, было сделано американскими учеными Яном Фостером и Карлом Кессельманомe Forster I., Kesselman K., "The Grid: Blueprint for a New Computing Infrastructure". Morgan Kaufmann, 1998.. По их представлению, Grid действительно является "надстройкой" над Интернетом, предназначенной для распределенных вычислений при решении задач высокой сложности в области науки и технологий.

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

    Grid-технологии решения информационных задач

    Уже известны разработки Ривкин М. ORACLE и коммерческая GRID, http://mrivkin.narod.ru., поддерживающие сложные распределенные базы данных для многоканального использования. Одним из проектов является разработка Oracle 10G, предназначенная для реализации коммерческой Grid-системы. Ее механизмы поддерживают следующие подсистемы и функции:

  • Grid хранения данных;
  • Grid серверов БД;
  • Grid серверов приложений;
  • Средства самонастройки узлов БД;
  • Систему управления Grid;
  • Средства для разделения информации между узлами Grid.
    •

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

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

    Но ведь именно в таком свете представляется проблема минимизации времени обращения к базе данных, изложенная в лекции 2! И там математически, на основе теории массового обслуживания, доказано, что активизация совокупной памяти БД посредством "встречной" циркуляции сегментов не только обеспечивает синхронизацию независимого многоканального доступа, но, главное, способствует медленному, вполне приемлемому росту времени выполнения запроса в зависимости от роста числа абонентов. (В противном случае это время быстро стремится к бесконечности.)

    Было показано, что одним из методов построения БД с циркулирующей информацией является объединение серверов в единую замкнутую систему — в "кольцо", по которому циркулируют сегменты этой базы. Абоненты же жестко связаны со своими серверами, обеспечивая распределенные, примерно равные, потоки запросов на каждый сервер. По каждому запросу должно учитываться среднее время ожидания нужного сегмента за счет его циркуляции.

    Тогда можно себе представить следующую схему функционирования гипотетической Ассоциации Web-серверов (рис. 13.1), объединенных на основе гигантской совокупной базы данных, мирового (или хотя бы корпоративного) масштаба. Учитывая все возрастающую мощность серверов и, главное, — средств передачи данных, можно уже сегодня ожидать значительного сокращения числа отказов при выполнении запросов, требующих сложного многоступенчатого трафика, зависящего от пропускной способности многих промежуточных пунктов.

    (рис 13.1) Ассоциация Web-серверов мирового информационного пространства

    Известные проекты Grid-технологии решения вычислительных задач

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

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

    Поучительным примером практического воплощения концепции Grid может служить глобальный проект China Grid, запущенный корпорацией IBM совместно с министерством образования Китая в целях повышения эффективности научно-исследовательской и образовательной деятельности ведущих китайских университетов. Grid-система, построенная на операционной платформе Linux, обеспечивает интегрированную, открытую, виртуализованную и автономную рабочую среду. Ею должно быть охвачено около 100 учебных заведений по всей стране, что вовлечет в проект более 200 тысяч студентов и преподавателей. Благодаря China Grid китайские университеты надеются сократить расходы на научно-исследовательские и опытно-конструкторские работы.

    Отечественным примером реализации рассматриваемой технологии может служить экспериментальный Grid-сегмент МГУ им. М.В.Ломоносова Экспериментальный Grid-сегмент МГУ им. М.В.Ломоносова. Руководство для пользователей. GRID — сеть для МГУ, ComNew.ru .

    В основе этого проекта лежит проект EDG ( EU Data GRID — европейский проект для физики высоких энергий, биоинформатики и системы наблюдений за Землей). В свою очередь, им используется проект Globus (разработчик — Argonne National Lab.), предоставляющий инструментальные средства связи, информационного обслуживания, безопасности, управления ресурсами, локального управления ресурсами и заданиями.

    Программное обеспечение Globus доступно и распространяется свободно.

    Проект EDG предполагает формирование вычислительных ресурсов на основе анализа сайтов организаций, подразделений, вычислительных узлов.

    Типичный сайт содержит следующие разделы информации.

  • Компьютер конечного пользователя, позволяющий пользователю взаимодействовать с Grid-средой, в частности, запускать задания и получать результаты.
  • Вычислительный элемент, представляющий ссылку на Grid-интерфейс к локальной системе управления пакетной обработкой (СУПО).
  • Рабочие узлы, входящие в состав вычислительного элемента и управляемые с помощью СУПО, что скрыто от пользователя.
  • Накопитель данных, управляющий единообразным доступом к любым устройствам памяти.
  • Брокер ресурсов, принимающий задания от пользователя, согласующий требования к ресурсам, которые содержатся в описании задания, с имеющимися, и направляющий задания на подходящий сайт вычислительного элемента.
  • Каталог реплик, поддерживающий базу данных о местах хранения оригинальных файлов и всех их копий.
    •

    Чтобы получить доступ к ресурсам МГУ-GRID, необходим компьютер с установленным пользовательским Grid-интерфейсом. Доступ в среду Grid происходит под именем, содержащимся в сертификате, и контролируется с помощью специальной программы-посредника (электронной доверенности), которая создается на ограниченный срок с помощью персонального ключа пользователя.

    Файл с описанием задания создается с помощью языка описания заданий ( Job Description Language ) и содержит необходимые входные данные, требования к ресурсам и сведения о том, куда должны быть записаны результаты обработки задания.

    Основы проектирования Центра Grid-технологий

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

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

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

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

    Первые опыты применения Grid-вычислений, сходные с опытом Тима Бернес-Ли, позволяли распределять между компьютерами мира работы, мало связанные между собой. Это были независимые эксперименты, большие массивы данных. Тем не менее, результаты возвращались и обрабатывались централизованно. Это — весьма простая схема распараллеливания по информации, примитивный аналог SPMD-технологии. В общем случае, даже при реализации этой технологии, являющейся воплощением распараллеливания по информации, невозможно избежать синхронизации по общим данным. Механизмы синхронизации должны работать быстро, что требует конкретного анализа возможности и целесообразности решения задач на основе виртуального ресурса Интернет. Это замечание говорит в пользу идеи концентрации вычислительных ресурсов.

    Сообразуясь с требованиями практической целесообразности, необходимо уяснить, какого типа бывают запросы вычислительного характера к Grid-системам (рис. 13.2).

    (рис 13.2) Типы запросов к системе Grid -вычислений

    Представим себе, что Пользователь заходит на сайт крупной GRID-Компании. Его желания могут быть следующими:

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

    Компания на основе своих возможностей согласует с пользователем предоставляемую услугу. Далее следуют договоренности финансового и юридического характера.

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

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

    Если условия ему не нравятся, пользователь обращается к сайту другой компании.

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

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

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

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

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

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

  • Домохозяйка просит о льготной помощи при расчете оплаты коммунальных услуг, исходя из текущего тарифа, с опережением указываемых расходов электроэнергии, горячей и холодной воды на случай непременного и скорого его повышения. Компания, в лице опытного консультанта, вступившего в диалог, располагая возможностями финансовых услуг по известным, постоянно обновляемым данным, предлагает оплатить не 112 квт, а 200, т.к. тариф в следующем месяце повысится, а указанный расход лежит в пределах критически допустимого. В этом смысле Grid-технология действительно вторгается в сферу коммунальных услуг.

    •

    На основе этих примеров можно заключить, что задачи нашей гипотетической Grid-Компании, которую точнее следует назвать "Центр GRID-Технологий", весьма широки и многообразны. Приведем ряд принципов его деятельности и некоторые пункты его обоснования.

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

  • Рассмотрим, какие вычислительные средства должны составлять собственную технологическую базу Центра.

    Центр, несомненно, должен объединять решение информационных и вычислительных задач. Поэтому наличие Web-серверов и участие их во Всемирной или Региональной ассоциации обязательно.

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

    Однако основной капитал Центра GRID-Технологий определяется собственными вычислительными средствами и сопутствующим оборудованием. Его комплектование и развитие определяется двумя возможными направлениями:

  • комплектацией на базе перспективных или разрабатываемых суперкомпьютеров и многопроцессорных вычислительных систем на их основе;
  • комплектацией на базе существующего, стремительно развивающегося парка компьютеров, рабочих станций и серверов, которые с помощью сопутствующего сетевого оборудования объединены в локальную вычислительную сеть, реализующую распределенные вычисления. Это направление, не отрицающее первое, несомненно, более перспективно.
    •

  • Центр должен быть укомплектован высококвалифицированными математиками-программистами и системотехниками, работающими по нескольким направлениям:

  • оперативное консультирование пользователей при "доводке" заданий;
  • разработка пакета прикладных программ и оболочек;
  • сотрудничество с пользователями при совместной разработке сложных программных и информационных проектов;
  • научно-исследовательская деятельность по развитию Grid-технологий и их применению;

    • Проанализировав материалы лекций, обозначим тот пакет прикладных программ и оболочек, который может быть предложен Центру GRID-Технологий. Это:

  • решение систем линейных уравнений;
  • задачи сортировки и поиска;
  • параллельный логический вывод;
  • параллельные технологии решения задач линейного программирования;
  • параллельные технологии решения задач целочисленного линейного программирования;
  • параллельные технологии решения транспортной задачи без ограничений и с ограничениями пропускной способности магистралей;
  • параллельные технологии нахождения максимальной пропускной способности сети;
  • методы точного решения задач распараллеливания как задач сетевого планирования и управления;
  • задачи оперативного параллельного планирования — задачи диспетчирования;
  • оболочка: конечно-разностные методы решения систем дифференциальных уравнений;
  • оболочка: параллельная технология решения оптимизационной задачи нелинейного программирования при линейных ограничениях;
  • оболочка: параллельная технология решения "плоской" оптимизационной задачи нелинейного программирования при нелинейных ограничениях (легко развивается на случаи большей размерности);
  • оболочка: параллельный ПРОЛОГ;
  • оболочка: расчет величины возбуждения нейронов нейросети.
    •

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

    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^