Презентация к ЛР2

1.

МТУСИ
Дизайн И. Гайдель 2007
Интеллектуальные системы
Лекция 6

2.

Дизайн И. Гайдель 2007
Пример выполнения задания
= (0,0).
Пусть дано следующее описание вычислительной системы.
Имеется многопроцессорная вычислительная система (ВС), состоящая из
двух параллельно включенных процессорных элементов ПЭ1 и ПЭ2. Ввод и
вывод данных в процессорную систему осуществляет канал ввода-вывода
(КВВ), состоящий из двух подканалов ПКВ1 и ПКВ2. Ввод данных
осуществляется при одновременном занятии подканалов ПКВ1 и ПКВ2. При
этом сообщения поступают на обработку сразу в оба процессорных элемента.
Прием вычислительной системой нового сообщения (новых данных) на
обработку возможно только тогда, когда процессорные элементы завершили
ввод данных и приступили к их обработке. Обработанные сообщения
выводятся из системы при использовании только подканала ПКВ2.

3.

Дизайн И. Гайдель 2007
Пример выполнения задания
= (0,0).
Особенности структуры ВС
1)
ВС
состоит
из
двух
параллельно
включенных
процессорных
элемента ПЭ1 и ПЭ2;
2)
КВВ состоит из двух подканалов ПКВ1 и ПКВ2, причем: а) ввод
данных осуществляется при одновременном занятии подканалов ПКВ1 и
ПКВ2; б) вывод данных из системы осуществляется использованием только
подканала ПКВ2;
3)
сообщение поступает на обработку сразу в оба процессорных
элемента (параллельная обработка данных);
4)
ввод нового сообщения на обработку возможно только тогда, когда
процессорные
сообщения.
элементы
приступили
к
обработке
введенного
ранее

4.

Дизайн И. Гайдель 2007
Пример выполнения задания
= (0,0).
Построение СП-модели ВС
Структурная схема заданной ВС
представлена на рис.1. Работу ПЭ разобьем
на три последовательных этапа: ввод
данных в ПЭ, обработка данных и вывод
данных из ПЭ. СП-модели работы ПЭ
представлены на рис.2. При этом введена
следующая интерпретация вершин:
t11 – начало ввода данных в ПЭ1,
Рис.1
t12 – окончание ввода данных в ПЭ2 и
начало обработки данных в ПЭ1,
t13 – окончание обработки данных в
ПЭ1,
t14 – вывод обработанных данных из
ПЭ1.
Рис.2
Аналогично
интерпретируются
переходы, моделирующие работу ПЭ2.

5.

Дизайн И. Гайдель 2007
Пример выполнения задания
= (0,0).
Построение СП-модели ВС
Структурная схема заданной ВС представлена на
рис.1. Работу ПЭ разобьем на три последовательных
этапа: ввод данных в ПЭ, обработка данных и вывод
данных из ПЭ. СП-модели работы ПЭ представлены на
рис.2. При этом введена следующая интерпретация
переходов ПЭ1:
Рис.1
Рис.2
t11 – начало ввода данных в ПЭ1,
t12 – окончание ввода данных в ПЭ2 и начало
обработки данных в ПЭ1,
t13 – окончание обработки данных в ПЭ1,
t14 – вывод обработанных данных из ПЭ1.
Аналогично
интерпретируются
переходы,
моделирующие работу ПЭ2.
Интерпретация позиций ПЭ1:
p11 – данные присутствуют для ввода в ПЭ1,
p12 – данные введены и готовы для обработки в
ПЭ1,
р13 – идет обработка данных в ПЭ1,
р14 – данные обработаны и готовы к выводу из
ПЭ1,
Аналогично интерпретируются позиции ПЭ2.

6.

Дизайн И. Гайдель 2007
Пример выполнения задания
= (0,0).

7.

Дизайн И. Гайдель 2007
Пример выполнения задания
= (0,0).
В исходных условиях для построения модели
задано, что ввод новых данных на обработку
возможен только тогда, когда закончен ввод
данных в процессорные элементы и они готовы
приступить к обработке введенных данных. СПмодель,
моделирующая
данную
ситуацию,
представлена на рис.4. Интерпретация введенных
вершин следующая:
t5 – формирование условия для ввода в ВС
очередных данных,
p01 -в ПЭ1 завершен ввод данных,
p02 - в ПЭ2 завершен ввод данных.
Рис.4.
Рис.5.
СП-модель, имитирующая работу подканалов ПКВ1
и ПКВ2 представлена на рис.5. При этом дана
следующая интерпретация введенных вершин:
t4
–
завершение
вывода
данных
из
многопроцессорной системы,
p3 – данные выводятся из многопроцессорной
системы,
p5 – условие занятости ПКВ1,
p6 – условие занятости ПКВ2.
Комбинация вершин p4 и t4 введена с целью
устранения избыточных меток (ловушка меток).

8.

Дизайн И. Гайдель 2007
Пример выполнения задания
= (0,0).
Для исследования данной СП-модели
произведем ее укрупнение путем ввода
иерархических переходов (сокращение
размерности). Предлагаемые структурные
преобразования представлены на рис.6.
Результирующая СП-модель представлена
на рис.7.
Рис.6.
Рис.7.

9.

Дизайн И. Гайдель 2007
Пример выполнения задания
= (0,0).
Алгебраическое
описание
иерархической СП-модели.
построенной
N: ((t1;t11;Q1) +
(t1;t21;Q2));t3;t4+(*(1>t4))+(t11;t5;(1>t1)) +
(h(t5;t4);(1>(g(t1;t3))) + (t5;(1>t1))
Q1: t12;t13;t14
Q2: t21;t22;t23 #
Рис.6.
Рис.7.

10.

Дизайн И. Гайдель 2007
Пример выполнения задания
= (0,0).
Исследуем построенную СПмодель с помощью дерева
достижимых разметок (ДДР).
Фрагмент ДДР представлен на
рис.8.
Рис.8.

11.

Дизайн И. Гайдель 2007
Пример выполнения задания
= (0,0).
Рис. 9. Состояние СП-модели при срабатывании перехода t1:
а) ДДР, б) разметка СП-модели

12.

Дизайн И. Гайдель 2007
Пример выполнения задания
= (0,0).
Рис. 10. Состояние СП-модели при срабатывании переходов t1, t11:
а) ДДР, б) разметка СП-модели

13.

Дизайн И. Гайдель 2007
Пример выполнения задания
= (0,0).
Рис. 11. Состояние СП-модели при срабатывании переходов t1, t11, t21:
а) ДДР, б) разметка СП-модели

14.

Дизайн И. Гайдель 2007
Пример выполнения задания
= (0,0).
Рис. 12. Состояние СП-модели при срабатывании переходов t1, t11, t21,t5:
а) ДДР, б) разметка СП-модели

15.

Дизайн И. Гайдель 2007
Пример выполнения задания
= (0,0).
Рис. 13. Состояние СП-модели при срабатывании переходов t1, t11, t21,t5, Q1:
а) ДДР, б) разметка СП-модели

16.

Дизайн И. Гайдель 2007
Пример выполнения задания
= (0,0).
Рис. 14. Состояние СП-модели при
срабатывании переходов t1, t11, t21,t5, Q1,t3,
t4,Q2,t3,t4:
а) ДДР, б) разметка СП-модели
Видно, что данная последовательность переходов приводит к достижению начальной
разметки µ0 исследуемой СП-модели.

17.

Дизайн И. Гайдель 2007
Пример выполнения задания
= (0,0).
Рис. 15. Состояние СП-модели при срабатывании переходов t1, t11, t21,t5,t1:
а) ДДР, б) разметка СП-модели

18.

Дизайн И. Гайдель 2007
Пример выполнения задания
= (0,0).
Рис. 16. Состояние СП-модели при срабатывании переходов t1, t11, t21,t5,t1,t11,t21:
а) ДДР, б) разметка СП-модели

19.

Дизайн И. Гайдель 2007
Пример выполнения задания
= (0,0).
Анализ
ДДР
показывает,
что
при
срабатывании
последовательности
переходов (t1, t11, t21, t5, t1, t11, t21, t1…) в
позициях p12 и p21 может накапливаться
неограниченное количество меток. Это
свидетельствует о том, что построенная СПмодель имеет недостатки, физическая
интерпретация которых говорит о том, что
на входе к ПЭ могут накапливаться
сообщения. Чтобы их не потерять и
обработать в порядке очереди необходимо
формировать буфер для хранения данных.
Причем размер буфера не известен, так как
число сообщений (меток) может быть
неограниченно.
С
целью
устранения
данного недостатка модифицируем СПмодель.

20.

Дизайн И. Гайдель 2007
Пример выполнения задания
= (0,0).
Модифицируемая СП-модель представлена
на рис.17. При этом вводится следующая
интерпретация введенных позиций:
p15 - обработка данных в ПЭ1 завершена,
они выведены из ПЭ1 и ПЭ1 готов к вводу
новых данных,
p25 - обработка данных в ПЭ2 завершена,
они выведены из ПЭ2 и ПЭ2 готов к вводу
новых данных.
Другими словами вводится некоторый
диспетчер, управляющий процессом ввода
данных в ПЭ. Если построить ДДР для
измененной
СП-модели,
то
можно
убедиться, что в нем отсутствуют разметки
с неограниченным числом меток.
Рис. 17. Иерархическая СП-модель, моделирующая диспетчеризацию ввода данных в ПЭ.

21.

Дизайн И. Гайдель 2007
Пример выполнения задания
= (0,0).
Для того, чтобы показать что полная СПмодель
(модель
с
раскрытыми
иерархическими
переходами)
хорошо
сформирована (не имеет тупиков и
неограниченных разметок), необходимо
показать
хорошую
сформированность
фрагментов СП-модели, которые замещают
ИП (рис.2). Анализ данных СП показывает
их
хорошую
сформированность.
Следовательно полная сеть Петри )(рис.18),
представленная путем раскрытия ИП, также
должна быть хорошо сформированной.
Рис. 18. СП-модель, моделирующая заданную многопроцессорную систему.

22.

Дизайн И. Гайдель 2007
Пример выполнения задания
= (0,0).
С учетом изменений внесенных в СП-модель
меняется
и
структура
ВС,
которая
представлена на рис.1. Модифицированная
структура ВС, в которой введены обратные
связи от ПЭ к управлению вводом в
многопроцессорную систему, представлена ни
рис.19.
Рич.19. Модифицированная структура ВС

23.

Дизайн И. Гайдель 2007
Пример выполнения задания
= (0,0).
Вывод. СП-модели представляют эффективный инструмент для анализа
сложных структур. Кроме этого, СП могут эффективно использоваться и для
анализа программного обеспечения, сетевых протоколов, бизнес-процессов.

24.

Дизайн И. Гайдель 2007
Спасибо за внимание!