Из ещё не распределённых задач взять задачу с наибольшей сложностью, пусть это задача vk1. Выбрать процессор с наименьшей загруженностью, пусть это процессор Pj1. Распределить задачу vk1 на процессор Pj1, т. е. Kn(vk1)=Pj1. Возврат к 1, если ещё не все задачи распределены.
Данный алгоритм можно применить для начального распределения задач при известных относительных сложностях задач.
На основе алгоритма построения остовного дерева максимального веса Приведённые далее алгоритмы, основанные на построении остовного дерева максимального веса, учитывают оба критерия оптимальности – они в разной степени осуществляют балансировку вычислительной нагрузки между процессорами и минимизацию потока данных в сети. Для следующего алгоритма требуется информация об отностительной сложности задач ek, и также относительные величины потоков данных в ГПД fio. Рассмотрим вариант алгоритма для частного случая вида графа потоков данных. ГПД представляет собой последовательность вершин, соединённых в цепь парами разнонаправленных каналов между каждой парой вершин. ГПД такого вида используют так называемые разностные параллельные алгоритмы. Вычисления производятся во всех вершинах одновременно, а по окончании очередного цикла задачи обмениваются результатами с задачами на двух соседних вершинах. Полученные от "соседей" данные используются в качестве входных для следующего цикла вычислений. Таким образом, обеспечивается стационарность потоков и загруженностей задач, и их относительные величины известны априори. Алгоритм для ГПД в виде цепи:
Выбрать N задач с максимальной сложностью, где N – число процессоров, пусть это задачи vk1, vk2, … vkN. Распределить эти задачи по одной на каждый процессор, т. е. Kn(vki)=Pi. Выбрать наименее загруженный процессор, пусть Pj1.
Среди не распределённых задач, являющихся соседними для тех задач, которые уже распределены на процессор Pj1, выбрать задачу с наибольшей сложностью, пусть это vki. Распределить vk1 задачу на процессор Pj1, т. е. Kn(vki)=Pj1. Переход к шагу 3, если еще не все задачи распределены.
Результат работы алгоритма для ГПД в виде цепи иллюстрирует рисунок, где в скобках показаны вершины, распределенные на один процессор. В данном примере алгоритма, основанного на построении остовного дерева максимального веса, используется принцип исключения дуг наибольшего веса из неравенства, ограничивающего суммарный поток в сети. Распределяя разные задачи на один и тот же процессор, мы их как бы объединяем, и соединяющая их дуга исключается из суммы межпроцессорных потоков. Следовательно, если мы попытаемся исключить из этой суммы дуги с максимальными потоками, то этим обеспечивается минимизация потока данных в сети, т. е. второй критерий оптимальности. Кроме того, если при выборе процессора для распределения очередной задачи использовать минимаксный принцип, показанный в алгоритме (6. 1), то мы приближаемся к удовлетворению и первого критерия оптимальности. Рассмотрим задачу построения остовного дерева с максимальной суммой весов дуг (МОД для краткости). Вес дуги (i, j) в данном случае – это поток fij. Любое поддерево МОДа будет называться фрагментом. Заметим, что узел может рассматриваться как фрагмент. Дуга, имеющая один узел во фрагменте, а другой узел – вне этого фрагмента, называется дугой, уходящей от фрагмента. Утверждение. Пусть L – некоторый заданный фрагмент МОДа, а u = (i, j) – дуга максимального веса, уходящая от фрагмента L, причём узел j не входит в L. Тогда, если к L добавить дугу u и узел j, то получится фрагмент МОДа. Данное утверждение используется в качестве основы для алгоритмов построения МОД. Идея алгоритма Крускаля состоит в том, что берутся несколько произвольных вершин как начальные фрагменты, и затем эти фрагменты увеличиваются путем последовательного добавления уходящих дуг минимального веса. Настанет момент, когда какие-либо пары фрагментов соедининяются дугой, имеющей минимальный вес среди дуг, добавление которых не создаёт цикла. Алгоритм заканчивает работу после N-1 итерации.
На этих принципах основан следующий алгоритм оптимального распределения для ГПД любого вида: Выбрать N задач с максимальной сложностью, где N – число процессоров, пусть это задачи vk1, vk2, … vkN. Распределить эти задачи по одной на каждый процессор, т. е. Kn(vki)=Pi. Вершины на каждом процессоре (с номерами V(j)) будут составлять N начальных фрагментов МОДа. Выбрать наименее загруженный процессор, пусть Pj1.
Найти ребро максимального веса, уходящее от j1-ого фрагмента, пусть на внешнем конце ребра находится задача vki. Распределить vki на процессор Pj1, т. е. Kn(vki)=Pj1. Переход к шагу 3, если еще не все задачи распределены.
Алгоритм с улучшенной балансировкой нагрузки между процессорами Заметим, что на шаге 4 предыдущего алгоритма выбирается задача не оптимальная в смысле балансировки нагрузки, в то время как в алгоритме для ГПД в виде цепи выбирается задача с максимальной сложностью из всех нераспределённых задач. Оптимизационные характеристики алгоритма можно улучшить, если построить остовное дерево максимального веса заранее, а затем выполнить алгоритм распределения, аналогичный примеру для ГПД в виде цепи, приняв определение соседней вершины исходя из построенного остовного дерева. Единственным недостатком такого подхода является необходимость постороения всего остовного дерева сразу, что для больших графов потребует много оперативной памяти. Адаптивный алгоритм распределения
Адаптивные или динамические алгоритмы оптимального распределения задач основаны на тех же принципах, что и статические. На каждой итерации динамического алгоритма в качестве начальных данных для используемого статического алгоритма берутся текущие усреднённые, с момента последней итерации, значения характеристик вычислительного процесса, такие как величины потоков, загруженности задач и процессоров. Осуществлять полное перераспределение задач на каждой такой итерации нецелесообразно, так как это может занять много времени. Вместо этого перераспределяется определённое подмножество задач. Это подмножество составляется из тех задач, перераспределение которых может привести к улучшению критерия качества. Затем над выбранным набором задач осуществляется алгоритм статического распределения. В приведённом здесь алгоритме выбирается одна из задач на основе текущих измерений характеристик параллельного вычислительного процесса. Затем задача переназначается на другой процессор с помощью алгоритма, аналогичного одной итерации алгоритма (6. 2). Выбор задачи кандидата на перераспределение является эвристическим – выбирается наименее загруженная задача в наиболее загруженном процессоре. Перераспределив такую задачу на меннее загруженный процессор мы, таким образом, улучшим степень сбалансированности нагрузки. Кроме того, при этом будет наименьшая вероятность того, что это может привести к колебательному режиму. Колебания в алгоритме распределения могут возникнуть в следующей ситуации. Предположим, по какому то принципу выбрана задача кандидат на перераспределение. Сначала её выполнение приостанавливается. Это действие последует за собой уменьшение загруженности того процессора, на котором работала эта задача. Затем задача запускается на другом процессоре, что приводит к увеличению его загруженности. В следующей итерации алгоритма может случиться так, что в качестве кандидата выберется та же самая задача и перераспределится снова на старый процессор. Этот процесс может продолжаться довольно долго и отнять много времени на никчемные перескоки с одного процессора на другой. Данная ситуация наиболее вероятна в случае, когда задача вносит большой вклад в загруженность процессора. Поэтому, одной из мер предотвращения таких ситуаций является выбор задачи с наименьшей загруженностью. Этот способ оправдывается, если изменения статистических характеристик параллельного вычислительного процесса происходит гораздо медленнее, чем период одной итерации алгоритма оптимизации. Еще одним способом улучшения оптимизационных характеристик алгоритма является перераспределение как можно большего числа задач за одну итерацию. Но, как уже говорилось, процедура перераспределения отнимает много времени. Поэтому, число этих задач должно быть не слишком большим. Программная реализация и эксперименты Программа
Система управления параллельным вычислительным процессом (ПВП) реализована для ОС Windows 95, она состоит из двух частей: программы-монитора (далее монитор) и программы-диспетчера (далее диспетчер). Монитор должен работать на каждой ЭВМ локальной сети. Он выполняет запросы от диспетчера - на запуск задач, присоединение каналов, сбора статистики и др. Монитор работает в полностью автоматическом режиме, и не требует от пользователя постоянного надзора. Диспетчер запускается перед началом работы параллельного алгоритма (ПА), на любой из машин сети. Входными данными для диспетчера является граф потоков данных (ГПД) и скомпилированная библиотека задач ПА. Эти данные подготавливаются программистом в среде разработки ПА, основанной на пакете Borland Delphi. А затем, передаются диспетчеру с помощью специальной утилиты запуска, входящей в эту среду. После получения всех данных для выполнения ПА имеется возможность выбора алгоритма начального распределения и алгоритма динамической оптимизации, а также настройки других параметров диспетчера. Начальное распределение задач можно задать и вручную. Что касается внутренней программной структуры системы, она состоит из трёх уровней: низкого, среднего, высокого и отображения. Функции низкого уровня: запуск нового экземпляра задачи на любой ЭВМ локальной сети; соединение каналов обмена данных любых пар запущенных задач; вычисление статистических данных в реальном времени. Функции среднего уровня: организация и поддержка внутренней структуры ГПД;
организация и поддержка текущей конфигурации параллельного алгоритма; организация абстрактного управления конфигурацией на основе ГПД, т. е. связь конфигурации и ГПД; внутреннее представление статистических данных. Функции высокого уровня:
реализация абстрактных алгоритмов начального распределения, и оптимального управления. Функции уровня отображения: Организация интерфейса пользователя;
Отображение текущей статистической информации в реальном времени. Эксперименты
Для проведения экспериментов были выбраны параллельные алгоритмы для численных методов вычислительной линейной алгебры (ВЛА): параллельное умножение матриц, итерационный метод Якоби решению СЛУ, параллельный алгоритм факторизации матриц (LU-разложение). Алгоритм параллельного умножения матриц имеет ГПД в виде звезды, эта задача аналогична задаче типа параметрического исследования. Каждая задача типа Worker выполняет операцию скалярного или блочного умножения. Задача типа Manager выполняет генерацию самих перемножаемых матриц. В данном случае генерируются квадратные матрицы, заполненные случайными числами. Данный ПВП характеризуется большими объёмами передаваемых данных, т. к. хорошее ускорение получается только при достаточно больших размерностях матриц, порядка нескольких сотен и тысяч. Поэтому с ним лучше работают алгоритмы оптимизации, оприрющиеся на критерий минимизации потоков (5. 17). ГПД метода Якоби имеет циклический или кольцевой вид. С данным видом ГПД хорошо должен работать алгоритм на с упором на балансировку нагрузки. ГПД алгоритма LU-разложения имеет более сложный вид. В данном алгоритме наблюдается частые обмены данных и быстрые процессы вычисления в каждой рабочей задаче. С данным типом алгоритма должны хорошо работать оба из предложенных критериев оптимальности. Заключение
Оптимальное управление параллельными вычислительными процессами является одной из сложнейших областей параллельных вычислений. Эффективность работы параллельного вычислительной программы (ПВП) зависит не только от её параллельной структуры, но и от того, как реализуется её выполнение на конкретной вычислительной системе, и от многих внешних факторов. Главное внимение в данной работе было сосредоточено на описание математической модели параллельного алгоритма на основе ГПД. Были строго матеметичеки выведены критерии оптимального выполнения ПВП в терминах потоков и загруженностей. А также, предложены алгоритмы оптимального управления, опирающиеся на эти критерии. Один из этих алгоритмов реализован программно, спомощью чего были проведены эксперименты на реальной вычислительной сети. Эксперименты показали, что эффективная работа алгоритмов оптимизации данного типа возможна только при стационарности ПВП во времени. По мере того, как параметры потоков данных и загруженностей процессоров начинают быстро меняться во времени, преимущества рассмотренных методов оптимального управления ПВП начинают исчезать. В таких случаях трудно рекомендовать какие-либо методы оптимизации, которые были бы одновременно эффективными и практичными. Литература.
Воеводин В. В. "Математические модели и методы в параллельных процессах", М. :Наука, 1986, 296 с. Бертсекас Д. , Галлагер Р. "Сети передачи данных", М. :Мир, 1989, 544 с. Ian Foster "Designing and Building Parallel Programs", 1995, в электронном виде. Нечепуренко М. И. , Попков В. К. , Майнагашев С. М. и др. "Алгоритмы и программы решения задач на графах и сетях", Новосибирск : Наука. Сиб. Отд-ние, 1990, 515 с. Сергиенко И. В. "Математические модели и методы решения задач дискретной оптимизации", Киев: Наукова Думка, 1988, 471 с. Михалевич В. С. "Методы последовательной оптимизации в дискретных сетевых задачах оптимального распределения ресурсов", М. :Наука, 1983, 208 с.
Страницы: 1, 2, 3, 4
