ЛЕКЦИЯ 12 (04.05.10) Методы логического моделирования Классификация методов моделирования Ранжирование схем Потактовое моделирование. - презентация

1 ЛЕКЦИЯ 12 ( ) Методы логического моделирования Классификация методов моделирования Ранжирование схем Потактовое моделирование

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

3 Методы логического моделирования Они весьма многочисленны и определяются следующими основными факторами: Различают следующие типы моделей цифровых элементов: Ранее мы познакомились с двумя основными механизмами продвижения модельного времени – принципами t и z. Принцип t продвигает время скачками равной длины t, которые называются тактами, или более мелкими «шажками» - квантами. Принцип z тоже продвигает время скачками, но теперь они могут быть разной длины, которая определяется временным интервалом между соседними событиями (переключениями). tз = 0 такт типом моделей цифровых элементов;1 способом продвижения модельного времени; 2 стратегией обработки элементов схемы; 3 принципами реализации моделирующей программы. 4 без учёта задержек булевские модели M21 троичные модели M32 многозначные модели MM3 модели с учётом временных задержек MT4

4 Методы логического моделирования Стратегия обработки элементов моделируемой схемы предполагает один из двух возможных способов: Второй способ гораздо сложнее в реализации, но он исключает «пустую» работу. Отыскивая и моделируя только активные элементы (а их в каждом цикле работы моделятора не более 10% от общего объёма схемы), удаётся многократно повысить эффективность моделирования. По способу реализации моделирующей программы различают компилирующее и интерпретирующее моделирование. Подробнее об их особенностях мы поговорим позднее. моделировать один за другим все элементы схемы;1 моделировать не всю схему, а только отдельные, так называемые активные элементы, то есть такие, на входах которых обнаружено хотя бы одно переключение. 2

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

6 Синхронное и асинхронное моделирование Подавляющее большинство цифровых устройств (до 80%) используют синхронный принцип работы. Принцип «Переждать неприятности» Его основная идея заключается в том чтобы, дождавшись окончания переходных процессов в комбинационной схеме, зафиксировать установившиеся сигналы на её выходах (не искажённые более гонками) в регистровой части схемы (по сигналу С2). C1 C2 D0 D1 A F1 F2 F3 Ya С1 С2 RG & & 11 мультиплексор статика Двухфазная синхронизация

7 Синхронное моделирование Если разработчик правильно выбрал частоту синхронизации (по максимально возможной задержке самого длинного пути в комбинационной схеме), то возникает законный вопрос, надо ли моделировать переходные процессы? Другими словами, задача моделирования сводится к проверке правильности логического функционирования. А для этого, как мы уже знаем, вполне пригодны самые простые типы моделей – булевские модели элементов, не учитывающие временные задержки. Рассмотренный метод моделирования называется синхронным двоичным моделированием. Ответ очевиден – в подобной ситуации временные задержки на элементах и возможные гонки, порождённые этими задержками и их разбросом, никакого интереса не представляют.

8 Асинхронное моделирование При асинхронном моделировании интерес представляют не только установившиеся значения сигналов в момент подачи синхроимпульса, но и сам переходный процесс, протекающий в цифровой схеме. Такую задачу нельзя решить, не моделируя задержки распространения сигналов внутри элементов. Синхронное моделирование Асинхронное моделирование Синхронные схемы Асинхронные схемы Зачем асинхронными методами моделировать синхронную схему? Другими словами, исследуя схему, надо определить не только состояния выходов элементов (статика), но и моменты времени, когда менялись эти состояния (динамика). Асинхронное моделирование даёт более реалистичную картину того, что происходит в действительности, и потому находит всё большее применение в современных системах моделирования.

9 Асинхронное моделирование Асинхронное моделирование позволяет проконтролировать соблюдение всех временных соотношений (ограничений) в проектируемой схеме, таких как время предустановки и удержания, минимальная длительность импульсов и т.п. К сожалению (и для многих это может оказаться откровением), эксперимент не является критерием правильности решения для схем, в которых возможны гонки. Риски сбоя (иголки) действительно трудно увидеть. Во-первых, они очень короткие и не всякий осциллограф их обнаружит. Во-вторых, надо знать, где их искать. Дело в том, что их печальные последствия (риски сбоя) могут проявлять себя эпизодически: сегодня всё работает, а завтра вдруг без всяких видимых причин начинаются сбои. И, наконец, «иголки» могут изменять свою ширину, вплоть до полного исчезновения.

10 Компилирующее и интерпретирующее моделирование Аналогия с компилирующими и интерпретирующими системами программирования. Компилирующее моделирование использует какой-либо специализированный проблемно (или процедурно) - ориентированный язык программирования. Затем исходный текст модели компилируется в объектный код. Обычно модель оформляется как подпрограмма, которая позднее подключается компоновщиком к моделирующей программе, выступающей в качестве головной. Прикомпоновав модель к программе моделирования, вы получите загрузочный модуль, который можно запустить на исполнение. В нашем случае его обычно называют языком моделирования или описания аппаратуры (например, VHDL). На этом языке «программируется» модель проектируемого устройства, например мультиплексора на два входа.

11 Компилирующее моделирование Вся неприятность компилирующего моделирования заключается в том, что внесение изменений в модель потребует повторной её компиляции и компоновки с головной программой (моделятором). Недостатки компилирующего моделирования Другой недостаток компилирующего моделирования заключается в нерациональном использовании оперативной памяти инструментальной ЭВМ, на которой выполняется работа. Другими словами, каждому элементу схемы соответствует свой «отрезок» программы, реализующий его функцию. Это весьма существенный недостаток, так как проектирование обычно выполняется методом проб и ошибок, носит итерационный характер, а внесение изменений, преследующих цель повысить качество проекта, составляет его суть. В нашем примере мультиплексор содержит два одинаковых элемента, выполняющих функцию AND2. Для каждого из них компилятор вставит свой «отрезок» кода. А если в схеме будет несколько сотен однотипных элементов, то компилятор породит столько же копий объектного кода.

12 Компилирующее моделирование Главное достоинство компилирующего моделирования заключается в том, что откомпилированная и отлаженная модель имеет высокое быстродействие. Для этого есть несколько причин. Во-первых, рабочая программа (моделятор + модель) обычно целиком загружается в оперативную память машины. Другая «бросающаяся в глаза» особенность этого вида моделирования – способ описания моделируемой схемы. Она представляется системой логических уравнений, то есть имеет место не структурное, а функциональное (или потоковое) описание схемы. Наиболее заметная особенность компилирующего моделирования заключается в том, что вся программа сначала транслируется, а уж потом исполняется. Обратите внимание, речь идёт о моделировании уравнений, а не элементов схемы, которые их реализуют. Другими словами, модель – это программа, а не данные. Во-вторых, все данные у неё «под рукой», обычно в массиве состояний сигналов, к которому моделятор обращается по именам (D0, D1, A, F1, F2, F3, Y), а не тратит время на поиск данных по адресам, задаваемым указателями.

13 Интерпретирующее моделирование Интерпретирующее моделирование выглядит более привлекательно с точки зрения итерационного проектирования. Главная идея интерпретирующего моделирования заключается в том, чтобы рассматривать модель не как программу, а как данные. Эти данные представляют собой структурное описание моделируемой схемы. Оно, правда, выполняется более медленно, чем только что рассмотренный вид моделирования, но этот недостаток с лихвой компенсируется удобством внесения изменений в схему. Изменив схему, вам не придётся её повторно компилировать и компоновать с моделирующей программой. Моделятор, который теперь интерпретирует вашу схему, при новом запуске просто не заметит, что она чем-то отличается от своей старой версии. Функции, выполняемые элементами схемы, задаются неявно, через их типы (INV, AND2, OR2). Чтобы моделятор мог реализовать их, они оформляются в виде подпрограмм (процедур или функций), а их объектный код «встраивается» в моделятор раз и навсегда.

14 Интерпретирующее моделирование Структура данных, описывающих схему, имеет во внешнем представлении вид схемы или таблицы, а во внутреннем – связный список. На прошлой лекции мы уже обсуждали этот способ описания схемы. Теперь при переходе от одной схемы к другой (или к модификации первой) меняются только списки (таблицы), а сама моделирующая программа остаётся неизменной. Можно сказать, что она стала универсальной. Обычно она хранится в виде загрузочного модуля и всегда готова к выполнению. Ещё одно достоинство интерпретирующего моделирования заключается в том, что оперативная память используется весьма экономно. Ведь все однотипные элементы, сколько бы их не было в схеме, обрабатываются одной и той же подпрограммой. Обращение к ней происходит всякий раз, когда интерпретатор «натыкается» на элемент с данной логической функцией. Конечно, за все приобретения надо платить. Платой за универсальность и простоту внесения изменений в схему является потеря быстродействия. Много процессорного времени уходит на операции поиска адресов данных по таблицам (спискам). Другой недостаток заключается в том, что библиотека моделей элементов, прикомпонованная к моделятору, является закрытой (пример EWB). У вас нет возможности добавлять в неё новые модели, так как исходный текст моделятора обычно не доступен простому пользователю.

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

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

17 Возникновение итераций при потактовом моделировании Придётся «прогнать» плохую модель ещё несколько раз (в нашем примере ещё два раза), прежде чем выход Y станет соответствовать действительности. Двоичная модель логической схемы Исходно е состояни е Такт Т0 (A = 0) Такт Т1 (A = 1) Номер итерации 1234 Y = not F F2 = not F F1 = not A Переключения Проверочная итерация 1 11 A Y F1F2 DD1DD2DD3 Соседние итерации совпали 0 -> 11 -> 0 плохая

18 Двоичная модель логической схемы F2 = not F1 F1 = not A Y = not F2 плохая Исходное состояние Такт Т0 (A = 0) Такт Т1 (A = 1) Номер итерации Y F1F2 DD1 DD2DD3

19 Проверочная итерация Переключения Возникновение итераций при потактовом моделировании Плохая модель 1 11 A Y F1F2 DD1DD2DD3 0101T0 1010T1T Исходное состояние Конечный результат T1.1 T1.2T1.2 T1.3 T1.4T F2 = not F1 F1 = not A Y = not F Соседние итерации совпали Номер итерации

20 Возникновение итераций при потактовом моделировании Интуиция подсказывает, что от итераций можно избавиться, если переписать уравнения модели в порядке срабатывания элементов в схеме, то есть слева – направо от входов – к выходам (см. хорошую функциональную модель). Теперь первым будет вычислено значение F1 = not A = 0. Определяя состояние выхода F2, мы уже будем располагать только что вычисленным значением F1 (итерации Зейделя): F2 = not F1 = 1. Наконец, выход Y тоже определяется новым значением F2: Y = not F2 = 0. Как видим, итераций нет. Из сказанного становится ясно, что прежде чем строить модель схемы, последнюю желательно проранжировать, то есть определить порядок срабатывания элементов, их причинно-следственные связи. Дадим определение этому понятию. Ранжирование – это сортировка элементов в порядке их срабатывания в логической схеме.

21 Ранжирование комбинационных схем Процедура ранжирования заключается в том, что каждому элементу ставится в соответствие целое число, называемое его рангом. Ранг несёт информацию о том, как далеко находится элемент от внешних входов. Ранг 0Ранг 1 Ранг 0Ранг 1 DigStim AF1 AY Ранг 1 получают элементы, на входах которых действуют только внешние сигналы. Рангом 2 помечаются элементы, входы которых подключены к внешним генераторам (входным контактам) и/или к выходам элементов первого ранга. В противном случае нулевой ранг приписывается входным контактам (цепям). Если на схеме показаны генераторы входных сигналов (например PSpice-проекты), то им присваивается нулевой ранг. Внешний вход Аналогичным образом определяются элементы более высоких рангов. Ранг 2 1 DD1 Y

22 Ранжирование комбинационных схем Ранг 0 Ранг 1 A F1 Ранг 2 Y B Ранг 0 & Смысл этой формулы прост. Чтобы вычислить ранг конкретного элемента R(E), надо, прежде всего, знать ранги всех элементов, подключённых к его входам: R(Ei). Ранг всей схемы определяется наибольшим числом элементов, через которые проходит сигнал от внешних входов до внешних выходов в течение одного такта. В нашем примере таких элементов два, следовательно, и ранг схемы равен двум. Ранг всей схемы R = 2 В общем случае ранг любого элемента определяется по следующей формуле Затем надо найти среди них самый высокий ранг и, увеличив его на единицу, получить искомый ранг элемента E, а значит и ранги его выходных сигналов.

23 Ранжирование комбинационных схем R(E) = 1 + max(R(E1), R(E2), …, R(Ek)), i = 1,k i Смысл этой формулы прост. Чтобы вычислить ранг конкретного элемента R(E), надо, прежде всего, знать ранги всех элементов, подключённых к его входам: R(Ei). Надо знать ранги всех элементов, подключённых к его входам: R(E1)=4 R(Ek)=7 R(E)=8 R(E2)= Пример Элемент E Затем надо найти среди них самый высокий ранг и, увеличив его на единицу, получить искомый ранг элемента E.

24 Ранжирование комбинационных схем Теперь мы в состоянии прояснить физический смысл понятия ранга схемы: это самый длинный путь в схеме. В схемотехнике ему соответствует другое название – логическая глубина схемы. Если говорить о ранге конкретного элемента, то он может быть определён по такому же правилу – это число элементов, последовательно включённых между выходом данного элемента и внешними входами схемы. Записав функции логических элементов в порядке возрастания их рангов, мы получим упорядоченный список – ранжированную модель схемы в виде системы булевских выражений. Взаимное расположение в списке элементов одного ранга может быть любым и не влияет ни на результат, ни на время моделирования. Понятно, что и здесь речь идёт о самой длинной цепочке элементов, включая (по определению) и сам элемент, для которого подсчитывается ранг.

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

26 Ранжирование комбинационных схем Ранг 0 Ранг 4 & AND2 DD1 DD2 & NAND2 DD3 1 OR2 A B C D E F1 F2 F3 & NAND2 DD4 F4 Y F5 & AND2 DD5 1 INV DD6 Это та же самая схема, что и на предыдущем слайде Это не обратная связь

27 Ранжирование схем с обратными связями Из-за наличия обратных связей ранг элемента DD1 не удаётся определить, так как неизвестен ранг элемента DD2, подключённого к его входу. & NAND2 & DD1 DD2 NS NR Q NQ & NAND2 DD1 NS Q & NAND2 DD2 NR NQ Ранг 1 Ранг 2 Ранг схемы = 2 Попытка сначала вычислить ранг элемента DD2 тоже оказывается неудачной, потому что теперь надо знать ранг DD1. Получается замкнутый круг в прямом смысле этого слова. Ситуация оказывается «патовой», если не «разрубить» этот гордиев узел. Контур Оборванный входОбратная связь

28 Ранжирование схем с обратными связями Разомкнём условно обратную связь и «оторванному» входу опять же условно присвоим нулевой ранг. Другими словами такой вход временно (пока ранжируется схема) получает статус внешнего входа. Но аналогия между ними не полная. На внешние входы подаются сигналы, не зависящие от состояния схемы, тогда как на «оборванный» вход подаётся старое значение сигнала обратной связи. Выполнив итерацию, моделятор получит новое значение на выходной линии обратной связи и сравнит его со старым значением на «оборванном» входе. Если они совпадут, то оборванную связь можно «восстановить», не нарушив состояния схемы. Если они различны, то моделятор повторит итерацию, передав на «оборванный» вход только что вычисленное значение. Таким образом, обратные связи как будто разрываются на время выполнения итераций и автоматически восстанавливаются при завершении итерационного процесса, когда получен результат. На следующем такте всё повторяется вновь.

29 Ранжирование схем с обратными связями. Аналогия 10V 5V5V 10K A B 5K A B 10V 5V5V 10K 5K Что изменится, если узлы A и B соединить? В какую сторону потечёт ток по проводнику AB? Что будет на выходе вместо 5V? ?

30 Ранжирование схем с обратными связями & NAND2 DD1 NS Q & NAND2 DD2 NR NQ Проверочная итерация показывает, что сигналы на оборванном входе и выходе цепи обратной связи совпали Такт T=0 Исходное состояние: на входах пассивный набор NS=1, NR=1 Триггер хранит «1»: Q=1, NQ=0 Такт T=1 На вход триггера приходит сигнал сброса: NR=0 Ранг 1 Ранг 2 Первым считаем выход NQ=1 (ранг 1) затем выход Q=0 (ранг 2) Итераций нет (кроме проверочной)

31 Ранжирование схем с обратными связями & NAND2 DD1 NS Q & NAND2 DD2 NR NQ Проверочная итерация показывает, что сигналы на оборванном входе и выходе цепи обратной связи совпали Ранг 1 Ранг 2 Такт T=0 Исходное состояние: на входах пассивный набор NS=1, NR=1 Теперь триггер хранит «0»: Q=0, NQ=1 Такт T=1 На вход триггера приходит сигнал установки: NS=0 Первым считаем выход NQ=1 (ранг 1) он сохраняет старое значение затем выход Q=1 (ранг 2) Делаем ещё одну итерацию теперь NQ=0 (ранг 1) выход Q=1 (ранг 2) остаётся тем же В схемах с ОС итерации неизбежны

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

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

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

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