Повышение эффективности мультипроцессорных систем, управляемых потоком дескрипторов данных



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

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

Improving of the efficiency of multi-processor systems, controlled by the data descriptors flow

V.I. Zhabin, V.V. Zhabina National Technical University of Ukraine "KPI", Kyiv, Ukraine

Annotation. The concept of dynamic allocation of tasks between multiprocessor systems computing modules that enables to identify automatically parallel branches in the process of task performance for maximum load of system computing resources is considered. The possibility to accelerate the data exchange between computing modules as wellas system reconfiguration in case of failure is shown.

Keywords. Parallel computing, descriptors flow, hidden parallelism, dynamic allocation of tasks, reconfiguration.

Введение.

Для систем управления и моделирования в реальном времени на длительность обработки данных накладываются внешние ограничения. Сокращение времени обработки информации может быть достигнуто путем применения параллельных систем. Продолжительность решения задач в параллельных вычислительных системах во многом определяется возможностью распараллеливания процессов с целью максимальной загрузки вычислительных узлов. Для разработки параллельных программ, созданы различные средства программирования. Кроме параллельных языков, таких как Ada, Java и ряд других, которые являются самостоятельными средствами для разработки параллельных программ, находят применение различные расширения последовательных языков (например, mpC, С-DVM, HPF, Fortran-DVM), а также библиотеки параллельного программирования (OpenMP, MPI, PVM и др).

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

В связи с этим важной задачей является создание методов динамического планирования вычислений в параллельных системах.

Недостатки статического планирования вычислений.

Пусть задан граф в ярусно-параллельной форме (ЯПФ) $G=({{V}_{i}},{{D}_{i}},{{W}_{i}})$, где ${{V}_{i}}=\{{{\nu}_{ij}}|j=\overline{1,{{k}_{i}}}\}$ – множество вершин $i$–го яруса ($i=\overline{1,s}$); ${{D}_{i}}$ – множество входных дуг вершин $i$–го яруса; ${{W}_{i}}=\{{{w}_{ij}}|j=\overline{1,{{k}_{i}}}\}$–множество весов вершин $i$–го яруса. Вершинам графа соответствуют операторы,осуществляющие определенное преобразование информации. Оператор $i$–го яруса активизируется только после завершения работы всеми операторами предшествующих ярусов, связанных с ним дугами. Каждой вершине ${{\nu }_{ij}}$ приписан вес ${{w}_{ij}}$, определяющий длительность преобразования информации.

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

Зачастую на этапе статического анализа программист определяет число параллельных процессов по ширине графа. Однако задача может обладать скрытым параллелизмом и распараллеливаться в значительно большей степени. Например, в ЯПФ с шириной два и более при отсутствии ограничений на значения весов ${{w}_{ij}}$ число активных вершин в один момент времени может достигать значения

\[N=2+\sum\nolimits_{i=1}^{s}{({{k}_{i}}-2)},\quad\quad\quad(1)\]

где $s$ - число ярусов, ${{k}_{i}}$ - число вершин на $i$-м ярусе.

На рис. 1 видно, что цепочка вершин, связанных двойными дугами (все вершины имеют только по одному входу), обеспечивает быструю активизацию вершин на следующем ярусе, а цепочка вершин, соединенных пунктирными дугами (все вершины имеют только по одному выходу), обеспечивает поэтапный переход вершин в пассивное состояние. В каждом ярусе, кроме первого и последнего, указанные функции выполняют по две вершины, а в первом и последнем ярусе – только по одной. В зависимости от значения весов одновременно в активном состоянии может находиться разное число вершин, но не более чем указано в (1). Вершины, которые могут одновременно находиться в активном состоянии, на рис. 1 затемнены (обозначения и веса вершин показаны выборочно, чтобы не затенять рисунок). В рассматриваемом случае при ширине ЯПФ, равной 5, одновременно могут выполняться 12 операторов. Очевидно, что число одновременно обрабатываемых операторов может существенно превышать ширину ЯПФ. Например, для регулярного ортогонального графа с шириной $k$ и длиной $s$ нетрудно показать, что число активных вершин может составлять $N=ks-2s+2$. В статике возможности широкого распараллеливания вычислений не очевидны.

Рис. 1. Ярусно-параллельная форма графа

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

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

Средства динамического распараллеливания вычислений позволяют выявить параллельные ветви,которые возникают непосредственно в процессе вычислений. С этой целью были предложены модели вычислений под управлением потоков данных (data flow) [1, 2].Распараллеливание в таких системах осуществляется преимущественно на аппаратном или микропрограммном уровне, что существенно разгружает операционную систему и уменьшает задержку при реализации мелкозернистых параллельных алгоритмов.Определяющим в данном случае является не порядок выполнения команд, а доступность данных для команды. Однако с увеличением зернистости алгоритмов существенно возрастают объемы пересылаемых данных, что делает такую модель вычислений неэффективной.

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

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

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

В основу концепции динамического распределения заданий между ВМ положены следующие положения.

  1. Задачи представляются с помощью потокового графа(его описанием), каждой i-й вершине которого соответствует определенный объем работы (вычислений), а каждой дуге –поток данных, необходимых для выполнения работы.

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

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

  4. Граф задачи разрабатывается без учета числаВМ в системе.

Потоковый граф G = (V, D) имеет множество вершин V и множество дуг D.

Каждой вершине соответствует задание(определенный объем работы, процесс), которое описывается дескриптором ${{V}_{i}}=\left\{{{N}_{i}},{{I}_{i}},{{P}_{i}},{{Q}_{i}} \right\}$, где ${{N}_{i}}$– имя данного дескриптора; ${{I}_{i}}$ – идентификатор задания (определяет функцию преобразования данных); ${{P}_{i}}=\left\{ {{p}_{ij}} \right\}$ – множество имен выходных данных (соответствуют дугам, выходящим из i-й вершины и входящим в j–ю вершину); ${{Q}_{i}}$–число дуг графа, входящих в i-ю вершину). Имя потока выходных данных ${{p}_{ij}}$может быть представлено кортежем ${{p}_{ij}}=\left\langle{{N}_{j}},{{n}_{ij}},{{Q}_{j}} \right\rangle $, где ${{n}_{ij}}$ имя входа j-й вершины графа, связанной с _i-_й вершиной.

Поток данных, соответствующий дуге графа, соединяющей j-ю вершину с i-й вершиной, характеризуется дескриптором данных ${{D}_{ij}}=\left\{ {{p}_{ij}},{{A}_{ij}}\right\}$, где ${{A}_{ij}}$– элемент адресации данных, определяющий расположение данных в памяти системы.

Из элементов дескрипторов в соответствии с определенной процедурой F формируются заявки на выполнение i-го задания $F\left({{V}_{i}},{{D}_{i}} \right)\to {{Z}_{i}}=\left\{ {{I}_{i}},{{P}_{i}},{{A}_{i}}\right\}$, где ${{A}_{i}}$ –множество элементов адресации данных для i-го задания.

Для формирования заявок ${{Z}_{i}}$ используется управляющий ВМ (УВМ), в котором создается таблица (массив объектов), i-я строка ${{S}_{i}}$ которой имеет вид ${{N}_{i}}:{{S}_{i}}=\left\langle{{I}_{i}},{{P}_{i}},{{A}_{i}},{{L}_{i}},{{C}_{i}},{{Q}_{i}} \right\rangle $, где ${{N}_{i}}$ имя строки; ${{C}_{i}}$ – счетчик дескрипторов, ${{L}_{i}}=\left\{ {{\delta }_{ij}} \right\}$ – признаки наличия поступивших дескрипторов данных. Число признаков в строке ${{S}_{i}}$ равно числу входных потоков данных ${{Q}_{i}}$.

В УВМ вводятся дескрипторы и исходные данные. При поступлении дескрипторов заданий в соответствующие позиции строк таблицы вводятся значения ${{I}_{i}}$ и ${{P}_{i}}$. При поступлении дескрипторов данных в соответствующие позиции строк записываются элементы множества ${{A}_{i}}$ и соответствующие им признаки ${{\delta }_{ij}}$. Полное накопление множества ${{A}_{i}}$ элементов адресации данных для задания определяется с помощью счетчика ${{C}_{i}}$. При поступлении любого дескриптора сравниваются значения ${{Q}_{i}}$ и ${{C}_{i}}$, затем ${{C}_{i}}$ увеличивается на единицу. Равенство указанных значений является условием активизации заявки.

Заявка передается в свободный исполняющий ВМ (ИВМ) по его запросу. При этом обнуляется счетчик ${{C}_{i}}$, то есть система готова для повторного формирования заявки с данным именем,если это необходимо. В системе одновременно могут решаться несколько задач.

На стадии формирования заявок между модулями пересылаются только короткие сообщения (дескрипторы). Потоки непосредственно данных перемещаются только на этапе выполнения заданий. В этом случае вычислительным процессом управляют стандартные средства операционной системы.

Минимизация пересылок данных.

В мультипроцессорных системах обмен данными между ВМ осуществляется через общее адресное пространство, которое физически может представляться разными модулями памяти с различным способом и временем доступа к ним [6]. Для ускорения вычислений необходимо стремиться к минимизации числа пересылок данных. Рассмотрим несколько таких возможностей.

ИВМ после выполнения задания возвращает УВМ только дескрипторы полученных данных. Сами данные при этом целесообразно оставлять в локальной памяти ИВМ, которая доступна другим ВМ. Это может быть коммуникационная память или вся локальная память ВМ при организации оконного доступа [6]. При такой организации вычислений для минимизации пересылок данных можно использовать весьма простой механизм. Как правило, элементы адресации ${{A}_{ij}}$ в явной или неявной форме содержат информацию о ВМ, в котором сохраняются данные. Для ИВМ среди готовых заявок ищется такая, в которой имеется максимальное число ссылок на его локальную память. Если поиск оказывается успешным, то отпадает необходимость, по крайней мере, одной пересылки данных.

Программно-аппаратная реконфигурация мультипроцессорных систем.

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

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

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

Между процессорными модулями распределены аппаратные средства, предназначенные для ускорения процесса реконфигурации системы при отказе процессоров. Они представляют эстафетную цепочку передачи сигнала назначения нового УПМ при отказе текущего и логические цепи голосования ИВМ.

Работоспособность УВМ проверяется совместным голосованием ИВМ. Стратегия голосования выбирается исходя из необходимого минимального числа работоспособных процессоров, которые,с учетом деградации системы, могут обеспечить решение поставленной задачи. Если система может выполнять свои функции при наличии g _изn ВМ (g Один из простых алгоритмов работы системы состоит в следующем. В начале каждого цикла УВМ запускает все ИВМ в широковещательном режиме. Затем выполняет свою программу. ИВМ запускают свой таймер и начинают выполнять свою программу, после завершения которой ожидают срабатывания своего таймера. Если при срабатывании таймера отсутствует сигнал запуска нового цикла со стороны УВМ, то ИВМ голосует за отключение УВМ. Отключенные ВМ в голосовании участия не принимают. При наличии не менее g голосов эстафетная цепочка передает функции УВМ следующему по цепочке ИВМ, который активизируется для работы в качестве УВМ.

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

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

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

Заключение.

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

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

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

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

Литература.

  1. Silva J. Design of processing subsystems for Manchester data flow computer / J.Silva,J.Wood // IEEE Proc. N.Y. – 1981. – Vol. 128, N 5. – P. 218 – 224.

  2. Watson R. A practical data flow computer /R.Watson, J.Guard // Com­puter. – 1982. – Vol. 15, N 2. – P. 51-57.

  3. Жабин В.И. Метод распараллеливания процессов в вычислительных системах / В.И.Жабин //Вiсник Нацiонального технiчного унiверситету України “Київський полiтехнiчний iнститут”. Iнформатика, управлiння та обчислювальна технiка. – 2000. – № 34. –С. 136-142.

  4. Жабин В.И. Реализация параллельных процессов в вычислительных системах / В.И.Жабин //Искусственный интеллект. – 2002. – №3. –С. 235-241.

  5. Жабин В.И. Реализация вычислений под управлением дескрипторов данных в мультипроцессорных системах / В.И.Жабин // Электронное моделирование. – 2003. –Т. 25, № 1. – С. 35-47.

  6. Жабин В.И. Архитектура вычислительных систем реального времени / В.И.Жабин. – К.: ТОО“ВЕК+”, 2003. – 176 с.
May 31, 2016