ЛР 5 / отчёт_task5

111Equation Chapter 1 Section 1МИНОБРНАУКИ РОССИИ

Санкт-Петербургский государственный

электротехнический университет

«ЛЭТИ» им. В.И. Ульянова (Ленина)

Кафедра математического обеспечения и применения ЭВМ

отчет

по практическому заданию №5

по дисциплине «Анализ, моделирование и оптимизация систем»

Тема: Структурная оптимизация многопроцессорной системы обработки данных

Студенты гр. 3381		Сучков А.И.
		Шкулёв А.А.
Преподаватель		Романцев В.В.

Санкт-Петербург

2017

Цель работы.

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

Для достижения поставленной цели требуется решить следующие задачи:

1. Определить основные характеристики модели;

2. Провести анализ загрузки многопроцессорной системы.

Основные теоретические положения.

Многопроцессорная вычислительная система обработки данных (МПСОД), состоящая из однотипных процессов, предназначена для решения заданного набора задач (ЗНЗ) обработки связанных между собой данных.

Модель, описывающая информационные связи между задачами X_i, задана в виде группы в ярусно-параллельной форме и представлена на рис. 1.

Рисунок 1 – Многопроцессорная вычислительная система обработки данных с пятью ярусами

Время решения ЗНЗ при параллельно-последовательной обработке данных в МПСОД, как это следует из графа (см. рис. 1), ограничено сверху некоторыми пороговым критическим значением Т_кр и определяется длиной критического пути графа.

Таким образом, оптимальное число процессоров МПСОД можно определить из соотношения:

, 22\* MERGEFORMAT ()

где T_о – время решения ЗНЗ с использованием одного процессора:

, 33\* MERGEFORMAT ()

где τ_i – время решения i-ой задачи.

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

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

Определить оптимальное число процессоров K_пр для МПСОД, граф решения ЗНЗ которой приведен на рис. 1. Построить график загрузки каждого процессора, чтобы достигнуть значения Т_кр.

Выполнение задания.

Для выполнения данного задания была разработана программа, вычисляющая оптимальное число процессов для заданной МПСОД, на языке R. Код программы представлен в приложении А. Граф на рис. 1 в программе представлен в виде списка, где в каждом i-ом элементе списка хранятся номера вершин, которые входят в i-ую вершину. Список с весами вершин (временами τ_i) приведён в табл. 1.

Таблица 1 – Список вершин графа с весами

Вершина i	Входящие вершины	Значение τi
1	-	10
2	-	10
3	-	20
4	-	40
5	{2; 4}	30
6	{1; 5}	10
7	{5}	10
8	{3; 5}	30
9	{6}	20
10	{6; 7; 8}	40
11	{10}	20
12	{10}	10
13	{10}	30

Исходя из данных табл. 1 и результатов работы программы было получено, что критическим путём будет X₄ → X₅ → X₈ → X₁₀ → X₁₃ и его критическое значение равно T_кр = 40 + 30 + 30 + 40 + 30 = 170.

С помощью формулы (2) было найдено время решения ЗНЗ с использованием одного процессора: T_о = 280. Таким образом, оптимальное число процессоров K_пр для МПСОД по формуле (1) равно . График загрузки каждого процессора для достижения значения Т_кр представлен в табл. 2.

Таблица 2 – График загрузки процессоров

Время	Доступные задачи	Процессор 1	Процессор 2
0-10	X2, X4	X4	X2
10-20			Простой процессора
20-30
30-40
40-50	X1, X3, X5	X5	X1
50-60			X2
60-70
70-80	X6, X7, X8	X8	X6
80-90			X7
90-100			Простой процессора
100-110	X9, X10	X10	X9
110-120
120-130			Простой процессора
130-140
140-150	X11, X12, X13	X13	X11
150-160
160-170			X12

Выводы.

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

Приложение А

РЕАЛИЗАЦИЯ Метода динамического программирования, Вычисляющая оптимальное число процессов

m <- readline("Введите число задач: ")

m <- as.numeric(m)

"%+%" <- function(...) paste0(...)

clc <- function() cat("\014")

X <- list()

for(i in m : 1) {

clc()

X.i <- readline("Введите вершину, которая входит в задачу X" %+% i %+% ".\nДля окончания ввода введите 0: ")

X.i <- as.numeric(X.i)

if (X.i >= 1) {

X[[i]] <- X.i

while(X.i >= 1) {

clc()

X.i <- readline("Введите вершину, которая входит в задачу X" %+% i %+% ".\nДля окончания ввода введите 0: ")

X.i <- as.numeric(X.i)

if(X.i >= 1) {

X[[i]] <- c(X[[i]], X.i)

}

}

}

}

clc()

action <- readline("Желаете ли вы самостоятельно ввести время решения каждой задачи? (y/n): ")

tau <- tau.i <- NULL

if(action == "y") {

for(i in 1 : m) {

tau.i <- readline("tau." %+% i %+% " = ")

tau.i <- as.numeric(tau.i)

tau <- c(tau, ifelse((tau.i >= 10 & tau.i <= 100) & (tau.i %% 10 == 0),

tau.i,

sample(seq(10, 100, 10), 1)))

}

} else {

tau <- sample(seq(10, 100, 10), m, replace = TRUE)

}

max.path <- rep(0, m)

for(i in m : 1) {

if(length(X[[i]]) != 0) {

for(j in 1 : length(X[[i]])) {

if(max.path[i] == 0) {

max.path[i] <- tau[i]

}

x <- tau[X[[i]][j]] + max.path[i]

if(max.path[X[[i]][j]] < x) {

max.path[X[[i]][j]] <- x

}

}

}

}

clc()

T.crit <- max(max.path)

T.o <- sum(tau)

K.pr <- ceiling(T.o / T.crit)

cat("T.кр = ", T.crit,

"\nT.о = ", T.o,

"\nK.пр = ", K.pr, "\n")