Главная / Естественные науки / Математика / Математическая логика

Расчетно-графическая работа №5 / РГР №5 (готово).doc

Вернуться к описанию файла

Скачать

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

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

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

Кафедра ПСИ: Проектирование систем информатики

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

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

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

Общая тема:

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

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

Часть 5

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

МНОГОПОТОЧНАЯ РЕАЛИЗАЦИЯ

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

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

5033.7491.0000-ПЗ

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

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

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

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

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

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

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

студент Манаев Р. Н.

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

Вариант задания: А580

Работу принял _____________ Житников А. П.

2007

1.1 Исходное описание алгоритма

СФА: Структурная формула алгоритма

Алгоритм операционного цикла // включая загрузку и разгрузку

A = (Zz — A581 — Zr)

Алгоритм этапа обработки:

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

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

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

Ввод явного отражения парной операции параллельной конъюнкции (#&):

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

= (Z₇((Z_{1 #}& (Z₆(Z_{0 #}& (Z₃Z₆))))_#& (Z₇(Z_{4 #}& 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₄, Z₅)& - Z₇))) =

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

ССА: Структурная схема алгоритма. Вариант 1. Линейный стиль

ШТА: Штрих-схема алгоритма

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

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

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

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

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

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

1.2 Специальная подготовка алгоритма

ССА: Структурная схема алгоритма. Вариант 2. Мозаичный стиль

СФА: Структурная формула алгоритма

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

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

ШСА: Штрих-схема алгоритма

Связный вариант

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

A581 = #(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₇)

= #(Z₇ - (#(Z₁, ---------------------------)&, -------------------------))& =

(Z₆ — #(Z₀, ---------)&) , (Z₇- #(Z₄, ---)& - Z₇)

(Z₃- Z₆) Z₅

Разделение потоков команд алгоритма:

A20:

A10:

Замена обозначений

A20:

A40:

A30:

A10:

Итоговая СФА: Структурная формула алгоритма:

Исходный параллельный алгоритм представлен системой линейных последовательных алгоритмов, взаимосвязанных командами узловой передачи-приемки управления:

1) Дополнительные алгоритмы (подалгоритмы), выделяемые в дополнительные потоки (упаковываются в треды):

A40 = Z5

A30 = Z7 — FA40 — Z4 — JA40 — Z7

A20 = Z3 — Z6

A10 = Z6 — FA20 — Z0 — JA20

2) Основной алгоритм (в основном потоке):

A581 = FA30 — FA10 — Z1 — JA10 — JA30

Структурные операторы:

FZi = F(Zi) = Fork(Zi) — оператор узла вилки:

упаковка в поток и вызов команды Zi в потоке

J&Zi = J&(Zi) = Join_&(Zi) — оператор узла сборки:

ожидание (wait) завершения команды Zi

Вербальные (словесные) тексты алгоритма

Промежуточные Питон-подобные формы записи алгоритма

ВТА: Вербальный текст алгоритма

ГИ: Горизонтальное исполнение

ШТА: Шаблон текста алгоиртма

A40 = Z5

A30 = Z7 — FA40 — Z4 — JA40 — Z7

A20 = Z3 — Z6

A10 = Z6 — FA20 — Z0 — JA20

A581 = FA30 — FA10 — Z1 — JA10 — JA30

РТА: Рабочий текст алгоритма

alg A40( ): Zh5( )

alg A30( ): Zh7; Fork(A40( )); Zh4; Join_&(A40( ));Zh7

alg A20( ): Zh3( );Zh6

alg A10( ): Zh6; Fork(A20( )); Zh0; Join_&(A20( ))

alg A581( ): Fork(A30( )); Fork(A10( )); Zh1( ); Join_&(A10( )); Join_&(A30( ))

ВИ: Вертикальное исполнение

ШТА:

Шаблон текста алгоритма

РТА:

Рабочий текст алгоритма

A40 =

| Z5

A40 =

| Z5

Alg40:

Zh5()

A30 =

—

FA40

—

JA40

—

A30 =

Z7 —

FA40 —

Z4 —

JA40 —

A30 =

| Z7 —

| FA40 —

| Z4 —

| JA40 —

| Z7

A30 =

| Z7

| FA40

| Z4

| JA40

| Z7

alg A30():

Zh7( )

Fork(A40( ))

Zh4

Join_&(A40( ))

Zh7( )

A20 =

—

A20 =

Z3—

A20 =

| Z3—

| Z6

A20 =

| Z3

| Z6

Alg20:

Zh3()

Zh6()

A10 =

—

FA20

—

JA20

A10 =

Z6 —

FA20—

Z0 —

JA20

A10 =

| Z6 —

| FA20—

| Z0 —

| JA20

A10 =

| Z6

| FA20

| Z0

| JA20

alg A10():

Zh6( )

Fork(A20( ))

Zh0

Join_&(A20( ))

A581= FA30

—

FA10

—

JA10

—

JA30

A581= FA30 —

FA10—

Z1—

JA10 —

JA30—

A581=

| FA30 —

| FA10—

| Z1—

| JA10 —

| JA30—

A581=

| FA30

| FA10

| Z1

| JA10

| JA30

alg A581():

Fork(A30())

Fork(A10())

Zh1()

Join_&(A10())

Join_&(A30())

1.3 Многопоточная программная реализация алгоритма

Реализация компонент алгоритма

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

Язык программирования: Питон (Python)

РТА:

Рабочий текст
алгоритма

ИТП:

Исходный текст подпрограмм

Alg40:

Zh5()

def A40(ccrt, hCycles):

hCycles.za40 = 0

# Переменная индикации окончания A40

hCycles.Zh(ccrt.techsys.head5)

hCycles.za40 = 1

# Индикация окончания процесса A40

alg A30():

Zh7( )

Fork(A40( ))

Zh4

Join_&(A40( ))

Zh7( )

def A30(ccrt, hCycles):

hCycles.za30 = 0

# Переменная индикации окончания A30

hCycles.Zh(ccrt.techsys.head7)

thread.start_new(expSub.A40, (ccrt, hCycles, ))

hCycles.Zh(ccrt.techsys.head4)

while not hCycles.za40:

time.sleep(0.1)

hCycles.Zh(ccrt.techsys.head7)

hCycles.za30 = 1

# Индикация окончания процесса A30

alg20:

Zh3()

Zh6()

def A20(ccrt, hCycles):

hCycles.za20 = 0

# Переменная индикации окончания A20

hCycles.Zh(ccrt.techsys.head3)

hCycles.Zh(ccrt.techsys.head6)

hCycles.za20 = 1

# Индикация окончания процесса A20

alg A10():

Zh6( )

Fork(A20( ))

Zh0

Join_&(A20( ))

def A10(ccrt, hCycles):

hCycles.za10 = 0

# Переменная индикации окончания A10

hCycles.Zh(ccrt.techsys.head6)

thread.start_new(expSub.A20, (ccrt, hCycles, ))

hCycles.Zh(ccrt.techsys.head0)

while not hCycles.za20:

time.sleep(0.1)

hCycles.za10 = 1

# Индикация окончания процесса A10

alg A581():

Fork(A30())

Fork(A10())

Zh1()

Join_&(A10(

))

Join_&(A30(

))

def eA581(ccrt, hCycles):

thread.start_new(expSub.A30, (ccrt, hCycles, ))

thread.start_new(expSub.A10, (ccrt, hCycles, ))

hCycles.Zh(ccrt.techsys.head1)

while not hCycles.za10:

while not hCycles.za30:

time.sleep(0.1)

Исходный текст программной реализации

ВИ: Вертикальное исполнение

Первичное решение

def A40(ccrt, hCycles): # подпрограмма дополнительного потока

hCycles.za40 = 0 # Введение индикации окончания A40

hCycles.Zh(ccrt.techsys.head5) # СГ5 - типовой цикл

hCycles.za40 = 1 # Окончание процесса A40

def A30(ccrt, hCycles): # подпрограмма дополнительного потока

hCycles.za30 = 0 # Введение индикации окончания A30

hCycles.Zh(ccrt.techsys.head7) # СГ7 - типовой цикл

thread.start_new(expSub.A40, (ccrt, hCycles, )) # поток A40

hCycles.Zh(ccrt.techsys.head4) # СГ4 - типовой цикл

while not hCycles.za40: # Контроль окончания A40

time.sleep(0.1) # задержка в цикле ожидания

hCycles.za30 = 1 # Окончание процесса A30

def A20(ccrt, hCycles): # подпрограмма дополнительного потока

hCycles.za20 = 0 # Введение индикации окончания A20

hCycles.Zh(ccrt.techsys.head3) # СГ3 - типовой цикл

hCycles.Zh(ccrt.techsys.head6) # СГ6 - типовой цикл

hCycles.za20 = 1 # Окончание процесса A20

def A10(ccrt, hCycles): # подпрограмма дополнительного потока

hCycles.za10 = 0 # Введение индикации окончания A10

hCycles.Zh(ccrt.techsys.head6) # СГ6 - типовой цикл

thread.start_new(expSub.A20, (ccrt, hCycles, )) # поток A20

hCycles.Zh(ccrt.techsys.head0) # СГ0 - типовой цикл

while not hCycles.za20: # Контроль окончания A20

time.sleep(0.1) # задержка в цикле ожидания

hCycles.za10 = 1 # Окончание процесса A10

def eA581(ccrt, hCycles): # alg A581() программа основного потока

thread.start_new(expSub.A30, (ccrt, hCycles, )) # поток A30

thread.start_new(expSub.A10, (ccrt, hCycles, )) # поток A10

hCycles.Zh(ccrt.techsys.head1) # СГ1 - типовой цикл

while not hCycles.za10: # Контроль окончания A10

while not hCycles.za30: # Контроль окончания A30

time.sleep(0.1) # задержка в цикле ожидания

Вернуться к описанию файла

Новости

Статистика

Расчетно-графическая работа №5 / РГР №5 (готово).doc

Скачать

1.1 Исходное описание алгоритма

СФА: Структурная формула алгоритма

ССА: Структурная схема алгоритма. Вариант 1. Линейный стиль

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

1.2 Специальная подготовка алгоритма

ССА: Структурная схема алгоритма. Вариант 2. Мозаичный стиль

Итоговая СФА: Структурная формула алгоритма:

Вербальные (словесные) тексты алгоритма

1.3 Многопоточная программная реализация алгоритма

Реализация компонент алгоритма

Исходный текст программной реализации

Скачать