Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

Методы, алгоритмы и специализированные устройства ускоренного планирования размещения параллельных программ в отказоустойчивых матричных мультипроцессорах Борзов Дмитрий Борисович

Методы, алгоритмы и специализированные устройства ускоренного планирования размещения параллельных программ в отказоустойчивых матричных мультипроцессорах
<
Методы, алгоритмы и специализированные устройства ускоренного планирования размещения параллельных программ в отказоустойчивых матричных мультипроцессорах Методы, алгоритмы и специализированные устройства ускоренного планирования размещения параллельных программ в отказоустойчивых матричных мультипроцессорах Методы, алгоритмы и специализированные устройства ускоренного планирования размещения параллельных программ в отказоустойчивых матричных мультипроцессорах Методы, алгоритмы и специализированные устройства ускоренного планирования размещения параллельных программ в отказоустойчивых матричных мультипроцессорах Методы, алгоритмы и специализированные устройства ускоренного планирования размещения параллельных программ в отказоустойчивых матричных мультипроцессорах Методы, алгоритмы и специализированные устройства ускоренного планирования размещения параллельных программ в отказоустойчивых матричных мультипроцессорах Методы, алгоритмы и специализированные устройства ускоренного планирования размещения параллельных программ в отказоустойчивых матричных мультипроцессорах Методы, алгоритмы и специализированные устройства ускоренного планирования размещения параллельных программ в отказоустойчивых матричных мультипроцессорах Методы, алгоритмы и специализированные устройства ускоренного планирования размещения параллельных программ в отказоустойчивых матричных мультипроцессорах Методы, алгоритмы и специализированные устройства ускоренного планирования размещения параллельных программ в отказоустойчивых матричных мультипроцессорах Методы, алгоритмы и специализированные устройства ускоренного планирования размещения параллельных программ в отказоустойчивых матричных мультипроцессорах Методы, алгоритмы и специализированные устройства ускоренного планирования размещения параллельных программ в отказоустойчивых матричных мультипроцессорах Методы, алгоритмы и специализированные устройства ускоренного планирования размещения параллельных программ в отказоустойчивых матричных мультипроцессорах Методы, алгоритмы и специализированные устройства ускоренного планирования размещения параллельных программ в отказоустойчивых матричных мультипроцессорах Методы, алгоритмы и специализированные устройства ускоренного планирования размещения параллельных программ в отказоустойчивых матричных мультипроцессорах
>

Диссертация - 480 руб., доставка 10 минут, круглосуточно, без выходных и праздников

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Борзов Дмитрий Борисович. Методы, алгоритмы и специализированные устройства ускоренного планирования размещения параллельных программ в отказоустойчивых матричных мультипроцессорах: диссертация ... доктора технических наук: 05.13.05 / Борзов Дмитрий Борисович;[Место защиты: Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Юго-Западный государственный университет»].- Курск, 2015.- 366 с.

Содержание к диссертации

Введение

1. Анализ методов, алгоритмов и специализированных устройств планирования размещения подпрограмм в мультипроцессорных системах 18

1.1 Обзор мультипроцессорных систем 18

1.2 Задача размещения программ в мультипроцессорных системах 21

1.3 Классификация методов и алгоритмов размещения 23

1.4 Метаэвристические алгоритмы планирования размещения 1.4.1 Муравьиные алгоритмы 30

1.4.2 Алгоритм роящихся частиц 35

1.4.3 Пчелиный алгоритм поиска варианта размещения 36

1.4.4 Планирование размещения на основе генетических алгоритмов 1.4.5 Планирование размещения методом «гильотинного» разреза 49

1.4.6 Планирование размещения параллельных программ методом свертки 50

1.5 Анализ целесообразности аппаратной реализации задачи размещения 1.6 Выводы 71

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

2.1 Обобщенная постановка задачи разбиения 72

2.2 Формализованная постановка и математические модели задачи разбиения 75

2.3 Методы разбиения в линейных, условных и циклических участках последовательных программ 89

2.4 Алгоритмы разбиения линейных, условных и циклических участков последовательных программ 92

2.5 Выводы 99

3. Математическая модель, методы и алгоритмы ускоренного планирования

размещения параллельных программ в отказоустойчивых матричных

масштабируемых мультипроцессорах 100

3.1 Обобщенная постановка задачи планирования размещения программ в матричных масштабируемых мультипроцессорах 100

3.2 Формализованная постановка задачи размещения программ в масштабируемых мультипроцессорах 104

3.3 Подход планирования размещения программ в матричных масштабируемых мультипроцессорах 106

3.4 Методика и алгоритмы планирования размещения программ в масштабируемых мультипроцессорах 108

3.5 Выводы 117

4. Математическая модель, методы и алгоритмы оператвного переразмещения параллельных программ в матричных масштабируемых мультипроцессорах с учетом отказов 118

4.1 Анализ средств обеспечения отказоустойчивости мультипроцессорных систем 118

4.2 Метод оперативного переразмещения программ в отказоустойчивых мультикомпьютерных системах

4.2.1 Обобщенная постановка задачи переразмещения программ 131

4.2.2 Математическая постановка задачи отказоустойчивого переразмещения 133

4.3 Алгоритмы переразмещения программ при отказах процессоров и

межпроцессорных связей 137

4.3.1 Алгоритм замены отказавшего процессора резервным 137

4.3.2 Алгоритм переразмещения при отказе процессора и межпроцессорной связи 138

4.4 Выводы 143

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

5.1 Методы и методики постановки эксперимента 144

5.2 Оценка эффективности алгоритмов разбиения 146

5.3 Оценка эффективности алгоритмов размещения программ в мультипроцессорных системах 147

5.4 Оценка эффективности алгоритмов отказоустойчивого переразмещения программ в мультипроцессорных системах

5.4.1 Программная модель процедур переразмещения с учётом отказа процессора и/или отказа линка 159

5.4.2 Результаты исследования эффективности алгоритма планирования размещения 161

5.4.3 Результаты исследования эффективности алгоритма переразмещения с учетом отказа процессора и/или отказа линка 166

5.5 Выводы 169

6. Аппаратные средства планирования размещения параллельных программ в отказоустойчивых масштабируемых мультипроцессорных системах 171

6.1 Анализ подходов к аппаратной реализации задачи планирования размещения программ в мультипроцессорных системах 171

6.2 Алгоритмы, структурные и функциональные схемы специализированного устройства разбиения

6.2.1 Функциональная организация устройства формирования матрицы неполного параллелизма 183

6.2.2 Алгоритмы работы устройства разбиения 185

6.2.3 Алгоритмы работы вычислительных модулей 190

6.2.4 Анализ временной и аппаратной сложности устройства разбиения 196

6.3 Структурные и функциональные схемы планирования размещения

программ в мультипроцессорных системах 199 6.3.1 Структурная организация специализированного акселератора

планирования размещения программ 201

6.3.2 Алгоритмы функционирования специализированного устройства 203

6.3.3 Устройство проверки качества размещения задач 207

6.4 Устройство оперативного переразмещения программ в

отказоустойчивых мультипроцессорных системах 217

6.4.1 Принцип аппаратной реализации переразмещения подпрограмм в отказоустойчивых мультикомпьютерах 217

6.4.2 Структурная организация акселератора переразмещения 219

6.4.3 Алгоритмы функционирования акселератора 220

6.4.4 Устройство замены отказавшего модуля резервным 224

6.4.5 Оценка производительности и быстродействия акселератора 230

6.4.6 Устройство поиска кратчайшего пути обхода межпроцессорной связи 234

6.4.7 Оценка аппаратной и временной сложности устройства поиска кратчайшего пути 240

6.5 Выводы 245

Заключение 247

Библиографический список 251

Задача размещения программ в мультипроцессорных системах

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

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

Исходный (размещаемый) процесс представляется в виде направленного графа или гиперграфа, заданного соответствующей матрицей смежности. Строки и столбцы матрицы отмечаются номерами вершин графа. На пересечении і-й строки и j-го столбца ставится единица, если і-ю и j-ю вершину соединяет дуга, направленная из вершины і в вершину], и ноль - в противном случае. Матрица смежности отображается однородной средой, содержащей mxn элементов (где тип- число процессов).

Критерий оценки степени удаленности размещения На рис. 1.19а представлен вариант гипотетического исходного размещения, а рис. 1.19б задает матрицу смежности для исходного размещаемого графа. Рис. 1.19в описывает вариант размещения после перестановки модулей 2 и 3, а рис. 1.19г отображает соответствующую ему матрицу смежности. На рис. 1.19а и 1.19в кружками обозначены гипотетические модули, а цифры внутри модулей - их соответствующие номера. Числа над пунктирными линиями обозначают степени загрузки канала между смежными модулями. Из рис. 1.19а видно, что канал между модулями 2-3 и 3-4 имеет наибольшую загрузку. Качество размещения улучшается при перестановке местами модулей 2 и 3 (рис. 1.19в). В этом случае качество размещения улучшается и для остальных пар модулей. Максимальная степень загрузки канала при этом уменьшается. Тем самым при применении предлагаемого устройства в вычислительных системах - уменьшается общее время выполнения задачи.

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

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

Исходная (размещаемая) задача (процесс, алгоритм) представляется в виде ориентированного невзвешенного графа G= Х,E , вершины хі є X которого соответствуют подзадачам (подалгоритмам), а дуги е ЕсХхХ за 65 дают управляющие и/или информационные связи между подзадачами. Размещаемый граф G задается соответствующей матрицей смежности. Строки и столбцы матрицы отмечаются номерами вершин графа. На пересечении i-й строки и j-го столбца ставится единица, если i-ю и j-ю вершину соединяет дуга, и ноль – в противном случае.

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

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

Исходный (размещаемый) процесс (задача, алгоритм) представляется в виде ориентированного невзвешенного графа (орграфа) или гиперграфа G = X,U , вершины хі є X которого соответствуют подзадачам (процессам), а дуги еуєЕсХхХ задают связи между подзадачами (процессами). Граф G

задается матрицей смежности А. Строки и столбцы матрицы отмечаются номерами вершин графа. На пересечении і-й строки и j-го столбца ставится единица, если і-ю и j-ю вершину соединяет дуга, направленная из вершины і в вершину], и ноль - в противном случае.

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

Между каждой парой процессоров матрицы (2.2) в общем случае существует множество маршрутов передачи сообщений, которые обеспечивают разное время доставки данных между соответствующими подпрограммами. В рамках решаемой задачи интерес представляют кратчайшие маршруты, гарантирующие минимум указанного времени. Для описания множества таких маршрутов вводится матрица длин LM= dtj , элемент dtj которой численно равен длине кратчайшего маршрута между процессорами, в которых размещены подпрограммы х. и х..

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

Сущность созданного метода заключается в двухэтапном решении задачи переразмещения. На первом этапе вычисляется теоретически минимальная наибольшая частная коммуникационная задержка gmin из предположения, что граф Ф размещается в мультикомпьютере без учета ограничений связности подпрограмм (дуги графа Ф «укладываются» наилучшим образом, т.е. так, что более высоким значениям mtj соответствуют меньшие длины маршрутов dtj). На втором этапе отыскивается вариант размещения Д, кото 136 рый минимизирует отклонение - min и, таким образом, дает локальный минимум наибольшей коммуникационной задержки.

В случае наличия в мультикомпьютере отказавших процессоров [59-65] размещение вычисления по формуле (4.4) для различных отображений вида (4.3) проводятся с учетом неоднородности топологической структуры. Например, при отказе процессора pl 2 выполняется перебор отображений вида (рис. 4.2):

В этом случае учитывается, что отказавший процессор замещается резервным, например, процессором l1,2 и изменяется множество допустимых маршрутов передачи данных.

Алгоритм замены отказавшего процессора резервным С учетом приведенных выше замечаний, алгоритм замены отказавшего модуля резервным состоит из следующих шагов: ЗАГРУЗИТЬ матрицы AM и LM; УСТАНОВИТЬ zv=etl=ktl=0,i = 1,nj = 1,n; ЦИКЛ по всем процессорам ptj є Р ЕСЛИ 3p9GP:z9=1, то найти в матрице 0 элемент 0st = 0 такой, что ш - s\ 1) л (\j -1\ 1); ЕСЛИ такой 9st найден, то принять 9st = 1, lst=Pij (замещение успешно), иначе необходим останов системы; КОНЕЦ ЦИКЛА

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

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

Важным этапом созданного метода переразмещения является определение теоретической нижней оценки наибольшей частной коммуникационной задержки juminmax, относительно которой осуществляется минимизация времени межпроцессорного обмена при выборе варианта размещения программ согласно постановке задачи (п. 4.2.2). Для вычисления указанной оценки используется следующий алгоритм. 1. Переписать все значения dkl 0 из матрицы LM в вектор LM в порядке невозрастания, т.е. соблюдая условие: \/zl Ф22: d\ d L = zx z2, где zx,z2 - порядковые номера значений dk4,,dkr в векторе LM . 2. Переписать все значения mtJ Ф 0 из матрицы AM в вектор AM в порядке неубывания, т.е. соблюдая условие: \fzx Ф Z2 : nf}, nf?f ozx z2, где zx,z2 - порядковые номера значений т.,,,т,, в векторе AM . 3. По векторам LM и AM вычислить оценку juminmax, используя фор мулу: Мшптах ахЦ /}, (4.6) где ml,d2u - элементы векторов AM и LM , расположенные в одинаковых позициях. В дальнейшем переразмещение сводится к выполнении серии перестановок столбцов и строк матрицы AM с тем, чтобы достичь наибольшего приближения к оценке juminmax. После каждой перестановки вычисляется значе 139 ние тах{тіґсіу}. Если найденное значение больше предыдущего, то перестановки продолжаются от предыдущего варианта, иначе далее рассматривается текущий вариант.

В качестве примера работы разработанных алгоритмов, рассмотрим мультипроцессорную систему 2x2 с отказавшим модулем 2 (рис. 4.3) и соответствующую ей ММР (рис. 4.4).

Рабочее окно программы Программная система обладает следующими функциональными возможностями (рис. 5.1): ввод МОИ и ММР; показывающий полученный вариант размещения; расчет и вывод на экран векторов М и D; поиск размещения для матриц процессоров размерами 4x4 и 8x8; задания порога г]п\ работы с направленными и ненаправленными связями в матрице ММР.

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

Обобщенная постановка задачи переразмещения программ

Назначение элементов и блоков предлагаемого устройства заключается в следующем. Генератор 14 импульсов предназначен для генерации тактовых импульсов устройства. ОЗУ 15 Р1 необходимо для моделирования мультикомпьютера состоящего из двух непересекающихся подмножеств: m = P L, где P - множество основных процессоров, а L - множество резервных процессоров. Идентифи каторы процессоров множества P упорядочим в виде матрицы P ОЗУ 16 z служит для определения исправных процессоров. В нем в ячейке матрицы хранится код единицы, если процессор не исправен и о - если исправен. ОЗУ 17 0 показывает наличие резервных процессоров. Аналогично ОЗУ 16 хранит единицу, если резервного процессора ячейке нет и о - если есть. Регистр 18 необходим для хранения кода нуля, необходимого для сравнения с кодами, полученными из матрицы 16. Первый 19 элемент сравнения необходим для сравнения очередного кода, полученного из ОЗУ 16 с кодом нуля из регистра 18. Второй 20 элемент сравнения предназначен для сравнения кода нуля из регистра 16 с очередным кодом, полученным из ОЗУ 17. Дешифратор 21 выбора необходим для выбора счетчика, необходимого для операций с выбором свободного резервного процессора в случае выхода из строя основного. Первый 22 счетчик строки необходим для выбора номера строки выше на одну строки, в которой расположен отказавший процессор. Второй 23 счетчик строки служит для выбора номера строки ниже на одну той, в которой расположен отказавший процессор. Первый 24 счетчик столбца предназначен для выбора столбца резервного процессора на один правее столбца, в котором расположен отказавший процессор. Второй 25 счетчик столбца необходим для выбора столбца резервного процессора на один левее столбца, в котором расположен отказавший процессор. Счетчик 26 номера предназначен для подсчета номера выбираемого счетчика 22, 23, 24, 25, необходимого для проведения операций с заменой основного процессора резервным. Первый 27 элемент ИЛИ служит для подачи единичного импульса на вход we разрешения записи ОЗУ Р1.

Второй 28 и третий 29 Элементы ИЛИ необходимы для подачи единичных сигналов на адресные входы А1 и А2 ОЗУ 17 0, необходимые для выбора и последующей проверки наличия соответствующего резервного процессора. На вход 30 строки подается из ВУУ номер строки, в который отказал неисправный процессор с последующей подачей на соответствующей адресные А1 и А2 входы ОЗУ 15 и 16. На вход 31 столбца подается номер столбца, в котором отказал неисправный процессор с последующей подачей на соответствующей адресные А1 и А2 входы ОЗУ 15 и 16. Выход 32 ОЗУ 15 Р1 с соответствующим входом ВУУ устройства. Вход 33 регистра служит для соединения соответствующего входа со входом ВУУ устройства. Выход 34 переполнения счетчика 24 столбца служит для подачи на ВУУ сигнала переполнения, что одновременно сообщает о завершении работы устройства.

Регистр 35 единицы предназначен для хранения код числа единица («0…01»). Триггер 36 выбора служит для выбора счетчика, предназначенного для выбора резервного процессора. Вход S 37 установки необходим для установки в единицу триггера 36 выбора. На начальном этапе элементы и блоки устройства находятся в следующем состоянии. В ОЗУ 15 хранится матрица Р1 процессорных модулей и матрица L резервных процессоров, так как показано на рис. 6.32.

Работа устройства происходит следующим образом. В случае появления на входах j и / двоичных кодов происходит внештатная ситуация в системе логического управления (СЛУ), вызванная сбоем процессора. В этом случае, необходима оперативная реакция системы на отказ, связанная с применением аппаратных средств, предлагаемых в данной работе. В этом случае, данные коды с входов подаются на адресный вход А1 ОЗУ 16 и ОЗУ 15, на установочный s-вход ОЗУ 24 и 23. В результате в счетчике 23 и 24 устанавливается код строки / матрицы процессоров, в которой отказал процессор, в счетчиках 22 и 25 - код столбца матрицы процессоров, к которой отказал данный процессор. В то же время на адресный вход А1 ОЗУ 16 поступает код столбца, в которой произошел отказ. Одновременно и со входа 30 код строки у подается на адресный вход А2. Одновременно с этим эти же коды поступают на установочные s-входы счетчиков 23 и 24, устанавливая в них начальные значения, которые фактически являются координатами отказавшего процессора, необходимые для дальнейшего переназначения на резервный процессор. Тем не менее, изменений в ОЗУ 15 не происходит из-за отсутствия единичного импульса на вход we разрешения записи.

Первый тактовый импульс с выхода генератора 14 импульсов поступает на вход разрешения выдачи oe ОЗУ 16, а так как на адресных входах А1 и А2 присутствуют соответствующие коды, то значение с выхода ОЗУ 16 подается на первый вход элемента 19 сравнения, на втором входе которого присутствует код нуля с выхода регистра 18. В результате сравнения происходит анализ исправен ли данный процессор. В случае если результат сравнения положительный, то есть он исправен, процессор должен быть отмечен как неисправный, поэтому единичный импульс со второго выхода элемента сравнения 19 подается на вход we разрешения записи ОЗУ 16. Поэтому единица с выхода регистра 34 поступает на вход данных D ОЗУ 16 и заносит туда код единицы, как признак неисправности данного процессора.

Одновременно с этим единичный потенциал с выхода элемента сравнения 19 подается на второй вход элемента 27 ИЛИ и счетный вход счетчика 23. Единица проходит через элемент 27 ИЛИ и поступает на вход we разрешения записи ОЗУ 15, чем разрешает запись нулевого кода с выхода регистра 16, что означает признак неисправности процессора с данным адресом в матрице P1.

Оценка эффективности алгоритмов отказоустойчивого переразмещения программ в мультипроцессорных системах

Зависимость времени компиляции задач хост-процессором п устройством от числа операторов На рисунке 6.20 представлена зависимость времени выполнения задач распараллеливания в секундах хост-процессором (график 1) и предлагаемым СВУ (график 2) от числа N операторов фрагмента программы при суммарном числе входных и выходных переменных М, равном 200. Каждой точке гра-фиков соответствует отдельная задача, характеризующаяся исходными дан ными - оішарньгмп матрицами при которых суммарная временная сложность задачи является максимальной. Частота работы устройства и хост-процессора равна 200 МГц, время доступа к внешней памяти хост-процессора - 20 не, время доступа к внутренней памяти предлагаемого устройства - 8 не.

Структурные и функциональные схемы планирования размещения программ в мультипроцессорных системах

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

Ведущая ЭВМ кластерной системы передает в акселератор планирования размещения задач (АИР) матрицы МОИ и ММР для размещения пакета задач, описанного матрицей МОП, в базовом матричном блоке, описанном

матрицей ММР [171]. Акселератор планирования размещения задач представляет собой программно-аппаратный комплекс на базе микропроцессорного контроллера и функционирует на основе методики ускоренного выполнения процедуры планирования размещения задач (п. 2.2).

Контроллер акселератора работает в соответствии с описанной в приложении 2 программой. Входными данными являются переданные через последовательный сетевой интерфейс файлы матриц МОИ и ММР.

На аппаратный уровень акселератора вынесены операции, требующие больших временных затрат, а именно вычисление показателя коммуникационной задержки max ІГд (раЬ,рхЛ\ в соответствии с выражением (2.9, 2.10).

Для его нахождения используется блок акселератора вычисления показателя коммуникационной задержки (АВПКЗ). подключенный к контроллеру через параллельный порт. Для расчета в блок АВПКЗ передается новая МОП в виде вектора.

В первом шаге вычислений также в виде вектора передается ММР. Далее она многократно используется при поиске. АВПКЗ за время, пропорциональное (6464) тактам, вычисляет показатель Т = max{my - іД/ = \,N;j = \,N как максимум результатов перемножения соответствующих элементов векторов с помощью матричного конвейерного блока умножения. По окончании обработки МОИ блок АВПКЗ передает величину найденного показателя коммуникационный задержки в контроллер акселератора.

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

Для подключешія блока АВПКЗ к контроллеру используется порт параллельного интерфейса типа LPT (Line PiinTer - построчный принтер). С внешней стороны порт имеет 8-битную шину данных, 5-битную шину сигналов состояния и 4-битную шин} управляющих сигналов, выведенные на разъем-розетку DВ-25 S.

С программной стороны контроллера LPT-порт представляет собой набор регистров, расположенных в пространстве ввода-ввгвода. Регистры порта адресуются относительно базового адреса порта, стандартными значениями которого являются 3BCh, 378h и 278h. Порт может использовать линию запроса аппаратного прерывания, обычно IRQ7 или IRQ4. Для управления обменом данными через порт разработаны специальные алгоритмы: передачи данных в АВПКЗ. приема данных от АВПКЗ, передачи данных в контроллер. приема данных от контроллера.

АВПКЗ - акселератор вычисления показателя коммуникационной задержки, МП - микропроцессор, ОП - оперативная память, КПДП - контроллер прямого доступа в память, Ппорт - последовательный порт, Прпорт - параллельный порт, MUX - мультиплексор, УУ - устройство управления, БУМК -блок умножения матрично-конвейерный, МАХ - блок сравнения и нахождения максимума, МО - микроперация, А - адрес.

МП контроллера работает в соответствии с программой, записанной в ОП, переставляет строки (столбцы) матрицы МОИ и передает новое МОИ в ОЗУ1. В ОЗУ2 можно заранее передавать ММР, а далее ее многократно использовать при поиске. Самую частую операцию, требующую ускорения -вычисление максимальной коммуникационной задержки предполагается вычислять в аппаратном ускорителе.

Для этих целей в состав схемы введен акселератор вычисления показателя коммуникационной задержки (АВПКЗ), ускоряющий решение задачи планирования размещения задач в базовом блоке кластерной ПС. Блок АВПКЗ отличается тем. что в нем применены конвейерный и матричный подходы для поэлементного перемножения векторов с одновременным подсчетом максимального пропзведенгья. В составе АВПКЗ можно выделить шесть основных функциональных блоков. Данные с параллельного порта поступают в блок специализированного мультиплексора (MUX). В зависимости от режима работы MUX загружает одно из ОЗУ данными соответствующей разрядности, при этом если идет загрузка в ОЗУ2 из 8-ми разрядного порта за один цикл приема MUX принимает два 4-х разрядных слова, если же идет загрузка в ОЗУ] то MUX принимает два байта 16-ти разрядного слова и после их склеивания помещает целое слово в ОЗУ і.

203 Блок умножения матричной-конвейерный (БУМК) осуществляет перемножение синхронно считанных го ОЗУ и ОЗУ2 двух слов и выдает результат в блок нахождения максимума (МАХ). Умножение происходит конвепер-но за один такт. Исключение составляет первые такты загрузки ступеней матричного конвейера. Таких ступеней 3, т.к. при размерности данных в ОЗУ2, равный 4 битам, используется только 3 из них.

Блок МАХ находит максимум и по сигналу об окончании расчета выдает результат за три цикла вывода в порт контроллера.

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