Xreferat.com » Рефераты по информатике и программированию » Выполнение планирования вычислений алгоритма на однородной вычислительной сети при известной структуре

Выполнение планирования вычислений алгоритма на однородной вычислительной сети при известной структуре

Содержание


Введение

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) - номер процессора, на котором рассчитывается нить в существующем разбиении.


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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таким образом, каждая нить характеризуется своим номером (к), временем начала

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

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: