Расчет задач вычислительных систем

МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ

“ХАРКІВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ”



Кафедра “Обчислювальна техніка та програмування”













РГЗ

з курсу “Комп’ютерні системи”

Варіант № xxxx













Виконав:

Студент групи xxxx

xxxxxx.

Перевірив:

xxxxxxxxx.







Харків 2007


Задача №1



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

 ,

де  – условие окончания расчетов.



Решение

Однопроцессорный алгоритм решения заданной задачи:





Многопроцессорный алгоритм решения задачи:







Программа на параллельном Паскале:

Program par_pascal;

Var

		R, S, x, f, L, e	: real;

K	: longinteger;

BEGIN

FORK;

begin

read(e);

R := 0;

K = 1;

end;

begin

read(x) ;

S := x;

F := x*x;

end;

JOIN;

repeat

FORK;

begin

R := R + S;

L = S*(-1);

end;

begin

K = K + 2;

Z=1/(K*(K-1))

end;

JOIN;

S := L*z;

until (ABS(S) > e);

writeln(R);

END.


Задача №2



Спроектировать два универсальных программируемых конвейера с числом звеньев m1 и m2 для вычисления массивы С длинной n элементов. Определить и сравнить эффективности конвейеров и выполнить анализ полученных результатов. Определить размер буферной памяти между звеньями. 

Длительность операций:



Чтение, запись

4

+, -

3

*, /

5

, 

6

инкремент, декремент

1



m1 = 5, m2 = 6.



Решение

Составим таблицу операций:

№ п/п

Операция 

Количество тактов

1

чтение 

4

2

чтение 

4

3

вычисление 

5

4

вычисление  

5

5

вычисление 

3

6

вычисление 

3

7

вычисление 

5

8

вычисление 

5

8

вычисление 

3

9

вычисление 

3

10

вычисление

6

11

вычисление

5

12

вычисление

5

13

запись 

4

14

n = n -1

1

15

if n >…, goto п. 1

1



Тпосл = 6т + 65т +34т + 43т + 21т = 62т

при m = 4 Тзв.треб.1 62т / 5 = 12,4 = 13;

при m = 6 Тзв.треб.2 62т / 6 = 10,33 = 11;

Распределение операций между звеньями конвейера при m = 5:







Входные данные поступают на первое ( и ) звено, обратной линией отмечено управление конвейером (когда на первом звене выполняется условие n>0, то на пятом звене оно соответствует условию n-4>0; это условие проверяется на пятом, и сигнал о чтении следующего значения или прекращение чтения поступает на первое звено).

Распределение операций между звеньями конвейера при m = 6:







Графики загрузки процессоров







Для m = 5 Тдейств = 13.

Для m = 6 Тдейств = 11.



Для m = 5  

при  .

Для m = 6  

при  ,

 – эффективность конвейера на 6-ть шагов выше.

Размер буферной памяти между звеньями:

при m = 5 – 5 элементов;

при m = 6 – 5 элементов.

Критическая длина массива

	m=5	m=6

	=1	=1

		

		

Вывод: Наиболее эффективна конвейерная обработка при наибольшем числе звеньев конвейера. Критическая минимальная эффективная длина массива для обработки конвейером – 2. 


Задача №3



Реализовать заданные функции на вычислительных системах с программируемой структурой.

а) 

б) 



Решение

a) 



Схема элементарного процессора:



б)  = 

Схема элементарного процессора:






Задача №4



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





Составили граф-схему модели:







Система уравнений:



Решили систему уравнений:





Определили середнюю продолжительность каждого состояния:

t0=; t1=; t2=; t3= .

Задача №5

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







Каждый модуль может находиться в одном из состояний: рабочее – “1”, нерабочее – “0”. 

Состояния системы:

S0 — все ЭВМ рабочие;

S1 —	одна из ЭВМ 2, ЭВМ 3 не работает, а ЭВМ 1 работает;

S2 —	ЭВМ 2, ЭВМ 3 не работают, ЭВМ 1 работает;

S3 —	ЭВМ 2, ЭВМ 3 работают, ЭВМ 1 не работает;

S4 —	одна из ЭВМ 2, ЭВМ 3 не работает, а ЭВМ 1 не работает;

S5 — все ЭВМ не работают.

Таблица состояний:

Si

ЭВМ2, ЭВМ3

ЭВМ1

Состояние системы

S0

11

1

1

S1

01v10

1

1

S2

00

1

1

S3

11

0

1

S4

10v01

0

0

S5

00

0

0



Система уравнений:



Граф переходов имеет вид:





Исключим выходящие стрелки из отказных состояний и получим граф переходов для задачи Шерра II рода:







Система уравнений:



Задали  и . Решили данные системы уравнений в математическом пакете MathCad:







Полученные вектор-матрицы – решения сформулированных систем уравнений, задающих вероятности состояний вычислительной системы.