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

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

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

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

Таким образом, в рассмотрение вводится граф ВС, который будем представлять в виде ГС = <p, , >, где ={_i, i=1..p} - есть вектор производительностей процессоров,

={_ij, i, j=1..p} - взвешенная матрица смежности графа ГС, элементы которой равны 0, если i -ая и j - ая вершины не связаны дугой, и весу этой дуги в противном случае. За ₀ обозначим производительность самого мощного процессора в ВС. На рис. 38 приведен пример параллельной ВС и ее графовое представление.

Принята следующая схема обмена информацией во введенной модели ВС. Пусть процессор с номером 1 должен передать некоторую информацию объема V процессору с номером 2. Пусть обмен начинается в момент времени t. Возможны следующие варианты: 1) Процессоры 1 и 2 связаны каналом со скоростью передачи информации m. Тогда, на время обмена [t, t + V/m] оба процессора считаются занятыми только этим обменом и не могут выполнять вычисления или другие обмены. 2) В графе ВС существует ориентированный путь из вершины 1 в вершину 2. В этом случае, весь путь разбивается на последовательность дуг, каждый из которых соединяет по два процессора. Тогда процесс передачи информации распадается на последовательность обменов первого типа.

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

Рис.38. Параллельная вычислительная система и ее графовое представление.

На рис. 39 приведены графовые представления ВС с различными режимами работы 1-ого процессора. Рис. 39 изображает ВС со стандартным режимом 1-ого процессора. На остальных рисунках показаны системы, в которых процессор 1 может совмещать выполнение вычислений и обменов. На рис. 39 процессор 1 выполняет обмены по всем каналам последовательно. Для этого вводится дополнительный процессор 6. Все каналы, связывающие 1-ый процессор с другими устройствами, предназначаются на процессор 6. Если процессору 1 надо передать информацию процессору 2, то он передает ее за нулевое время процессору 6 и может продолжать вычисления, а процессор 6 уже в нормальном режиме передает информацию дальше. Таким образом, вычисления и обмены для процессора 1 могут совмещаться по времени. На рис. 39 показана система, в которой процессор 1 может выполнять обмены по всем каналам параллельно. Для этого в модель добавлено 4 дополнительных процессора. На рис. 39 показана система, в которой все каналы 1-ого процессора разбиты на 2 группы и все обмены в каждой группе выполняются последовательно, а обмены по каналам из разных групп могут выполняться параллельно.

Рис. 39. Моделирование некоторых режимов совмещения счета и обменов для процессора 1. (Дуги помеченные “х” имеют бесконечно большой вес).

1. Постановка задачи распараллеливания вычислений.

Под распараллеливанием вычислительных алгоритмов будем понимать распределение операций этого алгоритма по процессорам, а в графовых представлениях - вершин графа ГА по подграфам, общее число которых равно p и каждому из которых соответствует один из процессоров (одна из вершин ГС). Такое распределение будем представлять в виде матрицы разрезания R размерности pxn, элементы r которой равны 1 – если l - ая вершина принадлежит i - ому подграфу, и нулю в противном случае (см. рис. 40).

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

Элементы такой матрицы определяют суммарный вес вершин, принадлежащих i - ому подграфу и k - ому ярусу в ГА. Время на выполнение межпроцессорных обменов информацией будет определяться объемом дуг, соединяющих вершины, принадлежащие разным подграфам. Для вычисления этого объема вводится матрица коммуникационной нагрузки F размерности pxp, элементы которой определяют связность двух подграфов

Рис. 40. Отображение графа алгоритма на граф ВС.

Основываясь на графовых представлениях алгоритмов и ВС, а также на введенных матрицах G и F, напишем функционал J(R), который будем называть приведенным

временем выполнения алгоритма на ВС при заданном отображении R.

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

Оптимизационную задачу распараллеливания вычислений сформулируем следующим образом: Пусть заданы ГА = <n, c, S> и ГС = <p, , >. Найти матрицу разрезания R графа ГА на p подграфов, дающую минимум функционалу J(R).

1. Свойства функционала J(R) и поставленной задачи.

Относительно поставленной задачи отображения графов алгоритмов на архитектуры многопроцессорных ВС известно, что она является NP - сложной. По этой причине для ее решения малопригодны точные (переборные) методы, типа метода ветвей и границ. Некоторое представление о характере функционала J(R) дает рис. 41. На этом рисунке построены две функции распределения относительной ошибки E = (J(R)-J_min)/J(R), где за J_min обозначено минимальное значение функционала, для задачи отображения двоичного дерева с числом вершин на верхнем уровне 40 на ВС, содержащую 8 процессоров. Кривая 1 соответствует функции распределения данной ошибки при случайном выборе разрезания R. Видно, что наиболее вероятным является выбор разрезания со значением ошибки 0.8 < E < 0.85. Кривая 2 соответствует функции распределения относительной ошибки при случайном выборе локального минимум функционала J(R). Для получения этой кривой, случайным образом выбиралось разрезание R, а затем искался ближайший к этому R минимум (алгоритм такого поиска описывается ниже). Видно, что функционал J(R) содержит большое количество локальных минимумов, что подавляющее большинство локальных минимумов сосредоточено в области 0.5 < E < 0.6, и что вероятность случайного выбора хорошего решения (E < 0.1) практически равна нулю.

Рис. 41. Функция распределения относительной ошибки E = (J(R)-J_min)/J(R) при: 1) случайном выборе разрезания R; 2) случайном выборе локального минимума J(R).

1. Обзор существующих методов решения поставленной оптимизационной задачи.

Методы решения сформулированной задачи можно разделить на точные и приближенные. Все точные методы, в силу NP - сложности задачи, являются некоторыми модификациями метода полного перебора. Когда за счет разного рода эвристик пытаются сократить число перебираемых вариантов. Наиболее известным является метод ветвей и границ (МВГ) [73]. Этот метод разбивает исходную задачу на ряд подзадач, так что любое допустимое ее решение является решением одной из подзадач, и наоборот. Для каждой подзадачи производится оценка функционала на наилучшем из ее решений. Если это значение больше, чем минимальное значение функционала на уже просмотренных решениях исходной задачи, то эта подзадача не решается. Все другие подзадачи решаются тем же способом. Качество подобных методов определяется, во-первых, способом разбиения каждой из возникающих задач на подзадачи; во-вторых, выбором хорошей оценочной функции для отбрасывания заведомо не оптимальных решений. Вместе с тем, ничто не гарантирует, что поиск оптимального назначения не потребует полного перебора всех возможных вариантов. В [74] отмечается, что точные методы целесообразно применять на графах с n < 10, т.е. на очень небольших задачах.

Существует другая разновидность точных методов, имеющих полиномиальную сложность, но рассчитанных на ограниченный класс графов алгоритмов и/или графов ВС [75]. Так, в [76] ограничивается граф ВС - произвольный граф алгоритма отображается на линейный граф ВС (цепочка процессоров). В [77, 78] уже на произвольный граф ВС отображаются деревья и так называемые последовательно - параллельные графы. И, наконец, в [77, 79] ограничения касаются обоих графов - линейный граф алгоритма отображается на линейный граф ВС. Почти все такие методы на основе графа алгоритма строят специальный граф назначения и сводят исходную задачу к некоторой задаче из теории графов (задача минимальной бисекции [76, 77, 78], поиск наикратчайшего пути [77, 78] для графа назначения, для которой известны быстрые методы решения).

В любом случае, применение точных методов решения задачи назначения для больших размеров используемых графов является проблематичным, либо из-за их большой сложности, либо из-за чересчур узкого класса допустимых графов. Поэтому, большое распространение получили приближенные методы. Эти методы также можно разделить на специализированные (рассчитанные на ограниченный класс графов алгоритмов и/или ВС) и универсальные. К первым относится семейством методов описанных в [80] и предназначенных для решения ряда задач с ограничениями и на граф алгоритма и на граф ВС. Описывается процедура Probe, которая для заданного числа a определяет, существует или нет назначение, значение функционала, на котором меньше или равно a. Если такое отображение существует, то оно строится. Далее, определяется отрезок [x, y], в котором лежат всевозможные значения функционала для решаемой задачи. Поиск оптимального назначения осуществляется методом деления отрезка пополам, т.е. на указанном отрезке ищется точка J_min, для которой существует отображение, а левее ее такого отображения нет.

Еще один специализированный метод описан в [81], где решается задача назначения на архитектуру ВС типа гиперкуб.

Более распространены универсальные методы. Некоторые из них являются модификациями точных методов. Так, в [82] предлагается метод, являющийся расширением метода поиска минимальной бисекции в графе назначения на случай P > 2. Метод состоит из p итераций, на i - ой итерации через объединение всех процессоров кроме j -ого в один задача сводится к случаю p = 2 и решается каким-либо методом из [77]. Если некоторые вершины графа алгоритма после p итераций остались не назначенными, простая процедура доназначает их.

В работах [83, 84] описаны два метода, основанных на переносах вершин графа алгоритма между процессорами ВС. Сначала строится некоторое начальное назначение. Выбирается пара процессоров с наибольшей коммуникационной нагрузкой (второе слагаемое в функционале J(R)). Путем переносов вершин между этими процессорами пытаются понизить функционал. Потом переходят к следующей паре процессоров и т.д. Эти методы можно трактовать, как методы безусловного спуска, т.к. все изменения в распределении вершин графа алгоритма по процессорам ВС происходят только при уменьшении функционала J(R). Отмечается, что вследствие этого качество методов сильно зависит от начального назначения.

В [85] рассматривается семейство методов, основанных на построении приоритетных списков вершин графов алгоритма и ВС. Предлагается три критерия для вершин графа ГА и три - для ГС. Списки формируются по убыванию (или возрастанию) одного из критериев, при равенстве критерия для нескольких вершин они упорядочиваются по второму критерию и т.д. Метод работает следующим образом. Специальная процедура выбирает одну вершину в ГА и назначает ее на некоторый процессор. Пересчитываются динамические критерии (которые зависят от уже проведенного назначения) и соответствующим образом переупорядочиваются списки. Первая вершина в списке вершин из ГА назначается на первый процессор в списке процессоров. Снова пересчитываются критерии и т.д. Метод работает пока есть еще не назначенные вершины в ГА. Различные комбинации введенных шести критериев порождают большое число возможных методов, называемых стратегиями. В работе проведено численное сравнение 12 стратегий, которое показало, что каждая из них может оказаться оптимальней других в зависимости от типов графа алгоритма и графа ВС (рассмотрены такие графы, как деревья, решетки, гиперкубы).

В [86] предлагается быстрый эвристический метод решения задачи назначения, в которой критерием оптимальности служит только коммуникационная нагрузка - второе слагаемое в J(R). Дополнительно предполагается, что на каждый процессор назначается не более вершин из ГА. Метод состоит в преобразовании исходного графа алгоритма в граф, состоящий из вершин. Оно осуществляется через последовательное объединение вершин, связанных самым тяжелым ребром, в одну новую вершину, если для последней не нарушается ограничение на нагрузку процессоров - число ей соответствующих вершин из ГА не должно превышать n₀. Все вершины графа алгоритма, соответствующие одной вершине из построенного таким образом графа, назначаются на отдельный процессор.

В [87] описывается очень популярный в последнее время метод решения различных дискретных задач оптимизации - метод имитации отжига, являющийся модификацией известного алгоритма Метрополиса. В [87] решается задача о разбиении графа на два подграфа с равным числом вершин и с минимальным числом ребер, соединяющих эти подграфы. Эта задача соответствует задаче назначения с p = 2. Вершины графа трактуются как частицы, совершающие случайные блуждания между этими подграфами в потенциальном силовом поле, роль потенциала которого играет функционал J(R). Наиболее вероятное распределение частиц соответствует распределению с минимумом потенциала, и, следовательно, минимальному значению функционала J(R). Для поиска этого распределения предлагается следующий алгоритм. Формируется начальное случайное распределение. На каждой итерации t = 1, 2, … в случайном порядке перебираются все вершины графа. Для каждой из них высчитывается приращение функционала D_J при переносе этой вершины в другой подграф. Если оно отрицательно (функционал понизился), то вершина переносится, если положительно, то переносится с вероятностью exp(-D_J / J), где параметр J играет роль температуры в системе частиц. Имитация отжига заключается в постепенном стремлении температуры к нулю. Если осуществлять его достаточно медленно (как 1 / ln(t)), то вся система частиц выходит не стационарное распределение, которое является оптимальным. Отмечается, что важным преимуществом метода является его способность к получению решения с любой степенью точности.

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

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