Ну не может тут быть никаких дыр в теории. Я ничего нового не делаю. Все же вставляют новые сигналы (хотя бы для того, чтобы CSC разрулить). Те же авторы Petrify подвели под это теоретическую базу. Я пользуюсь этим же механизмом добавления новых сигналов (тут надо различать цель добавления сигналов и собственно сам механизм добавления). Единственная новизна заключается в том, что после моего добавления логические функции всех сигналов вписываются в минимальный базис (2И-НЕ, 2ИЛИ-НЕ).
Если Вы хотите отменить мои схемы, то Вам придется отменить все: и Мараховского, и Стародубцева, и Кондратьева, и Яковлева. Ну честное слово, Вы раздуваете слона, где и мухи нет. По Вашему выходит, что и такое поведение невообразимая проблема.
a, b — входные, x, y — выходные. Логические функции: x=a, y=b.
Алексей, кажется начинаю понимать суть Ваших претензий.
Полумодулярность. Обязательна для внутренних и выходных сигналов. Для входных — вредна, поскольку безосновательно сужает класс рассматриваемых поведений.
SI. Независимость от скорости обеспечивается алгоритмом вычисления логических функций. Алгоритм исходит из предположений:
1. Задержка провода нулевая, т.е. каждое событие становится известно любой части схемы моментально.
2. Задержка внешней среды и любого элемента произвольна, т.е. произвольна задержка любого события.
Логические функции строятся так, чтобы обеспечить переключение сигнала при срабатывании всех событий-причин.
В итоге получается схема, обеспечивающая заданную последовательность переключений вне зависимости от задержек элементов схемы и задержек внешней среды.
Я понял почему Вы так пишите. Вы наверно коллега Плеханова Л.П. Тогда Вы наверно считаете, что событийный подход предполагает работу только с автономными схемами (поведениями). Отсюда и достраивание избыточного окружения для замыкания.
Я считаю, что лезть во внешнюю среду и вредно, и не зачем. Заменять причины для входных событий, значит менять исходное задание. Требование автономности, это уже перебор. Ну просто посчитайте логические функции для внутренних и выходных сигналов, а для входных не надо. Ими внешняя среда занимается. А что Вы будете делать, если поведение с выбором, по определению оно недетерминированное в отношении входных сигналов.
А схемку еще раз посмотрите, там SI в полный рост.
Настал мой черед каяться. Напрягся и вспомнил, что такое полумодулярность. «Если сигнал возбудился, он обязан переключиться». Архиважнейшее свойство. Конечно же все мои схемы вписываются в этот критерий. Просто за давностью лет и многолетним отсутствием практики, я подзабыл что это свойство именуется так. Я считал это требование совершенно естественным, и не акцентировал на нем внимание.
А теперь по Вашим вопросам. Надо разделять полумодулярность схемы и полумодулярность внешней среды. Полумодулярность схемы обеспечивает независимость от задержек элементов. А вот полумодулярность внешней среды — требование излишнее и даже вредное. Так Вы не сможете реализовать выбор. При выборе возбуждаются 2 сигнала (входных), а срабатывает один. Грубо говоря, не мое дело как среда обеспечивает нужный порядок входных сигналов. Мое дело сделать схему, правильно реагирующую на эти сигналы.
PS Делать схемы с недетерминированным поведением внутренних и выходных сигналов, ну это вообще ужос.
По всей видимости Вы не учли, что a, b — входные сигналы. Они определяют выбор, что переключать после b+: x+ (если a=1), или y+ (если a=0).
То что Петрифай для x и y пристегивает еще по одному бесполезному кубу (b&x и b&y), думаю получилось в силу того, что Петрифай делает структурный синтез, и каждый сигнал представляет в виде защелки.
Вообще то в произвольном базисе (НЕ-И-ИЛИ-НЕ) схемка получается простейшая (даже без дополнительной коррекции): x=AND(b,a) y=AND(b,!a). При описанной дисциплине входных сигналов все работает корректно при любых задержках элементов x и y.
Ох, Алексей, вижу Вы очень хотите меня уесть. И либо торопитесь, либо специально провоцируете. По левой верхней картинке. Представленная сеть Петри безопасная и живая. Ну нигде маркеры не накапливаются. Интерпретация тоже корректная. Вы сами можете засунуть этот граф в Petrify, или еще куда, и убедиться что косяков нет.
Вы очень напрасно не разобрались с полумодулярностью, поскольку используете общепринятые графы. Суть полумодулярности — отсутствие состязаний (гонок, races, glitches).
Отсутствие состязаний — характеристика итоговой схемы, но никак ни исходного поведения. Таким образом Вы забракуете добрую половину всех заданий.
ветка b+x+b-x-b+… может циклически переключаться независимо от всей другой схемы
Во-первых, наверно, b+ x+ b- x-. А во-вторых, в этом и есть суть выбора: альтернативные ветви могут чередоваться в любой последовательности. В том числе, будет работать только одна альтернативная ветвь, а вторая — простаивать. Все определяется входными сигналами.
(которая может вообще остановиться из-за задержки в одном из проводов)
Вот это вообще не понятно, что такое. Меня всегда напрягало как последователи Варшавского совмещают два понятия: исходное задание и синтезированная по нему схема. Я понимаю, что рефайнмент для них что-то непонятное. Но CSC нарушения вы как-то устраняете. А по Вашему выходит: в исходном задании есть нарушение CSC, значит схема неполумодулярная, в корзину ее. По поводу задержки в проводе. Про DI я не сказал ни слова. Что же касается квази-DI, для проводов должно соблюдаться следующее предположение о задержках. Задержка провода от элемента A до элемента B должна быть меньше чем суммарная задержка (задержка провода от элемента A до элемента C + задержка элемента C + задержка провода от элемента C до элемента B).
Это не только не DI схема, но даже и не SI!
Это не DI-схема, а квази-DI. Или же SI (классы совпадают). Соотношение задержек выше. Вместо того чтобы бросать голословные обвинения, основанные на Ваших неверных умозаключениях, просто найдите косяк в схеме, благо она небольшая, и предъявите его.
Вы используете общепринятые графы, но читаете их как то по своему
Графы я читаю также как все. Записываю их несколько в сокращенном виде. Но из этого сокращенного вида полноценный граф восстанавливается без труда.
Мой добрый совет: отредактируйте свой комментарий. Ахинея жуткая. Наставит Вам кто-нибудь минусов за такое.
И еще раз. Перед Вами есть все необходимое. Предъявите конкретное обвинение, с доказательствами, а не болтовню. Я понимаю, что Ваше отношение к этому: «Этого не может быть!». И все-таки постарайтесь разобраться сами. Ведь мои проверки в Petrify, или еще где, Вас не убедят. Вы будете говорить, что это подтасовка.
Желаю приятно провести вечер за разгадыванием этой загадки.
Алексей, действительно, Вы ухватили за самое чувствительное место. Но оно чувствительное не потому что слабое, а потому что крайне важное. Без решения этой проблемы вообще не было бы смысла писать статью.
Начну с начала. Мои нововведения с новыми типами событий это всего лишь более удобный способ описания некоторых типов поведений. И не более.
Вот простейший пример. a, b — входные, x, y — выходные. И слева, и справа — одно и тоже поведение. Только записано по разному. Именно только в этом и есть смысл нововведения.
Теперь по терминологии. Такие определения как полумодулярный, дистрибутивный я воспринимаю как внутренние термины приверженцев модели состояний. Для меня важное значение имеют термины SI, DI. Но если Вы подскажете, чем плохи неполумодулярные SI схемы, я намотаю на ус.
А теперь снова к рисунку. Важнейшая задача: построить для такого поведения SI схему в монотонном базисе (И-ИЛИ-НЕ). И хотя, несомненно, Варшавский был человеком крайне изобретательным, у меня очень большие сомнения, что в модели состояний можно логическим путем прийти к нужному результату. А вероятность случайного успеха крайне низка. В любом случае мне было бы интересно взглянуть на решение подобной задачки, если оно имеется.
В событийной модели задача решаема. Вот результат:
Поведение этой штуки такое:
В конце еще раз хочу сказать. Все эти "?", "/", "\" используются для описания исключительно входных сигналов. Причем эти сигналы являются не управляющими, а данными (например разряд второго регистра, как в статье).
Вернувшись к основной статье, можно сказать так. Представленная схема разряда регистра не отслеживает изменения состояний разряда буфера или разряда второго регистра. Лишь получив команду на операцию (копирования), а это значит что разряд буфера установился в определенном состоянии, схема выясняет в каком состоянии находится разряд буфера и в соответствии с этим выполняет свои действия.
Огорчительным во всем этом является факт, что подобного рода поведения невозможно реализовать DI схемой. Но квази-DI — всегда пожалуйста.
Признаю, наверно, надо было на этом акцентировать внимание. Событие "?" ни в коем случае не дополнительное логическое значение. Значений сигнала как было так и осталось два: 0 и 1. Событие "?" означает, что с этого момента и до наступления события "/" (или "\") сигнал может произвольным образом менять свое значение: с 0 на 1 и обратно произвольное количество раз. А может и оставаться все это время без изменений. Т.е. событие "?" означает, что с этого момента у нас нет информации о поведении этого сигнала, кроме того что он ведет себя как обычный асинхронный сигнал.
В STG есть некий аналог такой ситуации. Например он присутствует в бенчмарке rcv-setup. Просто, когда таких сигналов с неопределенным поведением больше одного, описывать все это с помощью STG крайне неудобно.
Я вообще категорический противник введения всевозможных надстроек типа парафазности, трехзначной логики. Есть только двузначная логика реализации, и причинно-следственные связи между событиями. И все.
PS. Я пока претендую только на половинку революции.
Вот честное слово, синхронной реализации я в глаза не видел. Может в такой конфигурации (2 операции) ее и нет, не знаю. Если бы кто подсказал, самому было бы интересно. А вообще целью статьи я считал просто в принципе сделать асинхронную схему.
Я в затруднении даже. Очевидно же, что асинхроника уже лет 20 пребывает в тупике. Причем очень глубоком. И завели ее туда все наши корифеи: от Маллера до Варшавского. А причина в том что они упорно изучали эту тему через модель состояний. Извлекать логические функции до сих пор учат по кубам. А сколько можно осилить переменных? Пять? С применением софта ситуация чуть лучше. Petrify осилит ну 25 сигналов. Дальше то тупик. С корректировкой поведения тоже похвастать нечем. CSC, dual-rail… В группе Варшавского был Стародубцев. Он предлагал изучать событийную модель. Но его идеи приняты не были.
На самом деле асинхроника проста. В ней нет ничего кроме причинно-следственных связей между событиями и двоичной логики, с помощью которой эти связи обеспечиваются. А лучший инструмент для исследования — простейшие логические функции: 2И-НЕ и 2ИЛИ-НЕ.
Так что ссылаться я могу только на Стародубцева. Но сейчас, кроме признания факта, что я являюсь его последователем, ничего интересного в его работах я порекомендовать не могу. А может я чего-то не знаю… Прошу прощения, если показался высокомерным. Это не так.
Да я вообще только картинки рассматриваю.
Если серьезно, не очень хорошо я английским владею, чтобы писать. А так у меня есть пара застарелых публикаций на английском, но в соавторстве.
Нет, это не старая перепечатка. Это ответ на цитату в начале статьи. А ей не больше месяца. Саму схему я закончил полторы недели назад. Оставшееся время вбивал результат в компьютер. Всех вещей, о которых Вы пишите, нет, т.к. все сделано с помощью бумаги, ручки и текст-корректора. Ни на симуляторе, ни на железе ничего не запускал, т.к. руки коротки. Но есть уверенность и небольшой давний опыт, что все это проскочит на «Ура!».
В хабе пишу, т.к. не знаю другого места куда умище приткнуть на русском языке. По англицки не пишу принципиально. А в этом хабе была статейка по асинхронике.
Да, это я как-то не учел. Думаю ни одна программа верификации, а тем более вычисления логических функций (т.к. все они работают через состояния), с таким количеством сигналов не справится. Я то работаю через события, для меня нет разницы 100 сигналов, 500 или 1000. Остается два пути. Либо научиться вычислять логические функции по графу событий, а этому нигде не учат. Либо моделирование. А оно не даст ответ на точное соответствие логических функций и итогового поведения. Хотя само моделирование пройдет без проблем, это по определению.
Если Вы хотите отменить мои схемы, то Вам придется отменить все: и Мараховского, и Стародубцева, и Кондратьева, и Яковлева. Ну честное слово, Вы раздуваете слона, где и мухи нет. По Вашему выходит, что и такое поведение невообразимая проблема.
a, b — входные, x, y — выходные. Логические функции: x=a, y=b.
Полумодулярность. Обязательна для внутренних и выходных сигналов. Для входных — вредна, поскольку безосновательно сужает класс рассматриваемых поведений.
SI. Независимость от скорости обеспечивается алгоритмом вычисления логических функций. Алгоритм исходит из предположений:
1. Задержка провода нулевая, т.е. каждое событие становится известно любой части схемы моментально.
2. Задержка внешней среды и любого элемента произвольна, т.е. произвольна задержка любого события.
Логические функции строятся так, чтобы обеспечить переключение сигнала при срабатывании всех событий-причин.
В итоге получается схема, обеспечивающая заданную последовательность переключений вне зависимости от задержек элементов схемы и задержек внешней среды.
Я считаю, что лезть во внешнюю среду и вредно, и не зачем. Заменять причины для входных событий, значит менять исходное задание. Требование автономности, это уже перебор. Ну просто посчитайте логические функции для внутренних и выходных сигналов, а для входных не надо. Ими внешняя среда занимается. А что Вы будете делать, если поведение с выбором, по определению оно недетерминированное в отношении входных сигналов.
А схемку еще раз посмотрите, там SI в полный рост.
А теперь по Вашим вопросам. Надо разделять полумодулярность схемы и полумодулярность внешней среды. Полумодулярность схемы обеспечивает независимость от задержек элементов. А вот полумодулярность внешней среды — требование излишнее и даже вредное. Так Вы не сможете реализовать выбор. При выборе возбуждаются 2 сигнала (входных), а срабатывает один. Грубо говоря, не мое дело как среда обеспечивает нужный порядок входных сигналов. Мое дело сделать схему, правильно реагирующую на эти сигналы.
PS Делать схемы с недетерминированным поведением внутренних и выходных сигналов, ну это вообще ужос.
То что Петрифай для x и y пристегивает еще по одному бесполезному кубу (b&x и b&y), думаю получилось в силу того, что Петрифай делает структурный синтез, и каждый сигнал представляет в виде защелки.
Вообще то в произвольном базисе (НЕ-И-ИЛИ-НЕ) схемка получается простейшая (даже без дополнительной коррекции): x=AND(b,a) y=AND(b,!a). При описанной дисциплине входных сигналов все работает корректно при любых задержках элементов x и y.
Отсутствие состязаний — характеристика итоговой схемы, но никак ни исходного поведения. Таким образом Вы забракуете добрую половину всех заданий.
Во-первых, наверно, b+ x+ b- x-. А во-вторых, в этом и есть суть выбора: альтернативные ветви могут чередоваться в любой последовательности. В том числе, будет работать только одна альтернативная ветвь, а вторая — простаивать. Все определяется входными сигналами.
Вот это вообще не понятно, что такое. Меня всегда напрягало как последователи Варшавского совмещают два понятия: исходное задание и синтезированная по нему схема. Я понимаю, что рефайнмент для них что-то непонятное. Но CSC нарушения вы как-то устраняете. А по Вашему выходит: в исходном задании есть нарушение CSC, значит схема неполумодулярная, в корзину ее. По поводу задержки в проводе. Про DI я не сказал ни слова. Что же касается квази-DI, для проводов должно соблюдаться следующее предположение о задержках. Задержка провода от элемента A до элемента B должна быть меньше чем суммарная задержка (задержка провода от элемента A до элемента C + задержка элемента C + задержка провода от элемента C до элемента B).
Это не DI-схема, а квази-DI. Или же SI (классы совпадают). Соотношение задержек выше. Вместо того чтобы бросать голословные обвинения, основанные на Ваших неверных умозаключениях, просто найдите косяк в схеме, благо она небольшая, и предъявите его.
Графы я читаю также как все. Записываю их несколько в сокращенном виде. Но из этого сокращенного вида полноценный граф восстанавливается без труда.
Мой добрый совет: отредактируйте свой комментарий. Ахинея жуткая. Наставит Вам кто-нибудь минусов за такое.
И еще раз. Перед Вами есть все необходимое. Предъявите конкретное обвинение, с доказательствами, а не болтовню. Я понимаю, что Ваше отношение к этому: «Этого не может быть!». И все-таки постарайтесь разобраться сами. Ведь мои проверки в Petrify, или еще где, Вас не убедят. Вы будете говорить, что это подтасовка.
Желаю приятно провести вечер за разгадыванием этой загадки.
Начну с начала. Мои нововведения с новыми типами событий это всего лишь более удобный способ описания некоторых типов поведений. И не более.
Вот простейший пример. a, b — входные, x, y — выходные. И слева, и справа — одно и тоже поведение. Только записано по разному. Именно только в этом и есть смысл нововведения.
Теперь по терминологии. Такие определения как полумодулярный, дистрибутивный я воспринимаю как внутренние термины приверженцев модели состояний. Для меня важное значение имеют термины SI, DI. Но если Вы подскажете, чем плохи неполумодулярные SI схемы, я намотаю на ус.
А теперь снова к рисунку. Важнейшая задача: построить для такого поведения SI схему в монотонном базисе (И-ИЛИ-НЕ). И хотя, несомненно, Варшавский был человеком крайне изобретательным, у меня очень большие сомнения, что в модели состояний можно логическим путем прийти к нужному результату. А вероятность случайного успеха крайне низка. В любом случае мне было бы интересно взглянуть на решение подобной задачки, если оно имеется.
В событийной модели задача решаема. Вот результат:
Поведение этой штуки такое:
В конце еще раз хочу сказать. Все эти "?", "/", "\" используются для описания исключительно входных сигналов. Причем эти сигналы являются не управляющими, а данными (например разряд второго регистра, как в статье).
Вернувшись к основной статье, можно сказать так. Представленная схема разряда регистра не отслеживает изменения состояний разряда буфера или разряда второго регистра. Лишь получив команду на операцию (копирования), а это значит что разряд буфера установился в определенном состоянии, схема выясняет в каком состоянии находится разряд буфера и в соответствии с этим выполняет свои действия.
Огорчительным во всем этом является факт, что подобного рода поведения невозможно реализовать DI схемой. Но квази-DI — всегда пожалуйста.
В STG есть некий аналог такой ситуации. Например он присутствует в бенчмарке rcv-setup. Просто, когда таких сигналов с неопределенным поведением больше одного, описывать все это с помощью STG крайне неудобно.
Я вообще категорический противник введения всевозможных надстроек типа парафазности, трехзначной логики. Есть только двузначная логика реализации, и причинно-следственные связи между событиями. И все.
PS. Я пока претендую только на половинку революции.
На самом деле асинхроника проста. В ней нет ничего кроме причинно-следственных связей между событиями и двоичной логики, с помощью которой эти связи обеспечиваются. А лучший инструмент для исследования — простейшие логические функции: 2И-НЕ и 2ИЛИ-НЕ.
Так что ссылаться я могу только на Стародубцева. Но сейчас, кроме признания факта, что я являюсь его последователем, ничего интересного в его работах я порекомендовать не могу. А может я чего-то не знаю… Прошу прощения, если показался высокомерным. Это не так.
Если серьезно, не очень хорошо я английским владею, чтобы писать. А так у меня есть пара застарелых публикаций на английском, но в соавторстве.
m1=NAND(q1,q0) b5=NOT(p1) i1=NAND(o1,j1) l1=NAND(i1,q0) z4=NAND(q2,o2) p2=NOR(m2,n0)
q2=NAND(j6,x2) o2=NAND(k1,n0) m2=NAND(q1,q2) j4=NAND(o2,j6) j6=NAND(x2,j4) l2=NAND(j4,q2)
x2=NAND(x,q2) k1=NOR(k2,j5) k2=NAND(l1,l2) j5=NAND(y,i5) i5=NAND(g3,j5) g3=NAND(d3,r0)
t8=NAND(z3,z4) b6=NOT(k2) q1=NOR(b6,i5) b4=NOT(g3) y1=NAND(b4,i5) k3=NAND(h3,y0)
o3=NAND(k3,p3) p3=NAND(y,o3) y3=AND(f3,o3) m3=NAND(p3,i6) i6=NAND(o3,k3) f9=NAND(i6,g9)
g9=NAND(x3,f9) x3=NAND(x,t9) l3=NAND(f9,e3) q3=NOR(l3,y0) z5=AND(g9,x3) k4=NAND(h3,n0)
o4=NAND(k4,p4) p4=NAND(n,o4) m4=NAND(p4,j9) n3=AND(f3,o4) j9=NAND(o4,k4) h9=NAND(j9,i9)
i9=NAND(b9,h9) b9=NOT(q4) q4=NOR(l4,n0) l4=NAND(h9,e3) z6=NOR(b8,q4) b8=NOT(i9) b7=NOT(e3)
e3=NOR(m3,m4) f3=NOR(a1,r0) h3=AND(d3,f3) t9=NAND(z5,z6) t6=NOR(t8,t9) v2=OR(p2,q3)
d3=NOR(b7,a1) a1=NAND(a,r) z7=NAND(l9,j7) l9=NAND(j7,k9) j7=OR(l5,y0) k9=NAND(q9,l9)
l5=NAND(k9,q5) q9=NAND(o5,k5) y4=AND(g4,o5) k5=NAND(i7,y0) o5=NAND(k5,p5) p5=NAND(y,o5)
m5=NAND(p5,q9) z8=NAND(m9,w3) m9=NAND(w3,o9) w3=NAND(w,z8) o9=NAND(p9,m9)
p9=NAND(o6,k6) o6=NAND(k6,p6) k6=NAND(i7,n0) p6=NAND(n,o6) q6=OR(l6,n0) l6=NAND(o9,q5)
m6=NAND(p6,p9) n4=AND(g4,o6) q5=NOR(m5,m6) z1=OR(z7,z8) i7=AND(q5,g4) g4=AND(d4,r0)
z0=NAND(q7,o7) q7=NAND(j0,w2) o7=NAND(k8,y0) j0=NAND(w2,i0) w2=NAND(w,q7) i0=NAND(o7,j0)
p7=NAND(i0,q7) l7=NAND(k7,q7) m7=OR(l7,y0) z9=NAND(q8,o8) q8=NAND(l0,m8) o8=NAND(k8,n0)
l0=NAND(m8,k0) m8=OR(l8,n0) k0=NAND(o8,l0) l8=NAND(k7,q8) p8=NAND(k0,q8) z2=NAND(z0,z9)
n1=NAND(f4,i8) k8=NOR(h4,j8) k7=NOR(c5,i8) c5=NOT(e4) i8=NAND(h4,j8) j8=NAND(n,i8) f4=NOR(a2,r0)
h4=NAND(d4,f4) e4=NAND(p7,p8) d4=NOR(e4,a2) a2=NAND(a,s) t7=NOR(z1,z2) u2=NAND(q6,m7)
t=NAND(t6,t7) y2=NOR(y3,y4) y=NAND(y1,y2) n2=NOR(n3,n4) n=NAND(n1,n2) g1=AND(d1,b)
t3=NAND(j2,x1) x1=NAND(x,t3) j2=NAND(e1,h1) e1=NOR(b1,i2) h1=NAND(d1,f1) b1=NOT(x1)
i2=NOR(b0,e1) f1=NOR(c1,b) b0=NOT(h1) d1=NOR(e1,c1) c1=NAND(c,r) t1=NOR(g1,t3) v1=NOR(i2,f1)
t4=NAND(j3,w1) j3=NAND(w1,i3) w1=NAND(w,t4) i3=NAND(g2,j3) g2=NAND(d2,b) u1=AND(i3,g2)
t5=AND(i4,h2) i4=NAND(h2,e2) h2=NAND(d2,f2) e2=NAND(f2,i4) f2=NOR(c2,b) c2=NAND(c,s)
d2=NOR(b2,c2) b2=NOT(e2) t2=NOR(t4,t5) t0=NAND(t2,t1) r=NAND(u,s) s=NAND(v,r) u=NOR(u1,u2)
v=NOR(v1,v2) x=NOR(v,r) w=NOR(u,s)
В хабе пишу, т.к. не знаю другого места куда умище приткнуть на русском языке. По англицки не пишу принципиально. А в этом хабе была статейка по асинхронике.