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

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

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

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

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

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

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

Общая тема:

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

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

Часть 2

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

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

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

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

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

5033.7491.0000-ПЗ

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

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

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

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

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

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

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

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

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

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

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

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

2007

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

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-й вариант

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

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

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

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

СФА 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₇)))

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

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

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

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

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

Вариант 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: Штрих-схема алгоритма / ГИ: Горизонтальное исполнение

Вариант 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.1: Структурная формула алгоритма / У: Поток управления

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.2: Структурная формула алгоритма / У: Поток управления

// Замена обозначений: "®" - "—"; "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           Расчеты параметров алгоритмов

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

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

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

mai = tai^о — tai^н,

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

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

Вариант 1

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

Вариант 2

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

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

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

Вариант 1

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

Вариант 2

ma582" = mz7 + mz6 + mz0 = 95

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

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

Вариант 1

ma581' = 105 = ma581" = 105

Вариант 2

ma582' = 45 = ma582" = 95

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

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

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

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

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

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

Вариант 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

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

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

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

Вариант 1

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

Вариант 2

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

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