Тезисы выступления

УДК 681.3.06

 РАСПРЕДЕЛЕННЫЕ ВЫЧИСЛЕНИЯ:
СОСТОЯНИЕ ДЕЛ, ПЕРСПЕКТИВЫ, ПРИЛОЖЕНИЯ*

 В.В. Топорков

Россия, Москва

Московский энергетический институт (технический университет)

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

 ------------------------------------------------------------------------------------------------------

 ОГЛАВЛЕНИЕ

  1. Масштабируемые системы и распределенные вычисления. 1

2. Модели вычислений и модели программирования. 2

3. Проблемы однозначности результата и блокировок вычислений. 3

4. Отображение  программ на архитектуру и планирование распределенных вычислений. 3

5. Заключение. 4

Л и т е р а т у р а. 5

1. Масштабируемые системы и распределенные вычисления

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

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

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

К параллельным масштабируемым системам можно отнести мультикомпьютеры, вычислительные кластеры, симметричные мультипроцессоры с общей памятью (SMP – symmetrical multiprocessing), системы с распределенной разделяемой памятью (DSM – distributed shared memory) и массово-параллельные системы (MPP – massively parallel processing). Подобное деление основывается на проявлении функциональных возможностей систем с точки зрения конечного пользователя и ни в коей мере не претендует на классификацию по структурно-функциональным признакам. Более того, известные MPP-архитектуры перекрывают такие разновидности масштабируемых систем, как мультикомпьютеры (семейство SP фирмы IBM), кластеры (МВС-1000) и подклассы DSM – NUMA (суперкомпьютеры Cray T3D/3E) и ccNUMA (компьютеры компании SGI Onyx2, Origin 2000/3x00). Исключение составляют, пожалуй, симметричные мультипроцессоры.

Нужно сказать, что систематизация Флинна, а также позднее появившиеся классификации Хокни, Фенга, Хендлера и Скилликорна [1] не делают различий в организации распределенных вычислений с учетом взаимодействия процессов. Общим же свойством, обеспечивающим возможность повышения производительности масштабируемых систем, как раз и является распределенность процессов вычислений и распределенность данных. Это свойство характерно и для SMP-архитектур, если принять во внимание типичную иерархию "кэш процессора – основная память – подсистема ввода/вывода".

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

2. Модели вычислений и модели программирования

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

Модель вычислений служит связующим звеном между архитектурой и моделью программирования и в распределенных системах должна отражать взаимодействие процессов. Это взаимодействие представляется явно в некоторых моделях программирования и может быть организовано с помощью стандартных коммуникационных библиотек, например, MPI (Message Passing Interface) или PVM (Parallel Virtual Machine). Другие, более высокоуровневые модели освобождают программиста от выраженного управления параллельными процессами, примитивами передачи сообщений или синхронизации. Так, стандарт OpenMP может рассматриваться как модель программирования систем с разделяемой памятью и надстройка над библиотеками нитей, организуемыми с помощью интерфейса POSIX. Модель вычислений должна помогать в поисках ответа на вопрос: "Насколько эффективно реализуется программа на данной архитектуре?" Эффективность реализации может интерпретироваться как сбалансированность загрузки процессоров, согласованность степени параллелизма и трафика обмена данными, длительность простоя процессоров из-за отсутствия данных и т.д.

Несмотря на большое разнообразие моделей выполнения программ, в масштабируемых системах чаще всего используются две из них – модель обмена сообщениями и модель общей памяти (промежуточная форма – прямой доступ к удаленной памяти). Особенности моделей однако не предполагают их реализаций на архитектурах соответствующего типа. Так, первая может быть надстроена над любой архитектурой. Вторая чаще всего применяется в SMP- и DSM-архитектурах, где программа рассматривается как система нитей, взаимодействующих через общие переменные и примитивы синхронизации. При этом программист имеет дело с привычным для него единым адресным пространством. Основная проблема – обеспечение согласованного состояния памяти [2]. Модель обмена сообщениями позволяет избавиться от проблем разделения памяти и может быть надстроена над архитектурами с общей памятью. Реализация модели разделяемой памяти над архитектурами с передачей сообщений значительно сложнее [5].

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

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

3. Проблемы однозначности результата и блокировок вычислений

  Известно, что чем менее строгая модель, в смысле точного порядка выполнения инструкций, принимается программистом, тем эффективнее и быстрее работают его программы в распределенных системах. Например, разновидности модели общей памяти с ослабленными требованиями к согласованности данных являются более производительными, чем модель последовательной непротиворечивости [2]. Но это одна сторона медали. Другая ее сторона – недетерминизм процессов вычислений: возможны различные истории выполнения программы на одних и тех же исходных данных. Естественным ограничением в этих условиях является требование однозначности результата.

В работе [3] предпринята попытка решить эту проблему на основе принципа взаимной транзитивности: любой допустимый процесс программы может быть началом или окончанием другого допустимого процесса. При этом оказывается, что в случае детерминированных вычислительных процессов конфлюэнтность, или аналог свойства Черча – Россера, в смысле определенном Келлером [6], является частным проявлением свойства взаимной транзитивности.

Еще одна проблема распределенных вычислений – блокировки, причем не все исчерпывается тупиками. В сложно организованных программах блокировки могут быть обусловлены и недетерминированным характером протекания процессов, и структурой программы, и структурой данных, которыми обмениваются процессы. Вопросы обнаружения и предотвращения таких ситуаций требуют специальных методов анализа свойств распределенных программ, в частности, использования потоковых моделей, представимых маркированными графами. В [7, 8] удалось выделить алгоритмически разрешимый подкласс таких моделей (М-сети) и свести проблему реализуемости распределенных программ к разметке М-сетей.

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

4. Отображение  программ на архитектуру и планирование распределенных вычислений

  Существует ряд задач, для решения которых необходима оценка времени выполнения программ или их фрагментов. Например, прогнозирование динамики программ целевой архитектуры на основе моделирования в инструментальной среде, планирование и управление параллельными процессами и т.д. В [9] предлагаются и описываются методы оценивания времени реализации фрагментированных программ. Причем эта оценка производится с учетом природы операционной системы, например, многозадачности, характерной для LINUX, и особенностей архитектурных решений современных процессоров.

Автоматизация отображения прикладных программ на архитектуру, выбор вида целевой архитектуры требуют специальных инструментальных средств. Одно из таких средств было разработано в середине 90-х годов прошлого столетия на кафедре Вычислительной техники МЭИ. Со времени первого аннонсирования [10] система GSSS была существенно развита и прошла апробацию в ряде проектов.

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

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

Здесь уже не "работают" классические расписания [15]: прикладную программу и аппаратную платформу можно рассматривать как программно-аппаратную среду, которая соответствующим образом настраивается, конфигурируется для ускорения вычислений, балансировки загрузки процессоров и т. д. [16-18].

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

Один из возможных путей практической реализации этого подхода представлен проектом AppLeS (Application Level Scheduling): агент-планировщик формирует и координирует выполнение расписания для повышения эффективности работы приложения с точки зрения конечного пользователя [19]. Для "настройки" ресурсов используются, как правило, эвристические подходы, дающие весьма приближенное решение.

Иной путь – совместное планирование процессов и масштабирование ресурсов [16-18], которые в книге [3] нашли выражение в так называемой метафоре масштабирования: программа и ресурс рассматриваются как единая настраиваемая среда вычислений.

Для воплощения этой метафоры разработан специальный аппарат – метод критических работ [18].

Метафора масштабирования предполагает развитие с целью порождения стратегии (множества вариантов) выполнения программы на основе совокупности критериев, включающей, например, стоимость и загрузку процессоров [16, 18]. Конкретный вариант плана процессов может выбираться из стратегии в зависимости от временных параметров контрольных событий, наступление которых обусловлено динамикой загрузки процессорных узлов и коммуникаций, пространственно-временной конкуренцией различных программ и т.п. Таким образом, несмотря на априорный характер формирования стратегии, управление ресурсами может осуществляться динамически.  

5. Заключение

  В рамках одного доклада вряд ли возможно охватить все проблемы, связанные с моделями вычислений и распределения ресурсов в масштабируемых системах. Так же ясно, что нельзя предложить некой универсальной модели распределенной обработки. Было выделено несколько проблем:

– недетерминизм и блокировки вычислений;

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

– управление распределенными процессами и ресурсами.

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

Л и т е р а т у р а  

1. Воеводин В.В., Воеводин Вл. В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.

2. Таненбаум Э., Ван Стеен М. Распределенные системы. Принципы и парадигмы. - СПб.: Питер, 2003. - 880 с.

3. Топорков В.В.  Модели  распределенных  вычислений.  - М.: Физматлит, 2004. - 320 с.

4. Фостер Я., Кессельман К., Тьюке С. Grid-службы для интеграции распределенных систем // Открытые системы. - 2003. - № 1. - С. 20-26.

5. Корнеев В. Архитектуры с распределенной разделяемой памятью // Открытые системы. - 2001. - №3. - С. 15-23.

6. Keller R.M. A fundamental theorem of asynchronous parallel computation // Proceedings of the Sagamore Comput. Conf. Parallel Process. Lecture Notes on Computer Science. Berlin: Springer-Verlag. - 1975. - Vol. 24. - P.102-112.

7. Топорков В.В. Реализуемость потоковых моделей распределенных программ // Программирование. - 2001. - №5. - С. 18-25.

8. Топорков В.В. Проблема разрешимости задачи анализа потоковых моделей программ // Программирование. - 2003. - №3. - С. 3-14.

9. Топорков В.В., Топоркова А.С., Богданов Д.В. Прямые измерения времени выполнения программ на RISC-процессорах // Информационные технологии. - 2002. - №10. - С. 2-8.

10. Toporkov V.V. Hardware-software cosynthesis by metaoperator net // Proceedings of the VHDL-forum for CAD in Europe at the EURO-DAC'94, Grenoble, France. - 1994. - P. 17-27.

11. Toporkov V.V. An adaptive strategy in hardware-software codesign for real-time embedded systems // Proceedings of the Workshop on Design Methodologies for Microelectronics with Special Day on Co-operation and Vienna Industrial Day: Institute of Computer Systems, Slovak Academy of Sciences. - 1995. - P. 187-194.

12. Toporkov V. V. Performance-complexity analysis in hardware-software codesign for real-time systems // Proceedings of the European Design Automation Conf., Brighton: UK, IEEE CS Press. - 1995. - P. 340-345.

13. Toporkov V.V. The MPEI approach to heterogeneous system design: co-operation and technology transfer opportunities // Proceedings of the Special Day on pan-European Co-operation and Technology Transfer, Zakopane, Poland: IEEE CS Press. - 1996. - P. 117-124.

14. Toporkov V.V. Dataflow-dominated system-level functional partitioning // Proceedings of the 42nd International Scientific Colloquium, Ilmenau, Germany. - 1997. - Vol. 1. - P. 486-491.

15. Теория расписаний и вычислительные машины / Под ред. Э.Г. Коффмана. - М.: Наука, 1984. - 334 с.

16. Топорков В.В., Топоркова А.С. Оптимизация характеристик вычислительных процессов в масштабируемых ресурсах // Автоматика и телемеханика. - 2002. - №7. - C. 149-157.

17. Топорков В.В. Разрешение коллизий параллельных процессов в масштабируемых вычислительных системах // Автоматика и телемеханика. - 2003. - №5. - С. 180-189.

18. Топорков В.В. Оптимизация распределения ресурсов в системах жесткого реального времени // Известия РАН. Теория и системы управления. - 2004. - №3. - С. 57-67.

19. Berman F. High-performance scheduling // The Grid: Blueprint for a New Computing Infrastructure. Eds. I. Foster, C. Kesselman. San Francisco: Morgan Kaufmann, 1999. - P. 279-307.

Организаторы  семинара

"Виртуальный компьютерный музей" \ Директор Музея, главный редактор PC Week/RE, Пройдаков Эдуард Михайлович.
     "Виртуальная школа компьютерных технологий" \  Автор проекта  к.т.н. Сазанов Владимир Михайлович.

Кафедра "Вычислительная техника" МЭИ \ Зав. кафедрой д.т.н., проф. Топорков Виктор Васильевич.

Координатор  проекта  к.т.н. Сазанов В. М. *