Пупков К.А., Коньков В.Г. Интеллектуальные системы (1-е изд., 2001) (1245264), страница 24
Текст из файла (страница 24)
формулы (150),(151)), сводится к задаче смешанного булева линейного программирования~min ( X ) *(152)~X ,с ограничениямии ограничениями 0, ~x , ij 0,1; [1, N 2 ], ij [1, n 2 ].Задача содержит (n2N2 + N + 1) переменных и (n2 + N2 + N + 2)ограничений.Теорема. Задача оптимального отображения структуры ИСУ наархитектуру МВС является NP - сложной.Справедливость теоремы следует из того факта, что задача булевалинейного программирования (152) является NP - сложной [70].Точное решение задачи отображения реализовано в последовательномфортрановском GOMORY - отображателе, использующем программу НО2ВАFрешения задачи целочисленного линейного программирования (152) известнымметодом Гомори из библиотеки численного анализа NAG (National AlgorithmicGroup).Проиллюстрированная далее эффективность GOMORY - отображателяможет быть значительно повышена за счет использования параллельныхалгоритмов метода Гомори.Приближенное решение задачи на основе метода релаксации.Обозначим алгоритм решения задачи линейного программирования (152) спомощью симплекс-метода (SIMPLEX), а соответствующие значенияотображающей матрицы (нецелочисленной) и критерия эффективности Xs, Es.Введем алгоритмы ROUND, UNIFORM, UNIFORM, COMBI.Алгоритм ROUND заменяет величину (xs),i ее целочисленнымзначением (xr),i по формуле1, если 0 ;( xr ) , i (153)0 в противном случаегде 0 определяется из условияmax ( x s ) , i ( xs ) 0 , i , [1, N ], i [1, n ](154)Приэтомвыполнениеограничений(147)обеспечиваетсяавтоматически.каждому процессору (кроме Q1 или QN)Алгоритм UNIFORM1назначает n1 = [n/N] программ независимо от их вычислительной сложности.Здесь [n/N] - ближайшее целое, меньшее n/N.80Алгоритм UNIFORM2 каждому процессору назначает такое количествопрограмм со смежными номерами, чтобы вычислительная загрузка этогопроцессора не превышала средней:pn pi N .i 1Алгоритм COMBI является комбинацией алгоритмов ROUND,UNIFORM1 и UNIFORM2.
Выбирается лучший из них по критерию (151).Эффективность рассматриваемых приближенных алгоритмов решениязадачи отображения исследована с помощью статистического моделирования.Приведем результаты исследования для МВС с архитектурой типа«линейка» [70], в которой Host – процессор Q1 и процессоры Q2, … , QNодинаковы. Положим, что вычислительная сложность p1, p2, …, pn программопределяется случайными величинами, равномерно распределенными винтервале [0, pmax].
При этом обмены происходят только с программой,выполняемой на Host - процессоре, и параметры этих обменов одинаковы.На рис. 35, 36 представлены результаты исследования при следующихданных: количество процессоров N = 8, количество программ n = 20, приодинаковых значениях параметров обменов c = 1 количество статистическихиспытаний равно 300. На рис.
35 проиллюстрирован случай, когда средняявычислительная сложность программ p превышает сложность коммуникаций в5 раз; на рис. 36 - в 50 раз. Символом E обозначена оценка математическогоожидания критерия эффективности отображения, кривым 1-5 соответствуюталгоритмы GOMORY, COMBI, ROUND, UNIFORM1, UNIFORM2.Автором были проведены подобные исследования и с другимиколичествами программ, процессоров и pmax. Во всех случаях результаты былиблизки к представленным на рис.
35, 36, что дает основание сделать следующиевыводы.При приближенном решении задачи отображения алгоритм релаксацииROUND целесообразно комбинировать с простейшими алгоритмамиравномерного распределения UNIFORM1, UNIFORM2, т.е. использоватькомбинированный алгоритм COMBI. При этом средняя эффективностьотображения повышается на 5 - 10% (в зависимости от соотношения среднейвычислительной сложности программ и стоимости коммуникаций).При некоторых наборах исходных данных стандартные программы,использующие симплекс - метод, могут не давать решения (из-за погрешностейвычислений и представления данных).
Алгоритм COMBI обеспечивает решениезадачи во всех случаях.Алгоритм COMBI обеспечивает среднюю эффективность отображениялишь на 5% худшую, чем точный алгоритм целочисленного линейногопрограммирования GOMORY.Были также рассмотрены более сложные, чем ROUND, алгоритмыокругления и более сложные, чем UNIFORM1 и UNIFORM2, алгоритмыравномерного распределения. Так, при округлении компонентов отображающейматрицы X наряду с алгоритмом (153) использовалась величина max ( x s ) , i ; для 0равномерного распределения был использован алгоритм, близкий к «жадномуалгоритму упаковки в контейнеры» [71].
Заметного повышения эффективностиалгоритма COMBI эти усложнения не дали.Приближенное решение задачи отображения с помощью методарелаксации было реализовано в последовательном фортрановском COMBI отображателе. Алгоритм SIMPLEX в COMBI - отображателе реализован наоснове одной из библиотечных программ симплекс - метода.Рис. 35Рис. 36813.2. Стохастические методы решения задачи отображения алгоритмов ипрограмм на мультитранспьютерные системы1.Графовое представление алгоритмов.представлять в виде матрицы Н размерности hxn, элементы Hkj которой равны 1,если j - ая вершина принадлежит k - ому ярусу, и 0 в противном случае. Смыслтакого поярусного распределения состоит в том, что операции алгоритма,соответствующие вершинам одного уровня, могут выполняться параллельно.Вычислительныеалгоритмыпредставляютсявзвешеннымиориентированными ациклическими графами [72] (рис.
37). Вершины такихграфов соответствуют некоторым частям алгоритма, в дальнейшемназываемыми операциями. Дуги графа, соединяющие вершины, означаютналичие информационной зависимости между соответствующими операциямиалгоритма - результат выполнения одной операции является аргументом длядругой. Веса вершин пропорциональны времени выполнения соответствующихопераций - будем измерять их числом некоторым элементарных операций,содержащихся в соответствующей данной вершине операции. Подэлементарной операцией можно понимать, например, арифметическуюоперацию (сложения/умножения) или один такт процессора. Дуги графаалгоритма также являются взвешенными, и их вес равен объему (например, вбайтах) передаваемой по этой дуге информации.Будем задавать введенный граф алгоритма, как ГА = <n, c, S>, где n число вершин в графе, cl={cl, l=1..n} - вектор весов вершин, S - взвешеннаяматрица смежности графа.
Это матрица размерности nxn , элементы sij которойравны 0, если i - ая и j - ая вершины не связаны дугой и весу связывающей ихдуги в противном случае.Каждую дугу графа будем представлять в виде упорядоченной парыномеров вершин (i, j) , которые эта дуга соединяет.За UA обозначим число элементарных операций алгоритма:U A cll 1, nРис.37. Пример графого представления алгоритма.Назовем степенью параллелизма графа алгоритма максимальное числопопарно независимых вершин в графе. Степень параллелизма графа определяетмаксимально возможное число процессоров ВС для эффективногораспараллеливания алгоритма при заданной агрегации операций алгоритма ввершины графа. При числе процессоров, большем степени параллелизма, влюбой момент времени часть их обязательно будет простаивать.Средней степенью параллелизма назовем отношение h/n, которое дляпоследовательных (h = n) алгоритмов равно 1, а для полностью параллельных (h= 1) алгоритмов - n.Ациклические орграфы допускают поярусное разложение.
На первыйярус помещаются вершины, которые не имеют входных дуг. На каждыйпоследующий ярус помещаются те вершины, которые не имеютпредшественников, за исключением уже распределенных на предыдущие ярусы.Обозначим число таких ярусов за h. А само поярусное распределение буемПод мультитранспьютерной системой (ВС) будем понимать набор,состоящий изтранспьютеров, объединенных некоторой системой связи.Такие ВС будем представлять в виде взвешенных ориентированных графов,вершины которых соответствуют процессорам ВС и их число равно p.
Каждаявершина является взвешенной, и ее вес равен производительности (оп/с)соответствующего процессора ВС.2.Графовое представление мультитранспьютерных систем.82Если два процессора в ВС связаны ориентированным каналом передачиинформации (т.е. информация может быть передана от первого процессоравторому процессору), то соответствующие вершины в графе ВС связываютсядугой, направленной в вершину, соответствующую второму процессору.Каждая дуга в графе является взвешенной, и ее вес равен скорости передачиинформации (Бт/с) по соответствующему физическому каналу.
Предполагается,что в графе ВС для любых двух его вершин существует ориентированный путь,ведущий из первой вершины во вторую, что означает возможность обменаинформацией между любыми процессорами ВС.Таким образом, в рассмотрение вводится граф ВС, который будемпредставлять в виде ГС = <p, , >, где ={i, i=1..p} - есть векторпроизводительностей процессоров,={ij, i, j=1..p} - взвешенная матрица смежности графа ГС, элементы которойравны 0, если i -ая и j - ая вершины не связаны дугой, и весу этой дуги впротивном случае.
За 0 обозначим производительность самого мощногопроцессора в ВС. На рис. 38 приведен пример параллельной ВС и ее графовоепредставление.Принята следующая схема обмена информацией во введенной моделиВС. Пусть процессор с номером 1 должен передать некоторую информациюобъема V процессору с номером 2. Пусть обмен начинается в момент времени t.Возможны следующие варианты: 1) Процессоры 1 и 2 связаны каналом соскоростью передачи информации m.
Тогда, на время обмена [t, t + V/m] обапроцессора считаются занятыми только этим обменом и не могут выполнятьвычисления или другие обмены. 2) В графе ВС существует ориентированныйпуть из вершины 1 в вершину 2. В этом случае, весь путь разбивается напоследовательность дуг, каждый из которых соединяет по два процессора.Тогда процесс передачи информации распадается на последовательностьобменов первого типа.Существенным ограничением введенной модели ВС является то, чтокаждый процессор в каждый момент времени может либо выполнятьвычисления, либо обмениваться с одним другим процессором, т.к.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
