Расчетно-графическая работа №4 / РГР №4(готово).doc
Министерство образования Российской Федерации
Уфимский государственный авиационный технический университет
Факультет ИРТ: Информатика и робототехника
Кафедра ПСИ: Проектирование систем информатики
Учебная дисциплина:
МЛТА: МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ
РГР: Расчетно-графическая работа
Общая тема:
ПАРАЛЛЕЛЬНЫЕ ЛОГИКО-АЛГОРИТМИЧЕСКИЕ СИСТЕМЫ
(алгоритмы и логика, аппаратная и программная реализация)
Часть 4
ПРОСТЫЕ ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ
МНОГОПОТОЧНАЯ ПРОГРАММНАЯ РЕАЛИЗАЦИЯ
Пояснительная записка
5033.4491.0000-ПЗ
Направление подготовки:
654600: ИВТ: Информатика и вычислительная техника
Специальность:
САПР: Системы автоматизированного проектирования
Курс обучения: 2
Учебная группа: САПР-230
Работу выполнил
студент _____________ Манаев Р. Н.
Зачетная книжка № 065491
Вариант задания: A230
Работу принял
должность _____________ Житников А. П.
2007
Формирование индивидуального задания.
а) Код индивидуального задания:
номер зачетной книжки: XXХabc = 065491
последние три цифры номера: abc = 491
б) Таблица параметров задания:
| Номера команд | i = c | j = b | k = a |
| 1 | 9 | 4 | |
| Команды | Zi = Zc | Zj = Zb | Zk = Za |
| Z1 | Z9 | Z4 | |
| Длительности команд | mi = с*10 = 10 | mj = b*10 = 90 | mk = a*10 = 40 |
// длительности представлены в некоторых условных единицах
Индивидуальный комплект алгоритмов
Комплекта простых алгоритмов определяется согласно личному коду:
abc = 491
1) Вырожденные алгоритмы:
Пустой алгоритм:
A001 = ( )
Единичный (однокомандный) алгоритм:
А101 = (Zi) = (Z1)
2) Двухкомандые алгоритмы // Первичные невырожденные алгоритмы
A211 = (Zi — Zj) = (Z1 — Z9) — последовательный алгоритм;
А222 = (Zi & Zj) = (Z1 & Z9) = (Z1 #& Z9) — параллельная конъюнкция команд;
3) Трехкомандный алгоритм:
А323 = (Zi & Zj & Zk) = (Z1 & Z9 & Z4) = (Z1 #& Z9 #& Z4) — параллельная конъюнкция команд.
ПАРАЛЛЕЛЬНАЯ КОНЪЮНКЦИЯ (#&).
МНОГОПОТОЧНАЯ ПРОГРАММНАЯ РЕАЛИЗАЦИЯ
ИСХОДНЫЕ ДАННЫЕ
Алгоритм A001: Пустой алгоритм - проходная интерпретация
Описание алгоритма
СФА: Структурная формула алгоритма
Алгоритм этапа обработки (основного перехода тех. операции):
A001 = ( ) = (—) = (—>) = (R) = —> = R
R: Репитер (повторитель) — оператор функции повторения;
равносилен простой линии связи
Алгоритм операционного цикла// включая загрузку и разгрузку
A = (Zz — A001 — Zr) = (Zz — R — Zr) = (Zz — — — Zr) = (Zz — Zr)
ССА: Структурная схема алгоритма
ВТА: Вербальный текст алгоритма / ПиПТ: Питон-подобный текст
ГИ: Горизонтальное исполнение
ШТА: Шаблон текста алгоритма
A001 = ( ) = (R) = R
A001 = R
РТА: Рабочий текст алгоритма
alg A001(): pass
ВТА: Вербальный текст алгоритма / ПиПТ: Питон-подобный текст
ВИ: Вертикальное исполнение:
A001 = (R) = R
ШТА: Шаблон текста алгоритма РТА: Рабочий текст алгоритма
A001 A001= A001= A001= alg A001():
= ( ( | R pass
( R | R
R ) )
)
Исходный текст программной реализации
Подпрограмма реализации алгоритма A001:
def eA001(ccrt, hCycles): // alg A001( ):
pass // пустой оператор
// равносилен повторителю и простой связи: R = ->
Алгоритм A101: Единичный алгоритм
Описание алгоритма
СФА: Структурная формула алгоритма
Алгоритм этапа обработки (основного перехода тех. операции):
A101 = (Z1) = Z1
Алгоритм операционного цикла // включая загрузку и разгрузку
A = (Zz — A101 — Zr) = (Zz — (Z1) — Zr) = (Zz —Z1 — Zr)
ССА: Структурная схема алгоритма
Вариант 1 Вариант 2
ДИА: Диаграмма исполнения алгоритма: mz9 = 10
ВТА: Вербальный текст алгоритма / ПиПТ: Питон-подобный текст
ГИ: Горизонтальное исполнение
ШТА: Шаблон текста алгоритма
A101 = (Z1) = Z1
A101 = Z7
РТА: Рабочий текст алгоритма
alg A101(): Zh1()
ВИ: Вертикальное исполнение
ШТА: Шаблон текста алгоритма РТА: Рабочий текст алгоритма
A101 A101= A101= A101= alg A101():
= ( ( | Z1 Zh1()
( Z1 | Z1
Z1 ) )
)
Исходный текст программной реализации
ВИ: Вертикальное исполнение
def eA101(ccrt, hCycles):
hCycles.Zh(ccrt.techsys.head1) // Zh1() - типовой цикл СГ9
Алгоритм A211: Последовательность двух команд
Описание алгоритма
СФА: Структурная формула алгоритма
Алгоритм этапа обработки (основного перехода тех. операции):
A211 = (Z1 — Z9) = Z1 — Z9
Алгоритм операционного цикла // включая загрузку и разгрузку
A = (Zz — A211 — Zr) = (Zz — (Z1 — Z9) — Zr) = (Zz — Z1 — Z9 — Zr)
ССА: Структурная схема алгоритма
Вариант 1 Вариант 2
ДИА: Диаграмма исполнения алгоритма: mz1 = 20, mz9 = 90
ВТА: Вербальный текст алгоритма / ПиПТ: Питон-подобный текст
ГИ: Горизонтальное исполнение
ШТА: Шаблон текста алгоритма
A211 = (Z1—Z9) = Z1—Z9
A211 = Z1—Z9
РТА: Рабочий текст алгоритма
alg A211( ): Zh1( ); Zh9( )
ВИ: Вертикальное исполнение
ШТА: Шаблон текста алгоритма РТА: Рабочий текст алгоритма
A211 A211= A211= A211= A211= alg A211( ):
= ( ( | Z1 — | Z1 Zh1( )
( Z1 — | Z1 — | Z9 | Z9 Zh9( )
Z1 Z9 | Z9
— ) )
Z9
)
Исходный текст программной реализации
ВИ: Вертикальное исполнение
def eA211(ccrt, hCycles): # alg A211( ):
hCycles.Zh(ccrt.techsys.head1) # Zh1( ) - типовой цикл СГ9
hCycles.Zh(ccrt.techsys.head9) # Zh9( ) - типовой цикл СГ1
Алгоритм A222: Параллельная конъюнкция двух команд
Исходное общее описание алгоритма
СФА: Структурная формула алгоритма
Алгоритм этапа обработки (основного перехода тех. операции):
A222 = (Z1 & Z9) = (Z1 #& Z9) = #( Z1, Z9)& = # Z1, Z9 &
Алгоритм операционного цикла // включая загрузку и разгрузку
A = (Zz — A222 — Zr) = (Zz — (Z1 & Z9) — Zr)
ССА: Структурная схема алгоритма
Вариант 1 Вариант 2
ДИА: Диаграмма исполнения алгоритма: mz1 = 10, mz9 = 90
Многопоточные представления
ССА: Структурная схема алгоритма / Вариант 3
|
|
Структурные операторы:
FZi = F(Zi) = Fork(Zi) — оператор узла вилки:
упаковка в поток и вызов команды Zi в потоке
JZi = J&Zi = J&(Zi) = Join_&(Zi) — оператор узла сборки:
ожидание (wait) завершения команды Zi
ВТА: Вербальный текст алгоритма / ПиПТ: Питон-подобный текст
ГИ: Горизонтальное исполнение
ШТА: Шаблон текста алгоритма
A222 = (Z1 & Z9 = (Z1#& Z9 = #(Z1 Z9)& = # Z1, Z9 & =
= # Z1 Z9 & = # Z1 Z9 & = # Z1 Z9 & =
= FZ9 Z1 JZ9 = FZ9—Z1—J&Z9
РТА: Рабочий текст алгоритма
alg A222 ( ): Fork(Zh9( )); Zh1( ); Join_&(Zh9( ))
ВИ: Вертикальное исполнение
ШТА: Шаблон текста алгоритма РТА: Рабочий текст алгоритма
A222 = alg A222( ):
| FZ9 Fork(Zh9( ))
| Z1 Zh1( )
| J&Z9 Join_&(Zh9( ))
Исходный текст программной реализации
ВИ: Вертикальное исполнение
Простой вариант:
def eA222(ccrt, hCycles): // alg A222():
thread.start_new(hCycles.Zh, (ccrt.techsys.head9, )) // Fork(Zh())
hCycles.Zh(ccrt.techsys.head1) // Zh1()
while not ccrt.techsys.head9.yzh: // Join(Zh3()): ожидание (head1.yzh = 9)
pass // пустой оператор тела цикла
// Выполняется активное ожидание события — процессор занят до конца цикл
Более рациональный вариант:
def eA222(ccrt, hCycles): // alg A222():
thread.start_new(hCycles.Zh, (ccrt.techsys.head9, )) // Fork(Zh9())
hCycles.Zh(ccrt.techsys.head1) // Zh1()
while not ccrt.techsys.head9.yzh: // Join(Zh9()): ожидание (head1.yzh = 9)
time.sleep(0.1) // Задержка повторения цикла:
// Пассивное (почти пассивное) ожидание события:
// процессор освобождается на время задержки
Алгоритм A323: Параллельная конъюнкции трех команд
Исходное общее описание алгоритма
СФА: Структурная формула алгоритма
Алгоритм этапа обработки (основного перехода тех. операции):
A323 = (Z1 & Z9 & Z4) = (Z1 #& Z9 #& Z4) =
= #(Z1, Z9, Z4)& = # Z1, Z9, Z4 &
Алгоритм операционного цикла // включая загрузку и разгрузку
A = (Zz — A323 — Zr) = (Zz — (Z1 & Z9 & Z4) — Zr)
ССА: Структурная схема алгоритма
Вариант 1 Вариант 2
ДИА:Диаграмма исполнения алгоритма: mz7 = 30, mz3 = 70, mz1 = 10
Многопоточные представления
СФА: Структурная формула алгоритма
A323 = (Z1 & Z9 & Z4) = ((Z1 & Z9) & Z4) = ((Z1 #& Z9) #& Z4)
= #(#(Z1, Z9)&, Z4)& = # # Z1,Z9 &, Z4&
ССА: Структурная схема алгоритма / Вариант 3
ССА: Структурная схема алгоритма / Вариант 4
|
Структурные операторы:
FZi = F(Zi) = Fork(Zi) — оператор узла вилки:
упаковка в поток и вызов команды Zi в потоке
J&Zi = J&(Zi) = Join_&(Zi) — оператор узла сборки:
ожидание (wait) завершения команды Zi
ВТА: Вербальный текст алгоритма / ПиПТ: Питон-подобный текст
ГИ: Горизонтальное исполнение
ШТА: Шаблон текста алгоритма
A323 = ((Z1 & Z9) & Z4) = ((Z1 #& Z9) #& Z4) =
= #(#(Z1, Z9)&, Z4)& = # # Z1, Z9 &, Z4 & =
= # # Z1 Z9 & Z4 & = # # Z1 Z9 & Z4 & = # # Z1 Z9 & Z4 & =
= # FZ9 Z1 J&Z9 Z4 & = # FZ9 Z1 JZ9 Z4 & = # FZ9 Z1 JZ9 Z7 & =
= FZ4 FZ9 Z1 J&Z9 J&Z4 = FZ4 — FZ9 — Z1 — J&Z9 — J&Z4
// Рабочий оператор Z3 связывают:
// слева вилка # — переходит в структурный оператор FZ3;
// справа сборка & — переходит в структурный оператор J&Z3.
// Рабочий оператор Z1 связывают:
// слева вилка # — переходит в структурный оператор FZ1;
// справа сборка & — переходит в структурный оператор J&Z1.
РТА: Рабочий текст алгоритма
alg A323( ): Fork(Zh4( )); Fork(Zh9( )); Zh1( ); Join_&(Zh9( )) ; Join_&(Zh4( ))
ВИ: Вертикальное исполнение
ШТА: Шаблон текста алгоритма РТА: Рабочий текст алгоритма
A323 = alg A323( ):
| FZ4 Fork(Zh4( ))
| FZ9 Fork(Zh9( ))
| Z1 Zh1( )
| J&Z9 Join_&(Zh9( ))
| J&Z4 Join_&(Zh4( ))
Исходный текст программной реализации
ВИ: Вертикальное исполнение
Первичное решение
def eA323(ccrt, hCycles): // alg A323():
thread.start_new(hCycles.Zh, (ccrt.techsys.head4, )) // Fork(Zh2())
thread.start_new(hCycles.Zh, (ccrt.techsys.head9, )) // Fork(Zh1())
hCycles.Zh(ccrt.techsys.head1) // Zh1()
while not ccrt.techsys.head9.yzh: // Join(Zh1()): ожидание (head9.yzh = 1)
pass // пустой оператор тела цикла
while not ccrt.techsys.head4.yzh: // Join(Zh2()): ожидание (head4.yzh = 1)
pass // пустой оператор тела цикла
Модификация:
введение оператора задержки в циклы ожидания завершения параллельной конъюнкции — для разгрузки процессора.
def eA323(ccrt, hCycles): // alg A323():
thread.start_new(hCycles.Zh, (ccrt.techsys.head4, )) // Fork(Zh1())
thread.start_new(hCycles.Zh, (ccrt.techsys.head9, )) // Fork(Zh3())
hCycles.Zh(ccrt.techsys.head7) // Zh7()
while not ccrt.techsys.head9.yzh: // Join(Zh1(): ожидание (head9.yzh = 1)
time.sleep(0.1) // задержка для разгрузки процессора
while not ccrt.techsys.head4.yzh: // Join(Zh2(): ожидание (head4.yzh = 1)
time.sleep(0.1) // задержка для разгрузки процессора