Пупков К.А., Коньков В.Г. - Интеллектуальные исследования (Современнаяя теория управления) (1072100), страница 21

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

Текст из файла (страница 21)

(147)

Критерий эффективности построим на основе вычислительной и коммуникационной загрузок процессоров. Вычислительная загрузка WL (Work Load) процессора определяется суммарным временем выполнения назначенных ему программ

(148)

Коммуникационная загрузка CL (Communication Load) процессора Q_ - это суммарное время обменов, которые должны выполнить программы, назначенные этому процессору

(149)

В качестве критерия эффективности отображения используем максимальную из суммарных загрузок процессоров МВС

(150)

Ставится задача поиска отображающей матрицы X = X*, доставляющей минимум критерию эффективности (150)

(151)

Заметим, что модель (147) - (151) не учитывает коммуникационную загрузку процессоров МВС, обусловленную транзитными обменами; возможные задержки обменов из-за перегрузки каналов обмена; дополнительное время на организацию обменов. Последнюю составляющую, которая в транспьютерных сетях, например, может быть весьма существенной, легко учесть, если положить

где l_, -«расстояние» между процессорами Q_, Q_ ; t_st - стартовое время; t_com - время передачи байта данных между соседними процессорами МВС [66].

Точное решение задачи. Входящая в соотношение (151) составляющая (148) линейна, а составляющая (149) нелинейна относительно компонентов отображающей матрицы X. Введем вспомогательную отображающую N² x n² – матрицу , компоненты которой представляют собой произведение компонентов матрицы X. С использованием матрицы выражение запишется в виде

где - элемент матрицы , находящейся в строке, соответствующей , , и столбце, соответствующем i, j.

Вычислительная загрузка (148) выражается через матрицу в виде

где

- (n² x 1) - вектор.

Таким образом, критерий эффективности согласования оказывается линейным относительно матрицы .

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

(152)

с ограничениями

и ограничениями

Задача содержит (n²N² + N + 1) переменных и (n² + N² + N + 2) ограничений.

Теорема. Задача оптимального отображения структуры ИСУ на архитектуру МВС является NP - сложной.

Справедливость теоремы следует из того факта, что задача булева линейного программирования (152) является NP - сложной [70].

Точное решение задачи отображения реализовано в последовательном фортрановском GOMORY - отображателе, использующем программу НО2ВАF решения задачи целочисленного линейного программирования (152) известным методом Гомори из библиотеки численного анализа NAG (National Algorithmic Group).

Проиллюстрированная далее эффективность GOMORY - отображателя может быть значительно повышена за счет использования параллельных алгоритмов метода Гомори.

Приближенное решение задачи на основе метода релаксации. Обозначим алгоритм решения задачи линейного программирования (152) с помощью симплекс-метода (SIMPLEX), а соответствующие значения отображающей матрицы (нецелочисленной) и критерия эффективности X_s, E_s. Введем алгоритмы ROUND, UNIFORM, UNIFORM, COMBI.

Алгоритм ROUND заменяет величину (x_s)_,i ее целочисленным значением (x_r)_,i по формуле

(153)

где ₀ определяется из условия

(154)

При этом выполнение ограничений (147) обеспечивается автоматически.

Алгоритм UNIFORM₁ каждому процессору (кроме Q₁ или Q_N) назначает n₁ = [n/N] программ независимо от их вычислительной сложности. Здесь [n/N] - ближайшее целое, меньшее n/N.

Алгоритм UNIFORM₂ каждому процессору назначает такое количество программ со смежными номерами, чтобы вычислительная загрузка этого процессора не превышала средней:

Алгоритм COMBI является комбинацией алгоритмов ROUND, UNIFORM₁ и UNIFORM₂. Выбирается лучший из них по критерию (151).

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

Приведем результаты исследования для МВС с архитектурой типа «линейка» [70], в которой Host – процессор Q₁ и процессоры Q₂, … , Q_N одинаковы. Положим, что вычислительная сложность p₁, p₂, …, p_n программ определяется случайными величинами, равномерно распределенными в интервале [0, p_max]. При этом обмены происходят только с программой, выполняемой на Host - процессоре, и параметры этих обменов одинаковы.

На рис. 35, 36 представлены результаты исследования при следующих данных: количество процессоров N = 8, количество программ n = 20, при одинаковых значениях параметров обменов c = 1 количество статистических испытаний равно 300. На рис. 35 проиллюстрирован случай, когда средняя вычислительная сложность программ превышает сложность коммуникаций в 5 раз; на рис. 36 - в 50 раз. Символом обозначена оценка математического ожидания критерия эффективности отображения, кривым 1-5 соответствуют алгоритмы GOMORY, COMBI, ROUND, UNIFORM₁, UNIFORM₂.

Автором были проведены подобные исследования и с другими количествами программ, процессоров и p_max. Во всех случаях результаты были близки к представленным на рис. 35, 36, что дает основание сделать следующие выводы.

При приближенном решении задачи отображения алгоритм релаксации ROUND целесообразно комбинировать с простейшими алгоритмами равномерного распределения UNIFORM₁, UNIFORM₂, т.е. использовать комбинированный алгоритм COMBI. При этом средняя эффективность отображения повышается на 5 - 10% (в зависимости от соотношения средней вычислительной сложности программ и стоимости коммуникаций).

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

Алгоритм COMBI обеспечивает среднюю эффективность отображения лишь на 5% худшую, чем точный алгоритм целочисленного линейного программирования GOMORY.

Были также рассмотрены более сложные, чем ROUND, алгоритмы округления и более сложные, чем UNIFORM₁ и UNIFORM₂, алгоритмы равномерного распределения. Так, при округлении компонентов отображающей матрицы X наряду с алгоритмом (153) использовалась величина ; для равномерного распределения был использован алгоритм, близкий к «жадному алгоритму упаковки в контейнеры» [71]. Заметного повышения эффективности алгоритма COMBI эти усложнения не дали.

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

Рис. 35

Рис. 36

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

1. Графовое представление алгоритмов.

Вычислительные алгоритмы представляются взвешенными ориентированными ациклическими графами [72] (рис. 37). Вершины таких графов соответствуют некоторым частям алгоритма, в дальнейшем называемыми операциями. Дуги графа, соединяющие вершины, означают наличие информационной зависимости между соответствующими операциями алгоритма - результат выполнения одной операции является аргументом для другой. Веса вершин пропорциональны времени выполнения соответствующих операций - будем измерять их числом некоторым элементарных операций, содержащихся в соответствующей данной вершине операции. Под элементарной операцией можно понимать, например, арифметическую операцию (сложения/умножения) или один такт процессора. Дуги графа алгоритма также являются взвешенными, и их вес равен объему (например, в байтах) передаваемой по этой дуге информации.

Будем задавать введенный граф алгоритма, как ГА = <n, c, S>, где n - число вершин в графе, c_l={c_l, l=1..n} - вектор весов вершин, S - взвешенная матрица смежности графа. Это матрица размерности nxn , элементы s_ij которой равны 0, если i - ая и j - ая вершины не связаны дугой и весу связывающей их дуги в противном случае.

Каждую дугу графа будем представлять в виде упорядоченной пары номеров вершин (i, j) , которые эта дуга соединяет.

За U_A обозначим число элементарных операций алгоритма:

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

Ациклические орграфы допускают поярусное разложение. На первый ярус помещаются вершины, которые не имеют входных дуг. На каждый последующий ярус помещаются те вершины, которые не имеют предшественников, за исключением уже распределенных на предыдущие ярусы. Обозначим число таких ярусов за h. А само поярусное распределение буем представлять в виде матрицы Н размерности hxn, элементы H_kj которой равны 1, если j - ая вершина принадлежит k - ому ярусу, и 0 в противном случае. Смысл такого поярусного распределения состоит в том, что операции алгоритма, соответствующие вершинам одного уровня, могут выполняться параллельно.

Рис.37. Пример графого представления алгоритма.

Средней степенью параллелизма назовем отношение h/n, которое для последовательных (h = n) алгоритмов равно 1, а для полностью параллельных (h = 1) алгоритмов - n.

1. Графовое представление мультитранспьютерных систем.

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

Характеристики

Список файлов книги