автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Управление потоками данных в системе коммутации мультипроцессора с динамическим распределением работ

ь 3 IV 2 9 и

ЛЕНИНГРАДСКИЙ ОРДЕНА ЛЕНИНА И ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ ЭЛЕКТРОТЕХНИЧЕСКИЙ ИНСТИТУТ ИМЕНИ 8,И. УЛЬЯНОВА ( ЛЕНИНА )

На правах рукописи

СЕРДЦЕВ АЛЕКСЕЙ АЛЕКСАНДРОВИЧ

УПРАВЛЕНИЕ ПОТОКАМИ'ДАННЫХ В СИСТЕМЕ КОММУТАЦИЙ МУЛЬТИПРОЦЕССОРА С ДИНАМИЧЕСКИЙ РАСПРЕДЕЛЕНИЕМ РАБОТ

Специальность: 05.13.13 - Вычислительные кагаины, комплексы,

еистеуы и сети

А в го рвфе.рат диссертации на соискание ученой степени кандидата технических на/к

Ленинград - 1990

)

Работа выполнена в Ивституте проблей вычислительной техники АН СССР

Научный руководитель -доктор технических наук профессор Манатов В.А.

Официальные■оппоненты: доктоп технических наук профессор Барашенкоа В.В. кандидат технических наук ст. науч. сотр. Бдагово В.В.

Ведущая организация - НИИ "Доаьта"

Защита состоится "* ^м^ях/а**- 199<3". в Ю '"часов иа заседания специализированного совета К 063.36.12 Ленинградского ордене Ленина и ордена Октябрьской Реъолвции электротехнического института имени В.И. Ульянова (Дешша) по адресу: 197022, Ленинград уд. Проф. Попова 5.

С диссертацией можно ознакомиться в библиотеке института.

Автореферат разослан " ' 199^ г,

Учений секретарь специализированного совета

Анисииов А.В.

- I -

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы. Развитие катодов параллельной обработки и успехи в области технологии СБИС приводи к созданию мультипроцессорных систем ( МПС ), которые содержат в своем составе десятки тысяч процессорных элементов ( ПЭ ). Взаимодействие отдельных компонент таких систем обеспечивается системой коммутации ( СК ), которая является обдим ресурсом для всех ПЭ. Значительная часть СК строится по принципу коммутации пакетов, что обусловлено малым объемом информации, передаваемой при обмене, и кроме того, это позволяет лучше использовать коммуникационную мощность.

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

В настоящей работе развивается подход,основанный на управлении потокамг (управление входной нагрузкой) в СК мультипроцессоров ( МП ) , предназначе ный для предотвращения деградации

производительности СК ЯП при возникновении "горячих точек".

Работа выполнялась в соответствии с исследованиями, проводимыми в Институте Проблем Вычислительной Техники АН СССР в об-д£ :тн разработки и исследования принципов построения высокопроизводительных многопроцессорных вычислительных систем.

Объектом исследований являют.:« системы коццутации мультипроцессоров с общей паиятьп и коммутацией пакетов.

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

В соответствии с поставленной целью » работе решаются следующие задачи:

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

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

- разработка рекоиендац*. по реализации предложенного метода;

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

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

Научная новизна:

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

- в рамках предложенного метода:

- разработан способ снижения накладных расходов с ис-

- 3 -

пользованием "селективного ограничения";

-определены условия справедливости "селективного ограничения".

Практическая ценность:

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

- разработана и реализована система коммутации мультипроцессора с динамический распределением работ.

Внедрение результатов работы. Результаты работы внедрены:

- в ИÜBT АН СССР : используются в экспериментальном образце мультипроцессора с динамически« распределением работ, создаваемой в Институте проблей вычислительной техники АН СССР;

- в СКВ МВТ АН СССР ':. использование результатов позволило сократить сроки размотки документации по теме 1-2/90 на 2 месяца.

Апробация работы. Основные положения я результаты доклады-

вались и обсуждались ¡га:

- шестом Всесоюзном семинаре по однородным вычислительным средам и систолически« структурам, Львов,1907г.

• - III Всесоюзной симпозиуме "Перспективы развития вычислительных систем*, г.Рига, 1989т.

- на ежегодных научно-практических конференциях научного центра по фундаментальный проблема» гычислительной техники и систем управления в 1989, I9SO ГГ.

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

Структура и объем работы. Диссертация состоит из введения, четырех разделов с выводами, заключения и двух приложений. Основной текст работы изложен на 124 страницах машинописного текста, содержит рисунка, 1 таблицу. Список литературы включает 84 наименования.

- V-

СОДЕРЙАНИЕ РАБОТЫ

Во введении обоснована актуальность Тепы,• охарактеризовано со"тояние вопроса, сформулированы цель и основные задачи исследования.

В первой разделе представлена классификация СК. Основными

классификационными признаками являются:

- способ коммутации ( коммутация каналов, коммутация пакетов) ;

- стратегия управления (централизованная, децентрализованная);

- топология коммутационной сети { КС >;

Быделен класс СК, характеризующийся коммутацией пакетов с децентрализованным управление«, как получивший наибольшее распространение при построении 1ШС. Входной нагрузкой < Вй > для та-кик СК являются запросы от центральных процессоров ПЭ, требующие формирования пакетов для доступа к общей памяти { ОН ). В отличии от однопроцессорных систем, Вй в МВС С tflAD (t.U)) является двумерной и характеризуется временный <t) и пространственным (U) распределением. Компонента У определяет адресацию к физически раздельным модуляи ОП.

Исследования, связанные с изучением программ мультипроцессоров с общей памятью, показали что доступ к ОП в обцец случае пе является пространственно-равномерный. Одним из источников появления этой неравномерности являются операции, используемые для синхронизации параллельный процессов, создающие дополнительную нагрузку на тот модуль памяти, где расположена синхронизирующая переменная. Было отиечено, что эта дополнительная нагрузка составляет в каждом ПЭ около 2% от общей ВН. Пока число ПЭ в системе не велико, этот эффект не заметен, tto если размерность системы увеличивается, то возникает ситуация, когда суммарная мнтенси ность запросов к модулю, где расположена синхронизирующая переменная, превышает интенсивность обслуживания в нем. Этот модуль становится "горячей точкой" ( hot ¿pot ). Необслуженные запросы-пакеты накапливаются в соседних буферах КС, образуя зону блокировки или "дерево насьщени! ' v. \?&В ¿atU2Qti.CH ). Так как

- в изменении одновременно существующих "горячих точек";

- в изменении числа ПЭ, имеющих % - I.

Исследования показали слабую устойчивость метода "селективного уничтожения" с обратной связьи при изменении параметров "горячей точки". Так,. например, изменение числа ^ с 64 до 256 при N=256, привело к падению с 0,94 до 0,56 ( Дцд ).

Следовательно, предложенный метод обеспечивает высокий ^ я (0,8 -0,9), когда параметры настройки Аад совпадает с реальной ситуацией. При возрастании относительная доля уничтожаемых пакетов, в обдеи числе передаваемых пакетов начинает возрастать, что увеличивает накладные -засходы, связанные с дополнитель'-ш потоком на КС И Дополнительный временем, необходимым для формирования а КП пакетов, которые уничтожаются.

Для уменьшения накладных расходов предлагается способ, основанный на селективной ограничении. Суть его состоит в том, что каждый ПЗ содержит в своем составе устройство селективного ограничена, которое ограничивает обработку, т.е. генерацию заявок, направленных к "горячей точке". В КП добавляется устройство ограничения, таблица "горячих" адресов и таймер. Сигнал "возникновение горячей точки" формируется аналогично методу "селективного уничтожения" с обратной связью. Основное отличие состоит в том, что вместе' с перезаписью элементов в очередь необслуженных заявок, адреса этих заявок, соответствующие адресам "горячих точек", переписываются Ь таблицу "горячих" адресов. При этом устройстго ограничения будет с некоторой вероятностью ограничивать (отбрасывать с некоторой вероятностью отказа Ротк ) долю потока, адресованного к "горячей точке". "Отброшенные" заявки сразу переписываются в очередь необслуженных заявок. Целью ограничения является установление равновесия между интенсивностью поступающего потока и потока обслуживания. Т.к. параметры "горячей точки" неизвестны» то процесс нахождения требуемой вероятности отказа происходит ш\рационно. В работе исследуется итерационный процесс с линейной стратегией увеличения ( уменьшения ) вероятности откази Ротк. В качестве модели процесса использовалась модель поведения автомата в случайной среде. В качестве сигналов "штраф" ( увели-

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

Можно показать что при введении "селективного ограниче-ия" «/ц определяется по следующей формуле {

О ___

* ~ -/[^^^(Ть^Тпп^^-Тпп/^а-^).

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

Ротк1 = Ротк^ ?и = 1....К .

где Ротк1 - вероятность отказа заявки из 1-го ПЭ при обслуживании в "горячей точке". Можно показать, что метод "селективного уничтожения" удовлетворяет условию справедливости ограничен 1". Введеное дополнительно "селективное ограничение* удовлет-

воряет требовании справедливости при равных начальных интенсив-ностях потоков от (1Э. При неравных начальных интенсивностях разность вероятностей отказа определяется

д Р - I JOTK; - PoTKji =■ ),/%/ • 1 •

Видно, что с увеличением степени отказа ("селективное ограничение" становится Солее справедливым. П'строение аналитической модели процесса "селективного ограничения" затруднительно, поэтому исследование его свойств проводилось при помощи имитационного моделирования.

Третий раздел посг-ицен исследованию свойств метода "селективного уничтожения" с обратной свяью при помощи имитационного моделирования. Имитационная модель МПС с пространственно-не равномерной Ш реализована в системе функционально-логического моделирования I1ISS. Модель включает в себя:

- групповой управляемый источник ВН SOURCE;

- очередь с уничтожение« FIFO;

- приемник - "горячая точка" DEST;

- устройство сбора иуатистнки CONTROL;

- подсистема формирования статистики STAT.

В основе методики проведения имитационного моделирования лежит метод повторных экспериментов. Расхождение с аналитически-и» результатами составляет 15%, что позволяет использовать аналитическую модель для инженерных расчатов.

Эксперимент подтвердил неустойчивость Jg метода "селективного унй .гонения" при изменении числа ПЭ, имеющих Введение дополнительного "селективного ограничения" резко увеличивает устойчивость >$е яри изменении параметров "горячей точки", за счет высоких значений jhd и Sc. Так изменение I от ЬЧ до 256 при {I I 256 приводит к незначительному уменьшению JR с 0,94 до 0,9а >.

Уведи' ния JW «ожн» добиться за счет "частичного уничтожения", при котором после каждого уничтожения в очере^ оставляется необходимое количество заявок для загрузки "горячей точ-

ки" во время периодов д t. Реализация "частичного уничтожения" требует использования вместо простой очереди для хранения необслуженных заявок буфера с произвольным доступом, так как подтверждения от оставленных заявок придут после окончания интервалов д t. При этом Jltt,! Sz сохраняют высокие значения при изменении Мб и Ъгч . Таким образом настроив А 24 на ГОШ можно Об( почить высокий л При изменении (увеличении)

"Частичное уничтожение" но уменьшает накладных расходов. Селективное ограничение" удерживает накладные расходы на одном уровне. Выигрьш в накладных раскодак пропорционален .

В четвертом разделе приводятся рекомендации m реализации мотода "селеьтивного уничтожения" . Преаде всего они касаются оценки целесообразности использования предложенного метода. Целесообразность определяется условиями эксплуатации ИБС, в частности вероятностью решения задач, приводящих к появлению "горячих точек". Требования по функционированию МВС при возникновении "горячих точек" могут быть сведены к двум случаям:

- обнаружить появление "горячей точки" и передать управление операционной системе;

- продолжать решение задачи по мере возможности.

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

- вариант I : "селективное уничтожение".,

- вариант 2 : "частичное уничтожение",

- вариант 3 : введение дополнительного "селективного ограничения",

- вариант к : вариант 2 * вариант 3.

Аппаратные затраты растут с увеличением номера варианта. Вариант I рекомендуется использовать При стабильных параметрах "горячей точки" и малых йнтеисивностях • Вариант 2 - при

нестабильных параметрах и также малых Tli^ . Вариант 3 - при высоких значениях "hiВариант Ч обеспечивает лучший JV 00 сРа-вг нию с вариантой 3.

Метод "селективного уничтожения" реализован в СК мультипроцессора с динамический распределение»! работ. Основными компонентами СК являются КП и коммутационный узел ( КУ ). КП реализован с использованием ткропрограииирувиого микропроцессорного набора К1<Ю4, КУ с применением ИС малой и средней степени интеграции. Дополнительные затраты на реализацию варианта I составили 200 микрокоманд, варианта 3 - 270. В раздоле представлено подробное описание алгоритмов работы компонентов СК, форматы передаваемых сообщений, интерфейсы. Обций объеи (аппаратуры СК составляет две платы формата 1)10 ( 280 х 112').

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

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ

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

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

3. Сформулированы условия справедливости ограничения. Показано, что метод "селективного уничтожения" с обратной связью удовлетворгт требованиям справедливости. Вводимое "селективное ограничение" удовлетворяет требованию справедливости пр1: равны., начальных потоках входной нагрузки от всех ПЗ. При неравенстве потоков справедливость увеличивается при возрастании степени ог-

раничения.

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

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

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

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

8. Получено'три положительных решения ВНЙЙГПЗ tro заявкам на изобретения:

1). Кричмара A.A., Сердцев A.A., Соколов A.B. Устройство для умножения ленточной матрицы на вектор. /Положительное решение по заявке ЫЧ0Ъ2Ъ10№-2к от 15,01.88 г.

2). Бмелин В.П., Манатов D.А., Пешков A.B., Сердцев A.A. Устройство управления нагрузкой коммутационной среды мультипроцессорной системы. Положительное решение по заявке

№4731178/24-2'» от II.07.1989.

3). Емелин В.П., Маматов Ю.А., Пешков A.B.. Сердцев A.A.

Устройство для коммутации сообщений. Полохчителыюе решение по заявке №1731179/21-24 от II.07.1989.

ПУБЛИКАЦИИ ИГ ТЕМЕ ДИССЕРТАЦИИ

I. О влиянии направления потоков данных на общее время вычислений в систолических структурах линейно-рекуррентн m алгоритмов. / A.A. Кричиара, П,Г. Романовский, A.A. Сердцев, A.B. Соколов // Моделирование и оптимизация вычислительных систем и процессов : Сб. статей.- Ярославль ЯрГУ., 1988 . С-бб-^З.

2. A.c. 1534471 СГПР НШ G06F 15/347 Устройство длг умножения ленточной матрицы на полную матрицу / A.A. Кричмара, П.Г. Роиановский, A.A. Сердцев (СШ3).- №4402311 /24-24; Заявл 15.01.88; Опубл. 26.01.90; Бюл. MI. -Ч с. ил.

3. Рекурсивная векторно-потоковая вычислительная система / ».А. Манатов, E.tt. Енелин, A.A. Сердцев и др. // Тез. докл. III Всесосзного симпозиума "Перспективы развития вычислительных систеи", г. Рига, 31 окт.- 2 ноябр. 1989 г. - Рига, 1989, - С. 39.

4. Система коыыутации рекурсивной векторно-потоковой системы /A.A. Сердцев, А.З. Виноградов, А.К. Кайеров, С.А. Лейиан - Ярославль, 1989. - 48 е.,- ( препринт / ИПВТ АН СССР ; №8 ).