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

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

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

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

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

МАТЕМАТИЧЕСКАЯ ЛОГИКА

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

Общая тема:

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

Часть 1

НАЧАЛЬНАЯ ПОДГОТОВКА

Простейшие алгоритмы:

Структурные схемы и формулы

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

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

3053.4371.0000-ПЗ

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

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

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

230102: АСОИ: Автоматизированные системы обработки информации и управление

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

Учебная группа: Асои -231

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

студент _____________ Баймуратов А.С.

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

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

преподаватель _____________ Житников А.П.

2006

1.     Параллельная конъюнкция (#&). Многопоточная реализация

Порядок записи комбинаций заданных параметров

а) Код индивидуального задания:

номер зачетной книжки: XXХabc = 055547

последние три цифры номера: abc = 547

б) Таблица параметров задания:

Номера команд	i = c	j = b	k = a
	7	4	5
Команды	Zi = Z7	Zj = Z4	Zk = Z5
	Z7	Z4	Z5
Длительности команд	mi = 4*10 = 40	mj = 7*10 = 70	mk = 5*10 = 50
Силовая головка	СГ7	СГ4	СГ5
Длина инструмента силовой головки	Li = L7 = 40	Lj = L4 = 70	Lk = L5 = 50

в) Установка заданных параметров длины инструмента:

Li = L7 = 40 Lj = L4 = 70 Lk = L5 = 50

Пустой алгоритм:

A001 = ( )

Единичный (однокомандный) алгоритм:

А101 = (Z7)

2) Двухкомандые алгоритмы // Первичные невырожденные алгоритмы

A211 = (Z7 — Z4) — последовательный алгоритм;

А222 = (Z7 & Z4) = (Z7 #& Z4) — параллельная конъюнкция команд;

3) Трехкомандный алгоритм:

А323 = (Z7 & Z4 & Z5) = (Z7 #& Z4 #& Z5) — параллельная конъюнкция команд.

Алгоритм 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 ) )

)

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

Рабочий файл:

expSub.py: Учебные (экспериментальные) подпрограммы.

Подпрограмма реализации алгоритма A001:

def eA001(ccrt, hCycles): // alg A001( ):

pass // пустой оператор

// равносилен повторителю и простой связи: R = ->

Алгоритм A101: Единичный алгоритм

Описание алгоритма

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

Алгоритм этапа обработки (основного перехода тех. операции):

A101 = (Z7) = Z7

Алгоритм операционного цикла

A = (Zz — A101 — Zr) = (Zz — (Z7) — Zr) = (Zz —Z7 — Zr)

ССА: Структурная схема алгоритма

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

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

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

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

A001 = (Z7) = Z7

A001 = Z7

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

alg A001(): Zh7()

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

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

A001 A001= A001= A001= alg A001():

= ( ( | Z7 Zh7()

( Z7 | Z7

Z7 ) )

)

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

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

def eA101(ccrt, hCycles): // alg A211():

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

Алгоритм A211: Последовательность двух команд

Описание алгоритма

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

Алгоритм этапа обработки (основного перехода тех. операции):

A211 = (Z7 — Z4) = Z7 — Z4

Алгоритм операционного цикла

A = (Zz — A211 — Zr) = (Zz — (Z7 —Z4) — Zr) = (Zz — Z7 —Z4 — Zr)

ССА: Структурная схема алгоритма

ДИА: Диаграмма исполнения алгоритма: mz7 = 40, mz4 = 70

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

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

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

A211 = (Z7—Z4) = Z7—Z4

A001 = Z7—Z4

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

alg A001( ): Zh7( ); Zh4( )

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

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

A211 A211= A211= A211= A211= alg A211( ):

= ( ( | Z7 — | Z7 Zh7( )

( Z7 — | Z7 — | Z4 | Z4 Zh4( )

Z7 Z4 | Z4

— ) )

Z4

)

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

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

def eA211(ccrt, hCycles): # alg A211( ):

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

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

Алгоритм A222: Параллельная конъюнкция двух команд

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

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

Алгоритм этапа обработки (основного перехода тех. операции):

A222 = (Z7 & Z4) = (Z7 #& Z4) = #(Z7, Z4)& = # Z7, Z4 &

Алгоритм операционного цикла

A = (Zz — A222 — Zr) = (Zz — (Z7 & Z4) — Zr)

ССА: Структурная схема алгоритма

ДИА: Диаграмма исполнения алгоритма: mz7 = 40, mz4 = 70

Многопоточные представления

ССА: Структурная схема алгоритма

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

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

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

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

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

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

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

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

A222 = (Z7 & Z4) = (Z7 #& Z4) = #(Z7, Z4)& = # Z7, Z4 & =

= # Z7 Z4 & = # Z7 Z4 & = # Z7 Z4 & =

= FZ4 Z7 JZ4 = FZ4—Z7—J&Z4

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

alg A222 ( ): Fork(Zh4( )); Zh7( ); Join_&(Zh4( ))

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

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

A222 = alg A222( ):

| FZ4 Fork(Zh4( ))

| Z7 Zh7( )

| J&Z4 Join_&(Zh4( ))

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

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

def eA222(ccrt, hCycles): // alg A222():

thread.start_new(hCycles.Zh, (ccrt.techsys.head4, )) // Fork(Zh4())

hCycles.Zh(ccrt.techsys.head7) // Zh7()

while not ccrt.techsys.head4.yzh: // Join(Zh4()): ожидание (head4.yzh = 1)

pass

Алгоритм A323: Параллельная конъюнкции трех команд

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

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

Алгоритм этапа обработки (основного перехода тех. операции):

A323 = (Z7 & Z4 & Z5) = (Z7 #& Z4 #& Z5) =

= #(Z7, Z4, Z5)& = # Z7, Z4, Z5 &

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

A = (Zz — A323 — Zr) = (Zz — (Z7 & Z4 & Z5) — Zr)

ССА: Структурная схема алгоритма

Вариант 1 Вариант 2

ДИА: Диаграмма исполнения алгоритма: mz7 = 40, mz4 = 70, mz5 = 50

Многопоточные представления

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

A323 = (Z7 & Z4 & Z5) = ((Z7 & Z4) & Z5) = ((Z7 #& Z4) #& Z5)

= #(#(Z7, Z4)&, Z5)& = # # Z7,Z4 &, Z5&

ССА: Структурная схема алгоритма / Вариант 3

ССА: Структурная схема алгоритма / Вариант 4

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

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

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

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

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

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

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

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

A323 = ((Z7 & Z4) & Z5) = ((Z7 #& Z4) #& Z5) =

= #(#(Z7, Z4)&, Z5)& = # # Z7, Z4 &, Z5 & =

= # # Z7 Z4 & Z5 & = # # Z7 Z4 & Z5 & = # # Z7 Z4 & Z5 & =

= # FZ4 Z7 J&Z4 Z5 & = # FZ4 Z7 JZ4 Z5 & = # FZ4 Z7 JZ4 Z5 & =

= FZ5 FZ4 Z7 J&Z4 J&Z5 = FZ5 — FZ4 — Z7 — J&Z4 — J&Z5

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

alg A323( ): Fork(Zh4( )); Fork(Zh4( )); Zh7( ); Join_&(Zh4( )) ; Join_&(Zh5( ))

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

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

A222 = alg A222( ):

| FZ5 Fork(Zh5( ))

| FZ4 Fork(Zh4( ))

| Z7 Zh7( )

| J&Z4 Join_&(Zh4( ))

| J&Z5 Join_&(Zh5( ))

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

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

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

def eA323(ccrt, hCycles): // alg A222():

thread.start_new(hCycles.Zh, (ccrt.techsys.head5, )) // Fork(Zh5())

thread.start_new(hCycles.Zh, (ccrt.techsys.head4, )) // Fork(Zh4())

hCycles.Zh(ccrt.techsys.head7) // Zh7()

while not ccrt.techsys.head4.yzh: // Join(Zh4()): ожидание (head4.yzh = 1)

pass // пустой оператор тела цикла

while not ccrt.techsys.head5.yzh: // Join(Zh5()): ожидание (head5.yzh = 1)

pass // пустой оператор тела цикла

Модификация:

введение оператора задержки в циклы ожидания завершения параллельной конъюнкции — для разгрузки процессора.

def eA323(ccrt, hCycles): // alg A222():

thread.start_new(hCycles.Zh, (ccrt.techsys.head5, )) // Fork(Zh5())

thread.start_new(hCycles.Zh, (ccrt.techsys.head4, )) // Fork(Zh4())

hCycles.Zh(ccrt.techsys.head7) // Zh7()

while not ccrt.techsys.head4.yzh: // Join(Zh4(): ожидание (head4.yzh = 1)

time.sleep(0.1) // задержка для разгрузки процессора

while not ccrt.techsys.head5.yzh: // Join(Zh5(): ожидание (head5.yzh = 1)

time.sleep(0.1) // задержка для разгрузки процессора