ЛЕКЦИЯ 11 (19.05.09) Потактовое и событийное моделирование Блок-схема алгоритма потактового моделирования Событийное моделирование Сравнение методов. - презентация

1 ЛЕКЦИЯ 11 ( ) Потактовое и событийное моделирование Блок-схема алгоритма потактового моделирования Событийное моделирование Сравнение методов

2 Из выступления перед академиками Казуальное поведение оптимально-динамической системы в условиях полиантагонистического воздействия эффектированно возбуждённой интегрально-обобщённой среды с тремя степенями неопределённости описывается оказывается вполне стохастически, ибо квинтэссенция не есть субстанция, а есть концепция радикального эксцесса, локализованного дивергенцией ротора H и инкапсулированного в рамках гипераффигенного предиката.

3 Классификация методов моделирования Способы моделирования Моделирование без учёта задержек (синхронное) Моделирование с учётом задержек (асинхронное) Потактовое моделирование (Принцип дельта T) Событийное моделирование (Принцип дельта Z) Двоичное моделирование Троичное моделирование Многозначное моделирование Интерпретирующее моделирование Компилирующее моделирование Итак, в зависимости от рассмотренных факторов, принято выделять следующие методы (алгоритмы) моделирования статика динамика

4 Потактовое (сплошное, сквозное) моделирование Слово «потактовое» означает, что этот вид моделирования использует принцип t, при котором модельное время дискретезируется, то есть разбивается на интервалы одинаковой величины t. Они называются тактами. Слово «сплошное или сквозное» означает, что данный способ моделирования основан на обработке всех элементов схемы на всех временных тактах. Элементы всегда просматриваются в неизменном порядке. Это довольно примитивное решение значительно упрощает реализацию алгоритма моделирования. Альтернативой ему является событийный метод, при котором в каждом цикле работы моделятора отыскиваются и обрабатываются только активные элементы, то есть такие, у которых хотя бы на одном входе в текущий момент времени произошли переключения и, значит, они могут изменить своё состояние.

5 Возникновение итераций при потактовом моделировании Третья особенность заключается в том, что данному алгоритму присущи итерации, то есть многократные прогоны модели на одном и том же наборе данных (входных сигналов) A Y F1F2 DD1DD2DD3 R(DD1)=1R(DD1)=2R(DD1)=3 Ранг схемы = 3 Структурная (графическая) модель Функциональная модель ПлохаяХорошая Y = not F2; F2 = not F1; F1 = not A; F2 = not F1; Y = not F2; Неупорядоченный список Упорядоченный список Допустим, мы построили модель по варианту и выполнили первый прогон. Так как вычисления начинаются «с конца», то выход Y будет определён для старого состояния F2, а значение F2 – для старого F1. Таким образом, только выход F1 будет подсчитан верно. 12 1

6 Ранжирование комбинационных схем F1 = B and C; F2 = not D; F4 = F1 nand F2; F3 = A nand F1; F5 = F4 and E; Y = F3 or F5; & AND2 & NAND2 & AND2 DD1 DD2 & NAND2 DD3 DD4 1 OR2 A B C D E F1 F2 F3 F4 F5 Y DD5 1 INV Самый длинный путь в схеме Ранг 0Ранг 1Ранг 2 Ранг 3 Ранг 4 DD6 Упорядоченный список Обратите внимание, что к моменту решения очередного уравнения значения всех его аргументов уже определены. Так, вычисляя выход F4, моделятор уже имеет вновь вычисленные значения F1 и F2. Вот он Flow – поток распространения данных от входов к выходам. Итераций нет!

7 Генерация в схеме & 1 1 A Y F1F2 DD1DD2DD3 NAND2INV Исходное состояние A=0F1=1F2=0Y=1 РаботаA=1F1=0F2=1Y=0 F1=1F2=0Y=1 F1=0F2=1Y=0 F1=1F2=0Y=1Y=1 и т.д. Получился генератор (осциллятор) Случай, когда на некотором такте модельного времени итерации не сходятся, а их число превысило величину R+1, свидетельствует о появлении колебаний в схеме.

8 Структура данных при потактовом моделировании Имена сигналов Номера тактов T0T1T1T2T2T3T3Tmax D0 D1D1 A F1 F2 F3 Y F1 = INV(A); 1 INV Исходное состояние Текущий такт 0 1 Двумерный массив – наиболее удобная структура данных при потактовом моделировании Входы Выходы

9 Блок-схема алгоритма потактового моделирования Начало Конец Ввод исходной информацииНачальные установки, T:=0 Формирование входного набора, IT:=0 Прогон модели (Система булевских уравнений) A A Соседние итерации совпали? IT = IT + 1 IT < R + 1 Нет Да Сообщение «Генерация в схеме» Хранение T := T+1 T < Tmax Вывод В В Да Нет Да Счётчик модельного времени Счётчик итераций ВД, R, Tmax

10 Особенности потактового моделирования N 1 Модельное время движется по тактам (принцип t) T = T Обработке подлежат все элементы схемы на всех тактах 3Моделирование выполняется без учёта задержек (tз = 0) 4 В процессе моделирования возникают итерации – повторные прогоны модели на неизменном наборе данных 5 Используется ранжирование схемы, то есть сортировка элементов в порядке их срабатывания 6В качестве структуры данных используется двумерный массив 7 Используется функциональное или потоковое описание модели в виде систем логических уравнений. Модель – это программа, а не данные 8Предпочтение отдаётся компилирующему моделированию 9 За один цикл работы моделятора обрабатывается один такт модельного времени, соответствующий одному набору входных данных

11 Событийное моделирование Событием называется любое изменение значения сигнала и неважно, в каком месте схемы оно произошло: на входе, выходе или внутри схемы. При двузначном алфавите {0,1} возможны только два события: 0 1 и 1 0. Для многозначного алфавита типов переключений может быть гораздо больше, например: 0 Х, 1 Х, Х 0, Х 1, 0 Z, 1 Z, Z 0, Z 1, X Z, Z X и т.п. Способ, основанный на моделировании событий, называют событийным моделированием. Основная его идея заключается в том, чтобы проследить, каким образом изменения на входах схемы передаются на выходы. При этом элементы, на входах которых нет изменений, вообще не моделируются (их состояния остаются неизменными), а таких элементов в цифровых схемах по разным оценкам от 90 до 98%. Это означает, что, отслеживая только пути переключений в схеме и моделируя только активные элементы (а их 2…10% в схеме), можно существенно повысить эффективность моделирования (примерно в 10…50 раз).

12 Событийное моделирование Итак, первая особенность событийного моделирования заключается в том, что при прогоне модели схемы обрабатываются только 2…10% её элементов. Это так называемые активные элементы, у которых в текущий момент времени изменились входные сигналы. Вторая особенность заключается в механизме продвижения модельного времени. Оно движется не равномерно с ранее заданным шагом t, а скачками разной величины от текущего события до ближайшего будущего (принцип z). В этом случае говорят, что время движется, опираясь на события, которые должны быть отсортированы в хронологическом порядке. Элементы - приёмники Генератор события Элемент - предшественник ИсточникПриёмник Элемент - последователь

13 Разновидности событий Все события можно разделить на безусловные и возможные (предполагаемые, условные). 1 INV & AND2 1 & События нет Безусловное событиеУсловное событие Условие D C R T DFF Исходное состояние События нет 1 0 Событие есть Условное событие Условие Событие есть 0 Сброс R=1 более приоритетная команда

14 Разновидности событий События делятся также на отработанные, текущие и будущие. Графически событие E (от слова event) отображается точкой на оси модельного времени. E1E2 E3 E4 E5 E6 E7 0 t E1 tMtM t E2 t E3 tE4tE4 t M =t E4 Текущее событие Отработанные события Модельные часы всегда указывают на текущее событие NOW - сейчас Ближайшее будущее событие E8E8 E9E9 Кратные (одновременные) события t E5 t E6 t E7 = t E8 t E9 Будущие события Симулятор уже выполнил часть работы (обработал первые три события)

15 Разновидности событий Модельное время «перепрыгнуло» на событие E4, которое стало текущим. Очередной цикл работы моделятора связан теперь с обработкой реакции схемы на это событие. Будущие события – это те, которые ещё предстоит обрабатывать. Среди них выделим ближайшее будущее событие, то есть то событие, на которое моделятор собирается перевести модельные часы в следующем цикле работы (в примере E5). При моделировании схемы в текущий момент времени могут произойти новые события, которые добавляются в очередь будущих событий в хронологическом порядке. Если новое событие появится на интервале t E4 …t E5, то оно и станет ближайшим.

16 Очередь будущих событий Очередь будущих событий ОБС - это отсортированный в порядке возрастания времени список будущих событий. Иногда ОБС называют календарем событий. В общем случае каждое событие в ОБС задается тремя параметрами: именем, временем и новым значением события. ИмяВремя ns Новое значение R201 R400 C801 C1000 С1401 С1600 ОБС R С tMtM 20ns80ns 40ns100ns 140ns 160ns Изначально ОБС хранит только список событий на внешних входах. События расставлены в хронологическом порядке Формат события – запись. В вершине очереди находится событие (R 20ns 1), которое должно произойти раньше других – ближайшее будущее событие.

17 Массив состояний сигналов В отличие от потактового метода событийное моделирование использует не двумерный, а одномерный массив данных. Он называется массивом состояний сигналов МСС и хранит только текущие значения всех сигналов, действующих в моделируемой схеме. Для каждого сигнала (цепи) резервируется по одной ячейки в МСС. & & 11 D0 D1 A F1 F2 F3 Y Имя сигнала Текущее значение D00 A0 D10 F1X F2X F3X YX МСС ( t M = 0) Перед началом моделирования в МСС заносятся исходные значения входных сигналов для tm = 0, по которым модулятор пытается выяснить исходное состояние схемы. 0 50ns t З =10ns t З =15ns DD1 DD3

18 Список отработанных событий В процессе работы моделятор накапливает все события, которые произошли в схеме. По ним легко восстановить историю, «картину» работы схемы, а, значит, их удобно использовать при выводе результатов моделирования. ОБС Ближайшее будущее событие Обработка СОС По имени события в табличном описании схемы находятся элементы - приёмники Время события передаётся в модельные часы (событие становится текущим) Новое значение события передаётся в МСС. Планируются (предсказываются) новые будущие события – транзакты. ИмяВремя Новое значение Обработка заключается в следующем: 50nsA1 В хвост

19 Планирование новых событий В процессе моделирования содержимое ОБС будет изменяться, так как переключения на входах могут порождать в будущем другие (новые) события – переключения на выходах элементов схемы. Кроме того, из ОБС будут удаляться текущие события и запоминаться в списке отработанных событий (СОС). Предположим, ближайшее будущее событие, записанное в ОБС – это переключение входа A из 0 в 1 в момент времени 50ns (см. слайд 17). По табличному описанию схемы мультиплексора находим элементы – приёмники сигнала A. Их два – DD1 и DD3 (см. слайд 17 или 21). Моделятор вызовет одну за другой подпрограммы моделей этих элементов (DD1 – инвертора и DD3 – элемент 2И) и определит, изменятся ли в будущем их выходы. Понятно, что модели элементов прогоняются на текущем наборе входных сигналов, причем вход A уже переключился на новое значение (A=1).

20 Планирование новых событий Имя сигнала Текущее значение D00 A1 D10 F1X F2X F3X YX МСС ( t M = 50ns) Текущее модельное время Будущие события на выходах F1 и F3 (если они произойдут) будут удалены от текущего времени на величину задержки этих элементов, то есть на время 10ns (инвертор) и 12ns (2И) соответственно. Добавляя эти задержки к текущему времени, моделятор спланирует два новых события: ИмяВремя ns Новое значение F F Старое значение X X Спланированные события будут вставлены в ОБС в соответствии со временем их свершения: выше будут события с меньшим или равным временем, ниже – с большим временем.

21 Табличное представление цифровой схемы & & 11 D0 D1 A F1 F2 F3 Y мультиплексор DD1 DD2 DD3 DD4 INV AND2 OR2 Графическое описание Текстовое описание Потоковая форма F1

22 Табличное представление цифровой схемы Номер логического элемента Имя логического элемента Тип логического элемента Задержка ns Указатель адреса в таблице цепей ВходыВыходы 1DD1INV1034 2DD2AND2151, 45 3DD3AND2152, 36 4DD4OR2205, 67 Таблица элементов Таблица цепей Указатель адреса в таблице элементов Имя цепи Текущее значение (МСС) Номер цепи 2D011 3D102 1, 3A13 2F104 4F205 4F306 nullY07

23 Блок-схема алгоритма событийного моделирования Начало Включение в ОБС событий на входах A В Да Инициализация схемы ОБС пуста? t m < t max ? Выбор из ОБС ближайшего события Нет Да Нет Конец Ввод исходной информации Вывод результатов Табличное описание схемы ВД на входах Исходное состояние t max

24 Блок-схема алгоритма событийного моделирования A t m =t ближ Нет Да Есть приёмник? Да Нет Занесение в МСС нового значенияПоиск приёмников текущего событияМоделирование элемента-приёмника Выход переключился? Планирование нового события B Модельные часы Здесь движется модельное время ИмяВремя Новое значение A 50ns 1 Имя сигнала A передаётся в таблицу описания схемы для поиска элементов-приёмников t c = t m + t з

25 Особенности событийного моделирования N 1 Модельное время движется, опираясь на события скачками произвольной длины. Модельные часы t m = t ближ 2Обработке подлежат только активные элементы схемы (2…10% схемы) 3Моделирование выполняется с учётом задержек на элементах (tз 0) 4 В процессе моделирования возникают итерации (повторные прогоны модели на неизменном наборе данных) не возникают 5 Ранжирование схемы, то есть сортировка элементов в порядке их срабатывания, не требуется 6В качестве структуры данных используется одномерный массив МСС 7 Используется структурное описание модели в табличном представлении Модель – это данные, а не программа 8Часто событийное моделирование выполняется в режиме интерпретации 9 За один цикл работы моделятора обрабатывается только одно событие (или несколько одновременных)