Расчетно-графическая работа №2

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

Уфимский государственный авиационный технический университет

Факультет ИРТ: Информатика и робототехника

Кафедра КМ: Компьютерная математика

Учебная дисциплина:

Математическая логика и теория алгоритмов

РГР: Расчетно-графическая работа

Общая тема:

ПАРАЛЛЕЛЬНЫЕ ЛОГИКО-АЛГОРИТМИЧЕСКИЕ СИСТЕМЫ

(алгоритмы и логика, аппаратная и программная реализация)

Часть 2

ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ.

ВРЕМЕННЫЕ ДИАГРАММЫ.

(техника построений,

параметрический расчет и анализ)

Пояснительная записка

5033.7491.0000-ПЗ

Направление подготовки:

654600: ИВТ: Информатика и вычислительная техника

Специальность:

САПР: Системы автоматизированного проектирования

Курс обучения: 2

Учебная группа: САПР-230

Работу выполнил (выполнила)

студент (студентка) _____________ Манаев Р.Н.

Зачетная книжка № 065490

Вариант задания: A230

Работу принял

должность _____________ Житников А.П.

2007

1. Исходные условия

1. Индивидуальное задание

Комплект исходных формул алгоритмов

Задан комплект A580 структурных формул алгоритмов:

А581=Z₇((Z₁ & Z₆(Z₀&Z₃Z₆))& Z₇(Z₄ & Z₅)Z₇) 1-й вариант СФА группы A580

А582= Z₇((Z₁ & Z₆(Z₀&Z₃Z₆)) V Z₇(Z₄ & Z₅)Z₇) 2-й вариант СФА группы A280

A583 = Z₇((Z₁ ¹& Z₆(Z₀&Z₃Z₆)) V Z₇(Z₄ & Z₅ _&¹)Z₇) 3-й вариант

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

2. Восстановление стандартной формы структурных формул

1. Стандартная форма формулы алгоритма

По исходной СФА строится стандартная СФА – полная инфиксная форма.

СФА 0.1: Структурная формула алгоритма / У: Поток управления

ИнФ: Инфиксная форма записи формулы

СИнФ: Сокращенная инфиксная форма // исходная форма

// Неявная операция суперпозиции

Вариант 1 (A581):

Z₇((Z₁ & Z₆(Z₀&Z₃Z₆))& Z₇(Z₄ & Z₅)Z₇) =

Вариант 2 (A582):

Z₇((Z₁ & Z₆(Z₀&Z₃Z₆)) V Z₇(Z₄ & Z₅)Z₇) =

ПИнФ: Полная инфиксная форма // пошаговое построение

Поэтапная простановка неявных операций суперпозиции:

Вариант 1 (A581)

= Z₇ - ((Z₁ & Z₆ - (Z₀&Z₃ - Z₆))& Z₇ - (Z₄ & Z₅) - Z₇) =

Вариант 2 (A582)

= Z₇ - ((Z₁ & Z₆ - (Z₀&Z₃ - Z₆)) V Z₇ -(Z₄ & Z₅) - Z₇) =

Вариант 1 (A581)

= (Z₇ - ((Z₁ & Z₆ - (Z₀&(Z₃ - Z₆)))& (Z₇ - (Z₄ & Z₅) - Z₇))) =

Вариант 2 (A582)

= (Z₇ - ((Z₁ & Z₆ - (Z₀&(Z₃ - Z₆))) V (Z₇ -(Z₄ & Z₅) - Z₇))) =

Основная стандартная форма записи СФА

Вариант 1 (A581)

Явная операция суперпозиции:

= (Z₇  ((Z₁ & Z₆  (Z₀&(Z₃  Z₆)))& (Z₇  (Z₄ & Z₅)  Z₇))) =

Неявная операция суперпозиции:

= (Z₇((Z₁ & Z₆(Z₀&(Z₃Z₆)))& (Z₇(Z₄ & Z₅)Z₇))) =

Вариант 2 (A582)

Явная операция суперпозиции:

= (Z₇  ((Z₁ & Z₆  (Z₀&(Z₃ Z₆))) V (Z₇  (Z₄ & Z₅)  Z₇))) =

Неявная операция суперпозиции:

= (Z₇((Z₁ & Z₆(Z₀&(Z₃Z₆))) V (Z₇(Z₄ & Z₅)Z₇)))

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

1. Исходные условия

Выполняется работа с программой GRAMPRAL.

В программу вводятся СФА в полном формате:

ПИнФ: Полная инфиксная форма – с явными операциями суперпозиции (–) и всеми необходимыми парами скобок (внешние скобки могут не вводиться).

2. Вариант 1 структурной схемы. Автоматизация построений

СФА 0.2: Структурная формула алгоритма / У: Поток управления

// Замена обозначений: "" на "–"

A581 = (Z₇  ((Z₁ & Z₆  (Z₀&(Z₃  Z₆)))& (Z₇  (Z₄ & Z₅)  Z₇)))

A581 = (Z₇ - ((Z₁ & Z₆ - (Z₀&(Z₃ - Z₆₎)))& (Z₇ - (Z₄ & Z₅) - Z₇)))

Набор формулы:

Настройки программы: ИнФ / ГИ / БСА / БФ

БСА 0.1: Блок-схема алгоритма / ГИ: Горизонтальное исполнение

Настройки: ИнФ / ГИ / ШСА / БФ

ШСА 0.1: Штрих-схема алгоритма / ГИ: Горизонтальное исполнение

3. Вариант 2 структурной схемы. Автоматизация построений

СФА 0.3: Структурная формула алгоритма / У: Поток управления

// Замена обозначений: "" на "–". "V" на "|"

А582 = (Z₇  ((Z₁ & Z₆  (Z₀&(Z₃ Z₆))) V (Z₇  (Z₄ & Z₅)  Z₇)))

А582 = (Z₇ - ((Z₁ & Z₆ - (Z₀&(Z₃ - Z₆))) V (Z₇ -(Z₄ & Z₅) - Z₇)))

Набор формулы

Настройки: ИнФ / ГИ / БСА / БФ

БСА 0.2: Блок-схема алгоритма / ГИ: Горизонтальное исполнение

Настройки: ИнФ / ГИ / ШСА / БФ

ШСА 0.2: Штрих-схема алгоритма / ГИ: Горизонтальное исполнение

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

2.1 Вариант 1 диаграммы (A141). Автоматизация построений

Используется программа GRAMPRAL

СФА 2.4: Структурная формула алгоритма / У: Поток управления

A581 = (Z₇  ((Z₁ & Z₆  (Z₀&(Z₃  Z₆)))& (Z₇  (Z₄ & Z₅)  Z₇)))

A581 = (Z₇ - ((Z₁ & (Z₆ - (Z₀&(Z₃ - Z₆))))& (Z₇ - (Z₄ & Z₅) - Z₇)))

Набор формулы и данных:

ДИА 2.1: Диаграмма исполнения алгоритма

ЛД: Линейная (временная) диаграмма

СД: Сетевая (временная) диаграмма:

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

нумерация

2.2 Вариант 2 диаграммы (A142). Автоматизация построений

Используется программа GRAMPRAL.

СФА 2.5: Структурная формула алгоритма / У: Поток управления

// Замена обозначений: "" - "–"; "V" - "|"

А582 = (Z₇  ((Z₁ & Z₆  (Z₀&(Z₃ Z₆))) V (Z₇  (Z₄ & Z₅)  Z₇)))

А582 = (Z₇ - ((Z₁ & Z₆ - (Z₀&(Z₃ - Z₆))) | (Z₇ -(Z₄ & Z₅) - Z₇)))

Набор формулы и данных

ДИА 2.2: Диаграмма исполнения алгоритма

ЛД: Линейная (временная) диаграмма

СД: Сетевая (временная) диаграмма:

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

нумерация

3. Расчеты параметров алгоритмов

1. Графический расчет длительности алгоритма

1. Непосредственный отсчет длительности

Отсчет длины линии по времени начального и конечного события:

mai = tai^о – tai^н,

где tai^н – время начала (цикла) исполнения алгоритма Ai,

tai^о – время окончания (цикла) исполнения алгоритма Ai.

Вариант 1

ma581' = ta581^о – ta581^н = 125 – 20 = 105

Вариант 2

ma582' = ta582^о – ta582^н = 115 – 20 = 95

2. Графический расчет длины линии

Расчет выполняется по критическому пути временного графа:

Вариант 1

ma581" = mz7 + mz7 + mz4 + mz7 = 105

Вариант 2

ma582" = mz7 + mz6 + mz0 = 95

3. Проверка результатов

Выполняется проверка соотношения mai' =? mai":

Вариант 1

ma581' = 105 = ma581" = 105

Вариант 2

ma582' = 45 = ma582" = 95

Вывод: данные графического отсчета и расчета совпадают.

2. Аналитический расчет длительности алгоритма

1. Подготовка формулы расчета длительности

СФА 3.6: Структурная формула алгоритма / У: Поток управления

ИнФ: Инфиксная форма

ПИнФ: Полная инфиксная форма

Вариант 1

A581 = (Z₇  ((Z₁ & (Z₆  (Z₀&(Z₃  Z₆))))& (Z₇  (Z₄ & Z₅)  Z₇))) = Вариант 2

А582 = (Z₇  ((Z₁ & (Z₆  (Z₀&(Z₃ Z₆)))) V (Z₇  (Z₄ & Z₅)  Z₇))) =

// удаление наружных скобок (не нужны для последующего)

Вариант 1

= Z₇  ((Z₁ & (Z₆  (Z₀&(Z₃  Z₆))))& (Z₇  (Z₄ & Z₅)  Z₇)) =

Вариант 2

= Z₇  ((Z₁ & (Z₆  (Z₀&(Z₃ Z₆)))) V (Z₇  (Z₄ & Z₅)  Z₇)) =

ШФР 3.1: Шаблон формулы расчета

КоФ: Комбинированная форма

ИнПрФ: Инфиксно-префиксная форма

Вариант 1 // пошаговое построение

= Z₇  ((Z₁ & (Z₆  (Z₀&(Z₃  Z₆))))& (Z₇  &(Z₄ , Z₅)  Z₇)) =

= Z₇  (&(Z₁ , (Z₆  &(Z₀ , (Z₃  Z₆))))& (Z₇  &(Z₄ , Z₅)  Z₇)) =

= Z₇  &(&(Z₁ , (Z₆  &(Z₀ , (Z₃  Z₆)))) , (Z₇  &(Z₄ , Z₅)  Z₇)) =

Вариант 2 // пошаговое построение

= Z₇  V(&(Z₁ , (Z₆  &(Z₀ , (Z₃  Z₆)))) , (Z₇  &(Z₄ , Z₅)  Z₇)) =

= Z₇  V(&(Z₁ , (Z₆  &(Z₀ , (Z₃  Z₆)))) , (Z₇  &(Z₄ , Z₅)  Z₇)) =

// операция суперпозиции () остается в инфиксах

// операции конъюнкции (&) и дизъюнкции (V) выносятся в префиксы

ТЗО 3.1: Таблица замены обозначений

Компоненты ШФР	Ai	Zi		&	V
Компоненты ФРД	mai	mZi	+	Max	Min

ФРД 3.1: Формула расчета длительности

// получается из ИнПрФ заменой обозначений по ТЗО

Вариант 1 // пошаговое построение

ma581"' = mZ₇ + Max(Max(mZ₁ , (mZ₆ + Max(mZ₀ , (mZ₃ + mZ₆)))) , (mZ₇ + Max(mZ₄ , mZ₅) + mZ₇))

Вариант 2 // пошаговое построение

ma582"'= mZ₇ + Min(Max(mZ₁ , (mZ₆ + Max(mZ₀ , (mZ₃ + mZ₆)))) , (mZ₇ + Max(mZ₄ , mZ₅) + mZ₇))

Расчет длительности алгоритма

Подставить данные (длительности mzi команд Zi) в ФРД.

РДА 3.1: Расчет длительности алгоритма

// общая длительность mai цикла выполнения алгоритма Ai

Вариант 1

ma581"' = 20 + Max(Max(30 , (10 + Max(65 , (35 + 10)))) , (20 + Max(45 , 40) + 20)) = 105

Вариант 2

ma582"' = 20 + Min(Max(30 , (10 + Max(65 , (35 + 10)))) , (20 + Max(45 , 40) + 20)) = 95

2. Общая проверка результатов

Проверка результатов mai'" =? mai":

// данные совпадают (mai"' = mai") или не совпадают (mai"'  mai")

Вариант 1

ma581"' = 105 = ma581" = ma581' = 105

Вариант 2

ma582"' = 45 = ma582" = ma582' = 95

Вывод: данные графического и аналитического расчета совпадают.

9