Скачать презентацию
Идет загрузка презентации. Пожалуйста, подождите
Презентация была опубликована 3 года назад пользователемДмитрий Зайцев
1 Методы анализа моделей. Композиция кланов Дмитрий Анатольевич Зайцев Для научного лектория Ришельевского Лицея, Одесса
2 Моделирование сетями Петри и Слепцова Верификация протоколов сетями Петри Методы анализа моделей. Композиция кланов Методы анализа моделей. Композиция кланов Анализ вычислительных решеток и облаков бесконечными сетями Петри Анализ вычислительных решеток и облаков бесконечными сетями Петри Оценка производительности систем раскрашенными сетями Петри Оценка производительности систем раскрашенными сетями Петри Организация вычислений на сетях Слепцова
3 Области применения Верификация сетевых протоколов – основа кибербезопасности Корректность параллельных программ Организация автоматизированного производства Организация бизнес-процессов Программируемые контроллеры Управление движением транспорта 3
4 Свойства моделей Ограниченность – конечное число состояний Безопасность – маркировка не превышает единицы Консервативность – сохраняет взвешенную сумму фишек Достижимость заданной маркировки Живость – из любого состояния достижима маркировка в которой можно запустить указанный переход 4
5 Методы анализа сетей Петри Графы (деревья) достижимых и покрывающих маркировок Фундаментальное уравнение сети и линейные инварианты – решение линейных систем в целых неотрицательных числах Сифоны и ловушки Редукция – преобразования уменьшающие размер и сохраняющие свойства Декомпозиция – разделение на части 5
6 Модель протокола SimAck 6
7 Поведение сети 7
8 Пространство состояний модели REACHABILITY ANALYSIS bounded 4 marking(s), 4 transition(s) MARKINGS: 0 : p1 p3 1 : p2 p3 p5 2 : p2 p4 3 : p2 p3 p6 REACHABILITY GRAPH: 0 -> t1/1 1 -> t3/2 2 -> t4/3 3 -> t2/ s LIVENESS ANALYSIS live reversible 0 dead marking(s), 4 live marking(s) 0 dead transition(s), 4 live transition(s)
9 ГДМ: маркировки в виде векторов
10 Протокол двусторонней передачи сообщений с подтверждениями (DupAck) 10
11 Граф достижимых маркировок DupAck 11
12 Фундаментальное уравнение и линейные инварианты фундаментальное уравнение инварианты позиций инварианты переходов Решить в целых неотрицательных числах!
13 Пример систем для вычисления инвариантов Инварианты позиций Инварианты переходов
14 Базисные инварианты P-SEMI-FLOWS GENERATING SET invariant p1 p2 (1) p1 p4 p5 p6 (1) p3 p4 (1) 0.000s T-SEMI-FLOWS GENERATING SET consistent t1 t2 t3 t s ANALYSIS COMPLETED
15 Композиция кланов для ускорения решения линейных систем 15 Отношение близости уравнений – два уравнения близки если содержат некоторую переменную с коэффициентами одинаковых знаков Отношение клана – транзитивное замыкание отношения близости Отношение клана – отношение эквивалентности Клан – элемент разбиения системы с помощью отношения клана
16 Декомпозиция матрицы системы на кланы
17 The Innovative Computing Laboratory Джек Донгарра – легенда суперкомпьютерных технологий Пакет LAPACK (LINPACK) – наиболее цитируемый источник компьютерных наук; решение (больших) линейных систем; тестирование производительности компьютеров Пакеты для современных параллельных архитектур с использованием OpenMP, MPI, CUDA
18 Самые мощные компьютеры в мире Top 500
19 Клан – транзитивное замыкание отношения близости два уравнения близки если содержат некоторую переменную с коэффициентами одинаковых знаков
20 Пример декомпозиции на кланы
21 Системы и ориентированные двудольные графы Уравнение – переход (квадрат) Переменная – позиция (круг) Положительный знак – входящая дуга позиции Отрицательный знак – исходящая дуга позиции
22 Граф декомпозиции на кланы x 1, x 2, x 3, x 4, x 5, x 11, x 12, x 13, x 15, x 18 x 1, x 10, x 17 x 6, x 8, x 16 x 7, x 9, x 19
23 Коллапс графа декомпозиции I.II.
24 ParAd: Разделяй и властвуй
25 Протоколы передачи данных MPI
26 Модель протокола
27 Ускорения вычислений
28 Программное обеспечение Deborah – декомпозиция на кланы, 2005 Adriana – решение однородных систем в процессе композиции (a) одновременной или (b) последовательной, 2006 Реализованы как встраиваемые модули для Tina ParAd (Параллельная Adriana),
29 Проблема Развитие прикладных областей: коммуникационные системы суперкомпьютеров – многомерные торы, сети на чипах, численное решение систем уравнений в частных производных, ускорители частиц, моделирование термоядерной реакции Анализ свойств моделей заданной структуры и произвольного размера в многомерных пространствах 29
30 Литература Dmitry Zaitsev, Stanimire Tomov, Jack Dongarra. Solving Linear Diophantine Systems on Parallel Architectures, IEEE Transactions on Parallel and Distributed Systems, 30(5), 2019, Solving Linear Diophantine Systems on Parallel Architectures, IEEE Transactions on Parallel and Distributed Systems, 30(5), 2019, Zaitsev D.A. Sequential composition of linear systems' clans, Information Sciences, Vol. 363, 2016, Sequential composition of linear systems' clans, Information Sciences, Vol. 363, 2016, Зайцев Д.А. Композиционный анализ сетей Петри, Кибернетика и системный анализ , 1. - С Композиционный анализ сетей Петри
Еще похожие презентации в нашем архиве:
© 2025 MyShared Inc.
All rights reserved.
Скачать презентацию
Идет загрузка презентации. Пожалуйста, подождите
Презентация была опубликована 3 года назад пользователемДмитрий Зайцев
1 Методы анализа моделей. Композиция кланов Дмитрий Анатольевич Зайцев Для научного лектория Ришельевского Лицея, Одесса
2 Моделирование сетями Петри и Слепцова Верификация протоколов сетями Петри Методы анализа моделей. Композиция кланов Методы анализа моделей. Композиция кланов Анализ вычислительных решеток и облаков бесконечными сетями Петри Анализ вычислительных решеток и облаков бесконечными сетями Петри Оценка производительности систем раскрашенными сетями Петри Оценка производительности систем раскрашенными сетями Петри Организация вычислений на сетях Слепцова
3 Области применения Верификация сетевых протоколов – основа кибербезопасности Корректность параллельных программ Организация автоматизированного производства Организация бизнес-процессов Программируемые контроллеры Управление движением транспорта 3
4 Свойства моделей Ограниченность – конечное число состояний Безопасность – маркировка не превышает единицы Консервативность – сохраняет взвешенную сумму фишек Достижимость заданной маркировки Живость – из любого состояния достижима маркировка в которой можно запустить указанный переход 4
5 Методы анализа сетей Петри Графы (деревья) достижимых и покрывающих маркировок Фундаментальное уравнение сети и линейные инварианты – решение линейных систем в целых неотрицательных числах Сифоны и ловушки Редукция – преобразования уменьшающие размер и сохраняющие свойства Декомпозиция – разделение на части 5
6 Модель протокола SimAck 6
7 Поведение сети 7
8 Пространство состояний модели REACHABILITY ANALYSIS bounded 4 marking(s), 4 transition(s) MARKINGS: 0 : p1 p3 1 : p2 p3 p5 2 : p2 p4 3 : p2 p3 p6 REACHABILITY GRAPH: 0 -> t1/1 1 -> t3/2 2 -> t4/3 3 -> t2/ s LIVENESS ANALYSIS live reversible 0 dead marking(s), 4 live marking(s) 0 dead transition(s), 4 live transition(s)
9 ГДМ: маркировки в виде векторов
10 Протокол двусторонней передачи сообщений с подтверждениями (DupAck) 10
11 Граф достижимых маркировок DupAck 11
12 Фундаментальное уравнение и линейные инварианты фундаментальное уравнение инварианты позиций инварианты переходов Решить в целых неотрицательных числах!
13 Пример систем для вычисления инвариантов Инварианты позиций Инварианты переходов
14 Базисные инварианты P-SEMI-FLOWS GENERATING SET invariant p1 p2 (1) p1 p4 p5 p6 (1) p3 p4 (1) 0.000s T-SEMI-FLOWS GENERATING SET consistent t1 t2 t3 t s ANALYSIS COMPLETED
15 Композиция кланов для ускорения решения линейных систем 15 Отношение близости уравнений – два уравнения близки если содержат некоторую переменную с коэффициентами одинаковых знаков Отношение клана – транзитивное замыкание отношения близости Отношение клана – отношение эквивалентности Клан – элемент разбиения системы с помощью отношения клана
16 Декомпозиция матрицы системы на кланы
17 The Innovative Computing Laboratory Джек Донгарра – легенда суперкомпьютерных технологий Пакет LAPACK (LINPACK) – наиболее цитируемый источник компьютерных наук; решение (больших) линейных систем; тестирование производительности компьютеров Пакеты для современных параллельных архитектур с использованием OpenMP, MPI, CUDA
18 Самые мощные компьютеры в мире Top 500
19 Клан – транзитивное замыкание отношения близости два уравнения близки если содержат некоторую переменную с коэффициентами одинаковых знаков
20 Пример декомпозиции на кланы
21 Системы и ориентированные двудольные графы Уравнение – переход (квадрат) Переменная – позиция (круг) Положительный знак – входящая дуга позиции Отрицательный знак – исходящая дуга позиции
22 Граф декомпозиции на кланы x 1, x 2, x 3, x 4, x 5, x 11, x 12, x 13, x 15, x 18 x 1, x 10, x 17 x 6, x 8, x 16 x 7, x 9, x 19
23 Коллапс графа декомпозиции I.II.
24 ParAd: Разделяй и властвуй
25 Протоколы передачи данных MPI
26 Модель протокола
27 Ускорения вычислений
28 Программное обеспечение Deborah – декомпозиция на кланы, 2005 Adriana – решение однородных систем в процессе композиции (a) одновременной или (b) последовательной, 2006 Реализованы как встраиваемые модули для Tina ParAd (Параллельная Adriana),
29 Проблема Развитие прикладных областей: коммуникационные системы суперкомпьютеров – многомерные торы, сети на чипах, численное решение систем уравнений в частных производных, ускорители частиц, моделирование термоядерной реакции Анализ свойств моделей заданной структуры и произвольного размера в многомерных пространствах 29
30 Литература Dmitry Zaitsev, Stanimire Tomov, Jack Dongarra. Solving Linear Diophantine Systems on Parallel Architectures, IEEE Transactions on Parallel and Distributed Systems, 30(5), 2019, Solving Linear Diophantine Systems on Parallel Architectures, IEEE Transactions on Parallel and Distributed Systems, 30(5), 2019, Zaitsev D.A. Sequential composition of linear systems' clans, Information Sciences, Vol. 363, 2016, Sequential composition of linear systems' clans, Information Sciences, Vol. 363, 2016, Зайцев Д.А. Композиционный анализ сетей Петри, Кибернетика и системный анализ , 1. - С Композиционный анализ сетей Петри
Еще похожие презентации в нашем архиве:
© 2025 MyShared Inc.
All rights reserved.