BC/NW 2006, №2, (9) :2.1

КОНФЛИКТНЫЕ СИТУАЦИИ ПРИ ПЕРЕДАЧЕ ДАННЫХ В МНОГОМАШИННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РЕГУЛЯРНОЙ СТРУКТУРОЙ

А. А. Дерюгин, И. А. Уткин

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

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

Связи между узлами вычислительной системы могут быть двух типов: в виде шин и в виде линков [1]. В случае шинных связей сигналы между ВМ передаются по одним и тем же линиям связи (проводникам) в двух направлениях (полудуплексные связи). В случае линковых связей сигналы между ВМ передаются в одном направлении по одним линиям связи (линкам), а в другом направлении по другим линиям связи (симплексные связи). В дальнейшем в данной статье будем рассматривать вычислительные системы только с линковыми связями (узлы такой вычислительной системы способны одновременно передавать и принимать данные) и c регулярной структурой.

Основными регулярными структурами являются:

· одномерная структура – кольцо;

· двухмерная структура – тор, витой тор, решетка;

· многомерные структуры – трехмерная решетка, трехмерный тор, гиперкуб и др.

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

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

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

Рассмотрим также существующие варианты передачи пакета данных:

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

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

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

· дополнительные аппаратные затраты на буферную память коммутаторов;

· более медленное по сравнению со вторым вариантом движение пакетов данных (поскольку они буферизуются в каждом узле).

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

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

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

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

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

Результатами работы модели будут являться коэффициент замедления работы ММВС

, (1)

и коэффициент загруженности линий связи

, (2)

где:

· k – общее число линий связи в вычислительной системе;

· NBL_i – число тактов, проведенных в блокировке i-й линией связи (то есть значение счетчика CTB на момент окончания моделирования);

· NSEND_i – число тактов, в течение которых осуществлялась передача по i-й линии связи (то есть значение счетчика CTS на момент окончания моделирования);

· T – общее число тактов модельного времени (входной параметр модели).

Оба коэффициента являются функцией параметра λ.

При передаче пакета данных необходимо знать адрес узла-приемника. Определение адреса узла-приемника имеет в модели вероятностный характер и осуществляется одним из трех способов:

· вероятность стать узлом-приемником пакета равна для всех узлов;

· вероятность стать узлом-приемником пакета линейно уменьшается с увеличением удаления от узла-источника;

· вероятность стать узлом-приемником пакета квадратично уменьшается с увеличением удаления от узла-источника.

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

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

Если узел находится в состоянии ожидания освобождения тракта (то есть им был сгенерирован пакет данных, но еще не был передан), то новые пакеты данных этим узлом генерироваться не будут – это и приводит к замедлению работы ММВС.

Также в работе модели примем следующие допущения:

· время передачи пакета не зависит от длины тракта (числа линий связи, входящих в тракт);

· установка тракта происходит мгновенно.

Итак, с учетом всего вышесказанного, обобщенный алгоритм работы модели выглядит следующим образом:

1. Ввод исходных данных для моделирования:

· вида структуры моделируемой системы (в рассматриваемом случае – кольцевой);

· числа узлов вычислительной системы;

· интенсивности передачи пакетов данных между узлами λ;

· числа тактов модельного времени T;

· способа определения адреса узла-приемника;

· способа задания приоритетов узлов.

2. Обнуление счетчиков CTW, CTS, CTB для всех линий связи.

3. Для первого узла вычислительной системы генерируется случайное число a, лежащее на отрезке [0,1] с равномерной плотностью распределения.

4. Если a < λ, значит, узел генерирует пакет данных в текущем такте модельного времени, определяется приоритет узла и адрес узла-приемника. Адрес узла-приемника определяется на основе значений a и λ в соответствии с одним из указанных выше способов.

5. Производится увеличение на 1 значения CTW для линий связи, входящих в тракт.

6. Пункты 3 – 5 выполняются последовательно для всех узлов.

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

8. После просмотра всех узлов делается подсчет блокировок линий связи. Для линий, у которых CTW не равен 0, произошла блокировка, и поэтому производится увеличение CTB на 1. Иными словами, остались пакеты данных – кандидаты на передачу по этой линии связи, которые не были переданы в текущем модельном такте, и переносятся на следующий

9. Производится увеличение на 1 счетчика тактов модельного времени. Если значение счетчика достигло значения T, то переход к п. 10. Иначе, возврат к п. 3.

10. Производится подсчет коэффициента замедления работы ММВС и коэффициента загруженности линий связи по формулам (1), (2) на основе полученных значений в CTB и CTS.

ЛИТЕРАТУРА

1. Дерюгин А. А. Коммутаторы вычислительных систем. – Статья в электронном журнале «Вычислительные сети» №1 (8) за 2006.

http://network-journal.mpei.ac.ru/cgi-bin/main.pl?l=ru&n=8&pa=3&ar=1