Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Содержание

Введение

1. Постановка задачи

2. Анализ исходных данных

3 Описание используемой структуры ВС

4. Описание алгоритма решения задачи

4.1 Основные определения

4.2 Алгоритм построения нитей в сети G.

4.3 Алгоритм уплотнения нитей.

4.4 Алгоритм распределения вершин графа решаемой задачи на узлах вычислительной сети с одинаковой степенью вершин

5. Описание интерфейса программы

6. Результаты работы программы

Заключение

Список использованных источников



Введение

В настоящее время увеличилась тенденция использования многопроцессорных систем для обработки данных. Для эффективного использования таких систем необходимо, во-первых, преобразовывать последовательные алгоритмы обработки данных в параллельные, а во-вторых, использовать специальные алгоритмы, которые позволят распределить операторы параллельных алгоритмов по процессорам вычислительной сети.

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

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

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



1. Постановка задачи

Цель - найти оптимальный план распределения решаемой задачи по узлам вычислительной сети (ВС).

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

Далее необходимо реализовать полученный алгоритм в виде программы. Программа должна обеспечить:

1. Возможность получения матрицы следования для различных информационных графов. Это позволит лучше протестировать полученный алгоритм распределения.

2. Возможность выбора параметров (размерностей) структуры ВС типа обобщенный гипертор.

3. Построение информационного графа решаемой задачи, по его заданной матрице следования.

4. Построение диаграммы размещения нитей на узлах ВС.



2. Анализ исходных данных

Решаемые задачи представляются треугольными матрицами следования 40х40 со скалярными весами для ИГ с помощью датчика псевдослучайных чисел, где первые две строки - нулевые. Необходимо сформировать ИЛГ с четырьмя логическими операторами в графе, представленном полученной матрицей, заменив произвольные вершины графа логическими. Связи, исходящие из логических операторов, кроме двух, исключить.

Рассматриваемая структура вычислительной сети - обобщенный гипертор. Степень вершины графа решаемой задачи не должна превышать 6, при этом она превышает степень вершины ВС на 3. В случае невыполнения этого условия матрица следования должна корректироваться: из столбца удаляются последние единицы, а из строки - первые.

Необходимо минимизировать количество узлов ВС, обеспечивая при этом минимальное время решения задачи.

С помощью программных средств необходимо организовать просмотр процесса построения нитей.

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

Вес вершины (pV) - время расчета (в условных единицах) оператора на i-ом процессоре.

Вес дуги (pA) - время передачи (в условных единицах) данных из одного оператора в другой, при условии, что эти операторы находятся на соседних процессорах. Если операторы находятся на процессорах, расстояние между которыми равно d, то время передачи данных из одного оператора в другой будет равно d*pA.



3 Описание используемой структуры ВС

Структура ВС типа обобщенный nD-тор описывается графом GS(M,S*), где М - множество вычислителей M={mi}, i=0…N-1, а S* - сеть, состоящая из множества ребер.

Структура ВС типа обобщенный трехмерный гипертор описывается следующими соотношениями:

- по каждой координате k=1, 2, 3 откладываются точки (вершины) с номерами 0,1,…,Nk-1, где Nk - размерность тора по координате k;

-множество вершин графа коммутационной структуры задается декартовым произведением [0,1,…,N1-1]x[0,1,…,N2-1]x[0,1,…,N3-1];

- две вершины соединяются ребром, если их декартовы произведения отличаются друг от друга на единицу по любой координате или на N1-1 по координате 1 или на N2-1 по координате 2 или на N3-1 по координате 3 соответственно.

Рис. 1 - Схема представления обобщенного трехмерного тора 3x2x2

Данная структура ВС имеет ряд преимуществ перед другими структурами ВС такими, как циркулянта, n-мерный двоичный гиперкуб, обобщенный трехмерный гиперкуб, бинарное дерево. Обобщенный гипертор является симметричной структурой со множеством дополнительных связей, что значительно облегчает процесс распределения вершин информационного графа по процессорам заданной структуры вычислительной сети.

4. Описание алгоритма решения задачи

4.1 Основные определения

Вершина - оператор информационного графа заданной задачи.

Вес вершины (pV) - время расчета вершины на i-ом процессоре.

Время старта вершины (Vs) - время старта расчета вершины в существующем разбиении вершин между процессорами.

Время финиша вершины (Vf) - время финиша расчета вершины в существующем разбиении вершин между процессорами.

Начальная и конечная вершины добавляются к информационному графу. Начальная вершина имеет номер 0 и необходима для того, чтобы граф имел одну точку входа. Конечная вершина имеет номер N+1, где N - размерность матрицы следования исходного информационного графа, и необходима, чтобы граф имел одну точку выхода. Веса этих вершин равны нулю. Веса дуг, выходящих из нулевой вершины равны единице. После этого добавления исходная матрица следования S преобразуется, будет иметь размер N+2 и обозначаться C.

Высота вершины (h) - максимальное время от начала выполнения вершины до конца выполнения алгоритма, заданного матрицей следования С.

По определению высота конечной вершины равна нулю.

Родители вершины - все предшествующие данной вершине вершины, от которых она зависит по данным.

Нить - набор из одной или нескольких вершин, которые последовательно рассчитываются на одном процессоре.

Родительские нити вершины - набор нитей, каждая из которых содержат одного или нескольких родителей данной вершины

Время готовности вершины (r) - максимум из времен финиша всех родителей вершины.

Время старта нити (sT) - время старта нити в существующем разбиении нитей между процессорами.

Время финиша нити (fT) - время финиша нити в существующем разбиении нитей между процессорами.

Номер процессора нити (nfp) - номер процессора, на котором рассчитывается нить в существующем разбиении.

Матрица дистанций (ProcDistance) - матрица, содержащая расстояния между всеми процессорами заданной структуры вычислительной сети.

Лучший процессор (BestProc) - это такой процессор, что расстояние от него до всех других процессоров минимально в заданной структуре вычислительной сети.

4.2 Алгоритм построения нитей в сети G

Алгоритм построения нитей в графе G, представляющим решаемую задачу.

1. В графе G выделим множество начальных вершин В матрице S, построенной для графа G начальным вершинам соответствуют нулевые строки. Вычислим i:=1- параметр определяющий текущий номер элемента в множестве , V - номер массива перебора операторов.

K:=1 - номер очередной создаваемой нити, -множество связей нитей с другими нитями, f:=0 - номер очередного разрезания графа G, - множество продолжения нитей.

2. Возьмем вершину .

3. Вычислим обобщенный вес вершины как если вес вершины не модифицировался или в противном случае.

4. Если из вершины не выходит связь, то переходим к шагу 9, иначе выполняется следующий шаг.

5. Если их вершины выходит одна связь в j вершину, т.е. в матрице S d -м столбце содержится единица в j-й строке. Обобщенный вес j-й вершины определится как если j-я вершина не модифицировалась и в противном случае. Обобщенный вес вершины определяется как на шаге 3. Переходим к шагу 10, иначе выполняется следующий шаг.

6. Если из вершины выходит несколько связей (развертка -вершины), то среди множества дуг J, исходящих из вершины ищем , (1), где -вес дуги, исходящей из вершины и входящей в вершину j.

7. Если условию (1) удовлетворяют несколько вершин, то выбирается первая вершина рассматриваемого множества, составляющих эти вершины. Для вершины вычисляется вес , если вершина не модифицировалась и , в противном случае. Веса вершин из множества J, исключая вершину , вычисляются как , если j-я вершина не модифицировалась и в противном случае, где -вес дуги, выходящей из вершины и входящей в вершину j. Обобщенный вес вершины определяется, как на шаге 3. Переходим к шагу 11. Если из вершины не выходит несколько связей, то выполняется следующий шаг.

8. Если вершина входит в свертку J, то обобщенный вес вершины , связанной с вершиной , вычисляется как , если обобщенный вес -й вершины не модифицировался и в противном случае. Веса остальных вершин, исключая вершину , вычисляются как , если вес вершины j не модифицировался и в противном случае. Обобщенный вес вершины вычисляется как на шаге 3. Переходим на шаг 12.

9. Вершина включается в Tk-ю нить как конец нити и исключается из рассмотрения. Tk-я нить включается в множество нитей NT.

10. Вычислим .Если , то вычисляем f:=f+1 и переходим к шагу 13, иначе положим i:=i+1 и переходим на шаг 2.

11. Вершина оформляется как элемент Tk-й нити и исключается из рассмотрения. Вершина включается в множество продолжения нити . Дуги исключаются из графа G или его компонентов. Составляется таблица(множество) связей фрагмента Tk нити в виде , где -включает номера операторов множества J, исключая оператор . Осуществляется переход на шаг 10.

12. Вершина оформляется как элемент Тк нити и исключается из рассмотрения. Вершина включается в множество продолжения нити . Дуги исключаются из графа G или его компонентов. Составляется таблица связей для фрагмента нити, где -включает номера операторов составляющих множество J, исключая оператор . Осуществляется переход на шаг 10.

13. Рассмотрим множество К компонентов графа G, образованные в результате удаления связей. Если множество , то переходим на шаг 16, иначе выполняем следующий шаг.

14. С помощью матрицы S, составленной для компонентов графа G определим множество начальных вершин .

15. Образуем множество таким образом , чтобы элементы множества предшествовали элементам множества , полученного на шаге 14. Множество Положим i:=1 и переходим на шаг 2.

16. Для графа G*, который имеет ту же конфигурацию, что и исходный граф G, но в котором изменены весы вершин с учетом весов дуг, вычислим ранние сроки окончания выполнения операторов.

17. Для каждой нити вычислим время старта нити в виде , где - ранний срок выполнения первого оператора Тк нити. Время окончания нити определяется как , где - ранний срок окончания последнего оператора Тк нити.

Конец описания алгоритма.

Таким образом, каждая нить характеризуется своим номером (к), временем начала нити , временем окончания нити и таблицей связей к-й нити с другими операторами, входящими в нити множества Тк.

4.3 Алгоритм уплотнения нитей

1. Времена начала и конца нитей объединяются в множества где n - число нитей, полученных в предыдущем алгоритме.

2. Упорядочим множество в порядке не убывания. Элементы представляются таким образом, чтобы i-ый номер начала нити соответствовал i-му номеру конца нити.

3. Найдем такой что для соседних нитей, размещаемых на интервале [0,T], после вычислений по соотношения (1) выполняется условие, что время окончания предшествующей нити должно быть меньше или равно времени начала последующей нити.

4. Если нити, удовлетворяющие условию (1) найдены, то соответствующие и удаляются и записываются в множество в виде составной к-й нити. Объединяются множества таблиц связей в виде где I -число нитей, вошедших в составную нить.

5. Если =0, то работа алгоритма заканчивается, иначе осуществляется переход к п.3.

Конец описания алгоритма.

4.4 Алгоритм распределения вершин графа решаемой задачи на узлах вычислительной сети с одинаковой степенью вершин

Предполагаем, что количество узлов вычислительной сети неограниченно и множество нитей Т получено с помощью алгоритма 4.2.

1. Просматриваем множество нитей Т, выберем к-ю нить с максимальным количеством элементов в множестве (таблице связей к-й нити). Предположим таблица связей имеет элементов.

2. Если степень i-й вершины вычислительной сети есть , то сравниваем и .

3. Если , то нить размещается в узле i, и переходим к шагу , иначе следующий шаг.

4. Если то образуется комплексный узел, в котором один вычислитель основной, остальные являются передающими звеньями. Полагаем f:=1 и переходим к следующему шагу.

5. Определяем где Т множество нитей.

6. Если , то переход на шаг 10.

7. Нить занимает узел вычислительной сети на минимально возможном расстоянии от узла i. Все вершины из окружения нити Ti, принадлежащие множеству удаляются из узлов, соседних с узлом I, т.е.

8. В соседних узлах с узлом размещаются элементы таблицы . Если количество узлов с минимальным расстоянием недостаточно, то организуются комплексные узлы, как пункте 4.

9. Если то вычисляется f:=f+1 и переход на шаг 5. Иначе полагаем и переход на шаг 5.

10. Вычисляем узел х, удовлетворяющий соотношению , где - количество свободных связей у рассматриваемых узлов. f=1,…f `, затем полагаем i:=x, T:=T\Tк. Если , то переходим к шагу 1, иначе конец алгоритма.

5. Описание интерфейса программы

Интерфейс разработанной программы состоит из трех основных окон:

1. Окно генерации матрицы следования S информационного графа решаемой задачи (рис. 2).

Рис. 2 - Окно ввода матрицы следования

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

Поскольку информационный граф не должен содержать циклов, то данные можно вводить только ниже главной диагонали матрицы следования.

2. Окно вывода информационного графа, заданного матрицей следования (рис.3).

Рис. 3 - Окно вывода информационного графа

3. Окно ввода параметров (размерности) обобщенного гипертора (рис. 4).



Рис. 4 - Окно выбора параметров обобщенного гипертора

В данном окне можно выбрать одну указать параметры структуры ВС.

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

Рис. 5 - Окно вывода результатов

6. Результаты работы программы

На рисунке 6 показана генерация матрицы следования.

Рис. 6 - Генерация матрицы следования S

На рисунке 7 показан построенный программой по указанной в задании матрице S информационный граф задачи.



Рис. 7 - Информационный граф задачи

Получим диаграммы размещения нитей на узлах вычислительной сети, задавая для вычислительной сети различные размерности.

1. Обобщенный гипертор размерности 2х2х2



Рис. 8 - Диаграмма размещения нитей на узлах ВС типа обобщенный гипертор размерности 2х2х2

Рис. 9 - Диаграмма распределения вершин графа по нитям



Рис. 10 - Распределение вершин ИГ по процессорам

Как видно, полное время решения задачи составило 30 условных единиц. Задействовано 8 процессоров, по которым распределено 30 нитей. Образовался комплексный узел, соответствующий процессорам 2 и 3, на котором обрабатывается вершина 40 ИГ.

2. Обобщенный гипертор размерности 2х2х3



Рис. 11 - Диаграмма размещения нитей на узлах ВС типа обобщенный гипертор размерности 2х2х3



Рис. 12 - Распределение вершин ИГ по процессорам

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

3. Обобщенный гипертор размерности 3х3х3



Рис. 13 - Диаграмма размещения нитей на узлах ВС типа обобщенный гипертор размерности 3х3х3

Время решения задачи составило 29 условных единиц, задействовано 12 процессоров из 27, 30 нитей.

Сведем полученные результаты в общую таблицу.

Таблица 1 - Результаты анализа размерности обобщенного гипертора

Тип ВС	Размерность	Полное время решения задачи в условных единицах
Обобщенный гипертор	2x2x2	30
Обобщенный гипертор	2x2x3	29
Обобщенный гипертор	2x3x3	29
Обобщенный гипертор	3x3x3	29
Обобщенный гипертор	3х4х4	30
Обобщенный гипертор	4x4x4	30

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

Заключение

процессорный обработка алгоритм граф

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

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

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

Размещено на Allbest.ru