РАЗДЕЛ 1. ОСОБЕННОСТИ ОБРАБОТКИ В СИСТЕМАХ С МАСШТАБИРУЕМОЙ АРХИТЕКТУРОЙ
ВВЕДЕНИЕ. Масштабируемые системы и распределенные вычисления
Вопросы, связанные с распределением процессов вычислений, привлекают к себе внимание уже не один десяток лет. Однако с появлением и активным использованием масштабируемых архитектур многие проблемы приходится переосмыслить и взглянуть на них по-новому. Масштабируемость, наряду с надежностью, соотношением "стоимость/производительность", совместимостью и мобильностью программного обеспечения, является одним из важнейших требований к современным вычислительным системам. Она подразумевает возможность наращивания количества процессоров, объемов памяти и независимость пропускной способности коммуникационной подсистемы от числа процессорных узлов, участвующих в вычислениях. В настоящее время вопросы масштабирования находятся в поле зрения пользователей и разработчиков как параллельных систем, так и распределенной среды метакомпьютинга Grid. В таких системах поддержка образа общего ресурса сочетается с высокой степенью автономности процессорных узлов, не говоря уже о том, что в глобальной среде Grid на отдельных сайтах могут применяться различные локальные планировщики и отсутствует единая политика администрирования вычислительных ресурсов. Все это заставляет задуматься над новыми принципами организации вычислений и распределения ресурсов, обеспечением однозначности результата выполнения распределенных программ и эффективным планированием параллельных процессов.
|
|
|
К параллельным масштабируемым системам можно отнести мультикомпьютеры, вычислительные кластеры, симметричные мультипроцессоры с общей памятью (SMP – symmetrical multiprocessing), системы с распределенной разделяемой памятью (DSM – distributed shared memory) и массово-параллельные системы (MPP – massively parallel processing). Подобное деление основывается на проявлении функциональных возможностей систем с точки зрения конечного пользователя и ни в коей мере не претендует на классификацию по структурно-функциональным признакам. Более того, известные MPP-архитектуры перекрывают такие разновидности масштабируемых систем, как мультикомпьютеры (семейство SP фирмы IBM) и подклассы DSM – NUMA (суперкомпьютеры Cray T3D/3E) и ccNUMA (компьютеры компании SGI Onyx2, Origin 2000/3x00). Некоторые авторы подразделяют масштабируемые параллельные системы на MPP, SMP, ccNUMA, кластеры и распределенные системы.
В литературе можно найти различные подходы к построению структурно-функциональной систематизации компьютеров. Так, на основе классификации Флинна различаются следующие параллельные архитектуры: SIMD (Single Instruction Multiple Data), MIMD (Multiple Instruction Multiple Data), MISD (Multiple Instruction Single Data) и MSIMD (Multiple SIMD). Кроме этого, особо выделяются векторные и конвейерные системы, которые часто относят к подклассам SIMD (MSIMD) или MISD. Иногда к современным MIMD-архитектурам причисляют MPP-, SMP-системы и кластеры, причем кластеры и MPP-системы, в основном, различаются по степени согласованности набора прикладных программ и характеристикам коммуникационных сред. Нужно сказать, что систематизация Флинна, а также позднее появившиеся классификации Хокни, Фенга, Хендлера и Скилликорна не делают различий в организации распределенных вычислений с учетом взаимодействия процессов. Общим же свойством, обеспечивающим возможность повышения производительности масштабируемых систем, как раз и является распределенность процессов вычислений и распределенность данных. Это свойство характерно и для SMP-архитектур, если принять во внимание типичную иерархию "кэш процессора – основная память – подсистема ввода/вывода". Неудивительно, что не так давно появившиеся спецификации InfiniBand, RapidIO, развивающие идеи стандарта SCI (Scalable Coherent Interface) и спецификаций Next Generation I/O, Future I/O, основаны на моделях распределенной обработки. Выигрыш от распределения вычислений и данных определяется степенью параллелизма, организацией взаимодействия и планированием процессов.
|
|
|
По параллельным вычислениям и системам имеется обширная библиография. В последнее время появились работы, систематизирующие и развивающие отдельные положения в этой области. В настоящем курсе рассмотрим результаты, полученные в двух основных направлениях.
|
|
|
Одно из них – построение моделей распределенных вычислений, наиболее адекватных особенностям масштабируемых архитектур. Другое – выбор конфигурации ресурсов и планирование процессов на основе масштабируемой модели обработки с целью эффективной реализации прикладных программ.
Часто в литературе по параллельной обработке смешиваются или отождествляются понятия моделей (технологий, систем) программирования и моделей выполнения программ, т.е. моделей вычислений. В общем случае это приводит к тому, что детальный анализ структуры алгоритма и особенностей компьютерной архитектуры, на которой он реализуется, подменяется поиском системы программирования без учета того, насколько она адекватна архитектуре и решаемой задаче.
Модель вычислений служит связующим звеном между архитектурой и моделью программирования и в распределенных системах должна отражать взаимодействие процессов. Это взаимодействие представляется явно в некоторых моделях программирования и может быть организовано с помощью стандартных коммуникационных библиотек, например, MPI (Message Passing Interface) или PVM (Parallel Virtual Machine). Другие, более высокоуровневые модели освобождают программиста от выраженного управления параллельными процессами, примитивами передачи сообщений или синхронизации. Так, стандарт OpenMP может рассматриваться как модель программирования систем с разделяемой памятью и надстройка над библиотеками нитей pthreads, организуемыми с помощью интерфейса POSIX. Модель вычислений должна помогать в поисках ответа на вопрос: "Насколько эффективно реализуется программа на данной архитектуре?" Эффективность реализации может интерпретироваться как сбалансированность загрузки процессоров, согласованность степени параллелизма и трафика обмена данными, длительность простоя процессоров из-за отсутствия данных и т.д. Несмотря на большое разнообразие моделей выполнения программ, в масштабируемых системах чаще всего используются две из них – модель обмена сообщениями и модель общей памяти (промежуточная форма – прямой доступ к удаленной памяти). Особенности моделей однако не предполагают их реализаций на архитектурах соответствующего типа. Так, первая может быть надстроена над любой архитектурой. Вторая чаще всего применяется в SMP- и DSM-архитектурах, где программа рассматривается как система нитей, взаимодействующих через общие переменные и примитивы синхронизации. При этом программист имеет дело с привычным для него единым адресным пространством. Основная проблема – обеспечение согласованного состояния памяти. Модель обмена сообщениями позволяет избавиться от проблем разделения памяти и может быть надстроена над архитектурами с общей памятью. Реализация модели разделяемой памяти над архитектурами с передачей сообщений значительно сложнее.
|
|
|
В первой части курса рассматриваются недетерминированные модели распределенной обработки, когда процессы взаимодействуют через асинхронный обмен сообщениями. Недетерминизм означает, что могут иметь место разные истории выполнения программ на одних и тех же входных данных. Помимо поддержки недетерминизма, эти модели обогащаются таким свойством, как произвольная структурированность (неоднородность) сообщений. В модели общей памяти обмен осуществляется строго структурированными данными: слово, кэш-строка, страница и т.д. В неоднородных сообщениях возможно различное число компонентов (например, пакетов), а также различие компонентов по числу операндов. В частности, в SCI транзакции предусматривают передачу пакетов с блоками данных фиксированной и переменной длины. В среде Memory Channel пакеты данных могут иметь длину от 4 до 256 байтов. Недетерминированный обмен неоднородными сообщениями адекватно представляет многие черты функционирования масштабируемых систем, такие как массовый параллелизм, взаимодействия типа "точка-точка", коммутация пакетов. Однако подобное сочетание свойств требует исследования реализуемости моделей (проблем однозначности результата и блокировки вычислений) и алгоритмической разрешимости задач их анализа. Первый раздел курса носит вводный характер и посвящена особенностям функционирования масштабируемых систем, а также анализу требований к моделям вычислений и распределения ресурсов в таких системах. Во втором и третьем разделах рассматриваются различные формы модели обмена сообщениями, исследуются вопросы семантики и реализуемости вычислений. Существует ряд задач, для решения которых необходима оценка времени выполнения программ или их фрагментов. Например, прогнозирование динамики программ целевой архитектуры на основе моделирования в инструментальной среде, планирование и управление параллельными процессами и т.д. В четвертом разделе рассматриваются методы оценивания времени реализации фрагментированных программ.
Вторая часть курса посвящена задачам распределения ресурсов и планирования процессов на основе масштабируемой модели обработки. В пятом разделе обосновываются комбинаторные методы выбора целевой архитектуры вычислительных ресурсов по заданной спецификации (модели) прикладной программы. Эти методы могут использоваться для автоматизации отображения программ на архитектуру. Планирование процессов в масштабируемых средах, рассматриваемое в шестом разделе, принципиально отличается от составления расписаний на заданной архитектуре и связано с конфигурированием ресурсов под конкретную прикладную программу до начала вычислений, например, в ходе компиляции. Эта идея хорошо согласуется с парадигмой метакомпьютинга, согласно которой пользователь должен иметь полную иллюзию использования "чужих" ресурсов исключительно в интересах своего программного приложения. При этом, естественно, острой становится проблема эффективного использования дорогостоящих ресурсов путем обоснованного планирования вычислительных процессов. Один из возможных путей практической реализации этого подхода представлен проектом AppLeS (Application Level Scheduling): агент-планировщик формирует и координирует выполнение расписания для повышения эффективности работы приложения с точки зрения конечного пользователя. Для "настройки" ресурсов используются, как правило, эвристические подходы, дающие весьма приближенное решение. Иной путь – совместное планирование процессов и масштабирование ресурсов. В седьмом разделе эта идея развивается для порождения стратегии (множества вариантов) выполнения программы на основе совокупности критериев, включающей, например, стоимость и коэффициенты использования (загрузки) процессоров. Конкретный вариант плана процессов может выбираться из стратегии в зависимости от временных параметров контрольных событий, наступление которых обусловлено динамикой загрузки процессорных узлов и коммуникаций, пространственно-временной конкуренцией различных программ и т.п. Таким образом, несмотря на априорный характер формирования стратегии, управление ресурсами может осуществляться динамически. В этом же разделе излагается общий формализм, в рамках которого согласованно выполняются структурные преобразования и масштабирование модели вычислений.
В рамках одного курса вряд ли возможно охватить все проблемы, связанные с моделями вычислений и распределения ресурсов в масштабируемых системах. Так же ясно, что нельзя предложить некой универсальной модели распределенной обработки. В этом смысле представленный в курсе материал, с одной стороны, дополняет публикации последних лет, посвященные параллельным вычислениям и архитектурам параллельных вычислительных систем, а с другой, позволяет обозначить сравнительно малоизученные области в распределенных вычислениях.
ЧАСТЬ I . МОДЕЛИ ВЫЧИСЛЕНИЙ
РАЗДЕЛ 1. ОСОБЕННОСТИ ОБРАБОТКИ В СИСТЕМАХ С МАСШТАБИРУЕМОЙ АРХИТЕКТУРОЙ
Дата добавления: 2021-03-18; просмотров: 76; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!