Савкин Леонид Васильевич. Метод случайных булевых производных в оценке комбинационных схем - презентация

1 1 Секция «Математика» «Дискретная математика и теория игр» Метод случайных булевых производных в оценке комбинационных схем Савкин Леонид Васильевич

2 2 Цель работы - разработка и исследование эффективных методов оценки сложных комбинационных схем (КС) вычислительных архитектур на предмет наличия внутрисхемных логико-арифметических коллизий. Основные задачи: 1)Исследование методов оценивания комбинационных схем с использованием вероятностных способов тестирования ВС; 2)Разработка собственного метода оценки КС, основанного на синтезе вероятностных методов оценки КС и аппарате булевых производных (метод случайных булевых производных); 3)Практическая реализация разработанного метода для тестирования вычислительных архитектур однородного типа.

3 Переход от комбинационных схем к орграфам 3 Выделение подграфа G1 из фрагмента комбинационной схемы: Т.к. общее число подграфов графа G всегда может варьироваться!!! Орграф КС

4 Рандомные способы оценки комбинационных схем 4 Почему возникает необходимость использования рандомных методов оценки комбинационных схем? 1)Общая сложность КС, не позволяющая однозначно идентифицировать локальные логико-арифметические коллизии с помощью методов прямой оценки булевых функций. Что такое логико-арифметические коллизии? Под логико-арифметические коллизией (ЛАК) понимается любое локальное несоответствие данных, регистрируемых в контрольной точке КС, с ее заданными значениями (с таблицей истинности). При этом причина возникновения ЛАК не рассматривается. 2)Относительная простота в практической реализации по сравнению со сложными комбинированными методами анализа вычислительных архитектур. 3)Высокая степень универсальности рандомных способов оценки различных типов КС. 4)Возможность сочетания с аналитическими (количественными и качественными) методами. Как это выглядит в действительности (эпюры напряжений в контрольной точке КС):

5 Суть предлагаемого метода СБП 5 !!! Причем неважно какого рода будет изменение значения функции: с 0 на 1, или с 1 на 0 !!! Булеву производную функции по двоичной переменной : Шаг 1. Ставим во взаимно однозначное соответствие орграфубулеву функцию Пусть для орграфа Шаг 2. можно записать как В общем случае Выражение позволяет найти такие значения переменных(все кроме ), при которых изменение значения будет приводить к изменению значения функции Поэтому, выражение часто записывают в сокращенной форме вида: Шаг 3. Введем индикаторную функцию, позволяющую однозначно зафиксировать факт наличия логико-арифметической коллизии на орграфе а)Случай без регистрации ЛАК: : б)Случай с регистрации ЛАК: Шаг 4. Представим процедуру положительной оценки комбинационной схемы (выражение ) в виде следующего формального выражения: Здесь – параметр рандомизации; - выборка из генеральной совокупности.

6 Параметр рандомизации H 6 Параметр рандомизации представляет собой оператор, правило или алгоритм, на основе которого задается случайная выборка орграфов из их генеральной совокупности, соответствующей полной (исходной) КС. Генератор выборки (вариант, использовавшийся в данной работе) 1 2 Берем отрезок длиной Разбиваем его на равных частей 3 Сгибаем его в замкнутый «бассейн», задаем начальные условия для биллиарда и считываем номера орграфов для первой выборки на основе касаний биллиарда о стенки бассейна или Исх. положение

7 7 Параметр рандомизации H (продолжение) Небольшое пояснение В рамках различных вероятностных моделей выборок орграфов длины отрезков m могут варьироваться случайным образом. Ну а сам способ генерации выборки в целом, как Вы понимаете, уже относится к совершенно другой области исследования, а именно к хаотическим одиночным биллиардам В рамках различных вероятностных моделей выборок орграфов длины отрезков m могут варьироваться случайным образом. Ну а сам способ генерации выборки в целом, как Вы понимаете, уже относится к совершенно другой области исследования, а именно к хаотическим одиночным биллиардам Генеральная совокупность орграфов КС и принцип присвоения порядковых номеров элементам ее выборок Строго периодическая Не периодическая

8 Минимизация общего числа выборок орграфов 8 Об использовании метода минимизации набора контролируемых параметров (метод И.М. Синдеева) p n p n Оптимизация любого рандомного способа оценки КС заключается в сведении к минимуму общего числа выборок фрагментов КС, т.е. орграфов: Рис. 1. Максимум итераций тестирования КС Рис. 2. Минимум итераций тестирования КС К примеру, две выборки орграфов, содержащие одинаковое число элементов (n=3), могут обеспечивать различную вероятность обнаружения ЛАК в исходной КС!

9 Анализ областей применимости метода СБП 9 2. Макросистемный 1. Микросистемный Два подхода - условный уровень системы (мета графы) РВП

10 Однородная ВС на базе микроконтроллеров ATtiny13 10

11 Анализ достоинств и недостатков предлагаемого метода 11 Положительная сторона: Отрицательная сторона: 1. Возможность регистрации коллизий как на входах дерева КС, так и во внутренних каналах КС. 2. Качественная многоуровневая оценка КС 3. Метод очень удобен для верификации топологии ОВС и моделей ИНС с логическими функциями активации и синаптическими связями. 1. Резкое возрастание числа контрольных точек КС. 2. Сложность практической реализации схем встроенного контроля КС.

12 Выводы 12 Перспективы дальнейшей работы 1)Разработан метод оценки комбинационных схем, заключающийся в вероятностной (рандомной) оценке орграфов фрагментов КС на предмет наличия в них логико-арифметических коллизий; 2)В отличии от распространенных рандомных тестов, использующих прямую оценку булевых функций, предложенный метод производит оценку орграфов КС с помощью производных булевых функций; 3)Достоинство метода – многоуровневая оценка сложных КС, а недостаток – существенная сложность при его практической реализации. 1)Разработан метод оценки комбинационных схем, заключающийся в вероятностной (рандомной) оценке орграфов фрагментов КС на предмет наличия в них логико-арифметических коллизий; 2)В отличии от распространенных рандомных тестов, использующих прямую оценку булевых функций, предложенный метод производит оценку орграфов КС с помощью производных булевых функций; 3)Достоинство метода – многоуровневая оценка сложных КС, а недостаток – существенная сложность при его практической реализации. 1)Приложение разработанного метода к системам с динамической реконфигурацией комбинационных схем; 2)Разработка и исследование новых эффективных методов оценки сложных комбинационных схем. 1)Приложение разработанного метода к системам с динамической реконфигурацией комбинационных схем; 2)Разработка и исследование новых эффективных методов оценки сложных комбинационных схем.

13 Спасибо за внимание! 13