Пупков К.А., Коньков В.Г. Интеллектуальные системы (1-е изд., 2001) (1245264), страница 25

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

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

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

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

На рис.39 показана система, в которой процессор 1 может выполнять обмены по всемканалам параллельно. Для этого в модель добавлено 4 дополнительныхпроцессора. На рис. 39 показана система, в которой все каналы 1-ого процессораразбиты на 2 группы и все обмены в каждой группе выполняются83последовательно, а обмены по каналам из разных групп могут выполнятьсяпараллельно.gk i ( R) n hkl ri l cll 1Элементы такой матрицы определяют суммарный вес вершин, принадлежащих i- ому подграфу и k - ому ярусу в ГА. Время на выполнение межпроцессорныхобменов информацией будет определяться объемом дуг, соединяющихвершины, принадлежащие разным подграфам.

Для вычисления этого объемавводится матрица коммуникационной нагрузки F размерности pxp, элементыкоторой определяют связность двух подграфовФij nn  ril r jm Slml 1m 1Рис. 39. Моделирование некоторых режимов совмещения счета иобменов для процессора 1. (Дуги помеченные “х” имеют бесконечно большойвес).3.Постановка задачи распараллеливания вычислений.Под распараллеливанием вычислительных алгоритмов будем пониматьраспределение операций этого алгоритма по процессорам, а в графовыхпредставлениях - вершин графа ГА по подграфам, общее число которых равно pи каждому из которых соответствует один из процессоров (одна из вершин ГС).Такое распределение будем представлять в виде матрицы разрезания Rразмерности pxn, элементы r которой равны 1 – если l - ая вершинапринадлежит i - ому подграфу, и нулю в противном случае (см. рис. 40).Т.к.

операции, соответствующие вершинам одного яруса в ГА,способны выполняться параллельно, то степень параллелизма будетоцениваться поярусно. С этой целью вводится в рассмотрение матрицавычислительной нагрузки G размерности hxp, в которойРис. 40. Отображение графа алгоритма на граф ВС.84Основываясь на графовых представлениях алгоритмов и ВС, а также навведенных матрицах G и F, напишем функционал J(R), который будем называтьприведеннымвременем выполнения алгоритма на ВС при заданном отображении R.p gp 1 phJ ( R )  0 (  max ( ki )    Фij  ij )U A k 1 i 1  ii 1 j  i 1что вероятность случайного выбора хорошего решения (E < 0.1) практическиравна нулю.Первое слагаемое функционала отражает время, затрачиваемое навыполнение вычислений, второе - время на выполнение межпроцессорныхобменов информацией (накладные расходы на организацию параллельныхвычислений).

Множитель  0 U Aвведен в функционал для его нормировки,т.к. U A  0 есть время выполнения алгоритма на самом быстром процессореданной ВС. Записанный функционал, в которой степени, можно рассматриватькак величину, обратную ускорению, достигаемому при выполнении алгоритмана ВС при заданном распараллеливании R.Оптимизационнуюзадачураспараллеливаниявычисленийсформулируем следующим образом: Пусть заданы ГА = <n, c, S> и ГС = <p, ,>. Найти матрицу разрезания R графа ГА на p подграфов, дающую минимумфункционалу J(R).4.Свойства функционала J(R) и поставленной задачи.Относительно поставленной задачи отображения графов алгоритмов наархитектуры многопроцессорных ВС известно, что она является NP - сложной.По этой причине для ее решения малопригодны точные (переборные) методы,типа метода ветвей и границ.

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

Для получения этой кривой, случайнымобразом выбиралось разрезание R, а затем искался ближайший к этому Rминимум (алгоритм такого поиска описывается ниже). Видно, что функционалJ(R) содержит большое количество локальных минимумов, что подавляющеебольшинство локальных минимумов сосредоточено в области 0.5 < E < 0.6, иРис. 41. Функция распределения относительной ошибки E = (J(R)Jmin)/J(R) при: 1) случайном выборе разрезания R; 2) случайном выборелокального минимума J(R).5. Обзор существующих методов решения поставленнойоптимизационной задачи.Методы решения сформулированной задачи можно разделить наточные и приближенные. Все точные методы, в силу NP - сложности задачи,являются некоторыми модификациями метода полного перебора.

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

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

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

Описывается процедура Probe, которая длязаданного числа a определяет, существует или нет назначение, значениефункционала, на котором меньше или равно a. Если такое отображениесуществует, то оно строится. Далее, определяется отрезок [x, y], в которомлежат всевозможные значения функционала для решаемой задачи. Поископтимального назначения осуществляется методом деления отрезка пополам,т.е. на указанном отрезке ищется точка Jmin, для которой существуетотображение, а левее ее такого отображения нет.Еще один специализированный метод описан в [81], где решаетсязадача назначения на архитектуру ВС типа гиперкуб.Более распространены универсальные методы.

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

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

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