Как видно из цитаты проблема состоит из двух частей: операции над данными и операции над адресами. С адресами разберусь в следующей статье, а сейчас — данные.
Для примера попробую сделать схему разряда регистра, выполняющего две операции. Почему две? Потому что две, три операции или десять — принципиальной разницы нет. От увеличения количества операций увеличивается только объем вычислений при синтезе схемы. Главное, чтобы таких операций было более одной. В качестве операций выберу копирование из буфера и сложение с содержимым другого регистра.
Итак, попробую нарисовать поведение разряда такого регистра. Как понимаю, проблема описания поведения объекта (носителя информации) заключается в том, что он взаимодействует с другими объектами (носителями информации). И эти связанные объекты могут изменять свои значения произвольно (относительно описываемого объекта). Если связанных объектов 2, 3 и более, то описывать все возможные изменения таких объектов на языке STG занятие бессмысленное. Но есть выход. Достаточно ввести в STG три новых типа событий:
f? — с этого момента значение сигнала f не определено,
f/ — с этого момента значение сигнала f определено, и оно равно 1,
f\ — с этого момента значение сигнала f определено, и оно равно 0.
Очередность типов событий для одного сигнала такая:
после "+" — "-" или "?",
после "-" — "+" или "?",
после "?" — "/" или "\",
после "/" — "?" или "-",
после "\" — "?" или "+".
Используя новые типы событий можно описать поведение разряда регистра.
Входные сигналы:
a — команда на операцию прибавления значения второго регистра;
c — команда на операцию копирования из буфера;
r0 — значение соответствующего разряда второго регистра;
b — значение соответствующего разряда буфера;
y0 — сигнал переноса из младшего разряда при операции сложения;
n0 — сигнал отказа от переноса из младшего разряда при операции сложения.
Выходные сигналы:
r — значение разряда описываемого регистра;
t — сигнал завершения операции сложения;
t0 — сигнал завершения операции копирования;
y — сигнал переноса в старший разряд при операции сложения;
n — сигнал отказа от переноса в старший разряд при операции сложения.
Процесс исполнения команд по шагам выглядит так:
Копирование:
1. Внешняя управляющая схема (ВУС) вырабатывает сигнал c+. К этому моменту сигнал b устанавливается в одном из состояний (0 или 1).
2. Схема разряда регистра (СРР) вырабатывает сигнал t0+ для ВУС.
3. ВУС вырабатывает сигнал c-.
4. Если это необходимо, СРР меняет значение сигнала r на противоположное.
5. СРР вырабатывает сигнал завершения операции t0-. После этого ВУС может изменять значение сигнала b.
Сложение:
1. ВУС вырабатывает сигнал a+. К этому моменту сигнал r0 устанавливается в одном из состояний (0 или 1).
2. Если это возможно без использования информации о переносе из младшего разряда, СРР вырабатывает сигнал y+ или n+ для старшего разряда.
3. СРР дожидается из младшего разряда сигнал y0+ или n0+.
4. СРР вырабатывает для старшего разряда сигнал y+ или n+, если он еще не был сформирован.
5. СРР вырабатывает сигнал t+ для ВУС.
6. ВУС, собрав сигналы t+ со всех разрядов, вырабатывает сигнал a-.
7. СРР вырабатывает сигнал y- или n- для старшего разряда.
8. СРР дожидается сигнала y0- или n0- из младшего разряда.
9. Если это необходимо, СРР меняет значение сигнала r на противоположное.
10. СРР вырабатывает сигнал завершения операции t-. После этого ВУС может изменять значение сигнала r0.
Взаимодействие с младшим разрядом осуществляется опосредованно через ВУС. Введение прямого ответного сигнала для младшего разряда позволило бы запараллелить взаимодействие с ВУС и с соседними разрядами. Но для этой статьи я решил выбрать исходное задание попроще.
Казалось бы, задание составлено, можно приступать к синтезу схемы. Но не все так просто. Ни один из известных методов не способен для данного типа поведений синтезировать SI схему (даже если адаптирует новые типы событий). Более того, на мой взгляд ни один из методов не сможет это задание втиснуть в более менее приемлемую элементную базу.
Но, к счастью есть мой метод, который позволяет эти проблемы решить. Процесс корректировки исходного задания я здесь приводить не буду. Покажу лишь конечный результат. Для удобства восприятия покажу его на четырех отдельных картинках.
Копирование когда r=1.
Копирование когда r=0.
Сложение когда r=1.
Сложение когда r=0.
А теперь логические функции.
Как видно, схема синтезирована в базисе 2И-НЕ, 2ИЛИ-НЕ Задачу ограничения нагрузок на выходы элементов я не ставил. Но если каждый выход элемента ограничить двумя нагрузками, то схема увеличится процента на 2-3 (по моей оценке). А вот если ограничить входы схемы двумя нагрузками, то это задача посложнее. Тут я ожидаю увеличения схемы процентов на 25.
Комментарии (49)
yegorf1
25.07.2017 03:22Есть какой-то простой способ проверить, есть там ошибка или нет? 3 часа ночи, а тут…
ajrec
25.07.2017 19:45Да, это я как-то не учел. Думаю ни одна программа верификации, а тем более вычисления логических функций (т.к. все они работают через состояния), с таким количеством сигналов не справится. Я то работаю через события, для меня нет разницы 100 сигналов, 500 или 1000. Остается два пути. Либо научиться вычислять логические функции по графу событий, а этому нигде не учат. Либо моделирование. А оно не даст ответ на точное соответствие логических функций и итогового поведения. Хотя само моделирование пройдет без проблем, это по определению.
nckma
25.07.2017 13:56Сколько не пытался понять асинхронные схемы — никогда не понимал.
Как это вообще может работать?
Fragster
25.07.2017 16:46Я и классические не понимаю… попробовал http://www.kongregate.com/games/krispykrem/kohctpyktop-engineer-of-the-people — не смог пройти дальше 8 уровня
ajrec
25.07.2017 20:12Все в мире загадка. Хотел бы ответить как предыдущий автор, но даже не представляю откуда он вышел, и куда пришел.
32bit_me
25.07.2017 18:21+1Я не то, что бы вас критикую или упрекаю, но вы публикуете статью в хабе FPGA, при этом нет ни строчки HDL-кода, ни скриншотов симуляций, ни ссылок на исходники проекта.
Создаётся впечатление, что это просто перепечатка какой-то старой публикации.
Вы реально это запускали на симуляторе или на железе?ajrec
25.07.2017 20:09Нет, это не старая перепечатка. Это ответ на цитату в начале статьи. А ей не больше месяца. Саму схему я закончил полторы недели назад. Оставшееся время вбивал результат в компьютер. Всех вещей, о которых Вы пишите, нет, т.к. все сделано с помощью бумаги, ручки и текст-корректора. Ни на симуляторе, ни на железе ничего не запускал, т.к. руки коротки. Но есть уверенность и небольшой давний опыт, что все это проскочит на «Ура!».
В хабе пишу, т.к. не знаю другого места куда умище приткнуть на русском языке. По англицки не пишу принципиально. А в этом хабе была статейка по асинхронике.
Des333
25.07.2017 22:06Правильно ли я понял, что если написать это на Verilog (нарисовать в схемном редакторе), собрать прошивку и залить в ПЛИС, то оно должно заработать?
Если это так, то я бы ради интереса провёл такой эксперимент.ajrec
25.07.2017 22:11Должно работать в соответствии с исходным заданием. За эксперимент был бы очень признателен.
Des333
25.07.2017 22:08Нет ли у Вас схемы в базисах 2И-НЕ, 2ИЛИ-НЕ (или любом другом), но не картинкой, а текстом.
Так было бы проще скопировать.
Спасибо!ajrec
25.07.2017 23:00Щас напрягусь, выдам текст. Запись уравнений как на картинке устроит?
Des333
25.07.2017 23:14Да, вполне.
Спасибо!ajrec
26.07.2017 00:43z3=NAND(q0,o1) q0=OR(b3,p1) o1=NAND(k1,y0) b3=NOT(j1) p1=NOR(m1,y0) j1=NAND(b5,i1)
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)
32bit_me
26.07.2017 02:46-1По англицки не пишу принципиально.
И не читаете, как я понимаю, тоже из неких принципов?ajrec
26.07.2017 03:31Да я вообще только картинки рассматриваю.
Если серьезно, не очень хорошо я английским владею, чтобы писать. А так у меня есть пара застарелых публикаций на английском, но в соавторстве.32bit_me
26.07.2017 04:05Просто у вас нет никаких ссылок на литературу, ничего. Так делать не принято.
ajrec
26.07.2017 04:59Я в затруднении даже. Очевидно же, что асинхроника уже лет 20 пребывает в тупике. Причем очень глубоком. И завели ее туда все наши корифеи: от Маллера до Варшавского. А причина в том что они упорно изучали эту тему через модель состояний. Извлекать логические функции до сих пор учат по кубам. А сколько можно осилить переменных? Пять? С применением софта ситуация чуть лучше. Petrify осилит ну 25 сигналов. Дальше то тупик. С корректировкой поведения тоже похвастать нечем. CSC, dual-rail… В группе Варшавского был Стародубцев. Он предлагал изучать событийную модель. Но его идеи приняты не были.
На самом деле асинхроника проста. В ней нет ничего кроме причинно-следственных связей между событиями и двоичной логики, с помощью которой эти связи обеспечиваются. А лучший инструмент для исследования — простейшие логические функции: 2И-НЕ и 2ИЛИ-НЕ.
Так что ссылаться я могу только на Стародубцева. Но сейчас, кроме признания факта, что я являюсь его последователем, ничего интересного в его работах я порекомендовать не могу. А может я чего-то не знаю… Прошу прощения, если показался высокомерным. Это не так.32bit_me
26.07.2017 06:06-1У вас нет сравнений вашей реализации с синхронной схемой. Насколько ваша реализация лучше по ресурсам и по частоте?
ajrec
26.07.2017 06:58Вот честное слово, синхронной реализации я в глаза не видел. Может в такой конфигурации (2 операции) ее и нет, не знаю. Если бы кто подсказал, самому было бы интересно. А вообще целью статьи я считал просто в принципе сделать асинхронную схему.
valeriyk
27.07.2017 01:41-1Я бы лучше узнал, насколько лучше по энергопотреблению. Кому сейчас нужны ресурсы и частота, даже тупейший трехстадийный процессор можно разогнать до гигагерца на 16нм техпроцессе.
Khort
29.07.2017 00:31Корректно синхронные и асинхронные схемы сравнивать нельзя. Тем более, что асинхронных схем существует несколько разновидностей, и самосинхронные — только одни из.
Вот Вам пример, сравните две эквивалентных схемы:
1. Синхронный триггер, у которого выход замкнут на вход через инвертор
2. Три инвертора в последовательном включении, замкнутых в кольцо.
Первая схема — синхронная, вторая — самосинхронная, делают одно и то же — подают на вход инверсию выхода. Где будет больше частота?
Можно придумать и более сложные примеры, где синхронная реализация будет быстрее, а асинхронная медленнее (или наоборот), либо синхронная окажется больше по площади чем асинхронная (или наоборот). Т.е. вопрос сравнения «вообще» — некорректен, надо рассматривать каждый частный случай отдельно.
ajrec
26.07.2017 02:19Забыл добавить. Три новых типа событий ("?", "/" и "\") применимы только к входным сигналам.
Khort
29.07.2017 00:16Сергей, спасибо конечно, что назвали меня доктором наук, да еще компетентным. Последнее — может быть, а вот первое не так, увы — я простой к.т.н.
Теперь по делу. Вы вот пишете, что у сигнала есть три типа событий — ("?", "/" и "\"). Но в бинарной логике (и в классической цифровой электронике) у лог. сигнала возможно всего два состояния — 0 и 1. А Вы хотите получить 3 состояния. Варшавский с командой еще 40 лет назад нашли выход из положения — сигнал закодировали парой бинарных кодов: коды 01 и 10 соответствовали лог. 0 и 1 ("/" и "\" в Вашей интерпретации), а коды 11 и 00 они назвали служебными или спэйсером ("?" по-Вашему). Таким образом, сигнал передавался по двум проводам и в две фазы: служебной фазе ("?") и фазе данных ("/" или "\"). Чувствуете похожесть идеи? При этом, проектировать такие схемы методом Варшавского можно вообще без сетей Петри и Petrify, гораздо проще. Как? Слишком много печатать, читайте первоисточники. Впрочем, оказалось, что кодировать сигнал двумя проводами и вводить служебную фазу — ущербно, по ряду причин. Поэтому, революция отменяется, к сожалению. Но попытка засчитана.ajrec
29.07.2017 03:24Признаю, наверно, надо было на этом акцентировать внимание. Событие "?" ни в коем случае не дополнительное логическое значение. Значений сигнала как было так и осталось два: 0 и 1. Событие "?" означает, что с этого момента и до наступления события "/" (или "\") сигнал может произвольным образом менять свое значение: с 0 на 1 и обратно произвольное количество раз. А может и оставаться все это время без изменений. Т.е. событие "?" означает, что с этого момента у нас нет информации о поведении этого сигнала, кроме того что он ведет себя как обычный асинхронный сигнал.
В STG есть некий аналог такой ситуации. Например он присутствует в бенчмарке rcv-setup. Просто, когда таких сигналов с неопределенным поведением больше одного, описывать все это с помощью STG крайне неудобно.
Я вообще категорический противник введения всевозможных надстроек типа парафазности, трехзначной логики. Есть только двузначная логика реализации, и причинно-следственные связи между событиями. И все.
PS. Я пока претендую только на половинку революции.Khort
29.07.2017 09:41Событие "?" означает, что с этого момента и до наступления события "/" (или "\") сигнал может произвольным образом менять свое значение: с 0 на 1 и обратно произвольное количество раз.
Тогда это будет уже не полумодулярная схема, поскольку Вы множественные переходные процессы прячете под одним событием. Более того, это атрибут синхронных схем — маскировать переходные процессы в проводе сигналом управления.
Вот, посмотрите, как сделано у Варшавского: код фазы спэйсера 00 сменяется на код фазы данных (10 или 01), а затем снова входит в спейсер 00. Смена фаз дает монотонность, а значит и полумодулярность; данные могут спокойно меняться произвольным образом, поскольку между любым их изменением стоит разделитель.
ajrec
29.07.2017 21:28Алексей, действительно, Вы ухватили за самое чувствительное место. Но оно чувствительное не потому что слабое, а потому что крайне важное. Без решения этой проблемы вообще не было бы смысла писать статью.
Начну с начала. Мои нововведения с новыми типами событий это всего лишь более удобный способ описания некоторых типов поведений. И не более.
Вот простейший пример. a, b — входные, x, y — выходные. И слева, и справа — одно и тоже поведение. Только записано по разному. Именно только в этом и есть смысл нововведения.
Теперь по терминологии. Такие определения как полумодулярный, дистрибутивный я воспринимаю как внутренние термины приверженцев модели состояний. Для меня важное значение имеют термины SI, DI. Но если Вы подскажете, чем плохи неполумодулярные SI схемы, я намотаю на ус.
А теперь снова к рисунку. Важнейшая задача: построить для такого поведения SI схему в монотонном базисе (И-ИЛИ-НЕ). И хотя, несомненно, Варшавский был человеком крайне изобретательным, у меня очень большие сомнения, что в модели состояний можно логическим путем прийти к нужному результату. А вероятность случайного успеха крайне низка. В любом случае мне было бы интересно взглянуть на решение подобной задачки, если оно имеется.
В событийной модели задача решаема. Вот результат:
Поведение этой штуки такое:
В конце еще раз хочу сказать. Все эти "?", "/", "\" используются для описания исключительно входных сигналов. Причем эти сигналы являются не управляющими, а данными (например разряд второго регистра, как в статье).
Вернувшись к основной статье, можно сказать так. Представленная схема разряда регистра не отслеживает изменения состояний разряда буфера или разряда второго регистра. Лишь получив команду на операцию (копирования), а это значит что разряд буфера установился в определенном состоянии, схема выясняет в каком состоянии находится разряд буфера и в соответствии с этим выполняет свои действия.
Огорчительным во всем этом является факт, что подобного рода поведения невозможно реализовать DI схемой. Но квази-DI — всегда пожалуйста.Khort
30.07.2017 09:32Сергей, а Вы очень напрасно не разобрались с полумодулярностью, поскольку используете общепринятые графы. Суть полумодулярности — отсутствие состязаний (гонок, races, glitches). Посмотрите на свой левый граф первого рисунка: ветка b+x+b-x-b+… может циклически переключаться независимо от всей другой схемы (которая может вообще остановиться из-за задержки в одном из проводов). Или же, судя по графу, допустимо циклическое переключение а+а-а+а-… независимо от другой схемы. С такими независимыми сегментами графа в кружках могут накапливаться точки — а значит возможны состязания. Это не только не DI схема, но даже и не SI!
Что я могу сказать. Вы используете общепринятые графы, но читаете их как то по своему, видимо. А значит, мы говорим на разных языках. Это значит, что и Вы, возможно, не поймете мои аргументы выше. Могу посоветовать только разобраться с сетями Петри, как ими принято описывать СС, и если окажется что Вы читаете графы как то иначе, то подробно изложите, как их следует читать (хотя я предпочел бы иметь дело с традиционными графами). А может и сами ошибки у себя увидите.ajrec
30.07.2017 15:51Ох, Алексей, вижу Вы очень хотите меня уесть. И либо торопитесь, либо специально провоцируете. По левой верхней картинке. Представленная сеть Петри безопасная и живая. Ну нигде маркеры не накапливаются. Интерпретация тоже корректная. Вы сами можете засунуть этот граф в 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, или еще где, Вас не убедят. Вы будете говорить, что это подтасовка.
Желаю приятно провести вечер за разгадыванием этой загадки.Khort
30.07.2017 16:35Сергей, у меня никакого желания Вас уесть, поверьте. Как видите, я тут единственный, кто задает вопросы и высказывает сомнения. Мой интерес исключительно спортивный — самосинхронными схемами я больше не занимаюсь, поэтому докопать до истины для меня не есть дело принципа. Но пока существует диалог — почему бы и не поговорить?
По поводу графа и накопления точек, объясню свою позицию еще раз, кратко. Представьте что в левом верхнем графе здесь несколько раз отрабатывает нижняя часть b+ x+ b- x-, а верхняя арка а+ а- не работает (или там внезапно случилась огромная задержка). Поскольку нижняя часть отработала несколько раз, в а+ накопятся точки. Отсюда следуют и состязания, и несоответствие классу SI, и все остальное, о чем я писал выше. Что Вас в этом смущает: что арка а+ а- может «залипнуть», или что в а+ в случае залипания начнут накапливаться точки?Khort
30.07.2017 17:47p.s. Загнал схему в воркрафт, был не прав касательно накопления точек. Признаю.
Тем не менее, петрифай подтвердил что схема не полумодулярна.
Синтез дал следующее:
assign a = (~a | b | x) & a | ~a & ~b & ~y;
assign b = ~x & ~y | b & ~x & ~y;
assign x = a & b | b & x;
assign y = ~a & b | b & y;
Итого, получилась какая то асинхронная схема, но не самосинхронная. Что с этим делать и как использовать, мне не понятно. Но что то в этом есть, наверное. За сим, с критикой завязываю.ajrec
30.07.2017 18:47По всей видимости Вы не учли, что 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.Khort
30.07.2017 19:21Это синтез в MPSat (входит в пакет воркрафт), петрифай вообще отказался работать с такой схемой. Про этот тул мне ничего не известно, кроме того что это альтернатива петрифаю.
что переключать после b+: x+ (если a=1), или y+ (если a=0).
Должно учитываться, ведь это следует из графа. Хотя, за MPSat ручаться не буду — раньше я только петрифаем пользовался.
Размышлял, почему петрифай не считает этот граф полумодулярным. Накопления точек нет, граф безопасный — это выяснили. Второе условие полумодулярности — живая сеть, и вот тут нашла коса на камень. С одной стороны, все переменные могут переключаться. С другой — могут и не переключиться. К примеру, если точка не будет попадать в нижнюю часть графа, то Y вообще не будет переключаться. Что из это следует. Условие полумодулярности — это представление состояний автомата в виде алгебраической структуры с верхней и нижней гранью. Верхняя и нижняя грани означают, что есть конечное число смен состояний графа от начальной маркировки, за которое все переменные переключатся хотя бы один раз в 1 (+) и один раз в 0 (-). А здесь получается, что верхней грани нет. Поэтому живая или не живая эта сеть, но она точно не полумодулярна. И вот тут возникает опасный момент. Если мы имеем дело с полумодулярными схемами, то их свойство DI доказано математикой (возможностью представить автомат полумодулярной алгебраической структурой — это фактически независимость от задержек). А если схема не полумодулярна, как у Вас, то где гарантия независимости от задержек? Вы попадаете на необходимость доказывать DI-свойство своей схемы, пробел в теории однако…Khort
30.07.2017 19:35Еще один момент. Вы ведь хотите получить схему — фаргмент графа со сходами а,b и выходами x,y, но вынуждены замыкать схему, чтобы получить автомат. Т.е. достраиваете избыточное окружение для замыкания. Из этого следует, что полумодулярность может нарушаться и в замыкании — Вы просто неправильно достроили часть графа, отвечающую за внешнюю среду. Но может быть и так, что неполумодулярность заключается в части схемы между а,b и x,y. Так что надо поработать еще с замыканием графа — может быть и получится сделать его полумодулярным за счет внешней части. Но формула x=AND(b,a) y=AND(b,!a) тут никак не получается, мне кажется.
ajrec
31.07.2017 03:32Я понял почему Вы так пишите. Вы наверно коллега Плеханова Л.П. Тогда Вы наверно считаете, что событийный подход предполагает работу только с автономными схемами (поведениями). Отсюда и достраивание избыточного окружения для замыкания.
Я считаю, что лезть во внешнюю среду и вредно, и не зачем. Заменять причины для входных событий, значит менять исходное задание. Требование автономности, это уже перебор. Ну просто посчитайте логические функции для внутренних и выходных сигналов, а для входных не надо. Ими внешняя среда занимается. А что Вы будете делать, если поведение с выбором, по определению оно недетерминированное в отношении входных сигналов.
А схемку еще раз посмотрите, там SI в полный рост.Khort
31.07.2017 08:40Сергей, я не коллега Плеханова, хотя знаком — встречал пару раз, несколько лет назад.
По поводу замыкания. Во-первых, Вы ведь сами замкнули граф(!). Без внешней среды должны получиться только отдельные треки зависимостей входных переменных от выходных, а у Вас все замкнуто — входы на выходы. Почему Вы его замкнули? Второе: все известные тулы вроде петрифая работают только с замкнутыми графами, видимо — по той же причине что и Ваш алгоритм. Мне приходилось проектировать самосинхронные защелки — для их проверки в петрифае пришлось выдумывать внешнюю обвязку схемы, чтобы полный замкнутый граф получился полумодулярный. В принципе, идея понятна, поскольку проектируемая схема все равно предназначена для использования в неком самосинхронном окружении, чью полумодулярность она не должна нарушать. Поэтому делается заглушка, эмулирующая это окружение, и вполне логично что с этой заглушкой проверяемая схема должна получиться полумодулярной. Если же Вы предлагаете использовать неполумодулярную заглушку, то как судить о том, что разрабатываемая схема не испортит полумодулярности конечной схемы, в которой она должна быть использована потом?
Таким образом, Вам надо либо самому перестать замыкать граф, и придумать какое то доказательство, что полученная синтезом схема будет полумодулярна, когда ее встроят в общую схему (где она будет использоваться в дальнейшем), либо доказать полумодулярность разрабатываемой схемы при том, что заглушка неполумодулярна. Либо — делать как все, т.е. замыкаемый граф обязан быть полумодулярным.
По поводу опредления полумодулярности — я его сформулировал выше. Суть сводится к тому, что у Вашего графа (с учетом замыкания) нет верхней грани. На самом деле, я допускаю, что требование верхней грани может оказаться избыточным — Маллер, Варшавский, и последователи тоже могли ошибаться. В таком случае, это дырка в теории самосинхронных схем, и Вам надо ее закрыть математикой, раз уж Вы этой (гипотетической) дырой решили воспользоваться.
С другой стороны, я ведь не комиссия по науке, а просто высказываю свое мнение. И тоже могу ошибаться, поскольку самосинхронными схемами занялся сравнительно недавно — 4 года назад, всего лишь. Наверное, Вам лучше пообщаться с корифеями — Мараховским, Стародубцевым, Кондратьевым, Яковлевым… да Вы их и так знаете всех.ajrec
31.07.2017 19:04Ну не может тут быть никаких дыр в теории. Я ничего нового не делаю. Все же вставляют новые сигналы (хотя бы для того, чтобы CSC разрулить). Те же авторы Petrify подвели под это теоретическую базу. Я пользуюсь этим же механизмом добавления новых сигналов (тут надо различать цель добавления сигналов и собственно сам механизм добавления). Единственная новизна заключается в том, что после моего добавления логические функции всех сигналов вписываются в минимальный базис (2И-НЕ, 2ИЛИ-НЕ).
Если Вы хотите отменить мои схемы, то Вам придется отменить все: и Мараховского, и Стародубцева, и Кондратьева, и Яковлева. Ну честное слово, Вы раздуваете слона, где и мухи нет. По Вашему выходит, что и такое поведение невообразимая проблема.
a, b — входные, x, y — выходные. Логические функции: x=a, y=b.ajrec
31.07.2017 19:12А заглушки это вообще какой-то древнейший атавизм. Я последний раз о них слышал лет 25 назад.
ajrec
31.07.2017 02:52Настал мой черед каяться. Напрягся и вспомнил, что такое полумодулярность. «Если сигнал возбудился, он обязан переключиться». Архиважнейшее свойство. Конечно же все мои схемы вписываются в этот критерий. Просто за давностью лет и многолетним отсутствием практики, я подзабыл что это свойство именуется так. Я считал это требование совершенно естественным, и не акцентировал на нем внимание.
А теперь по Вашим вопросам. Надо разделять полумодулярность схемы и полумодулярность внешней среды. Полумодулярность схемы обеспечивает независимость от задержек элементов. А вот полумодулярность внешней среды — требование излишнее и даже вредное. Так Вы не сможете реализовать выбор. При выборе возбуждаются 2 сигнала (входных), а срабатывает один. Грубо говоря, не мое дело как среда обеспечивает нужный порядок входных сигналов. Мое дело сделать схему, правильно реагирующую на эти сигналы.
PS Делать схемы с недетерминированным поведением внутренних и выходных сигналов, ну это вообще ужос.
Khort
30.07.2017 09:38Вот что я могу еще посоветовать. Графы в этом последнем примере небольшие, их можно засунуть в Петрифай. Можете сами убедиться, что они небезопасны. Петрифай можно взять из пакета Workraft — под линукс или виндос, я об этом писал здесь https://habrahabr.ru/post/306056/. Я понимаю, что синтез в Петрифай Вы не приемлете, но проверку на полумодулярность почему бы не сделать.
ajrec
31.07.2017 05:54Алексей, кажется начинаю понимать суть Ваших претензий.
Полумодулярность. Обязательна для внутренних и выходных сигналов. Для входных — вредна, поскольку безосновательно сужает класс рассматриваемых поведений.
SI. Независимость от скорости обеспечивается алгоритмом вычисления логических функций. Алгоритм исходит из предположений:
1. Задержка провода нулевая, т.е. каждое событие становится известно любой части схемы моментально.
2. Задержка внешней среды и любого элемента произвольна, т.е. произвольна задержка любого события.
Логические функции строятся так, чтобы обеспечить переключение сигнала при срабатывании всех событий-причин.
В итоге получается схема, обеспечивающая заданную последовательность переключений вне зависимости от задержек элементов схемы и задержек внешней среды.Khort
31.07.2017 09:05Небольшое уточнение, полумодулярность — это свойство замкнутого автомата, а не отдельных фрагментов. Когда говорят о полумодулярности фрагмента, то это жаргон: имеется ввиду, что этот фрагмент можно замкнуть внешним окружением до полного автомата, и уже полный автомат будет самосинхронным.
ajrec
31.07.2017 19:39Ну тогда все эти автоматы с полумодулярностями надо снести на помойку. А оставить одно нормальное требование: Внутренние и выходные сигналы не могут снимать возбуждение без переключения. Как Вы собираетесь эмулировать среду при выборе. Вы не сможете эмулировать произвольный порядок выбора альтернативных ветвей. Вы сможете эмулировать только один единственный жестко зафиксированный порядок. Или Вам надо сделать бесконечное количество эмуляций. Зачем цепляться за автомат, выдуманный не от хорошей жизни, если проку от него немного? За 40 лет можно было бы развить из него что-либо стоящее? Значит идея тупиковая.
valeriyk
помнится, его еще лет двадцать с лишним назад сделали.
ajrec
Насколько я понимаю, речь тогда шла о локализации тактового сигнала. И о асинхронном взаимодействии между компонентами.
ajrec
В этой статье я пытаюсь показать, что в асинхронном виде можно сделать все, т.е. полностью отказаться от тактового сигнала.
32bit_me
http://www.computer-museum.ru/technlgy/asynproc.htm
Например, ARM Handshake.