Материал: Распределение задач с помощью нитей по процессорам вычислительной системы заданной структуры

T8={13, 23, 32, 40}

T9={14, 25, 33, 39, 49}ак как рассматривается ВС с общей памятью, обмена данными через каналы связи между процессорами нет, и количество нитей меньше, чем число процессоров, поэтому распределение нитей между ВМ может осуществляться, например, следующим образом: первая нить загружается в первый ВМ, вторая - во второй и т. д.

Учёт времён передачи информации осуществляется, используя следующие соотношения: для развёртки- p_,j=q_i,j+p_j, где j=- номера операторов, образующих развёртку; для свёртки- p_j= q_j,i +p_j где j=- номера операторов, образующих cвёртку. С помощью матрицы следования с указанными весами дуг и вершин модифицированные веса вершин можно вычислить следующим образом: если в i-й строке найдено одно число, то вес i-й вершины модифицируется к виду: р_i:=p_i+q_ji;если в i-й строке найдено несколько чисел, то веса вершин модифицируются к виду р_j:=p_j+q_i,j, j={}, где j - номера столбцов, в которых найдены числа,q_i,j- множество весов дуг, принадлежащихi-й строке.

В таблице 3 приведены ранние сроки окончания выполнения операторов.

Таблица 3- Ранние сроки окончания выполнения операторов

Рисунок 4 - Диаграмма ранних сроков окончания выполнения операторов

Паузы, возникшие по окончанию 12, 15, 20, 21, 22 единиц времени, обусловлены синхронизацией вычислений, определяемой структурой рассматриваемой граф-схемы. Общее время выполнения алгоритма составляет 26 условных единиц времени.

Этот способ графического представления плана выполнения алгоритма на ВС позволяет в максимальной степени компактно распределить параллельные операторы по узлам ВС. Это позволяет обеспечить экономию времени при выполнении задач. Как видим, при таком раскладе наиболее продолжительный по времени последовательный путь в ИЛГ незначительно выдаётся за пределы компактного распределения интервалов работы операторов основного тела ИЛГ.

При построении временных диаграмм выполнения операторов необходимо учитывать, что они строятся для информационно-логической граф-схемы, и не все операторы будут выполнены. Это можно сделать, например, с помощью динамического плана, состояние которого изменяется каждый раз, как только выполняется очередной логический оператор. То есть для каждой возможной цепи выполнения операторов предусматривается своя временная диаграмма. Для рассматриваемой граф-схемы временные диаграммы будут выглядеть так, как показано на рисунках 5-14.

Рисунок 5 - Временная диаграмма при срабатывании дуги 5.1

Рисунок 6 - Временная диаграмма при срабатывании дуги 5.2

Рисунок 7 - Временная диаграмма при срабатывании дуги 5.3

Рисунок 8 - Временная диаграмма при срабатывании дуги 5.4

Рисунок 9 - Временная диаграмма при срабатывании дуги 5.5 и 10.1

Рисунок 10 - Временная диаграмма при срабатывании дуги 5.5 и 10.2

Рисунок 11 - Временная диаграмма при срабатывании дуги 5.6

Рисунок 12 - Временная диаграмма при срабатывании дуги 5.7

Рисунок 13 - Временная диаграмма при срабатывании дуги 5.8

Рисунок 14 - Временная диаграмма при срабатывании дуги 5.9

Как видно из рисунка 14, максимальное число нитей для данного алгоритма равно 7. Полная временна диаграмма свидетельствует о наличии 9 таких нитей.

3.3 Распределение нитей на структуре типа циркулянта

В задании в качестве исходных данных для архитектуры ВС дана информация о циркулянте {49, 1, 3, 4, 5, 7}. Эта циркулянта представлена на рисунке 15.

Рисунок 15 - Схематическое представление циркулянты {49, 1, 3, 4, 5, 7}

Для показанной на рисунке 15 циркулянты строится матрица дистанций (см. таблицу 3 в приложении 5.1), в которой расстояния указываются в минимальном числе промежуточных связей между соответствующими вычислительными модулями. Минимальная сумма расстояний от любого ВМ циркулянты до других ВМ равна 116 ед. То есть эта сумма является постоянной величиной, не зависящей от номера ВМ в циркулянте. Таким образом, отдать предпочтение каким-либо конкретным ВМ в составе циркулянтной ВС не представляется возможным. Тем не менее, очевидно, что ВМ для размещения 9 нитей должны быть выбраны среди всего множества ВМ циркулянтной ВС так, чтобы расстояния между ВМ внутри группы были минимальны.

Таким образом, первую нить можно разместить в любом ВМ (например, в 0-ом), а последующие нити - на минимально возможном расстоянии от первой. Так, расстояние от нитей 2 и 3, размещённых соответственно на 48 и 1 ВМ составит единицу от первой нити, размещённой на нулевой ВМ. Аналогично на единичном расстоянии от первой нити будут находиться 4 и 5 нити, размещённые на ВМ 3 и 46 соответственно. 6 и 7 нити целесообразно разместить на 4 и 45 ВМ соответственно, тогда как 8 и 9 нити разместятся на 5 и 44 ВМ. Таким образом, нити с 2 по 9 находятся на минимальном (единичном) расстоянии от первой нити. Расстояние между ними также минимально возможным в силу конструктивным особенностей ВС типа циркулянта {49, 1, 3, 4, 5, 7}. На рисунке 16 представлено распределение нитей по ВМ ВС структуры циркулянта {49, 1, 3, 4, 5, 7} (см. также таблицу 4 в приложении 5.2).

Рисунок 16 - Распределение нитей по вычислительным модулям ВС структуры циркулянта {49, 1, 3, 4, 5, 7}

Заключение

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

Так, в процессе проектирования были решены задачи:

         нахождение ранних сроков окончания выполнения операторов;

         построение нитей решения задачи в соответствии с заданной граф-схемой;

         распределение нитей по ВС, с учетом времени передачи между операторами и между процессорами.

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

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

.       Руденко Ю.М., Волкова Е.А. Вычислительные системы. Москва, НИИ РЛ МГТУ им. Н.Э.Баумана, 2010.

.       Корнеев В.В. Параллельные вычислительные системы, Издательство НГТУ, 2009.

.       Хорошевский В.Г. Архитектура вычислительных систем, МГТУ им. Н.Э. Баумана, 2014.

4.     Руденко Ю.М. Новый подход к изображению схем алгоритмов для вычислительных систем. Информатика и системы управления в ХХ1 веке. Сборник трудов №7 молодых учёных, аспирантов, и студентов - М,: МГТУ им. Н.Э. Баумана, 2012. 167-181 с.

.       Руденко Ю.М. Построение плана выполнения параллельных алгоритмов на базе граф-схем. Аэрокосмические технологии. Научные материалы МНТК - 2009.Реутов - Москва 2009. 179-181с.

.       Руденко Ю.М. Учёт зависимостей программных модулей по данным и последовательностям их выполнения при параллельных вычислениях. Известия высших учебных заведений. Поволжский регион. Технические науки. № 3 (11), 2009. 67-75 с.

1.   Приложение 1

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

1.      Просматриваем матрицу SDR по строкам сверху вниз. Если просмотрены все строки, то - конец алгоритма.

2.      Если в i-й строке найдено одно число, то вес i-й вершины модифицируется к виду: р_i:=p_i+q_j,i . Если в i-й строке найдено несколько чисел, то веса вершин модифицируются следующим образом: р_j:=p_j+q_i,j ,j={}, где ,j - множество столбцов, в которых найдены числа,q_i,j- множество весов дуг, принадлежащихi-й строке .

3.      Используя модифицированные веса, с помощью алгоритма 6.1.1 вычисляем ранние сроки окончания выполнения операторов.

4.      Вычисленные ранние сроки окончания выполнения операторов служат основой для построения диаграммы загрузки ВМ. Каждая строка диаграммы может служить нитью для загрузки в процессор.

Приложение 2

Алгоритм вычисления ранних сроков окончания выполнения операторов

. Вычислим t_1,j:=0, где j :=1,…,RS. RS - размер матрицы следования

2. Просматриваются строки матрицы S сверху вниз, выбирается первая необработанная строка матрицы, и осуществляется переход к следующему шагу, если обработаны все строки, то - конец алгоритма.

. Если выбрана j-я строка, не содержащая единичных элементов, то вычисляем t_1,j:= p_j , где p_j - вес j-го оператора и переходим на шаг 5.

. Если j-я строка содержит единичные элементы, то вычисляется

t_1,j:= + p_j,

где max , берётся по множеству времён t_1,j, где j_q- номера элементов j-й строки, равных единице. Если в множестве  есть нулевые элементы, то выполняется шаг 6, иначе выполняется шаг 5.

5. Обработанная j-я строка исключается из рассмотрения. Осуществляется переход на шаг 3.

. Выбираем столбец j:=j_q и переходим на шаг 3.

Примечание: пункт 6 алгоритма 6.1.1 используется для нетреугольной матрицы S

Приложение 3

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

1.   Задана ВС с N вычислительных модулей, нумеруемых как {0,1,…,N-1}. Предполагается, что мощность множества удовлетворяет потребность в количестве ВМ для решения поставленной задачи предполагаемым методом.

2.      Количество нитей W. Множество нитей Т.

.        Вычислим матрицу расстояний между вычислительными модулями.

Минимальное расстояние между двумя ВМ равно 1, максимальное - N-2.

.     Для определения показателя близости ВМ определим сумму столбцов матрицы R.

j=1,2,…,N.
При j=1 показатель близости наилучший.

5.      Упорядочим St(j) в порядке возрастания

6.      Построим диаграмму ранних сроков окончания выполнения операторов с указанием связей между операторами, с учетов времени передачи между операторами. Образуем множества несвязных между собой пучков нитей {}; S={0,1,…,q}.

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

Примечание: таких множеств нитей может быть несколько, и тогда выбирается любое из них.

8.      Составим из связей между нитями множества {} массив MS и обнулим все его элементы.

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

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