Лабораторные работы по информатике

Практикум по механике и молекулярной физике
ОПРЕДЕЛЕНИЕ МОМЕНТА ИНЕРЦИИ
МАТЕМАТИЧЕСКИЙ МАЯТНИК
Физический маятник
ОПРЕДЕЛЕНИЕ МОДУЛЯ ЮНГА
ПОПЕРЕЧНЫЕ КОЛЕБАНИЯ СТРУНЫ
ОПРЕДЕЛЕНИЕ КОЭФФИЦИЕНТА ВЯЗКОСТИ
ОПРЕДЕЛЕНИЕ КОЭФФИЦИЕНТА ПОВЕРХНОСТНОГО НАТЯЖЕНИЯ
ОПРЕДЕЛЕНИЕ ВЛАЖНОСТИ ВОЗДУХА
ОПРЕДЕЛЕНИЕ АДИАБАТИЧЕСКОЙ ПОСТОЯННОЙ ВОЗДУХА
Вынужденные колебания линейного осциллятора
Лабораторные работы по информатике
Определение параметров n-мерных коммутационных структур
Преобразование последовательного алгоритма в параллельный
Представление алгоритмов в виде граф–схем.

Построение матрицы логической несовместимости операторов

Построение множеств взаимно независимых операторов
Определение ранних и поздних сроков окончания выполнения операторов
Запуск параллельных программ на кластере
Microsoft Visio
Спецификация требований к информационной системе
Основы работы в редакторе деловой графики Microsoft Visio 2010.
Лабораторная работа №3
Лабораторная работа №4
Функциональное моделирование
Диаграмма классов
Алгоритмические основы машинной графики

Анимация и морфинг

Отсечение прямоугольным окном
Построение проекции трехмерного объекта
Создание простых объектов
Основные навыки работы с объектами
Привязка объектов
Редактирование формы произвольных кривых
Приемы работы с контурами объектов
Создание цветных изображений
Обмен изображениями с другими программами
Ввод и редактирование текста
СИСТЕМА АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ AutoCAD
Основы работы с использованием системы AutoCAD
Команды рисования
Нанесение надписей
Команды редактирования
Проставление размеров на чертеже
Работа с блоками чертежа
 

Лабораторная работа №2. Преобразование последовательного алгоритма в параллельный

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

Теоретическая часть

При организации вычислений на ВС на первый план выходит проблема создания параллельных алгоритмов.

Определение 2.1. Параллельный алгоритм [1] – это описание процесса обработки информации, ориентированного на реализацию его с помощью вычислительных систем.

Определение 2.2. Представление параллельного алгоритма на языке программирования, доступном данной ВС, называется параллельной программой.

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

При создании параллельных программ будем использовать схемы программ в соответствии с ГОСТ 19.003-80 ЕСПД, ГОСТ 19.701-90 ЕСПД, хотя следует отметить, что создание параллельных процессов в решаемых задачах и отображение их в таких схемах – достаточно трудоёмкая задача. В связи с этим, предложена следующая процедура создания параллельных схем алгоритмов или программ.

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

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

Не ограничивая общности рассуждений, можно считать, что при изображении параллельных алгоритмов можно ограничиться обозначениями логических выходов операторов типа “IF”, “CASE” в виде “№.n”, где № – номер рассматриваемого логического оператора, n – номер выхода из логического оператора. Такое обозначение позволяет упорядочить существующие обозначения: «истина», «ложь», «FALSE», «TRUE», «>», «<» ,«<>» и т.д., что создает определённые удобства при дальнейшем анализе схем алгоритмов в виде граф–схем.

Традиционное изображение вводимой информации в указанных ГОСТах более или менее приемлемо для ВС с общей памятью и совсем не приемлемо для ВС с разделяемой памятью, так как вводится достаточно искусственная зависимость программных модулей по данным. Эта зависимость существенно сужает возможности распараллеливания решаемой задачи. При рассмотрении ВС с разделяемой памятью ввод-вывод информации включается в процесс обмена информацией между процессорами и таким образом учитывается в планировании вычислительного процесса. В связи с этим при рассмотрении ВС с общим полем памяти считается, что вся исходная информация введена в поле общей памяти и на схеме не показывается. Аналогично решаем проблему вывода. Выводимая информация также находится в поле общей памяти. Отсутствие символа вывода (например, параллелограмма) можно объяснить тем, что преобразование и вывод информации не включается в план решения параллельных задач. В связи с этим при преобразовании исходного алгоритма в параллельный опускаются символы ввода-вывода информации.

Сущность алгоритма преобразования схемы последовательного алгоритма в схему параллельного алгоритма заключается в следующем. Разобьем последовательный алгоритм на линейные участки, заключенные между логическими операторами. Каждый логический оператор порождает не менее двух линейных участков. Линейный участок, образованный входом в алгоритм и логическим оператором назовем начальным. Начальный участок может содержать только один оператор. Следующий за начальным участок начинается и заканчивается логическим оператором, т. е., если участок Ui состоит из множества операторов , то следующий участок  и т. д., где  – логические операторы, причем , а  – некоторые операторы. Таким образом, последний логический оператор Lj+1 участка Ui является первым оператором для участка Ui+1. На каждом участке операторы перенумерованы: 1, 2, …, uk. Последние участки – это линейные участки, не имеющие в качестве последнего оператора логический оператор. Пусть в результате такого разбиения образовалось N участков k = 1, …, N, в каждом из которых оказалось uk операторов.

Назовём связи, входящие в вычислительный или логический блоки, входными; выходящие из этих блоков – выходными. Будем полагать, что в каждый блок может входить и выходить несколько связей. Для упрощения анализа зависимости рассматриваемого программного модуля от предыдущих в анализируемом алгоритме принята следующая схема: анализируемый алгоритм представляет собой последовательность программных модулей (процедур и/или функций). Обмен данными между ними происходит только через параметры, указанные в списке при вызове модулей. Результаты работы модуля передаются через параметры, формируемые как <имя параметра> ::= <префикс> <имя модуля>. Так, например, на рисунке 2.1 модуль с именем АВ передает результаты своих вычислений через параметр SAB и т.д. Модуль DE использует данные, формируемые модулем АВ, что означает, что модуль DE зависит по данным от модуля АВ и т.д. Нетрудно заметить, что предлагаемое упрощение не является принципиальным и в случае необходимости легко можно учесть зависимости программных модулей по данным, осуществляемых с помощью понятий глобальных переменных различных уровней.

Алгоритм 2.1. Преобразование схемы последовательного алгоритма в параллельную.

1.  Вычислим k:=1, MV:= Ø – множество входов в алгоритм, Flag:=TRUE.

2.  Если uk*2, то выполнить шаг 3, иначе – шаг 13.

3. Вычислим uk = 1.

4. Вычислим v:=uk, uk:=uk+1.

5. Если uk uk*, то выполнить шаг 6, иначе – шаг 16.

6. Если uk зависит от v, то выполнить шаг 7, иначе – шаг 11. 

7.  Проводим связь из блока v в блок uk.

8. Вычислим Flag:=False.

9.  Вычислим v:=v-1.

10. Если v < 1, то переходим к шагу 4, иначе – шаг 6.

11. Если Flag:=TRUE, то переходим к шагу 12, иначе – шаг 9.

12.  Вычислим MV:= MV{uk} и переходим к шагу 9,

Если uk*=2, то переходим к шагу 14, иначе – шаг 15.

14.  Вычислим MV:= MV +{1}.

15. Все ли блоки имеют выходные связи? Если – «да», то выполнить шаг 16, 

иначе – шаг 17.

16. Вычислим k:=k+1 и затем выполним шаг 18.

17. Проводим связи из блоков uk в блок uk* и переходим к шагу 16.

 Если kN, то переходим к шагу 20, иначе – шаг 19.

19. Конец алгоритма.

 Очередной участок является внутренним? Если – «да», то выполнить шаг 21, иначе – шаг 34.

Если uk*=3, то  переходим к шагу 22, иначе – шаг 23.

Проводим связи из блоков uk =1 в блок uk =2 и uk =2 в блок uk* =3 и переходим к шагу 16. 

23. Вычислим uk: = 2 .

24. Вычислим v:=uk, uk:=uk+1.

25. Если uk < uk*, то выполнить шаг 26, иначе – шаг 30.

26. Если uk зависит от v, то выполнить шаг 27, иначе – шаг 28. 

27. Проводим связь из блока v в блок uk.

28. Вычислим v:=v-1 и затем выполним шаг 29.

29. Если v < 2, то переходим к шагу 24, иначе – шаг 26.

30. Все ли блоки имеют входные связи? Если – «да», то выполнить шаг 32, 

иначе – шаг 35.

31. Проводим связи из блока uk =1 в блоки, не имеющих входных связей. 

32. Все ли блоки имеют выходные связи? Если – «да», то выполнить шаг 16, 

иначе – шаг 33.

Провести связи из блоков, не имеющих выходных связей, в блок uk*, и затем выполним шаг 16.

Если uk*=2, то переходим к шагу 35, иначе – шаг 36.

Проводим связи из блоков uk =1 в блок uk* и переходим к шагу 16.

Вычислим uk: = 2.

Вычислим v:=uk, uk:=uk+1.

Если uk < uk*, то выполнить шаг 39, иначе – шаг 43.

Если uk зависит от v, то выполнить шаг 40, иначе – шаг 41.

Проводим связь из блока v в блок uk и переходим к шагу 41.

Вычислим v:=v-1.

Если v < 2, то переходим к шагу 37, иначе – шаг 39.

Все ли блоки имеют входные связи? Если – «да», то выполнить шаг 16,

иначе – шаг 44.

44. Проводим связи из блока uk =1 в блоки, не имеющих входных связей, и 

переходим к шагу 16. 

Результат работы данного алгоритма показан на рисунке 2.2 (исходным является алгоритм, изображённый на рисунке 2.1).

Рисунок 2.1. Классическая схема алгоритма

Рисунок 2.2. Схема модифицированного алгоритма

Вопросы для самопроверки

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

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

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

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

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

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

Задание на лабораторную работу

Создать и отладить программу для преобразования последовательного алгоритма в параллельный и проиллюстрировать её работоспособность на заданном варианте алгоритма, предусмотрев возможность редактирования информации на один или два шага назад («откат»). После написания программы необходимо ввести в неё последовательный алгоритм, выданный преподавателем, предпочтительно в виде, показанном на рисунке 1. Результирующий алгоритм представить также в соответствии с вышеуказанными ГОСТами. Сохранить программу для выполнения последующих лабораторных работ.

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

Продемонстрировать работающую программу преподавателю и получить отметку о её выполнении.

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

Оформить отчет о проделанной работе.

Содержание отчета

Цель работы.

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

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

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

Анализ полученных результатов.

Лабораторные работы