РГЗ по теории вычислительных процессов

Подождите немного. Документ загружается.

Содержание

Введение …………………………………………………………………….…........3

1 Теоретические предпосылки поставленной проблемы..………………………..4

2 Разработка программного средства……………………………..………............10

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

2.2 Установка и эксплуатация программного средства…………………............10

Заключение………………………………………………………………................11

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

Приложение А – Текст программы ………………………..……………….….....13

Лист

Введение

Параллельные ЭВМ, возникшие преимущественно для

высокопроизводительных научных вычислений, получают все более широкое

распространение: их можно встретить в небольших научных подразделениях и

офисах. Этому способствует как непрерывное падение цен на них, так и

постоянное усложнение решаемых задач. Поэтому выбранная тема данной

работы является актуальной.

Параллельная обработка - модель выполнения прикладного процесса

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

параллелизма:

-1- способ SIMD работы с одним потоком команд и несколькими потоками

данных, при котором все процессоры, работающие по одной программе,

обрабатывают собственные массивы данных под управлением ведущего

процессора;

-2- способ MIMD работы с несколькими потоками команд и несколькими

потоками данных, при котором процессоры работают по своим программам

независимо друг от друга, лишь эпизодически связываясь друг с другом;

-3- способ MISD работы с несколькими потоками команд и одним потоком

данных.

При написании параллельных программ ставятся следующие задачи:

1. Идентификация естественного параллелизма, который существует в

контексте предметной области.

2. Разбиение задачи, стоящей перед программным обеспечением, на

несколько подзадач, которые можно выполнять одновременно, чтобы

достичь требуемого уровня параллелизма.

3. Координация этих задач, позволяющая обеспечить корректную и

эффективную работу программных средств в соответствии с их

назначением.

В нашей работе предполагалось разработать программное средство

распараллеливания вычислительных алгоритмов, выполняющее определенные

функции. В соответствии с этим можно выделить следующие цели данной

работы:

- закрепление теоретических знаний в области теории распараллеливания

вычислительных алгоритмов;

- формирование практических умений и навыков разработки программного

средства для распараллеливания вычислительных алгоритмов;

- закрепление практических навыков самостоятельного решения

инженерных задач, развитие творческих способностей студентов и умений

пользоваться технической, нормативной и справочной литературой.

Лист

1 Теоретические предпосылки поставленной проблемы

Вариант №6.

A=(N

+3F)/2-(G+N)*(W-2Z), где



















.0,

;0,sin

;0,cos

WWG



















.0),2cos(

;0),2ln(

;0),sin(

ZGGZ

ZGZG

Cоставим блок-схему алгоритма решаемой задачи (рис. 1) и здесь можно

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

оператор.

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

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

арифметические операторы. На рисунке 1 они представлены в виде ромба и

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

определения порядка и состава выполнения операторов. Преемственность

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

ИСКЛЮЧАЮЩЕЕ ИЛИ.

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

выполнения операторов на основе информационных связей между ними, так как

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

Преемственность операторов при их выполнении осуществляется по схеме И.

Составим информационно-логическую граф-схему алгоритма (рис.2). С

помощью граф-схемы алгоритма можно ясно представить и проанализировать как

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

Далее составим матрицу следования S, в которой отражено множество

задающих связей в графе (рис.3).

На рисунке 4 представлена матрица транзитивности S

, отражающая

множество транзитивных связей, которые определены задающими связями и

заданы неявно. Из рис. 4 видно, что на главной диагонали располагаются

ненулевые элементы. Это означает, что контуров в графе нет.

На рисунке 5 изображена матрица логической несовместимости L,

задающая связи логической несовместимости. Данная матрица строится на

основе управляющих связей в графе, которые прямо указывают, что образующие

их операторы не могут выполняться одновременно ни при каких условиях.

Далее составим матрицу транзитивных связей логической несовместимости

(рис.6). Данная матрица представляет информацию о том, что могут ли, либо

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

алгоритма, т.е. при некотором наборе значений логических переменных. Матрица

S, дополненная транзитивными связями, отражает ограничения на порядок

выполнения операторов.

Лист

W>0

W=0

W<0

N:=G+Q

Вход (G, W, Z)

Q:= cos W

N:=G

N:=G - Q

Q:=sin W

:=N

A2:=G+Z

W=0

A2>0

A2=0

A2<0

Q:=2·Z

Q:=G+Z

A2=

Q:=2·Z

F:=sin Q

F:=ln S

S:=Q+G

F:=cos S

S:=Q

- G

A3:=3·F

A4:=A1+A3

:=2·Z

A4:=A4

:=W – Y

:=G+N

Лист

A5:=Y

·Y

A6:=A4 –

А5

Выход (A)

Рисунок 1 – Блок-схема алгоритма

Рисунок 2 – Информационно-логическая граф-схема алгоритма

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

1                         

2 *



                      

3 *                        

Лист

2 3

1110

171

4 *                        

5  1                       

6    1                     

7   1  1 1                   

8                         

9        1                 

10         *                

11         *                

12         *                

13          1               

14           1              

15            1             

16             1            

17              1           

18               1 1 1        

19       1           1       

20                   1      

21                         

22                     1    

23   1  1 1                   

24                      1 1  

25                    1    1 

Рисунок 3 – Матрица следования S

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

1                         

2 1



                      

3 1                        

4 1                        

5 1 1                       

6 1   1                     

7 1 1 1 1 1 1                   

8                         

9        1                 

10        1 1                

11        1 1                

12        1 1                

13        1 1 1               

14        1 1  1              

15        1 1   1             

16        1 1 1   1            

17        1 1  1   1           

18        1 1 1 1 1 1 1 1 1 1        

19 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1       

20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1      

21                         

22                     1    

23 1 1 1 1 1 1                   

24 1 1 1 1 1 1               1 1 1  

25 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 

Рисунок 4 – Матрица транзитивности S

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

1                         

2 



1 1                     

3  1  1                     

4  1 1                      

5                         

6                         

7                         

Лист

8                         

9                         

10           1 1             

11          1  1             

12          1 1              

13                         

14                         

15                         

16                         

17                         

18                         

19                         

20                         

21                         

22                         

23                         

24                         

25                         

Рисунок 5 - Матрица логической несовместимости L

 1 2 3 4 5 6 7 8 9 10 1 1 12 13 14 1 5 16 17 18 1 9 20 21 22 2 3 24 25

1                         

2 



1 1  1                   

3  1  1 1 1                   

4  1 1  1                    

5   1 1  1                   

6  1 1  1                    

7                         

8                         

9                         

10           1 1             

11          1  1             

12          1 1              

13                         

14                         

15                         

16                         

17                         

18                         

19                         

20                         

21                         

22                         

23                         

24                         

25                         

Рисунок 6 - Матрица транзитивных связей логической

несовместимости L

Построим для графа матрицу независимости M, отражающую

информационно-логические связи между операторами без учета их ориентации, а

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

связей (рис. 7). По нулевым элементам этой матрицы в столбце каждого

оператора можно указать множество тех операторов, каждый из которых при

выполнении некоторых условий может быть выполнен одновременно с данным,

т.е. он информационно или по управлению не зависит от данного оператора и не

является с ним логически несовместимым.

 1 2 3 4 5 6 7 8 9 10 11 12 1 3 14 15 16 17 18 19 20 21 22 23 24 25

Лист

1  1 1 1 1 1 1            1 1   1 1 1

2 1  1 1 1 1 1            1 1   1 1 1

3 1 1  1 1 1 1            1 1   1 1 1

4 1 1 1  1 1 1            1 1   1 1 1

5 1 1 1 1  1 1            1 1   1 1 1

6 1 1 1 1 1  1            1 1   1 1 1

7 1 1 1 1 1 1             1 1     1

8         1 1 1 1 1 1 1 1 1 1 1 1     1

9        1  1 1 1 1 1 1 1 1 1 1 1     1

10        1 1  1 1 1   1  1 1 1     1

11        1 1 1  1  1   1 1 1 1     1

12        1 1 1 1    1   1 1 1     1

13        1 1 1      1  1 1 1     1

14        1 1  1      1 1 1 1     1

15        1 1   1      1 1 1     1

16        1 1 1   1     1 1 1     1

17        1 1  1   1    1 1 1     1

18        1 1 1 1 1 1 1 1 1 1  1 1     1

19 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  1     1

20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1      1

21                      1  1 1

22                     1   1 1

23 1 1 1 1 1 1                  1 1

24 1 1 1 1 1 1               1 1 1  1

25 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 

Рисунок 7 - Матрица независимости М

2 Разработка программного средства

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

В соответствии с вариантом составить схему алгоритма предложенной

задачи, разбив ее на неделимые атомы.

Разработать программное средство распараллеливания вычислительных

алгоритмов. Программное средство должно выполнять следующие функции:

1) ввод и редактирование информационно-логической граф-схемы

вычислительного алгоритма;

2) нахождение транзитивных связей и связей логической

несовместимости операторов;

Лист

3) нахождение транзитивных связей логической несовместимости

операторов и независимости операторов;

4) нахождение множества взаимно-независимых операторов;

5) нахождение ранних и поздних сроков окончания выполнения

операторов алгоритма;

6) построение диаграммы выполнения операторов алгоритма;

оценка минимального числа п процессоров, необходимого для

выполнения заданного алгоритма за время Т;

оценка минимального времени Т выполнения заданного алгоритма

на ВС, содержащей п процессоров.

Листинг программы представлен в приложении А.

2.2 Установка и эксплуатация программного средства

Для установки данного программного средства необходимо скопировать

все содержимое папки «ТВП» на жесткий диск. Для запуска необходимо

запустить файл «parall.exe». Для установки надо иметь инсталлированный Builder

6, 2,5 МБ свободного места на жестком диске, не менее 32 МБ оперативной

памяти. Операционная система windows 98/NT/2000/XP.

Заключение

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

средство распараллеливания вычислительных алгоритмов. Оно выполняет

следующие функции:

1) ввод и редактирование информационно-логической граф-схемы

вычислительного алгоритма;

2) нахождение транзитивных связей и связей логической несовместимости

операторов;

3) нахождение транзитивных связей логической несовместимости

операторов и независимости операторов;

4) нахождение множества взаимно-независимых операторов;

Лист

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

алгоритма;

6) построение диаграммы выполнения операторов алгоритма;

Лист