Министерство образования Российской Федерации

Московский Государственный технический Университет им. Н.Э. Баумана

Факультет «Аэрокосмический»

Лабораторная работа №2

по теме: «Преобразование последовательного алгоритма в параллельный»

по курсу «Вычислительные системы»

Выполнил

студ. гр. АК5-91 Гукетлев Д.В.

Проверил

к.т.н., доц. Руденко Ю.М.

2011

Цель работы:

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

Ответы на контрольные вопросы:

1. 
   Чем отличается последовательный код от параллельного?
   

У параллельного кода выделяются параллельные ветви вычислений. Алгоритмы с выделенными параллельными ветвями.

2. 
   Почему символы ввода-вывода данных, а также символы «терминатор» исключены из схемы параллельного алгоритма?
   

При параллельном выполнении программ окончание алгоритма зависит от составленного плана решения задачи, поэтому символ «терминатор» конца и начала алгоритма надо исключить.

3. 
   Какое правило положено в основу определения зависимости блоков алгоритма по переменным?
   

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

Разобьем последовательный алгоритм на линейные участки, заключенные между логическими операторами. Каждый логический оператор порождает не менее двух линейных участков. Линейный участок, образованный входом в алгоритм логическии оператором, назовем начальным. Начальный участок может содержать несколько операторов. Следующий за начальным участок начинается и заканчивается логическим оператором, т.е. если участок U_i состоит из множества операторов {Lⁱ_j,cⁱ₁,...,cⁱ_ni,Lⁱ_j+1}, то следующий участок U_i+1 = {Lⁱ⁺¹_j+1,cⁱ⁺¹₁,...,cⁱ⁺¹_ni+1,Lⁱ⁺¹_j+2} и т.д., где Lⁱ_j, Lⁱ_j+1, Lⁱ⁺¹_j+1, Lⁱ⁺¹_{j+2 –} логические операторы, причем Lⁱ_j+1 = Lⁱ⁺¹_j+1 , а cⁱ₁,...,cⁱ_ni , cⁱ⁺¹₁,...,cⁱ⁺¹_ni+1 - некоторые операторы. Таким образом, последний логический оператор L_j+1 участка U_i является первым оператором для участка U_i+1. На каждом участке операторы пронумированы: 1, 2, ..., u_k. Последние участки - это линейные участки, не имеющие в качестве последнего оператора логических операторов. Пусть в результате такого разбиения образовалось N участков k = 1, ..., N , в каждом из которых оказалось u_k операторов.

4. 
   Какие еще зависимости по переменным между блоками алгоритма следует учесть при реализации алгоритма 3.1?
   

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

5. 
   Как образуются дополнительные входы в алгоритм?
   

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

6. 
   Как проводиться разбиение алгоритма на ветви?
   

Разобьем последовательный алгоритм на линейные участки, заключенные между логическими операторами. Каждый логический оператор порождает не менее двух линейных участков. Линейный участок, образованный входом в алгоритм логическии оператором, назовем начальным. Начальный участок может сожержать несколько оператором. Следующий за начальным участок начинается и заканчивается логическим оператором, т.е. если участок U_i состоит из множества операторов {Lⁱ_j,cⁱ₁,...,cⁱ_ni,Lⁱ_j+1}, то следующий участок U_i+1 = {Lⁱ⁺¹_j+1,cⁱ⁺¹₁,...,cⁱ⁺¹_ni+1,Lⁱ⁺¹_j+2} и т.д., где Lⁱ_j, Lⁱ_j+1, Lⁱ⁺¹_j+1, Lⁱ⁺¹_{j+2 –} логические операторы, причем Lⁱ_j+1 = Lⁱ⁺¹_j+1 , а cⁱ₁,...,cⁱ_ni , cⁱ⁺¹₁,...,cⁱ⁺¹_ni+1 - некоторые операторы. Таким образом, последний логический оператор L_j+1 участка U_i является первым оператором для участка U_i+1. На каждом участке операторы пронумированы: 1, 2, ..., u_k. Последние участки - это линейные участки, не имеющие в качестве последнего оператора логических оператором. Пусть в результате такого разбиения образовалось N участков k = 1, ..., N , в каждом из которых оказалось u_k операторов.

Схема исходного последовательного алгоритма:

Схема преобразованного параллельного алгоритма:





Выводы

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